デッドロック
英語表記: Deadlock
概要
デッドロックとは、並列処理や分散システムにおいて、複数のプロセスやスレッドが互いに相手が占有しているリソースの解放を待ち続け、その結果、どの処理も永久に進行できなくなる状態を指します。これは、「アルゴリズムと計算量」の分野で「並列・分散アルゴリズム」を設計する際に、データの整合性を守るために導入した「一貫性と同期」のメカニズムが、かえってシステムの動作を停止させてしまうという、深刻な同期の失敗例です。システム全体の処理効率を考える上で、デッドロックの発生条件と対処法を理解することは非常に重要になります。
詳細解説
デッドロックは、システムが共有リソースを効率的かつ安全に管理しようとする際に直面する、根本的な課題の一つです。私たちは「並列・分散アルゴリズム」を設計する目的が、処理速度の向上にあることを知っていますが、その速度向上のために導入した同期メカニズムがボトルネックとなり、最終的にシステムを停止させてしまう可能性があるのですから、非常に皮肉な現象だと感じます。
発生のメカニズムと4つの必要条件
デッドロックが発生するためには、計算機科学において確立されている4つの必要条件がすべて同時に満たされる必要があります。これらの条件は、デッドロックを理解し、予防策を講じる上での基礎知識となります。
1. 相互排除（Mutual Exclusion）
リソースが非共有であり、一度に一つのプロセスしか使用できない状態を指します。もしリソースが共有可能であれば、デッドロックは発生しませんが、データベースの書き込み領域やプリンタなど、排他制御が必須なリソースが存在するため、この条件は多くのシステムで避けられません。
2. 保持と待機（Hold and Wait）
リソースを一つ以上保持しているプロセスが、さらに別のリソースを要求し、そのリソースが解放されるのを待っている状態です。これは、プロセスが「自分のものは手放さず、他人のものを待つ」という、非常に自己中心的な振る舞いを許容していることを意味します。この状態が、リソースの円滑な流れを妨げます。
3. 非割込み（No Preemption）
プロセスに割り当てられたリソースは、そのプロセスが自発的に解放するまで、オペレーティングシステムや他のプロセスによって強制的に奪い取ることができない状態です。もしリソースを強制的に奪える（プリエンプションできる）ならば、待機状態にあるプロセスからリソースを取り上げて、待っている他のプロセスに渡すことでデッドロックを解消できますが、一般的にメモリやファイルといったリソースは非割込み性が求められます。
4. 循環待機（Circular Wait）
デッドロック状態にあるプロセス群が、リソースの待機に関して円環状の鎖を形成している状態です。例えば、プロセスP1がP2のリソースを待ち、P2がP3のリソースを待ち、最終的にP3がP1のリソースを待っている、という閉じたループができあがります。この循環こそが、デッドロックの最も決定的な要因であり、処理の進行を永久に妨げます。
デッドロックへの対処戦略
デッドロックはシステムの進行可能性（Liveness）を損なうため、
