Virtual memory and paging: Exercises — Hinglish deep dive

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

Shuru karne se pehle, ek picture har problem ko jodti hai — ek address ki anatomy.

Recall Teen operations jo tum har jagah reuse karoge

Maano page size $P = 2^{p}$ bytes hai. Ek virtual address $A$ ke liye:

offset $= A mod 2^{p} = A & (2^{p} - 1)$ — neeche ke $p$ bits (page ke andar kaun sa byte).
VPN $= ⌊ A / 2^{p} ⌋ = A ≫ p$ — upar ke bits (kaun sa page).
Rebuild karo: $PA = (PFN ≪ p) ∣ offset$ .

Neeche sab kuch inhi teen lines ka dhyaan se application hai.

Level 1 — Recognition

Exercise 1.1

Inmein se kaun sa MMU dwara translate hota hai, aur kaun sa unchanged copy hota hai: VPN ya offset?

Recall Solution

VPN translate hota hai (woh page table mein look up karke PFN ban jaata hai). Offset unchanged copy hota hai.

Kyun: kisi page ko frame mein move karna ek rigid shift hai — page ka byte 5, frame ka bhi byte 5 rehta hai. Sirf base badalta hai. Figure s01 dekho: peele offset bits seedha pass ho jaate hain, coloured VPN bits table se guzarte hain.

Exercise 1.2

Ek system 4 KiB pages use karta hai. Offset kitne bits ka hai, aur $p$ kya hai?

Recall Solution

$4 KiB = 4 \times 1024 = 4096 = 2^{12}$ bytes. Toh $p = 12$ aur offset 12 bits ka hai.

Kyun: offset ko ek page ke andar ka har byte naam dena hoga. $2^{12}$ bytes per page hone par, $0$ se $4095$ tak count karne ke liye exactly $12$ bits chahiye.

Level 2 — Application

Exercise 2.1

Page size $= 4 KiB$ ( $p = 12$ ). Virtual address hai $VA = 0x2C4F7$ . Ise VPN aur offset mein split karo.

Recall Solution

Neeche ke $12$ bits $=$ aakhiri teen hex digits (har hex digit $4$ bits ka hota hai, toh $3 \times 4 = 12$ ). $offset = 0x2C4F7 & 0xFFF = 0x4F7$ $VPN = 0x2C4F7 ≫ 12 = 0x2C$ Kyun last-3-digits shortcut kaam karta hai: $12$ bits se right shift karna aakhiri $12/4 = 3$ hex digits drop karne ke barabar hai. Toh VPN $= 0x2C$ , offset $= 0x4F7$ .

Exercise 2.2

2.1 se aage: page table VPN $0x2C \to$ PFN $0x5$ map karta hai. Physical address kya hai?

Recall Solution

$PA = (PFN ≪ 12) ∣ offset = (0x5 ≪ 12) ∣ 0x4F7 = 0x5000 ∣ 0x4F7 = 0x54F7$ Kyun PFN ko 12 se shift karte hain: frame number $f$ physical byte $f \times 2^{12}$ par shuru hota hai. Left shift by $12$ se woh base address banta hai ( $0x5000$ ); untouched offset ko OR karne se exact byte milta hai.

Level 3 — Analysis

Exercise 3.1

Ek machine mein $32$ -bit virtual address, $4 KiB$ pages, aur har page-table entry $4$ bytes ki hai. Single-level page table ke liye entries ki sankhya aur har process ka total size compute karo.

Recall Solution

Entries $= \frac{2 ^{32}}{2 ^{12}} = 2^{20} = 1, 048, 576$ (ek million ke lagbhag). Kyun: har virtual page ke liye ek entry; (address-space size)/(page size) pages hote hain. $Table size = 2^{20} \times 4 bytes = 2^{22} bytes = 4 MiB per process$ Kyun dhyan dein: $100$ processes ke saath woh $400 MiB$ RAM sirf translation tables par kharach hoti hai — yahi pressure Multi-level page tables ko motivate karta hai.

Exercise 3.2

$t_{m e m} = 100 ns$ , $t_{T L B} = 1 ns$ , TLB hit ratio $h = 0.98$ (single-level table). Effective access time (EAT) nikalo.

Recall Solution

Formula dobara banao: hit par, TLB + memory pay karo. Miss par, TLB + ek table walk ( $t_{m e m}$ ) + asli access ( $t_{m e m}$ ) pay karo. $EAT = h (t_{T L B} + t_{m e m}) + (1 - h) (t_{T L B} + t_{m e m} + t_{m e m}) = t_{T L B} + t_{m e m} + (1 - h) t_{m e m}$ $= 1 + 100 + (0.02) (100) = 1 + 100 + 2 = 103 ns$ Kyun sirf $+ 2$ ns: extra table walk sirf unhi $2%$ accesses par pay hoti hai jo TLB miss karte hain. Saare accesses ka average nikalo toh $0.02 \times 100 = 2 ns$ hai. Isliye TLB, Locality of reference exploit karke, translation ko almost free bana deta hai.

Level 4 — Synthesis

Exercise 4.1

$32$ -bit machine par two-level page table jo $4 KiB$ pages use karta hai, $20$ -bit VPN ko $10$ -bit outer index aur $10$ -bit inner index mein split karta hai. Ek process sirf apna pehla $4 KiB$ virtual memory use karta hai (ek page). Maan lo $4$ -byte entries hain aur har table (outer ya inner) ek $4 KiB$ page mein fit hoti hai — actually kitni page-table memory chahiye, count karo.

Recall Solution

Kyun VPN split karte hain: taaki inner tables sirf unhi regions ke liye allocate ho jinhein process actually touch kare. Figure s02 dekho — outer table mein $2^{10}$ slots hain lekin sirf ek real inner table ki taraf point karta hai.

Outer table hamesha exist karta hai: $2^{10}$ entries $\times 4$ bytes $= 4096$ bytes $= 4 KiB$ .
Exactly ek inner table chahiye (process ek page touch karta hai, jo ek outer slot ke neeche rehta hai): aur $2^{10} \times 4 = 4 KiB$ . $Total = 4 KiB + 4 KiB = 8 KiB$ Kyun yeh single-level cost ko crush karta hai: single-level ko $4 MiB$ chahiye tha (Ex 3.1). Two-level ko sparse process ke liye $8 KiB$ chahiye — $512 \times$ saving. Unused outer slots simply khali rehte hain (koi inner table allocate nahi hoti).

Exercise 4.2

Wahi machine (two levels, $t_{m e m} = 100 ns$ , $t_{T L B} = 1 ns$ ). TLB miss par MMU ko dono levels walk karne padte hain (do memory reads) real access se pehle. Hit ratio $h = 0.98$ ke saath, EAT nikalo.

Recall Solution

Kyun do extra reads: ek miss ab outer table padhta hai (1 access) phir inner table (1 access) PFN lane ke liye, phir real data. $EAT = h (t_{T L B} + t_{m e m}) + (1 - h) (t_{T L B} + 2 t_{m e m} + t_{m e m})$ $= 1 + 100 + (0.02) (2 \times 100) = 1 + 100 + 4 = 105 ns$ Kyun pehle ke $+ 2$ ki jagah sirf $+ 4$ : deeper walk $2 t_{m e m} = 200 ns$ cost karta hai $100 ns$ ki jagah, lekin yeh abhi bhi sirf un $2%$ par pay hota hai jo miss karte hain: $0.02 \times 200 = 4 ns$ . Locality ek lambi tree ko bhi sasta rakhti hai.

Level 5 — Mastery

Exercise 5.1

Design check. Tumhe $48$ -bit virtual address space $4 KiB$ pages ke saath support karna hai, aur tum chahte ho ki har level par har page table exactly ek $4 KiB$ page mein fit ho, $8$ -byte entries use karte hue. Page table ko kitne levels chahiye?

Recall Solution

Step 1 — offset. $p = 12$ , toh VPN $48 - 12 = 36$ bits ka hai. Step 2 — har level mein kitne index bits. Ek $4 KiB$ page mein $\frac{2 ^{12} bytes}{8 bytes/entry} = 2^{9} = 512$ entries aati hain, toh har level $9$ VPN bits consume karta hai. Step 3 — divide karo. Levels $= \frac{36 VPN bits}{9 bits/level} = 4$ levels. Answer: 4 levels (yeh exactly real x86-64 ka 4-level scheme hai, PML4 → PDPT → PD → PT). Kyun poora nikalta hai: $36$ exactly $9$ se divisible hai; agar nahi hota, toh top level kam bits use karta (ek partially-filled table).

Exercise 5.2

Capstone. Us $48$ -bit, $4$ -level machine par ( $t_{m e m} = 100 ns$ , $t_{T L B} = 1 ns$ ), ek program ek huge array mein stride karta hai jo almost har access par ek fresh page touch karta hai, isliye TLB hit ratio $h = 0.10$ par gir jaata hai. EAT compute karo, aur ek sentence mein batao ki program ne kaun sa principle violate kiya.

Recall Solution

Ek miss ab chaar levels walk karta hai ( $4 t_{m e m}$ ) phir real access hoti hai: $EAT = h (t_{T L B} + t_{m e m}) + (1 - h) (t_{T L B} + 4 t_{m e m} + t_{m e m})$ $h = 0.10$ daalo: $= 0.10 (1 + 100) + 0.90 (1 + 400 + 100)$ $= 0.10 (101) + 0.90 (501) = 10.1 + 450.9 = 461 ns$ Yeh raw memory time $100 ns$ se $4.6 \times$ zyada slow hai. Principle violated: poor locality of reference — har access par ek naya page touch karke, program TLB ko defeat kar deta hai (dekho Locality of reference), toh almost har access poora $4$ -level walk pay karta hai.

Recall

Recall Ek-line self-test

VA ka kaun sa part translate hota hai? ⟶ VPN; offset copy hota hai.
$32$ -bit VA, $4 KiB$ pages ke liye single-level table entries? ⟶ $2^{20}$ ( $4 MiB$ ).
EAT formula, single level? ⟶ $t_{T L B} + t_{m e m} + (1 - h) t_{m e m}$ .
Multi-level tables memory kyun bachate hain? ⟶ inner tables lazily allocate hoti hain, sirf used regions ke liye.
$48$ -bit VA, $4 KiB$ pages, $8$ -byte entries, $4 KiB$ tables ke liye levels? ⟶ $4$ .