応用情報技術者 2011年 秋期 午前2 問20
問題文
三つの資源X〜Zを占有して処理を行う四つのプロセスA〜Dがある。各プロセスは処理の進行に伴い、表中の数値の順に資源を占有し、実行終了時に三つの資源を一括して解放する。プロセスAとデッドロックを起こす可能性のあるプロセスはどれか。
選択肢
ア：B, C, D
イ：C, Dだけ（正解）
ウ：Bだけ
エ：Dだけ
🔒 解説は解答すると表示されます
資源取得順序とデッドロック【午前2解説】
正解の理由
正しい選択肢は イ（CとD）です。
ポイントは「少なくとも1つの資源ペアで、プロセス間で取得順序が逆転しているかどうか」です。Aの取得順序は X→Y→Z（Xが1、Yが2、Zが3）です。Cは Z→X→Y、Dは Z→Y→X の順になるため、A と C の間、A と D の間で少なくとも1つ（具体的には X と Z）の資源ペアで取得順が逆転しています。取得順の逆転があると、ある時点で互いに相手が保持する資源を待ち続ける「循環待ち」が発生し得るため、デッドロックの可能性があります。一方、B は A と全く同じ順序（X→Y→Z）なので順序の逆転がなく、A と B の間ではデッドロックは発生しません。
ポイントは「少なくとも1つの資源ペアで、プロセス間で取得順序が逆転しているかどうか」です。Aの取得順序は X→Y→Z（Xが1、Yが2、Zが3）です。Cは Z→X→Y、Dは Z→Y→X の順になるため、A と C の間、A と D の間で少なくとも1つ（具体的には X と Z）の資源ペアで取得順が逆転しています。取得順の逆転があると、ある時点で互いに相手が保持する資源を待ち続ける「循環待ち」が発生し得るため、デッドロックの可能性があります。一方、B は A と全く同じ順序（X→Y→Z）なので順序の逆転がなく、A と B の間ではデッドロックは発生しません。
解法ステップ
- 各プロセスの資源取得順序を読み替える（数値が小さいほど先に取得）。
- A: X(1) → Y(2) → Z(3)
- B: X(1) → Y(2) → Z(3)
- C: Z(1) → X(2) → Y(3)
- D: Z(1) → Y(2) → X(3)
- A と比較して、資源ペア（X,Y）、（Y,Z）、（X,Z）の各ペアで取得順が逆になっているかを確認する。
- A vs B: どのペアも順序は一致 → 逆転なし
- A vs C: X と Z の順が逆（A: X→Z、C: Z→X）→ 逆転あり
- A vs D: X と Z の順が逆（A: X→Z、D: Z→X）→ 逆転あり
- 逆転が1ペアでもあれば、デッドロックの発生可能性ありと判断する。
- よって A とデッドロックを起こす可能性があるのは C と D → イ
（参考：逆転があると想定しうるタイムラインの例）
- A がまず X を獲得する。
- 同時に C（または D）がまず Z を獲得する。
- C は次に X を要求するが、X は A が保持中のため待ちになる。
- A はその後 Y を獲得してから Z を要求するが、Z は C が保持中のため A も待ちになる。
- 結果、A は Z を、C は X をそれぞれ相手が持っているため循環待ち（デッドロック）が成立する。
選択肢別の誤答解説
- ア: B, C, D
誤り。B を含めるのが間違い。B は A と同一順序（X→Y→Z）であり、資源ペアの逆転がないため A とデッドロックは発生しない。 - イ: C, Dだけ
正しい。上で示した通り、A と C、A と D の間で X と Z の取得順が逆になっており、デッドロックが起こり得る。 - ウ: Bだけ
誤り。B はデッドロックを起こさないため「Bだけ」という選択は誤り。C と D も可能性がある。 - エ: Dだけ
誤り。D は確かに可能性があるが、C も同様に X と Z の取得順が逆転しているため除外できない。
よくある誤解
- 「逆転が2ペア以上でないとデッドロックは起きない」
誤りです。少なくとも1つの資源ペアで取得順が逆転していれば、他の条件（排他保持・保持中は解放しない等）が満たされる限りデッドロックは発生し得ます。 - 「プロセスがすぐに待ち状態にならないとデッドロックは起きない」
誤解です。あるプロセスが後である資源を要求して待ち状態になる間に、他のプロセスが先に別の資源を要求して待機することで循環待ちは成立します。時点がずれていても構いません。
補足コラム
この問題はデッドロックの必要十分条件の一部（特に「循環待ち（circular wait）」）に関する理解を問うものです。古典的なデッドロック回避／予防策としては、すべての資源にグローバルな順序を定め、すべてのプロセスがその順序に従って取得するようにする方法があります。これにより資源ペアの順序逆転を根本的に防ぎ、循環待ちを排除できます（実務上よく使われる単純で有効な手法）。
FAQ
Q1: 「どの程度の逆転でデッドロックが確実に起きるのか？」
A1: 逆転が1つあればデッドロックの可能性は十分にあります。発生の確率や実際の発生は実行タイミングに依存しますが、可能性があると判断されます。
A1: 逆転が1つあればデッドロックの可能性は十分にあります。発生の確率や実際の発生は実行タイミングに依存しますが、可能性があると判断されます。
Q2: 「資源を途中で解放する設計ならどうなるか？」
A2: 問題文では「実行終了時に三つの資源を一括して解放する」とあるため解放は最後です。途中で解放するなら循環待ちの成立条件が変わり、逆転していてもデッドロックを回避できる場合があります。
A2: 問題文では「実行終了時に三つの資源を一括して解放する」とあるため解放は最後です。途中で解放するなら循環待ちの成立条件が変わり、逆転していてもデッドロックを回避できる場合があります。
Q3: 「3プロセス以上の場合はどう判定するか？」
A3: ペアごとの順序逆転の有無を調べ、循環（AがRを持ちBを待ち、BがSを持ちCを待ち、…と戻ってくる）を起こし得るかを検討します。グローバル順序を強制する方法が有効です。
A3: ペアごとの順序逆転の有無を調べ、循環（AがRを持ちBを待ち、BがSを持ちCを待ち、…と戻ってくる）を起こし得るかを検討します。グローバル順序を強制する方法が有効です。
関連キーワード: デッドロック、循環待ち、資源順序、排他制御、資源割当
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！