TL;DR
プロセスとリソースの関係を表す有向グラフ。OS がデッドロックを検出するのに使う。
仕組み
各エッジ（矢印）は、プロセスがどのリソースを要求または保持しているかを表す。
- プロセス → リソース: そのプロセスがそのリソースを要求している
- リソース → プロセス: そのリソースをそのプロセスが保持している
グラフに循環があれば、デッドロックが起きている。
デッドロック検出アルゴリズム
必要なリソースをすべて保持しているプロセスは、他のプロセスに依存せず、今あるリソースだけで終了できるので、グラフから取り除ける。そのプロセスが終了すれば、保持していたリソースが解放される。
次に終了できるプロセスを見つけて、同じ手順を繰り返す。こうして段階的にプロセスを取り除き、最終的にすべてのプロセスを取り除ければ、デッドロックは起きていない。