応用情報技術者 2016年 秋期 午前2 問17

CPU遊休時間の比較【午前2解説】

正解の理由

解法ステップ

1. 各タスクのCPU/I/Oの区間を時刻ゼロから順に並べる（Gantt図を作る）。
2. ルール：高優先のCPU区間が準備できたら即座にCPUを得る（低優先はプリエンプトされる）。I/Oは競合しないので並行可能。
3. CPUが遊休になるのは「同時に両方がI/Oに入っている区間」のみ。したがって両者のI/O区間の重なりを時系列で合計する。
4. 各選択肢について上記を適用し、重なり時間（CPU遊休時間）を算出する。値が最小の選択肢を選ぶ。

選択肢別の誤答解説

• ア（低：C2→I5→C2→I2→C3）
  高（H）：
  • H:C 0–3, H:I 3–6, H:C 6–9, H:I 9–12, H:C 12–14
  低（L=ア）をスケジューリング：
  • H占有で低は0–3待ち
  • H:I 3–6 の間に低が CPU を使う → L:C 3–5，続いて L:I 5–10
  • 5–6 は低が I/O に入ったため CPU は遊休（5–6）
  • 6–9 は H:C（低はI/O）
  • 9–10 は H:I 9–12 と低の I/O 5–10 が重なり、CPU遊休（9–10）
  • 10–12 は低が CPU（L:C 10–12）
  • 12–14 H:C（低は I/O 12–14）
  • 14–17 低が残りの CPU を実行
  遊休時間の合計 = (5–6) 1ms + (9–10) 1ms = 2 ms
  誤りの要点：低の長い最初のI/O(5ms)が高のI/Oと部分的重複し、遊休が発生するためウより大きくなる。
• イ（低：C3→I2→C2→I3→C2）
  高（H）は同上。
  低（L=イ）：
  • 0–3 低待ち
  • 3–6 低:C 3–6 → 続けて低:I 6–8
  • 6–9 H:C（低はI/O）
  • 9–12 H:I の間に低が CPU を使える → 9–11 L:C
  • 11–14 低:I 11–14 と H:C 12–14 があるが、11–12 は H:I と低:I の重複 → CPU遊休（11–12）
  • 12–14 H:C（低はI/O）
  • 14–16 低:C 扱いで終了
  遊休時間の合計 = (11–12) 1 ms
  誤りの要点：低の中間のI/O(3ms)が高のI/Oと一部重複し1msの遊休が発生する。
• ウ（低：C3→I2→C3→I1→C4） ← 正解候補（ウ） 高（H）は同上。
  低（L=ウ）：
  • 0–3 低待ち
  • 3–6 低:C 3–6（ちょうど H:I と同期）
  • 6–8 低:I 6–8（H:C 6–9 の間に低はI/Oで不在）
  • 9–12 H:I の間に低:C 9–12（ちょうど並行）
  • 12–13 低:I 12–13（だが H:C 12–14 なのでCPUは占有されている）
  • 13–14 低は待ち（I/O終了→CPUはHが使用中）
  • 14–18 低:C 14–18（高の処理完了後に実行）
  両者のI/Oが同時に存在する区間をチェックすると、I/Oの重複は発生しない（高のI/O区間と低のI/O区間が常にCPU実行区間とずれている）。
  遊休時間の合計 = 0 ms
  正答理由の核：全ての高のI/O区間で低はCPUを使うか、低のI/Oは高がCPUを使用しているため同時I/Oが生じず、CPUは常にどちらかが使っている（＝遊休ゼロ）。
• エ（低：C3→I4→C2→I5→C2）
  高（H）は同上。
  低（L=エ）：
  • 0–3 低待ち
  • 3–6 低:C 3–6
  • 6–10 低:I 6–10（長め）
  • 6–9 H:C（低はI/O）
  • 9–12 H:I と 低:I 9–10 が重なり、CPU遊休（9–10）
  • 10–12 低:C 10–12（高I/O中にCPUを使う）
  • 12–14 H:C（低は I/O 12–17）
  • 14–17 低がまだI/Oなので CPU は遊休（14–17）
  • 17–19 低:C 17–19
  遊休時間の合計 = (9–10) 1ms + (14–17) 3ms = 4 ms
  誤りの要点：低の長い後半I/O(5ms)が高の終了後も続き、終了まで CPU は遊休になる区間が生じる。

よくある誤解

1. 「CPUは高がI/Oの間、必ず低がCPUを使う」と考えてしまう誤り。低がI/O中ならCPUは遊休になります。重要なのは「両方がI/Oの重なり」を見ることです。
2. プリエンプションの誤認：高のCPU区間が始まったら低の現在のCPU区間も続行されると誤想する受験者が多い。高優先は即時奪取（プリエンプト）される点を忘れないこと。
3. I/Oが「競合しない」ことを見落とす誤解。問題ではI/Oは同時実行可能なので、I/O競合で低が遅れるという考えは誤り。

補足コラム

• 速算のコツ：CPU遊休時間 = 両タスクのI/O区間同士の“実際の”重複時間の合計、ただし「実際の」開始時刻はプリエンプションでずれるので必ず時系列でイベント（CPU開始・I/O開始・終了）を追うこと。手早く済ませたいときはGantt図を紙に書くのが最も確実です。
• 別解として、各タスクのCPU総和と（試験終了時刻 − CPU総和）を使う方法もあります。両者が終了する時刻を求めて、総実行期間から合計CPU時間を引けば遊休時間が出ます（ただし期間の計算は時系列解析が必要）。

FAQ