Paging, TLB og sidetabeller

Hvorfor paging vant

Segmentering ga oss fleksibilitet på bekostning av ekstern fragmentering. Paging fjerner problemet ved å bruke faste blokker overalt. Virtuelt minne deles i side (page) av lik størrelse (typisk 4 KiB), og fysisk minne deles i ramme (frame) av samme størrelse. En side kan plasseres i hvilken som helst ledig ramme, og scheduleren trenger aldri å lete etter et sammenhengende område stort nok.

Prisen er at hver virtuell adresse må slås opp i en sidetabell før minneaksess.

Uten støtte i maskinvare ville det vært katastrofalt tregt. Med tlb og smarte sidetabell-strukturer er det praktisk talt gratis.

Adresse-mekanikken

En virtuell adresse deles i to: vpn på toppen og offset nederst.

ƒantall offset-biter bestemmer hvor mange bits som går til offset, og resten blir VPN — ƒantall vpn-biter.

Eksempel: 32-bits virtuell adresse, sidestørrelse 4 KiB. log₂(4096) = 12, så de nederste 12 bitene er offset, de øverste 20 bitene er VPN. Det gir 2²⁰ = ca 1 million sider per prosess.

Oversettelsen er like enkel: slå opp VPN i sidetabellen, hent ramme-nummeret (PFN), og konkateneres med offset. Den fysiske adressen blir PFN || offset. Offset beholdes uendret fordi sider og rammer har samme størrelse — der bytte 17 i siden er på fysisk byte 17 i rammen.

PTE — det som ligger i hver sidetabell-rad

Hver oppføring i sidetabellen er en pte (Page Table Entry). Den inneholder mer enn bare PFN. pte (page table entry) har typisk:

- Frame number (PFN) — hvilken fysisk ramme siden ligger i. - valid-bit — er denne sidekartleggingen i bruk? En ugyldig PTE betyr at adressen ikke er allokert; aksess gir page fault. - Present-bit — ligger siden i RAM nå, eller er den swappet til disk? - Protection-bits — read, write, execute. Lar OS markere kode som ikke-skrivbar og data som ikke-kjørbar. - Accessed-bit / dirty-bit — settes av MMU ved aksess/modifikasjon. Brukes av OS for å velge hvilke sider som skal swappes ut. - User/kernel-bit — kan kun kjernen aksessere denne siden, eller også brukerprogrammer?

TLB — uten denne dør paging

Naivt krever paging to minneaksesser per logisk lesing: én for å hente PTE fra sidetabellen, og én for selve dataene. Det halverer ytelsen. Løsningen er en hardware-cache i MMU-en — tlb, Translation Lookaside Buffer.

TLB holder de siste ti-talls til hundrevis av PTE-ene. Ved en aksess sjekker MMU TLB først; ved hit (vanligvis 95-99 % av aksessene) trengs ingen ekstra minneaksess. Ved miss må sidetabellen leses normalt.

Effekten kan måles med ƒeffektiv tilgangstid med tlb. La α være TLB hit-rate. Ved hit: én aksess for data + TLB-tid. Ved miss: én aksess for PTE + én for data + TLB-tid. Med α = 0,98, TTLB = 1 ns og TM = 100 ns blir EAT ≈ 103 ns — bare 3 % over rå minneaksess. Med α = 0,5 blir EAT 151 ns — 51 % overhead. Programmer med god spatial locality (de bruker sider om og om igjen) får høy hit-rate; tilfeldige aksessmønstre dreper TLB-en.

Lineær sidetabell — ufleksibelt

Den enkleste sidetabellen er linear page table: én entry per virtuell side, lagt etter hverandre i RAM. Slå opp med VPN som indeks, ferdig.

Problemet er størrelsen. 32-bits adresseområde med 4 KiB sider og 4-byte PTE-er gir 2²⁰ × 4 = 4 MiB per prosess. Med 100 prosesser blir det 400 MiB sidetabell-data — bare for tabellene. På 64-bits systemer er det helt umulig: 2⁵² × 8 = 32 PiB per prosess.

Det meste av adresseområdet er ubrukt. Mellom heap-toppen og stack-bunnen er det enorme tomme områder, men en lineær tabell må ha en entry der likevel. Alle disse entry-ene er bare valid-bit = 0, men de tar plass.

Flernivå-sidetabell — sparing

flernivå-sidetabell løser dette ved å gjøre sidetabellen til et tre. multi-level page table deler VPN i flere chunks, hver indekserer ett nivå. På toppnivå er det en page directory (sidekatalog) med entries som peker på neste-nivås sidekataloger, og bare bunn-nivåene har faktiske PTE-er. Tomme områder representeres ved at toppnivå-entry er ugyldig — da slipper vi å allokere noen av de nedre tabellene.

Eksempel: 32-bit adresseområde, 2-nivå med 10+10+12 bits. En prosess som bare bruker første og siste 4 MiB trenger toppnivå (4 KiB) og to bunn-nivå-tabeller (2 × 4 KiB) — 12 KiB totalt, mot 4 MiB for lineær.

Sv39 — RISC-V i praksis

xv6-riscv bruker sv39, RISC-V sin 39-bits virtuelle adressering. Av 64 adresse-bits brukes 39 (resten må sign-extendes). De 12 nederste er offset (4 KiB sider), og de øvrige 27 er VPN delt på tre nivåer á 9 bits — utledet av ƒantall pte per nivå (3-nivå paging): 4096 / 8 = 512 entries per katalog, log₂(512) = 9 bits per nivå.

Oversettelsen følger ƒhex-translation 3-nivå (sv39). Plukk de 12 nederste bitene som offset. De neste 9 indekserer L1-katalogen, de neste 9 L2, de neste 9 L3. Slå opp top-PTE i satp-registeret, gå nedover tre nivåer, og PFN i bunnen kombinert med offset gir fysisk adresse. Tre minneaksesser per oversettelse — som er nettopp grunnen til at TLB er obligatorisk i praksis.

Invertert sidetabell — annen retning

inverted page table snur problemet på hodet: i stedet for én tabell per prosess, én entry per fysisk ramme — på hele systemet. Hver entry sier «hvilken prosess + hvilken VPN bor i denne rammen». Totalt minneforbruk er O(fysisk RAM), ikke O(virtuelt × prosesser).

Ulempen er oppslag. Vi kan ikke bare indeksere — vi må søke gjennom tabellen, eller bruke en hash. I praksis sjeldent brukt utenom på systemer med veldig mye virtuelt og lite fysisk minne. Sharing av sider mellom prosesser blir også tungvint: én entry kan ikke samtidig representere to prosesser.

Page fault — når PTE er ugyldig

Hva skjer ved aksess på en side som ikke ligger i RAM? MMU finner PTE-en, ser at valid- eller present-bit er 0, og utløser en page fault-trap. Kjernen tar over: er adressen lovlig (innenfor prosessens adresseområde) men siden er swappet til disk, leser kjernen den inn til en ledig ramme, oppdaterer PTE-en, og returnerer. Aksessen prøves på nytt, og denne gangen lykkes den.

Hvis adressen ikke er lovlig — typisk null-pointer-dereferanse eller stack-overflow — sender kjernen et SIGSEGV-signal til prosessen, som vanligvis dør. Page faults har altså to roller: de bygger broen til disk-baserte minne (swap, mmap), og de fanger ulovlige aksesser. Begge er essensielle for at virtuelt minne skal fungere.

Det finnes en tredje variant — minor faults — der siden faktisk ligger i RAM, men ikke er mappet i den aktuelle prosessens sidetabell ennå. Vanlig ved fork: kjernen markerer alle delte sider som copy-on-write, og første skriving utløser en minor fault som kopierer siden. Det er billig (ingen disk-I/O), men det skjer ofte og er målbart i ytelsesprofileringer.

Hva du tar med deg

Lærepoenget er at det ikke finnes én optimal sidetabell-struktur. Lineær er enkel og rask, men slukker minne. Flernivå sparer minne mot ekstra oppslag. Invertert minimerer minne, men ofrer oppslagstid. Valget avhenger av hvor mye minne du har, hvor stort adresseområdet er, og hvor godt TLB-en din skjuler oppslagskostnaden.

Tre prinsipper holder seg uansett valg. TLB er essensielt — uten den kollapser ytelsen, fordi hver minneaksess plutselig krever to (eller tre, eller fire) i stedet for én. Sider må være store nok til at sidetabellen blir håndterbar, men små nok til at intern fragmentering ikke ødelegger. 4 KiB har stått som de facto-standard i tre tiår, og det er ingen tilfeldighet — det er en god kompromiss for typiske aksessmønstre, selv om Linux nå støtter «huge pages» på 2 MiB og 1 GiB for spesielle bruksområder. Og PTE-formatet må romme nok metadata til at OS kan implementere både beskyttelse, swapping og deling — alle tre er bygget oppå PTE-bitene, og uten dem ville virtuelt minne vært en mye fattigere abstraksjon.