Begreper & formler
Alle nøkkelbegrepene og formlene fra CPU-planlegging: fra FIFO til MLFQ, 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.
First In, First Out. Den som kom først, kjører først til den er ferdig.
Shortest Time-to-Completion First. Preemptiv variant som alltid velger jobben med minst gjenværende tid.
Hver jobb får et tidskvantum før neste slipper til. Godt for responstid, men gir overhead.
Multi-Level Feedback Queue. Endrer prioritet dynamisk basert på oppførsel for å favorisere interaktive jobber.
En jobb blir forbigått så lenge at den i praksis nesten aldri får kjøre.
Interaktive jobber som ofte blokkerer på I/O bør ikke straffes som om de var CPU-bundne.
MLFQ-regel der alle jobber periodisk flyttes opp til høyeste prioritetskø. Forhindrer at lange CPU-bundne jobber sulter ut, og lar nye interaktive jobber få respons.
MLFQ-regel der schedulerns nedrykk er basert på samlet CPU-tid brukt på et nivå, ikke på antall ganger jobben ble preemptert. Hindrer at en jobb gamingen schedulere ved å frivillig slippe CPU akkurat før time slice utløper.
Maksimal CPU-tid en jobb får før Round Robin/MLFQ tvinger en context switch. Stort quantum → mindre overhead, men dårligere responstid. Lite quantum → bedre respons, men flere context switches.
Når en prosess utnytter scheduler-reglene for å få urettferdig mye CPU — f.eks. ved å frivillig slippe CPU rett før time slice utløper, slik at gammel scheduler-versjon ikke registrerer forbruket.
Å lagre nåværende prosess sin tilstand (registre, PC, minne-mapping) og laste en annens. Tar typisk 1–10µs på moderne CPU-er, og inkluderer cache- og TLB-flushing.
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
Turnaround-tid
Batch-jobber ønsker ofte lav gjennomsnittlig turnaround.
Response-tid
Interaktive systemer bryr seg spesielt om denne metrikken.
Slowdown
Normaliserer opplevd venting etter hvor stor jobben egentlig er.
MLFQ-regelsett
Lær reglene utenat. Eksamen tester gjerne hva som skjer hvis en regel mangler (f.eks. uten regel 5 → starvation; uten regel 4 → gaming).
Trade-off i time quantum
MLFQ bruker ofte 10 ms øverst og 40+ ms nederst — interaktive jobber merker quantum knapt, batch-jobber unngår overhead.
Snitt turnaround
Gjennomsnitt av turnaround-tid over alle prosesser. SJF gir teoretisk minimum når alle jobber er klare samtidig.
Stride pr. prosess
I stride-scheduling: jo flere billetter, desto kortere stride, desto oftere blir prosessen valgt.
Round-Robin kvantum
Typisk tidsvindu pr. prosess i RR. For lite gir høyt switch-overhead, for stort gir dårlig respons.
CFS time-slice
Lengden på tidsvinduet i Linux CFS. Hver tråd får en andel proporsjonalt med sin vekt.
Virtual runtime
Vekt-justert kjøretid. CFS plukker alltid tråden med lavest vruntime — lavt nice → høy vekt → vruntime vokser saktere → mer CPU.
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Forklare forskjellen på turnaround-tid og responstid, og hvorfor de drar i hver sin retning
- 02Sammenligne FIFO, SJF og RR på et eksempel-jobbsett og regne ut snitt-verdier
- 03Beskrive de fem MLFQ-reglene og hvilken bug hver av dem hindrer
- 04Forklare hvordan CFS bruker vruntime og rød-svart-tre for å plukke neste tråd