応用情報技術者 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