Proportional share og multiprosessor-planlegging

Når MLFQ ikke er nok

MLFQ er pragmatisk og fungerer i de fleste systemer, men den gir ingen garanti om hvor mye CPU en prosess faktisk får. Hvis du sier «denne kodebasen skal ha 30 % av kjernen», må du ha en helt annen mekanisme. Det er det proportional share handler om: gi hver jobb en eksplisitt vekt eller andel, og sørg for at fordelingen over tid samsvarer med vekten.

I dette kapittelet tar vi to skritt utover MLFQ. Først ser vi på algoritmer som leverer proporsjonal fordeling — lottery scheduling, stride scheduling og cfs (completely fair scheduler). Deretter løfter vi blikket til flere kjerner: når CPU-en har 8 eller 64 kontekster, blir spørsmålet «hvilken jobb skal kjøre på hvilken kjerne», ikke bare «hvem er nestemann».

Lottery — sannsynlighet som fordelingsmekanisme

Ideen er enkel: gi hver prosess et antall billetter. Ved hvert kvantum trekker scheduleren en tilfeldig billett, og vinneren kjører. Forventet andel er bare ƒforventet cpu-andel i lottery scheduling. Med 75 billetter til A og 25 til B, vinner A i snitt 75 % av trekningene.

Det fine er at mekanismen er triviell å implementere — én array, én random — og at den naturlig håndterer dynamiske endringer: gi en prosess flere billetter, og den får mer CPU umiddelbart. Det vanskelige er at det er stokastisk. Over korte intervaller kan A få mye mindre eller mye mer enn 75 %; først når antall trekninger er stort konvergerer det.

stride scheduling fjerner usikkerheten. Hver prosess har en stride omvendt proporsjonal med billetter (mange billetter → kort stride) og en pass-teller. Scheduleren velger alltid prosessen med lavest pass og øker passet med stride. Resultatet er nøyaktig proporsjonal fordeling, men det krever at scheduleren holder global tilstand — pass-tellere må rebalanseres når en ny prosess kommer eller går.

CFS — Linux sin proporsjonale scheduler

Linux sin Completely Fair Scheduler er proportional share i ren form, men uten lotteri. Hver tråd har en virtual runtime (vruntime) — vekt-justert kjøretid. Reglen er enkel: kjør alltid tråden med lavest vruntime.

Vekten kommer fra nice value. Nice går fra -20 (høyest prioritet) til +19 (lavest), default 0. Lavt nice betyr høy vekt, og høy vekt betyr at vruntime vokser saktere. Da ligger tråden lenger venstre i køen, og den blir valgt oftere. Sammenhengen er multiplikativ — ƒvruntime-akkumulering viser hvordan en tråd med dobbelt så høy vekt akkumulerer vruntime halvparten så fort.

Time slice er ikke fast, men beregnes per tråd som ƒcfs time slice. Med sched_latency på 48 ms og fire like tråder får hver 12 ms. Med åtte like tråder ville det blitt 6 ms — men sched_min_granularity setter en gulv-verdi (typisk 6 ms) slik at vi ikke ender opp med 0,5 ms-vinduer som drukner i kontekstbytte-overhead.

Rød-svart tre og min_vruntime

For å velge raskt holder CFS alle aktive tråder i et rød-svart tre i cfs indeksert på vruntime. Innsetting og sletting er O(log n), og «hent neste» er O(1) — det er bare å plukke noden lengst til venstre. På en moderne kjerne er det mye raskere enn å iterere gjennom et MLFQ med flere køer.

Et subtilt problem dukker opp ved I/O. En tråd som har sovet i et halvt sekund har lav vruntime sammenlignet med tråder som har kjørt mye. Hvis den våkner og blir lagt rett i treet, dominerer den CPU-en helt til vruntime når opp på nivå med de andre. Det er ikke rettferdig — den sov, den jobbet ikke. Løsningen er min_vruntime: scheduleren bokfører laveste vruntime i køen, og når en tråd vekkes settes vruntime til ƒvruntime ved oppvåkning fra i/o. Da må den konkurrere normalt fra første kvantum.

Speedup — den enkleste multiprosessor-metrikken

Når vi går fra én kjerne til flere, måler vi gevinsten med ƒspeedup. Hvis et program tar 100 sekunder på én kjerne og 30 på fire, har vi speedup 3,33. Idealet er lineær — fire kjerner gir 4× — men nesten ingen reelle arbeidslaster når det.

Hvor effektivt vi bruker maskinvaren sier ƒparallell effektivitet. Speedup 3,33 på fire kjerner gir effektivitet 0,83 — vi kaster bort 17 % av kapasiteten på synkronisering, ledige kjerner og cache-misser. Når vi snakker om skalerbarhet, mener vi hvor godt effektiviteten holder seg når p øker. Et godt skalerbart program har effektivitet > 0,8 selv ved 32 kjerner; et dårlig faller til 0,3 fordi alle tråder kjemper om samme lås.

Single queue vs multi queue

Den enkleste multiprosessor-scheduleren er single-queue scheduling: alle kjerner henter sin neste jobb fra én felles kø. Den er korrekt og enkel å resonere om. Problemet er låsen — hver gang en kjerne plukker en jobb, må den ta en spinlock på køen, og med 32 kjerner som plukker hvert kvantum blir låsen en flaskehals. Dessuten har køen ingen idé om hvor jobben kjørte sist, så den samme jobben kan hoppe fra kjerne 0 til kjerne 7 mellom hvert kvantum.

multi-queue scheduling løser begge: hver kjerne har sin egen kø. Inga global lås, og en jobb pleier å bli liggende på samme kjerne. Men det skaper et nytt problem — hva om kø 0 har 10 jobber og kø 7 har null? Da må scheduleren periodisk balansere, vanligvis ved at en ledig kjerne stjeler arbeid fra en travel.

Cache affinity og når flytting koster

Grunnen til at vi prøver å holde tråder på samme kjerne er cache affinity. Når en tråd har kjørt et par millisekunder på en kjerne, har L1- og L2-cachen «varmet opp» — instruksjoner og data tråden trenger ligger der. Flytter vi tråden til en annen kjerne, må alt lastes inn på nytt fra L3 eller hovedminnet. Det kan koste flere millisekunder før ytelsen er tilbake.

Konkret: en typisk L1-cache er 32 KiB med ~1 ns aksesstid. L2 er 256 KiB med 4 ns. L3 deles mellom kjerner og er 8-32 MiB med 12-30 ns. Hovedminne er 100 ns. En tråd som mister sin L1+L2-state og må fylle den på nytt, gjør tusenvis av cache-misser i de første millisekundene etter flytting. Det er målbart — opptil 25 % ytelsestap på minnetunge programmer rett etter en migrering.

load balancing må derfor være konservativt. En typisk regel: ikke flytt en tråd hvis kjernen den kjørte på sist fortsatt er aktiv. Bare hvis ulempen ved at en kjerne står ledig er større enn cache-tapet, gjør vi flyttingen. På NUMA-systemer (der hovedminne også er kjerne-nært) er regelen enda strengere — å flytte en tråd til en annen NUMA-node betyr at alle dens minne-aksesser må krysse en sakte interconnect, og latensen kan dobles.

I praksis bruker Linux CFS multi-queue per kjerne (en runqueue per CPU) og kjører periodisk lastbalansering. Cache-affinity er heuristikk: scheduleren foretrekker å holde tråden lokalt, men gir slipp hvis ubalansen blir stor nok. Det er en pragmatisk balansegang — verken ren proporsjonalitet eller ren cache-vennlighet vinner alene.

Pris for rettferdighet

En siste tanke: alle disse mekanismene har overhead. CFS sin rød-svart-tre er ikke gratis å oppdatere ved hvert kvantum — innsetting og sletting tar noen titalls nanosekunder, multiplisert med hyppigheten av kontekstbytte. Lottery sin tilfeldighetsgenerator må kjøres for hver trekning. Lastbalansering på multi-queue krever låser når jobber stjeles, og må kjøre med jevne mellomrom selv om ingenting skjer.

På et system med få tråder og lite konkurranse er den enkleste mulige scheduleren ofte raskest. Det er først når man har dusinvis av tråder og strenge rettferdighetskrav at proportional share betaler tilbake — og det er nettopp scenariet i moderne servere og datasentre. På en mobil-CPU med fire tråder kan en MLFQ-variant være mer enn nok; på en server med 64 kjerner og hundrevis av container-prosesser er CFS uerstattelig.