名前だけ聞くと物騒な響きですが、正体は身近な話です。
お箸の取り合いにたとえると、 仕組みがすっと理解できます。
ラーメン屋さんでの出来事
たろうくんとはなこちゃんは、 1つのラーメンを仲良く分けて食べようとしています。
テーブルには箸が2本。 右側の箸と左側の箸です。
右の箸🥢を持っている
左の箸🥢を持っている
ラーメンを食べるには、両方の箸が必要です。
たろうくんは「はなこちゃんが左の箸を渡してくれたら食べられる」と思い、 自分の右の箸を離さずに待っています。
一方のはなこちゃんも 「たろうくんが右の箸を渡してくれたら食べられる」と思い、 自分の左の箸を離さずに待っています。
お互いに相手の箸を待ったまま、自分の箸も渡さない。
このままでは、二人とも永遠にラーメンを食べられません。
コンピュータの世界では、この状態を
デッドロック
と呼びます。
お箸の取り合いとコンピュータの対応関係
この状況を、コンピュータの処理に置き換えてみましょう。
デッドロックとは、複数の処理が互いに相手の確保しているリソースの解放を待ち続け、 どちらも処理を先へ進められなくなる状態のことです。
デッドロックが起きる4つの条件
デッドロックは偶然ではなく、次の4つの条件がすべて揃ったときに発生します。 これはコンピュータ科学で「コフマンの条件」と呼ばれる古典的な整理です。
たろうくんとはなこちゃんの例では、この4つがすべて揃っているため、 デッドロックが成立しています。 逆にいえば、どれか1つでも崩せばデッドロックは解消できます。
🔄 循環待機を3Dで見てみよう
たろうくんとはなこちゃんが、互いの箸を待ち続けている様子を 3Dグラフィックで表現しました。矢印がぐるっと輪になっているのが「循環待機」です。
🧒🥢→待つ→👧🥢→待つ→🧒
という輪（お使いの環境では3D表示に対応していません）
実際のシステムではどう解消するのか
現実のコンピュータでは、店員さんが割って入るように、 システム側がデッドロックを検出して解消する仕組みを持っています。
タイムアウトによる検出
一定時間リソースを確保できない処理を、システムが強制的に打ち切る方式です。
実装は単純ですが、デッドロックでなくても長い待ちを打ち切ってしまうことがあります。
主要なDBMSでは次の待機グラフによる検出が基本で、タイムアウトは検出できない場合の補助として使われます（MySQL InnoDBの innodb_lock_wait_timeout など）。
待機グラフによる検出
「どの処理がどのリソースを待っているか」を有向グラフとして管理し、 循環（ループ）が発生した時点でデッドロックと判定する方式です。 SQL ServerやMySQL（InnoDB）などのDBMSはこの仕組みで循環を検出し、 どちらかのトランザクションを自動的にロールバック（取り消し）します。 Oracleは取り消す範囲がトランザクション全体ではなく、デッドロックに関わった1つのSQL文です。
ロック順序の統一（予防）
すべての処理が「必ず箸Aを先に取り、次に箸Bを取る」というように リソースを確保する順序を統一しておけば、循環待機そのものが起こらなくなります。 プログラミングの現場ではこの予防策が最も基本的な対策です。
デッドロックは「起きたら検出して取り消す」方式と、 「そもそも起きない順序で設計する」方式の両輪で対処します。
デッドロックに出会う場面
データベースのトランザクション
複数のユーザーが同時に同じテーブルの異なる行を更新し、 互いのロックの解放を待ち合ってしまうケースです。 ECサイトの在庫更新や銀行の口座振替処理など、 同時アクセスが多いシステムほど発生しやすくなります。
マルチスレッドプログラミング
JavaのsynchronizedやC#のlockなど、
複数のスレッドが共有資源を排他制御する場面で発生します。
設計時にロックの取得順序を揃えることが基本対策です。
Javaでどうスレッドセーフな実装にするかを押さえておくと、デッドロックの予防にもつながります。
基本情報技術者試験
デッドロックは基本情報技術者試験のテクノロジ系分野で頻出のテーマです。 コフマンの4条件と、循環待機を断ち切れば解消できるという原理を セットで押さえておくと得点しやすくなります。
よくある質問
複数の処理が、互いに相手の確保しているリソースの解放を待ち続け、 どちらも先に進めなくなる状態のことです。 お箸の取り合いのように、双方が譲らないまま止まってしまうイメージです。
無限ループは1つの処理が同じ手順を繰り返し続ける状態です。 デッドロックは複数の処理が互いを待ち合って停止する状態で、 原因も現れ方も異なります。
相互排他・保持と待機・非奪取・循環待機という4つの条件が すべて揃ったときに発生します。 このうちどれか1つを崩せば防ぐことができます。
複数のユーザーが同時に同じテーブルへ書き込みを行う場面が多く、 行ロックの取得順序がユーザーごとにばらばらになりやすいためです。
待機グラフによる循環検出のうえで、どちらかの処理を自動的に取り消す方式が一般的です。 検出できない場合の補助として、タイムアウトによる強制打ち切りも使われます。
リソースを確保する順序をあらかじめ全処理で統一しておくことが 最も基本的な予防策です。ロックの保持時間を短くすることも有効です。
複数のロックを同時に扱う処理では、取得する順序をコード全体で 統一することが重要です。順序がバラバラだと循環待機が発生しやすくなります。
コフマンの4条件の内容と、どれか1つを崩せば解消できるという原理、 そしてデータベースのトランザクション処理との関連が頻出です。
おさらい
デッドロックは名前こそ物々しいものの、 仕組み自体はお箸の取り合いと同じくらいシンプルです。
- デッドロック ＝複数の処理が互いに相手のリソースを待ち続け、先に進めなくなる状態
- 発生には 相互排他・保持と待機・非奪取・循環待機 の4条件がすべて必要
- 解消には タイムアウトや 待機グラフによる検出が使われる
- 予防には リソース確保の順序統一が最も基本的
- データベースのトランザクションやマルチスレッドプログラミング、 基本情報技術者試験でよく登場する
デッドロック
＝🥢を離さず、🥢を待ち続けて、誰も🍜を食べられない状態！
次に「デッドロック」という言葉を見つけたら、
🧒🥢 自分の箸を離さない
＋
👧🥢 相手の箸を待ち続ける
＋
🍜 誰も食べられない
を思い出してみてください。
お箸の取り合い：順番を決めないと／決めると
順番を決めた場合