デッドロック (英: deadlock) とは、特に計算機科学において、2つ以上のスレッドあるいはプロセスなどの処理単位が互いの処理終了を待ち、結果としてどの処理も先に進めなくなってしまうことを言う。また、合弁契約書などにおいてパートナーと利害関係がぶつかるような問題が生じた場合の解決方法を定めた条項を「デッドロック条項（Deadlock Clause）」と言う。英語ではもともと行き詰まりの意味である。基本的にデッドロックは資源数が2以上の場合に発生する（たとえばクリティカルセクションが一つあれば資源は１つと数えられる。二つのクリティカルセクションがあれば資源数は２である）。資源数が1の場合、セマフォ等はバイナリセマフォとなり、振る舞いはミューテックスと同じになるのでデッドロックは発生しない（ライブロックする。これを回避する方法は数多く考案されており、たとえばCSMA/CDでは乱数を用いて回避する）。資源数を1にする事は、デッドロックを回避する根本的な解決方法であるが、その場合プログラムの並列性は著しく損なわれるため、現代のコンピュータープログラミングにおいて現実的な手段とは言えない。資源を多数用い、なおかつデッドロックを回避する手段については以下に述べる。クリティカルセクションで排他制御を用いた場合の例をあげる。変数Aと変数Bの二つのデータと、"BにAの値を加算し、Aを0にする処理Aと"AにBの値を加算し、Bを0にする処理Bの二つの処理があったとする。マルチスレッドで処理をするため変数Aと変数BにアクセスするためのクリティカルセクションA（以下CSA）とクリティカルセクションB（以下CSB）の二つのクリティカルセクションを用意する。処理Aは以下の手順であるとする。また同様に処理Bは以下の手順であるとする。この場合は以下のようにプログラムが動作するとデッドロックが発生する。処理Aを実行するスレッドAが生成され、処理が開始する。処理Aの1でCSAに入った直後にコンテキストスイッチが発生し、処理Bを実行するスレッドBが生成され、処理Bの1でCSBに入る。そして再びコンテキストスイッチが発生しスレッドAがアクティブになり、2でCSBに入ろうと試みる。しかし、"スレッドBが既にCSBに入っているため"スレッドAは待機状態に入り、スレッドBがアクティブになる。スレッドBは同じく2でCSAに入ろうと試みるが"スレッドAが既にCSAに入っているため"スレッドBは待機状態に入ってしまう。こうして両方のスレッドが待機状態になり、プログラムが停止してしまう。この状態がデッドロックである。以上の処理を時間に沿ってまとめたものが以下の表である。以上のようなデッドロックを回避するには以下のような方法がある。他にも様々な回避方法が存在する。優先度上限プロトコル機能が拡張されたミューテックスを利用することでも、デッドロックを回避することが可能である。優先度上限プロトコルは組み込みシステムで主に使われ、使うことで効果があるプログラムも限定的であり、汎用的に使える方法ではない。オブジェクト指向プログラミングでは、クラス間の依存関係を単方向にし、クラス間の依存関係の構造が階層構造になるように設計するのが、必須ではないものの定石である。。ここでは、独立している方を下と定義する。つまり、上の階層のクラスは、下の階層のクラスについて知っている。下の階層のクラスは、上の階層のクラスについて知らない。上の階層のクラスから、下の階層のクラスへの呼び出しは、普通のメソッド呼び出しで行う。下の階層から、上の階層に戻すときは、Observerパターンを使う。階層構造をとる軍隊にたとえると、メソッド呼び出しが上官からの命令であり、Observerパターンが部下の上官への報告である。そして、デッドロックを回避するには、ロックをかけるオブジェクトのクラスの順番を統一するというのが一つの方法である。そして、クラスの依存関係が階層構造になっているときは、必ず、上の階層のクラスから順番にロックをかけるということで統一する。そうすると、上の階層でロックをかけたまま、下の階層のオブジェクトのメソッドを呼び出すことが可能になる。軍隊の比喩でいうと、上官が部下よりも先にリソースを独占する。また、Observerパターンで上の階層に戻す場合は、自分のかけているロックを全て解放してから、上の階層に戻す。そうすることにより、「下の階層でロック→上の階層でロック」の発生を防げる。また、同じ階層同士ではロックをかけない。それが必要な場合は、上の階層でロックをかける。こうすることにより、デッドロックを回避できる。Lock-freeとWait-freeアルゴリズムでもデッドロックを回避できる。

出典:wikipedia