OPERATING SYSTEMS / CPU SCHEDULING
CPUタスクスケジューリングを図解｜FCFS・ラウンドロビン・SJF・優先度とスタベーション
仕事が次々と到着するとき、CPUは誰を先に処理するべきでしょうか。短い仕事を優先すると平均待ち時間は減りますが、長い仕事がいつまでも始まらない問題が起こります。
1. 飲食店の厨房から考える「誰を先に処理するか」
料理人が一人しかいない厨房を想像してください。先に届いた30分かかる煮込み料理を始めるか、後から届いた2分で作れるサラダを先に出すか。注文順なら公平ですが短い料理も待ち、短い料理優先なら長い料理がいつまでも着手されない可能性があります。限られた処理能力をどう分けるか、という問題がCPUスケジューリングの出発点です。
現実のPCでは、文書編集・音楽再生・印刷データの作成・ウイルススキャンなどが並行して進みます。1コア上ではOSが実行するスレッドを切り替えることで、複数の仕事が進んでいるように見えます。この切替えの規則を学びます。
2. プロセス・スレッド・タスクを区別します
プロセス（process）は実行中のプログラムの管理単位、スレッド（thread）はプロセス内の実行の流れです。「タスク（task）」は文脈によって処理単位を広く指します。OSは実行可能なスレッド等にCPU時間を割り当てます。1つのCPUコアは、ある瞬間には基本的に1つの命令の流れを進めます。高速に切り替えることで、多数の仕事が同時進行して見えます。
3. CPUが仕事を選ぶ場所──実行可能待ち行列
CPUで今すぐ動けるタスクは、実行可能待ち行列（ready queue）で順番を待ちます。スケジューラ（scheduler）は「次は誰にCPUを渡すか」を決めます。切替え時にはコンテキストスイッチ（context switch）が発生し、レジスタなど実行状態を保存・復元します。
4. 実行可能と待機中は違います
ディスクからデータが届くのを待っているタスクは、CPUを使う準備ができていません。これは待機（blocked / waiting）状態です。一方、実行可能（ready）状態は「CPUが空けばすぐ実行できるが、割当てを待っている」状態です。『待ち時間』の議論ではこの違いが重要です。
5. プリエンプティブとノンプリエンプティブ
| 方式 | 意味 | 典型例 |
|---|---|---|
| プリエンプティブ（preemptive） | 途中でCPUを取り上げ、ほかのタスクに渡せる | ラウンドロビン、SRTF |
| ノンプリエンプティブ（non-preemptive） | 実行開始後は原則として完了や自主的な待機まで動かす | FCFS、通常のSJF |
例えば料理人が「今の料理を仕上げるまで次に行かない」のがノンプリエンプティブ、「一定時間ごとに別の料理へ移る」のがプリエンプティブに近い考え方です。
6. FCFS / FIFO──最初に来た仕事から
FCFS（First Come, First Served／ファースト・カム・ファースト・サーブド）は到着順方式です。FIFO（First In, First Out／先入れ先出し）とも結び付く考え方です。順序が予測しやすく、後から来た仕事が先に割り込まない一方、巨大な処理が先頭にいると、小さな処理まで長く待たされます。これをコンボイ効果（convoy effect）と呼びます。
7. ラウンドロビン──時間を区切って公平に回す
Round Robin（ラウンドロビン、RR）は、タイムクォンタム（time quantum／時間片）と呼ぶ一定時間だけCPUを渡し、終わらなければ待ち行列の末尾へ戻します。待っているタスクにも順番が回りやすくなりますが、切替えを細かくしすぎるとコンテキストスイッチのコストが増えます。
8. SJF──短い仕事から処理して平均待ち時間を減らす
SJF（Shortest Job First／ショーテスト・ジョブ・ファースト）は、次に実行可能な仕事の中から予定CPU処理時間が最も短いものを選びます。現在実行中の仕事は途中で奪わないノンプリエンプティブ方式として扱うのが一般的です。
例えば、全タスクが同時到着し、処理時間がA=8、B=2、C=1であれば、到着順 A→B→C の待ち時間は0、8、10で平均6です。SJFで C→B→A にすると待ち時間は0、1、3で平均約1.33です。ただし必要処理時間を事前に正確に予測することは容易ではありません。
9. スタベーション──短い仕事が増えると長い仕事は始まらない
スタベーション（starvation／飢餓）は、一部のタスクに必要なCPU時間がいつまでも割り当てられない状態です。SJFでは、長いタスクLが待っている間、Lより短い仕事が次々と到着すると、スケジューラが短い仕事を選び続ける可能性があります。
10. SRTF──実行中でも短い仕事を優先する方式
SRTF（Shortest Remaining Time First／残り実行時間最短優先）は、SJFをプリエンプティブにした考え方です。処理中より残り時間の短いタスクが到着すると切り替えます。平均待ち時間を小さくできる場合がありますが、長いタスクの飢餓をさらに起こしやすくなるケースもあります。
11. 優先度スケジューリングとエージング
優先度方式（priority scheduling）は、重要なタスクからCPUを割り当てます。固定優先度のままだと低優先度の仕事が待ち続けることがあります。そこで、待機時間が長いほど優先度を徐々に上げる「エージング（aging）」を使うと、飢餓を緩和できます。期限のある処理と公平性の調整にも関わる発想です。
12. 方式ごとの違いをガントチャートで見る
ガントチャート（Gantt chart）は、時間軸のどの区間でどのタスクがCPUを使ったかを示します。同じ処理の総量でも、処理する順番によって「誰がどれほど待ったか」は変わります。
同じ仕事を異なる順序で処理した場合（模式図・すべて時刻0に到着した例）
上図は方式による順序の直感を示す模式図です。正確な完了時刻・到着時刻を考慮した結果は下の操作ラボで確認できます。
13. 平均待ち時間・ターンアラウンド時間・応答時間
| 指標 | 式・意味 | 実感しやすい例 |
|---|---|---|
| 待ち時間（waiting time） | 実行可能な状態でCPUの割当てを待った合計時間 | 料理の調理開始を待つ |
| ターンアラウンド時間（turnaround time） | 完了時刻 − 到着時刻 | 注文してから料理が完成するまで |
| 応答時間（response time） | 最初の実行開始時刻 − 到着時刻 | 最初に調理が始まるまで |
この操作ラボでは、CPU処理だけを扱い、I/O待ち時間とコンテキストスイッチ時間を0としています。そのため「待ち時間＝ターンアラウンド時間−必要CPU時間」が成り立ちます。
14. どの方式にも一長一短があります
| 方式 | 利点 | 注意点 |
|---|---|---|
| FCFS | 単純で到着順の公平性 | 長い処理が先頭を占有する |
| RR | 多くの仕事へ順番が回る | 時間片の設定と切替えコスト |
| SJF | 平均待ち時間の短縮が期待できる | 処理時間の見積りが必要、長い仕事の飢餓 |
| SRTF | 残り時間に応じ柔軟に切替え | 短い仕事の継続到着で長い仕事が不利 |
| 固定優先度 | 重要処理へ資源を先に配分 | 低優先度タスクの飢餓 |
| 優先度＋エージング | 待ち続けるタスクを救いやすい | 調整と実装が複雑 |
15. 具体的な問いから方式を識別する
「待ち時間が長いほど優先度を上げる」はエージング付きの動的優先度方式です。「一定時間で処理を中断し待ち行列の最後尾」はRRです。「最短の予定処理時間から選び、現在実行中の処理の終了等を待つ」はノンプリエンプティブSJFです。「到着した順に先頭から実行」はFCFSです。
16. 実際のOSではより複雑な条件が加わります
現代のOSは、タスクの優先度だけでなく、CPUコア数、I/O待ち、対話応答性、CPUキャッシュ、プロセッサ間の移動、リアルタイム期限などを考慮します。複数のCPUコアがある場合、ここまでの単一CPUモデルをそのまま適用することはできません。
例えば、ファイルを読み込む処理はディスクの応答を待つ間CPUを使わず、動画のエンコードはCPUを長く使うことがあります。OSはこうしたI/O中心の仕事とCPU中心の仕事を区別しながら実行を進めます。
17. 操作ラボで方式を比較してみましょう
タスクの到着時刻、必要CPU時間、優先度を自由に変更してください。RRでは時間片を変えられます。タイムラインを1単位ずつ進めると、各タスクの処理順が分かります。
操作ラボ｜CPUスケジューラを動かしてみましょう
単一CPU・整数時間・切替えコスト0の教育用モデルです。優先度は数値が小さいほど高く、エージングは待機3単位ごとに優先度を1上げます。
| タスク | 到着時刻 | 必要CPU時間 | 優先度 |
|---|---|---|---|
| A | |||
| B | |||
| C | |||
| D |
各マスは1時間単位です。色が薄いマスはまだ再生していない未来です。
| タスク | 完了時刻 | 滞在時間 | 待ち時間 |
|---|---|---|---|
| A | 9 | 9 | 0 |
| B | 12 | 11 | 9 |
| C | 10 | 8 | 7 |
| D | 15 | 12 | 9 |
実験：Aの必要CPU時間を16に、B・C・Dを1にしてSJFを選んでください。短い仕事が先に終わり、長いAの開始が遅れます。短い仕事が継続的に追加される環境では、Aがいつまでも待つ「スタベーション」が起こり得ます。
18. 要点の整理
OSのタスクスケジューリングは、CPUを使いたい複数のタスクから次に実行するものを選ぶ仕組みです。FCFSは到着順、RRは一定時間で交代、SJFは短い仕事から、SRTFは残り時間の短い仕事を優先します。固定優先度とSJF系ではスタベーションに注意が必要で、エージングは待機時間に応じて優先度を引き上げる対策になります。