デッドロック

プロセスの集合 $D \ne \emptyset$ がデッドロックしているとは、$D$ のどのプロセスも、$D$ の別のプロセスが保持している資源の解放を待っており、その解放が起こり得ない状態をいう。待ちグラフ（wait-for graph）を、頂点をプロセス、辺 $P \to Q$ を「$P$ が要求している資源を $Q$ が保持している」と定めた有向グラフとする。