どちらのプロセスも実行を継続するにはリソースが必要です。P1は 追加のリソースR1 を必要とし、リソースR2 を保有しています。P2は 追加のリソースR2を必要とし、リソース R1 を保有しています。どちらのプロセスも実行を継続できません。 4つのプロセス（青線）が、右優先のポリシーに従って1つのリソース（灰色の円）を奪い合っています。すべてのプロセスが同時にリソースをロックすると（黒線）、デッドロックが発生します。デッドロックは、対称性を破ることで解消できます。 並行コンピューティング において、デッドロック とは、あるグループのエンティティのどのメンバーも、メッセージの送信や、より一般的にはロックの 解放などのアクションを自身を含めた他のメンバーが行うのを待つため、処理を進めることができない状況を指します。[ 1 ] デッドロックは、マルチプロセッシング システム、並列コンピューティング 、分散システム でよく発生する問題です。これらのシステムでは、共有リソースの仲裁やプロセス 同期の実装にソフトウェアまたはハードウェアロックがよく使用されるためです。[ 2 ]
オペレーティングシステム では、デッドロックは、要求 されたシステムリソースが別の待機中のプロセスによって保持され、そのプロセスがさらに別の待機中のプロセスによって保持されている別のリソースを待機しているために、 プロセス またはスレッド が待機状態に入ったときに発生します。[ 3 ] [ 4 ]
通信システム では、デッドロックは主にリソースの競合ではなく、信号の損失や破損によって発生します。[ 5 ]
2つのプロセスが、2つの資源を逆の順序で奪い合う。単一のプロセスが実行される。 後の工程は待たなければならない。 デッドロックとは、最初のプロセスが最初のリソースをロックしたのと同時に、2番目のプロセスが2番目のリソースをロックしようとしたときに発生する現象です。 デッドロックは、最初のプロセスをキャンセルして再起動することで解消できます。
条件 リソースのデッドロック状態は、システム内で以下のすべての条件が同時に発生した場合にのみ発生する可能性があります。[ 6 ]
相互排他 : [ 7 ] [ 8 ] 保持と待機、 またはリソース保持： プロセスが現在少なくとも1つのリソースを保持しており、他のプロセスによって保持されている追加のリソースを要求している状態。プリエンプション なし：循環待機: 各プロセスは、別のプロセスが保持しているリソースを待機する必要があり、その別のプロセスは、最初のプロセスがリソースを解放するのを待機します。一般に、待機中のプロセスの集合 P = { P 1 、P 2 、 ...、P N P 1は P 2 が保持しているリソースを待機し、P 2 は P 3 が保持しているリソースを待機し、 P N が P 1 が保持しているリソースを待機するまで続きます。[ 4 ] [ 9 ] これらの4つの条件は、 1971年にエドワード・G・コフマン・ジュニア が発表した論文で初めて記述されたことから、コフマン条件として知られています 。[ 9 ]
これらの条件は、単一インスタンスのリソースシステムではデッドロックを引き起こすのに十分ですが、リソースのインスタンスが複数あるシステムではデッドロックの可能性を示すにすぎません。[ 10 ]
デッドロック処理 現在のほとんどのオペレーティングシステムはデッドロックを防ぐことができません。[ 11 ] コフマン条件 のうちの 1 つ、特に 4 番目の条件の発生を防ぐことによって機能します。[ 12 ]
検出 デッドロック検出では、デッドロックの発生が許容されます。次に、システムの状態を調べてデッドロックが発生したことを検出し、その後修正します。リソース割り当てとプロセス状態を追跡するアルゴリズムが使用され、検出されたデッドロックを解消するために、1 つ以上のプロセスをロールバックして再起動します。各プロセスがロックしている、または現在要求しているリソースはオペレーティングシステムのリソーススケジューラに知られているため、既に発生したデッドロックを検出することは容易です。 [ 13 ]
デッドロックが検出された後、以下のいずれかの方法を使用して修正できます。[ 15 ]
プロセスの終了: デッドロックに関与する 1 つ以上のプロセスを中止することができます。デッドロックに関与する競合するすべてのプロセス を中止することもできます。これにより、デッドロックが確実かつ迅速に解決されます。ただし、部分的な計算が失われるため、コストが高くなります。または、デッドロックが解決されるまで、一度に 1 つのプロセスを中止することもできます。このアプローチでは、中止するたびにシステムがまだデッドロック状態にあるかどうかをアルゴリズムで判断する必要があるため、オーバーヘッドが高くなります。プロセスの優先度や経過時間など、終了候補を選択する際にはいくつかの要素を考慮する必要があります。[ 15 ] リソースのプリエンプション： さまざまなプロセスに割り当てられたリソースは、デッドロックが解消されるまで、順次プリエンプションされて他のプロセスに割り当てられることがあります。[ 16 ]
防止 （A）2つのプロセスが1つのリソースを競合し、先着順でリソースをロックする。（B）両方のプロセスが同時にリソースをロックするとデッドロックが発生する。（C）デッドロックはロックの対称性を破ることで解決 できる。（D）デッドロックはロック機構の対称性を破ることで防止 できる。 デッドロック防止は、コフマンの4つの条件のうちいずれか1つが発生するのを防ぐことによって機能します。
相互排他 条件をなくすということは、どのプロセスもリソースへの排他的アクセスを持たないことを意味します。これは、スプールできないリソースでは不可能です。しかし、スプール可能なリソースであっても、デッドロックが発生する可能性は依然としてあります。相互排他を回避するアルゴリズムは、 ノンブロッキング同期 アルゴリズムと呼ばれます。保持と待機 、またはリソース保持 条件は、プロセスが起動前（または特定の一連の操作を開始する前）に必要なすべてのリソースを要求するように要求することで解消できます。しかし、この事前知識を満たすことはしばしば困難であり、いずれにしてもリソースの非効率的な使用です。別の方法として、プロセスがリソースを全く持っていない場合にのみリソースを要求するように要求する方法があります。まず、プロセスは必要なすべてのリソースを最初から要求する前に、現在保持しているすべてのリソースを解放する必要があります。これも多くの場合、非現実的です。リソースが割り当てられても長期間使用されない場合があるためです。また、人気のあるリソースを必要とするプロセスは、そのようなリソースが常に何らかのプロセスに割り当てられる可能性があるため、無期限に待機しなければならず、結果としてリソース枯渇を 引き起こす可能性があります。[ 17 ] （トークンのシリアル化 などのこれらのアルゴリズムは、全か無かのアルゴリズム として知られています。） プロセスが一定時間リソースを保持できなければ処理結果が不整合になったり、スラッシングが 発生したりする可能性があるため、プリエンプションなしの状態 を回避することは困難または不可能な場合もあります。ただし、プリエンプションを強制できないと、優先度 アルゴリズムに支障をきたす可能性があります。「ロックアウト」されたリソースのプリエンプションは一般的にロールバックを 意味し、オーバーヘッドが非常に大きいため避けるべきです。プリエンプションを許可するアルゴリズムには、ロックフリーおよび待機フリーのアルゴリズム 、楽観的並行性制御 などがあります。プロセスがリソースを保持していて、すぐに割り当てることができない別のリソースを要求する場合、そのプロセスが現在保持しているすべてのリソースを解放することで、この状態を解消できます。 最後の条件は循環待機 条件です。循環待機を回避するアプローチには、クリティカルセクション中に割り込みを無効にすることや、階層を使用してリソースの部分的な順序 を決定することなどがあります。明らかな階層が存在しない場合は、リソースのメモリ アドレスを使用して順序を決定し、列挙の昇順でリソースを要求します。[ 4 ] ダイクストラ法 も使用できます。
デッドロック回避 デッドロック防止と同様に、デッドロック回避アプローチは、システム内でデッドロックが発生しないことを保証します。「デッドロック回避」という用語は、言語的には「デッドロック防止」と非常に近いように見えますが、デッドロック処理の文脈では大きく異なります。デッドロック回避は、防止のように条件を課すのではなく、各リソース要求を慎重に分析し、デッドロックを引き起こすことなく安全に処理できるかどうかを確認します。
デッドロック回避には、プロセスがその存続期間中に要求および使用するリソースに関する追加情報をオペレーティングシステムに事前に提供する必要があります。デッドロック回避アルゴリズムは、要求されたリソースが割り当てられた場合、将来デッドロックが発生する可能性がないことを検証することにより、すべての要求を分析します。このアプローチの欠点は、将来どのようにリソースが要求されるかについての情報を事前に必要とすることです。最もよく使用されるデッドロック回避アルゴリズムの 1 つは、バンカーのアルゴリズム です。[ 18 ]
ライブロック ライブロックは デッドロックに似ていますが、ライブロックに関与するプロセスの状態が互いに対して絶えず変化し、どのプロセスも進行しない点が異なります。
この用語は、エドワード・A・アシュクロフト が1975年の論文[ 19 ] [ 20 ] 。ライブロックはリソース不足 の特殊なケースであり、一般的な定義では特定のプロセスが進行していないことだけが述べられています[ 21 ] 。
ライブロックは、デッドロック を検出して回復する一部のアルゴリズム におけるリスクです。複数のプロセスがアクションを実行すると、デッドロック検出アルゴリズムが 繰り返しトリガーされる可能性があります。これは、1つのプロセスのみがアクションを実行するようにすることで回避できます（任意に選択するか、優先順位によって選択）。[ 22 ]
分散デッドロック 分散システムでは、 分散トランザクション や並行性制御 が使用されている場合に、分散デッドロックが 発生する可能性があります。
集中型システム とは異なり、分散型システムでは共有メモリが存在せず、ノード間の連携が必要となるため、デッドロックの検出と解決はより複雑になります。このような状況に対処するために、待機グラフ 、分散アルゴリズム （エッジ追跡アルゴリズム、例：Chandy-Misra-Haas アルゴリズム）、デッドロック防止 （例：タイムアウトベースの手法）などの技術が用いられます。課題は、ネットワークの遅延や部分的な障害による誤検出や誤検出を回避し、一貫性を確保することです。
ファントムデッドロック とは、分散システムにおいてシステム内部の遅延によって誤って検出されるものの、実際には存在しないデッドロックのことです。例えば、プロセスがリソースR1を解放し、 R2 を要求する際に、最初のメッセージが失われたり遅延したりした場合、コーディネータ（デッドロック検出器）は、R1を保持している状態でR2を要求すると デッドロック が発生すると誤って判断する可能性があります。
参考文献 ↑ クーロリス、ジョージ (2012).分散システム概念と設計 . ピアソン. p. 716. ISBN 978-0-273-76059-7 。 ↑ Padua, David (2011). 並列コンピューティング百科事典 . Springer. p. 524. ISBN 9780387097657 2021年4月18日にオリジナルからアーカイブされました。2020年 10月16日 に取得 。↑ Falsafi, Babak; Midkiff, Samuel; Dennis, JackB; Dennis, JackB; Ghoting, Amol; Campbell, Roy H; Klausecker, Christof; Kranzlmüller, Dieter; Emer, Joel; Fossum, Tryggve; Smith, Burton; Philippe, Bernard; Sameh, Ahmed; Irigoin, François; Feautrier, Paul; Praun, Christoph von; Bocchino, Robert L.; Snir, Marc; George, Thomas; Sarin, Vivek; Jann, Joefon (2011). "Deadlocks". 並列コンピューティング百科事典 . ボストン、マサチューセッツ州: Springer US. pp. 524–527 . doi : 10.1007/978-0-387-09766-4_282 . ISBN 978-0-387-09765-7 S2CID 241456017デッドロックとは、共有リソースにアクセスできる複数のプロセスで構成されるシステムで発生する可能性のある状態です。デッドロックは、2つ以上のプロセスが互いにリソースの解放を待っている状態を指します。どのプロセスも処理を進めることができません。 1 2 3 シルベルシャッツ、アブラハム (2006). オペレーティングシステム原理 (第 7 版). ワイリー・インディア. p. 237. ISBN 9788126509621 2022年1月25日にオリジナルからアーカイブされました。2020年 10月16日 に取得 。↑ シュナイダー、G. マイケル (2009). コンピュータサイエンスへの招待 . Cengage Learning. p. 271. ISBN 978-0324788594 2021年4月18日にオリジナルからアーカイブされました。2020年 10月16日 に取得 。↑ シルベルシャッツ、アブラハム (2006). オペレーティングシステム原理 (第7 版). ワイリー・インディア. p. 239. ISBN 9788126509621 2021年4月18日にオリジナルからアーカイブされました。2020年 10月16日 に取得 。↑ オペレーティングシステム概念 。Wiley。2012年。319 ページ 。ISBN 978-1-118-06333-0 。↑ "ECS 150 Spring 1999: デッドロックの4つの必要十分条件" . nob.cs.ucdavis.edu . 2018年4月29日のオリジナルから アーカイブ済み. 2018年 4月29日 取得 . 1 2 3 渋、K. (2009)。 組み込みシステム入門 (第 1 版)。タタ・マグロウヒル教育。 p. 446.ISBN 9780070145894 2021年4月18日にオリジナルからアーカイブされました。2020年 10月16日 に取得 。↑ 「オペレーティングシステム：デッドロック」 。www.cs.uic.edu 。 2020年5月28日にオリジナルから アーカイブ 。 2020年 4月25日 に取得 。 リソースカテゴリに複数のインスタンスが含まれている場合、リソース割り当てグラフにサイクルが存在すると、デッドロックの可能性が示唆されますが、必ずしもデッドロックが発生するとは限りません。たとえば、以下の図7.3と7.4を参照してください。 ↑ シルベルシャッツ、アブラハム (2006). オペレーティングシステム原理 (第7 版). ワイリー・インディア. p. 237. ISBN 9788126509621 2021年4月18日にオリジナルからアーカイブされました。2020年 10月16日 に取得 。1 2 スチュアート、ブライアン L. (2008). オペレーティングシステムの原理 （第 1 版）. Cengage Learning. p. 446. ISBN 9781418837693 2021年4月18日にオリジナルからアーカイブされました。2020年 10月16日 に取得 。1 2 Tanenbaum, Andrew S. (1995). 分散オペレーティングシステム （第1 版）. Pearson Education. p. 117. ISBN 9788177581799 2021年4月18日にオリジナルからアーカイブされました。2020年 10月16日 に取得 。↑ 「序文 - リアルタイム割り込み駆動並行処理」 。 2020年9月18日にオリジナルから アーカイブ済み 。 2020年 10月1日 に取得。 1 2 "6.2: デッドロックの検出と防止" . Engineering LibreTexts . 2021年3月22日. 2025年 10月22日 取得 . ↑ 「IBM Knowledge Center」 。www.ibm.com 。 2017 年3月19日のオリジナルから アーカイブ済み 。 2018年 4月29日 取得。 ↑ シルベルシャッツ、アブラハム (2006). オペレーティングシステム原理 (第7 版). ワイリー・インディア. p. 244. ISBN 9788126509621 2021年4月18日にオリジナルからアーカイブされました。2020年 10月16日 に取得 。↑ 「オペレーティングシステム（OS）におけるデッドロック回避アルゴリズム」 . Electronics Mind . 2022年1月26日。 ↑ Ashcroft, EA (1975). "並列プログラムに関する主張の証明" . Journal of Computer and System Sciences . 10 : 110– 135. doi : 10.1016/S0022-0000(75)80018-3 . ↑ Kwong, YS (1979). 「並列プログラムにおけるライブロックの不在について」. Semantics of Concurrent Computation . Lecture Notes in Computer Science. Vol. 70. pp. 172–190 . doi : 10.1007/BFb0022469 . ISBN 3-540-09511-X 。↑ アンダーソン、ジェームズ H. ; ヨンジク キム (2001). 「共有記憶の相互排除：1986 年以降の主要な研究動向」 。2006 年 5 月 25 日のオリジナルから アーカイブ。 ↑ Zöbel, Dieter (1983 年 10 月) 「 デッドロック問題: 分類文献目録」 ACM SIGOPS Operating Systems Review 17 (4): 6– 15. doi : 10.1145/850752.850753 . ISSN 0163-5980 . S2CID 38901737 .
さらに読む Kaveh, Nima; Emmerich, Wolfgang. "分散オブジェクトシステムにおけるデッドロック検出" (PDF) .第 8 回欧州ソフトウェアエンジニアリング会議と 第 9 回 {ACM} {SIGSOFT} ソフトウェアエンジニアリングの基礎に関する国際シンポジウム 2001 の合同開催、オーストリア、ウィーン、2001 年 9 月 10 ～ 14 日 . ACM SIGSOFT ソフトウェアエンジニアリングノート . ACM. doi : 10.1145/503209.503216 . 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). "System Deadlocks" (PDF) . ACM Computing Surveys . 3 (2): 67– 78. doi : 10.1145/356586.356588 . S2CID 15975305 . 2012年1月27日にオリジナル(PDF) からアーカイブ済み。 2004年 12月20日 取得 。 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). "On Optimal Deadlock Detection Scheduling". IEEE Transactions on Computers . 55 (9): 1178–1187 . Bibcode : 2006ITCmp..55.1178L . CiteSeerX 10.1.1.259.4311 . doi : 10.1109/tc.2006.151 . S2CID 7813284 .
外部リンク 「Javaスレッドにおける高度な同期」スコット・オークス、ヘンリー・ウォン著 デッドロック検出エージェント ポートランドパターンリポジトリのDeadLock 「行き詰まり」の語源
