オペレーティングシステムのデッドロックとは:条件と検出アルゴリズム

問題を排除するために楽器を試してください





オペレーティングシステムの主な目的は、ハードウェアとソフトウェアのリソース間の適切な通信を提供し、プログラムに共通のサービスを提供することです。オペレーティングシステムプロセスが任意のリソースにアクセスする場合、最初にアクセスする特定のリソースに要求を送信し、次にそのリソースを利用し、最後に使用後にリソースを解放します。多くのプロセスが同時に1つのリソースにアクセスしようとしているとすると、デッドロックという概念が発生するような状況では、一度にすべてのプロセスに1つのリソースを提供することが困難になります。したがって、この記事では、デッドロックがどのように発生するか、およびこのデッドロック状況を克服する方法について説明します。

オペレーティングシステムのデッドロックとは何ですか?

定義: デッドロックは、2つ以上のプロセッサが何らかのイベントの発生を待機している状況ですが、発生しないイベントはデッドロック状態であり、プロセッサはデッドロック状態にあると言われます。たとえば、一方通行の道路で2人の個別のドライバーが運転する2台の車AとBがあるリアルタイムシナリオを想定します。ここで、車Aの運転手が北に向かって移動するのが正しい方向であると言い、車Bの運転手が南に向かって移動するのが正しいと言う状況が発生します。しかし、どちらも後退して別の車を前進させることはできません。この状態はデッドロック状態と呼ばれます。




車-例

車の例

理解を深めるために、2つのリソースR1、R2、および2つのプロセスP1とP2があり、R1がP1に割り当てられ、R2がP2に割り当てられている別の例を考えてみましょう。ここで、P1がR2にアクセスしたい場合、R2はP2によって保持されていることがわかっているので、P2はR1にアクセスしたいのです。つまり、P1はR2にアクセスしたときにのみ実行され、P2もR1にアクセスしたときにのみ実行されます。デッドロック状態です。



プロセッサー-例

プロセッサ-例

デッドロック状態

以下は、すべての条件が同時に発生した場合に発生する4つの重要なデッドロック条件であり、デッドロックが発生する可能性があります。

相互排除

つまり、使用しているリソースはすべて、相互に排他的な方法で使用する必要があります。 1つのプロセスのみが一度に1つのリソースのみを使用する場合。たとえば、印刷プロセスが進行中で、突然別のプロセスが印刷プロセスを中断しようとします。したがって、ここで相互排除の状況では、印刷タスクが完了した後でのみ、次のタスクのみが処理されます。リソースを同時に共有することで相互排除を排除できますが、これは実際には不可能です。

相互排除

相互排除

プリエンプションなし

による 先制攻撃 現在のタスクを中断しようとしている優先タスクがある場合は、ベースのアルゴリズム。現在のタスクを保持し、最初に優先タスクを実行して最初のタスクに戻るプリエンプティブアルゴリズム。上記の例で説明したように、プロセスが実行される限りリソースを保持する状況、つまりP1は実行後にのみR1を解放でき、同様にP2は実行後にのみR2を解放できます。プリエンプションがない場合、デッドロックが発生する可能性があります。


プリエンプションなし-例

プリエンプションなし-例

待ってください

プロセスはいくつかのリソースを保持していて、追加のリソースを待機していますが、それらのリソースは他のプロセスによって取得されます。上記の例から、P1はR1を保持してR2を待機しています。R2はP2によって取得され、P2はR2を保持してR1を待機しています。R1はP1によって取得されているため、システムでデッドロックが発生する可能性があります。

ホールドアンドウェイト-例

ホールドアンドウェイトの例

循環待機

あるプロセスが別のプロセスに割り当てられたリソースを待機していて、そのプロセスがリソースを待機している場合、一連のプロセスはデッドロック状態にあると言われます。これは、ループ形式である上記の例と同様です。ここで、P1はR2を待機し、R2はP2に割り当てられ、P2はR1を待機し、R1はP1に割り当てられます。これは、この条件がデッドロックを満たした場合の循環待機形式です。

サーキュラー-待機-例

Circular-wait-example

デッドロック検出アルゴリズム

プロセスにリソースを割り当て、オペレーティングシステムが、システムでデッドロックが発生したかどうか、または2つの主要なデッドロック検出アルゴリズムを使用していないかどうかを再チェックする場合。

  • 単一インスタンス
  • リソースタイプの複数のインスタンス

シングルインスタンス

単一インスタンスは、システムがすべてのリソースの単一インスタンスを持っている状況です。待機グラフアルゴリズムまたはリソース割り当てグラフとも呼ばれます。リソース割り当てグラフは、2つの異なる頂点として表される一連のプロセスと一連のリソースで構成されます。リソース割り当てグラフのリソースは変更され、グラフ形式の待機として表されます。グラフ形式を待つ場合、以下に示すように頂点として表されるプロセスのみがあります。ここで、

  • リソース割り当てグラフ:プロセスP1、P2、P3およびリソースR1、R2、R3は、リソース割り当てグラフで表されます。
  • グラフの待機:グラフの待機には、プロセスP1、P2、P3のみが記載されています。
  • サイクル条件がある場合、一方向にプロセスの連続フローがある場合、それはサイクル条件が終了し、グラフがデッドロック状態になるのを待つことを意味します。

例1: 以下の例は、グラフの待機中に継続的なフローが観察されないため、デッドロック状態がないことを示しています。

単一インスタンス-例1

単一インスタンスの例1

例2: P1からP4へのサイクルの連続フローがあるため、デッドロック状態が発生しました。

シングルインスタンス-例2

単一インスタンス-example2

システムでデッドロックが非常に頻繁に発生する場合は、検出アルゴリズムが頻繁に使用されます。検出アルゴリズムの使用が増えると、オーバーヘッドと計算時間が長くなります。したがって、これを克服するために、同じ時間を与えた後にアルゴリズムを呼び出します。これは、グラフの重みを使用してデッドロックを検出する方法です。

リソースタイプの複数のインスタンス

リソースタイプの複数のインスタンスは、システムにすべてのリソースの複数のインスタンスがある状況であり、バンカーアルゴリズムとも呼ばれます。銀行家のアルゴリズムによると、プロセスは必要なすべてのリソースを取得するとすぐに、そのリソースを解放します。

次の例を考えてみましょう。3つのプロセスP0、P1、P2、およびリソースタイプA、B、Cがあり、Aは次のようになります。 CPU 、Bはプリンタ、Cはキーボードにすることができます。列の数字「0」は、リソースの可用性を表します。

ケース(i): 条件要求がP0とP2に存在する「000」条件であるとすると、どの要求が満たされているかを確認する必要があります。プロセスP0は割り当て後にプロセスを解放し、次のP2プロセスは割り当て後に解放します。このように、シーケンスでは、プロセスが1つずつP0、P2、P3、P1、P4をシーケンスで解放します。最後に、P7、P2、P6として利用可能なリソースを取得します。使用可能なシーケンスは、デッドロックがない状態です。

銀行家のアルゴリズム-例1

銀行家のアルゴリズム-example1

住宅(ii): P2が000ではなく001である場合、銀行家のアルゴリズムを適用して、5つのプロセスすべての中でP0のみが実行されるデッドロック状態をチェックするとします。したがって、P1、P2、P3、P4は、P0を除いてデッドロック状態になります。

銀行家-例2

銀行家-example2

デッドロックのアプリケーション

デッドロックの適用は、オンライン試験の結果のリアルタイムの例で説明できます。この例では、複数の学生がリリース時に大学のWebサイトにアクセスしようとします。 Webページが一度に複数のユーザーにロードされない場合があり、これはデッドロック状態であることがわかります。これは、いずれかのアルゴリズムを使用して克服できます。

利点

デッドロックの利点は次のとおりです。

  • デッドロック回避ではプリエンプションは観察されません
  • プロセスの遅延なし

短所

デッドロックの欠点は

  • 使用するリソースは事前に知っておく必要があります
  • 長期間のプロセスの妨害
  • プリエンプション損失は継承されます。

この記事では、2つ以上のプロセスが存在する場合にデッドロックが発生する方法と、デッドロックが発生する原因となる3つの条件、およびその存在を検出する2種類のアルゴリズム(リソース共有アルゴリズム)について概説します。 デッドロック状態 デッドロック回避アルゴリズムである銀行家のアルゴリズム。 「デッドロックを無視するとどうなりますか?」という質問があります。