デッドロック：コンピューティングとシステムにおける原因、例、対処法

デッドロックを成立させる基本条件

デッドロックは偶然に起こるものではなく、複数の状況が組み合わさることで発生する。実務では、デッドロックの発生に必要な条件として、しばしば次の4つが挙げられる。

• 相互排他：一度に1つの主体だけが保持できる資源があること。たとえば、ファイルに対するロックが該当する。
• 保持と待機：主体が少なくとも1つの資源を保持したまま、追加の資源の獲得を待つこと。
• 非奪取：資源を主体から強制的に取り上げることができず、その主体が自発的に解放しなければならないこと。
• 循環待機：各主体が次の主体の保持する資源を待つ、主体の循環が存在すること。

一般的な例と利用文脈

単純な類例は、この考え方を具体的に理解する助けとなる。たとえば、図を描く2人のうち、一方が鉛筆を、もう一方が定規を持ち、どちらも作業を続けるために相手の道具を必要とするなら、デッドロックに陥りうる。コンピュータシステムでは、スレッドやプロセスがミューテックス、セマフォ、入出力装置を競合して取得しようとする際、マルチプログラミングや並列計算でデッドロックがしばしば発生する。教育で用いられる古典的な問題には、食事する哲学者の問題や、生産者・消費者問題の変種がある。データベースではトランザクションロックやインデックスでデッドロックが起こりうるほか、オペレーティングシステムやデバイスドライバでもその防止が求められる。電気通信システムでは、プロセスの状態と空チャネルによってデッドロックを厳密に定義する。マルチプロセッシング向け、またはリアルタイム動作向けに設計されたシステムでは、特定の種類のデッドロックを低減または排除するための特別な技法が用いられる。

デッドロックへの対処法

技術者は、デッドロックの危険を管理するために、大きく4つの方策を用いる。

• 防止：必要条件のいずれかを排除する。たとえば、プロセスに必要な資源をすべて一度に要求させることで、「保持と待機」を認めない。
• 回避：システム全体の状態を把握して割り当てを決定する。たとえば、システムが安全な状態にとどまる場合にのみ資源を割り当てるアルゴリズムを使用する。
• 検出と回復：デッドロックの発生を許容する一方、待機グラフや資源割当ての検査によって検出し、選択したプロセスを中止またはロールバックして循環を断ち切る。
• 緩和技法：タイムアウト、資源取得順序の規則化、権限の縮小、またはノンブロッキング・アルゴリズムの設計により、循環が形成される可能性を低減する。

関連概念との違いと留意点

デッドロックは関連する問題とは区別される。ライブロックは、主体が進展しないまま状態を継続的に変化させる状態である。一方、飢餓状態は、他の主体が進行しているにもかかわらず、特定の主体だけが恒常的に資源を与えられない状態をいう。一部のシステムでは、排他的アクセスを保証するためにハードウェアや優先度の仕組みを使用する。これによりソフトウェア層のデッドロックは減らせるが、循環待機を生む設計上の誤りを完全に除去することはできない。デッドロックはタイミングや相互作用のパターンに左右されることが多いため、万能の解決策は存在しない。設計者は性能、複雑性、正確性の間のトレードオフに基づき、適切な防止、回避、または回復の戦略を選択する。