デッドロックの原因と防止設計
デッドロックは、複数のタスクがロックを握ったまま互いに待ち続け、処理が進まなくなる停止状態です。設計段階で循環待ちを作らないのが最も確実です。
複数のタスクが同時に動作する組み込みシステムでは、いったんはまると再起動でしか復帰できないことも多く、テストでは再現しにくい不具合です。
この記事では、デッドロックが起きる仕組みを整理した上で、設計とレビューの段階で芽を摘む具体策まで解説します。
- デッドロックとは｜資源を持ったまま次の資源を待つ状態
- デッドロックが成立する4つの必要条件（Coffman 4条件）
- 組み込みで起こる典型的なデッドロック事例
- 予防設計｜4条件のうち1つを崩す
- 検出と再現の手法
- 設計チェックリスト｜レビュー段階で防ぐ
デッドロックとは｜資源を持ったまま次の資源を待つ状態
デッドロックは、複数のタスクが排他資源を握ったまま、互いに相手の解放を待ち続けて処理が止まる状態です。RTOS（Real-Time Operating System：リアルタイムOS）上でミューテックスやセマフォを使う場面で起こりやすく、規模が大きくなるほど検出や管理が難しくなります。
組み込みで排他の対象になるのは、I2C（Inter-Integrated Circuit：集積回路間通信）やSPI（Serial Peripheral Interface：シリアル周辺インタフェース）のバス、フラッシュへの書き込み経路、共有の状態変数など、同時に1つの文脈からしか触れない資源です。複数のタスクがこうした資源を2つ以上またいで使い始めると、待ちの関係がこじれる余地が生まれます。
この記事では用語を次のとおり使い分けます。共有資源は上記のような資源を指します。排他手段はミューテックスで、実装により優先度継承を備えます。同期手段はセマフォ（バイナリ／カウンティング）、キュー、タスク通知です。ロックという語は、排他、つまりミューテックスによる保護を指すものとして使います。
組み込みで起きやすい2タスク＋2ミューテックスの例
たとえば、センサ制御タスクAがI2Cバス（Mutex1）を押さえてからログ用フラッシュ（Mutex2）を要求し、記録タスクBが先にフラッシュ（Mutex2）を押さえてからI2Cバス（Mutex1）を要求するとします。
ふだんは順番がずれて問題なく流れますが、AがMutex1を、ほぼ同時にBがMutex2を取得した瞬間に互いが相手の資源を要求すると、そこで止まります。どちらも自分の資源を手放さないまま相手を待つので、時間がたっても抜け出せません。時間で追うと、t0でAがMutex1を取得しBがMutex2を取得、t1でAがMutex2を待ちBがMutex1を待つ状態になり、ここで循環待ちが成立します。
優先度逆転との違い
優先度逆転は、高優先度のタスクが低優先度のタスクに間接的に足止めされる現象で、低優先度側が資源を手放せばいずれ処理は前に進みます。一時的な遅れにとどまるわけです。
この現象に対してデッドロックは、関係するタスクがそろって停止し、外から介入しない限り自力では回復しません。両者は対策が異なります。
優先度逆転の「再現→検出→対策」までの記事もあわせてご参照ください。
デッドロックが成立する4つの必要条件（Coffman 4条件）
防止策を理屈で押さえるには、成立条件を知っておくと近道です。1971年に提唱された4つの必要条件（Coffman 4条件）が土台になります。この4つは必要条件であり、すべてそろったときだけ起こりえます。裏を返せば、どれか1つでも成立しないように設計すれば、資源デッドロックは原理的に起きません。
相互排除・保持と待ち
相互排除（mutual exclusion）は、資源が一度に1つの文脈からしか使えない状態です。保持と待ち（hold and wait）は、資源を握ったまま別の資源の解放を待つ状態を指します。デバイスなどのハードウェア資源は排他型のことが多く、この2つに当てはまりやすいといえます。
あるデバイスを1つのタスクが占有している間、他は待つしかなく、その待っている側がすでに別の資源を握っていれば、保持と待ちが同時に成立します。
横取り不可・循環待ち
横取り不可（no preemption）は、割り当てた資源を外部から強制的に取り上げられない状態です。ミューテックスは保持しているタスク自身が解放するまで奪えません。循環待ち（circular wait）は、AはBを、BはCを、CはAを待つように、待ちの関係が輪のようにつながった状態を指します。
この輪さえできなければ停滞は起こらないため、循環待ちを生まないように取得順を制約するのが有効な対策になります。
組み込みで起こる典型的なデッドロック事例
見落としやすいパターンを2つ取り上げます。どちらも個々のコードは正しく見えるのに、組み合わさった瞬間に輪ができるのが共通点です。
事例1：ネスト取得順の不ぞろいで循環が生まれる
あるドライバがロックをB、Aの順で取り、別のドライバがA、Bの順で取るコードが同居すると、循環待ちが生まれます。ロックの取得順はコード全体で守るべき慣習にすぎず、コードベース全体と呼び出し関係を理解していないと、たった1箇所の食い違いを見落としやすいのが厄介です。
事例2：割り込みハンドラ内でミューテックスを取ろうとする落とし穴
割り込みハンドラ（ISR：Interrupt Service Routine）の中からミューテックスを取ろうとすると、タスクと割り込みハンドラの間で待ちが成立し、処理が進まなくなります。問題はミューテックス取得そのものではなく、待ちを伴うブロッキングAPIをISRから呼ぶ点にあります。ISRでは通知（セマフォの解放、キューへの送信、タスク通知）に限定し、排他を伴う実処理はタスク側でおこなうのが定石です。
予防設計｜4条件のうち1つを崩す
代表的な対策を3つあげます。最初の2つは4条件のどれかを崩す直接的な予防策、3つ目は待ちを緩和する補完的な対策です。
資源の取得順序を一意に決める
すべての資源にロックID（固定の序列）を設計で定義し、必ず昇順で取得すると決めます。全コードで同じ順序に統一すれば、取得の向きが一方向にそろい、循環待ちが原理的に起こらなくなります。実装例としては、ロックのアドレスの小さいほうから取る方法もあります。ただしアドレスはビルド設定・リンク順・配置やLTO（Link Time Optimization：リンク時最適化）の影響を受けるため、序列は設計側で固定するほうが確実です。複数ロックを同時に持つ箇所では、この順序を破っていないかをレビューの必須項目にすると効果が続きます。
タイムアウト付きロックで待ち時間を切る
RTOSが提供するロック取得APIの多くは、取得のタイムアウトを指定できます。決めた時間内に取れなければあきらめてエラー処理へ抜け、必要なときは保持していた資源も解放するため、保持と待ちの状態を崩せます。抜けた後にリトライすれば、輪ができかけてもほどけます。
ただし、タイムアウトが満了すると取得は失敗として戻るため、資源の最悪ブロッキング時間を見積もって値を決めます。
優先度継承ミューテックスで優先度逆転も緩和する
ミューテックスを保持している間、待ち状態にある高優先度タスクの優先度を保持側が一時的に引き継ぐ仕組みです。低優先度タスクが資源を早く手放せるようになり、高優先度タスクの足止めが短くなります。
優先度逆転による停滞を避けるには役立ちますが、循環待ち（circular wait）を解消できないため、デッドロックの予防策にはならない点に注意が必要です。優先度継承ミューテックス間でデッドロックが起きると、関係するタスクの優先度が連鎖的に引き上げられ、システム全体を巻き込む停止を招くおそれもあります。
検出と再現の手法
テストで見つけにくいデッドロックを、体系立ててあぶり出す方法を紹介します。
RTOSトレースで待ち関係を可視化する
RTOS対応のトレースツールで、タスクごとのロック取得と解放をタイムラインに並べます。どのタスクが何を持ち、何を待っているかが時系列で見えるため、待ちの循環を目で追えます。停止した瞬間のトレースを残せば、どの2つの資源が輪を作ったかを後から特定できます。
静的解析でロック取得順の不一致を洗い出す
商用の静的解析ツール（モデル検査ツールなど）で、広範な実行順序の組み合わせを検証し、デッドロックに至る命令の順序を洗い出します。動的テストは実際に通った経路しか確かめられませんが、静的解析は分岐を網羅できるため、めったに通らない経路での順序の食い違いも実装前に見つけられます。
設計チェックリスト｜レビュー段階で防ぐ
デッドロックは、起きてから直すよりも起きない前提で設計するほうが、手間もコストも抑えられます。レビューで確認したい観点を2つあげます。
ロック粒度と保持時間を絞る
読み取りだけであればロックはいらないのではないか、取得と解放の区間を短く保てないか、といった問いをレビューのたびに投げかけます。
ロックを持ったままI/Oや別のブロッキング呼び出しをしていないかにも注意が必要です。触る範囲を狭めて持つ時間を短くするほど、他のタスクを待たせる時間が減り、競合そのものが起こりにくくなります。
割り込みからは直接ロックを取らずキュー経由にする
割り込みハンドラとタスクの間にキューを1段はさむと、割り込みは通知を送るだけで済みます。割り込みハンドラはブロックするロック取得ができないため、資源アクセスを受け取ったタスク側に一本化すれば、割り込みハンドラとタスクがロックを奪い合う構造そのものをなくせます。誰がいつ資源を握るかが追いやすく、後から保守する人にとっても読みやすい形に近づきます。
