デッドロック

2025年11月17日

デッドロック

英語表記: Deadlock

概要

デッドロックは、並行・並列処理環境、特にマルチスレッドプログラムにおいて、複数のプロセスやスレッドが互いに相手が保持しているリソースの解放を永久に待ち続け、結果としてすべての処理が停止してしまう状態を指します。これは、共有リソースへのアクセスを制御する「同期制御」が適切に行われなかった際に発生する、最も深刻な「並行バグ」の一つです。システム全体の処理能力を著しく低下させ、応答不能に陥らせるため、並行システムの「安全性」を確保する上で、デッドロックの回避は非常に重要な課題となっています。

詳細解説

デッドロックは、並行・並列処理（マルチスレッド, GPU並列）の文脈における「同期制御と安全性」の領域で深く議論されます。複数の処理が同時に動作する際、データベースのレコードやメモリ領域、ファイルといった共有リソースへのアクセスを排他的に行うために、私たちは「ロック」機構（ミューテックスやセマフォなど）を用います。しかし、このロックの獲得と解放の順序を誤ると、デッドロックが発生してしまいます。

デッドロックが発生するためには、一般的に以下の4つの条件（コフマンの条件）がすべて同時に満たされる必要があります。これは、システム設計者がデッドロックを予防するための鍵となる知識ですから、ぜひ覚えておきたいポイントです。

1. 相互排他 (Mutual Exclusion)

資源は一度に一つのプロセス（またはスレッド）しか使用できません。もしリソースが同時に複数から利用可能であれば、そもそも待機する必要がないため、この条件はデッドロックの出発点となります。

2. 保持と待機 (Hold and Wait)

あるプロセスがすでに何らかのリソースを保持している状態で、さらに別のリソースを要求し、それが利用可能になるまで待機している状態です。リソースを保持したまま次のリソースを待つ、という行動が問題を引き起こします。

3. 非割込み (No Preemption)

プロセスが保持しているリソースは、そのプロセス自身が明示的に解放するまで、強制的に取り上げられることはありません。つまり、システム側が強制的にロックを解除できない、ということです。

4. 循環待機 (Circular Wait)

これがデッドロックを形成する最も決定的な要因です。複数のプロセスが鎖状につながり、それぞれが次のプロセスが保持しているリソースを待機している状態です。例えば、プロセスAがリソースR1を保持しR2を待ち、プロセスBがR2を保持しR1を待つ、という循環構造です。

デッドロックは、この循環待機が成立した瞬間にシステムが機能停止に至る「並行バグ」の一種です。この問題の厄介な点は、発生頻度が低く、特定のタイミングや負荷状況下でしか再現しないことが多いため、デバッグが極めて困難である、という点にあります。このため、設計段階でデッドロックが起こり得ないような仕組み（デッドロック予防）や、発生を検出した際に回復する仕組み（デッドロック検出と回復）を組み込むことが、同期制御の安全性確保において非常に重要視されます。

具体例・活用シーン

デッドロックの概念を理解するために、身近な例やITシステムにおける具体的な発生シーンを見ていきましょう。

1. 交通整理のアナロジー：二つの橋と二台のトラック

デッドロックを理解するための古典的なメタファーは、「二つの資源を巡る循環待機」の状況です。

ある街に、幅が狭く、一度に一台しか渡れない橋が二つ（橋A、橋B）あると想像してください。そして、それぞれ資源R1（橋A）と資源R2（橋B）に対応するとします。

トラックP1（プロセス1）：「橋A」を渡り始めました（R1を保持）。次に「橋B」が必要になりましたが、まだ渡れません（R2を待機）。
トラックP2（プロセス2）：「橋B」を渡り始めました（R2を保持）。次に「橋A」が必要になりましたが、まだ渡れません（R1を待機）。

P1はR1を保持したままR2を待ち、P2はR2を保持したままR1を待ちます。両方のトラックは、相手が持っている橋を永久に待ち続けることになり、誰も動けなくなります。これがデッドロックです。交通整理員（同期制御機構）が、この循環待機が発生しないように、事前にどちらかのトラックを待機させるルール（例えば、必ず橋Aから渡る、など）を設けていれば、このバグは回避できたわけです。

2. データベーストランザクションにおけるデッドロック

ITシステムでは、特にデータベースのトランザクション処理でデッドロックが頻繁に問題となります。

トランザクションT1：テーブルXのレコードを更新し（Xをロック）、次にテーブルYのレコードを更新しようとします（Yを待機）。
トランザクションT2：テーブルYのレコードを更新し（Yをロック）、次にテーブルXのレコードを更新しようとします（Xを待機）。

T1とT2が同時に実行され、上記のようなロックの獲得順序が入れ替わると、循環待機が発生しデッドロックに至ります。現代のデータベース管理システム（DBMS）の多くは、デッドロックを自動的に「検出」し、どちらか一方のトランザクションを強制的に中止（ロールバック）させてロックを解放させることで、「回復」を図るメカニズムを持っています。しかし、これは処理のやり直しを意味するため、パフォーマンス上のオーバーヘッドとなります。

3. オペレーティングシステムのリソース管理

マルチスレッドOSにおいて、あるスレッドがプリンタを占有している間に、別のスレッドがそのプリンタを使うためのバッファメモリを占有し、互いに相手の解放を待つといった状況もデッドロックの典型例です。並行処理の設計においては、リソースの階層化や、リソースを獲得する順序をシステム全体で統一することが、デッドロック予防の基本戦略となります。

資格試験向けチェックポイント

デッドロックは、基本情報技術者試験（FE）や応用情報技術者試験（AP）において、同期制御やOSの仕組みを問う上で非常によく出題されるテーマです。ITパスポート試験でも、概念理解が問われることがあります。

デッドロックの定義: 「複数のプロセスが互いに相手の持つ資源の解放を待ち、処理が永久に停止する状態」であることを正確に把握しましょう。
四つの必要条件: デッドロックが発生するために必要な「相互排他」「保持と待機」「非割込み」「循環待機」の4条件は必ず暗記してください。特に「循環待機」がデッドロックを成立させる直接的な原因であることを理解することが重要です。
デッドロック対策: 対策として、「予防（Prevention）」「回避（Avoidance）」「検出（Detection）」「回復（Recovery）」の4つのアプローチがあることを知っておきましょう。特に、リソースの事前要求や、リソース要求順序の統一は「予防」策としてよく問われます。
銀行家のアルゴリズム: 応用情報技術者試験では、デッドロックを未然に防ぐ「回避」戦略の一つとして、銀行家のアルゴリズム（安全状態をチェックし、リソース割り当てを判断する手法）の概念が出題されることがあります。
関連用語との区別: デッドロック（Deadlock）と、リソースが足りずに特定のプロセスだけが永久に実行できない「スタベーション（Starvation、飢餓）」や、状態が変化し続けるが先に進まない「ライブロック（Livelock）」との違いを明確にしておくと、高難度の問題に対応できます。