CPU スケジューリングはどのように機能し、一般的なアルゴリズムは何ですか?

Question

IT Interview Practice · Accepted Answer

**CPU スケジューリング (CPU scheduling)** は、*どの* 実行可能なスレッドが *次に* CPU を得るか、そして *どれだけの間* かという kernel の決定です。通常、実行可能なスレッドはコアより多いため、**scheduler** はそれらを多重化 (multiplex) し、競合する目標 — **スループット**、**低レイテンシ / 応答時間**、**公平性** — のバランスを取りつつ、**スタベーション (starvation)** を避けようとします。

## 一般的なアルゴリズム

```text
FCFS (first-come, first-served) → simple, but one long job blocks everyone (convoy effect)
SJF  (shortest job first)       → optimal avg wait, but needs to know job length; can starve long jobs
Round-robin (RR)                → each job a fixed TIME SLICE (quantum), cycle through → fair, good latency
Priority                        → highest priority first → can STARVE low priority (fix: aging)
MLFQ (multi-level feedback)     → several priority queues; jobs that use a full quantum sink,
                                  interactive jobs that yield stay high → approximates SJF without knowing lengths
```

**Round-robin** は中核的なつまみ — **quantum** — を示します:

```text
quantum too SMALL → fair & responsive, but lots of context-switch overhead
quantum too LARGE → less overhead, but degrades toward FCFS (poor responsiveness)
```

## 実際の scheduler

Linux の長年のデフォルトは **CFS (Completely Fair Scheduler)** でした: 固定スライスの代わりに各タスクの **virtual runtime (vruntime)** を追跡し、常にこれまで最も CPU を受け取っていないスレッドを、その **nice** 値で重み付けして実行します — 「全員が公平な取り分を得る」を近似します。vruntime をキーにした赤黒木 (red-black tree) を使うので、次のタスクの選択は O(log n) です。(新しいカーネルは EEVDF を使い、同じ公平性の目標に加えてより厳しいレイテンシ限界を持つ改良版です。)

**Preemptive vs cooperative:** 現代の OS は **preemptive (プリエンプティブ)** です — タイマー割り込みにより scheduler が強制的に CPU を取り返せるので、1 つのスレッドがコアを独占できません。

## なぜ重要なのか

スケジューリングは、ユーザーが感じるレイテンシとスループットを直接形作ります。面接官はトレードオフを理解しているか探ります — なぜインタラクティブなワークロードは短い quantum や優先度ブーストを望むのか、なぜ priority scheduling はスタベーションを防ぐために **aging** を必要とするのか、MLFQ/CFS はどうやってジョブ長を事前に知らずに良好なインタラクティブ挙動を得るのか。これは `nice` の調整、リアルタイム優先度、そしてスタベーションや遅延したサービスの診断の背後にあるメンタルモデルでもあります。

一般的なアルゴリズム

実際の scheduler

なぜ重要なのか

関連する質問