0 / 4
デッドロック（Deadlock）
デッドロックは、二つ以上のプロセスが互いに占有している資源を待ち、どれも先に進めない状態だ。相互排除、保持と待機、横取り不可、循環待ちの四つの条件がすべて成立したときにだけ起きる。
例：P1がR1を、P2がR2を先に割り当てられるところから始まる。誰が何を占有し要求しているかは矢印で描く。このような図を資源割り当てグラフという。
1 / 4
相互排除（Mutual Exclusion）
R1はP1に、R2はP2に割り当てられた。プリンターとスキャナーは一度に一つのプロセスしか使えない。他のプロセスは一緒に使えず、資源が解放されるまで待つしかない。
2 / 4
保持と待機（Hold and Wait）
P1はR1を占有したままR2を要求して待つ。P2もR2を占有したままR1を待つ。どちらもすでに占有した資源は返さない。
3 / 4
横取り不可（No Preemption）
横取り（プリエンプション）は、他のプロセスが使っている資源をOSが強制的に取り上げることだ。横取り不可は、そうして取り上げないことだ。資源は、占有しているプロセスが仕事を終えて自分で返したときにだけ解放される。
4 / 4
循環待ち（Circular Wait）
P1はP2が占有するR2を、P2はP1が占有するR1を待つ。待ちが輪（閉路）になり、どちらも先に終われない。資源が一つずつしかないので、待ちの輪はそのままデッドロックだ。二つのプロセスは止まったままになる。
1 / 4
規則1：相互排除を崩す
読み取り専用ファイルのように本来一緒に使える資源には、相互排除はいらない。しかしプリンターは、二つのプロセスが同時に印刷すると結果が混ざるので、一度に一つしか使えない。そのため相互排除はふつう崩しにくい。この規則では、図のようにデッドロックを防げない。
2 / 4
規則2：保持と待機を崩す
必要な資源を、実行前にまとめて要求させる。占有している資源をすべて返してからでないと新しく要求できないようにする方法もある。P1がR1とR2を一緒に割り当てられて終えるまで、P2は何も占有せずに待つ。その代わり、使っていない資源まで占有するので無駄が出る。必要な資源がすべて空くのを待ち続け、いつまでも実行されない飢餓状態も起こりうる。
3 / 4
規則3：横取り不可を崩す
さらに資源を要求してすぐに割り当てられなければ、占有していた資源をすべて返させる。P2が先にR1を要求したとしよう。P2はR1をすぐに割り当てられないので、R2を返す。その後、R1とR2の両方を得られるまで再び待つ。この規則は、CPUのレジスタやメモリのように状態を保存して戻せる資源に使う。プリンターやスキャナーには使いにくいので、図は規則がどう当てはまるかだけを示す。
4 / 4
規則4：循環待ちを崩す
すべての資源の種類に番号を付け、番号の小さい種類から順に要求させる。プリンターR1が1番、スキャナーR2が2番なので、P2もR1から要求しなければならない。P2がR1を待つあいだR2は空いているので、P1がすぐ割り当てられる。だから待ちが輪にならない。
1 / 5
必要な資源を前もって伝える
P1とP2は実行を始めるとき、これからR1とR2の両方が必要だとOSに伝える。こうして前もって伝えた量を最大要求量という。OSは要求が来るたびに、この値で結果を前もって確かめる。
2 / 5
P1のR1要求：安全なので割り当てる
P1がR1を要求する。割り当てても、P1が後でR2まで割り当てられて終わり、その次にP2が終わる順序がある。安全状態なのでR1を割り当てる。
3 / 5
P2のR2要求：不安全なので保留
P2がR2を要求する。R2は空いているが、割り当てるとP1はR2を、P2はR1を待つことになりうる。どちらも終われる順序が一つもない不安全状態だ。だからR2を割り当てず、P2を待たせる。不安全状態は、それ自体がデッドロックではない。デッドロックにつながるおそれのある状態だ。
4 / 5
P1のR2要求：安全なので割り当てる
P1がR2を要求する。割り当てるとP1は必要な資源をすべて占有し、すぐに終われる。P1が返した資源でP2も終われる。安全状態なのでR2を割り当てる。
5 / 5
P1が終わりP2の番
仕事を終えたP1がR1とR2を返す。待っていたP2のR2要求をもう一度検査すると、今度は安全なのでR2を割り当てる。続けて要求したR1も割り当てる。P2も必要な資源をすべて得て、デッドロックなしで終われる。
1 / 4
検査なしで割り当てる
回避とちがい、要求が来れば空いている資源を検査なしですぐ割り当てる。P1はR1を、P2はR2を割り当てられる。
2 / 4
デッドロックの発生
P1がR2を、P2がR1を要求し、互いに待つ。四つの条件がすべて成立してデッドロックが起きたが、OSはまだ気づいていない。
3 / 4
検出アルゴリズムの実行
検出アルゴリズムは、どのプロセスがどの資源を待ち、その資源を誰が占有しているかを矢印に沿ってたどる。要求にすぐ応じられないたびに実行すると負荷が大きい。そのため、ふつうは決めた間隔ごとか、CPU使用率が大きく下がったときに実行する。
4 / 4
輪の発見
P1から出発し、R2、P2、R1を経て再びP1に戻る輪を見つけた。資源が種類ごとに一つなら、輪があればそのままデッドロックだ。同じ種類の資源が複数あると、輪があってもデッドロックでないことがあるので、別の検出アルゴリズムを使う。
1 / 5
犠牲者を選ぶ
輪を断ち切るプロセス（犠牲者）を選ぶ。優先度、これまで実行した時間、占有している資源の数を見て、止めたときの損失が最も小さいものを選ぶ。この図では、これまでの実行時間が短いP2を選ぶとしよう。
2 / 5
P2が占有するR2を解放する
方法は二つある。P2を強制的に終了させるプロセス終了と、P2が占有するR2だけを取り上げる資源の横取りだ。どちらでもR2が解放され、待ちの輪が断ち切られる。
3 / 5
P1が進む
待っていたP1がR2を割り当てられて実行される。
4 / 5
P1が終わり返す
仕事を終えたP1がR1とR2を返す。これで二つの資源がどちらも空いた。
5 / 5
P2の再実行
P2を終了させたなら、最初からもう一度実行する。資源を取り上げたなら、R2を割り当てられる前の状態に戻してから（ロールバック）再び実行する。同じプロセスばかり犠牲者に選ばれると、いつまでも実行されない飢餓状態に陥る。そのため犠牲者を選ぶときは、これまで犠牲者になった回数もあわせて考える。