Page tables and multi-level paging: Exercises — Hinglish deep dive

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

Shuru karne se pehle, ek shared picture. Inn problems mein har virtual address bits ki ek row hai jo named fields mein cut ki gayi hai — blue aur yellow blocks milke VPN banate hain, aur green block woh offset hai jo bina kisi badlaav ke through chali jaati hai. Hum is picture ka seedha reference Solutions 2.1 aur 2.2 mein karte hain, isliye ise abhi dhyan se dekho.

Figure — Page tables and multi-level paging

Definition Jo symbols hum baar baar use karte hain (sab parent mein explain hain)

$V$ = virtual address ki width bits mein (e.g. 32 matlab address 32 binary digits ka hai).
$P$ = page size bytes mein; $p = lo g_{2} P$ = offset bits ki sankhya (woh low bits jo ek page ke andar kisi byte ka naam batate hain).
$v = V - p$ = VPN bits ki sankhya (VPN = virtual page number, "kaun sa page" wala part).
$≪$ matlab "shift left" (right side par zeros lagao — do ki power se multiply karo). $≫$ matlab "shift right" (right end se low bits hatao — do ki power se integer-divide karo; yeh exactly $≪$ ka undo hai). $∣$ matlab bitwise-OR (non-overlapping bit fields ko glue karo). Bit Manipulation and Masking dekho agar yeh naye lagte hain.
$⌊ x ⌋$ = floor: $x$ ko nearest whole number tak round down karo (koi bhi fraction phenko). $a mod b$ = modulus: $a$ ko $b$ se divide karne ke baad jo remainder bachta hai. Dono plain "integer divide, quotient rakho / remainder rakho" operations hain — Bit Manipulation and Masking mein dekho yeh powers of two par shifting aur masking ke barabar kaise hain.
Ek PTE (page table entry) ek table ki ek row hai: yeh ek PFN (physical frame number) plus flag bits store karta hai.

L1 — Recognition

Problem 1.1

Ek system mein $V = 32$ -bit virtual addresses hain aur page size $P = 4 KiB$ hai. $p$ (offset bits), $v$ (VPN bits), aur flat page table ko kitni entries chahiye hogi, yeh batao.

Recall Solution 1.1

KYA compute karein: field widths, phir table length. KYUN: $P = 4 KiB = 4096 = 2^{12}$ bytes. Ek page ke andar kisi byte ka naam lene ke liye kitne bits chahiye, yeh exactly $lo g_{2}$ hai kitne bytes woh hold karta hai: $p = lo g_{2} P = lo g_{2} 2^{12} = 12 bits.$ Address ka baaki hissa page ka naam batata hai: $v = V - p = 32 - 12 = 20 bits.$ Flat table mein har possible page ke liye ek entry hoti hai, yaani har VPN value ke liye ek: $entries = 2^{v} = 2^{20} = 1048576 \approx 1 million.$ Answer: $p = 12$ , $v = 20$ , entries $= 2^{20}$ .

Problem 1.2

Har item ko match karo ki woh kya store karta hai: (a) page table ka index, (b) ek page table entry (PTE).

Recall Solution 1.2

KYA/KYUN: Parent ka rule "position is the key, entry is the value" yeh decide karta hai.

(a) Index khud VPN hai (ya us level ka VPN ka slice) — yeh position se implied hota hai, yeh khud kuch store nahi karta.
(b) PTE store karta hai PFN + flags (valid, read/write, user/supervisor, dirty, accessed). Answer: index ↔ virtual page number (positional); PTE ↔ physical frame number + flags.

L2 — Application

Problem 2.1

$V = 32$ , $P = 4 KiB$ . Virtual address 0x00003FFF ke liye offset aur VPN compute karo.

Recall Solution 2.1

KYA: address ko bit $p = 12$ par split karo — exactly shared picture (figure s01) mein green/coloured boundary. KYUN offset pehle: low $p = 12$ bits offset hain (green block); unhe mask karne par VPN bachta hai (blue+yellow blocks). Bit Manipulation and Masking dekho. Symbol list se yaad karo ki $a mod b$ remainder rakhta hai aur $⌊ \cdot ⌋$ whole-number quotient rakhta hai: $offset = addr mod P = 0x00003FFF mod 0x1000 .$ 0x00003FFF = 0x3 * 0x1000 + 0xFFF, toh offset $= 0xFFF = 4095$ (remainder). $VPN = ⌊ \frac{addr}{P} ⌋ = 0x00003FFF ≫ 12 = 0x3 = 3.$ Yahan $≫ 12$ (right mein 12 shift, symbol list se) 12 offset bits right end se hata deta hai — exactly wahi undo jab address $≪ 12$ se banaya gaya tha. Answer: offset $= 0xFFF = 4095$ , VPN $= 3$ .

Problem 2.2

Same system. Do-level split 10 / 10 / 12 ( $i_{1}$ = top 10 bits, $i_{2}$ = next 10, offset = 12). Virtual address 0x00801234 ke liye $i_{1}$ , $i_{2}$ , offset nikalo. Agar L2[i2].PFN = 0x000AB hai, toh final physical address do.

Recall Solution 2.2

KYA: address ko teen fields mein kato — literally shared picture (figure s01) ke blue $i_{1}$ , yellow $i_{2}$ , green offset blocks — phir physical address reassemble karo. Address ko binary mein likho. 0x00801234: $0x00801234 = 0000000010000000000100100011010 0_{2} .$ Offset = low 12 bits = 0001 0010 0011 0100... last 12 lo: 0010 0011 0100 $= 0x234$ . KYUN: $p = 12$ , toh 12 low bits bina badlaav ke through jaate hain. Baaki top 20 bits hain 0000 0000 1000 0000 0001 $= 0x00801$ . Un 20 bits ko $i_{1}$ (top 10) aur $i_{2}$ (next 10) mein split karo:

top 10: 0000 0000 10 $= 2$ , toh $i_{1} = 2$ .
next 10: 00 0000 0001 $= 1$ , toh $i_{2} = 1$ . Final PA: deliver kiye gaye PFN ko bina chhue offset ke saath glue karo: $PA = (PFN ≪ p) ∣ offset = (0x000AB ≪ 12) ∣ 0x234 = 0x000AB234 .$ Answer: $i_{1} = 2$ , $i_{2} = 1$ , offset $= 0x234$ , PA $= 0x000AB234$ .

L3 — Analysis

Problem 3.1

$V = 32$ , $P = 4 KiB$ ke liye, flat table 4 MiB use karta hai (4-byte PTEs ke saath). Explain karo kyun 10/10/12 two-level split har table ko exactly ek page banata hai — aur arithmetic dikhao.

Recall Solution 3.1

KYA: entries per table count karo aur PTE size se multiply karo. Har 10-bit index $2^{10} = 1024$ entries mein se ek select karta hai. 4-byte PTEs ke saath: $table size = 2^{10} \times 4 B = 4096 B = 4 KiB = P .$ KYUN yeh elegant hai: ek table jo exactly ek page hai, khud wahi machinery use karke page, allocate, aur swap ho sakta hai jo woh describe karta hai — koi special "bada region" nahi chahiye. 10/10/12 numbers isliye choose kiye gaye hain taaki $2^{10} \times 4 = P$ ho. Answer: har level ki table $= 1024 \times 4 B = 4 KiB =$ ek page.

Problem 3.2

Ek process exactly ek code page aur ek stack page use karta hai, address space mein door door. (a) flat, (b) two-level 10/10/12 ke liye total page-table memory compute karo. Batao yeh kyun alag hain.

Recall Solution 3.2

KYA: actually allocate hue tables ka sum karo. (a) Flat: table fixed-size hai chahe usage kuch bhi ho: $2^{20} entries \times 4 B = 4 MiB = 4194304 B .$ (b) Two-level: tumhe hamesha ek top table chahiye (4 KiB). Code aur stack "door hain," toh woh alag top-level entries ke neeche aate hain ⇒ do inner tables (4 KiB har ek): $1 \times 4 KiB + 2 \times 4 KiB = 3 \times 4096 = 12288 B = 12 KiB .$ KYUN alag hain: flat table saare $2^{20}$ pages ke liye slot pre-reserve karta hai chahe sab untouched hon. Concretely: top table mein $2^{10} = 1024$ slots hain; process sirf $2$ use karta hai, baaki $1022$ unused top-level slots hain. Un $1022$ slots mein se har ek $1024$ entries wali ek inner table point karta, yaani woh $1022 \times 1024 = 1046528$ page-entries ki jagah le leti jo flat table reserve karta hai par tree kabhi allocate nahi karta. Tree un $1022$ unused top entries ko invalid mark karta hai, unke liye koi inner table allocate nahi karta (dekho Page Faults and Demand Paging ki "invalid" access par kya trigger hota hai). Answer: flat $= 4194304 B$ ; two-level $= 12288 B$ .

L4 — Synthesis

Problem 4.1

Ek 64-bit machine $P = 4 KiB$ aur four-level page table use karta hai jisme 48-bit usable virtual address hai (jaise x86-64), har level ek 9-bit index. Field widths verify karo ki add up hote hain, aur compute karo ki full walk mein kitne RAM accesses chahiye, phir actual target byte padhne ke liye total.

Recall Solution 4.1

KYA: check karo $9 + 9 + 9 + 9 + 12 = 48$ , phir accesses count karo. Offset bits: $p = lo g_{2} 4096 = 12$ . Chaar index levels 9 bits each: $9 + 9 + 9 + 9 + 12 = 48 = V_{usable} . ✓$ KYUN 9-bit levels: $2^{9} \times 8 B = 512 \times 8 = 4096 B = P$ — har table ek page hai (64-bit PTEs 8 bytes hote hain). Same "table = ek page" trick jaise L3 mein. Walk cost: har level ek memory read hai jo next-level pointer fetch karta hai, toh 4-level walk = 4 reads. Phir actual data byte ke liye ek aur read: $total accesses (TLB miss) = 4 + 1 = 5.$ Answer: widths sum to 48; walk = 4 reads; data tak pahunchne ke liye total = 5 reads.

Problem 4.2

Model $avg = t_{T L B} + (miss rate) \times (walk cost)$ use karke, maano $t_{T L B} = 1$ cycle, walk cost $= 4$ memory reads $\times$ 100 cycles/read $= 400$ cycles, aur TLB miss rate $2% = 0.02$ hai. Average translation time compute karo. Phir woh miss rate nikalo jo ise double kar de.

Recall Solution 4.2

Term note: yahan "walk cost" ka matlab sirf woh page-table reads hain jo frame dhundh lete hain — Problem 4.1 ke 4 translation accesses, final data fetch nahi. Data read ek alag cost hai jo translation ke baad hoti hai chahe kuch bhi ho, isliye yeh translation-time model mein nahi aati. (Agar kabhi include karo, kaho "translation + data" = 5 reads, jaise Problem 4.1 mein.) KYA: plug in karo, phir target ke liye invert karo. $avg = 1 + 0.02 \times 400 = 1 + 8 = 9 cycles.$ Double matlab target $= 18$ cycles. Miss rate $m$ ke liye solve karo: $18 = 1 + m \times 400 \Rightarrow m = \frac{17}{400} = 0.0425 = 4.25%.$ KYUN yeh matter karta hai: walk cost dominate karta hai jab miss rate non-tiny hoti hai, isliye TLB exist karta hai — Cache Memory Basics mein same "hit fast / miss slow" trade-off dekho. Answer: avg $= 9$ cycles; double karne ke liye miss rate $= 0.0425$ ( $4.25%$ ) chahiye.

L5 — Mastery

Problem 5.1

Tum ek naye 32-bit CPU ke liye paging design kar rahe ho. Tum page size $P \in {4 KiB, 16 KiB}$ aur 1, 2, ya 3 levels choose kar sakte ho. Requirement: har table exactly ek page mein fit hona chahiye, PTEs 4 bytes hain. $P = 16 KiB$ ke liye, ek page-table page mein kitni entries fit hongi, kitne index bits hote hain, aur kya ek clean 2-level design saare $V = 32$ bits cover kar sakta hai? Split dikhao.

Recall Solution 5.1

KYA: per-page index width derive karo, phir levels ko $V$ mein fit karo. $P = 16 KiB = 2^{14}$ bytes ⇒ offset $p = 14$ bits, VPN $v = 32 - 14 = 18$ bits. Ek-page table mein entries: $\frac{P}{PTE size} = \frac{2 ^{14}}{4} = \frac{16384}{4} = 4096 = 2^{12}$ entries, yaani 12-bit index per level. Kya 2 levels 18 VPN bits cover kar sakte hain? Do 12-bit indices $12 + 12 = 24$ bits ki indexing capacity dete hain — hamare zaroorat ke $18$ se zyada, toh haan, aaram se. Ek clean split ek pura 12-bit level aur ek chhota top level use karta hai: $v = 18 = i_{1} 6 + i_{2} 12, address = [i_{1} : 6 ∥ i_{2} : 12 ∥ offset : 14] .$ KYUN top level sirf 6 bits ka hai: top table tab apne 4096 possible slots mein se sirf $2^{6} = 64$ use karta hai — ise pura hona zaruri nahi; unused high slots simply invalid mark ho jaate hain. Yeh legal hai kyunki indexing capacity ( $24$ ) $\geq$ VPN width ( $18$ ). Answer: $P = 16 KiB$ ⇒ 4096 entries/page = 12-bit index; 2 levels (12+12=24 ≥ 18) kafi hain; split $6/12/14$ .

Problem 5.2

Defend ya refute karo: "Is same 32-bit, $P = 16 KiB$ machine ke liye, ek single-level flat table ab bilkul theek hai — koi tree ki zarurat nahi." Ek size calculation aur ek design caveat se support karo.

Recall Solution 5.2

KYA: flat table ko size karo, phir judge karo. Flat table entries $= 2^{v} = 2^{18} = 262144$ . 4-byte PTEs ke saath: $size = 2^{18} \times 4 = 262144 \times 4 = 1048576 B = 1 MiB per process.$ Verdict — thoda defensible: 1 MiB 4 KiB-page case ke 4 MiB se kaafi chhota hai, kyunki bade pages matlab track karne ke liye kam pages hain ( $v$ 20 se 18 gira, aur har page 4× zyada memory cover karta hai). Kam processes wali machine ke liye, 1 MiB flat acceptable ho sakta hai. Caveat (kyun hum phir bhi tree prefer karte hain): flat 1 MiB poora allocate hota hai chahe process sirf do pages touch kare; $6/12/14$ tree ko sirf top table $+$ used inner tables chahiye hoti. Aur 16 KiB pages internal fragmentation se memory waste karte hain (ek 1-byte allocation bhi ek poora 16 KiB frame jalata hai). Trade-off yahan space-vs-space hai, usual space-vs-time nahi. Answer: flat table $= 1048576 B = 1 MiB$ ; kam process counts ke liye defensible hai lekin tree sparse usage par phir bhi jeet jaata hai; 16 KiB pages internal fragmentation badhate hain.

Recall Self-quiz ke liye one-line summaries

Page size se offset bits ::: $p = lo g_{2} P$ . Flat 32-bit / 4 KiB table size ::: $2^{20} \times 4 B = 4 MiB$ . Two-level, 1 code + 1 stack page ::: $\approx 12 KiB$ (top + 2 inner tables). x86-64 4-level walk memory reads (miss) ::: translate karne ke liye 4, data read including 5. Tree kya kharidta hai vs TLB kya kharidta hai ::: tree space kharidta hai, TLB time kharidta hai.

Parent: Page tables and multi-level paging · See also Address Space Layout, Virtual Memory, TLB and Translation Caching.