デッドロック

計算機科学において、デッドロック (英: deadlock) とは、2つ以上のスレッドあるいはプロセスなどの処理単位が互いの処理終了を待ち、結果としてどの処理も先に進めなくなってしまうことを言う。英語ではもともと行き詰まりの意味である。

デッドロックが発生する原因

基本的にデッドロックは資源数が2以上の場合に発生する（たとえばクリティカルセクションが一つあれば資源は１つと数えられる。二つのクリティカルセクションがあれば資源数は２である）。資源数が1の場合、セマフォ等はバイナリセマフォとなり、振る舞いはミューテックスと同じになるのでデッドロックは発生しない（ライブロックする。これを回避する方法は数多く考案されており、たとえばCSMA/CDでは乱数を用いて回避する）。資源数を1にする事はデッドロックを回避する根本的な解決方法であるが、その場合プログラムの並列性は著しく損なわれ、現代のコンピュータープログラミングにおいて現実的な手段とは言えない。資源を多数用い、なおかつデッドロックを回避する手段については以下に述べる。

例

クリティカルセクションで排他制御を用いた場合の例をあげる。

ここに変数Aと変数Bの二つのデータと、BにAの値を加算し、Aを0にする処理AとAにBの値を加算し、Bを0にする処理Bの二つの処理があったとする。マルチスレッドで処理をするため変数Aと変数BにアクセスするためのクリティカルセクションA（以下CSA）とクリティカルセクションB（以下CSB）の二つのクリティカルセクションを用意する。

処理Aは以下の手順であるとする。

1. CSAに入る
2. CSBに入る
3. BにAの値を加算
4. Aに0を代入
5. CSBから出る
6. CSAから出る

また同様に処理Bは以下の手順であるとする。

1. CSBに入る
2. CSAに入る
3. AにBの値を加算
4. Bに0を代入
5. CSAから出る
6. CSBから出る

この場合は以下のようにプログラムが動作するとデッドロックが発生する。

処理Aを実行するスレッドAが生成され、処理が開始する。処理Aの1でCSAに入った直後にコンテキストスイッチが発生し、処理Bを実行するスレッドBが生成され、処理Bの1でCSBに入る。そして再びコンテキストスイッチが発生しスレッドAがアクティブになり、2でCSBに入ろうと試みる。しかし、スレッドBが既にCSBに入っているためスレッドAは待機状態に入り、スレッドBがアクティブになる。スレッドBは同じく2でCSAに入ろうと試みるがスレッドAが既にCSAに入っているためスレッドBは待機状態に入ってしまう。

こうして両方のスレッドが待機状態になり、プログラムが停止してしまう。これがデッドロックである。

以上の処理を時間に沿ってまとめたものが以下の表である。

スレッドA	スレッドB	CSAの所有者	CSBの所有者
スレッド発生
処理Aを開始
CSAに入る		スレッドA
コンテキストスイッチ A→B
待機	スレッド発生
	処理Bを開始
	CSBに入る		スレッドB
コンテキストスイッチ B→A
CSBへ入ることに失敗	待機
コンテキストスイッチ A→B
CSBの解放を待機	CSAへ入ることに失敗
	CSAの解放を待機
デッドロックの発生

回避方法

以上のようなデッドロックを回避するには以下のような方法がある。

• CSAとCSBに入る順番を二つの処理で同じにする
• “変数Aと変数Bにアクセスする”というミューテックスを用いる
• クリティカルセクションに入れない場合は、既に入っているクリティカルセクションから出て処理を終了するようにする

他にも様々な回避方法が存在する。

優先度上限プロトコル機能が拡張されたミューテックスを利用することでも、デッドロックを回避することが可能である。優先度上限プロトコルは組み込みシステムで主に使われ、使うことで効果があるプログラムも限定的であり、汎用的に使える方法ではない。

オブジェクト指向プログラミングでの回避方法

オブジェクト指向プログラミングでは、クラス間の依存関係を単方向にし、クラス間の依存関係の構造が階層構造になるように設計するのが、必須ではないものの定石である。en:Hierarchy (object-oriented programming)。ここでは、独立している方を下と定義する。つまり、上の階層のクラスは、下の階層のクラスについて知っている。下の階層のクラスは、上の階層のクラスについて知らない。上の階層のクラスから、下の階層のクラスへの呼び出しは、普通のメソッド呼び出しで行う。下の階層から、上の階層に戻すときは、Observerパターンを使う。階層構造をとる軍隊にたとえると、メソッド呼び出しが上官からの命令であり、Observerパターンが部下の上官への報告である。

そして、デッドロックを回避するには、ロックをかけるオブジェクトのクラスの順番を統一するというのが一つの方法である。そして、クラスの依存関係が階層構造になっているときは、必ず、上の階層のクラスから順番にロックをかけるということで統一する。そうすると、上の階層でロックをかけたまま、下の階層のオブジェクトのメソッドを呼び出すことが可能になる。軍隊の比喩でいうと、上官が部下よりも先にリソースを独占する。

また、Observerパターンで上の階層に戻す場合は、自分のかけているロックを全て解放してから、上の階層に戻す。そうすることにより、「下の階層でロック→上の階層でロック」の発生を防げる。また、同じ階層同士ではロックをかけない。それが必要な場合は、上の階層でロックをかける。

こうすることにより、デッドロックを回避できる。

Lock-free での回避

Lock-freeとWait-freeアルゴリズムでもデッドロックを回避できる。

関連項目

• 排他制御
• クリティカルセクション
• セマフォ
• マルチスレッド
• スレッド
• 食事する哲学者の問題
• ダチョウ・アルゴリズム
• SPINモデルチェッカ - 形式手法によりシステムがデッドロックに陥らないことを検証できるモデル検査ツール

テンプレート:Asbox