リソース割り当てグラフ
• プロセス
• 4 つのインスタンスをもつリソース
• P i が R j を要求
• P i は R j を保持している
P
iRj
P
iリソース割り当てグラフの例
デッドロック状態
循環グラフになっているが
デッドロック状態ではない場合
基本性質
• グラフに閉路あり
– デッドロックなし
• グラフに閉路あり
– リソースの種類一つにつき、それらのインスタンスはただ一 つの場合、デッドロック
– リソースの種類一つにつき、それらのインスタンスは複数あ る場合、デッドロックの可能性あり
.
デッドロック問題に対する手法
• デッドロック予防 (Deadlock Prevention)
– デッドロック状態にならないように共有資源の使い方を決定
• デッドロック回避 (Deadlock Avoidance)
– デッドロック状態になると検知したらそれを回避
• 多くのシステムではデッドロック回避手法は実装されていない
• OS 自身はデッドロックが生じないように注意深く設計
• プログラムがデッドロックするかどうかをソースプログラム
（あるいは仕様）からあらかじめ検査する研究
– モデル検査
Deadlock Prevention
• Mutual Exclusion
–
資源によっては、Mutual Exclusion
を回避することは不可能• Hold and Wait
–
この状態を作らないようにするには、プロセスが資源を要求する時は、そのプロセスは他の資源を占有しない
–
方法１•
実行前に使用する資源全てを占有–
方法２•
プロセスが資源を要求する時は、そのプロセスは何も資源を占有していな いときに限定– 問題点
•
リソースが利用性が低下•
飢餓状態になる可能性４つの状態が同時に生じないようにプログラミング
Deadlock Prevention (Cont.)
• No Preemption
– いくつかの資源を占有しているプロセスが、ある資源を占有 しようとして失敗したら、占有していた資源を解放
– 開放された資源は、このプロセスの資源リストに追加
– このプロセスは必要とする資源が開放されたら、再度資源の 占有を実行
• Circular Wait
– 全ての資源の total ordering を決め、その順番に資源を占有
Circular Wait != 十分条件
• 循環待ち → デッドロック発生
R1 が２個の資源を持つ場合
P3
が終わればP1
が動作...
プロセスP2 プロセスP1 プロセスP3 資源R1 資源R2
デッドロックの回避
• それぞれのプロセスが必要なリソースの最大値をあらかじ め宣言（単純かつ最も有用）
• Circular-wait 状態をさけるため、リソースの確保状況を動的
に検査
–
リソースの確保状況とは、利用可能な数とすでに確保されている数、プロセスからの要求の最大値によって定義
システムは、いくつかのアプリオリな情報を利用可能であるこ とが必要
ここでは、詳細な話はしない
デッドロックの回避
• スケジューリングによってデッドロックを回避
• 銀行家のアルゴリズム
–
デッドロックを起こさない資源のプロセスへの割付け順を決定（銀行家が資源の貸し出しを制御）
プロ セス
保持している 資源数 U
必要な資源 の最大数 N
A B A B
P1 2 0 3 2
P2 0 1 2 1
ある時点の実行状態
必要な資源の最大数－保持している資源数
＝残りの必要な資源数
R
例：資源
A
は５個，資源Ｂは２個存在 現在の空き資源数F=(2 0)
残りの必要な資源数
R=((1 2) (2 0) (1 1))
デッドロックの回避
• 例：資源 A は５個，資源Ｂは２個存在
–
現在の空き資源数F=(2 0)
–
残りの必要な資源数R=((1 2) (2 0) (1 1))
★ 初期値：W=(2 0), S=(偽 偽 偽）
1. WとRから要求を満足できるプロセスを探索
•
P2のみ
2. WとSを更新しP2実行後の状態を計算
•
W=W+(0 1)=(2 0)+(0 1)=(2 1)
•
S=(偽 真 偽)
3.
１へ．ただし，P2を除くプロ セス
保持している 資源数 U
必要な資源 の最大数 N
A B A B
P1 2 0 3 2
P2 0 1 2 1
F ＝
デッドロックの回避
• 例：資源 A は５個，資源Ｂは２個存在
–
現在の空き資源数F=(2 0)
–
残りの必要な資源数R=((1 2) (2 0) (1 1))
★ W=(2 1), S=(偽 真 偽）
1. WとRから要求を満足できるプロセスを探索
• P3のみ
2. WとSを更新
• W=W+(1 1)=(2 1)+(1 1)=(3 2)
• S=(偽 真 真)
3. １へ．ただし，P2，P3を除く
➡ P1にも割付可能
プロ セス
保持している 資源数 U
必要な資源 の最大数 N
A B A B
P1 2 0 3 2
P2 0 1 2 1
P3 1 1 2 2
デッドロックを回避する割り当て
• 通常はプロセスが実行に合わせて資源要求を出してくる
–
それを受け入れて良いかどうかの判断が必要–
資源を与えてなお、デッドロック回避が可能（＝安全）な実行順があるか？• 手順
–
要求が残り必要な資源数R
を超えていないことを確認–
要求が利用可能な資源数F
を超えていたら、そのプロセスは待ち•
そうでなければ次ステップの確認–
要求を割り当てた後の残り必要資源R
を計算•
利用可能資源F
から、要求の分を引いてW
を初期化•
デッドロック回避が可能な実行順があるか調査•
なければ、そのプロセスは待ちにして残り必要資源R
の状態を元に戻すデッドロックを回避する割り当て
プロ セス
保持している 資源数 U
必要な最大 資源数 N
残り必要 資源数 R
A B A B A B
P1 2 0 3 2 1 2
P2 0 1 2 1 2 0
P3 1 1 2 2 1 1
総資源数：
A 5
個、B 2
個資源要求列
P3: A 1
個P2: A 1
個P1: A 1
個P1: B 1
個P3: B 1
個P2: A 1
個P1: B 1
個 残り資源：A
個、B
個
2 0
ここでは、必要最大資源数が割 り当てられたらすぐにプロセス
待
○ 1 待 待 待
○ 2
1 0
2 1
1 0
P2 終了
○ 3
○ 5
P3 終了
○ 6
○ 7
2 1 0
○ 4 待
0
2
デッドロック検出と回復
• 検出
–
システムがデッドロ ック状態か？• 資源割付グラフ
–
要求(P → R) –
割付(R → P)
• 左図の一番下は デッドロック
P1 R1 R2 P2
P3 R3 P4
P5
R4
P6
R5
P1 R1 P2
P4 R2 P3
デッドロックの検出
• グラフの簡約
–
あるプロセスの資源要求が 満足されるとき，グラフは 当該プロセスにより簡約可 能という–
矢印を削除可能• それでも循環待ちが残れば
デッドロック状態
デッドロックからの回復
• デッドロックを検出
– 循環待ちを解除しデッドロックから回復 – 具体的手法は以下のどちらか
1. デッドロック状態のプロセスを１つ異常終了
➡リスクはあるが最悪の事態は回避
2. デッドロック状態のプロセスを１つ前の状態に戻し (rollback), やり直し
➡プログラムの実行状態を時々保存
（チェックポインティング）
演習問題 3.10 銀行家のアルゴリズム
• 資源Ａ： 10 個， B ： 5 個， C ： 7 個
プロセス 保持している資源数 必要な資源の最大数