狭い一車線の橋の真ん中で、両側から入ってきた2台の車が向かい合って止まったとしましょう。どちらの運転手も相手が先に下がるのを待って動かなければ、2台の車は永遠に橋を渡れません。誰が悪いとも言いにくいのに、誰も前に進めない状況ができあがってしまったのです。
コンピュータの中でもまったく同じことが起こり、これを「デッドロック（Deadlock）」と呼びます。デッドロックとは、簡単に言えば、複数のプログラムが互いに相手の持つ資源を待っているために、どれも作業を続けられずに止まってしまった状態のことです。コンピュータが壊れたわけでもないのに急に固まったように見える現象の多くは、まさにこのデッドロックが原因です。
本記事では、デッドロックがどのような形で現れるのか、デッドロックが起こる4つの条件とは何か、それを説明する有名な例、そしてコンピュータがデッドロックに対処する方法まで、順に見ていきます。
互いに待ち合って止まってしまうコンピュータ
デッドロックはどうして起こるのか
コンピュータの中では、複数のプログラムが同時に動きながら、プリンター、ファイル、メモリといった資源を分け合って使っています。
(1) 一度に一つしか使えない資源
資源の中には、複数のプログラムが同時に使うと内容がめちゃくちゃになってしまうものがあるため、あるプログラムが使っている間、ほかのプログラムは待たなければなりません。このとき資源を一時的に独り占めする仕組みをロック（Lock）と呼びます。
(2) 食い違った順番が生む停止
たとえば、1つ目のプログラムがファイルAをロックしたままファイルBを待ち、2つ目のプログラムがファイルBをロックしたままファイルAを待つ場合があります。どちらのプログラムも自分のものは手放さずに相手のものだけを待つため、両方とも永遠に止まったままになります。
(3) 外から見た様子
デッドロックに陥ったプログラムは、エラーメッセージも出さずにただ応答しなくなります。銀行のオンラインシステムや予約システムのように、大量の要求を一度に処理する場所では、こうした停止が大きな問題につながることがあります。
デッドロックが起こる4つの条件
1971年、コンピュータ科学者のエドワード・コフマン（Edward G. Coffman Jr.）は、デッドロックが起こるには次の4つの条件が同時にそろわなければならないと整理しました。彼の名にちなみ、これをコフマンの条件と呼びます。
- 相互排除（Mutual Exclusion）：資源は一度に一つのプログラムしか使えません。
- 保持と待機（Hold and Wait）：プログラムがすでに資源を一つ握ったまま、ほかの資源をさらに待ちます。
- 横取り不可（No Preemption）：他者が握っている資源を無理やり奪うことはできず、持っている側が自ら手放すしかありません。
- 循環待ち（Circular Wait）：1番は2番を、2番は3番を、3番はまた1番を待つというように、待ちが輪のようにつながります。
(1) 一つ断ち切るだけで解ける
4つの条件のうち一つでも欠ければ、デッドロックは起こりません。そのため、デッドロックを防ぐ方法のほとんどは、この4つの輪のうち一つを断ち切ることから始まります。
食事する哲学者の問題
デッドロックを説明するときに最もよく使われる話は、オランダのコンピュータ科学者エドガー・ダイクストラ（Edsger W. Dijkstra）が出した問題に由来する「食事する哲学者の問題（Dining Philosophers Problem）」です。
(1) 問題の状況
丸いテーブルに哲学者が5人座り、人と人の間にフォークが1本ずつ、全部で5本置かれています。哲学者は考えごとをしていてお腹が空くと、両隣のフォーク2本をどちらも手に取らなければ食事ができません。
(2) 全員が飢えてしまう瞬間
5人が同時に左のフォークを手に取ると、全員が右のフォークを待つことになります。誰も左のフォークを置かないので、結局5人とも食事ができず、ただ待ち続けるだけになります。4つの条件がすべてそろった典型的なデッドロックです。
(3) 簡単な解決策
フォークに番号を付け、誰もが番号の小さいフォークから取ると決めれば、待ちの輪は生まれません。順番を一つ決めるだけで循環待ちを断ち切れることがよくわかります。
コンピュータがデッドロックに対処する方法
オペレーティングシステムやデータベースは、状況に応じてさまざまな方法を使い分けます。
(1) 前もって防ぐ
資源を使う順番を決めておいたり、必要な資源を最初にまとめて要求させたりして、4つの条件のうち一つがそもそも成り立たないようにします。
(2) 避けて通る
資源を渡す前に、この要求に応じると後でデッドロックが起こりうるかどうかを前もって計算します。ダイクストラが考案した銀行家のアルゴリズム（Banker’s Algorithm）が代表的な方法で、銀行が融資をするときに、すべての顧客の要求を最後まで満たせるかどうかを見極めるのに似ています。
(3) 見つけてほどく
デッドロックが起こることはひとまず許し、誰が誰を待っているかを調べて輪が見つかれば、プログラムを一つ止めるか最初からやり直させて、結び目をほどきます。多くのデータベースがこの方式を使っています。
(4) 見て見ぬふりをする
デッドロックがごくまれにしか起こらず被害も小さいなら、あえて防がず、起きたら再起動するほうを選ぶこともあります。砂に頭を埋めるダチョウにたとえて、これをダチョウアルゴリズム（Ostrich Algorithm）と呼びます。
デッドロックは、誰か一人が間違えたせいではなく、全員が自分の取り分を握ったまま相手だけを待つときに生じる問題です。だからこそ解決策も、順番を決め、ときには持っているものを先に手放すことから始まります。
互いに握り合った手を一つ離すだけで道が開けると知ること、それこそが止まったシステムを再び動かす知恵の第一歩です。
