Virtuelt minne, page faults og sideerstatning

Når RAM ikke strekker til

Operativsystemet later som hver prosess har sitt eget, sammenhengende adresseområde — ofte mye større enn den fysiske RAM-en. Det fungerer fordi bare en aktiv del av adresseområdet ligger i minnet til enhver tid; resten bor på disk i swap. Når prosessen refererer til en adresse hvis side ikke er i RAM, oppstår en page fault. CPU-en feller en exception, og OS-et må håndtere det: finne siden på disk, frigjøre en ramme (kanskje skrive en annen tilbake til swap først), oppdatere pagetabellen, og restarte instruksjonen som ble avbrutt.

Mekanismen — å mappe virtuelle adresser via en pagetabell — er én ting. Policyen — hvilken side som må vike når en ny må inn — er noe helt annet, og det er der ytelsen står og faller. Vi kaller policy-laget replacement policy, og resten av kapittelet handler om hvordan vi bedømmer om en policy er god.

Hva koster en page fault?

Et vanlig RAM-oppslag tar i størrelsesorden 100 nanosekunder. En lesning fra SSD tar ~100 mikrosekunder, fra magnetisk disk flere millisekunder. Forskjellen er fire–fem størrelsesordener — som å sammenligne et tastetrykk med en flytur til en annen verdensdel.

Vi måler kostnaden med ƒeffektiv tilgangstid med page faults. Hvis bare 1 av 1000 oppslag forårsaker fault, og et fault koster 10 ms, blir forventet tilgangstid (0,999 · 100 ns) + (0,001 · 10 ms) ≈ 10 µs — hundre ganger tregere enn et rent RAM-oppslag. En miss-rate på en promille ødelegger snittet. Det er hele grunnen til at policy betyr noe.

Den samme idéen, med mer typiske variabelnavn, ser vi som ƒeffektiv minnetilgangstid (emat). I dag rapporterer profil-verktøy oftest tallet som ƒhit ratio og miss ratio fordi det er enklere å snakke om en cache som har 99 % hit enn å huske at miss-raten er 1 %. Begge måler det samme.

OPTIMAL som målestokk

Den teoretisk beste policyen — optimal (min, belady), også kjent som Belady-MIN — kaster ut den siden som vil bli brukt sist i fremtiden. Den krever fremtidsviten, så vi kan ikke implementere den i ekte systemer. Men den er fantastisk som referanse: hvor langt fra optimum er FIFO eller LRU på en gitt referanse-strøm?

OPTIMAL er bevist å minimere antall page faults for et gitt antall rammer. Når en ekte policy ligger i nærheten, vet vi at det er lite mer å vinne på smartere bokføring. Klassisk eksempel: ref-strømmen 1,2,3,4,1,2,5,1,2,3,4,5 på 3 rammer. OPTIMAL gir 7 faults; FIFO gir 9; LRU gir 10. Forskjellen virker liten på papiret, men i tette løkker over mange millioner referanser blir den målbar — og fault-kostnaden er stor nok at en prosent gjør forskjell.

FIFO, LRU og klokke

fifo page replacement er enklest å forklare: en kø, eldste rad må ut. Lett å implementere, men leverer kontraintuitive resultater. belady-anomali viser hvordan flere rammer kan gi flere page faults — fordi FIFO ikke har «stack-egenskap», en garanti om at innholdet i en mindre cache alltid er en undermengde av innholdet i en større. Det er en advarsel om at intuisjon ikke holder her.

lru (least recently used) bygger på antakelsen om temporal locality: en side som ble brukt nylig, blir antakelig brukt igjen. Ekte LRU krever at hver tilgang oppdaterer et tidsstempel eller flytter siden bakerst i en lenkeliste — for dyrt i praksis, fordi hver minnetilgang ellers er bare en CPU-instruksjon, ikke en datastruktur-operasjon.

clock algorithm er den vanlige approksimasjonen. Sidene står i en sirkel; en pekepinn vandrer rundt. Hver side har en referenced-bit som hardwaren setter ved hver tilgang. Pekepinnen finner en side med bit = 0 og kaster den; sider med bit = 1 får bitten nullstilt og en ny sjanse rundt. Resultatet er nesten LRU, til en brøkdel av kostnaden. Forbedringer som enhanced clock tar også med dirty-biten, så modifiserte sider får ekstra sjanse — de er dyrere å kaste, siden de må skrives tilbake først.

Working set og thrashing

ƒworking-set-idé fanger hvor mye fysisk minne en prosess egentlig trenger akkurat nå. Hvis programmet itererer over et 200 MB array, er working set 200 MB. Gir du det 50 MB RAM, faulter du på nesten hver iterasjon — policyen er smart, men jobben er umulig. Det er ikke noe en bedre algoritme kan fikse.

Når flere prosesser konkurrerer og ƒfault pressure holder, ender systemet i thrashing: CPU-en venter konstant på disk, brukbart arbeid stuper, mens disk-aktivitet og swap-bruk når taket. Symptomene er klare: lav CPU-utnyttelse + skyhøy I/O = thrashing. Løsningen er ofte ikke smartere algoritmer, men færre samtidige prosesser eller mer RAM. Mange OS-er har en swap-daemon som suspenderer hele prosesser når thrashing detekteres og restarter dem når trykket faller — bedre at noen sover enn at alle krabber.

Pagetabell og TLB

Selve oppslaget — virtuell adresse til fysisk ramme — gjøres av maskinvaren via en pagetabell. Pagetabellen er stor: med 4 KB sider og 64-bits adresser har vi i prinsippet 2^52 sider per prosess. Derfor er pagetabellen seksjonert og lagret i et flernivå-tre, der bare aktive grener faktisk er allokert.

Hvert oppslag i pagetabellen er flere minneaksesser i seg selv. For å unngå at hver eneste instruksjon koster fire-fem ekstra RAM-oppslag, har CPU-en en Translation Lookaside Buffer (TLB) — en liten cache med 64–1024 oppføringer som holder de varmeste virtuelle-til-fysisk-mappingene. Hit i TLB-en koster én CPU-syklus; miss koster oppslag i hele tre-strukturen.

TLB-press er den skjulte ytelseskostnaden i moderne systemer. Hopp gjennom store datasett (databaser, dypelæring) tømmer TLB-en og gir mange flere referanser per ramme. Det er hovedgrunnen til at huge pages finnes: 2 MB sider gir 512x færre TLB-oppføringer per gigabyte minne.

Demand paging og sidestørrelse

Moderne OS bruker demand paging: en side lastes fra disk først når noen faktisk leser eller skriver til den. Programstart blir raskere, og minne brukes bare på det som faktisk trengs. Trade-offen er at de første aksessene betaler fault-kostnaden. Noen systemer prefetcher naboer for å amortisere — hvis du faulter på side 7, last også 8 og 9, fordi sjansen er stor for at de trengs snart.

Valg av sidestørrelse er et klassisk kompromiss. Større sider gir færre pagetable-oppføringer, mindre TLB-trykk og mer effektive disk-lesinger per fault, men de gir også mer intern fragmentering: en allokering på 1 byte spiser fortsatt en hel side. Mindre sider gir presis bokføring, men flere page faults og en større pagetabell. 4 KB har vunnet i de fleste systemer fordi det balanserer disse. Linux og Windows støtter også huge pages (2 MB / 1 GB) for spesielle arbeidsbelastninger som databaser og hypervisorer der TLB-trykket dominerer. ƒtrade-off i sidestørrelse oppsummerer regelen.

page hit / page miss i praksis

Et fault er ikke alltid svindyrt. Hvis siden ligger i en free-list som ikke er gjenbrukt enda, kan OS-et bare mappe den tilbake uten disk-I/O — det kalles en soft fault eller minor fault. Hvis siden må hentes fra disk eller fra swap, er det en hard fault eller major fault. Profil-verktøy som vmstat og perf rapporterer begge — vær obs på forskjellen før du bekymrer deg over fault-tallene. Mange tusen minor faults per sekund er normalt under tunge programstarter; flere hundre major faults per sekund er et alvorlig tegn.

Det praktiske bildet: VM-policy er en kjede av kompromisser. Maskinvaren leverer referenced- og dirty-biter; OS-et bruker dem til å approksimere LRU; demand paging utsetter kostnaden til den ikke kan utsettes lenger; working-set-modellen forteller deg om systemet er i balanse. Hver enkelt brikke er triviell, men summen gir det moderne, virtuelle minnet — billig nok per ramme til at applikasjoner kan allokere som om RAM var uendelig.