ITパスポート 2010年 春期 問76

ジョブの到着順（非プリエンプティブ）処理での所要時間計算【ITパスポート 解説】

正解の理由

解法ステップ

1. 各ジョブの到着時刻と処理時間を確認する。
   • ジョブ1：到着0秒、処理3秒
   • ジョブ2：到着4秒、処理4秒
   • ジョブ3：到着5秒、処理3秒
   • ジョブ4：到着7秒、処理5秒
2. 到着順で順に実行する。現在の時刻（CPUが空く時刻）を追う。
   • ジョブ1 は時刻0に開始、3秒で終了 → 終了時刻＝3秒
   • 次にジョブ2は到着が4秒。時刻3→4の間はCPUは空く（アイドル）。ジョブ2は到着時刻4秒に開始、処理4秒で終了 → 終了時刻＝8秒
   • ジョブ3は5秒に到着しているが、ジョブ2が8秒まで動作しているため8秒に開始、処理3秒で終了 → 終了時刻＝11秒
   • ジョブ4は7秒に到着しているが、ジョブ3の終了（11秒）まで待ってから開始、処理5秒で終了 → 終了時刻＝16秒
3. ジョブ4の所要時間（到着から完了まで）を計算する。
   • 到着7秒、完了16秒 → $16-7=9$ 秒

選択肢別の誤答解説

• ア: 5
  • ジョブ4の「処理時間」だけ（5秒）を答えてしまったパターン。設問は「到着してから完了するまで」の時間（到着からの経過）を問っているため、待ち時間を無視すると誤りです。
• イ: 8
  • おそらく「到着時刻7秒 + 処理1秒」など誤った計算や、前のジョブの終了時刻を短く見積もった結果です。実際はジョブ4は11秒開始→16秒終了なので到着からの時間は9秒になります。
• ウ: 9
  • 正解。上記の通り、到着7秒から完了16秒までで $16-7=9$ 秒です。
• エ: 12
  • 前のジョブの待ち時間を二重に数えた、またはアイドル時間を不適切に加算した可能性があります。正しい順序で終了時刻を求めると12秒にはなりません。

よくある誤解

• 「CPUは常に忙しい」と思い込むこと
  • ジョブ1終了（3秒）からジョブ2到着（4秒）までのように、CPUがアイドルになる時間が生じることがあります。アイドル時間を無視すると開始時刻の計算を誤ります。
• 到着順＝到着時間の単純な足し算で済むと考えること
  • 各ジョブの開始時刻は「そのジョブの到着時刻」と「前のジョブの終了時刻」のどちらか遅い方（max）になります。これを忘れると間違います。

補足コラム

• 用語メモ
  • ジョブ：処理すべき仕事（タスク）。ここではプログラムや処理要求を指します。
  • 到着時刻：ジョブがスケジューラに現れる時刻。
  • 処理時間（サービス時間）：そのジョブを終わらせるのに必要な実行時間。
  • ターンアラウンドタイム（到着から完了までの時間）：今回問われている量。
  • FCFS（First-Come-First-Served：到着順）: 到着順に処理する方式。ノンプリエンプティブ（実行中のジョブは中断されない）であることが多いです。
• 一般式（ジョブiの開始時刻）
  • start_i = max(arrival_i, finish_{i-1})
  • finish_i = start_i + service_i
  • 到着から完了まで = finish_i - arrival_i

jobs = [(0,3),(4,4),(5,3),(7,5)]  # (arrival, service)
finish = 0
for idx,(a,s) in enumerate(jobs, start=1):
    start = max(a, finish)
    finish = start + s
    print(f"Job{idx}: arrival={a}, start={start}, finish={finish}, turnaround={finish-a}")
# Job4 の turnaround は 9

FAQ