OSのデッドロック（資源割当グラフと4条件）
複数プロセスが互いのリソース解放を待ち合って永遠に止まる「デッドロック」の発生と回避を可視化します。
📌デッドロックとは — 永遠に止まる状況
デッドロック（deadlock、膠着状態）とは、複数のプロセスが互いのリソース解放を待ち合って永遠に進めなくなる状態のことです。「動けないのに動けない原因が他の動けないプロセス」という不思議なロック状態が発生します。
身近な例えだと、「狭い橋で出会った2人」のような状況です。お互いに「どけ」と要求しあい、相手がどくのを待っていてどちらも進まない ── これがデッドロック。譲り合いや交通整理（OS の介入）がないと永遠に解決しません。
上のツール「デッドロック発生」シナリオを ▶ 再生すると、ステップ5で P1 と P2 が互いに待ち合う様子を確認できます。
📌デッドロックの4条件
| 条件 | 内容 |
|---|---|
| ① 相互排除 | リソースは同時に1プロセスしか使えない（排他制御をかけている） |
| ② 保持と待機 | リソースを保持しつつ、別のリソースを待っている |
| ③ 横取り不可 | 他プロセスのリソースを強制的に奪えない |
| ④ 循環待ち | 待ち関係が環状（P1→P2→...→Pn→P1）になっている |
デッドロックは4 つの条件がすべて成立したときに限り発生します（Coffman 条件）。逆に言えば、このうち 1 つでも成立させなければデッドロックは起きないのがポイント。
上のツール「デッドロック発生」のステップ 5 で、4 条件すべてが揃った瞬間（循環矢印が完成）にデッドロックが宣言される様子を確認できます。
📌資源割当グラフで検出する
デッドロックを検出する代表的な手法が資源割当グラフ（Resource Allocation Graph）です。プロセスとリソースをノードとし、関係を有向矢印で表します。
矢印の意味：
・R → P（割当）：リソース R が プロセス P に割当てられている
・P → R（要求）：プロセス P がリソース R を要求して待っている
グラフを描いて循環（サイクル）があれば、それがデッドロックの正体です。上のツール「デッドロック発生」シナリオのステップ 5 で、P1 → R2 → P2 → R1 → P1 という循環が赤くハイライトされる様子を確認できます。
📌デッドロックを防ぐ — 4条件を崩す
| 崩す条件 | 防止策の例 |
|---|---|
| 相互排除 | 共有可能なリソース（読み取り専用ファイル等）にする |
| 保持と待機 | 必要なリソースを最初に全部取得する（一括確保） |
| 横取り不可 | OS が強制的にリソースを取り上げる（高優先度プロセスに譲らせる） |
| 循環待ち | 取得順序を全プロセスで統一する（番号順に取る） |
デッドロックを事前に防ぐ戦略は、4 条件のいずれかを成立させないことです。実用上は「循環待ちを崩す」のが最も使われます。
典型的なベストプラクティス：リソースを取得する順序をプロジェクト全体で統一する（例: アカウントID の若い順、ロックの番号順）。上のツール「デッドロック回避」シナリオで、R1 → R2 の順を守ればデッドロックが起きないことを確認できます。
📌対処戦略 — 防止・回避・検出
デッドロックへの対処戦略は大きく3 つに分類されます。
・防止（Prevention）：4 条件のいずれかを構造的に成立させない。取得順序の統一など
・回避（Avoidance）：実行時に「リソース割当しても安全か」を判定して、危険なら拒否。銀行家のアルゴリズムが代表
・検出と回復（Detection & Recovery）：起きてから検出して、片方のプロセスを強制終了するなどで回復
銀行家のアルゴリズムは「銀行員が融資を承認する前に、全顧客の最大借入を考えて安全に貸せるか判断する」というアナロジーで、Edsger Dijkstra が提唱しました。「銀行家のアルゴリズム＝デッドロック回避」と整理して覚えておくと分かりやすいです。
📌デッドロック vs ライブロック vs 飢餓
| 用語 | 状況 |
|---|---|
| デッドロック | 互いに待ち合って停止。一切動かない |
| ライブロック | 動いているのに進まない。お互いに譲り合って何も完了しない |
| 飢餓 | 特定プロセスだけが永遠に CPU・リソースを得られない |
混同しがちな用語ですが、性質は違います。
ライブロックの身近な例：「狭い廊下で出会った2人」。お互いに「お先にどうぞ」と譲り合って何度も同じ動きを繰り返し、結局すれ違えない状態。動いているのに進まない、というのがデッドロックとの違いです。
飢餓は、優先度方式で「常に高優先度のプロセスが来る」場合に、低優先度プロセスが永遠に CPU を得られない問題です。デッドロックやライブロックとは区別して理解しておきましょう。
