デッドロックとは？ - 1日10分で学ぶOS 8日目

サムネイルは、リソースを保持して互いに待つプロセスが輪になったデッドロックの様子を、GPTに描いてもらったものです。中央がリソースでしょうか。ずいぶん立体的な回路ですね（笑）。 コンピューターが突然止まり、応答しなくなったとき、原因は*デッドロック（deadlock）*かもしれません。デッドロックとは、複数のプロセスが互いのリソースを待って、です。 今回は発生条件から解決策まで、順に整理します。技術面接でもよく出るため、例とともに正確に理解することが大切です。

デッドロックとは、2つ以上のプロセスがリソースを保持したまま、相手の持つリソースを待ち続け、どちらも先に進めなくなる状態です。 例えば、P1がプリンターを、P2がスキャナーを保持し、それぞれが相手の装置を要求して待つと、両方とも止まってしまいます。

P1はプリンターを保持し、P2はスキャナーを保持しています。P1はP2のスキャナーを、P2はP1のプリンターを待ちます。このように互いの進行を妨げる状態がデッドロックです。

デッドロックは、次の4条件がすべて満たされたときに発生します。

1つでも成立しなければデッドロックは発生しません。そのため、少なくとも1つの条件を崩すことが解決の手がかりになります。

Coffman条件のうち1つが方法です。

プロセスから要求が来たら、それを許可してもシステムが安全状態にとどまるか確認してから許可します。代表例は*銀行家のアルゴリズム（Banker's Algorithm）*です。 銀行が融資の申請を受けたとき、全体の資金が不足するおそれを計算して、承認するか判断するのに似ています。

デッドロックの発生を許しつつ、システムを定期的に調べて検出します。 *リソース割り当てグラフ（Resource Allocation Graph）待ちグラフ（Wait-for Graph）*を使います。 検出アルゴリズムはシステムに負荷をかけることがあるため、利用には注意が必要です。

デッドロックを検出してから、システムを正常な状態に戻します。主な方法は次のとおりです。

スレッドを使う場合にもデッドロックはよく起きます。例えばJavaで、2つのスレッドが別々のオブジェクトのロックを取り、互いに相手のオブジェクトを待つと、デッドロックになることがあります。

// Thread 1
synchronized(objA) {
  synchronized(objB) {
    // 작업
  }
}
// Thread 2
synchronized(objB) {
  synchronized(objA) {
    // 작업
  }
}

対策として、ロックを取る順序を固定したり、タイムアウトを設定したりします。

今回は、デッドロックの意味と発生条件、予防、回避、検出、回復という代表的な対処方法を例とともに整理しました。 技術面接では、定義を覚えているかに加え、を問われることが多いため、条件や対策を実際の状況に結び付ける練習が大切です。 これで長かったプロセス編は終わりです。次回は、コンピューターのメモリの基本となるの構造を学びます。