Begreper & formler
Alle nøkkelbegrepene og formlene fra Paging, TLB og sidetabeller, 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.
Virtual Page Number; delen av en virtuell adresse som identifiserer hvilken side det er snakk om.
Page Table Entry; metadata som forteller hvor siden ligger og hvilke rettigheter den har.
Translation Lookaside Buffer; en liten, rask cache for nylige adresseoversettelser.
Hierarkisk oppdeling av sidetabellen for å unngå å allokere store tabeller for ubrukte deler av adresseområdet.
Bit som forteller om en side er gyldig tilordnet prosessen eller ikke.
RISC-V virtuell adressering brukt i xv6-riscv: 39 bits virtuell adresse av 64. 27 bits page index (3 nivåer × 9 bits) + 12 bits offset. Adresserbart minne: 2^39 = 512 GB.
En side full av page table entries. I flernivå-paging peker entry på neste nivå sin sidekatalog, helt til siste nivå som peker på den fysiske rammen.
Sidetabell delt i hierarkiske nivåer, der hvert nivå indekseres av en bit-bit av VPN. Sparer minne fordi tomme grener kan utelates (ikke alle nivå-2/3-tabeller må allokeres).
Klassisk enkelnivå-sidetabell: én entry per virtuell side. Enkel oppslag, men kan bli enormt stor for store adresseområder.
Én entry per fysisk ramme i hele systemet (ikke per prosess). Mindre minnebruk totalt, men dyrere oppslag (krever søk/hash) og vanskelig å dele sider mellom prosesser.
Datastruktur som mapper VPN → PFN. Inneholder: frame number, valid-bit, present-bit, protection-bits (R/W/X), accessed/dirty-bits, user/kernel-bit.
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
Antall offset-biter
Hvis sidestørrelsen er 4 KiB, blir offset-delen 12 biter.
Antall VPN-biter
Resten av adressen brukes til å identifisere hvilken virtuell side vi er i.
Effektiv tilgangstid med TLB
Ved TLB-hit trengs én minneaksess for data. Ved miss må vi også lese sidetabellen.
Antall offset-bits
4 KB side → log2(4096) = 12 bits offset. 16 KB → 14 bits. 2 KB → 11 bits. Resten av virtuell adresse er VPN.
Antall PTE per nivå (3-nivå paging)
Med 4 KB side og 8 B PTE: 4096/8 = 512 entries per nivå → 9 bits per nivå. 3 nivåer × 9 = 27 bits VPN, samme som xv6/Sv39.
Hex-translation 3-nivå (Sv39)
Plukk de 12 LSB som offset, så 9-bits chunks oppover for L1, L2, L3. Slå opp L3→L2→L1, ta frame fra L1-PTE, konkateneres med offset.
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Beregne hvor mange offset- og VPN-bits en virtuell adresse har gitt sidestørrelse
- 02Forklare hva en PTE inneholder og hvordan valid-bit, beskyttelses-bits og frame-nummer brukes
- 03Beskrive hvordan TLB påvirker effektiv tilgangstid og hvorfor paging ville vært ubrukelig uten den
- 04Sammenligne lineær, flernivå og invertert sidetabell med tanke på minnebruk og oppslagskostnad