応用情報技術者 2012年 春期 午前2 問20

優先度スケジューリング【午前2解説】

正解の理由

解法ステップ

1. 初期条件の確認
   • CPU: 1個（高優先があればCPUを取得）
   • I/O: 1台（同時動作不可）。I/O要求は空き次第開始、空いていなければ待ち行列に入り待機（待ち状態）。
   • 高優先を H、低優先を L と表記。
2. 時系列（各区間は開始時刻–終了時刻、単位は ms）
   • 0–2: CPU = H の CPU(2)。I/O = 空き。L は待機（準備状態）。
   • 2–4: CPU = L の CPU(2)（H はI/O要求のためブロック）。I/O = H の I/O(7) が 2–9 で占有開始。
     • 詳細: H が 2ms のCPUを終え、直ちに I/O(7) を要求して I/O を占有（2→9）。CPUは空くので L が 2–4 を使う。
   • 4–9: CPU = 空き（実行可能なタスクなし）。I/O = H(2–9)。L は 4ms に I/O要求（I/Oが使用中のため待ち行列に入る）。
     • 注意: L は I/O開始を待っている間ブロックしているため CPU を消費しない。
   • 9–12: CPU = H の CPU(3)（9–12）。I/O = L の I/O(3)（9–12）。
     • 理由: H の最初の I/O が 9ms に終了し、同時に待ち行列先頭の L の I/O が開始（9–12）。H は CPU に戻り CPU3 を実行。
   • 12–14: CPU = L の CPU(2)（12–14）。I/O = H の I/O(4)（12–16）。
     • 理由: 12ms に H の CPU3 が終了して I/O4 を要求し、I/O は空きなので直ちに H の I/O(12–16) が始まる。一方 L は 12ms に I/O3 が終わり CPU2 を実行。
   • 14–16: CPU = 空き。I/O = H の I/O(12–16)。L は 14ms に I/O(2) を要求して待ち行列に入る（I/Oが占有中のため）。
   • 16–19: CPU = H の CPU(3)（16–19）。I/O = L の I/O(2)（16–18）。
     • 理由: 16ms に H の I/O4 が終わり H は再び CPU を実行（CPUが空いているため開始）。同時に L の待ちだった I/O2 が 16–18 で実行される。
   • 18–19: CPU = H の CPU(残り)。I/O = 空き。L は 18ms に I/O2 完了して CPU 最終バースト待ち（準備状態）。
   • 19–22: CPU = L の CPU(3)（19–22）。I/O = 空き。全ての処理が 22ms に終了。
3. 合計
   • 最終完了時刻 = 22ms（したがって選択肢エ）。

• 0–2: CPU=H(C2) ／ I/O=idle
• 2–9: CPU=2–4:L(C2)、4–9:idle ／ I/O=H(I7)
• 9–12: CPU=H(C3) ／ I/O=L(I3)
• 12–16: CPU=12–14:L(C2)、14–16:idle ／ I/O=H(I4)
• 16–19: CPU=H(C3) ／ I/O=16–18:L(I2), 18–19:idle
• 19–22: CPU=L(C3) ／ I/O=idle

選択肢別の誤答解説

• ア: 19
  • 19ms にしてしまう誤りは、L の最後の CPU(3) を H の CPU3 の直後（16–19）に重ねて実行可能と考える誤解に由来します。だがその時点で L はまだ I/O2 実行（16–18）中で、さらに 18–19 で L は CPU を取れない（H が優先で 16–19 を占有）。よって 19ms は不足。
• イ: 20
  • 20ms とするのは、CPU のアイドル時間（例: 4–9 や 14–16）を過小評価している場合に出ます。特に 4–9 のCPUアイドルを見落とし、L の I/O を同時に走らせられると誤認すると発生します。
• ウ: 21
  • 21ms は I/O の待ちと優先度によるプリエンプトを一部考慮しているものの、L の最終 CPU(3) の開始が 19ms で終わると誤って計算した場合に出ます。実際は L は 19–22 の CPU3 を得るので完了は 22ms。
• エ: 22
  • 正しい。上記の時系列で両リソース（CPUと単一I/O）と待ち行列の振る舞いを正しく追えば導出できる。

よくある誤解

• I/O要求は「要求時に即座に始まらないとCPUを使い続ける」と思う誤解：
  • 実際は I/O が空いていなければ要求したタスクはブロック（CPU を放す）。ブロック中のタスクは CPU を消費しません。
• I/Oは複数同時に動作すると誤想する：
  • 本問では I/O は1台で排他。複数同時実行を許すとタイミングが大きく変わり、解答が変わる。
• 高優先度がI/O待ちでも低優先を強引に追い越せると考える：
  • 高優先度がI/Oから復帰した瞬間に低優先をプリエンプトしてCPUを奪います（プリエンプティブ優先度スケジューリングの原則）。

補足コラム

• タスクが I/O を要求したらすぐに CPU を解放する（I/Oが空いていなくても待ち状態）。
• I/Oは単一のサーバーとしてキューイングされる（先着順でよい）。
• 高優先度タスクが実行可能になったら低優先度タスクは即座にプリエンプトされる（問題文の前提に準拠）。

FAQ