CPU スケジューリング

OS がどのプロセスに CPU を使わせるかを決める FCFS・SJF・SRTF・ラウンドロビン・優先度・多段フィードバックを、ガントチャートと待ち行列で 1 単位ずつ見せます。平均待ち時間や応答時間を方式ごとに比べられます。

例

OS の教科書でよく使われる 4 つのプロセスです。平均待ち時間は FCFS で 8.75、SJF で 7.75、SRTF で 6.5 になります。

プロセス	終了	ターンアラウンド	待ち時間	応答時間
P1	17	17	9	0
P2	5	4	0	0
P3	26	24	15	15
P4	10	7	2	2
平均		13	6.50	4.25

到着は 0〜30、バーストは 1〜20、優先度は 1〜9（小さいほど高い）。終了から右の列は、選んだ方式で最後まで動かしたときの値です。

残り時間が一番短いプロセスを選び、もっと短いプロセスが到着したら横取りします（Shortest Remaining Time First）。平均待ち時間は最小になりますが、長いプロセスが後回しにされ続けることがあります。

時刻 25 → 26 / 26

CPU

CPU を使っている待っている到着

時刻 25 の様子

CPU: P3残り 0
待ち行列: なし

この時刻に起きたこと

そのまま続けます

方式の比較

同じプロセスを 7 つの方式で動かした結果です（ラウンドロビンはクォンタム 2）。それぞれの列で一番小さい値を強調しています。待ち時間を減らす方式は長いプロセスを後回しにしがちで、応答時間や最長の待ち時間と引き換えになることがあります。

方式	平均待ち時間	平均ターンアラウンド	平均応答時間	最長の待ち時間	切り替え
FCFS	8.75	15.25	8.75	18	3
SJF	7.75	14.25	7.75	15	3
SRTF	6.50	13	4.25	15	4
ラウンドロビン	12.75	19.25	2	15	12
優先度	7.75	14.25	7.75	15	3
優先度（横取り）	6.50	13	4.25	15	4
多段フィードバック	13	19.50	1.50	15	9

使い方

例を選ぶか、表でプロセスの到着時刻・バースト時間（CPU を使う時間）・優先度を入力します。プロセスは 8 個まで追加できます。
方式を選び、再生や ◀ ▶ で 1 単位ずつ進めます。キーボードの ← → でも動かせ、Home / End で最初と最後に移ります。下の目盛りの数字を押すと、その時刻まで進みます。
ガントチャートの一番上は CPU を使っているプロセス、その下はプロセスごとの「使っている（濃い色）」「待っている（薄い色）」時間です。
「方式の比較」で、同じプロセスを 7 つの方式で動かしたときの待ち時間・応答時間・切り替えの回数を比べられます。

CPU スケジューリング

CPU は一度に 1 つのプロセスしか動かせないので、OS は動ける状態のプロセスの中から次に CPU を使わせるものを選びます。これを CPU スケジューリングといいます。何を良しとするかで選び方が変わり、全体の待ち時間を短くしたいなら短いプロセスを先に、操作への反応を速くしたいなら短い時間ずつ順番に、重要な処理を先に終わらせたいなら優先度で選びます。

SJF や SRTF は平均待ち時間が最小になることが証明されていますが、実際の OS はプロセスがあとどれだけ CPU を使うかを知りません。多段フィードバックキューは、CPU を長く使い続けるプロセスの段を下げていくことで、事前の知識なしに短いプロセスを優先します。Linux や Windows のスケジューラも、この考え方を発展させたものです。

計算のきまり

時間は 1 単位ずつ進めます。同じ時刻に到着したプロセスは表の順に並び、時間切れや横取りで戻るプロセスは、その時刻に到着したプロセスの後ろに並びます。
同じ条件のプロセスが複数あるときは、待ち行列に先に並んだほうを選びます。
プロセスの切り替えにかかる時間（コンテキストスイッチ）は 0 としています。切り替えの回数は表に出しています。