CMD + K
CMD + K
CPU-planlegging: fra FIFO til MLFQ
Scheduleringsdelen handler om policy: når flere prosesser vil ha CPU samtidig, hvem skal få kjøre først, hvor lenge og etter hvilke mål? Ulike algoritmer optimaliserer ulike metrikker, og det er derfor ingen universelt beste scheduler.
- 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
To mål som strir mot hverandre
God planlegging vil ha kort turnaround (oppgaver blir ferdige raskt) og kort responstid (interaktive ting føles snappy). De to målene drar i hver sin retning — det er hele dramaet i CPU-planlegging.
Vi måler det presist. ƒturnaround-tid sier hvor lenge prosessen var i systemet fra ankomst til ferdig. ƒresponse-tid sier hvor lenge brukeren ventet før prosessen kjørte i det hele tatt. Snitt-verdiene ƒsnitt turnaround brukes til å sammenligne algoritmer.
FIFO — enkleste mulige
fifo kjører prosesser i ankomstrekkefølge til de er ferdige. Resultatet er optimalt så lenge alle jobber er like lange. La én lang jobb komme først, og alle korte må vente på den — konvoy-effekten.
Eksempel: tre prosesser ankommer samtidig. A trenger 100 ms, B trenger 10 ms, C trenger 10 ms. Snitt-turnaround blir (100 + 110 + 120) / 3 = 110 ms.
SJF — sorter på lengde
sjf fjerner konvoyen ved å sortere på gjenstående kjøretid. Snitt-turnaround for samme tre prosesser: (10 + 20 + 120) / 3 = 50 ms. Mer enn dobbelt så bra.
To problemer: (1) du må kjenne kjøretidene på forhånd, og (2) lange jobber kan sulte hvis nye korte fortsetter å komme.
RR — bytt fort og ofte
round robin bytter mellom alle klare prosesser i et fast tidsvindu, ƒround-robin kvantum. Snitt-respons blir glimrende, men snitt-turnaround blir middelmådig — vi oppgir ferdig først for alle litt etter litt.
Kostnaden er kontekstbytte. Med 10 µs pr. switch og 10 ms kvantum bruker du 0.1 % av tida på overhead. Halver kvantumet og du dobler overhead.
MLFQ — det som faktisk brukes
Multi-Level Feedback Queue har flere køer med synkende prioritet. Nye prosesser starter på toppen. Bruker prosessen hele kvantumet sitt, synker den ett nivå. Gjør den I/O og blokkerer raskt, beholder den prioritet. Periodisk løftes alle tilbake til toppen for å unngå sult.
Resultatet: korte interaktive jobber holder seg høyt og får god respons; lange CPU-bundne synker og lar de små slippe gjennom.
Linux CFS — proporsjonal rettferdighet
Linux sin Completely Fair Scheduler er en variant. Alle tråder har en vekt (omvendt proporsjonal med nice-verdien). Hver får en time-slice gitt av ƒcfs time-slice, og kjøretiden bokføres som ƒvirtual runtime — vekt-justert kjøretid.
CFS plukker alltid tråden med lavest vruntime, lagret i et rød-svart tre. O(log n) innsetting, O(1) plukk. Etter en I/O-sleep settes vruntime til max(egen, min i køen), så tråden ikke får alle CPU-en når den våkner.
Lotteri og stride — andel, ikke prioritet
En annen skole: gi hver prosess billetter. ƒstride pr. prosess sier hvor langt hver prosess «går» pr. kvantum. Velg alltid den som har gått kortest. Resultatet er deterministisk proporsjonal CPU-deling uten å spore historie.
Lotteri er den randomiserte kusinen: trekk en billett tilfeldig. Over tid konvergerer det til samme fordeling, men er lettere å implementere.