デッドロック、ライブロック、飢餓
1. 序章
マルチプログラミング環境では、複数のプロセスが有限のリソースセットをめぐって競合する可能性があります。 プロセスがリソースを要求し、そのリソースが現在利用できない場合、プロセスはそれを待ちます。 この待機プロセスがリソースへのアクセスに成功しない場合があります。 このリソースの待機は、デッドロック、ライブロック、および飢餓の3つのシナリオにつながります。
このチュートリアルでは、これら3つの条件について説明します。
2. デッドロック
このセクションでは、最初にデッドロック、その必要な条件、およびそれを防ぐ方法について説明します。
2.1. デッドロックとは何ですか？
デッドロックとは、リソースの取得のためにプロセスが相互にブロックし、他のプロセスが保持しているリソースを待機している間、どのプロセスも進行しない状況です。
上の図は、プロセス1とプロセス2の間のデッドロックシナリオを示しています。 両方のプロセスが一方のリソースを保持しており、もう一方のプロセスが保持しているもう一方のリソースを待機しています。 プロセス1もプロセス2も、いずれかのプロセスがリソースを放棄するまで進行できないため、これはデッドロック状態です。
2.2. デッドロックに必要な条件
シナリオをデッドロックとして正常に特徴付けるためには、次の4つの条件が同時に成立する必要があります。
相互排除：少なくとも1つのリソースが非共有モードのプロセスによって保持されている必要があります。 そのリソースを要求する他のプロセスは待機する必要があります。 保留して待機：プロセスは1つのリソースを保持する必要があり、他のプロセスによって現在保持されている追加のリソースを要求します。 プリエンプションなし：リソースをプロセスから強制的に解放することはできません。 プロセスは、リソースを解放すると見なした場合にのみ、リソースを自発的に解放できます。 Circular Wait：プロセスのセットは、によって保持されているリソースを待機し、によって保持されているリソースを待機する方法で存在します。
2.3. デッドロックを防ぐ方法
デッドロックの発生を防ぐために、前のセクションで説明した必要な条件の少なくとも1つが当てはまらないようにする必要があります。 これらの条件のいずれかが誤っている可能性を調べてみましょう。
相互排除：場合によっては、この条件が偽になることがあります。 たとえば、読み取り専用ファイルシステムでは、1つ以上のプロセスに共有可能なアクセスを許可できます。 ただし、この条件が常にfalseであるとは限りません。 一部のリソースである理由は、本質的に共有できません。 たとえば、mutexロックは共有できないリソースです。
保留と待機：保留と待機の状態が発生しないようにするには、
プリエンプションなし：この条件をfalseにするには、プロセスは、新しく要求されたリソースが利用できない場合に、現在保持されているすべてのリソースを自動的に解放することを確認する必要があります。
Circular Wait：この条件は、すべてのリソースタイプの全順序を課し、各プロセスが列挙の昇順でリソースを要求するようにすることで、falseにすることができます。 したがって、リソースのセットがある場合、プロセスにはリソースが必要であり、タスクを完了するには、最初に要求してから、を要求する必要があります。
3. Livelock
このセクションでは、デッドロックに似ていますが、微妙な違いがあるライブロックについて説明します。
3.1. Livelockとは何ですか？
ライブロックの場合、ライブロックシナリオに関連するプロセスの状態は常に変化します。 一方、プロセスは依然として相互に依存しており、タスクを完了することはできません。
上の図は、ライブロックの例を示しています。 「プロセス1」と「プロセス2」の両方に共通のリソースが必要です。 各プロセスは、他のプロセスがアクティブ状態にあるかどうかをチェックします。 その場合、リソースを他のプロセスに渡します。 ただし、両方とも、プロセスは非アクティブステータスであり、どちらもリソースを相互に無期限に引き渡し続けます。
ライブロックの実際の例は、2人がお互いに電話をかけ、両方が回線が混雑していることに気付いた場合に発生します。 両方の紳士は、同じ時間間隔の後に電話を切り、電話をかけることを試みることにしました。 したがって、次の再試行でも、同じ状況になりました。 これは、永久に続く可能性があるため、ライブロックの例です。
3.2. デッドロックとリブロックの違いは？
性質は似ていますが、デッドロックとライブロックは同じではありません。 デッドロックでは、デッドロックに関係するプロセスは無期限にスタックし、状態を変更しません。 ただし、ライブロックのシナリオでは、プロセスは相互にブロックし、無期限に待機しますが、リソースの状態は継続的に変更されます。 注目すべき点は、リソースの状態の変更は効果がなく、プロセスがタスクを進めるのに役立たないことです。
4. 飢餓
このセクションでは、デッドロック、ライブロックの結果として、または貪欲なプロセスによって引き起こされる一般的な飢餓について説明します。
4.1. 飢餓とは何ですか？
飢餓は、タスクを完了するために必要な共有リソースに定期的にアクセスできないため、進行できないプロセスの結果です。
上の図は、「プロセス1」がCPUを長期間占有しているため、CPUの「プロセス2」と「プロセス3」が不足している例を示しています。
4.2. 飢餓の原因は何ですか？
スターベーションは、デッドロック、ライブロック、または別のプロセスが原因で発生する可能性があります。
デッドロックまたはライブロックが発生した場合に見たように、プロセスは別のプロセスと競合して、タスクを完了するために必要なリソースを取得します。 ただし、デッドロックまたはライブロックのシナリオが原因で、リソースの取得に失敗し、通常はリソースが不足していました。
さらに、他のプロセスが同じリソースを待機している間に、プロセスが共有リソースに繰り返しアクセスしたり、共有リソースを長期間使用したりする場合があります。 したがって、待機中のプロセスは、貪欲なプロセスによってリソースが不足しています。
4.3. 飢餓の回避
枯渇を防ぐための可能な解決策の1つは、エージング技術も使用する優先キューでリソーススケジューリングアルゴリズムを使用することです。 エージングは、待機中のプロセスの優先度を定期的に上げる手法です。 このアプローチでは、リソースを長時間待機するプロセスは、最終的に優先度が高くなります。 また、リソースの共有はプロセスの優先順位によって推進されるため、リソースを無期限に枯渇させるプロセスはありません。
飢餓を防ぐ別の解決策は、リソースをプロセスに割り当てながらラウンドロビンパターンに従うことです。 このパターンでは、リソースは各プロセスに公平に割り当てられ、別のプロセスに再度割り当てられる前にリソースを使用する機会を提供します。
5. 結論
この記事では、マルチプロセッシングオペレーティングシステムで発生するデッドロック、ライブロック、および枯渇の概念について説明しました。
デッドロックは、プロセスがリソースの取得で相互にブロックし、それ以上進行しない場合に発生する状況です。 Livelockはデッドロックのような状況であり、プロセスは状態の変化を繰り返して互いにブロックしますが、進行はありません。 枯渇は、デッドロック、ライブロックの結果、またはプロセスに対する継続的なリソース拒否の結果です。
