デッドロック

デッドロックとは

複数の処理が、それぞれ何らかの資源（ロック・メモリ・ファイル・デバイスなど）を握ったまま、互いに相手が握る資源を待ち合う と、誰も次へ進めなくなります。この膠着状態が デッドロック です。

古典的な例が「ロックを取る順番の食い違い」です。

スレッド1: lock(A) 取得 → lock(B) を待つ（2が持っている）
スレッド2: lock(B) 取得 → lock(A) を待つ（1が持っている）
→ 互いに永久に待つ＝デッドロック

どちらも相手が手放すのを待ち続けるため、外から介入しない限り自力では解けません。

発生の4条件（Coffman条件）

デッドロックは、次の 4つが同時に成り立つとき にのみ発生します。逆に言えば、どれか1つでも崩せば防げます。

条件	意味
相互排他	資源は同時に1つの処理しか使えない
保持と待機	資源を握ったまま、別の資源を待つ
横取り不可	他者が握る資源を強制的に奪えない
循環待ち	待ち関係が輪を描く（A→B→…→A）

「資源の割り当て状況」を矢印で図にした 資源割り当てグラフ に 閉じた輪（サイクル） が現れることが、循環待ちの目印になります。

予防（Prevention）

4条件のいずれかを 構造的に成立させない のが予防です。

• 保持と待機を崩す：必要な資源を最初に まとめて確保 し、揃わなければ何も握らずに待つ。
• 横取り不可を崩す：取得できなければ、いま持っている資源を一度手放して やり直す。
• 循環待ちを崩す：全資源に 番号（順序） を付け、必ず番号の小さい順に取得 する。

実務で最も効くのが循環待ちの排除です。ロック取得順をコードベース全体で一本化すれば、輪が閉じません。

ルール: ID が小さい資源から先にロックする
スレッド1: lock(min(A,B)) → lock(max(A,B))
スレッド2: lock(min(A,B)) → lock(max(A,B))
→ 両者とも同じ順で取るので循環しない

回避（Avoidance）と検出（Detection）

回避 は、資源を割り当てる 直前に「割り当てても安全か」を判定 し、危険なら割り当てを遅らせる手法です。各処理が将来必要とする資源の最大量が分かっている前提で、常に安全状態を保てるかを調べる 銀行家アルゴリズム が代表例です。ただし最大需要を事前申告する必要があり、汎用OSでは現実的でないことが多いです。

検出と回復 は、デッドロックの発生を許したうえで、定期的に資源割り当てグラフを調べて サイクルを検出 し、見つかったら回復させる方針です。回復策には、

• 巻き込まれたプロセスの 強制終了（被害が小さいものから）
• 資源を一度 横取り して別の処理に回す
• 安全な時点まで ロールバック する

などがあります。データベースは多くがこの方式で、デッドロックを検出すると一方のトランザクションを犠牲者として中断します。

まとめ

• デッドロックは、互いの資源を待ち合って 誰も進めなくなる 膠着状態。
• 4条件（相互排他・保持と待機・横取り不可・循環待ち） がすべて揃うと発生し、1つ崩せば防げる。
• 対策は 予防・回避・検出と回復 の3方向。実務では 取得順序の統一 が最も効く。

排他制御そのものの基礎は 排他制御とデッドロック、切り替えの仕組みは プロセスとスレッド も合わせてどうぞ。