デッドロック
出典: フリー百科事典『ウィキペディア（Wikipedia）』
デッドロック(Dead lock)とは排他制御の欠陥で、2つ以上のスレッドあるいはプロセスなどの処理単位が互いの処理終了を待ち、結果としてプログラムが停止してしまうことを言う。 英語では行き詰まりの意味がある。
プログラムが複雑になっていくと原因不明のバグとして発生しやすいため、マルチスレッドのプログラムを書くときは注意が必要である。
目次 |
[編集] 例
クリティカルセクションで排他制御を用いた場合の例をあげる。
ここに変数Aと変数Bの二つのデータと、BにAの値を加算し、Aを0にする処理AとAにBの値を加算し、Bを0にする処理Bの二つの処理があったとする。マルチスレッドで処理をするため変数Aと変数BにアクセスするためのクリティカルセクションA（以下CSA）とクリティカルセクションB（以下CSB）の二つのクリティカルセクションを用意する。
処理Aは以下の手順であるとする。
- CSAに入る
- CSBに入る
- BにAの値を加算
- Aに0を代入
- CSBから出る
- CSAから出る
また同様に処理Bは以下の手順であるとする。
- CSBに入る
- CSAに入る
- AにBの値を加算
- Bに0を代入
- CSAから出る
- 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にアクセスする”というミューテックスを用いる
- クリティカルセクションに入れない場合は、既に入っているクリティカルセクションから出て処理を終了するようにする
他にも様々な回避方法が存在する。
優先度上限プロトコル機能が拡張されたミューテックスを利用することでも、デッドロックを回避することが可能である。優先度上限プロトコルは組み込みシステムで主に使われ、使うことで効果があるプログラムも限定的であり、汎用的に使える方法ではない。
[編集] オブジェクト指向での回避方法
以下、JavaやC#などのオブジェクト指向言語での話である。
オブジェクト指向では、クラス間の依存関係を単方向にし、クラス間の依存関係の構造が階層構造になるように設計するのが、必須ではないものの定石である。en:Hierarchy (object-oriented programming)。ここでは、独立している方を下と定義する。つまり、上の階層のクラスは、下の階層のクラスについて知っている。下の階層のクラスは、上の階層のクラスについて知らない。上の階層のクラスから、下の階層のクラスへの呼び出しは、普通のメソッド呼び出しで行う。下の階層から、上の階層に戻すときは、Observer(Listener)デザインパターンを使う。階層構造をとる、軍隊での比喩にたとえると、メソッド呼び出しが上官からの命令であり、Observerパターンが部下の上官への報告である。
そして、デッドロックを回避するには、ロックをかけるオブジェクトのクラスの順番を統一するというのが一つの方法である。そして、クラスの依存関係が階層構造になっているときは、必ず、上の階層のクラスから順番にロックをかけるということで統一する。そうすると、上の階層でロックをかけたまま、下の階層のオブジェクトのメソッドを呼び出すことが可能になる。軍隊の比喩でいうと、上官が部下よりも先にリソースを独占する。
また、Observerパターンで上の階層に戻す場合は、自分のかけているロックを全て解放してから、上の階層に戻す。そうすることにより、「下の階層でロック→上の階層でロック」の発生を防げる。また、同じ階層同士ではロックをかけない。それが必要な場合は、上の階層でロックをかける。
こうすることにより、オブジェクト指向でデッドロックが回避できる。
[編集] Lock-free での回避
Lock-freeとWait-freeアルゴリズムでもデッドロックを回避できる。
[編集] 関連項目
 |
この「デッドロック」は、コンピュータに関連した書きかけです。この記事を加筆して下さる人を求めています。（Portal:コンピュータ） |
