デッドロック回避と銀行家アルゴリズム

デッドロックの4条件と「同時成立」の意味

/os/deadlock/で扱う通り、デッドロックは次のCoffman条件が 同時に成立 したときに のみ 発生します。重要なのは「同時に」という点で、4つは独立した必要条件であり、どれか1つを恒常的に崩せば発生は不可能になります。

• 相互排他：資源は同時に1プロセスしか使えない。
• 保持と待機：資源を保持したまま別の資源を待つ。
• 横取り不可：保持中の資源を強制的に奪えない。
• 循環待ち：待ち関係が輪を描く。

この4条件は「必要条件の連言」であって、4つ揃えば必ず即デッドロックという十分条件ではない点に注意が要ります。十分性まで言えるのは資源の構造を限定したときで、それを与えるのが次の資源割当グラフです。

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

資源割当グラフ（RAG）は、プロセスと資源を頂点とする有向グラフです。P→R は「P が R を要求中」（要求辺）、R→P は「R が P に割り当て済み」（割当辺）を表します。

各資源タイプが 1インスタンスしか持たない 場合、グラフ中の サイクルの存在がデッドロックの必要十分条件 になります。サイクルが循環待ちそのものを意味し、単一インスタンスでは待ち相手が一意に定まるため、輪が閉じれば全員が永久に待つからです。

P1 → R1 → P2 → R2 → P1   （サイクル）
意味: P1はR1を待ち、R1はP2が保持、P2はR2を待ち、R2はP1が保持
→ 単一インスタンスならこれは即デッドロック

資源タイプが 複数インスタンス を持つ場合は話が変わります。サイクルがあっても、輪の外のプロセスが資源を返せば待ちが解けることがあるため、サイクルは必要条件ではあっても十分条件ではありません。複数インスタンスでの正確な判定には、グラフの単純な巡回ではなく、次節の行列ベースの解析が必要になります。

安全状態と銀行家アルゴリズム

回避（avoidance） は、デッドロックの発生を許さず、資源を割り当てる 直前 に「割り当てても安全か」を判定して危険なら保留する戦略です。中核概念が 安全状態（safe state） です。

安全状態とは、全プロセスを最後まで完走させられる実行順序（安全列）が少なくとも1つ存在する 状態を指します。安全列 <P_a, P_b, ...> とは、各 P_i の残り最大需要が「現在の空き資源＋それより前に並ぶプロセスが返す資源」で必ず賄える並びのことです。安全列が1つでもあればデッドロックには陥り得ません。逆に安全列が存在しない状態を 危険状態（unsafe） と呼びます。危険状態は「必ずデッドロックする」ではなく「デッドロックし得る」状態である点が肝心です。

銀行家アルゴリズムは、各プロセスが将来要求し得る 最大需要 を事前申告している前提で、次の3行列を保持します。

• Max：各プロセスの資源タイプ別の最大需要。
• Allocation：現在の割当量。
• Need = Max - Allocation：今後要求し得る残量。

そして空きベクトル Available を起点に安全性判定を行います。

安全性判定（Safety Algorithm）:
  Work = Available
  Finish[i] = false （全プロセス）
  繰り返す:
    「Finish[i]=false かつ Need[i] <= Work」な i を探す
    見つかれば:
      Work = Work + Allocation[i]   （i が完走して資源を返す）
      Finish[i] = true
    見つからなければ終了
  すべての Finish[i]=true なら安全状態（その探索順が安全列）

資源要求 Request[i] が来たら、まず仮に割り当てた状態（Available -= Request, Allocation += Request, Need -= Request）を作り、その状態が安全なら割当を確定、危険なら 要求を保留してプロセスを待たせます。要求自体は妥当でも、安全性を保てないなら待たせる——ここが防止と決定的に違う点です。

回避・防止・検出・無視の設計判断

4つの戦略は、コストとシステム前提のトレードオフで選びます。

防止 で実務上最も効くのは循環待ちの排除、すなわちロック取得順序の全域的な統一です。全資源に番号を振り昇順でのみ取得すれば、待ちの輪は決して閉じません。カーネル内のロックも/os/kernel-locking-primitives/で順序規約として徹底されています。

回避 が汎用OSで使われない理由は明確です。第一に、最大需要を事前に正確申告できるアプリはほぼ無く、第二に、プロセス・資源タイプが動的に増減する環境で毎回の安全性判定はコストが高すぎます。回避が成立するのは、タスクと資源が設計時に固定される組込み・リアルタイム系に限られます。関連して固定優先度下のロック競合は/os/priority-inversion-inheritance/の優先度上限プロトコルが、上限規則によってデッドロックを構造的に防ぐ点で回避と検出の中間的な性格を持ちます。

検出と回復 はDBが代表で、デッドロックを許したうえで待ちグラフ（waits-for graph）のサイクルを検出し、巻き戻しコストの小さい一方を犠牲者として中断・ロールバックします。発生頻度が低くロールバック機構が元々ある世界では、これが最も合理的です。

無視 は驚くほど広く採られています。LinuxやWindowsの汎用カーネルは、ユーザー空間アプリ同士のデッドロックを一般には検出しません。発生確率の低さと、回避・検出の常時コストを天秤にかけた結果「起きたら再起動」に委ねる判断で、頭を砂に埋めるダチョウになぞらえ ostrich algorithm と呼ばれます。

まとめ

• デッドロックは4条件の同時成立で発生し、単一インスタンス資源では資源割当グラフのサイクルが必要十分条件、複数インスタンスでは必要条件のみとなる。
• 銀行家アルゴリズムは Need・Allocation・Available から安全列の存在を判定し、仮割当が危険状態を生むなら妥当な要求でも保留して回避する。
• 4戦略は防止（ロック順序統一）・回避（安全性判定）・検出（DBの犠牲者中断）・無視（ostrich）であり、最大需要申告の可否と常時コストで使い分ける。
• 回避は資源が静的な組込み/RTOSに限られ、汎用OSは防止と無視を主軸に置く。基礎は/os/deadlock/、ロック競合の周辺は/os/concurrency-control/も参照。