デッドロック
Deadlock ・ でっどろっく
互いに相手のロック解放を待ち合って全員が永遠に止まる状態。成立には4条件が揃う必要がある。
✦ 30秒で試す — 航海誰も悪くないのに、全員が永遠に待ち続けるBの取る順もAと同じ「1→2」にそろえると？予想してみる概要
デッドロック（deadlock、膠着状態）は、複数の処理が互いに相手の持っている資源の解放を待ち合い、誰も先へ進めなくなって全員が永遠に止まってしまう状態です。二人が狭い廊下で正面から出会い、互いに「そっちが先に譲れ」と一歩も引かずに固まってしまう — あの構図が、そのままプログラムの中で起きたものだと考えると分かりやすいでしょう。
デッドロックは、排他制御を導入した副作用そのものです。ロックは「一度に一人」を保証するありがたい道具ですが、そのロックを2つ以上使い始めた瞬間から、「AがロックXを握ったままロックYを待ち、BがロックYを握ったままロックXを待つ」という待ち合いの円環が生まれうるのです。片方が譲らない限り、両者はそのまま凍りつきます。
この状態の恐ろしいところは、CPUを消費するわけでもエラーを吐くわけでもなく、ただ静かに応答が返らなくなる点です。サーバなら特定のリクエストが延々と終わらず、やがてスレッドやデータベースのコネクションが食い潰されてサービス全体が巻き添えになります。だからこそ、デッドロックは「起きてから直す」のではなく「起きない設計にする」ことが重視されます。
なぜ生まれたか
デッドロックは、それ単体で発明されたものではありません。排他制御という解決策が連れてきた、新しい種類の問題です。ロックを一つだけ使っているうちは、待たされることはあっても、いつかは必ず解放されます。ところが現実のプログラムは、複数の資源を同時に扱わずには済みません。「口座Aから口座Bへ送金する」には両方の口座をロックする必要があり、「複数のテーブルをまとめて更新する」トランザクションには複数の行ロックが要ります。資源が二つ以上になった途端、「どちらを先にロックするか」という順序の問題が忍び込みます。
もし送金処理Xが「AをロックしてからB」の順で、逆向きの送金処理Yが「BをロックしてからA」の順で同時に走ると、XがAを、YがBを握った状態で互いに相手を待ち始め、抜け出せなくなります。1960年代、複数のプログラムを同時に動かすマルチプログラミングの OS でこの膠着が実際に問題になりました。ダイクストラが1965年に出した演習問題は、のちにホーアの手で「5人の哲学者が両隣の箸を取り合う」食事する哲学者の問題として広まり、並行処理の定番の題材になります。そして1971年、エドワード・コフマンらが「デッドロックが成立するための4つの条件」を整理します。この4条件が「なぜ起きるのか」を教えると同時に、「どれか一つでも崩せば防げる」という設計の指針にもなっている点が重要です。
詳細
古典例 — ロックの取得順が逆だと
デッドロックの教科書的な例は、2つのロックを逆順に取得する2つのスレッドです。スレッドAは「ロック1を取ってからロック2」、スレッドBは「ロック2を取ってからロック1」を欲しがります。それぞれが最初のロックを取った直後、2つ目のロックを要求すると — 互いに相手が握っているため、双方が永遠に待ちます。それぞれのスレッドだけを見れば何も間違っていないのに、組み合わさった瞬間に凍りつくのが、この問題の不気味さです。しかも、Aが2つとも取り終えてからBが動けば何も起きないため、発生は実行のタイミング次第で、テストでは再現しにくいのが普通です。
コフマンの4条件
デッドロックが成立するには、次の4つがすべて同時に満たされている必要があります。裏を返せば、どれか一つでも崩せば決してデッドロックは起きません。
4条件とは、（1）相互排他 — 資源は一度に一人しか使えない（まさに排他制御そのもの）。（2）保持と待機 — あるスレッドが資源を握ったまま、別の資源の解放を待つ。（3）横取り不可 — 握られた資源を、外から無理やり取り上げることはできない。（4）循環待機 — 上の図のように、待ちの関係が「AはBを、BはAを」と一周して閉じた環になっている、の4つです。この4つが揃ってはじめてデッドロックが成立します。
この「誰が何を握り、誰が何を待っているか」を矢印で描いたものを待ちグラフ（wait-for graph）と呼びます。デッドロックとは、待ちグラフに環ができた状態のことです。下の部品では、あなたがスケジューラになってスレッドを1手ずつ進めます。環が閉じる瞬間と、取る順をそろえると何度試しても環が閉じないことを、自分の手で確かめてください。3人の「食事する哲学者」でも同じことが起きます。
あなたがスケジューラです。スレッド（丸）を押すと1手進みます。A を1手、B を1手、と交互に進めてみてください。A は「ロック1 → 2」、B は「ロック2 → 1」の順で取ります。
予防 — 実務の第一解はロック順序の統一
設計の段階で4条件のどれかを崩しておくのが「予防（prevention）」です。もっとも実務的なのは（4）循環待機を崩す方法で、ロックを取得する順序を全スレッドで統一します。「必ずロック1→ロック2の順でしか取らない」と決めておけば、逆順に取るスレッドが存在しなくなり、環は決して閉じません。先ほどの送金の例なら、口座IDの小さいほうから必ずロックする、というルールにするだけで防げます。
ほかに、（2）保持と待機を崩す手として、必要な複数のロックを一括で取得し、すべて取れなければ何も握らずにやり直す方法があります。Java の tryLock のように「取れなければ待たずに失敗を返す」ロックを使い、2つ目が取れなかったら1つ目も手放して少し待ってから再挑戦する、という書き方です。（3）横取り不可を崩す手としては、一定時間で諦めるタイムアウトを設け、時間内に全ロックを取れなければ持っているものを解放して最初からやり直します。ただしタイムアウトによる再試行は、後述のライブロックを招きやすい点に注意が必要です。
なお教科書では、予防とは別に「回避（avoidance）」という言葉があります。こちらは実行時に、資源を渡すたびに「この先デッドロックに陥る可能性のない安全な状態か」を計算し、危ない割り当てを先送りする方式で、ダイクストラの銀行家のアルゴリズムが代表です。各スレッドが最大でいくつの資源を使うかを事前に申告する必要があるため、一般のアプリケーションではほとんど使われません。
検出と回復 — データベースの場合
すべてを設計で防ぎきれないため、「起きたら検出して壊す」というアプローチもあります。その代表がRDBMSです。多くのDBは、内部で「どのトランザクションがどのロックを待っているか」の待ちグラフを管理しており、そこに環が現れたことを検出すると、片方のトランザクションを強制的にロールバック（巻き戻し）して犠牲者にし、環を断ち切ります。MySQL（InnoDB）なら「Deadlock found when trying to get lock」（エラー1213）、PostgreSQL なら deadlock_detected（40P01）というエラーが犠牲になった側に返ります。
犠牲になったトランザクションはエラーを受け取るので、アプリ側は「デッドロックで失敗したら少し待って再実行する」リトライを実装しておくのが定石です。検出とは別に、ロック待ちそのものにも上限があります。InnoDB の innodb_lock_wait_timeout（既定50秒）や PostgreSQL の lock_timeout がそれで、環になっていなくても長すぎる待ちを打ち切ります。DBが自動で面倒を見てくれるとはいえ、頻発するなら更新する行の順序をそろえるなど、設計を見直すべきサインです。
ロック以外のデッドロック
デッドロックはミューテックスに限った話ではありません。抽象的には「限りある資源を複数のプレイヤーが取り合う」あらゆる場面で起こりえます。よくあるのがコネクションプールの枯渇です。プール内のDB接続をすべて使い切ったスレッドたちが、処理の途中でさらに追加の接続を待つと、誰も接続を返さないまま全員が待ち続けます。分散システムでも、分散ロックを複数のサービスがまたいで取り合えば、ネットワーク越しに同じ循環待機が発生します。「資源・保持・待ち合い」という構図さえ揃えば、規模を問わず現れるのがデッドロックです。
ライブロック・スタベーションとの違い
最後に、似て非なる2つの状態と区別しておきます。デッドロックが「全員が完全に静止する」のに対し、ライブロックは「全員が動き続けているのに、誰も前進しない」状態です。廊下で出会った二人が、互いに気を利かせて同じ方向に避け続け、いつまでもすれ違えない様子がこれで、タイムアウトと再試行を同じ間隔で素朴に組むと陥りやすい罠です（再試行の間隔にランダムな揺らぎを入れると抜け出せます）。一方スタベーション（飢餓）は、特定のスレッドだけが運悪くいつまでも資源を得られず、後回しにされ続ける状態を指します。デッドロックは「全員が止まる」、ライブロックは「全員が空回り」、スタベーションは「一部が置き去り」と整理すると、それぞれの違いがはっきりします。
試問
食事する哲学者: 3人（P1・P2・P3）が丸いテーブルに座り、それぞれ両隣の箸（ロック）を2本とも取ってから食べます。1本目を握ったまま、2本目が空くのを待ちます。あなたはスケジューラで、人の丸を押すとその人が1手進みます。待ちの矢印が一周したら、環の中の人を押して巻き戻せます。箸を取る順の決まりは、上で切り替えられます。
食事する哲学者: 3人がそれぞれ両隣の箸（ロック）を2本とも取ってから食べます。3人を1手ずつ順に進めて、全員が1本目を握った状態にしてみてください。