Visual walkthrough — Page tables and multi-level paging

5.4.13 · D2 · Hardware › Memory Hierarchy & Caches › Page tables and multi-level paging

Prerequisites jinpe hum thoda rely karte hain: Virtual Memory, Bit Manipulation and Masking, Address Space Layout. End mein speed fix TLB and Translation Caching aur Cache Memory Basics se connect hota hai.

Step 1 — Ek address bits ki ek row hai, kuch nahi

KYA. Ek virtual address woh number hai jo ek program hardware ko deta hai jab woh kehta hai "yahan se padho." 32-bit machine par woh number exactly 32 binary digits hota hai — 32 boxes, har ek mein 0 ya 1. Koi jadoo nahi: yeh $0$ aur $2^{32}-1$ ke beech ek poora number hai.

KYU yahan se shuru karein. Jo kuch bhi aage aata hai woh sirf is bit row ko groups mein slice karna aur har group ko ek chhota number maanna hai. Agar tum address ko bits ki row ke roop mein dekhte ho, toh baaki sab bookkeeping hai.

PICTURE. Neeche, 32 boxes left (high bits, sabse zyada value wale) se right (low bits, sabse kam value wale) tak drawn hain. Example address hai 0x00402ABC.

Step 2 — Bottom bits kyun special hain: the page

KYA. Memory ko equal blocks mein chop kiya jaata hai jinhein pages kehte hain. Ek common size hai 4 KiB $=4096$ bytes $=2^{12}$ bytes. Page size ko $P$ kahein, toh yahan $P=2^{12}$.

KYU yahi exact idea. Poochho: ek single page ke andar ek particular byte ko name karne ke liye mujhe kitne bits chahiye? Ek page $P$ consecutive bytes hold karta hai, $0$ se $P-1$ tak numbered. $P$ alag positions tak count karne ke liye tumhe chahiye

$p=\underset{\text{"kitne bits se }P\text{ cheezein name ho sakti hain"}}{\underbrace{{\log }_{2}P}}$

Yahan $p={\log }_2{2}^{12}=12$. Woh bottom $12$ bits offset hain: yeh batate hain ki page ke andar byte kahan baith'ta hai. Tool ${\log }_2$ isliye aata hai kyunki har extra bit se naam ki ja sakne wali cheezein double ho jaati hain — aur doubling exactly wahi hai jo ${\log }_2$ invert karta hai. Koi aur function nahi hai jo "$P$ items ke liye kitne bits" ka jawab deta ho.

PICTURE. Wohi 32 boxes, ab low $12$ ko coral mein alag kar diya gaya hai. Woh coral chunk offset hai; yeh translation ke through bina chheday jaayega.

Step 3 — Address ka baaki hissa batata hai ki kaun sa page hai

KYA. Offset ke upar sab kuch virtual page number (VPN) hai. $V=32$ bit address aur $p=12$ offset bits ke saath, VPN hai

$v=V-p=32-12=20\text{ bits.}$

KYU. Humein sirf translate karna hota hai ki ek byte kis page mein rehta hai, kabhi page ke andar kahan nahi (Step 4 batata hai kyun). Toh hum top $v$ bits peel off karte hain aur unhe ek number maante hain, VPN:

$\text{VPN}=\lfloor \frac{\text{addr}}{P}\rfloor$

• $\frac{\text{addr}}{P}$ — page size se divide karo; yeh offset ko throw away karta hai.
• $\lfloor \cdot \rfloor$ — floor (round down) koi bhi fractional leftover discard karta hai, ek clean poora page number chodke.

PICTURE. Lavender = 20-bit VPN, coral = 12-bit offset. Do clean fields.

0x00402ABC ke liye, top 20 bits 0x00402 hain.

Step 4 — Offset kabhi kyun nahi badlta

KYA. Translation ke dauran VPN ko ek physical frame number (PFN) se replace kiya jaata hai, lekin offset verbatim copy hota hai.

KYU. Ek frame physical RAM ka ek block hai jo page ke same size $P$ ka hota hai. Kyunki woh same size ke hain, ek page ke andar byte number $k$, uske frame ke andar byte number $k$ par land karta hai — "$k$" nahi badlta. Translation sirf decide karta hai kaun sa frame, yani woh sirf top bits rewrite karta hai.

PICTURE. Ek page (lavender box, bytes $0\dots P-1$) ek frame (mint box) par placed hai. Coral offset arrow dono mein same slot ko point karta hai.

Step 5 — Ek flat table enormous hogi

KYA. Sabse simple translator ek giant array hai: entry number $\text{VPN}$ us page ka frame number hold karta hai. $v=20$ VPN bits ke saath iske liye $2^{20}\approx 1,048,576$ entries chahiye.

KYU yeh dikhao. Tree ko justify karne ke liye, humein pehle dard feel karna hoga. Har entry (ek PTE) lagbhag $4$ bytes ki hai:

$2^{20}\times 4\text{B}=4\text{MiB per process.}$

Un million entries mein se zyaadatar kisi cheez ki taraf point nahi karte — ek program sirf kuch pages hi touch karta hai. Yeh wasted RAM hai, aur 64-bit machines par ($2^{52}$ entries) flat table impossible hai.

PICTURE. Ek tall table jisme kuch used (lavender) rows hain aur empty (grey) rows ka ek vast sea.

Step 6 — VPN ko do indexes mein split karo: the tree

KYA. 20-bit VPN ko do 10-bit fields mein kato. Ab address mein teen fields hain:

$\text{addr}=[\underset{10\text{ bits}}{\underbrace{i_1}}\Vert \underset{10\text{ bits}}{\underbrace{i_2}}\Vert \underset{12\text{ bits}}{\underbrace{\text{offset}}}]$

• $i_1$ — outer index: top table (the "directory") mein ek row pick karta hai.
• $i_2$ — inner index: directory jis second-level table ki taraf point karta hai usmein ek row pick karta hai.
• $\text{offset}$ — Step 2 se unchanged.

KYU 10 / 10. $2^{10}=1024$ entries $\times 4$ bytes $=4$ KiB — har table exactly ek page hai. Aur sabse important: agar poora 1024-page region unused hai, toh uska inner table simply kabhi allocate hi nahi hota. Hum sirf un branches par memory kharch karte hain jo actually use hoti hain — yahi poora saving hai.

PICTURE. 32 boxes teen coloured fields mein regroup hue, 0x00402 decode hota hai $i_1=1$, $i_2=2$.

Step 7 — The walk: pointers follow karo frame tak

KYA. Ek base register (CR3 x86 par, top table ka physical address hold karta hai) se shuru karke, hum tree ke neeche hop karte hain:

KYU do reads. Har level RAM mein rehta hai, isliye har hop ek memory access hai. Do levels ⇒ do reads data touch karne se pehle — space bachane ki kimat (Step 9 speed fix karta hai).

PICTURE. CR3 → top table row 1 → inner table row 2 → frame 0x0009C, phir coral offset 0xABC end mein snap ho jaata hai.

Worked numbers: PFN $=\text{0x0009C}$, toh $\text{PA}=(\text{0x0009C}\ll 12)|\text{0xABC}=\text{0x0009C000}|\text{0xABC}=\text{0x0009CABC}.$

Step 8 — Degenerate case: ek unused branch

KYA. Maan lo $\text{L1}[i_1]$ ka valid flag = 0 hai — directory entry kisi cheez ki taraf point nahi karti.

KYU yeh matter karta hai. Yeh address space ke zyaadatar hisse ke liye normal case hai, aur exactly yahi woh tarika hai jisse tree memory bachata hai. Agar outer entry invalid hai, toh koi inner table hai hi nahi — walk turant ruk jaata hai aur hardware ek page fault raise karta hai (dekho Page Faults and Demand Paging). Humne un pages ke liye inner table par 4 KiB kabhi waste nahi kiya jo koi use hi nahi karta.

PICTURE. Directory mein ek green (valid) row aur 1023 grey (invalid) rows; ek grey row ka arrow "no table — fault" marker mein dead-end ho jaata hai.

Step 9 — Woh speed jo humne khoyi, aur TLB use wapas kaise deta hai

KYA. Walk ne humen per translation $n$ memory reads cost karaaye ($n=2$ yahan). TLB ek tiny, fast cache hai jo recent $\text{VPN}\to \text{PFN}$ results yaad rakhta hai.

KYU. Ek hit par, poora walk skip ho jaata hai — translation roughly ek cycle hoti hai. Ek miss par, hum walk karte hain, phir answer store karte hain. Average cost:

$t_{\text{avg}}=t_{\text{TLB}}+(\text{miss rate})\times (\text{walk cost})$

• $t_{\text{TLB}}$ — fast lookup ki cost (hamesha pay hoti hai).
• $\text{miss rate}$ — accesses ka fraction jo TLB mein nahi mila.
• $\text{walk cost}$ — $n$ memory reads, sirf miss par pay hote hain.

Kyunki real programs baar baar same few pages visit karte hain, miss rate tiny hoti hai — isliye tree apni memory savings rakhta hai aur flat-table speed nearly recover kar leta hai. Zyaada detail TLB and Translation Caching mein.

PICTURE. VPN se do paths: green "TLB hit → PFN" fast lane; longer lavender "TLB miss → walk the tree → fill TLB" path.

Ek-picture summary

Upar ka sab kuch ek single diagram mein: 32-bit address $i_1\Vert i_2\Vert \text{offset}$ mein split hota hai; $i_1$ directory walk karta hai, $i_2$ inner table walk karta hai, PFN untouched offset ke saath join hoke RAM mein ek byte name karta hai; TLB poori walk ko shortcut karta hai.

Active Recall