デッドロック

デッドロック（英: deadlock）とは、複数の処理単位が互いの終了を待ち続け、結果としてどの処理も進まないことである。

また、合弁契約書などにおいてパートナーと利害関係がぶつかるような問題が生じた場合の解決方法を定めた条項を「デッドロック条項（Deadlock Clause）」と言う。英語ではもともと行き詰まりの意味である。

古い文献では、デッドロックのことをチェス用語と同様のステイルメイトと呼称して説明をしている場合がある^[1]。

プログラム上の例

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

基本的にデッドロックは資源数が2以上の場合に発生する（たとえばクリティカルセクションが1つあれば資源は1つと数えられる。2つのクリティカルセクションがあれば資源数は2である）。資源数が1の場合、セマフォ等はバイナリセマフォとなり、振る舞いはミューテックスと同じになるのでデッドロックは発生しない（ライブロックする。これを回避する方法は数多く考案されており、たとえばCSMA/CDでは乱数を用いて回避する）。

資源数を1にすることは、デッドロックを回避する根本的な解決方法であるが、その場合プログラムの並列性は著しく損なわれるため、現代のコンピュータープログラミングにおいて現実的な手段とは言えない。資源を多数用い、なおかつデッドロックを回避する手段については以下に述べる。

例

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

処理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へ入ることに失敗
CSBの解放を待機	CSAの解放を待機
デッドロックの発生

回避方法

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

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

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

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

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

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

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

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

Lock-free での回避

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

交通での例

日本の兵庫県加古川市加古川町には、兵庫県道148号線の道中に、4方向に止まれ標識がある十字路がある。3方向に同時に車両が来た場合については、道路交通法第36条で、交差点中心を見て左側の車両を優先的に通過させるよう定められている。しかしながら、4方向に同時に車両が来た場合について明確な定めはない。なお、兵庫県警察は同件の取材者に対し、身振り手振りで意思疎通し、徐行しながら通り過ぎることを推奨する見解を提示している。 https://kuruma-news.jp/post/574471

脚注

^ J.DONOVAN 1972, p. 393-395,475.

参考文献

J.DONOVAN, JOHN (1972). systems programming. ISBN 0-07-085175-1