Hur fungerar CPU-scheduling, och vilka är de vanliga algoritmerna?

Question

IT Interview Practice · Accepted Answer

**CPU-scheduling** är kernels beslut om *vilken* redo thread som får CPU:n *härnäst*, och *hur länge*. Eftersom det oftast finns fler körbara threads än cores multiplexar **schedulern** dem, med målet att balansera konkurrerande mål — **throughput**, **låg latency / responstid** och **rättvisa** — samtidigt som **starvation** undviks.

## Vanliga 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** illustrerar den centrala ratten — **quantum**:

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

## Riktiga schedulers

Linux långvariga standard var **CFS (Completely Fair Scheduler)**: i stället för fasta slices spårar den varje tasks **virtual runtime (vruntime)** och kör alltid den thread som fått minst CPU hittills, viktad efter dess **nice**-värde — en approximation av "alla får en rättvis andel." Den nycklar ett röd-svart träd på vruntime, så att välja nästa task är O(log n). (Nyare kernels använder EEVDF, en förfining med samma rättvisemål plus snävare latency-gränser.)

**Preemptive vs cooperative:** moderna OS är **preemptive** — ett timer interrupt låter schedulern med tvång ta tillbaka CPU:n, så att en thread inte kan monopolisera en core.

## Varför det är viktigt

Scheduling formar direkt den latency och throughput användare känner. Intervjuare undersöker det för att se om du förstår avvägningarna — varför en interaktiv arbetslast vill ha korta quanta eller en priority-boost, varför priority scheduling behöver **aging** för att förhindra starvation, och hur MLFQ/CFS får bra interaktivt beteende utan att känna till jobblängder i förväg. Det är också den mentala modellen bakom att justera `nice`, real-time-prioriteter, och att diagnostisera en utsvulten eller trög tjänst.

Vanliga algoritmer

Riktiga schedulers

Varför det är viktigt

Relaterade frågor