プロセススケジューリング

一つの CPU で同時に走れるプロセスは一つだが、実行可能なプロセスは複数ある。スケジューラーは決定点ごとに次の実行者を選ぶ。本課は同じ 4 プロセスを FCFS、SJF、Round Robin で実行し、ガント図と待ち時間を比較する。

一つのレジで大小の買い物かごを処理する状況に似ている。到着順、小さいかご優先、一定量ずつ処理して列の後ろへ戻す方式では、同じ仕事でも待ち方が変わる。

仕組み

レディキューは到着済みで CPU を待つプロセスを持つ。CPU は一度に一つを実行し、ガント図は各時間帯の担当を記録する。方針はディスパッチ時にキューから誰を選ぶかを決める。

FCFS は先着順でキュー先頭を取り、その CPU バーストを最後まで実行し、横取りしない。

SJF は準備済みの最短バーストを選ぶ。本課は非プリエンプティブで、長い処理が既に走っていれば短い新着も待つ。同じ長さなら早い到着を選ぶ。

Round Robin は先頭を最大一量子だけ実行する。既定 quantum=2、スライダーは 1–4。片内で終われば完了し、残ればプリエンプトして末尾へ戻す。片内と境界に到着したものを先に入れ、その後で中断したプロセスを戻す。

ターンアラウンド時間は完了時刻から到着時刻を引く。待ち時間はそこからバーストを引く。本課には I/O 待機がないため、その差はレディ状態の待機だ。

固定入力は P1 が t=0、burst=5、P2 が t=1、burst=3、P3 が t=2、burst=1、P4 が t=3、burst=2。長い処理の後に三つの短い処理が来る。

ステップ実行

既定 FCFS の流れは次のとおり。

1. t=0 は P1 だけなので [0,5] を実行する。P2、P3、P4 は t=1、2、3 に到着して並ぶ。P1 は 5 に完了し、ターンアラウンド 5−0=5、待ち 5−5=0。
2. P2 は [5,8]、ターンアラウンド 8−1=7、待ち 7−3=4。
3. P3 は [8,9]、ターンアラウンド 7、待ち 6。一単位の処理に六単位待つ。
4. P4 は [9,11]、ターンアラウンド 8、待ち 6。

ガント図は P1[0,5] P2[5,8] P3[8,9] P4[9,11]。平均待ち (0+4+6+6)/4=4.00、平均ターンアラウンド (5+7+7+8)/4=6.75。長いバーストが短い仕事を止めるコンボイ効果だ。

SJF でも開始済み P1 は 5 まで走る。その時点の P2=3、P3=1、P4=2 から短い順を選び、P1[0,5] P3[5,6] P4[6,8] P2[8,11]。P3 と P4 の待ちは各 3、P2 は 7。平均待ち 3.25、平均ターンアラウンド 6.00 になる。

Round Robin、量子 2 の七区間は P1[0,2] P2[2,4] P3[4,5] P1[5,7] P4[7,9] P2[9,10] P1[10,11]。

t=2 に到着する P3 は、中断された P1 より先にキューへ入る。P3 は 5 に完了して待ち 2、P4 は 9 で待ち 4、P2 は 10 で待ち 6、三片に分かれた P1 は 11 で待ち 6。平均待ち 4.50、平均ターンアラウンド 7.25 だが、t=7 までに全プロセスが初回の CPU を得ている。

同じプロセスはキュー、CPU、ガント図で同じ色を使う。待機中にカウンターが増え、輪番時の CPU 枠の下には今の量子で使った時間がたまり、満杯になるとプリエンプトされる。

方針の比較

この入力では SJF の平均が最小だ。全ジョブが同時に利用可能で長さが既知なら、非プリエンプティブな短い順が平均待ちを最小化する。到着がずれる場合、この定理を全貪欲 SJF スケジュールへ一般化できない。実システムはバーストを推定し、短い仕事が続けば長い仕事の飢餓も起こり得る。

輪番はここで平均値が最悪でも、準備済みの仕事へ順番に機会を与える。有限のキューと量子で実行が進み続ければ、各周の待ちを制限でき、長さの事前知識も不要だ。対話系は応答性と公平性を重視し、実際には優先度なども組み合わせる。FCFS は到着順という公平さを持つが、長い処理が後続を止める。

境界ケース

• キューが空で未来の到着があるなら、その時刻へ進み、ガント図にアイドル区間を描く。既定入力にはない。
• 残りが量子と等しければ、その片で完了し、無意味に再キューしない。
• 到着と量子終了が同時なら、新着を先、中断処理を後に入れる。他の教材では別規約もあり得る。
• SJF の長さが等しければ、早い到着を選ぶ。

よくある間違い

• 待ちとターンアラウンドを混同する。FCFS の P3 は後者 7、前者 6 で、差は burst=1。
• SJF が普遍的に最善だと思う。最適性の証明には同時利用可能などの条件があり、長さの予知や飢餓の問題もある。
• 量子は小さいほどよいと考える。1 にすると切り替え回数が増える。モデルは無料だが、実機には切替とキャッシュなどの費用があり、応答性と釣り合わせる。

モデルの範囲

単一 CPU、CPU 中心のジョブ、既知バースト、切替費用ゼロでディスパッチ規則を見せる。実運用は切替コスト、長さの推定、多段フィードバックキュー、優先度とエージング、コア間の負荷分散も扱う。本課の単純な方式をそのまま実用スケジューラーとは見なさない。