CPU-virtualisering og Limited Direct Execution

Direct execution — fart uten bremser

Den enkleste måten å la et program kjøre på CPU-en er å gi det CPU-en. Last instruksjonene inn i minnet, sett programtelleren, og slipp den løs. CPU-en kjører i full hastighet, OS-et er ute av veien, og programmet gjør jobben sin.

Problemet er to. Hvordan beholder OS-et kontrollen? Og hvordan hindrer det at programmet gjør noe det ikke skal? Hvis programmet for eksempel går inn i en uendelig løkke, sitter OS-et bak og ser på uten å kunne avbryte. Hvis programmet bestemmer seg for å lese disken direkte, kan det overskrive andre prosessers data.

Løsningen kalles limited direct execution, Limited Direct Execution. Vi lar programmet kjøre direkte — for å beholde fart — men setter inn maskinvaremekanismer som gjør at OS-et kan gripe inn når det trenger det. "Limited" er det operative ordet: kjøringen er rask, men begrenset.

Trap-instruksjonen

Den første mekanismen er trap: en kontrollert overgang fra brukermodus til kjernen. Når et program trenger noe OS-et må gjøre — åpne en fil, allokere minne, lese fra disk — utfører det en spesiell instruksjon (typisk syscall på x86-64, svc på ARM). CPU-en bytter automatisk til kernel mode, hopper til en forhåndsbestemt adresse, og kjører kernel-koden.

For at dette ikke skal være et hull i sikkerheten, peker trap-instruksjonen ikke hvor som helst. Den hopper til en bestemt rutine satt opp av kjernen, kalt en trap handler. Programmer kan ikke velge hvor de havner; CPU-en bestemmer. Dette er kjernen av hele LDE-tankegangen — vi gir programmet fri kjøring, men overgangene tilbake til kjernen er låste.

Trap-håndteringen begynner med å lagre brukermodus-registerne på kjernens stack, sjekke hvilket systemkall som ble bedt om (typisk via et nummer i et bestemt register som rax på x86-64), og kalle riktig kernel-funksjon. Når den er ferdig, brukes en spesiell iret- eller sysret-instruksjon for å gjenopprette brukerregister-tilstanden og overgi kontrollen tilbake til programmet.

Trap-tabellen — hvordan vet kjernen hvor den skal hoppe?

Når CPU-en booter, setter kjernen opp en trap table (også kjent som IDT, Interrupt Descriptor Table på x86). Det er en tabell i minnet hvor hver rad peker på en handler-rutine for én type trap: systemkall, divisjon-på-null, sideoverføring (page fault), timer-avbrudd, og så videre. CPU-en har et register (idtr på x86) som peker på tabellens startadresse.

Når en trap inntreffer, slår CPU-en opp i tabellen og hopper. Bare privilegert instruksjon kode kan endre tabellen — å sette opp trap-tabellen er en av de første tingene kjernen gjør under boot, og brukermodus-programmer kan aldri overskrive den. Det er denne hardware-støtten som gjør LDE mulig: vi kan stole på at trap-er alltid lander i kjernen, ikke i ondsinnet kode.

Antall innslag er stort — vanligvis 256 — fordi det dekker alle CPU-eksepsjoner, alle eksterne avbrudd, og hele syscall-overgangen. Hver type har sin egen handler.

Timer-interrupt — hvordan OS-et tar tilbake CPU-en

Trap dekker tilfellet der programmet frivillig overgir kontrollen. Men hva med løkken som aldri kaller systemkall? Et program som spinner uten ende ville monopolisert CPU-en evig hvis ikke OS-et hadde et triks: timer interrupt.

Maskinen har en hardware-timer som tikker periodisk — typisk hvert millisekund eller hvert tiende. Hver gang den tikker, genererer den et avbrudd. CPU-en avbryter det den holdt på med, hopper til timer-handleren i kjernen (som ligger oppført i trap-tabellen), og lar OS-et bestemme om gjeldende prosess skal fortsette eller ikke.

Slik beholder OS-et kontroll uansett hva programmet gjør. Timer-interrupt er den ene grunnen til at en uendelig løkke i én prosess ikke henger hele systemet — kjernen får sjansen til å bytte hver gang timeren tikker.

Når kjernen først er der, sjekker den om noe annet skal kjøre. Hvis ja, gjør den et context switch. Hvis nei, returnerer den til samme prosess og lar den fortsette.

Context switch — selve byttet

Når OS-et bestemmer at en annen prosess skal kjøre, må det utføre et context switch. Det er flere steg, og hvert steg er ren maskinvare-koreografi.

1. Lagre nåværende prosess sine CPU-registere i dens PCB. 2. Bytt sidetabell — last den nye prosessens minnemap inn i MMU-en (cr3 på x86). 3. Last den nye prosessens registere inn i CPU-en fra dens PCB. 4. Returner fra trap til den nye prosessens kode med iret.

Kostnaden er ikke null. Bare registerkopiering tar et titalls nanosekunder. Bytte sidetabell kan flushe TLB-en (med mindre du har PCID-støtte), hvilket gir mange cache-misses i etterkant. Totalt 1–10 µs i moderne systemer. Det er lite per bytte, men hvis kvantumet er kort (1 ms), kan overhead bli betydelig: ƒandel tidskutt brukt på bytte.

Et eksempel: 5 µs context switch og 1 ms kvantum gir 5/1000 = 0,5 % overhead. Halver kvantumet til 0,5 ms og du dobler overhead til 1 %. Halver igjen og du er på 2 %. Det er derfor moderne schedulere ikke bytter aggressivt — overhead spiser fort opp gevinsten i respons.

Preemption — kontrollsløyfen

Når OS-et tvinger en prosess til å gi fra seg CPU-en uten at prosessen selv har valgt det, kaller vi det preemption. ƒpreemption-prinsippet oppsummerer mekanikken: timer-interrupt → trap til kernel → mulig reschedule.

Uten preemption ville scheduling vært kooperativ — hver prosess måtte frivillig kalle systemkall for at OS-et skulle få sjansen til å bytte. Det fungerer i godartede systemer (gamle Mac OS, Windows 3.x), men en buggy prosess kan ta ned hele maskinen ved bare å løkke. Med preemption gir maskinvaren OS-et et sikkerhetsnett: uansett hva programmet gjør, blir det avbrutt regelmessig.

Den fine balansen er hvor ofte vi bytter. Bytter vi for ofte er responsen god men overhead høyt. Bytter vi sjelden er overhead lavt men responsen treig. ƒfaktisk cpu-andel viser hvordan tida faktisk fordeles mellom prosesser over et tidsrom — det er sluttproduktet av schedulerens valg.

Privilegerte instruksjoner og beskyttelse

En siste brikke i LDE er at noen CPU-instruksjoner bare er lov i kernel mode. En privilegert instruksjon instruksjon kan være: oppsett av trap-tabellen, endring av CPU-modus, direkte I/O til portregister, eller å redigere sidetabell-pekeren. Hvis et brukermodus-program prøver, utløser CPU-en en general protection fault — som er en trap, som lander i kjernen, som typisk dreper programmet med SIGSEGV eller liknende.

Det er denne kombinasjonen — to modi, kontrollerte traps, timer-interrupts, trap-tabell, privilegerte instruksjoner — som lar OS-et være både rask og trygg. Programmer får nesten full CPU-tid uten innblanding, men aldri muligheten til å miste kontrollen for godt. Maskinvaren er på OS-ets side.

Hvorfor "limited"?

Navnet er presist. Vi vil ha direct execution — la programmer kjøre fritt på CPU-en — for fart. Men vi vil begrense hva de kan gjøre, for sikkerhet og rettferdighet. Limited Direct Execution er prinsippet. Trap, timer-interrupt, context switch og privilegerte instruksjoner er mekanikken som realiserer det.

Når du i kap 4 møter konkrete scheduling-algoritmer — FIFO, SJF, MLFQ, CFS — er det denne mekanikken som ligger under. Algoritmene velger hvem som får kjøre; LDE velger hvordan kjernen får kontrollen tilbake for å gjennomføre valget.

En liten oppsummering for eksamen

Kort sjekkliste: hvordan får OS-et CPU-en tilbake fra en pågående prosess? Tre måter. Én — prosessen gjør et systemkall (frivillig trap). To — prosessen gjør noe ulovlig, som å lese fra en ugyldig adresse (ufrivillig trap, page fault). Tre — timeren tikker og avbryter (asynkront avbrudd). I alle tre tilfellene lander vi i en handler oppført i trap-tabellen, kjernen tar over, og bestemmer hva som skjer videre.

Det er disse tre veiene som garanterer at OS-et aldri mister kontrollen for godt. Resten av faget bygger videre på dette grunnlaget.