Hoe werkt CPU-scheduling, en wat zijn de gangbare algoritmen?

Question

IT Interview Practice · Accepted Answer

**CPU-scheduling** is de beslissing van de kernel over *welke* gereedstaande thread de CPU *als volgende* krijgt, en voor *hoe lang*. Omdat er meestal meer uitvoerbare threads dan cores zijn, multiplext de **scheduler** ze, met als doel concurrerende doelen te balanceren — **throughput**, **lage latency / responstijd** en **fairness** — terwijl **starvation** wordt vermeden.

## Gangbare algoritmen

```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** illustreert de kernknop — het **quantum**:

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

## Echte schedulers

Linux' langdurige default was **CFS (Completely Fair Scheduler)**: in plaats van vaste slices houdt het de **virtual runtime (vruntime)** van elke task bij en draait het altijd de thread die tot nu toe de minste CPU heeft gekregen, gewogen naar zijn **nice**-waarde — een benadering van "iedereen krijgt een eerlijk aandeel." Het indexeert een red-black tree op vruntime, dus de volgende task kiezen is O(log n). (Nieuwere kernels gebruiken EEVDF, een verfijning met hetzelfde fairness-doel plus strakkere latencygrenzen.)

**Preemptive vs coöperatief:** moderne OS'en zijn **preemptive** — een timer-interrupt laat de scheduler de CPU met dwang terugnemen, zodat één thread een core niet kan monopoliseren.

## Waarom het belangrijk is

Scheduling bepaalt rechtstreeks de latency en throughput die gebruikers voelen. Interviewers polsen het om te zien of je de afwegingen begrijpt — waarom een interactieve workload korte quanta of een priority boost wil, waarom priority scheduling **aging** nodig heeft om starvation te voorkomen, en hoe MLFQ/CFS goed interactief gedrag krijgen zonder de joblengtes vooraf te kennen. Het is ook het denkmodel achter het afstellen van `nice`, real-time-prioriteiten, en het diagnosticeren van een uitgehongerde of haperende service.

Gangbare algoritmen

Echte schedulers

Waarom het belangrijk is

Gerelateerde vragen