デッドロック：資源グラフに輪ができる

プロセスと資源の「要求」「割当」の矢印を引いて、資源割当グラフに閉路（輪）ができた瞬間にデッドロックが発生することを体感します。

OS では複数のプロセス（P1, P2…）が複数の資源（R1, R2…）を奪い合います。
割当辺 R → P：資源 R が今プロセス P に渡っている。要求辺 P → R：プロセス P が資源 R を欲しがって待っている。
この有向グラフ（資源割当グラフ）に閉路ができると、互いに相手の持つ資源を待ち続けて誰も進めなくなる＝デッドロックです。
※ 各資源が 1 個ずつ（単一インスタンス）のとき、閉路の存在 = デッドロックが成り立ちます。

プロセス数 3

資源数 3

辺の種類を選んでから、ノードを2つクリックすると辺を引きます

クリック待ち：辺の始点となるノードを選んでください。

辺の本数

閉路（輪）

なし

状態

安全

凡例

プロセス（円）
資源（四角・中の●は実体）
━▸ 要求辺 P→R（待っている）
━▸ 割当辺 R→P（持っている）
━▸ 閉路に含まれる辺

いまの辺（クリックで削除）

（まだ辺がありません）

資源割当グラフ（ノードをクリックして辺を引く・ドラッグで移動）

単一インスタンスでは　閉路あり　⇔　デッドロック

いま何が起きている？

ここがポイント

循環待ち ── 各プロセスが「次のプロセスが持つ資源」を待つ輪ができるとデッドロック。
閉路 ⇔ デッドロック は各資源が1個ずつ（単一インスタンス）のときに厳密に成立する。複数インスタンスでは閉路は「必要条件」にすぎない。
輪を断ち切る（=辺を1本外す＝資源を1つ解放／要求を取り下げる）と、待ちが解けて再び進めるようになる。
デッドロックの4条件（相互排他・保持と待機・横取り不可・循環待ち）のうち、このグラフは循環待ちを可視化したもの。安全状態の判定（銀行家アルゴリズム）は別の話題。