TLB — structure, TLB miss handling: Worked examples

Symbols & vocabulary used on this page

Everything below is used before you meet it in an example — so it lives here, defined in plain words, so you never hit an unexplained symbol.

Definition The words and letters we will lean on

VPN (Virtual Page Number) — the high bits of a virtual address; it names which page you want. Think "the page's ID card."
PFN (Physical Frame Number) — the high bits of a physical address; it names which frame in real RAM holds that page. A "frame" is a page-sized slot in physical memory.
Offset — the low bits of an address; it names which byte inside the page/frame. It is never translated (identical in virtual and physical).
PTE (Page-Table Entry) — one row of the page table living in memory: it records the VPN→PFN mapping plus a valid bit, permissions, etc. The TLB is a cache of these.
$V$ — number of bits in a virtual address.
$p$ — number of offset bits, so page size $= 2^{p}$ bytes.
$h$ — the TLB hit ratio: the fraction of accesses (between $0$ and $1$ ) that find their translation already cached in the TLB. $h = 0.98$ means 98% of accesses hit.
$k$ — the number of levels in the page table: how many memory reads a full hardware walk costs (e.g. $k = 4$ for x86-64).
$t_{TLB}$ — time for one TLB lookup (translate), in nanoseconds.
$t_{m}$ — time for one memory (DRAM) access, in nanoseconds.

The scenario matrix

Before working problems, let us map the entire space of situations. Each row is a class of question; each example below fills one or more cells.

#	Cell (scenario class)	What is tricky about it	Covered by
A	Plain address split (VA → VPN + offset)	getting bit-counts right	Ex 1
B	Form the physical address on a HIT	shift-and-OR, hex arithmetic	Ex 2
C	Degenerate: offset = 0 / access at page boundary	the byte that sits exactly at a page start	Ex 3
D	TLB MISS but PTE valid (walk, then hit)	counting memory accesses	Ex 4
E	MISS that becomes a PAGE FAULT (PTE invalid)	ns vs ms; who does what	Ex 5
F	EMAT numeric (given h, t, k)	plugging the boxed formula	Ex 6
G	Limiting behaviour ( $h \to 1$ , $h \to 0$ )	forecast before computing	Ex 6
H	Context switch / ASID (same VA, two processes)	why entries don't collide	Ex 7
I	Huge page / TLB reach (real-world word problem)	reach = entries × page size	Ex 8
J	Exam twist: reverse-engineer (given PA & VA, find page size)	working backwards	Ex 9
K	Set-associative TLB indexing (which set?)	index bits vs tag bits	Ex 10

We will now hit every cell.

Example 1 — Plain address split (Cell A)

Worked example Split a virtual address

A system has a 32-bit virtual address and 8 KB pages. How many bits are offset, and how many are VPN? How many virtual pages exist?

Forecast: guess the offset bits from the page size alone before reading on. (Hint: $8 KB = 2^{?}$ .)

Step 1. Convert page size to a power of two: $8 KB = 8 \times 1024 = 8192 = 2^{13}$ bytes. Why this step? The offset must address every byte inside one page. If a page holds $2^{13}$ bytes, you need exactly $13$ bits to name a byte inside it — no more, no less.

Step 2. Offset bits $= p = 13$ . Why this step? By definition offset bits $= lo g_{2} (page size)$ , straight from the parent's derived formula.

Step 3. VPN bits $= V - p = 32 - 13 = 19$ . Why this step? Every bit that is not offset must select which page — that is the whole point of the VPN.

Step 4. Number of virtual pages $= 2^{V - p} = 2^{19} = 524288$ . Why this step? With 19 bits naming pages, there are $2^{19}$ distinct page numbers.

Verify: $13 + 19 = 32$ ✔ (all bits accounted for). And $2^{13} \times 2^{19} = 2^{32}$ bytes = the full 4 GB address space ✔.

Example 2 — Form the physical address on a HIT (Cell B)

Worked example Shift-and-OR the frame in

Page size 4 KB ( $p = 12$ ). Virtual address 0xDEADBEEF. The TLB hits: VPN maps to PFN 0x01234. What is the physical address?

Forecast: which hex digits of 0xDEADBEEF survive unchanged? Guess before Step 1.

Step 1. Offset = low 12 bits. $12$ bits $= 3$ hex digits, so offset $=$ 0xEEF. Why this step? Each hex digit is 4 bits; $12/4 = 3$ . The bottom 3 hex digits are "where inside the page," and translation never touches them.

Step 2. Drop the VPN — the TLB has already given us its replacement, PFN 0x01234. Why this step? On a hit we do not reuse the old VPN; the whole job of translation is to swap VPN for PFN.

Step 3. Shift PFN up by $p = 12$ bits (3 hex digits) and OR in the offset: $PA = (0x01234 ≪ 12) ∣ 0xEEF = 0x01234000 ∣ 0xEEF = 0x01234EEF .$ Why this step? Shifting left by 12 makes room for the offset (fills the low 3 hex digits with zeros); OR then slots the untouched offset back in.

Verify: The low 3 hex digits EEF are identical to the VA's low 3 digits ✔ (offset preserved). The high digits 01234 are the frame, not the original DEADB ✔.

Figure — Ex 2 (shift-and-OR): the cyan boxes are the page-number fields (VPN on top, PFN on the bottom — these get swapped); the amber box is the offset. Follow the amber arrow down the right edge: the offset 0xEEF drops straight through untranslated, while the top field changes from DEADB to the frame 01234.

Figure — TLB — structure, TLB miss handling

Example 3 — Degenerate: byte at a page boundary (Cell C)

Worked example Offset = 0

Same 4 KB pages. VA 0x00007000. TLB hits with PFN 0x000AA. Find the PA. Then: what is the PA of the byte one below it, 0x00006FFF?

Forecast: 0x7000 ends in 000 — is this byte the first byte of a page or somewhere in the middle? Guess.

Step 1. Offset of 0x00007000 = low 3 hex digits = 0x000. Why this step? Offset $= 0$ means this address is exactly the start of a page — the degenerate boundary case.

Step 2. VPN of 0x00007000 = 0x00007. PA $= (0x000AA ≪ 12) ∣ 0x000 = 0x000AA000$ . Why this step? With zero offset, the physical address is simply the frame shifted up — nothing to OR in.

Step 3. Now 0x00006FFF: its VPN is 0x00006 — a different page! Its offset is 0xFFF (last byte of that page). Why this step? The boundary is razor-thin: address ...6FFF and ...7000 are adjacent bytes but live in different pages, so they may map to totally different frames and need separate TLB entries.

Verify: 0x7000 - 0x6FFF = 1 byte apart in virtual space ✔, yet they differ in the top 20 bits (0x00007 vs 0x00006) ✔ — proving that crossing a page boundary changes the VPN. A single access that straddled this line would need two translations.

Example 4 — TLB MISS, PTE valid, then hit (Cell D)

Worked example Count the memory accesses

A 4-level page table (x86-64 style, so $k = 4$ ). A load misses in the TLB, but the walk finds a valid PTE. Exactly how many DRAM accesses does this single load cost, and what happens next?

Forecast: guess the total number of memory accesses before reading the steps.

Step 1. TLB lookup → miss. Why this step? The translation simply wasn't cached; the page table still contains it (this is the definition of a plain TLB miss, not a fault).

Step 2. Hardware walker reads $k = 4$ page-table levels, one DRAM access per level. Why this step? The table is hierarchical (from Page Tables (Multi-level)); each level's entry tells you where the next level lives, so you must read them in sequence. This is exactly what $k$ counts in our EMAT formula.

Step 3. PTE is valid → install VPN→PFN into the TLB (possibly evicting an LRU entry), retry the instruction. Why this step? On retry the entry is now cached, so it becomes a hit — no repeat walk.

Step 4. The retried load now performs 1 DRAM access to fetch the actual data. Why this step? Translation only produced the address; you still have to go get the byte.

Verify: Total DRAM accesses $= 4 (walk) + 1 (data) = 5$ . This matches the EMAT model's miss term $(k + 1) t_{m} = 5 t_{m}$ ✔. Note: zero disk access — this is a miss, not a fault.

Example 5 — MISS becomes a PAGE FAULT (Cell E)

Worked example The walk finds an invalid PTE

Same 4-level system. A store misses the TLB; the walker reaches the leaf PTE and its valid bit = 0 (page not in RAM). Trace the events and classify the cost.

Forecast: is this nanoseconds or milliseconds? Guess before Step 4.

Step 1. TLB miss → hardware walk begins (4 DRAM reads). Why this step? Identical start to Example 4 — the CPU cannot know yet whether the page is resident.

Step 2. Leaf PTE read → valid = 0. Why this step? A cleared valid bit means "this virtual page has no physical frame right now" — see Page Faults & Demand Paging.

Step 3. Hardware raises a page-fault exception; control jumps to the OS handler. Why this step? Only privileged OS code may allocate a frame and touch the disk; hardware can't do this alone.

Step 4. OS finds a free frame (or evicts one), reads the page from disk, updates the PTE (valid = 1, sets PFN), returns. Why this step? Disk I/O is the expensive part — milliseconds, ~ $1 0^{4}$ – $1 0^{5} \times$ a DRAM access.

Step 5. Instruction retried → likely TLB miss again → walk → now valid → install → hit. Why this step? The OS only fixed the page table; the TLB still hasn't cached it, so one more (cheap) miss occurs.

Verify: Cost ordering: TLB hit ( $\sim 1$ ns) $≪$ TLB miss + walk ( $\sim$ few hundred ns) $≪$ page fault ( $\sim$ ms). A page fault is ~ $1 0^{6} \times$ costlier than a hit ✔ — which is exactly why the "TLB miss = page fault" belief is a dangerous mistake.

Example 6 — EMAT numeric and limiting behaviour (Cells F & G)

Worked example Compute, then push h to the extremes

Recall the players: $h$ = TLB hit ratio, $t_{TLB}$ = one TLB-lookup time, $t_{m}$ = one memory-access time, $k$ = page-table levels. Using the boxed model $EMAT = t_{TLB} + t_{m} (1 + (1 - h) k)$ with $t_{TLB} = 1 ns$ , $t_{m} = 100 ns$ , $k = 4$ : (a) $h = 0.95$ ? (b) Limit $h \to 1$ ? (c) Worst case $h \to 0$ ?

Forecast: rank the three answers smallest→largest in your head first.

Step 1 (a). $(1 - h) k = 0.05 \times 4 = 0.20$ . Then $EMAT = 1 + 100 (1 + 0.20) = 1 + 120 = 121 ns$ . Why this step? Plug straight into the boxed formula; the miss penalty is $t_{m} \cdot (1 - h) k$ added onto the ideal.

Step 2 (b). As $h \to 1$ (a perfect TLB — every access hits): $(1 - h) k \to 0$ , so $EMAT \to 1 + 100 (1) = 101 ns$ . Why this step? A perfect TLB means every access is one translation ( $t_{TLB}$ ) plus one data fetch ( $t_{m}$ ) — no walk. This is the floor.

Step 3 (c). As $h \to 0$ (every access misses): $(1 - h) k \to 4$ , so $EMAT \to 1 + 100 (1 + 4) = 1 + 500 = 501 ns$ . Why this step? Every access pays the full 4-level walk plus the data fetch = 5 memory accesses. This is the ceiling.

Verify: $101 < 121 < 501$ ✔ matches our forecast ordering. Sanity: at $h = 0.95$ we're 20 ns above the floor, and $0.05 \times (501 - 101) = 0.05 \times 400 = 20$ ✔ — the penalty scales linearly with miss ratio.

Figure — Ex 6 (EMAT vs hit ratio): the cyan curve is EMAT as $h$ sweeps from 0 to 1. Watch the three amber dots: the right end ( $h \to 1$ ) sits at the 101 ns floor, the left end ( $h \to 0$ ) at the 501 ns ceiling, and our worked point $h = 0.95$ sits just above the floor at 121 ns.

Example 7 — Context switch & ASID (Cell H)

Worked example Same virtual address, two processes

Process P (ASID = 3) and process Q (ASID = 7) both access VA 0x00400000. In P it maps to PFN 0x00100; in Q to PFN 0x00500. Page size 4 KB. The scheduler switches P → Q → P. Do we need a TLB flush?

Forecast: without ASIDs, what would P read after switching back? Guess before Step 3.

Step 1. VPN of 0x00400000 = high 20 bits = 0x00400; offset = 0x000. Why this step? Both processes use the identical VPN — that's the collision danger a plain TLB would face.

Step 2. P's entry is tagged {ASID=3, VPN=0x00400 → PFN 0x00100}; Q's is {ASID=7, VPN=0x00400 → PFN 0x00500}. Both live in the TLB simultaneously. Why this step? The ASID field (from the parent's structure table) is part of the tag, so {3, 0x00400} ≠ {7, 0x00400} — no collision.

Step 3. On a lookup, hardware matches VPN and current ASID. Running Q (ASID 7) → matches Q's entry → PA 0x00500000. Switching back to P (ASID 3) → matches P's entry → PA 0x00100000. Why this step? The ASID acts as an extra tag dimension, so a context switch just changes the current ASID register, not the TLB contents — no flush.

Verify: P's PA $= (0x00100 ≪ 12) ∣0 = 0x00100000$ ; Q's PA $= (0x00500 ≪ 12) ∣0 = 0x00500000$ ✔. Same VA, two different physical frames, both correct and coexisting — exactly the mistake ASIDs prevent.

Example 8 — Huge pages & TLB reach (Cell I, word problem)

Worked example Real-world: sizing the reach

A database keeps a 4 GB hot working set. The L1 TLB has 64 entries. (a) With 4 KB pages, how much memory does the TLB "cover" (its reach)? (b) With 2 MB huge pages? (c) Which avoids constant TLB misses over the 4 GB set?

Forecast: guess by how many times huge pages boost reach before computing.

Step 1. Define reach: $reach = (TLB entries) \times (page size)$ . Why this step? Each entry maps exactly one page, so the total memory that can be translated without a miss is entries × page size (see Huge Pages / TLB Reach).

Step 2 (a). $64 \times 4 KB = 64 \times 4096 = 262144 bytes = 256 KB$ . Why this step? 256 KB $⋘$ 4 GB, so scanning the working set thrashes the TLB constantly.

Step 3 (b). $64 \times 2 MB = 128 MB$ . Why this step? Bigger page ⇒ each entry covers 512× more memory ( $2 MB /4 KB = 512$ ), lifting reach from 256 KB to 128 MB.

Step 4 (c). Even 128 MB < 4 GB, but it drastically cuts miss rate; combining huge pages with a larger L2 TLB is the real fix. Why this step? Huge pages help reach but aren't a silver bullet — matching the parent's "bigger pages aren't always better" caveat (fragmentation cost).

Verify: Reach boost factor $= 128 MB /256 KB = 131072/256 = 512$ ✔ — exactly the page-size ratio $2 MB /4 KB$ . Units: entries (count) × bytes/page = bytes ✔.

Example 9 — Exam twist: reverse-engineer the page size (Cell J)

Worked example Work backwards

You observe two translations on the same machine:

VA 0x0000ABCD → PA 0x0007ABCD
VA 0x0000A000 → PA 0x0007A000

From this data alone, deduce the offset width and hence the page size.

Forecast: which bits are identical between each VA and its PA? That identical low run is the offset — guess its width before Step 1.

Step 1. Compare pair 1 bit-by-bit: 0x0000ABCD vs 0x0007ABCD. They agree everywhere except the hex digit at position $1 6^{4}$ (bit 16): 0 becomes 7. So every bit below bit 16 is identical — the low 16 bits (ABCD) passed straight through. Why this step? The offset is by definition the run of low bits that is copied verbatim from VA to PA. The lowest bit that ever changes marks the top of the offset field.

Step 2. Confirm with pair 2: 0x0000A000 vs 0x0007A000. Again the only change is at bit 16 (0→7); the low 16 bits (A000) are untouched. Why this step? One data point could be a coincidence; a second translation showing the same boundary (bit 16) proves it isn't accidental — the offset genuinely ends at bit 16.

Step 3. Therefore offset width $= 16$ bits, so page size $= 2^{16} = 65536 = 64 KB$ . Why this step? Page size $= 2^{p}$ where $p$ is the offset width, straight from the address-breakdown formula.

Step 4. Sanity-name the fields: VPN of both VAs $=$ bits 16+ $=$ 0x0000; PFN $=$ 0x0007. Both VAs map through the same VPN→PFN pair 0x0000 → 0x0007. Why this step? If the page size is right, both sample addresses must fall inside one page — and they do, sharing one mapping.

Verify: Offsets 0xABCD and 0xA000 are both $< 2^{16}$ ✔ (they fit inside a 64 KB page). Reconstruct pair 1: PA $= (PFN 0 x 0007 ≪ 16) ∣ offset 0 x A B C D = 0x0007ABCD$ ✔. Both translations share VPN→PFN 0x0000→0x0007 ✔.

Example 10 — Set-associative TLB indexing (Cell K)

Worked example Which set does a VPN land in?

A 4-way set-associative L2 TLB has 256 sets. Page size 4 KB. For VA 0x9ABCD000, which set index is probed, and what is the tag stored in the matching entry?

Forecast: how many bits are needed to pick one set out of 256? Guess before Step 2.

Step 1. Strip the offset: low 12 bits = 0x000. VPN = remaining 20 bits = 0x9ABCD. Why this step? Set-associative indexing operates on the VPN — the offset is untranslated and plays no part in choosing a set (see Cache Memory & Associativity).

Step 2. Set-index width $= lo g_{2} (256) = 8$ bits. Take the low 8 bits of the VPN as the set index. Why this step? To name one of 256 sets you need exactly 8 bits; by convention the low VPN bits index the set, so consecutive pages spread across different sets (fewer conflicts).

Step 3. Low byte of VPN 0x9ABCD is 0xCD = 1100 1101 = set index 205. The tag is the remaining high VPN bits above the index = 0x9AB. Why this step? The index picks the set; the tag is stored inside the entry so hardware can confirm which of the many VPNs sharing that index actually matches.

Step 4. Inside set 205, all 4 ways are compared against tag 0x9AB in parallel; a match with Valid=1 and the right ASID ⇒ hit. Why this step? 4-way associativity limits the tag comparison to 4 entries (not all 1024), saving power versus a fully-associative TLB while keeping a good hit rate.

Verify: index bits (8) + tag bits (12) = 20 = VPN bits ✔. Set index $0xCD = 12 \times 16 + 13 = 205 < 256$ ✔ (a legal set). Reassemble: tag 0x9AB (high 12) prepended to index 0xCD (low 8) $= 0x9ABCD$ = the original VPN ✔.

Recall Quick self-test — cover the answers

What does VPN stand for, and which part of the address is it? ::: Virtual Page Number — the high bits naming which page What does PFN stand for? ::: Physical Frame Number — the high bits naming which frame in RAM A plain TLB miss with a 4-level walk costs how many DRAM accesses (incl. data)? ::: 5 (4 walk + 1 data) Same VA in two processes stays correct in the TLB because of what field? ::: ASID/PCID tag Reach of a 64-entry TLB with 2 MB pages? ::: 128 MB As $h \to 1$ with $t_{TLB} = 1, t_{m} = 100$ , EMAT tends to? ::: 101 ns Byte 0x6FFF and 0x7000 (4 KB pages) share a page? ::: No — different VPNs (0x6 vs 0x7) A 256-set TLB, page 4 KB, VA 0x9ABCD000 probes which set? ::: Set 205 (0xCD), tag 0x9AB