Miten CPU scheduling toimii, ja mitkä ovat yleiset algoritmit?

Question

IT Interview Practice · Accepted Answer

**CPU scheduling** on kernelin päätös siitä, *mikä* valmis thread saa CPU:n *seuraavaksi* ja *kuinka pitkäksi aikaa*. Koska ajettavia threadeja on yleensä enemmän kuin ytimiä, **scheduler** limittää (multiplex) ne pyrkien tasapainottamaan kilpailevia tavoitteita — **throughput**, **matala latenssi / vasteaika** ja **oikeudenmukaisuus** — samalla välttäen **starvationia** (nälkiintyminen).

## Yleiset algoritmit

```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** havainnollistaa ydinnuppulaa — **quantumia**:

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

## Todelliset schedulerit

Linuxin pitkäaikainen oletus oli **CFS (Completely Fair Scheduler)**: kiinteiden aikaviipaleiden sijaan se seuraa kunkin taskin **virtual runtimea (vruntime)** ja ajaa aina threadia, joka on saanut vähiten CPU:ta tähän mennessä, painotettuna sen **nice**-arvolla — approksimoiden ajatusta "kaikki saavat oikeudenmukaisen osuuden". Se avaimoi puna-mustan puun (red-black tree) vruntimen mukaan, joten seuraavan taskin valinta on O(log n). (Uudemmat kernelit käyttävät EEVDF:ää, hienosäätöä samalla oikeudenmukaisuustavoitteella plus tiukemmilla latenssirajoilla.)

**Preemptive vs. cooperative:** modernit OS:t ovat **preemptive** — timer interrupt antaa schedulerin ottaa CPU:n väkisin takaisin, joten yksi thread ei voi monopolisoida ydintä.

## Miksi se on tärkeää

Scheduling muovaa suoraan latenssia ja throughputia, jonka käyttäjät tuntevat. Haastattelijat luotaavat sitä nähdäkseen, ymmärrätkö kompromissit — miksi interaktiivinen työkuorma haluaa lyhyet quantumit tai priority boostin, miksi priority scheduling tarvitsee **agingin** starvationin estämiseksi ja miten MLFQ/CFS saavat hyvän interaktiivisen käytöksen tietämättä jobien pituuksia etukäteen. Se on myös ajatusmalli `nice`-arvon virittämisen, real-time-prioriteettien ja nälkiintyneen tai nykivän palvelun diagnosoinnin takana.

Yleiset algoritmit

Todelliset schedulerit

Miksi se on tärkeää

Aiheeseen liittyvät kysymykset