Worked examples — Page tables and multi-level paging

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

Yeh page parent topic ko concrete numbers ke through drill karta hai. Hum har tarah ka input cover karte hain jo translation machinery face kar sakti hai: normal addresses, exactly page boundary par baithne wale addresses, ek page ka pehla aur aakhri byte, invalid (unmapped) entries, single-level vs multi-level walks, ek 64-bit monster, ek word problem, aur ek exam twist. Prerequisites jinpar hum rely karte hain: Virtual Memory, Bit Manipulation and Masking, aur TLB and Translation Caching.

Scenario matrix

Yahan har cell ek alag situation hai jo reader ko survive karni hai. Neeche har example ko us cell(s) ke saath tag kiya gaya hai jo woh cover karta hai.

Setup jo hum reuse karte hain

Jab tak koi problem kuch aur na kahe: 32-bit virtual addresses ($V=32$), page size $P=4\text{ KiB}=2^{12}$ bytes, toh offset bits $p={\log }_2{2}^{12}=12$, aur VPN bits $v=32-12=20$. Two-level split hai 10 / 10 / 12 (outer index $i_1$ = 10 bits, inner index $i_2$ = 10 bits, offset = 12 bits).

Figure s01 is chop ko ek 32-bit address par apply hote dikhata hai: wahi knife-cut jo hum har example mein, haath se, perform karenge neeche. Orange offset field ko right par notice karo — yeh woh slice hai jo Examples A–I mein untranslated ride karti hai.

Example A — Normal single-level translation (Cell A)

Steps.

1. offset $=\text{0x00003ABC}\&\text{0xFFF}=\text{0xABC}$. Yeh step kyun? Low 12 bits page ke andar ek byte naam dete hain; yeh untranslated ride karte hain.
2. VPN $=\text{0x00003ABC}\gg 12=\text{0x00003}=3$. Yeh step kyun? Baaki bache high bits batate hain kaunsa page — table mein key.
3. table[3] look up karo → PFN = 0x00042, valid, toh translation succeed hoti hai. Yeh step kyun? Array position VPN hi hai; stored value frame hai.
4. PA $=(\text{PFN}\ll 12)|\text{offset}=(\text{0x00042}\ll 12)|\text{0xABC}=\text{0x00042ABC}$. Yeh step kyun? Reassemble karo: high bits mein frame number, low bits mein original offset.

Verify: low teen hex digits ABC unchanged hain (offset untouched — exactly parent ka rule). Sirf page portion 003 → 042 move hua. $0\text{x}42\times 4096+0\text{xABC}=270336+2748=273084=\text{0x42ABC}$. ✓

Example B — Offset zero, page boundary (Cell B, F-flavour)

Steps.

1. offset $=\text{0x7000}\&\text{0xFFF}=\text{0x000}=0$. Yeh step kyun? 0x7000 0x1000 = 4096 = $P$ ka multiple hai, toh yeh exactly ek page ke start par baitha hai. Offset 0 matlab "frame ka byte 0."
2. VPN $=\text{0x7000}\gg 12=\text{0x7}=7$. Yeh step kyun? Low 12 bits discard karne par page number milta hai — exactly wahi key jisse hum table index karte hain, bilkul Example A ki tarah.
3. table[7] → PFN 0x00100 look up karo. Yeh step kyun? Array position 7 VPN hai; stored value 0x100 woh frame hai jisme woh page rehta hai.
4. PA $=(\text{0x00100}\ll 12)|0=\text{0x00100000}$. Yeh step kyun? Reassemble karo: PFN ko high bits mein slide karo, offset (yahan 0) ko low bits mein daalo.

Verify: ek boundary address ek boundary address par map hoti hai — PA bhi 000 par khatam hoti hai. $0\text{x}100\times 4096=1048576=\text{0x100000}$. ✓ Yeh us frame ka sabse chhota address hai.

Example C — Page ka last byte, offset = P−1 (Cell C)

Steps.

1. offset $=\text{0x7FFF}\&\text{0xFFF}=\text{0xFFF}=4095=P-1$. Yeh step kyun? 0xFFF woh sabse badi value hai jo 12 bits hold kar sakti hai — page ka bilkul aakhri byte.
2. VPN $=\text{0x7FFF}\gg 12=\text{0x7}=7$. Yeh step kyun? Crucial: bhale hi address bada lagta ho, 0x7FFF tak sab kuch page 7 mein hi belong karta hai. Agla byte, 0x8000, page 8 ka pehla byte hai.
3. table[7] → PFN 0x00100. Yeh step kyun? Example B jaisa hi page number 7, toh yeh same row index karta hai aur same frame deta hai — maximum offset ne yeh nahi badla ki hum kaunse page mein hain.
4. PA $=(\text{0x00100}\ll 12)|\text{0xFFF}=\text{0x00100FFF}$. Yeh step kyun? Reassemble karo: frame Example B se unchanged hai; sirf offset (ab 0xFFF) low bits mein ride karta hai, hume frame ka last byte deta hai.

Verify: Example B (0x7000) aur Example C (0x7FFF) PFN 0x100 share karte hain; unke physical addresses sirf offset 000 vs FFF mein differ karte hain. Dono frame 0x100 ke andar rehte hain. Ek aur byte add karo (0x8000) aur VPN 8 ban jaata hai — alag table row. ✓ Yahi woh off-by-one hai jo logon ko trap karta hai: 0x8000 page 7 mein nahi hai.

Example D — Two-level walk, sab fields non-zero (Cell D)

Steps.

1. offset $=\text{0x00402ABC}\&\text{0xFFF}=\text{0xABC}$. Yeh step kyun? Low 12 bits, hamesha ki tarah.
2. VPN $=\text{0x00402ABC}\gg 12=\text{0x00402}=1026$. Yeh step kyun? Ab hamare paas 20-bit page number hai jise hume dobara split karna hai.
3. inner index $i_2=(\text{VPN}\gg 0)\&\text{0x3FF}=1026\&1023=2$. Yeh step kyun? Inner index sabse neechi VPN slice hai, toh shift $s=0$ (iske neeche kuch nahi); 0x3FF uske 10 bits rakhta hai.
4. outer index $i_1=(\text{VPN}\gg 10)\&\text{0x3FF}=(1026\gg 10)\&1023=1$. Yeh step kyun? Outer index 10 inner bits ke upar baitha hai, toh pehle $s=10$ shift karo, phir 10 bits rakho — VPN ka high slice.
5. Walk karo: L1[1] padho → L2 base milta hai; L2[2] padho → PFN 0x0009C. Yeh step kyun? Ek level per do memory accesses, parent ke cost formula ($n$ levels ke liye $n$ reads) se match karta hai.
6. PA $=(\text{0x0009C}\ll 12)|\text{0xABC}=\text{0x0009CABC}$. Yeh step kyun? Reassemble karo, bilkul single-level case ki tarah: final-level PFN high bits mein slide hota hai, untranslated offset low bits mein girta hai — tree ne sirf yeh badla ki humne PFN kaise dhundha, address banane ka tarika nahi.

Verify: dono indices se VPN reassemble karo: $(i_1\ll 10)|i_2=(1\ll 10)|2=1024+2=1026=\text{0x402}$. ✓ Parent note ke worked walk se exactly match karta hai.

Figure s02 is exact walk ko ek tree ki tarah draw karta hai: L1[1] (plum) humein L2 base deta hai, L2[2] (teal) humein frame 0x9C (orange) deta hai, aur offset 0xABC us frame ke andar byte select karta hai. Dono arrows follow karo — har ek ek memory read hai.

Example E — Invalid PTE: translation fail hoti hai kisi bhi level par (Cell E)

Steps (Case E1 — top-level fault).

1. offset $=\text{0x00801000}\&\text{0xFFF}=0$. Yeh step kyun? Har example ki tarah same pehla move: low 12 bits peel karo taaki baaki ek pure page number ho, chahe woh mapped nikle ya nahi.
2. VPN $=\text{0x00801000}\gg 12=\text{0x00801}=2049$. Yeh step kyun? Indices compute karne ke liye humein page number chahiye — missing mapping walk ke dauran discover hoti hai, toh hum pehle chop karte hain.
3. $i_1=(2049\gg 10)\&\text{0x3FF}=2$; $i_2=(2049\gg 0)\&\text{0x3FF}=1$. Yeh step kyun? Example D jaisa hi chop — mechanics nahi badlte sirf isliye ki ek entry missing hai.
4. L1[2] padho: valid = 0. Turant ruk jao — walk karne ke liye koi L2 table nahi hai. Yeh step kyun? Parent ka "empty subtrees omit karo" insight yahan rahta hai — ek unallocated branch exactly ek invalid top-level entry hai. Hum L2 kabhi nahi padhte.

Steps (Case E2 — second-level fault).

1. Example D ki tarah chop karo: $i_1=1$, $i_2=2$, offset 0xABC.
2. L1[1] padho: valid = 1 → real L2 base milta hai. Aage bado. Yeh step kyun? Top branch exist karta hai, toh hum dusra memory read lete hain — E1 ki tarah nahi.
3. L2[2] padho: valid = 0. Ruk jao. L2 table exist karta hai lekin yeh leaf koi frame map nahi karta. Yeh step kyun? Sparsity kisi bhi level par ho sakti hai; ek present inner table mein phir bhi unmapped rows ho sakti hain.
4. Hardware ek page fault raise karta hai — return karne ke liye koi PFN nahi hai, toh CPU PA nahi bana sakta aur OS ko control dena hoga. Yeh step kyun? Valid = 0 leaf matlab "yeh virtual page abhi kisi frame mein map nahi hoti"; sahi response OS ko signal karna hai (demand par frame map karo, ya process kill karo) na ki address fabricate karo.

Dono cases mein: OS decide karta hai — ek naya frame map karo (demand paging) ya process kill karo (illegal access). Page Faults and Demand Paging dekhein.

Verify: dono cases mein koi PA nahi milti — woh absence hi jawaab hai. E1 fault se pehle 1 table read karta hai; E2 karta hai 2. Valid-bit = 0 ko kabhi PFN 0 treat nahi karna chahiye (woh silently frame 0 read kar lega). ✓ Saath mein E1 aur E2 har fault point cover karte hain jo ek two-level walk mein ho sakta hai.

Example F — Degenerate address 0x0 (Cell F)

Steps.

1. offset $=0\&\text{0xFFF}=0$. Yeh step kyun? Sabse chhote address ke liye bhi hum offset peel karte hain — recipe kabhi nahi badlti, aur offset = 0 confirm karna batata hai ki hum page ke bilkul pehle byte par hain.
2. VPN $=0\gg 12=0$, toh $i_1=0$, $i_2=0$. Yeh step kyun? Zero shifts aur masks zero hote hain — sabse chhota possible sab kuch.
3. L1[0] → L2[0] → PFN 0x00000. Yeh step kyun? Hum abhi bhi dono levels walk karte hain: root ka index 0 ek L2 table point karta hai, jiska index 0 frame store karta hai — zero indices ordinary array positions hain, koi special case nahi.
4. PA $=(0\ll 12)|0=0$. Yeh step kyun? Hamesha ki tarah reassemble karo; PFN 0 aur offset 0 ke saath high aur low bits dono empty hain, toh physical address 0 hai.

Verify: PA = 0x0. Note karo ki yeh mapping ka ek choice hai, koi law nahi: virtual 0 physical 0 par sirf isliye map hota hai kyunki us PTE mein PFN 0 store tha. Real systems mein address 0 usually unmapped chhoda jaata hai (taaki null-pointer dereferences fault karein) — jo ek Example-E situation hogi. ✓ Dono readings valid hain; difference poori tarah valid bit mein hai.

Example G — 64-bit, 4-level walk (Cell G)

Steps.

1. offset $=\text{addr}\&\text{0xFFF}=\text{0xB04}$. Yeh step kyun? Page size abhi bhi 4 KiB hai, toh $p=12$ address width chahein koi bhi ho.
2. VPN $=\text{addr}\gg 12$. Har level ab ek 9-bit slice use karta hai, toh mask hai 0x1FF ($2^9-1$) aur shift $s$ har level par 9 badhta hai (10-bit levels ke liye "$s=10(k-1)$" rule ko 9-bit levels ke liye generalize karna: $s=9(k-1)$, bottom se count karte hue):
   • $i_4=(\text{VPN}\gg 0)\&\text{0x1FF}$ — sabse neechi slice, $s=0$, iske neeche kuch nahi.
   • $i_3=(\text{VPN}\gg 9)\&\text{0x1FF}$ — pehle $i_4$ ke 9 bits skip karo.
   • $i_2=(\text{VPN}\gg 18)\&\text{0x1FF}$ — $i_4,i_3$ ke 18 bits skip karo.
   • $i_1=(\text{VPN}\gg 27)\&\text{0x1FF}$ — iske neeche ke 27 bits skip karo. Yeh step kyun? Same knife jo 32-bit case mein tha, bas daant thode patle. Har shift exactly woh index bits discard karta hai jo hamari slice ke neeche hain, phir mask woh 9 bits rakhta hai jo hum chahte hain aur upar ka sab chod deta hai. $9\times 4+12=48$ bits total — split ko address exhaust karna chahiye.
3. Numerically yeh deta hai $i_1=497,i_2=48,i_3=336,i_4=337$ (Verify mein compute kiya gaya).
4. L1[i1] → L2[i2] → L3[i3] → L4[i4] walk karo = 4 memory reads, phir data ke liye 1 aur. Yeh step kyun? Parent ka rule: $n$-level table ⇒ caching se pehle $n$ reads per translation. Yahan $n=4$, toh TLB miss costly hai — exactly isliye TLB and Translation Caching levels badhne ke saath zyada matter karta hai.

Verify: $9\cdot 4+12=48$ = $V$ ✓. Aur reassemble karte hue: $((((i_1\ll 9|i_2)\ll 9|i_3)\ll 9|i_4)\ll 12)|\text{0xB04}$ original 48-bit address return karni chahiye (neeche check kiya gaya). ✓

Example H — Word problem: tree ne kitni memory bachi? (Cell H)

Steps.

1. Flat table size $=2^{20}\text{entries}\times 4\text{B}=4194304\text{B}=4\text{MiB}$. Yeh step kyun? Har possible page ke liye ek entry, used ho ya nahi.
2. Two-level: top table = hamesha 1 table of 4 KiB. Yeh step kyun? Root pointers hold karne ke liye exist karna chahiye.
3. Two-level: inner tables = 3 (worst case, ek per distinct top-level entry) × 4 KiB = 12 KiB. Yeh step kyun? Har used branch ko exactly ek inner table milta hai; baaki 1021 top entries invalid hain → koi table nahi.
4. Total tree $=4\text{KiB}+12\text{KiB}=16\text{KiB}$.
5. Savings $=4\text{MiB}-16\text{KiB}=4096\text{KiB}-16\text{KiB}=4080\text{KiB}$.

Verify: ratio $=4194304/16384=256\times$ chhota. Tree yahan flat table ki memory ka lagbhag 0.39% use karta hai. ✓ Units check: bytes vs bytes throughout. Agar saare 3 pages ek top entry share karein, toh sirf 1 inner table chahiye → 8 KiB total (aur sasta) — upar ka worst case ise bound karta hai.

Example I — Exam twist: translation ulta chalao (Cell I)

Steps.

1. PA se offset nikalo $=\text{0x0009CABC}\&\text{0xFFF}=\text{0xABC}$. Yeh step kyun? Offset virtual aur physical addresses dono share karte hain — woh ek field jo hum divide ke across trust kar sakte hain.
2. Trap: PA hamein frame number 0x9C deta hai, lekin VPN nahi. Bahut saari virtual pages ek hi frame map kar sakti hain (shared memory). Toh PA alone insufficient hai — hume walk info $(i_1,i_2)$ chahiye tha. Yeh step kyun? Translation generally many-to-one hai; reverse karne ke liye extra data chahiye.
3. Walk indices se VPN rebuild karo $=(i_1\ll 10)|i_2=(1\ll 10)|2=1026=\text{0x402}$. Yeh step kyun? Indices hi VPN hain, split; inhe concatenate karne se woh restore hota hai.
4. Virtual address rebuild karo $=(\text{VPN}\ll 12)|\text{offset}=(\text{0x402}\ll 12)|\text{0xABC}=\text{0x00402ABC}$. Yeh step kyun? Yeh hamare chop→look up→reassemble recipe ka reassemble move hai, ulta chalaya gaya: Step 3 mein VPN recover karke, hum use $p=12$ left slide karte hain taaki woh page-number position mein wapas aaye aur untranslated offset low bits mein giraye — exactly Step-1 chop ka inverse.

Verify: yeh exactly Example D ka original virtual address hai — round trip close ho jaata hai. ✓ Forward: 0x00402ABC → 0x0009CABC; backward (walk data ke saath): 0x0009CABC + $(i_1,i_2)$ → 0x00402ABC. Offset ABC dono directions mein untouched survive karta hai.

Active Recall