Begreper & formler
Alle nøkkelbegrepene og formlene fra Proportional share og multiprosessor-planlegging, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.
Begreper
Sentrale begreper fra kapittelet med korte definisjoner.
Schedulering der prosesser får billetter, og sannsynligheten for CPU-andel er proporsjonal med antall billetter.
Målet om at hver jobb får en andel CPU som samsvarer med tildelt vekt eller antall billetter.
Fordelen ved å la en tråd fortsette på samme kjerne for å gjenbruke varme cache-linjer.
Flytting av arbeid mellom kjerner for å unngå at noen er overbelastet mens andre er ledige.
Alle kjerner henter arbeid fra én felles kø. Enkelt, men kan gi låseinnhold og cache-tap.
Hver kjerne har sin egen kø, ofte kombinert med periodisk balansering.
Hvor godt ytelsen øker når systemet får flere prosessorer eller kjerner.
Linux sin standard-scheduler siden 2007. Mål: rettferdig fordeling av CPU-tid. Bruker ikke prioritetskøer som MLFQ, men en enkelt rød-svart tre indeksert på virtual runtime.
Hvor mye CPU-tid en tråd har akkumulert, vektet med tråden sin nice/weight. CFS velger alltid tråden med lavest vruntime — det er den som har fått minst tid relativt sett.
Tall fra -20 (høyest prioritet) til +19 (lavest), default 0. CFS oversetter nice til en weight: jo lavere nice, jo høyere weight, jo saktere vokser vruntime, jo mer CPU får tråden.
Selvbalanserende søketre der noder er sortert på vruntime. Innsetting/sletting/slå-opp er O(log n). Tråden lengst til venstre (laveste vruntime) er neste som skal kjøre.
Bokført minimum vruntime i køen. Brukes når en tråd vekkes etter I/O — den får vruntime = max(egen vruntime, min_vruntime) slik at den ikke får urettmessig mye CPU bare fordi den sov lenge.
Tidsvinduet CFS prøver å gi alle aktive tråder kjøring innenfor (typisk 48 ms). Time slice per tråd ≈ sched_latency / antall aktive tråder, modifisert av weight.
Minste mulige time slice (typisk 6 ms). Hindrer at time slice blir absurd liten ved mange tråder.
Deterministisk variant av lottery: hver prosess har en stride (omvendt proporsjonal med billetter) og en pass-teller. Velg alltid prosessen med lavest pass-verdi, øk passet med stride. Gir nøyaktig proporsjonal fordeling uten flaks.
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
Forventet CPU-andel i lottery scheduling
Med mange trekninger vil andelen CPU-tid nærme seg denne brøken.
Speedup
Måler gevinsten av å bruke p prosessorer i stedet for én.
Parallell effektivitet
Viser hvor stor del av ideell skaleringsgevinst systemet faktisk oppnår.
CFS time slice
Tråd med høyere weight (lavere nice) får større andel av sched_latency-vinduet. Med default-vekt og N like tråder blir det sched_latency/N hver.
vruntime-akkumulering
Default-tråden (weight_0, nice=0) sin vruntime vokser 1:1 med klokketid. Tråd med høyere weight (lavere nice) får vruntime til å vokse saktere → den ligger lenger venstre i treet → får mer CPU.
vruntime ved oppvåkning fra I/O
Forhindrer at en prosess som sovet lenge dominerer CPU når den vekkes (vruntime hadde vært lav). Setter den til minst min_vruntime så den må konkurrere normalt.
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Forklare hvordan lottery- og stride-scheduling oppnår proporsjonal CPU-fordeling
- 02Regne ut speedup og parallell effektivitet for et eksempel-jobbsett
- 03Sammenligne single-queue og multi-queue scheduling med hensyn til cache-affinity og lastbalansering
- 04Beskrive hvordan CFS bruker vruntime, weight og rød-svart tre for å velge neste tråd