デッドロック（コンピュータサイエンス）

並行コンピューティングにおいて、デッドロックとは、あるグループのどのメンバーも、自分自身を含む他のメンバーがアクション（メッセージの送信や、より一般的にはロックの解除など）を起こすのを待つため、先に進めない状況を指します。 [ ^{1]デッドロックは、}マルチプロセッシングシステム、並列コンピューティング、分散システムでよく見られる問題です。これらのコンテキストでは、システムがソフトウェアロックまたはハードウェアロックを使用して共有リソースを調停し、プロセス同期を実装することが多いためです。^[2]

オペレーティングシステムでは、プロセスまたはスレッドが待機状態になったときにデッドロックが発生します。これは、要求されたシステムリソースが別の待機中のプロセスによって保持されており、そのプロセスがさらに別の待機中のプロセスによって保持されている別のリソースを待機しているためです。^[3]プロセスが要求したリソースが、それ自体が待機中の別のプロセスによって使用されているために、プロセスの状態を無期限に変更できない場合、システムはデッドロック状態にあると言われます。^[4]

通信システムでは、デッドロックは主にリソースの競合ではなく、信号の損失や破損によって発生します。^[5]

リソースのデッドロック状況は、システム内で以下の条件がすべて同時に発生した場合にのみ発生する可能性があります。^[6]

1. 相互排他性：複数のリソースは共有できず、一度に1つのプロセスのみが各リソースを使用できます。 ^{[7] [8]}
2. 保留して待機またはリソース保持:プロセスは現在少なくとも 1 つのリソースを保持しており、他のプロセスによって保持されている追加のリソースを要求しています。
3. プリエンプションなし:リソースは、それを保持しているプロセスによってのみ自発的に解放できます。
4. 循環待機:各プロセスは、別のプロセスが保持しているリソースを待機している必要があり、そのリソースは最初のプロセスがリソースを解放するのを待機しています。一般的に、待機プロセスの集合P = { P ₁、P ₂、 ...、P _N } があり、P _1はP ₂が保持しているリソースを待機し、P _{2 は}P ₃が保持しているリソースを待機し、 P _NがP ₁が保持しているリソースを待機するまで続きます。^{[4] [9]}

これら4つの条件は、1971年にエドワード・G・コフマン・ジュニアが発表した論文で初めて説明されたことから、コフマン条件として知られています^。[9]

これらの条件は、単一インスタンスのリソースシステムではデッドロックを生成するのに十分ですが、リソースの複数のインスタンスを持つシステムではデッドロックが発生する可能性があることを示しているだけです。^[10]

現在のほとんどのオペレーティングシステムはデッドロックを防ぐことができません。^[11]デッドロックが発生すると、オペレーティングシステムによって対応方法が異なり、非標準的な方法が使用されます。ほとんどのアプローチは、4つのコフマン条件のうちの1つ、特に4番目の条件の発生を防ぐことで機能します。^[12]主なアプローチは次のとおりです。

このアプローチでは、デッドロックは決して発生しないと想定されています。これは、ダチョウアルゴリズムの応用でもあります。^{[12] [13]}このアプローチは、当初MINIXとUNIXで使用されていました。^[9]これは、デッドロックの発生間隔が大きく、毎回発生するデータ損失が許容できる場合に使用されます。

デッドロックが決して発生しないことが正式に証明されていれば、デッドロックを無視することは安全に行うことができます。一例としてRTICフレームワークが挙げられます。^[14]

デッドロック検出では、デッドロックの発生が許容されます。次に、システムの状態が検査され、デッドロックが発生したことが検出され、その後修正されます。リソース割り当てとプロセスの状態を追跡するアルゴリズムが採用され、検出されたデッドロックを除去するために、1 つ以上のプロセスをロールバックして再起動します。各プロセスがロックしているリソースや現在要求しているリソースは、オペレーティング システムのリソース スケジューラに認識されているため、すでに発生したデッドロックを検出することは簡単です。^[13]

デッドロックが検出されると、次のいずれかの方法で修正できます。^{[引用が必要]}

1. プロセスの終了:デッドロックに関係する 1 つ以上のプロセスを中止できます。デッドロックに関係するすべての競合プロセスを中止することもできます。これにより、デッドロックが確実かつ迅速に解決されます。 ^{[引用が必要]}ただし、部分的な計算が失われるため、コストが高くなります。または、デッドロックが解決されるまで、一度に 1 つのプロセスを中止することもできます。このアプローチでは、中止するたびにアルゴリズムがシステムがまだデッドロック状態にあるかどうかを判断する必要があるため、オーバーヘッドが高くなります。^{[引用が必要]}終了候補を選択する際には、プロセスの優先度や経過時間など、いくつかの要因を考慮する必要があります。^{[引用が必要]}
2. リソースのプリエンプション:デッドロックが解消されるまで、さまざまなプロセスに割り当てられたリソースが次々とプリエンプトされ、他のプロセスに割り当てられることがあります。^{[15] [検証失敗]}

デッドロック防止は、4 つのコフマン条件のいずれかの発生を防ぐことによって機能します。

• 相互排他条件を削除すると、どのプロセスもリソースに排他的にアクセスできなくなります。これは、スプールできないリソースでは不可能です。ただし、スプールされたリソースであっても、デッドロックは発生する可能性があります。相互排他を回避するアルゴリズムは、非ブロッキング同期アルゴリズムと呼ばれます。
• プロセスが起動する前（または特定の操作セットに着手する前）に必要なすべてのリソースを要求するようにすることで、保留と待機またはリソース保持の条件を取り除くことができます。この事前の知識を満たすことはしばしば困難であり、いずれにしてもリソースの非効率的な使用です。別の方法は、プロセスがリソースがない場合にのみリソースを要求するようにすることです。まず、プロセスは必要なすべてのリソースを最初から要求する前に、現在保持しているすべてのリソースを解放する必要があります。これもまた、多くの場合非現実的です。これは、リソースが割り当てられても長期間使用されない可能性があるためです。また、人気のあるリソースを必要とするプロセスは、そのようなリソースが常にいずれかのプロセスに割り当てられている可能性があるため、無期限に待機する必要がある可能性があり、その結果、リソースが不足します。^{[16] （}トークンのシリアル化などのこれらのアルゴリズムは、オールオアナッシングアルゴリズムとして知られています。）
• プリエンプションなしの状態は、プロセスが一定時間リソースを保持できなければならないため、回避が困難または不可能な場合もあります。そうしないと、処理結果に一貫性がなくなったり、スラッシングが発生したりする可能性があります。ただし、プリエンプションを強制できないと、優先順位アルゴリズムに干渉する可能性があります。「ロックアウトされた」リソースのプリエンプションは、通常、ロールバックを意味し、オーバーヘッドが非常に大きいため回避する必要があります。プリエンプションを許可するアルゴリズムには、ロックフリーおよびウェイトフリー アルゴリズムと、楽観的同時実行制御があります。プロセスがリソースを保持していて、すぐに割り当てることができない別のリソースを要求した場合、そのプロセスが現在保持しているすべてのリソースを解放することで、この状態を解除できます。
• 最後の条件は循環待機状態です。循環待機を回避するアプローチには、クリティカル セクション中の割り込みを無効にしたり、階層を使用してリソースの部分的な順序を決定することが含まれます。明らかな階層が存在しない場合は、リソースのメモリ アドレスを使用して順序が決定され、列挙の昇順でリソースが要求されます。^[4] ダイクストラのソリューションも使用できます。

デッドロック防止と同様に、デッドロック回避アプローチは、システムでデッドロックが発生しないようにします。「デッドロック回避」という用語は、言語的な文脈では「デッドロック防止」に非常に近いように見えますが、デッドロック処理の文脈では非常に異なります。デッドロック回避では、防止で見られるような条件は課されませんが、ここでは各リソース要求がデッドロックを引き起こすことなく安全に満たされるかどうかを確認するために慎重に分析されます。

デッドロックを回避するには、プロセスが存続期間中にどのリソースを要求し使用するかという追加情報をオペレーティングシステムに事前に提供する必要があります。デッドロック回避アルゴリズムは、要求されたリソースが割り当てられた場合、将来デッドロックが発生する可能性がないかどうかを調べて、すべての要求を分析します。このアプローチの欠点は、将来リソースがどのように要求されるかについて事前に情報が必要であることです。最もよく使用されるデッドロック回避アルゴリズムの1つは、バンカーのアルゴリズムです。^[17]

ライブロックはデッドロックに似ていますが、ライブロックに関係するプロセスの状態は互いに常に変化し、どれも進行しないという点が異なります。

^{この用語は、1975年の論文[18]}で、航空会社の予約システムの調査に関連してエドワード・A・アシュクロフトによって造られました。 ^{[19]ライブロックは}リソース不足の特殊なケースであり、一般的な定義では、特定のプロセスが進行していないことだけが述べられています。^[20]

ライブロックは、デッドロックを検出して回復するアルゴリズムの一部にリスクがあります。複数のプロセスがアクションを起こすと、デッドロック検出アルゴリズムが繰り返しトリガーされる可能性があります。これは、1つのプロセス（任意または優先順位によって選択された）だけがアクションを起こすようにすることで回避できます。^[21]

分散トランザクションまたは同時実行制御が使用されている場合、分散システムでは分散デッドロックが発生する可能性があります。

分散デッドロックは、デッドロック検出器でローカル待機グラフからグローバル待機グラフを構築するか、エッジ追跡などの分散アルゴリズムによって検出できます。

ファントム デッドロックとは、分散システムでシステム内部の遅延により誤って検出されるが、実際には存在しないデッドロックです。たとえば、プロセスがリソースR1 を解放し、 R2の要求を発行し、最初のメッセージが失われたり遅延したりした場合、コーディネーター (デッドロックの検出器) は、デッドロックを誤って結論付ける可能性があります ( R1がある状態でR2 を要求するとデッドロックが発生する場合)。

• Kaveh, Nima; Emmerich, Wolfgang. 「分散オブジェクト システムにおけるデッドロック検出」(PDF)。ロンドン: ユニバーシティ カレッジ ロンドン。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です
• Bensalem, Saddek; Fernandez, Jean-Claude; Havelund, Klaus; Mounier, Laurent (2006)。「実行時分析によって検出されたデッドロックの可能性の確認」。並列および分散システム: テストとデバッグに関する 2006 年ワークショップの議事録。ACM。pp . 41–50。CiteSeerX 10.1.1.431.3757。doi :  10.1145 / 1147403.1147412。ISBN 978-1595934147. S2CID  2544690。
• Coffman, Edward G. Jr.; Elphick, Michael J.; Shoshani, Arie (1971). 「システムデッドロック」(PDF) . ACM Computing Surveys . 3 (2): 67–78. doi :10.1145/356586.356588. S2CID  15975305.
• Mogul, Jeffrey C.; Ramakrishnan, KK (1997). 「割り込み駆動型カーネルにおける受信ライブロックの排除」. ACM Transactions on Computer Systems . 15 (3): 217–252. CiteSeerX  10.1.1.156.667 . doi :10.1145/263326.263335. ISSN  0734-2071. S2CID  215749380.
• Havender, James W. (1968). 「マルチタスクシステムにおけるデッドロックの回避」IBM Systems Journal . 7 (2): 74. doi :10.1147/sj.72.0074. 2012年2月24日時点のオリジナルよりアーカイブ。 2009年1月27日閲覧。
• Holliday, JoAnne L.; El Abbadi, Amr. 「分散デッドロック検出」。分散コンピューティング百科事典。2015年11月2日時点のオリジナルよりアーカイブ。 2004年12月29日閲覧。
• Knapp, Edgar (1987). 「分散データベースにおけるデッドロック検出」. ACM Computing Surveys . 19 (4): 303–328. CiteSeerX  10.1.1.137.6874 . doi :10.1145/45075.46163. ISSN  0360-0300. S2CID  2353246.
• Ling, Yibei; Chen, Shigang; Chiang, Jason (2006). 「最適なデッドロック検出スケジューリングについて」. IEEE Transactions on Computers . 55 (9): 1178–1187. CiteSeerX  10.1.1.259.4311 . doi :10.1109/tc.2006.151. S2CID  7813284.

• 「Java スレッドにおける高度な同期」、Scott Oaks と Henry Wong 著
• デッドロック検出エージェント
• ポートランドパターンリポジトリのデッドロック
• 「デッドロック」の語源