応用情報技術者 2014年 秋期 午前2 問16

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

正解の理由

• A: X → Y → Z
• B: X → Y → Z
• C: Z → X → Y （表の数値は X:2, Y:3, Z:1 なので Zが1番目）
• D: Z → Y → X

1. A がまず X を占有（A はその後 Y, Z を順に要求する）。
2. C がまず Z を占有（C はその後 X を要求する）。
3. A が Y を占有し、次に Z を要求するが Z は C が保持しているので A は待ち状態。
4. C は Z を保持したまま次に X を要求するが X は A が保持しているので C も待ち状態。
   このとき A は Z を待ち、C は X を待つため A→Z→C→X→A の循環待ちが成立します。

1. A が X を占有。
2. D が Z を占有。
3. A が Y を占有し、次に Z を要求するが Z は D が保持しているので A は待ち。
4. D は Z を保持したまま次に Y を要求するが Y は A が保持しているので D も待ち。
   このとき A は Z を待ち、D は Y を待つため A→Z→D→Y→A の循環が成立します。

解法ステップ

1. 表の数値を「占有順」に読み替える（数値1が最初に占有する資源）。
2. 対象プロセス（ここでは A）と他の各プロセスについて、それぞれの「先に占有する資源」と「後で要求する資源」を整理する。
3. 循環待ちとなる典型パターンを探す：
   • A が先に占有している資源 R1 を、相手プロセスが後で要求する（相手が R1 を待つ）。
   • かつ相手プロセスが先に占有している資源 R2 を、A が後で要求する（A が R2 を待つ）。
   • このような（A が R2 を待ち、相手が R1 を待つ）互いの待ちが成立すれば循環待ち。
4. 上記を満たすプロセスをすべて選ぶ。

選択肢別の誤答解説

• ア: B, C, D
  • 誤り。C と D は正しく含まれますが、B は A と同一順序（X→Y→Z）なので A と B の間に循環待ちは発生しません。したがって B を含めるのは誤りです。
• イ: C, D
  • 正解。上で示したとおり、C（Z→X→Y）も D（Z→Y→X）も A（X→Y→Z）と互いに先に占有する資源と後で要求する資源が逆向きになり、循環待ちを作れます。
• ウ: Cだけ
  • 誤り。C は確かに A とデッドロックを起こし得ますが、D も同様に起こし得るため D を除外するのは不正確です。
• エ: Dだけ
  • 誤り。D は A とデッドロックを起こし得ますが、C も同様に起こし得るため C を除外するのは不正確です。

よくある誤解

• 「数値をそのまま資源名と混同する」
  • 表の数値は「占有順」を示します。例えば C の Z が 1 であれば「C はまず Z を占有する（Z→...）」です。順序の読み間違いで解釈が逆になることが多いので注意してください。
• 「同じ順序のプロセス同士でもデッドロックになる」
  • 同一の総順序（全プロセスが同じ順で資源を要求）では循環待ちは発生しません。順序が一致する場合、要求の方向が揃うため閉路が作られません。

補足コラム

1. 相互排他（資源は同時に1つのプロセスだけが使用）
2. 保持と待ち（資源を保持したまま他の資源を待つ）
3. 非奪取（他のプロセスの資源を強制的に奪えない）
4. 循環待ち（待ち関係が閉路を形成する）
   本問は特に「循環待ち」が成立するかを判定する練習に適しています。実運用では資源に全体順序を設けることでデッドロックを予防することがよく行われます。

FAQ