pptファイル

デッドロック問題
タスク1
タスク2
…
…
②横取り
lock r1; ①
lock r2; ③
…
…
lock r2; ⑤blocked
lock r1; ④blocked
…
…
unlock r2;
unlock r1;
…
…
unlock r1;
unlock r2;
…
…
デッドロック問題
lock-r2
lock-r1
lock-r1
(blocked)
lock-r2
(blocked)
資源割り付けグラフ
lock(block)
保持
タスク1
r2
保持
r1
タスク2
lock(block)
デッドロック発生の4条件
③ホールド＆ウェイト
要求
保持
タスク1
r2
保持
④循環待ち
r1
タスク2
①相互排除
②横取り不可
要求
ダチョウのアルゴリズム（Wikipediaより）
ダチョウ・アルゴリズム（英: Ostrich algorithm）とは、計算機科学に
おいて、発生頻度が極めて稀であるとの考えに基き、「頭を砂の中
に突っ込み、問題がないようなふりをする」ダチョウのように潜在的
な問題を無視するという戦略である。問題の発生を防止するよりも、
問題が起きたほうがコストが低いということを仮定している。
この方法は、並列プログラミングでのデッドロックに問題に対して、
デッドロックが発生する可能性が極めて低く、解決や防止のコスト
が極めて高いとみなされれば、対策として用いることができる。
代償として利便性や正確性が失われる。
ダチョウ・アルゴリズムは回避(銀行家のアルゴリズム)、防止、検知
と復活といったデッドロックの対処方法の一つである。
タイムアウト付きlock
タスク
…
if (lock-wto(r1)) {
クリティカルセクション
unlock r1;
} else {
アプリケーション定義の例外処理
}
mutexの一括取得のための疑似コード
タスク
holdAll = false;
while (!holdAll) {
if (!(lock-nb(r1)) {
lock(r1);
} else if (!lock-nb(r2)) {
unlock(r1); lock(r2);
} else {
holdAll = true;
}
}
クリティカルセクション
unlock r2;
unlock r1;
…
循環待ちの解消
タスク1
…
lock r1;
…
lock r2;
…
unlock r2;
…
unlock r1;
…
タスク2
…
lock r2;
…
lock r1;
…
unlock r1;
…
unlock r2;
…
デッドロック検出と復旧
タスク1
タスク2
…
…
②横取り
lock r1; ①
lock r2; ③
ロールバック
…
…
lock r2; ⑤blocked
lock r1; ④blocked
…（デッドロック検出）
…
unlock r2;
unlock r1;
…
…
unlock r1;
unlock r2;
…
…
デッドロックの検出と復旧
要求
保持
タスク1
r2
保持
r1
タスク2
要求
デッドロック検出と復旧
タスク1
タスク2
チェックポイント（状態保存）
…
…
lock r1;
lock r2;
ロールバック
…
…
lock r2;
lock r1;
…
…
unlock r2;
unlock r1;
…
…
unlock r1;
unlock r2;
…
…
デッドロックの回避
タスク1
タスク2
…
…
②横取り
lock r1; ①
lock r2; ③blockしたい
…
…
lock r2;
lock r1;
…
…
unlock r2;
unlock r1;
…
…
unlock r1;
unlock r2;
…
…
デッドロック回避のための資源割り付けグラフ
取得予定
取得予定
保持
タスク1
r2
r1
×
要求
取得予定
（blocked）
タスク2
取得予定

Download Report