レッスン11

Deadlock

プロセスはブロックされ、互いに所有するリソースを待つ
しげん

ハードウェア、ソフトウェアなどの概念

I/O機器、CPUサイクル、メモリスペースSamephore等

プロセスリソースを使用するプロセス

Request -> Allocate -> Use -> Release

Deadlock発生条件

反発反発(Mutual Exclusion):所有時間内に独占的に使用

Noプリエンプト(非線形)

Hold and Wait
:リソースを所有するプロセスが他のリソースを待機している間も、リソースを解放せずにリソースを保持します.

Circular wait
:リソースを待機するプロセス間でループを形成します.
p 0はp 1が所有するリソースを待つ
p 1 p 2が所有するリソースを待つ
pn-1 pnが所有するリソースを待つ
PnはP 0が所有するリソースを待つ

Deadlock処理方法

deadlock prevention
リソースの割り当て時に、デッドロックの4つの必要条件の1つが満たされていないことを確認します.

deadlock avoidance
:リソース要求の追加情報にデッドロックの可能性がない場合のみ、リソースを割り当てます.
リソースは、システムステータスが元のステータスに復元できる場合にのみ割り当てられます.

deadlock detection and recovery
:デッドロックの発生は許可されていますが、デッドロックが検出されたときにリカバリされる検出ルーチンがあります.

deadlock ignorance
:デッドロックはシステムの責任ではありません.ほとんどのオペレーティングシステム(UNIXを含む)は採用されています(ユーザーがプロセスを自動的に終了するためです).

1. Deadlock Prevention

hold & wait
リソースを待っている場合は、リソースがなければ大丈夫です.
方法プロセスの開始時に必要なすべてのリソースを割り当てる方法(リソースの効率が低下...救済方法2)
方法リソースが必要な場合は、すべてのリソースを解放し、再要求します.

no preemption
資源を奪い取ればいい.
主にCPUとメモリに使用され、リソースの現在の状態を簡単に保存および復元できます.

circular wait
リソースの割当て順序を指定し、リソースのみを順番に割り当てます.

-->ソースのデッドロックは防止できますが、リソース使用率の低下、スループットの低下、飢餓の問題があります.

グラフにループがなければデッドロックではありません.

ループが存在する場合、

インスタンスがデッドロックである場合、

複数であれば、行き詰まりではない可能性もあります.

- **Banker's Algorithm사용**

2. Deadlock avoidance

プロセスが起動時に書き込む最大リソース量を知っていると仮定し、デッドロックが発生する可能性がある場合、リソースは割り当てられません.

Banker's Algorithm

では、P 0のすべての人がユーザーリソースを使用している場合、それはデッドロックですか?
珍しくない.これは、他のプロセスのリソースが埋められるからです.
しかしBanker'sアルゴリズムは非常に保守的なので、割り当てないだけです.

3. Deadlock detect & recovery

デッドロックは頻繁に発生するイベントではないので、デッドロックが発生すると検出され、復元されます.
リソースが1つしかない場合は、リソース割り当てグラフィックを使用します.
複数のファセットテーブルが検出されました(1つはテーブルとしても、グラフィックは追加の方法です).

cycleを探す費用は?O(n^2)cycleがあるかどうか知りたいなら、ついて行ってみてください.
n個の点がある場合、最大n-1個の矢印を持つことができます.( n * (n -1) )

もしそうなら?

デッドロックが検出された場合は、リカバリが必要です.

デッドロックに関連するすべてのプロセスを殺します.(プロセス終了)

を殺すたびに、どのプロセスがデッドロック(リソース競合)

を引き起こすかをチェックし続けます.
同じパターンが再発したら?(同じプロセスが犠牲者として選択され続ける場合)
リソースのプリエンプト・モードを変更します.
これにより、起動の問題が発生する可能性があります.
このため、ロールバック回数も考慮する必要があります.

4. Deadlock Ignorance

:デッドロックは発生しないと判断し、いかなる措置も取らない
デッドロックはめったに発生しないため、デッドロックを処理すること自体がより大きなオーバーヘッドになる可能性があります.
オーバーヘッドが発生した場合は、手動でプロセスを殺す方法で処理できます.