TLB (translation lookaside buffer): Question bank — Hardware deep dive

Recall Before you start — the vocabulary and symbols you must have

Words:

VPN = virtual page number, the "which page" part of a virtual address.
PFN = physical frame number, the "which frame in DRAM" the page lives in.
Offset = the byte position inside a page; never translated.
Walk = reading the Page Table in memory to find the PFN when the TLB doesn't know it.

Symbols used in the timing formula on this page:

$t_{TLB}$ = time to search the TLB (one small fast lookup, e.g. $\sim 1$ ns).
$t_{m}$ = time for one memory (DRAM) access (e.g. $\sim 100$ ns).
$W$ = the number of memory reads one walk costs. A single-level Page Table needs $W = 1$ read; an $L$ -level table needs $W = L$ reads (x86-64 uses $L = 4$ ). So a walk costs $W \cdot t_{m}$ in time.
$h$ = TLB hit rate (fraction of accesses found in the TLB, $0 \leq h \leq 1$ ).
EMAT = Effective Memory Access Time, the average time per access once hits and misses are blended.

If any of these feel shaky, revisit the parent note first — the traps assume you own them.

The pictures you need first

The traps below all lean on three mental images. Look at them before the questions.

1 — Why the offset bypasses the TLB (bit-level breakdown). Split any virtual address into two fields: the high bits (VPN) and the low $lo g_{2} P$ bits (offset). Only the VPN is looked up; the offset is copied straight across into the physical address.

Figure — TLB (translation lookaside buffer)

Look at the figure: the VPN box on the left is the only thing that enters the TLB and comes out changed (VPN→PFN). The offset box is drawn as a straight horizontal wire — it never touches the TLB. That is the whole reason "the offset is never translated": bytes keep their position inside the page, so their low bits are identical in VA and PA.

2 — Hit path vs miss path (where the time goes). The next figure traces the two routes an access can take. On a hit you pay $t_{TLB} + t_{m}$ . On a miss you additionally pay the walk $W \cdot t_{m}$ before the same final data access.

3 — The size-vs-speed trade-off (why "bigger is better" is false). A larger, more-associative TLB raises the hit rate $h$ but also lengthens the search time $t_{TLB}$ , and that search sits on the critical path of every access. The next figure shows EMAT as the sum of those two opposing effects.

Formula Where the EMAT formula comes from (the "why")

Every access does two things no matter what: it searches the TLB ( $t_{TLB}$ ) and eventually does one data access ( $t_{m}$ ). The only difference is whether it also walks.

With probability $h$ (a hit): cost $= t_{TLB} + t_{m}$ .
With probability $1 - h$ (a miss): cost $= t_{TLB} + W t_{m} + t_{m}$ (the extra $W t_{m}$ is the walk).

Blend them by their probabilities — an average is each outcome times how often it happens: $EMAT = h (t_{TLB} + t_{m}) + (1 - h) (t_{TLB} + W t_{m} + t_{m})$ The parts present in both brackets ( $t_{TLB} + t_{m}$ ) survive whatever $h$ is, so factor them out: $EMAT = t_{TLB} + t_{m} + (1 - h) W t_{m}$ Read it as: "always search + always one access + (miss fraction)×(walk cost)." The walk is the only optional term, and it is scaled by exactly how often you miss.

True or false — justify

The TLB is a cache of translations, not of data

True. It stores VPN→PFN mappings (plus permission bits), not the bytes at those addresses; the actual data still lives in the data Cache (memory hierarchy) or DRAM.

A TLB hit means the data you want is already in the CPU cache

False. A hit only means the translation (VPN→PFN) is known; the physical address it yields may still miss in the data cache and need a DRAM read.

On a TLB miss the CPU must always go to disk

False. A miss means the translation isn't cached, but the page is usually still in DRAM — you just walk the Page Table. Only a genuine Page Fault touches disk.

Flushing the TLB on a Context Switch is always necessary

False. It's only necessary if entries are not tagged. With ASID/PCID tags each entry carries its owning address space, so entries for different processes coexist safely without a flush.

Increasing the page size reduces the number of TLB entries needed to cover a given amount of memory

True. One entry covers a whole page, so bigger pages mean each entry maps more bytes — the same TLB "reach" needs fewer entries, raising the effective hit rate.

The offset bits are the same in the virtual and physical address

True. Paging relocates a whole page into a frame but never rearranges bytes inside it, so the low

lo g_{2} P

bits pass through translation untouched (see figure 1).

A fully-associative TLB can never suffer a conflict miss

True. Any entry may go in any slot, so misses are only capacity (or cold/compulsory) misses, never conflict misses caused by mapping collisions.

Doubling the TLB size always lowers effective access time

False. A bigger, more-associative TLB raises

h

but also raises

t_{TLB}

(more entries to compare in parallel), and

t_{TLB}

is paid on every access. When the added

Δ t_{TLB}

exceeds the saved

(Δ h) W t_{m}

, EMAT goes up — exactly the crossover shown in figure 3.

If the hit rate

h = 1

, the walk cost disappears from EMAT

True. In

EMAT = t_{TLB} + t_{m} + (1 - h) W t_{m}

the factor

(1 - h)

becomes

0

, leaving just the TLB search plus one data access — no walk is ever paid.

Spot the error

"To translate address 0x12ABC, we send all bits through the TLB."

Wrong: only the VPN (high bits) is looked up. The offset 0xABC bypasses the TLB entirely and is copied straight into the physical address (figure 1).

"A TLB miss and a page fault are two names for the same event."

Wrong: a TLB miss is resolved by a fast Page Table walk in memory; a Page Fault means the page isn't resident and the OS must fetch it from disk — thousands of times slower.

"We form the physical address by adding the offset to the PFN."

Wrong: you shift the PFN left by

lo g_{2} P

first (to reach the frame's base byte), then OR the offset in. Plain addition would corrupt bits that overlap the offset field.

"After a flush the TLB immediately runs at its old hit rate."

Wrong: a flushed TLB is cold. The next accesses all miss until translations refill, causing a temporary "miss storm" and slower running right after the switch.

"Because the TLB is a cache, a bigger TLB is like a bigger cache — strictly better."

Wrong: unlike a large L2/L3 data cache off the critical path, the TLB is consulted on every access, so its latency

t_{TLB}

directly taxes throughput. Size trades against speed here (figure 3).

"If the OS unmaps a page, the change takes effect instantly on all cores."

Wrong: other cores may still hold the stale entry in their TLBs. A TLB shootdown (an inter-processor interrupt) is needed to make them invalidate it.

"The valid/permission bits are stored in the page table, so the TLB doesn't need them."

Wrong: the TLB caches those bits alongside the PFN so it can enforce read/write/execute and user/kernel checks without a walk on every access.

Why questions

Why does the TLB exist at all instead of just reading the page table each time?

Because a page-table read lives in DRAM, so every access would cost at least one extra memory read (up to

W = L

reads for an

L

-level table). Caching recent translations exploits Locality of Reference to skip that walk almost always.

Why does the TLB work — what property of programs makes it effective?

Locality of Reference: programs revisit the same few pages repeatedly, so a small set of cached translations covers the vast majority of accesses.

Why is the offset deliberately left out of the translation?

Paging moves whole pages as units; a byte's position inside its page is invariant (figure 1), so translating the offset would be redundant work and would break the addressing scheme.

Why do multi-level page tables make the TLB more valuable, not less?

A walk of an

L

-level table costs

W = L

DRAM reads. The TLB avoids that whole chain on a hit, so the deeper the table (larger

W

), the larger the penalty

(1 - h) W t_{m}

it saves.

Why can two processes both hold "VPN 0x5" in the TLB simultaneously without confusion?

Only if entries are tagged with an ASID/PCID identifying the address space. The hardware matches both the VPN and the tag, so each process sees its own mapping.

Why does a small drop in hit rate hurt so much?

The extra cost term

(1 - h) W t_{m}

scales linearly with the miss fraction, and each miss pays a full walk of

W

memory accesses; even a few percent more misses adds many expensive walks.

Why is a multi-level (L1 + L2) TLB used instead of one medium TLB?

To get both speed and coverage: the tiny L1 TLB answers most accesses with a small

t_{TLB}

, while the larger slower L2 TLB catches L1 misses before resorting to a full page-table walk — mirroring the data Cache (memory hierarchy) hierarchy.

Edge cases

What happens on the very first access to a brand-new page after boot (cold TLB)?

It is a compulsory TLB miss: nothing is cached yet, so a walk fills the entry. Nothing is wrong — cold misses are unavoidable and self-correcting.

If the hit rate is

0

, what does EMAT reduce to?

EMAT = t_{TLB} + t_{m} + W t_{m} = t_{TLB} + (W + 1) t_{m}

: you pay the TLB search, the full walk, and the final data access on every single reference — the worst case.

What if a TLB entry is present but its permission bit forbids the operation (e.g. writing a read-only page)?

It is a hit for translation but a protection fault: the TLB supplies the PFN yet the permission check fails, so the hardware raises a fault instead of completing the access.

What happens to the TLB when the same VPN maps to a new PFN after the OS remaps it?

The old entry is now stale and must be invalidated (locally, and via shootdown on other cores) before it hands out the wrong PFN; otherwise the process reads the wrong frame.

If page size

P

equals the whole address space, how many offset bits and VPN bits exist?

All address bits become offset (

lo g_{2} P

of them) and the VPN is

0

bits — a single "page," so translation is trivial and the TLB is pointless. A degenerate but instructive limit.

What if a program's working set is larger than the TLB can hold?

The TLB thrashes: entries are evicted before reuse, hit rate collapses toward the cold case, and EMAT climbs — the same capacity-miss failure mode as any Cache (memory hierarchy).