デッドロックとは
デッドロックとは、複数の処理（プロセスやスレッド）が、互いに相手が占占有している資源の解放を待ち合ってしまい、どちらの処理も先に進めなくなって停止（フリーズ）してしまう現象です。マルチタスクや排他制御を行うシステムにおいて、設計上の配慮が不足していると発生することがあります。デッドロックが起きると、外部から強制終了するなどの対策をとらない限り、システムが永久に待ち状態になってしまいます。
具体例
- お互いの鍵の掛け合い：プロセス1が「ファイルA」をロックし、プロセス2が「ファイルB」をロックしているとします。次に、プロセス1が処理を完了するために「ファイルB」を必要として待ち状態になり、同時にプロセス2も「ファイルA」を必要として待ち状態になります。両者がお互いの持っているロックの解除を待ち続けるため、どちらも動けなくなります。
- 狭い道路でのすれ違い：車Aと車Bが、車1台分しか通れない狭い一本道で正面衝突しそうになり、お互いに「相手がバックしてくれるのを待つ」状態になり、どちらも一歩も動けなくなってしまう状況に似ています。
もう少し詳しく
デッドロック（Deadlock）は、複数の処理単位（プロセスやスレッド）が、互いに相手が占有している共有資源の解放を待ち合ってしまい、どちらの処理も永遠に先に進めなくなってシステム全体、あるいは一部が完全に停止（フリーズ）してしまう現象です。この現象が発生するためには、以下の4つの条件（一般にコフマン条件と呼ばれます）がすべて同時に満たされる必要があります。
1つ目は「相互排他（Mutual Exclusion）」です。これは、資源が一度に1つのプロセスにしか割り当てられず、複数のプロセスが同時にアクセスできない状態を指します。2つ目は「保持して待つ（Hold and Wait）」で、すでに何らかの資源を保持しているプロセスが、さらに別のプロセスが占有している資源を要求し、その割り当てを待機する状態です。3つ目は「横取り不可（No Preemption）」で、他のプロセスが保持している資源を、OSなどが強制的に奪い取ることができないことを意味します。4つ目は「循環待ち（Circular Wait）」で、複数のプロセスが環状に（AはBを待ち、BはCを待ち、CはAを待つというように）資源を待ち合っている状態です。
これらすべてが揃ったときにデッドロックが発生します。これを防ぐためには、プロセスが資源を要求する順番をあらかじめルール化して循環待ちを物理的に防いだり、処理を開始する前に必要な資源をすべて一括して要求・確保させる手法が取られます。また、デッドロックの発生を未然に防ぐのではなく許容しつつ、OSが定期的にシステムの状態を監視し、発生を検知した時点で一部のプロセスを強制終了（キル）させたり、トランザクションをロールバックして回復を図る「デッドロックの検出と回復」というアプローチもあります。現実のシステム設計では、パフォーマンスとのバランスを考慮してこれらの手法が組み合わされます。
試験でのポイント
基本情報技術者試験やITパスポート、さらには応用情報技術者試験などの情報処理技術者試験において、デッドロックの発生原理やその回避方法は非常によく出題される頻出テーマです。特に「複数のプロセスが互いに相手の資源の解放を待っている状態」という定義そのものを問う問題が多く出題されます。
また、排他制御の基本技術である「セマフォ」や「ミューテックス」といった専門用語とセットで出題されることが多いため、排他制御の仕組み全体を関連付けて理解しておくことが重要です。試験の選択肢の中で「フリーズ」「システム停止」「相互待機」といったキーワードを見つけたら、デッドロックに関連する記述である可能性が高いと考えましょう。
OSのプロセス管理だけでなく、データベースのトランザクション処理においてもデッドロックは重要です。複数のトランザクションが互いにレコードやテーブルのロックを掛け合うことでデッドロックが発生します。この場合、DBMS（データベース管理システム）がデッドロックを瞬時に検出し、一方のトランザクションをロールバック（取り消し）して他方を進行させるという処理が自動的に行われる仕組みについても問われることがあります。
関連する用語
排他制御、セマフォ、トランザクション、ミューテックス