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