デッドロック
Deadlock
互いに相手のロック解放を待ち合って全員が永遠に止まる状態。成立には4条件が揃う必要がある。
概要
デッドロック（deadlock、膠着状態）は、複数の処理が互いに相手の持っている資源の解放を待ち合い、誰も先へ進めなくなって全員が永遠に止まってしまう状態です。二人が狭い廊下で正面から出会い、互いに「そっちが先に譲れ」と一歩も引かずに固まってしまう — あの構図が、そのままプログラムの中で起きたものだと考えると分かりやすいでしょう。
デッドロックは、排他制御を導入した副作用そのものです。ロックは「一度に一人」を保証するありがたい道具ですが、そのロックを2つ以上使い始めた瞬間から、「AがロックXを握ったままロックYを待ち、BがロックYを握ったままロックXを待つ」という待ち合いの円環が生まれうるのです。片方が譲らない限り、両者はそのまま凍りつきます。
この状態の恐ろしいところは、CPUを消費するわけでもエラーを吐くわけでもなく、ただ静かに応答が返らなくなる点です。サーバなら特定のリクエストが延々と終わらず、やがてスレッドやコネクションが食い潰されてサービス全体が巻き添えになります。だからこそ、デッドロックは「起きてから直す」のではなく「起きない設計にする」ことが重視されます。
なぜ生まれたか
デッドロックは、それ単体で発明されたものではありません。排他制御という解決策が連れてきた、新しい種類の問題です。ロックを一つだけ使っているうちは、待たされることはあっても、いつかは必ず解放されます。ところが現実のプログラムは、複数の資源を同時に扱わずには済みません。「口座Aから口座Bへ送金する」には両方の口座をロックする必要があり、「複数のテーブルをまとめて更新する」には複数の行ロックが要ります。資源が二つ以上になった途端、「どちらを先にロックするか」という順序の問題が忍び込みます。
もし送金処理Xが「AをロックしてからB」の順で、逆向きの送金処理Yが「BをロックしてからA」の順で同時に走ると、XがAを、YがBを握った状態で互いに相手を待ち始め、抜け出せなくなります。この現象を厳密に理解するために、1971年にエドワード・コフマンらが「デッドロックが成立するための4つの条件」を整理しました。この4条件が「なぜ起きるのか」を教えると同時に、「どれか一つでも崩せば防げる」という設計の指針にもなっている点が重要です。
詳細
古典例 — ロックの取得順が逆だと
デッドロックの教科書的な例は、2つのロックを逆順に取得する2つのスレッドです。スレッドAは「ロック1を取ってからロック2」、スレッドBは「ロック2を取ってからロック1」を欲しがります。それぞれが最初のロックを取った直後、二人目のロックを要求すると — 互いに相手が握っているため、双方が永遠に待ちます。それぞれのスレッドだけを見れば何も間違っていないのに、組み合わさった瞬間に凍りつくのが、この問題の不気味さです。
コフマンの4条件
デッドロックが成立するには、次の4つがすべて同時に満たされている必要があります。裏を返せば、どれか一つでも崩せば決してデッドロックは起きません。
4条件とは、（1）相互排他 — 資源は一度に一人しか使えない（まさに排他制御そのもの）。（2）保持と待機 — あるスレッドが資源を握ったまま、別の資源の解放を待つ。（3）横取り不可 — 握られた資源を、外から無理やり取り上げることはできない。（4）循環待機 — 上の図のように、待ちの関係が「AはBを、BはAを」と一周して閉じた環になっている、の4つです。この4つが揃ってはじめてデッドロックが成立します。この円環が閉じる瞬間と、順序を統一すると閉じなくなることを、下の実験で自分の手で確かめてみてください。
- ① ロック1を取る
- ② ロック2を取る
- ③ 処理
- ④ 両方解放
- ① ロック2を取る
- ② ロック1を取る
- ③ 処理
- ④ 両方解放
Aが①、Bが①、と交互に1ステップずつ進めてみてください。Bの取得順序が逆なので、途中で両者が固まる瞬間が来ます。
回避策 — 実務の第一解はロック順序の統一
回避の定石は、4条件の（4）循環待機を崩すことです。もっとも実務的なのが、ロックを取得する順序を全スレッドで統一することです。「必ずロック1→ロック2の順でしか取らない」と決めておけば、逆順に取るスレッドが存在しなくなり、環は決して閉じません。先ほどの送金の例なら、口座IDの小さいほうから必ずロックする、といったルールにするだけで防げます。
そのほか、（2）保持と待機を崩す手として、必要な複数のロックを一括で取得し、すべて取れなければ何も握らずにやり直す方法があります。また、（3）横取り不可を崩す手として、一定時間で諦めるタイムアウトを設け、時間内に全ロックを取れなければ持っているものを解放して最初からやり直す方法もあります。ただしタイムアウトによる再試行は、後述のライブロックを招きやすい点に注意が必要です。
検出と回復 — データベースの場合
すべてを設計で防ぎきれないため、「起きたら検出して壊す」というアプローチもあります。その代表がリレーショナルデータベースです。多くのDBは、内部で「どのトランザクションがどのロックを待っているか」の待ちグラフを管理しており、そこに閉じた環（循環待機）が現れたことを検出すると、デッドロックと判断します。そして片方のトランザクションを強制的にロールバック（巻き戻し）して犠牲者にし、環を断ち切ります。犠牲になったトランザクションはエラーを受け取るので、アプリ側は「デッドロックで失敗したら少し待って再実行する」というリトライを実装しておくのが定石です。DBが自動で面倒を見てくれるとはいえ、頻発するならロック順序の設計を見直すべきサインです。
ロック以外のデッドロック
デッドロックはミューテックスに限った話ではありません。抽象的には「限りある資源を複数のプレイヤーが取り合う」あらゆる場面で起こりえます。よくあるのがコネクションプールの枯渇です。プール内のDB接続をすべて使い切ったスレッドたちが、さらに追加の接続を待つと、誰も接続を返さないまま全員が待ち続ける状態になります。分散システムでも、分散ロックを複数のサービスがまたいで取り合えば、ネットワーク越しに同じ循環待機が発生します。「資源・保持・待ち合い」という構図さえ揃えば、規模を問わず現れるのがデッドロックです。
ライブロック・スタベーションとの違い
最後に、似て非なる2つの状態と区別しておきます。デッドロックが「全員が完全に静止する」のに対し、ライブロックは「全員が動き続けているのに、誰も前進しない」状態です。廊下で出会った二人が、互いに気を利かせて同じ方向に避け続け、いつまでもすれ違えない様子がこれで、タイムアウトと再試行を素朴に組むと陥りやすい罠です。一方スタベーション（飢餓）は、特定のスレッドだけが運悪くいつまでも資源を得られず、後回しにされ続ける状態を指します。デッドロックは「全員が止まる」、ライブロックは「全員が空回り」、スタベーションは「一部が置き去り」と整理すると、それぞれの違いがはっきりします。