操作して学ぶ
銀行家アルゴリズム可視化
互いに相手の資源を待ち合って全員が止まる——それがデッドロック。銀行家アルゴリズムは、資源要求を仮に割り当ててみて全員が終われる順序が残るかを先に確かめ、残らない要求を拒否します。 教科書（Silberschatz）の5プロセス×3資源の例で、危険な要求が弾かれる様子を確かめてください。
安全状態実行順序の一例: P1 → P3 → P4 → P0 → P2
Available（空き資源）
A:3B:3C:2
| プロセス | Allocation（保有） | Max（最大宣言） | Need（残り必要） | |
|---|---|---|---|---|
| P0 | [0 1 0] | [7 5 3] | [7 4 3] | |
| P1今すぐ実行可 | [2 0 0] | [3 2 2] | [1 2 2] | |
| P2 | [3 0 2] | [9 0 2] | [6 0 0] | |
| P3今すぐ実行可 | [2 1 1] | [2 2 2] | [0 1 1] | |
| P4 | [0 0 2] | [4 3 3] | [4 3 1] |
資源を要求する
がを要求
銀行家アルゴリズムは、要求をいったん仮に割り当ててみて、その状態から全プロセスを終わらせられる順序が1つでも残るかを調べる。 残らなければ取り消して待たせる。だからデッドロックに「陥ってから直す」のではなく「陥らせない」。 代償は、各プロセスが最大必要量を事前に宣言する必要があることと、安全側に倒すので資源の利用率が下がること。
読み方のコツ
- Need = Max − Allocation：あと何を貰えれば終われるか。これが Available 以下なら、そのプロセスは今すぐ最後まで走れる。
- 安全状態＝全員を終わらせる順序が1つでもあること。順序が1つでもあれば、最悪その順に走らせれば詰まらない。
- 拒否には2種類ある：単に空きが足りない（待てばよい）のと、承認すると安全な順序が消える（＝デッドロックの危険なので取り消す）。後者が銀行家アルゴリズムの本体。
- 試すなら：初期状態で P1 が (1,0,2) を要求すると承認される。その後 P0 が (0,2,0) を要求すると、空きはあるのに「安全でなくなる」として拒否される。
現場ではどう扱うか
- 予防：一番よく使う手は循環待ちを崩すこと＝ロックを常に同じ順序で取る。DBでもアプリでも効く定石。
- 回避（このアルゴリズム）：最大必要量を事前宣言できる場面でしか使えず、安全側に倒すため利用率が落ちる。教科書の主役だが実務での採用は限定的。
- 検知と復旧：DBが実際に使う手。待ちグラフの循環を見つけ、片方を犠牲者としてロールバックする（デッドロック検知エラー）。
- 無視：滅多に起きないなら再起動で対処（ダチョウ算法）。多くの汎用OSの実質的な既定。