TLB (translation lookaside buffer): Worked examples

5.4.12 · D3 · Hardware › Memory Hierarchy & Caches › TLB (translation lookaside buffer)

Prerequisites jo hum use karte hain: Virtual Memory, Page Table, Cache (memory hierarchy), Context Switch, Page Fault, Locality of Reference.

Scenario matrix

Kuch bhi solve karne se pehle, chalte hain har us cheez ki list banate hain jo ek TLB question mein aa sakti hai. Ise poore deck of cards ki tarah socho; neeche ke examples har card ko kam se kam ek baar khelate hain.

#	Scenario class	Kya alag banata hai ise	Covered by
A	TLB hit	translation already cached → no walk	Ex 1
B	Address bit-split	VA ko VPN + offset mein todna non-obvious page sizes ke liye	Ex 2
C	TLB miss, page present	page table walk karo, page RAM mein hai	Ex 3
D	TLB miss → page fault	page RAM mein nahi, disk load chahiye	Ex 4
E	EMAT single-level	performance maths, $W = 1$	Ex 5
F	EMAT multi-level walk	$W = L > 1$ , x86-64 ka case	Ex 6
G	Context switch (flush vs ASID)	stale/wrong-process entries	Ex 7
H	Degenerate / limiting inputs	$h = 1$ , $h = 0$ , $t_{TLB} = 0$	Ex 8
I	Real-world word problem	array pe loop, locality in action	Ex 9
J	Exam twist	given EMAT, ulta solve karo $h$ ke liye	Ex 10

Har cell A–J neeche kaam kiya gaya hai. Chalte hain.

Reminders jo baar baar kaam aayenge (taaki koi symbol unexplained na rahe)

Figure — TLB (translation lookaside buffer)

Figure dekho: address ek ruler hai. Bit position $lo g_{2} P$ pe ek vertical red line ise saaf baant deti hai. Line ke upar kuch bhi kabhi within-page position nahi badalta; line ke neeche kuch bhi kabhi translate nahi hota.

Ex 1 — Scenario A: ek clean TLB hit

Step 1 — kitne offset bits? $P = 4 KiB = 2^{12}$ , toh offset $= 12$ bits. Ye step kyun? 12 bits = exactly 3 hex digits (har hex digit 4 bits ka hota hai), jo split ko hex boundary pe laata hai — acha lagta hai.

Step 2 — VA slice karo. Low 3 hex digits = offset = 0x2C4. Remaining top = 0x1F0AB = VPN. Kyun? Lowest $lo g_{2} P$ bits definition se offset hain; $12/4 = 3$ hex digits.

Step 3 — VPN ko TLB mein lookup karo. 0x1F0AB present hai → hit, PFN = 0x0072. Kyun? Ye scenario A hai: cached translation, toh hum page table bilkul skip karte hain.

Step 4 — PA rebuild karo. $PA = (0x0072 ≪ 12) ∣ 0x2C4 = 0x00072000 ∣ 0x2C4 = 0x000722C4$ . 12 se shift kyun? PFN 0x72 ek 4KiB frame ko name karta hai; uska base byte address $0 x 72 \times 2^{12}$ hai, aur 12 bits left shift karna wohi multiply hai. Phir hum untranslated offset ko emptied low bits mein OR karte hain.

Recall Verify

Offset VA aur PA mein unchanged hai? VA low = 2C4, PA low = 2C4. ✓ $0 x 72 \times 4096 = 0 x 72000$ ; OR 0x2C4 deta hai 0x722C4. ✓ Koi walk nahi hua.

Ex 2 — Scenario B: ek awkward page size (bit-split care)

Step 1 — offset bits. $8 KiB = 2^{13}$ , toh offset $= 13$ bits. Kyun? Wahi rule: $lo g_{2} P$ . Lekin 13, 4 ka multiple nahi hai — toh split hex boundary pe nahi padti. Trap!

Step 2 — VPN width. VPN bits $= 48 - 13 = 35$ bits. Kyun? Total address bits minus offset bits = page number ke liye bacha hua sab kuch.

Step 3 — offset mask banao, phir offset extract karo. Low 13 bits rakhne ke liye hum ek mask se AND karte hain jisme thirteen 1-bits hain. Woh mask hai $2^{13} - 1$ . Compute karo: $2^{13} = 8192$ , toh $2^{13} - 1 = 8191$ , aur $8191 = 0x1FFF$ (chaar hex digits 1FFF = binary 1 1111 1111 1111, jo exactly thirteen 1s hain). Ab 0xABCD binary mein $= 1010101111001101$ (16 bits). 0x1FFF se AND karna low 13 bits rakhta hai — bit 13 (value 0x2000) aur usse upar drop ho jaate hain, bit 12 se neeche sab survive karta hai. 0xABCD ke bits 15–13 hain 101, toh wo clear ho jaate hain; surviving low 13 bits hain 0 1011 1100 1101 = 0x0BCD. Kyun? Offset = lowest 13 bits; ek mask $2^{13} - 1$ "low $n$ bits rakhne" ki standard trick hai kyunki ye bit 13 ke neeche all-ones aur upar all-zeros hota hai.

Step 4 — VPN extract karo. Shift the whole VA right by 13: 0xABCD >> 13 = 0x5 (sirf top 3 bits 101 bachte hain). Kyun? VPN = offset ke upar sab kuch, yaani VA divided by $P$ .

Recall Verify

Mask: $2^{13} - 1 = 8191 = 0x1FFF$ . ✓ 0xABCD & 0x1FFF = 0x0BCD (offset) aur 0xABCD >> 13 = 0x5 (VPN). Reassemble karo: $(VPN ≪ 13) ∣ offset = (5 \times 8192) ∣ 0 x 0 BCD = 0 xA000 ∣ 0 x 0 BCD = 0 xABCD$ . ✓ Round-trip original VA se match karta hai.

Ex 3 — Scenario C: TLB miss, page memory mein hai

Step 1 — TLB lookup fail hoti hai. VPN 0x0055 absent → TLB miss. Kyun? Scenario C: translation simply abhi tak cached nahi tha (cold entry ya evicted).

Step 2 — page-table walk. Hardware DRAM mein page table entry padhta hai → PFN 0x0300, valid = 1. Ye step kyun? Mapping page table mein tab bhi rehti hai jab TLB use bhool jaata hai — TLB ek cache hai, sach ka source nahi (Page Table hai).

Step 3 — no fault, page present. Valid bit = 1 → page physical RAM mein hai. Koi Page Fault nahi, koi disk nahi. Kyun? Ye doosre parent mistake ka poora point hai: ek TLB miss ek fast event hai (ek ya zyada DRAM reads), na ki ek slow wala (disk).

Step 4 — fill aur retry. TLB mein 0x0055 → 0x0300 insert karo, phir access re-run karo → ab hit hoti hai. Kyun? Locality of Reference: is page ke liye agla access ab hit hoga — walk ek baar bharo, kai baar faida uthao.

Recall Verify

Is access ki cost = TLB search + 1 walk read + data read = kuch ns. Koi milliseconds (disk) kahin nahi. ✓

Ex 4 — Scenario D: TLB miss jo page fault ban jaata hai

Step 1 — TLB miss → walk. VPN 0x0400 TLB se absent → TLB miss, toh hardware page-table walk shuru karta hai. Kyun? Kisi bhi miss pe TLB ke paas offer karne ke liye koi translation nahi hoti, aur authoritative mapping sirf Page Table mein DRAM mein rehti hai — toh hume frame jaanne ke liye (ya ki koi nahi hai) page table entry padhni padti hai.

Step 2 — valid bit = 0. Page-table entry kehti hai: RAM mein resident nahi. Ye OS ko ek page fault trap raise karta hai. Kyun? Valid bit woh flag hai jo "RAM mein" aur "disk pe / kabhi allocate nahi hua" ke beech farq karta hai.

Step 3 — OS fault handle karta hai. OS ek free (ya evicted) frame chunta hai, disk se page ko usme padhta hai, page table entry update karta hai (valid = 1, naya PFN), phir return karta hai. Kyun? Sirf software disk layout aur eviction policy jaanta hai; hardware ye nahi kar sakta.

Step 4 — retry, ab TLB miss → walk → hit. Faulting instruction restart hoti hai; is baar walk succeed hoti hai aur TLB fill hoti hai.

Step 5 — cost comparison. DRAM access ≈ 100 ns; disk access ≈ 10 ms $= 10, 000, 000$ ns. Ratio $= 1 0^{7} /100 = 100, 000 \times$ Ex 3 walk se slower. Ye kyun dikhayein? "TLB miss ≠ page fault" ko quantitative banana ke liye: ek nanoseconds ka hai, doosra hundred-thousandfold worse hai.

Recall Verify

$10 ms = 10 \times 1 0^{- 3} s = 1 0^{7} ns$ ; $1 0^{7} /100 = 1 0^{5} = 100, 000$ . ✓

Ex 5 — Scenario E: EMAT, single-level walk

Step 1 — formula mein plug karo. $EMAT = t_{TLB} + t_{m} + (1 - h) W t_{m} = 1 + 100 + (0.05) (1) (100)$ . Ye form kyun? Tum hamesha TLB search + ek data read bharte ho; sirf variable extra walk hai, miss fraction $(1 - h)$ pe charge hota hai.

Step 2 — extra term evaluate karo. $(0.05) (100) = 5$ ns. Kyun? 5% accesses walk karte hain, har ek $t_{m} = 100$ ns cost karta hai; average extra $= 5$ ns.

Step 3 — total. $EMAT = 1 + 100 + 5 = 106$ ns.

Step 4 — no TLB se compare karo. TLB ke bina kuch search karne ki zaroorat nahi, toh $t_{TLB} = 0$ ; aur har access zaroor walk karta hai, effectively $h = 0$ . Formula reduce hota hai: $EMAT_{no TLB} = 0 + t_{m} + (1 - 0) W t_{m} = t_{m} + W t_{m} = 100 + 100 = 200 ns .$ Speedup $= 200/106 \approx 1.89 \times$ . Kyun? Dikhata hai ki TLB ek modest 95% hit rate pe bhi access time almost half kar deta hai — locality ka faida milta hai.

Recall Verify

$1 + 100 + 5 = 106$ . ✓ $200/106 = 1.886 \dots \approx 1.89$ . ✓

Ex 6 — Scenario F: EMAT 4-level walk ke saath (x86-64)

Step 1 — same formula, naya $W$ . $EMAT = 1 + 100 + (0.05) (4) (100)$ . Kyun? Sirf walk length $W$ badi: ek 4-level walk, 1 ki jagah 4 DRAM reads hai.

Step 2 — extra term. $(0.05) (4) (100) = 20$ ns. Kyun? 5% misses mein se har ek ab $4 \times 100 = 400$ ns walking cost karta hai; sab accesses pe average: $0.05 \times 400 = 20$ ns.

Step 3 — total. $EMAT = 1 + 100 + 20 = 121$ ns.

Step 4 — Ex 5 se contrast. Single-level = 106ns, four-level = 121ns. Usi 5% miss rate se ab $4 \times$ zyada nuksan hota hai (20ns vs 5ns extra). Kyun matter karta hai: deeper page tables TLB ko zyada valuable banate hain, kam nahi — isliye real CPUs L2 TLBs add karte hain.

Recall Verify

$1 + 100 + 20 = 121$ . ✓ Extra term ratio $20/5 = 4 = W$ . ✓

Ex 7 — Scenario G: context switch, flush vs ASID

Step 1 — khatara. VPN 0x5 A vs B mein alag frames mean karta hai. Ek stale A-entry B ko PFN 0x0100 pe bhej degi — B A ki memory padhta hai. Ek correctness disaster. Kyun? TLB ko koi idea nahi ki uske paas kiska address space hai jab tak hum batayein nahi.

Step 2 — (i) koi protection nahi. TLB abhi bhi A ka 0x5 → 0x0100 hold karta hai → 0x0100 return karta hai. GALAT. B ko A ka data milta hai. Ye kyun dikhayein? Ye woh failure hai jisko rokne ke liye baaki do options exist karte hain.

Step 3 — (ii) switch pe flush. Switch pe, OS poora TLB clear karta hai. B ka 0x5 pe access ab miss karta hai, B ki page table walk karta hai, sahi 0x0900 milta hai. Kyun? Sahi hai — lekin cold TLB har switch ke turant baad ek miss storm cause karta hai. Context Switch dekho.

Step 4 — (iii) ASID tags. Ek ASID (address-space identifier) ek chhota number hai jo OS har process ke address space ko assign karta hai. Har TLB entry us process ke ASID ke saath tagged hoti hai jis ki woh hai. A ki entry ASID=A tagged hai; B ASID=B ke saath search karta hai, match nahi karta, miss karta hai, walk karta hai, aur 0x5[B] → 0x0900 insert karta hai. Dono entries coexist karti hain. Kyun? Koi flush nahi → A ki entries tab ke liye survive karti hain jab hum switch back karein → kam misses. Modern win.

Recall Verify

B ke liye sahi frame = 0x0900. Options (ii) aur (iii) 0x0900 return karte hain; option (i) 0x0100 return karta hai (galat). ✓

Ex 8 — Scenario H: degenerate & limiting inputs

Step 1 — (a) $h = 1$ . $EMAT = 1 + 100 + (1 - 1) (4) (100) = 1 + 100 + 0 = 101$ ns. Kyun? Kabhi koi miss nahi → walk term vanish ho jaata hai. Tum abhi bhi 1ns TLB search + 100ns data read bharte ho.

Step 2 — (b) $h = 0$ . $EMAT = 1 + 100 + (1) (4) (100) = 1 + 100 + 400 = 501$ ns. Kyun? Har access miss karta hai → har access 4 reads walk karta hai. Ye worst case hai — TLB pure overhead hai (extra 1ns) plus har baar ek full walk.

Step 3 — (c) ideal TLB, $t_{TLB} = 0$ , $h = 1$ . $EMAT = 0 + 100 + 0 = 100$ ns. Kyun? Ek free, always-hitting TLB access time ko exactly ek raw memory read tak reduce kar deta hai — theoretical floor. Tum "bas data ek baar padhne" se beat nahi kar sakte.

Step 4 — range ki sanity. Real EMAT floor (100ns) aur ceiling (501ns) ke beech rehta hai; Ex 6 ka 121ns floor ke karib baitha hai, confirm karta hai ki ek accha hit rate best case ke saath chipka rehta hai.

Recall Verify

(a) $1 + 100 + 0 = 101$ . (b) $1 + 100 + 400 = 501$ . (c) $0 + 100 + 0 = 100$ . ✓ Aur $100 \leq 121 \leq 501$ . ✓

Ex 9 — Scenario I: real-world word problem (loop mein locality)

Step 1 — total accesses. $16 KiB = 16384$ bytes; 4 bytes per int par → $16384/4 = 4096$ accesses. Kyun? Har int read pe ek memory access.

Step 2 — accesses per page. Har 4KiB page mein $4096/4 = 1024$ ints aate hain. Kyun? $4096$ bytes per page $\div 4$ bytes per int.

Step 3 — misses count karo. Har page ke pehle access pe miss hoti hai (cold, TLB mein abhi nahi); usi page ke baaki 1023 accesses hit karte hain. 4 pages ke saath ye deta hai $4 \times 1 = 4$ misses total. Kyun? Ye Locality of Reference concrete bana ke: ek miss 1024 baar usi translation ke use ka "payment" karta hai (spatial locality).

Step 4 — hit rate. $h = \frac{hits}{total} = \frac{4096 - 4}{4096} = \frac{4092}{4096} = 0.99902$ (lagbhag 99.90%). Kyun? Total accesses mein se hits. Sequential scans TLB ke best friend hain.

Recall Verify

$16384/4 = 4096$ accesses; $4096/4 = 1024$ per page; misses $= 4$ ; $h = 4092/4096 = 0.999023 \dots$ ✓

Ex 10 — Scenario J: exam twist (ulta solve karo)

Step 1 — EMAT likho aur miss term isolate karo. $130 = 2 + 100 + (1 - h) (2) (100)$ . Always-paid part subtract karo: $130 - 102 = 28 = (1 - h) (200)$ . Kyun? $t_{TLB} + t_{m} = 102$ har access pe bhara jaata hai; bacha hua $28$ ns walk overhead hona chahiye.

Step 2 — $(1 - h)$ solve karo. $(1 - h) = 28/200 = 0.14$ . Kyun? $W t_{m} = 200$ factor divide out karo.

Step 3 — $h$ solve karo. $h = 1 - 0.14 = 0.86$ (86% hit rate). Kyun? Miss rate $0.14$ hai, toh hit rate uska complement hai.

Step 4 — confirm karne ke liye plug back karo. $EMAT = 2 + 100 + (0.14) (2) (100) = 102 + 28 = 130$ ns. ✓ Kyun? Inverse verify karna: $h = 0.86$ substitute karna given EMAT exactly reproduce karta hai.

Recall Verify

$(1 - 0.86) \cdot 2 \cdot 100 = 0.14 \cdot 200 = 28$ ; $2 + 100 + 28 = 130$ . ✓

Cover-check: kya humne har cell fill kiya?

Har card A–J kheela gaya. Space mein kuch bhi unshown nahi chuta.