Virtual memory and paging: Worked examples — Hinglish deep dive

5.4.11 · D3 · Hardware › Memory Hierarchy & Caches › Virtual memory and paging

Yeh page "no surprises" drill hai. Parent note ne tumhe address translation ki machinery sikhaayi; yahan hum har tarah ke numbers feed karte hain us machinery ko — clean cases, edge cases, degenerate cases, aur woh sneaky exam twists — taaki jab koi exam mein aaye toh tum uska twin pehle se dekh chuke ho.

Yahan sab kuch teen ideas pe based hai jo parent se hain aur hum baar baar use karenge, toh ek baar mein phir se anchor karte hain (koi naya symbol bina picture ke nahi):

Figure dekho: ek address ek ruler jaisa hai. Bit $p$ par red line woh cut hai. Cut ke left mein sab VPN hai (jo replace hota hai), right mein sab unchanged reh'ta hai. Is page mein yeh red line tab tak nahi move hogi jab tak page size na badle. Woh picture apne dimag mein rakho.

The scenario matrix

Is topic ka har problem in cells mein se ek (ya combo) hota hai. Hum sab hit karenge.

Cell	Kya tricky banata hai	Covered by
A. Clean split	plain hex, digits line up	Ex 1
B. Non-nibble page size	$p$ 4 ka multiple nahi, toh hex digits mid-digit split hoti hain	Ex 2
C. Offset = 0 (page boundary)	address exactly ek page start par baith'ta hai	Ex 3
D. Offset = max (page ka last byte)	address rollover se pehle bilkul last byte hai	Ex 3
E. Reverse direction	PA diya hua, VA recover karo (inverse map)	Ex 4
F. Table-size scaling	VA bits / entry size ke saath tables ke liye RAM kaise badhti hai	Ex 5
G. Multi-level walk	VPN khud index levels mein split hota hai	Ex 6
H. Performance / EAT	limiting behaviour jab hit ratio $h \to 1$ aur $h \to 0$	Ex 7
I. Word problem	swap/disk timing, "kya yeh ek page fault hai?"	Ex 8
J. Degenerate / trap	invalid VPN, unmapped page, offset overflow	Ex 9

Agar koi cell neeche kisi example mein nahi hai, toh is page mein bug hai. Chalte hain.

Cell A — the clean split

Worked example Example 1 — textbook translation (

$p = 12$ ) Page size $= 4 KiB$ , toh $p = 12$ . $VA = 0x2C4F9$ . Page table: VPN $0x2C \to$ PFN $0x15$ .

Forecast: aage padhne se pehle PA guess karo. (Hint: last 3 hex digits survive karte hain.)

Offset split karo. $offset = 0x2C4F9 & 0xFFF = 0x4F9$ . Yeh step kyun? $2^{12} - 1 = 0xFFF$ = exactly 3 hex digits = low 12 bits. $p = 12$ ke saath cut ek hex boundary par neatly land karta hai, toh "last 3 hex digits rakho" hi mask hai.
VPN extract karo. $VPN = 0x2C4F9 ≫ 12 = 0x2C$ . Yeh step kyun? 12 se right shift karne par woh same 3 hex digits throw away ho jaati hain, page number bach jaata hai.
Frame lookup karo. PFN $= 0x15$ . Yeh step kyun? Sirf VPN translate hota hai — yeh ek hi table access hai.
Rebuild karo. $PA = (0x15 ≪ 12) ∣ 0x4F9 = 0x15000 ∣ 0x4F9 = 0x154F9$ . Yeh step kyun? Frame base hai $PFN \times 2^{12}$ ; offset low bits mein untouched drop ho jaata hai.

Verify karo: $0x154F9 = 87289$ , aur $0x15 \times 4096 + 0x4F9 = 21 \times 4096 + 1273 = 86016 + 1273 = 87289$ . ✓ Offset ( $0x4F9$ ) VA aur PA ke beech unchanged hai — exactly wahi jo "offset stays" ne promise kiya tha.

Cell B — woh page size jo ek hex digit split karti hai

Real exams mein $1 KiB = 2^{10}$ jaisi page size bahut pasand hai, jahan $p = 10$ 4 ka multiple nahi hota. Ab cut ek hex digit ke beech mein se guzarti hai, aur "last few hex digits rakho" silently fail ho jaata hai. Tumhe binary pe fall back karna hoga.

Worked example Example 2 — non-nibble split (

$p = 10$ ) Page size $= 1 KiB$ , toh $p = 10$ . $VA = 0x3C7 = 967$ . VPN $\to$ PFN table: VPN $0 \to 5$ .

Forecast: offset "last 2.5 hex digits" nahi hai — bits mein socho.

Mask karo. $2^{10} - 1 = 1023 = 0x3FF$ . $offset = 0x3C7 & 0x3FF = 0x3C7 = 967$ . Yeh step kyun? $0x3C7 = 967 < 1024$ , toh poora address page 0 ke andar hai — offset poori value hi hai.
VPN. $VPN = 967 ≫ 10 = ⌊ 967/1024 ⌋ = 0$ . Yeh step kyun? 10 se shift karna (8 ya 12 se nahi) true cut ko respect karta hai; "hex digits" se karna galat hoga.
Map karo. PFN $= 5$ , toh frame base $= 5 \times 1024 = 5120$ .
Rebuild karo. $PA = 5120 + 967 = 6087 = 0x17C7$ .

Verify karo: $6087 mod 1024 = 967$ ✓ (offset preserved) aur $⌊ 6087/1024 ⌋ = 5$ ✓ (correct frame). Notice karo $0x3C7 \to 0x17C7$ : low hex digits sab intact survive nahi kiye — yeh mid-digit cut ka effect hai.

Cells C & D — dono extremes par offset (page boundaries)

Do sabse zyada misread inputs hain page ka pehla byte (offset $= 0$ ) aur last byte (offset $= 2^{p} - 1$ ). Dono ek saath karte hain aur dekhte hain kya hota hai agar last byte ke ek byte aage jaao.

Worked example Example 3 — offset

$= 0$ aur offset $= max$ ( $p = 12$ ) $p = 12$ , VPN $0x8 \to$ PFN $0x3$ .

Forecast: virtual page 8 ka pehla byte kis PA par land karta hai? Aur last?

Pehla byte: $VA = 0x8000$ . offset $= 0x8000 & 0xFFF = 0$ . VPN $= 0x8000 ≫ 12 = 0x8$ . Yeh step kyun? Ek address jo $2^{p}$ ka exact multiple hai, uske saare low bits zero hote hain — woh page boundary par baith'ta hai.
$PA = (0x3 ≪ 12) ∣ 0 = 0x3000$ . Frame base, exactly, koi offset nahi.
Last byte: $VA = 0x8FFF$ . offset $= 0xFFF = 4095$ (max). VPN abhi bhi $0x8$ . Yeh step kyun? $0xFFF$ hai $2^{12} - 1$ , woh sabse bada offset jo 4 KiB page hold kar sakta hai.
$PA = 0x3000 ∣ 0xFFF = 0x3FFF$ .

Verify karo: page 8 VA $0x8000$ – $0x8FFF$ tak span karta hai (yeh $4096$ bytes hai ✓), PA $0x3000$ – $0x3FFF$ tak map karta hai (yeh bhi $4096$ ✓). Ek byte aage, $0x9000$ , ka VPN $0x9$ hai — ek different table entry, possibly ek different, non-adjacent frame. Virtual mein contiguous ≠ physical mein contiguous.

Figure yeh dikhata hai: virtual pages 8 aur 9 side by side baithe hain, lekin unke frames (3 aur, maan lo, 7) physical RAM mein scattered hain. Page boundary ek hard wall hai — isko cross karo aur table phir se consult karni padti hai.

Cell E — map ko ulta chalana

Ek physical address diya hua hai, kaun sa virtual address usne produce kiya? Offset trivial hai (unchanged). Page part ke liye tum table invert karte ho: woh VPN dhundho jiska entry yeh PFN hai.

Worked example Example 4 — inverse translation (

$p = 12$ ) $p = 12$ . Table: VPN $0x1 \to$ PFN $0x9$ , VPN $0x2 \to$ PFN $0x4$ . Given $PA = 0x4ABC$ , VA find karo.

Forecast: kaun sa VPN yahan map karta hai — aur kya answer unique bhi hai?

PA split karo. offset $= 0x4ABC & 0xFFF = 0xABC$ . PFN $= 0x4ABC ≫ 12 = 0x4$ . Yeh step kyun? Physical addresses usi same $p$ par split hote hain — frames pages ke saath same size ke hote hain.
Invert karo. Kaun sa VPN PFN $0x4$ par map karta hai? Table row: VPN $0x2$ . Yeh step kyun? Hum map right-to-left padh rahe hain; offset pehle se correct hai, sirf page number ko undo karna hai.
VA rebuild karo. $VA = (0x2 ≪ 12) ∣ 0xABC = 0x2ABC$ .

Verify karo: $0x2ABC$ forward-translate karo: VPN $0x2 \to 0x4$ , offset $0xABC$ , PA $= 0x4ABC$ ✓. Caveat: inverse unique hai sirf ek process ki table ke andar. Do alag processes dono ka VPN PFN $0x4$ par map ho sakta hai — physical frames share ya reuse ho sakti hain, toh "PA → VA" globally invertible nahi hai.

Cell F — table cost kaise scale karta hai

Worked example Example 5 — teen scales par page-table size

32-bit, 48-bit, aur 64-bit VA compare karo, sab ke saath $4 KiB$ pages ( $p = 12$ ) aur $8$ -byte entries.

Forecast: inme se kaun sa flat store karna physically impossible hai?

Entries $= 2^{n - p}$ . $n = 32$ ke liye: $2^{20}$ . $n = 48$ ke liye: $2^{36}$ . $n = 64$ ke liye: $2^{52}$ . Yeh step kyun? Har virtual page ke liye ek entry; pages ki sankhya $= 2^{n} / 2^{p}$ .
Bytes $=$ entries $\times 8$ . $n = 32$ : $2^{20} \times 8 = 2^{23} = 8 MiB$ . $n = 48$ : $2^{36} \times 8 = 2^{39} = 512 GiB$ . $n = 64$ : $2^{52} \times 8 = 2^{55} = 32 PiB$ . Yeh step kyun? Raw table footprint per process paane ke liye count ko entry width se multiply karo.

Verify karo: $8 MiB$ annoying-but-survivable hai; $512 GiB$ per process absurd hai; $32 PiB$ abhi tak bane saare RAM se zyada hai. Yahi exactly reason hai kyun Multi-level page tables exist karte hain — tum kabhi bhi poora flat table allocate nahi karte.

Cell G — the multi-level walk

Cell F ka fix: VPN khud ko index pieces mein split karo, ek per table level, aur sirf woh sub-tables banao jo actually use ho rahe hain.

Worked example Example 6 — two-level walk (

$p = 12$ ) $32$ -bit VA, $p = 12$ (offset). Baaki $20$ VPN bits mein split: VPN1 = top 10 bits, VPN2 = next 10 bits. $VA = 0x00403ABC$ .

Forecast: ek translation mein data read se pehle kitne memory reads lagte hain?

Offset peel karo. offset $= 0x00403ABC & 0xFFF = 0xABC$ (low 12 bits).
VPN (saare 20 bits) $= 0x00403ABC ≫ 12 = 0x00403 = 1027$ . Yeh step kyun? Pehle jaisa hi cut; bas hum is VPN ko aur kaat'ne wale hain.
VPN1 = top 10 bits $= 1027 ≫ 10 = 1$ . VPN2 = low 10 bits $= 1027 & 1023 = 3$ . Yeh step kyun? Level-1 table VPN1 se index hoti hai level-2 table dhundhne ke liye; level-2 VPN2 se index hoti hai PFN dhundhne ke liye.
Walk: L1[1] → L2 table ka address; L2[3] → PFN. Phir PA $=$ (PFN $≪ 12$ ) $∣$ offset.

Verify karo: VPN uske parts se reconstruct karo: $VPN1 \times 2^{10} + VPN2 = 1 \times 1024 + 3 = 1027$ ✓, aur $1027 \times 4096 + 0xABC = 4206592 + 2748 = 4209340 = 0x00403ABC$ ✓. Cost: 2 table reads + 1 data read = 3 memory accesses on a TLB miss (single-level ke 2 ke comparison mein) — table shrink karne ki keemat.

Cell H — limits par performance

Worked example Example 7 — EAT aur uska limiting behaviour

Yaad karo $EAT = t_{T L B} + t_{m e m} + (1 - h) t_{m e m}$ (single-level miss penalty $=$ ek extra $t_{m e m}$ ). Use karo $t_{T L B} = 1 ns$ , $t_{m e m} = 100 ns$ .

Forecast: EAT kya hoga jab TLB hamesha hit kare ( $h = 1$ ) aur jab hamesha miss kare ( $h = 0$ )?

$h = 0.90$ : $EAT = 1 + 100 + (0.10) (100) = 111 ns$ . Yeh step kyun? 10% accesses table walk ki cost pay karte hain; average karo.
$h \to 1$ (best case): $EAT \to 1 + 100 + 0 = 101 ns$ . Yeh step kyun? Koi miss nahi ⇒ koi walk nahi; sirf TLB + real access pay karte ho.
$h \to 0$ (worst case): $EAT \to 1 + 100 + 100 = 201 ns$ . Yeh step kyun? Har access table walk karta hai — raw memory time se lagbhag double. Yahi hai jo Locality of reference hum se bachata hai.

Verify karo: EAT $(1 - h)$ mein linear hai: $h = 1$ par $101 ns$ se shuru hokar $h = 0$ par $201 ns$ tak jaata hai, aur $h = 0.90$ par $111 ns$ par hai, exactly $100 ns$ span ka $\frac{1}{10}$ ✓.

Figure EAT versus hit ratio plot karta hai: $(0, 201)$ se $(1, 101)$ tak ek straight line. Steepness ( $100 ns$ per unit of hit ratio) hi miss penalty hai. Real TLBs far-right par rehte hain ( $h > 0.99$ ), $101 ns$ ke paas.

Cell I — the word problem (swap timing)

Worked example Example 8 — page fault to disk

Ek page disk par hai (swapped out). Ek page fault service karne mein $8 ms$ disk I/O lagti hai. Ek normal in-RAM access $100 ns$ leta hai. Agar 1 in 100 000 accesses fault kare, toh average access time kya hai?

Forecast: compute karne se pehle guess karo — kya tiny fault rate matter karegi, disk kitni slow hai?

Units convert karo. $8 ms = 8000000 ns$ . Fault probability $= 1 0^{- 5}$ . Yeh step kyun? Kabhi bhi ms aur ns mix mat karo — sab ns mein daalo.
Average. $avg = (1 - 1 0^{- 5}) (100) + (1 0^{- 5}) (8000000)$ . Yeh step kyun? Weighted mean: almost hamesha $100 ns$ , kabhi kabhi $8 ms$ .
$= 100 - 0.001 + 80 = 179.999 ns \approx 180 ns$ .

Verify karo: $1 0^{- 5} \times 8000000 = 80 ns$ pure fault contribution hai; sirf $1$ -in- $100000$ ki fault rate effective time lagbhag double kar deti hai. Lesson: disk RAM se $80000 \times$ slow hai, toh thodi si bhi faulting dominate kar jaati hai — isliye Page replacement algorithms itni mehnat karte hain sahi pages resident rakhne ke liye.

Cell J — degenerate & trap inputs

Worked example Example 9 — invalid VPN aur offset overflow (

$p = 12$ ) Table mein sirf VPN $0x0$ aur $0x1$ ke liye valid entries hain; baaki sab ke liye valid bit 0 hai.

Forecast: kya hoga (a) $VA = 0x9004$ ke liye, aur (b) ek single 12-bit offset field mein $0x1000$ store karne ki koshish karne par?

(a) Unmapped page access karo. VPN $= 0x9004 ≫ 12 = 0x9$ . Table entry $0x9$ ka valid bit $= 0$ hai. Yeh step kyun? Translation VPN lookup se start hoti hai; valid bit pehle check hota hai.
MMU ek fault raise karta hai. OS inspect karta hai: kya VPN $0x9$ sirf disk par swapped hai (→ load karo, resume karo) ya kabhi allocate nahi hua / out of range (→ segmentation fault, process kill karo)? Dekho Segmentation. Yeh step kyun? Same hardware trap, do software meanings — inhe distinguish karna OS ka kaam hai.
(b) Offset overflow. Ek offset field $p = 12$ bits hold karta hai, max value $0xFFF = 4095$ . Value $0x1000 = 4096$ fit nahi hoti — yeh offset nahi hai bilkul, yeh agla page ka base hai. Yeh step kyun? $4096 = 2^{12}$ 12-bit field se carry out ho jaata hai VPN mein, matlab page number increment hota hai. Offsets hamesha $[0, 2^{p} - 1]$ mein hote hain.

Verify karo: sabse bada legal offset hai $2^{12} - 1 = 4095$ ✓; $4096 mod 4096 = 0$ quotient $1$ ke saath, confirm karta hai yeh agla page ka start hai, koi offset nahi ✓. Aur VPN $0x9 = 9$ mapped set ${0, 1}$ ke bahar hai, toh fault correct behaviour hai, hamari arithmetic mein bug nahi.

Recall

Recall Yeh kaun sa cell hai? (answers cover karo)

Page size $1 KiB$ , VA $= 1500$ : offset kya hai? ::: $1500 - 1024 = 476$ (Cell B — mask $1023$ , non-nibble).
PA exactly ek frame boundary par baith'ta hai. Uska offset kya hai? ::: $0$ (Cell C).
PA diya hua, kya VA recover karna hamesha unique hota hai? ::: Sirf ek process ki page table ke andar (Cell E).
48-bit VA, 4 KiB pages, 8-byte entries — flat table size? ::: $512 GiB$ , isliye multi-level (Cell F).
Two-level walk: TLB miss par translation mein memory accesses kitne? ::: 3 (2 table + 1 data) (Cell G).
EAT jab $h \to 0$ with $t_{m e m} = 100, t_{T L B} = 1$ ? ::: $201 ns$ (Cell H).
Valid bit 0 hai aur page kabhi allocate nahi hua — kya fire karta hai? ::: Segmentation fault (Cell J).