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

ラウンドロビンの終了時刻【午前2解説】

正解の理由

解法ステップ

1. 各プロセスの到着時刻と必要CPU時間を把握する
   • P1: 到着0, CPU5
   • P2: 到着3, CPU7
   • P3: 到着6, CPU5
2. タイムクウォンタムは2秒なので、CPUは2秒ごとにプリエンプト（中断）され、中断されたプロセスは待ち行列の末尾に入る。ただし「新規生成と中断再入が同時」の場合は新規を先に入れる規則に注意する。
3. 時刻ごとに実行中プロセスと待ち行列を更新していく（以下で詳細タイムラインを示す）。
4. P2の各実行スライスの合計が7秒に達する時刻を求め、P2到着時刻との差分を答えとする。

• 0–2: P1 実行（残り3）
  待ち行列: P1（実行後に再入）
• 2–4: P1 実行（残り1）
  到着3でP2がキューに追加 → キューは [P2, (P1は実行中が終われば末尾)]
• 4–6: P2 実行（残り5）
  キューは [P1]
• 6秒時点: P2が中断され再入と同時にP3が到着。規則により新規のP3を先に挿入するため、キューは [P1, P3, P2]
• 6–7: P1 実行（残り0）→ P1 完了
• 7–9: P3 実行（残り3）
  キューは [P2]
• 9–11: P2 実行（残り3）
  キューは [P3]
• 11–13: P3 実行（残り1）
  キューは [P2]
• 13–15: P2 実行（残り1）
  キューは [P3]
• 15–16: P3 実行（残り0）→ P3 完了
• 16–17: P2 実行（残り0）→ P2 完了

選択肢別の誤答解説

• ア: 12
  誤り。P2が到着後12秒で完了するとすると絶対完了時刻は15秒になりますが、上の正しいキュー順だとP2は15秒時点でまだ残り1秒を持っており未完了です（15–16でP3が先に実行されるため）。
• イ: 14
  正しい。上記のタイムラインにより、到着3秒から14秒後（絶対時刻17秒）にP2は完了します。
• ウ: 16
  誤り。到着から16秒後（絶対時刻19秒）ではP2は既に完了しているため過大評価です。これはP2の再入順や新規優先ルールを考慮せず、遅延を余分に見積もったケースに相当します。
• エ: 17
  誤り。到着から17秒後（絶対時刻20秒）はさらに過大。実際のスライス割当を正確に追えばP2はそれより早く終わります。

よくある誤解

• 「時刻6秒で新規到着のP3がP1より先に実行される」と誤るケース：実際は時刻6での競合は「再入されるP2」と「新規P3」の間の順序に関する規則であり、既に待ち行列にいるP1の存在を無視してはいけません。P1は待ち行列先頭にいるためまず実行されます（6–7）。
• 同時事象の扱いを逆にする：中断再入と新規到着が同時なら「新規優先」と明記されている点を見落とすと、P2がP3より先に再入されてしまい以後の順序と完了時刻を誤算定します。

補足コラム

FAQ