応用情報技術者 2019年 春期 午前2 問16

処理時間順スケジューリング【午前2解説】

正解の理由

• 0秒：Aが到着し最短なので A を 0–2秒で実行。
• 2秒：A 完了、到着済みは B(4秒), C(3秒) → C を 2–5秒で実行（非プリエンプティブなので途中到着の D は割り込めない）。
• 3秒にD到着、4秒にE到着（いずれも待ち）。
• 5秒：C 完了、待ちは B(4), D(2), E(1) → E を 5–6秒、次に D を 6–8秒、最後に B を 8–12秒で実行。
• B の完了は 12秒、到着 1秒 → ターンアラウンドタイム $=11$ 秒（エ）。

解法ステップ

1. 「到着時刻」を時刻軸に並べ、CPUが空いた瞬間ごとに到着済みのジョブ群を確認する。
2. CPUが空いた時点で、到着済みジョブのうち処理時間が最も短いものを選ぶ（非プリエンプティブ＝選んだら最後まで実行）。
3. 各ジョブの開始時刻・終了時刻を順に決め、対象ジョブ（B）の終了時刻から到着時刻を引いてターンアラウンドタイムを出す。
4. 本問では上の流れにより B の終了時刻が 12 秒で、$TAT=12-1=11$ 秒。

選択肢別の誤答解説

• ア: 8
  到着時刻や実行順序を誤って扱い、Bを早く開始した（あるいはAの実行を無視した）場合に出る誤答です。到着順やCPUが空く瞬間の選択ルールを守らないとこの値になります。
• イ: 9
  終了時刻の計算ミス（例えば完了時刻を 10 秒と誤認）や、途中の待ち時間を見落とした結果に起こりやすい誤りです。到着時刻差分の算出ミスに注意してください。
• ウ: 10
  D と E の実行順序や到着時刻の扱いを間違え、待ち行列の状態を誤認した場合に得られ得る値です。特に「到着時刻がいつか」を正しく反映していないと出ます。
• エ: 11（正解）
  上の手順どおりに時刻ごとに到着済みジョブから最短を選んでいけば得られる正しい値です。

よくある誤解

• 到着時刻の誤認：例えば D を 2 秒に到着と誤認すると実行順序が狂います。図にある到着時刻を正確に読み取ることが最重要です。
• 非プリエンプティブかプリエンプティブかの混同：処理時間順方式といっても「割り込み可（SRTF）」か「不可（SJF）」かで挙動が変わります。本問は非プリエンプティブとして処理するのが一般的です。
• ターンアラウンドタイムの計算誤り：完了時刻ではなく「完了時刻 − 到着時刻」が正しい定義です。開始時刻とは異なります。

補足コラム

• SJF（Shortest Job First）＝非プリエンプティブの処理時間順方式：CPUが空いた時点で待ちジョブの中から最短ジョブを選び、終わるまで実行する方式。平均待ち時間を最小化する性質がありますが、新しい短ジョブが次々到着する状況では長いジョブが飽和的に待たされる（スタベーション）の問題があります。
• プリエンプティブ版は SRTF（Shortest Remaining Time First）と呼ばれ、到着するたびに残り時間最小のジョブに切り替える可能性があります。本問の条件ではどちらを想定するかが結果に影響するため、問題文のニュアンスに注意してください。
• ターンアラウンドタイムの例示（本問の全ジョブで平均を求める場合）：
  • A: 完了 2, 到着 0 → TAT 2
  • B: 完了 12, 到着 1 → TAT 11
  • C: 完了 5, 到着 2 → TAT 3
  • D: 完了 8, 到着 3 → TAT 5
  • E: 完了 6, 到着 4 → TAT 2
  • 平均 TAT = $(2+11+3+5+2)/5=23/5=4.6$ 秒

FAQ