Worked examples — TLB (translation lookaside buffer)

Prerequisites we lean on: Virtual Memory, Page Table, Cache (memory hierarchy), Context Switch, Page Fault, Locality of Reference.

---

The scenario matrix

Before solving anything, let's list every kind of thing a TLB question can throw at you. Think of this as the full deck of cards; the examples below play every card at least once.

#	Scenario class	What makes it different	Covered by
A	TLB hit	translation already cached → no walk	Ex 1
B	Address bit-split	slicing VA into VPN + offset for non-obvious page sizes	Ex 2
C	TLB miss, page present	walk the page table, page is in RAM	Ex 3
D	TLB miss → page fault	page not in RAM, disk load needed	Ex 4
E	EMAT single-level	performance maths, $W=1$	Ex 5
F	EMAT multi-level walk	$W=L>1$, the x86-64 case	Ex 6
G	Context switch (flush vs ASID)	stale/wrong-process entries	Ex 7
H	Degenerate / limiting inputs	$h=1$, $h=0$, $t_{\text{TLB}}=0$	Ex 8
I	Real-world word problem	loop over an array, locality in action	Ex 9
J	Exam twist	given EMAT, solve backwards for $h$	Ex 10

Every cell A–J below is worked. Let's go.

---

Reminders you'll reuse (so no symbol appears unexplained)

Look at the figure: the address is a ruler. A vertical red line at bit position ${\log }_{2}P$ cleanly divides it. Nothing above the line ever changes the within-page position; nothing below the line is ever translated.

---

Ex 1 — Scenario A: a clean TLB hit

Step 1 — how many offset bits? $P=4\text{KiB}=2^{12}$, so offset $=12$ bits. Why this step? 12 bits = exactly 3 hex digits (each hex digit is 4 bits), which makes the split land on a hex boundary — nice.

Step 2 — slice the VA. Low 3 hex digits = offset = 0x2C4. Remaining top = 0x1F0AB = VPN. Why? The lowest ${\log }_{2}P$ bits are the offset by definition; $12/4=3$ hex digits.

Step 3 — look up VPN in TLB. 0x1F0AB is present → hit, PFN = 0x0072. Why? This is scenario A: cached translation, so we skip the page table entirely.

Step 4 — rebuild the PA. $\text{PA}=(\text{0x0072}\ll 12)|\text{0x2C4}=\text{0x00072000}|\text{0x2C4}=\text{0x000722C4}$. Why shift by 12? PFN 0x72 names a 4KiB frame; its base byte address is $0x72\times 2^{12}$, and shifting left 12 bits is that multiply. Then we OR the untranslated offset into the emptied low bits.

Recall Verify

Offset unchanged in VA and PA? VA low = 2C4, PA low = 2C4. ✓ $0x72\times 4096=0x72000$; OR 0x2C4 gives 0x722C4. ✓ No walk occurred.

---

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

Step 1 — offset bits. $8\text{KiB}=2^{13}$, so offset $=13$ bits. Why? Same rule: ${\log }_{2}P$. But 13 is not a multiple of 4 — so the split does not fall on a hex boundary. Trap!

Step 2 — VPN width. VPN bits $=48-13=35$ bits. Why? Total address bits minus offset bits = everything left for the page number.

Step 3 — build the offset mask, then extract the offset. To keep the low 13 bits we AND with a mask of thirteen 1-bits. That mask is $2^{13}-1$. Compute it: $2^{13}=8192$, so $2^{13}-1=8191$, and $8191=\text{0x1FFF}$ (four hex digits 1FFF = binary 1 1111 1111 1111, which is exactly thirteen 1s). Now 0xABCD in binary $=1010101111001101$ (16 bits). AND with 0x1FFF keeps the low 13 bits — bit 13 (value 0x2000) and above are dropped, everything from bit 12 down stays. Bits 15–13 of 0xABCD are 101, so they are cleared; the surviving low 13 bits are 0 1011 1100 1101 = 0x0BCD. Why? Offset = lowest 13 bits; a mask $2^{13}-1$ is the standard "keep the low $n$ bits" trick because it is all-ones below bit 13 and all-zeros above.

Step 4 — extract VPN. Shift the whole VA right by 13: 0xABCD >> 13 = 0x5 (only the top 3 bits 101 survive). Why? VPN = everything above the offset, i.e. VA divided by $P$.

Recall Verify

Mask: $2^{13}-1=8191=\text{0x1FFF}$. ✓ 0xABCD & 0x1FFF = 0x0BCD (offset) and 0xABCD >> 13 = 0x5 (VPN). Reassemble: $(\text{VPN}\ll 13)|\text{offset}=(5\times 8192)|0\text{x}0\text{BCD}=0\text{xA000}|0\text{x}0\text{BCD}=0\text{xABCD}$. ✓ Round-trip matches the original VA.

---

Ex 3 — Scenario C: TLB miss, page is in memory

Step 1 — TLB lookup fails. VPN 0x0055 absent → TLB miss. Why? Scenario C: translation simply wasn't cached yet (cold entry or evicted).

Step 2 — page-table walk. Hardware reads the page table entry in DRAM → PFN 0x0300, valid = 1. Why this step? The mapping still lives in the page table even when the TLB forgot it — the TLB is a cache, not the source of truth (Page Table is).

Step 3 — no fault, page present. Valid bit = 1 → page is in physical RAM. No Page Fault, no disk. Why? This is the whole point of the second parent mistake: a TLB miss is a fast event (one or more DRAM reads), not a slow one (disk).

Step 4 — fill and retry. Insert 0x0055 → 0x0300 into the TLB, then re-run the access → now it hits. Why? Locality of Reference: the next access to this page will now be a hit — we pay the walk once, benefit many times.

Recall Verify

Cost of this access = TLB search + 1 walk read + data read = a handful of ns. No milliseconds (disk) anywhere. ✓

---

Ex 4 — Scenario D: TLB miss that becomes a page fault

Step 1 — TLB miss → walk. VPN 0x0400 absent from the TLB → TLB miss, so hardware starts a page-table walk. Why? On any miss the TLB has no translation to offer, and the authoritative mapping lives only in the Page Table in DRAM — so we must read the page table entry to learn the frame (or that there isn't one yet).

Step 2 — valid bit = 0. The page-table entry says: not resident in RAM. This raises a page fault trap to the OS. Why? The valid bit is the flag that distinguishes "in RAM" from "on disk / never allocated."

Step 3 — OS handles the fault. OS picks a free (or evicted) frame, reads the page from disk into it, updates the page table entry (valid = 1, new PFN), then returns. Why? Only software knows the disk layout and eviction policy; hardware can't do this.

Step 4 — retry, now TLB miss → walk → hit. The faulting instruction restarts; this time the walk succeeds and fills the TLB.

Step 5 — cost comparison. DRAM access ≈ 100 ns; disk access ≈ 10 ms $=10,000,000$ ns. Ratio $=10^7/100=100,000\times$ slower than the Ex 3 walk. Why show this? To make "TLB miss ≠ page fault" quantitative: one is nanoseconds, the other is a hundred-thousandfold worse.

Recall Verify

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

---

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

Step 1 — plug into the formula. $\text{EMAT}=t_{\text{TLB}}+t_m+(1-h)W{t}_m=1+100+(0.05)(1)(100)$. Why this form? You always pay TLB search + one data read; the only variable extra is the walk, charged on the miss fraction $(1-h)$.

Step 2 — evaluate the extra term. $(0.05)(100)=5$ ns. Why? 5% of accesses walk, each costing one $t_m=100$ns; average extra $=5$ns.

Step 3 — total. $\text{EMAT}=1+100+5=106$ ns.

Step 4 — compare to no TLB. Without a TLB there is nothing to search, so $t_{\text{TLB}}=0$; and every access must walk, so effectively $h=0$. The formula reduces to ${\text{EMAT}}_{\text{no TLB}}=0+t_m+(1-0)W{t}_m=t_m+W{t}_m=100+100=200\text{ ns}.$ Speedup $=200/106\approx 1.89\times$. Why? Shows the TLB nearly halves access time even at a modest 95% hit rate — locality pays off.

Recall Verify

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

---

Ex 6 — Scenario F: EMAT with a 4-level walk (x86-64)

Step 1 — same formula, new $W$. $\text{EMAT}=1+100+(0.05)(4)(100)$. Why? Only the walk length $W$ changed: a 4-level walk is 4 DRAM reads instead of 1.

Step 2 — extra term. $(0.05)(4)(100)=20$ ns. Why? Each of the 5% misses now costs $4\times 100=400$ns of walking; averaged over all accesses: $0.05\times 400=20$ns.

Step 3 — total. $\text{EMAT}=1+100+20=121$ ns.

Step 4 — contrast with Ex 5. Single-level = 106ns, four-level = 121ns. The same 5% miss rate now hurts $4\times$ more (20ns vs 5ns extra). Why it matters: deeper page tables make the TLB more valuable, not less — which is why real CPUs add L2 TLBs.

Recall Verify

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

---

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

Step 1 — the danger. VPN 0x5 means different frames in A vs B. A stale A-entry would send B to PFN 0x0100 — B reads A's memory. A correctness disaster. Why? The TLB has no idea whose address space it holds unless we tell it.

Step 2 — (i) no protection. TLB still holds A's 0x5 → 0x0100 → returns 0x0100. WRONG. B gets A's data. Why show it? This is the failure the other two options exist to prevent.

Step 3 — (ii) flush on switch. On the switch, the OS clears the whole TLB. B's access to 0x5 now misses, walks B's page table, gets correct 0x0900. Why? Correct — but the cold TLB causes a miss storm right after every switch. See Context Switch.

Step 4 — (iii) ASID tags. An ASID (address-space identifier) is a small number the OS assigns to each process's address space. Each TLB entry is tagged with the ASID of the process it belongs to. A's entry is tagged ASID=A; B searches with ASID=B, doesn't match, misses, walks, and inserts 0x5[B] → 0x0900. Both entries coexist. Why? No flush → A's entries survive for when we switch back → fewer misses. Modern win.

Recall Verify

Correct frame for B = 0x0900. Options (ii) and (iii) return 0x0900; option (i) returns 0x0100 (wrong). ✓

---

Ex 8 — Scenario H: degenerate & limiting inputs

Step 1 — (a) $h=1$. $\text{EMAT}=1+100+(1-1)(4)(100)=1+100+0=101$ns. Why? No misses ever → the walk term vanishes. You still pay the 1ns TLB search + 100ns data read.

Step 2 — (b) $h=0$. $\text{EMAT}=1+100+(1)(4)(100)=1+100+400=501$ns. Why? Every access misses → every access walks 4 reads. This is the worst case — the TLB is pure overhead (the extra 1ns) plus a full walk each time.

Step 3 — (c) ideal TLB, $t_{\text{TLB}}=0$, $h=1$. $\text{EMAT}=0+100+0=100$ns. Why? A free, always-hitting TLB reduces access time to exactly one raw memory read — the theoretical floor. You can't beat "just read the data once."

Step 4 — sanity of the range. Real EMAT lives between the floor (100ns) and the ceiling (501ns); Ex 6's 121ns sits near the floor, confirming a good hit rate hugs the best case.

Recall Verify

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

---

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

Step 1 — total accesses. $16\text{KiB}=16384$ bytes; at 4 bytes per int → $16384/4=4096$ accesses. Why? One memory access per int read.

Step 2 — accesses per page. Each 4KiB page holds $4096/4=1024$ ints. Why? $4096$ bytes per page $÷4$ bytes per int.

Step 3 — count misses. The first access to each page misses (cold, not yet in the TLB); the other 1023 accesses to that same page hit. With 4 pages that gives $4\times 1=4$ misses total. Why? This is Locality of Reference made concrete: one miss "pays" for 1024 uses of the same translation (spatial locality).

Step 4 — hit rate. $h=\frac{\text{hits}}{\text{total}}=\frac{4096-4}{4096}=\frac{4092}{4096}=0.99902$ (about 99.90%). Why? Hits over total accesses. Sequential scans are the TLB's best friend.

Recall Verify

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

---

Ex 10 — Scenario J: the exam twist (solve backwards)

Step 1 — write EMAT and isolate the miss term. $130=2+100+(1-h)(2)(100)$. Subtract the always-paid part: $130-102=28=(1-h)(200)$. Why? $t_{\text{TLB}}+t_m=102$ is paid on every access; the leftover $28$ns must be the walk overhead.

Step 2 — solve for $(1-h)$. $(1-h)=28/200=0.14$. Why? Divide out the $W{t}_m=200$ factor.

Step 3 — solve for $h$. $h=1-0.14=0.86$ (86% hit rate). Why? The miss rate is $0.14$, so the hit rate is its complement.

Step 4 — plug back to confirm. $\text{EMAT}=2+100+(0.14)(2)(100)=102+28=130$ns. ✓ Why? Verifying the inverse: substituting $h=0.86$ reproduces the given EMAT exactly.

Recall Verify

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

---

Cover-check: did we fill every cell?

Every card A–J is played. Nothing in the space is left unshown.