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