応用情報技術者 2020年 秋期 午前2 問17

資源占有順序のデッドロック【午前2解説】

正解の理由

解法ステップ

1. 数値を「1→2→3 の順に資源を取得する」と読み替える（小さい数が先に取得）。
2. 対象を A と他プロセスの組み合わせにして、初期に取る資源（1番目）を確認する。
3. 各プロセスが1番目を取得した後の次の要求（2番目）を追い、相手が持っている資源を要求しているかを確認する。
4. 互いに「自分が持っている資源を相手が要求し、相手が持っている資源を自分が要求する」循環があればデッドロック成立。

• AとB:
  • 両者とも最初にX(1)を要求するため、どちらか一方がXを取得し、もう一方はXを待つだけ。循環待ちにならない。
• AとC:
  • A: 1:X を取得 → 次に Y を要求
  • C: 1:Z を取得 → 次に X を要求（XはAが保持）
  • その後 A が Y を取得できると、さらに A は Z を要求（ZはCが保持）
  • 結果、AはZを待ち、CはXを待つ循環待ちが成立する → デッドロック
• AとD:
  • A: 1:X を取得 → 次に Y を要求（仮に A が Y を得られない場合を考慮）
  • D: 1:Z を取得 → 次に Y を要求
  • もし D が先に Y を取得すると、Dは次に X を要求するが X はAが保持している
  • 結果、AはYを待ち（Dが保持）、DはXを待ち（Aが保持）で循環待ちが成立する → デッドロック

選択肢別の誤答解説

• ア: B, C, D
  • 誤り。BはAと全く同じ順序（X→Y→Z）なので、同時に開始しても両者が互いに別々の資源を取り合って循環する状況にはならない。片方がXを取って先に進み、もう片方はXを待つのみになる。
• イ: C, D
  • 正しい（上記参照）。AとC、AとDそれぞれで循環待ちが成立し得る。
• ウ: Cだけ
  • 誤り。Cは確かにデッドロックを起こす可能性があるが、Dとも同様に循環待ちが成立するためDも含める必要がある。
• エ: Dだけ
  • 誤り。Dはデッドロックを起こす可能性があるが、CもAと組むと循環待ちが成立するためCも含める必要がある。

よくある誤解

• 数字を優先度や重みと読み違える：この問題では「1,2,3 は取得の順序」を表す。順序と解放タイミングを正確に把握すること。
• 同じ最初資源を要求する＝デッドロックと考える：同じ資源を先に要求するだけでは単純競合（待ち）であって、循環待ちが発生しなければデッドロックにはならない。
• 全ての組み合わせで資源数が等しければ必ずデッドロックと誤認：実際には「相互排他、保持と待ち、非事前取得、循環待ち」の全てが満たされたときにデッドロックとなる（循環待ちの有無が鍵）。

補足コラム

• モデル化すると分かりやすいです。各プロセスをノード、資源をノードとする資源割当グラフ（プロセス→要求辺、資源→割当辺）で見ると、サイクルが存在すればデッドロックの可能性があります。
• 予防策の一つに「資源のグローバルな順序付け」を導入し、すべてのプロセスがその順序に従って資源を取得する方法があります（今回の問題では A/B は X→Y→Z の順序に従っており、C/D はこれと異なるため問題が発生します）。
• 検出と回復の戦略もあり、実際のOSではタイムアウトや検出アルゴリズムでサイクルを見つけ、プロセスの中断や資源の剥奪で回復することがあります。

FAQ