Hvordan fungerer CPU-scheduling, og hva er de vanlige algoritmene?

Question

IT Interview Practice · Accepted Answer

**CPU-scheduling** er kernelens beslutning om *hvilken* klar tråd som får CPU-en *neste*, og for *hvor lenge*. Siden det vanligvis er flere kjørbare tråder enn cores, multiplekser **scheduleren** dem, med mål om å balansere konkurrerende hensyn — **throughput**, **lav latency / responstid** og **rettferdighet** — samtidig som **starvation** unngås.

## Vanlige 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 sentrale justeringsknappen — **quantum**:

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

## Ekte schedulere

Linux sin mangeårige standard var **CFS (Completely Fair Scheduler)**: i stedet for faste tidsluker sporer den hver tasks **virtual runtime (vruntime)** og kjører alltid tråden som har fått minst CPU så langt, vektet etter sin **nice**-verdi — en tilnærming til "alle får en rettferdig andel." Den nøkler et rød-svart tre etter vruntime, så å plukke neste task er O(log n). (Nyere kerneler bruker EEVDF, en forbedring med samme rettferdighetsmål pluss strammere latency-grenser.)

**Preemptive vs cooperative:** moderne OS-er er **preemptive** — et timer interrupt lar scheduleren tvangsmessig ta CPU-en tilbake, så én tråd ikke kan monopolisere en core.

## Hvorfor det er viktig

Scheduling former direkte den latencyen og throughputen brukere føler. Intervjuere graver i det for å se om du forstår avveiingene — hvorfor en interaktiv arbeidsmengde vil ha korte quanta eller et prioritetsløft, hvorfor prioritets-scheduling trenger **aging** for å hindre starvation, og hvordan MLFQ/CFS oppnår god interaktiv oppførsel uten å kjenne jobblengder på forhånd. Det er også den mentale modellen bak justering av `nice`, sanntidsprioriteter og diagnostisering av en utsultet eller treg tjeneste.

Vanlige algoritmer

Ekte schedulere

Hvorfor det er viktig

Relaterte spørsmål