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

問題文

五つのジョブA〜Eに対して、ジョブの多重度が1で、処理時間順方式のスケジューリングを適用した場合、ジョブBのターンアラウンドタイムは何秒か。ここで,OSのオーバヘッドは考慮しないものとする。

選択肢

ア：8

イ：9

ウ：10

エ：11（正解）

五つのジョブA〜Eに対して、ジョブの多重度が1で、処理時間順方式のスケジューリングを適用した場合、ジョブBのターンアラウンドタイムは何秒か。【午前2 解説】

要点まとめ

結論：ジョブBのターンアラウンドタイムは11秒である。
根拠：処理時間順方式（SJF）では、到着済みの中で最も処理時間が短いジョブを優先し、ジョブBは後半に実行されるため待ち時間が長くなる。
差がつくポイント：到着時刻と処理時間の両方を考慮し、ジョブの実行順序を正確に把握することが重要である。

正解の理由

ジョブの多重度が1（単一ジョブ実行）で処理時間順方式を適用すると、常に到着済みの中で最も処理時間が短いジョブが選ばれます。

ジョブA（0秒到着、2秒処理）が最初に実行され、0〜2秒。
2秒時点で到着済みはB(4秒)、C(3秒)、D(2秒)。最短はD(2秒)、2〜4秒。
4秒時点で到着済みはB(4秒)、C(3秒)、E(1秒)。最短はE(1秒)、4〜5秒。
5秒時点で残るはB(4秒)、C(3秒)。最短はC(3秒)、5〜8秒。
最後にB(4秒)、8〜12秒。
ジョブBの終了時刻は12秒、到着時刻は1秒なのでターンアラウンドタイムは12−1＝11秒となり、選択肢のエが正解です。

よくある誤解

処理時間順方式は単純に処理時間が短い順に並べるだけと思い込み、到着時刻を無視してしまうことがあります。これにより実行順序や待ち時間の計算を誤ることが多いです。

解法ステップ

ジョブの到着時刻と処理時間を一覧で確認する。
時間0から開始し、到着済みのジョブの中で最短処理時間のジョブを選択する。
選択したジョブを完了まで実行し、終了時刻を記録する。
次の時刻で到着済みのジョブを再度確認し、最短処理時間のジョブを選ぶ。
すべてのジョブが完了するまで2〜4を繰り返す。
ジョブBの終了時刻から到着時刻を引き、ターンアラウンドタイムを算出する。

選択肢別の誤答解説

ア（8秒）：ジョブBを早く実行したと誤認し、待ち時間を過小評価している。
イ（9秒）：ジョブBの待ち時間を少し短く見積もり、処理順序を誤っている。
ウ（10秒）：ジョブBの実行開始時刻を早めに計算し、正確な待ち時間を算出できていない。
エ（11秒）：正しく処理時間順方式を適用し、待ち時間と実行時間を正確に計算している。

補足コラム

処理時間順方式（Shortest Job First, SJF）は平均待ち時間を最小化する理論的に優れたスケジューリング方式ですが、到着時刻が異なるジョブが混在する場合は、到着時刻を考慮した「最短残余時間優先（SRTF）」などの派生方式もあります。今回の問題は非プリエンプティブなSJFであるため、ジョブが一度開始すると中断されません。