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