応用情報技術者 2013年 春期 午前2 問17

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

正解の理由

解法ステップ

1. ターンアラウンドタイムの定義を確認する。
   ターンアラウンドタイム $=$ 終了時刻 − 到着時刻（$T_{turn}=C-A$）。
2. 時刻順に「到着済みの中で最短」を非プリエンプティブで選ぶ（途中で中断しない）。
3. 時刻ごとのスケジューリングを決める（到着時刻と処理時間に注目）:
   • 時刻0：到着済みはAのみ → Aを実行（処理時間2秒）
     Aは0→2で完了。
   • 時刻2：到着済みはB(1秒到着,4秒)とC(2秒到着,3秒) → 短いCを選択
     Cは2→5で完了。
   • 時刻5：到着済みはB(4秒), D(2秒), E(1秒)（いずれも到着済み） → 最短のEを選択
     Eは5→6で完了。
   • 時刻6：残りはB(4秒)とD(2秒) → Dを選択
     Dは6→8で完了。
   • 時刻8：残ったBを実行
     Bは8→12で完了。
4. ジョブBの到着時刻は1秒、終了時刻は12秒なのでターンアラウンドタイムは $12-1=11$ 秒。

選択肢別の誤答解説

• ア: 8
  誤りの多くは「到着していないジョブを選んでしまう」「到着済みでも短いジョブを見落とす」ことに由来します。例えば時刻2でCを選ばずBを優先したり、Eがまだ到着していない時刻にEを使う誤りがあると、Bの完了時刻を小さく見積もってしまいがちです。本問では時刻2でCが選ばれるため、この値は成り立ちません。
• イ: 9
  9秒となるのはBの完了時刻を10秒と見積もった場合（$10-1=9$）ですが、そのような完了時刻は到着順やSJFのルールに合致しません。到着・選択のルールを正しく適用するとBの実行開始は時刻8であり、完了は12秒になります。
• ウ: 10
  10秒はBの完了を11秒とする誤り（$11-1=10$）に対応します。これも、時刻5以降にEとDを先に終わらせる順序は正しいものの、どちらかを誤って扱うなどでBの開始時刻を短く見積もった場合に出やすい値です。正しいSJF適用ではBは8秒に開始します。
• エ: 11
  本問の正解です。上記の手順どおり到着済みの中から常に最短を非プリエンプティブで選ぶと、Bは8→12で完了しターンアラウンドは $12-1=11$ 秒になります。

よくある誤解

• 「到着予定の中で最短を選ぶ」と誤解する
  実際は「到着済みのジョブの中で最短」を選ぶのが原則です。到着していないジョブは比較対象になりません。
• プリエンプティブと非プリエンプティブを混同する
  プリエンプティブ（短いジョブ到着で実行中のジョブを中断）なら順序や待ち時間が変わる場合があります。本問は非プリエンプティブで中断しません。
• ターンアラウンドタイムと待ち時間を混同する
  ターンアラウンドは「終了−到着」、待ち時間は「実行されるまでの合計待ち時間」です。計算式を明確に区別してください。

補足コラム

• ターンアラウンドタイムの計算はシンプルですが、スケジューリングルールの適用ミスが誤答の主因です。到着時刻の境界（ちょうど到着する時刻）も「到着済み」に含めて判断します（本問でCは時刻2に到着し、A終了直後の選択対象になります）。
• SJFは平均待ち時間を短くする傾向がありますが、到着の偏りによっては後発の長いジョブが極端に遅れる（飢餓）ことがあります。プリエンプティブ版は短いジョブが来るたびに中断されるため、挙動が変わります。

FAQ