デッドロックの四条件と検出・回避

デッドロックとは「全員が永遠に待ち合う」膠着

デッドロック（deadlock）とは、複数のスレッドやプロセスが互いの保持する資源を待ち合い、誰も前進できなくなる膠着状態です。典型はロック2本の交差取得です。スレッドAが資源1を保持して2を待ち、スレッドBが2を保持して1を待つ——双方が相手の解放を待つため、外部介入がなければ永遠に止まります。重要なのは、これが運やタイミングの問題ではなく、特定の条件が揃ったときにのみ起こる構造的現象だという点です。だから条件を一つ崩せば必ず防げます。下地となるロックの仕組みはスレッド同期プリミティブの内部で押さえておくと理解が速くなります。

Coffman の四条件：すべて揃って初めて起きる

デッドロックが成立するには、Coffman（1971）が定式化した次の4条件がすべて同時に成立することが必要です（4条件はデッドロックの必要条件）。

この4条件は AND 条件です。つまりどれか一つでも恒久的に崩せば、デッドロックは原理上発生しません。デッドロック対策がすべて「この4条件のどれを、いつ崩すか」という一枚の地図に整理できるのが、この定式化の威力です。予防（prevention）は4条件のいずれかを設計時に常に崩す戦略、回避（avoidance）は条件は許しつつ危険な割当を実行時に拒む戦略、検出と回復（detection & recovery）は起きてから片づける戦略です。

資源割当グラフによる検出

検出の基礎は**資源割当グラフ（Resource Allocation Graph, RAG）**です。プロセスと資源をノードにし、有向辺で関係を表します。

• 割当辺（資源 → プロセス）：その資源がそのプロセスに割り当てられている。
• 要求辺（プロセス → 資源）：そのプロセスがその資源を要求して待っている。

資源が各種1個ずつ（単一インスタンス）の場合、判定は明快です。グラフに有向閉路があれば、それがそのままデッドロックを意味します。先のA・Bの交差は「A → 資源2 → B → 資源1 → A」という閉路を成します。閉路の検出は有向グラフのサイクル検出そのものなので、DFSで back edge（後退辺）を見つければよい。グラフ探索の原理はグラフ探索の原理（BFS・DFS）に整理しています。

ただし資源が複数インスタンス（同種の資源が複数個、例：3個あるメモリブロック）の場合は、閉路は必要条件であって十分条件ではありません。閉路があってもデッドロックでないことがある。この場合は閉路探索ではなく、次に述べる「割当を畳み込んでいく」reduction で判定します。

# 複数インスタンス資源のデッドロック検出（reduction）
# Work := 現在利用可能な各資源の本数ベクトル
# Finish[i] := プロセス i が完了可能か
for each process i: Finish[i] = false
loop:
  Finish[i] == false かつ Request_i <= Work を満たす i を探す
  見つからなければ終了
  Work = Work + Allocation_i   # i は完了し、保持資源を返すと仮定
  Finish[i] = true
# 終了後、Finish[i] == false が残るプロセス集合がデッドロック状態

直感は「いまある空き資源で要求を満たせるプロセスがいれば、そいつは完了して資源を返す」と仮定し、返ってきた資源で次のプロセスを満たせるか——を繰り返すことです。最後まで満たせず残ったプロセス群が、互いに待ち合って詰んでいます。

銀行家アルゴリズムによる回避

回避は「デッドロックを起こしうる割当を、起きる前に拒否する」戦略です。代表が Dijkstra の銀行家アルゴリズム（Banker's Algorithm）で、各プロセスが将来必要とする最大要求量を事前申告することを前提にします。銀行家アルゴリズムの中核概念が**安全状態（safe state）**です。

銀行家アルゴリズムは、資源要求が来るたびに「その要求を仮に許可した結果の状態が安全列を持つか」を安全性アルゴリズムで判定し、安全なら許可、危険なら（資源が物理的にあっても）プロセスを待たせます。安全性判定は前述の reduction と同型で、Need = Max - Allocation（残り必要量）を使います。

# 安全性アルゴリズム（状態が安全か判定）
Work = Available            # 各資源の空き本数ベクトル
Finish[i] = false  (全 i)
loop:
  Finish[i] == false かつ Need_i <= Work を満たす i を探す
  見つからなければ break
  Work = Work + Allocation_i   # i が完走し保持分を返すと仮定
  Finish[i] = true
return すべての Finish[i] == true ?  # true なら安全状態

Need_i <= Work は「プロセス i の残り必要量が現在の空きで賄える」を、各資源種ごとに成分比較した条件です。すべての成分で満たす必要があります。安全列が組めれば安全、組めなければ危険と判定します。

実務の主役：ロック順序付けとタイムアウト

実務でデッドロックを潰す最有力の手は、循環待ちを構造的に消すロック順序付け（lock ordering）です。プログラム中の全ロックにグローバルな全順序を定義し、各スレッドは常にその昇順でのみロックを取得するよう徹底します。

# 全ロックに番号（順序）を付ける： lockA < lockB < lockC ...
# どのスレッドも、必ず番号の小さい順に取得する
acquire(lockA)   # 例：常に A → B の順。B → A は禁止
acquire(lockB)
...              # クリティカルセクション
release(lockB)
release(lockA)

なぜこれで防げるのか。循環待ちが成立するには「Aを持ってBを待つ者」と「Bを持ってAを待つ者」が同居する必要がありますが、全員が昇順でしか取らないなら、Bを持つ者は既にBより前のAを取り終えており、Aを後から待つことがありえません。待ちグラフに環が作れず、4条件のうち循環待ちが恒久的に崩れるわけです。Linux カーネルの lockdep は実行時にロック取得順序を学習し、矛盾する順序が現れた瞬間に警告を出して、この規律違反を検出します。

順序付けが難しい場面（取得すべきロックが実行時に決まる等）では、タイムアウトと**try_lockが現実解になります。ロックを無限に待たず、一定時間で諦めて、既に取得済みのロックをすべて解放し、間を空けて最初からやり直す。これは「横取り不可」を実質的に崩す回復策です。データベースの世界では、各トランザクションの待ちを待機グラフ（wait-for graph）で監視し、閉路を検出したら片方のトランザクションを犠牲者（victim）として強制ロールバック**して環を断ち切るのが定石です。

予防・回避・検出をどう使い分けるか

四条件のどれを崩すかで戦略が決まります。相互排他を崩すのは資源が読み取り専用・不変なときに限られ（並行性モデルのSTMや不変データはこの方向）、汎用には使えません。保持と待機を崩す一括取得は、必要資源を最初に全部押さえる方式で確実ですが、長時間ロックを占有し並行度を落とします。横取り不可を崩すのはDBのロールバックやタイムアウト解放、循環待ちを崩すのがロック順序付け——という対応です。

汎用OSの多くは、実は回避も検出もコストに見合わないとして**何もしない（ostrich algorithm、ダチョウ戦略）**を採り、起きたら再起動で済ませます。一方DBやリアルタイム系では検出と回復が必須です。

まとめ

デッドロックは、(1) Coffman の四条件（相互排他・保持と待機・横取り不可・循環待ち）がAND同時成立したときにのみ起き、一つ崩せば必ず防げる、(2) 検出は資源割当グラフの閉路探索（単一インスタンスは閉路＝デッドロック、複数インスタンスは reduction）、回避は銀行家アルゴリズムで安全状態を保つ、(3) 実務の本命はロック順序付けで循環待ちを構造的に消すこと、回復にはタイムアウトと待機グラフ＋victimを使い、ライブロックを避けるためリトライにjitterを入れる——という三層で整理できます。「どの条件を、設計時に崩すのか実行時に崩すのか起きてから崩すのか」が一貫した判断軸です。