デッドロック：それは何ですか、どのように検出、処理、防止するのですか？
1. 概要
このチュートリアルでは、実際の例を使用して、デッドロックを防止、回避、検出、および無視する方法について説明します。
2. デッドロックの概要
デッドロックは、プロセスがリソースを共有するほとんどすべての状況で発生する可能性があります。 これはどのコンピューティング環境でも発生する可能性がありますが、複数のプロセスが異なるリソースで動作する分散システムで広く使用されています。
この状況では、あるプロセスが別のプロセスによってすでに保持されているリソースを待機している可能性があります。 デッドロックは、鶏が先か卵が先かに似ています。
デッドロックの例を見てみましょう。
3つのプロセスP1、P2、およびP3と、3つのリソースR1、R2、およびR3があるとします。
ここで、P1がP2によって保持されているリソースR2を要求するとします。 このような場合、P1はR2なしでは続行せず、P3が保持するR3を取得するまでP2はリソース2を解放できないため、無期限に待機します。 同じことがP1とP3にも当てはまります。 したがって、これはOSのデッドロック状況の理想的な例です。
3. デッドロックに必要な条件
次の4つの条件が同時に成立すると、デッドロックが発生する可能性があります。
最初の条件は相互排除です。この条件では、異なるプロセス間で同時にリソースを共有することはできません。
たとえば、2人で同時に用紙を印刷したい場合、このプロセスは実行できません。 システムが印刷物（リソース）をリリースするまで待つ必要があります。 したがって、一度に1つのプロセスにのみリソースを割り当てることができます。
デッドロックに必要な2番目の条件は、ホールドアンドウェイトまたはリソースホールドです。この条件では、プロセスは少なくとも1つのリソースを同時に保持し、一度に別のリソースを待機します。 ここでは、プロセスは実行状態ではありません。 待機状態です。
3番目の条件はプリエンプションなしです。プロセスがリソースを保持している場合、リソースを解放するまで、リソースをプロセスから強制的に削除することはできません。 このステートメントは、プロセスが待機状態にある場合にも当てはまります。
デッドロックの最終条件は循環待機です。プロセスP1がリソースR2を待機していると仮定します。 これで、特定のリソースR2がプロセスP2によってすでに保持されています。 プロセスP2は、次のプロセスによって保持されているリソースを待機しています。 これは、最後のプロセスが最初のプロセスによって保持されているリソースを待機するまで続きます。
循環待機条件は循環チェーンを作成し、すべてのプロセスを待機状態にします。
4. デッドロック防止
デッドロック防止プロセスでは、 OSは、デッドロックの原因となった4つの条件のいずれかを回避することにより、デッドロックの発生を防止します。 OSが必要な条件のいずれかを回避できる場合、デッドロックは発生しません。
4.1. 相互排除なし
複数のプロセスが同時に1つのリソースにアクセスできることを意味します。複数のプロセスが同じリソースに同時にアクセスすると、混乱が生じるため、不可能です。 また、プロセスは完了しません。 したがって、これは実行可能ではありません。 したがって、OSは相互排除を回避できません。
この問題を理解するために実際的な例を見てみましょう。 ジャックとジョーンズは一杯のスープを共有します。 両方とも同じボウルからスープを飲み、同時に1つのスプーンを使用したいのですが、これは現実的ではありません。
4.2. ホールドアンドウェイトなし
保留と待機を回避するために、実行を開始する前に必要なすべてのリソースを取得する方法は多数あります。ただし、プロセスは一度に1つのリソースを使用するため、これも実行できません。 ここでは、リソース使用率は非常に少なくなります。
実行を開始する前に、プロセスはそれを完了するために必要なリソースの数を知りません。 それに加えて、プロセスが完了してリソースを解放するバス時間も不明です。
別の方法は、プロセスがリソースを保持していて、追加のリソースが必要な場合、取得したリソースを解放する必要があることです。このようにして、保留と待機の状態を回避できますが、結果として[X214X ]飢餓。
4.3. プリエンプションなしの削除
デッドロックを引き起こす理由の1つは、プリエンプションがないことです。 これは、プロセスが待機状態であっても、CPUがプロセスから取得したリソースを強制的に取得できないことを意味します。プリエンプションなしを削除し、待機中のプロセスからリソースを強制的に取得できれば、デッドロック。 これは、デッドロックを回避するための実装可能なロジックです。
たとえば、ジョーンズからボウルを取り出して、ジャックがスープを飲むようになったときにそれをジャックに渡すようなものです。 ジョーンズが最初に来てリソースを取得し、待機状態になったと仮定しましょう。 ジャックが来たとき、仕出し屋はジョーンズからボウルを強引に取り、あなたが待っている状態にあるならボウルを持たないように彼に言いました。
4.4. サーキュラーウェイトの削除
循環待機では、2つのプロセスが相互に保持されているリソースの待機状態でスタックします。循環待機を回避するために、すべてのリソースに整数の数値を割り当てます。昇順または降順でリソースにアクセスします。
プロセスが昇順でリソースを取得する場合、そのリソースの整数値が高い場合にのみ、新しい追加リソースにアクセスできます。 また、そのリソースの整数値が小さい場合は、新しいリソースを取得する前に取得したリソースを解放する必要があり、その逆の場合は降順です。
たとえば、仕出し屋は、ボウルとスプーンにそれぞれ1と2の整数値を割り当てたため、リソースに昇順でアクセスできます。 さて、ジョーンズがボウルを持っているなら、彼はスプーンを持つことができます。 しかし、ジャックはより大きな整数値のスプーンを持っているので、最初にスプーンを離れてからボウルを取る必要があります。 その後、彼はスプーンにスープを飲ませます。
5. デッドロックの回避
デッドロック回避メソッドは、OSがデッドロックの発生を回避するのに役立ちます。 OSは、実行を開始する前に、ライフサイクル全体でプロセスに必要な最大必要リソースのログを保持します。 OSは、新しく要求されたリソースをプロセスに割り当てる前に、システムの状態を継続的にチェックします。
基本的に、デッドロック回避では、OSは周期的な待機状態にならないようにします。 OSが将来デッドロックを引き起こすことなく、要求されたすべてのリソースをプロセスに割り当てることができる場合、それは安全な状態と呼ばれます。 そして、OSが要求されたすべてのリソースを割り当てられない場合将来的にデッドロックを引き起こします。これは危険な状態として知られています。
5.1. リソース割り当てグラフ（RAG）アルゴリズム
RAGを使用すると、OSでのデッドロックの発生を予測できます。
リソース割り当てグラフは、割り当てられたすべてのリソース、使用可能なリソース、およびOSの現在の状態を図で表したものです。各プロセスに割り当てられているリソースの数と、将来必要になるリソースの数を把握できます。 したがって、デッドロックを簡単に回避できます。
すべてのグラフには頂点とエッジがあるため、同じように、RAGにも頂点とエッジがあります。 RAGには、プロセス頂点とリソース頂点の2つの頂点と、割り当てエッジと要求エッジの2つのエッジがあります。 ほとんどの場合、頂点は長方形で、エッジは円形で表されます。
RAGアルゴリズムには、すべてのリソースに単一のインスタンスがある場合にのみ機能するという制限があります。リソースのインスタンスが複数ある場合、デッドロックを特定するのは確実ではありません。 。 サークルを形成する可能性はありますが、デッドロックにつながる可能性があります。 したがって、そのような状況では、銀行家のアルゴリズムを使用してデッドロックを判別します。
たとえば、2つのプロセスP1、P2、および2つのリソースR1、R2とします。
ここで、P1はR1を使用し、将来的には点線で示されているR2を使用します。 現時点では無料です。 P2はR2を要求していますが、後でP1で必要になるため、OSはそれを割り当てません。 したがって、円の形成を回避します。 したがって、デッドロックが発生する可能性を回避できます。 ただし、上記のソリューションから、R2は使用されません。 したがって、リソース使用率は低くなります。
5.2. 銀行家のアルゴリズム
リソースに複数のインスタンスがある場合、銀行家のアルゴリズムを使用します。銀行がリソースを使い果たしてリソースを使い果たしないようにリソースを管理するため、銀行家のアルゴリズムとして知られています。安全でない状態に。 銀行は、銀行システムでローンを割り当てたり認可したりする前に、このアルゴリズムを使用します。
このアルゴリズムでは、ライフサイクルを完了するために各プロセスから必要な最大リソースやOSで使用可能なリソースの合計など、いくつかの事前定義されたデータが必要です。 そのデータから、
このアルゴリズムは、使用可能なリソースの合計、各プロセスに必要な最大リソース、各プロセスに割り当てられたリソースの合計、および現在必要なリソースのマトリックスを維持します。
6. デッドロックの検出と回避
この方法では、OSは将来デッドロックが発生することを想定しています。 そのため、一定の時間間隔でデッドロック検出メカニズムを実行し、デッドロックを検出すると、回復アプローチを開始します。
OSの主なタスクは、デッドロックを検出することです。 すでに説明した2つの検出方法があります。
ここでは、いくつかの即興で同じ方法を使用します。
待機グラフ方式では、OSが円の形成をチェックします。リソース割り当てグラフ（RAG）と少し違いがあります。 ほとんどの場合、RAGと待機グラフの間で混乱が生じます。
RAGと待機グラフの主な違いは、各グラフに含まれる頂点の数です。 RAGグラフには、リソースとプロセスの2つの頂点があります。 待機グラフには、プロセスという1つの頂点があります。
RAGを使用して待機グラフを作成することもできます。
待機グラフは円を描いていません。つまり、システムがデッドロックに陥ることはありません。
複数のインスタンスリソースには、銀行家のアルゴリズムと同じアプローチを使用する安全アルゴリズムを使用します。ただし、必要な最大リソースマトリックスがありません。 割り当てられたマトリックス、使用可能なマトリックス、現在の要件マトリックスの3つのマトリックスしかありません。
これで、OSがデッドロックを検出するとすぐに、回復方法が開始されます。 デッドロックから回復するには、主に2つのアプローチがあります。
6.1. オプティミストアプローチ
楽観的なアプローチの例は、リソースとプロセスのプリエンプションです。このアプローチでは、OSはいくつかのプロセスを選択し、それらのリソースをプリエンプションし、その後、他のプロセスに割り当てます。したがって、OSはサークル。
このアプローチの欠点の1つは、同じプロセスがプリエンプションの犠牲になる可能性があることです。 この状態では、プロセスは飢餓状態に陥ります。
デッドロックが発生していない特定の安全な状態にOSがロールバックする別のアプローチ。 ただし、このために、OSは安全な状態になるまでいくつかのログを維持する必要があります。
この方法の欠点の1つは、プロセスのロールバックの順序を選択するための決定パラメーターがないことです。
6.2. ペシミストアプローチ
1つの悲観的なアプローチは、すべてのデッドロックプロセスを中止することです。これは、デッドロックから回復するためにサイクルを中断する最も簡単な方法ですが、デッドロックを処理する最もコストのかかる方法でもあります。 この方法では、すべてのプロセスを強制終了し、OSはそれらを破棄するか、要件に応じてプロセスの一部を後で再起動します。
また、システムからデッドロックが解消されるまで、一度に1つのプロセスを中止できます。
この方法では、OSは一度に1つのプロセスを強制終了し、最も少ない作業を行ったプロセスを選択します。 その後、デッドロック検出アルゴリズムを実行して、デッドロックが回復したかどうかを確認します。 回復されない場合は、デッドロックが解消されるまでプロセスを強制終了し続けます。
7. デッドロックの無知
これは、デッドロックを処理するために広く使用されている方法の1つです。 この方法では、OSはデッドロックが発生しないことを前提としています。 デッドロック状態が発生した場合、OSはシステムを再起動します。この方法は、OSがエンドユーザー向けである場合に非常に人気があります。
デッドロック無知アプローチは、ユーザーがシステムに直接接触しているLinuxおよびWindowsベースのOSで使用されます。
8. 結論
このチュートリアルでは、OSでのデッドロックの概念について詳しく説明しました。 OSのデッドロックの背後にある考え方を説明するために例を示しました。
さらに、デッドロックを防止、回避、検出、および無視するためのさまざまなアプローチを検討しました。
