Hvordan fungerer CPU-scheduling, og hvad er de almindelige algoritmer?

Question

IT Interview Practice · Accepted Answer

**CPU-scheduling** er kernens beslutning om, *hvilken* klar tråd der får CPU'en *som den næste*, og for *hvor længe*. Da der som regel er flere kørbare tråde end cores, multiplexer **scheduleren** dem med det formål at balancere modstridende mål — **throughput**, **lav latency / responstid** og **fairness** — samtidig med at **starvation** undgås.

## Almindelige algoritmer

```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** illustrerer den centrale knap — **quantum**:

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

## Rigtige schedulere

Linux' mangeårige standard var **CFS (Completely Fair Scheduler)**: i stedet for faste slices sporer den hver tasks **virtual runtime (vruntime)** og kører altid den tråd, der indtil videre har fået mindst CPU, vægtet efter dens **nice**-værdi — hvilket tilnærmer "alle får en fair andel". Den nøgler et red-black tree efter vruntime, så det er O(log n) at vælge den næste task. (Nyere kerner bruger EEVDF, en forfining med samme fairness-mål plus strammere latency-grænser.)

**Preemptive vs. cooperative:** moderne styresystemer er **preemptive** — et timer-interrupt lader scheduleren tvangsmæssigt tage CPU'en tilbage, så én tråd ikke kan monopolisere en core.

## Hvorfor det betyder noget

Scheduling former direkte den latency og throughput, brugerne mærker. Interviewere borer i det for at se, om du forstår afvejningerne — hvorfor en interaktiv workload ønsker korte quanta eller et priority-boost, hvorfor priority-scheduling kræver **aging** for at forhindre starvation, og hvordan MLFQ/CFS opnår god interaktiv adfærd uden at kende joblængder på forhånd. Det er også den mentale model bag at justere `nice`, realtidsprioriteter og at diagnosticere en udsultet eller hakkende service.

Almindelige algoritmer

Rigtige schedulere

Hvorfor det betyder noget

Relaterede spørgsmål