TLB — structure, TLB miss handling: Question bank

Before we start, one shared vocabulary reminder so every line below is readable from zero:

Recall The words every question below assumes

VPN (Virtual Page Number) — the high bits of a virtual address that say which page. Call its width $V - p$ bits, where $V$ = total virtual-address width and $p$ = offset width.
PFN (Physical Frame Number) — the high bits of a physical address that say which frame in RAM.
Offset — the low $p$ bits that say where inside a page a byte lives; never translated. Here $p = lo g_{2} (page size)$ .
== $V$ (virtual-address width)== — how many bits a whole virtual address has (e.g. 48).
== $p$ (offset bits)== — the number of low bits selecting a byte within a page (e.g. 12 for a 4 KB page).
TLB miss — the translation wasn't cached, but it may still exist in the page table.
Page fault — the page isn't in physical RAM at all (PTE valid bit = 0).

Before the questions, one picture to anchor the two "who refills the TLB" paths that several traps below hinge on:

Figure — TLB — structure, TLB miss handling

True or false — justify

A TLB miss always causes a page fault.

False. A TLB miss usually just means the translation isn't cached; the hardware walker fetches the valid PTE from the page table in DRAM. A page fault only happens if that walk lands on an invalid PTE.

A TLB hit still requires reading the page table in memory.

False. That is the whole point — a hit gives the VPN→PFN mapping directly from the tiny fast cache, so we skip the multi-level walk entirely.

The page offset is passed through translation unchanged.

True. Translation happens at page granularity, so the bottom

lo g_{2} (page size)

bits (where-inside-the-page) are identical in the virtual and physical address and are copied verbatim.

A larger page size increases the number of offset bits.

True. Offset bits

p = lo g_{2} (page size)

, so doubling the page size adds one offset bit and removes one VPN bit.

Adding an ASID/PCID field to each TLB entry removes the need to ever flush the TLB.

False. It removes the need to flush on ordinary context switches, but you still flush (or recycle) when ASIDs run out or when a mapping actually changes (e.g. a page is freed).

The Global bit means a TLB entry belongs to every process.

True in effect — Global marks kernel pages shared by all address spaces, so those entries match regardless of ASID and survive an ASID-based flush.

A software-managed TLB is slower than a hardware-managed one because it uses more memory accesses on the walk itself.

False (subtle). Both walk the same

k

table levels; software-managed is slower per miss because it takes a trap into an OS handler, which adds pipeline-flush and exception overhead on top of the walk.

In the EMAT model

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

, the TLB lookup time is only paid on a miss.

False.

t_{TLB}

sits outside the parentheses because it is paid on every access — hit or miss — since the TLB is always consulted first.

If the TLB hit ratio

h

reaches 1, EMAT equals

t_{TLB} + t_{m}

True. The walk term is

(1 - h) k

; at

h = 1

it vanishes, leaving lookup plus one data access — exactly the "no walk penalty" case.

Two processes cannot safely have the same virtual address 0x400000 cached in the TLB at once.

False. With ASID/PCID tags, both entries coexist — the tag distinguishes whose 0x400000 it is, mapping to different PFNs.

A CPU core can invalidate a stale TLB entry on another core just by writing to its own TLB.

False. TLBs are per-core and not hardware-coherent with each other; stale copies on other cores must be knocked out by a TLB shootdown (see edge cases), not by a local write.

The instruction TLB and data TLB always hold the same entries.

False. Modern cores split them (iTLB for fetches, dTLB for loads/stores); a page mapped executable-only may live in the iTLB and never enter the dTLB, and vice versa.

Spot the error

"On a TLB miss the CPU immediately traps to the OS."

Error: that's only true for a software-managed TLB. On x86/ARM a hardware page-table walker refills the TLB silently — the OS is never involved unless the walk finds an invalid PTE.

"The physical address is

PFN ≪ (VPN bits)

OR-ed with the offset."

Error: you shift the PFN by the offset width

p

, not by the VPN width.

PA = (PFN ≪ p) ∣ offset

, because the offset must occupy exactly the low

p

bits.

"A fully associative TLB is always the best choice because it has the highest hit rate."

Error: it must compare every tag in parallel, which is power-hungry and area-costly. That's why it's reserved for small L1 TLBs; larger L2 TLBs use set-associative designs to stay affordable.

"After a page fault is serviced, the faulting instruction runs to completion immediately."

Error: the instruction is retried, and the retry typically incurs another TLB miss (then a hit) because the fault only fixed the PTE, it didn't install the entry in the TLB.

"The TLB stores data from recently-used memory pages."

Error: it stores translations (VPN→PFN + metadata), not the page contents. The data cache stores contents; the TLB stores address mappings.

"Number of virtual pages equals

2^{offset bits}

Error: it's

2^{V - p}

, i.e. two-to-the-VPN-bits, where

V

is the virtual-address width and

p

the offset width. Offset bits count bytes within a page, not the number of pages.

"A context switch is safe as long as we flush the TLB, so ASIDs are just an optimization for correctness."

Error: flushing is for performance, not correctness — a flush is always correct. ASIDs are the optimization that lets us avoid the costly flush.

"When one core changes a page mapping, the other cores see it automatically because the TLB is coherent like the data cache."

Error: TLBs are not kept coherent by hardware. The core that changed the mapping must issue a TLB shootdown (typically an inter-processor interrupt) so every other core invalidates its own stale entry.

"An access bit only lives in the PTE, so the TLB never touches it."

Error: hardware sets the accessed (and dirty) bits when a translation is used from the TLB, then propagates them to the in-memory PTE — so the TLB is directly involved in updating that metadata.

Why questions

Why is the page offset never stored as a TLB tag?

Because it isn't translated — it's identical in virtual and physical addresses. Storing it would waste bits and let two accesses to different bytes of the same page miss unnecessarily.

Why does a multi-level page table exist at all, given the TLB?

A flat table for

2^{36}

pages is impossibly large; the multi-level tree stores only populated regions. The TLB caches recent leaves so we rarely pay the

k

-level walk cost.

Why does even a 98% TLB hit rate still hurt performance noticeably?

The 2% of misses each pay a

k

-level walk; with

k = 4

EMAT = t_{TLB} + t_{m} (1 + 0.02 \times 4)

— an 8% penalty on every access, which is why hit rates are pushed toward 99%+.

Why does the Global bit exist separately from ASIDs?

Kernel pages are shared identically by all processes, so tagging them per-process would waste entries and force reloads. Global marks them as belonging to everyone, so they survive ASID flushes.

Why is a set-associative TLB indexed by VPN bits rather than offset bits?

The offset is the same across a page, so indexing by it would map every byte of a page to different sets uselessly. VPN bits are what distinguish pages, so they select the set.

Why can huge pages reduce TLB misses?

One huge-page entry covers far more memory (its "TLB reach"), so fewer distinct entries are needed to map a working set — cutting capacity misses. (See Huge Pages / TLB Reach.)

Why isn't "bigger pages" a free win despite improving TLB reach?

Larger pages cause internal fragmentation (a nearly-empty page still consumes its full size) and complicate allocation/eviction — it's a genuine tradeoff, not a pure gain.

Why do CPUs prefetch translations or use fill buffers during a walk?

A page-table walk stalls the access for several DRAM trips; prefetching the next likely translation (e.g. for sequential pages) and buffering an in-flight fill lets useful work overlap the latency, softening the miss cost that the EMAT model charges in full.

Why must the accessed and dirty bits be handled carefully across the TLB?

If a TLB entry is used many times, hardware may set the PTE's accessed/dirty bit only once and then serve later hits without re-touching memory; the OS's page-replacement logic relies on those bits, so their update timing and any lazy write-back must be correct.

Edge cases

What happens on a TLB miss whose walk finds a PTE with the valid bit = 0?

The miss escalates into a page fault: the OS must bring the page in from disk (or kill the process if the access is illegal), update the PTE, then let the instruction retry. See Page Faults & Demand Paging.

If a page's permissions say read-only but the instruction writes, and the entry is a TLB hit — then what?

A hit does not imply permission. The TLB checks permission bits on hit; a write to a read-only entry raises a protection fault, independent of whether the translation was cached.

What is the physical address when PFN = 0 (frame 0) and offset = 0x1F?

PA = (0 ≪ p) ∣ 0x1F = 0x1F

— a valid PFN of 0 is legal; the offset simply becomes the whole address within frame 0.

When ASIDs are exhausted and must be recycled, what must happen to old entries?

Every TLB entry still tagged with the reused ASID must be flushed, because otherwise a new process could inherit a stale mapping under the recycled tag. This is the case where a flush becomes unavoidable.

Does a TLB entry with valid bit = 1 guarantee the page is in physical RAM?

Yes — a valid cached translation means the walker earlier found a valid PTE pointing to a real frame. The valid=0 case never gets installed in the TLB; it takes the page-fault path instead.

If two virtual addresses in the same process map (aliased) to the same physical frame, how many TLB entries do they need?

Two, one per distinct VPN — the TLB is keyed by VPN, so different virtual pages need separate entries even if they point to the same PFN.

One core unmaps a page that another core has cached in its TLB — what protocol fixes this?

A TLB shootdown: the initiating core sends an inter-processor interrupt to every core that might hold the entry; each runs a handler to invalidate its own TLB entry and acknowledges before the unmap is considered complete. This is a real, measurable cost on many-core systems.

Which TLB(s) must be invalidated when self-modifying code rewrites a page's mapping — the iTLB, the dTLB, or both?

Both, if the page is used for execution and data, because the split iTLB and dTLB cache the same translation independently; missing one leaves a stale copy that only the other structure sees.

When are the accessed and dirty bits set relative to a TLB hit?

On a hit, hardware may set the PTE's accessed bit on first use and the dirty bit on first write, writing them back to memory; some designs fault into the OS to set them, which is a subtle miss-like cost hidden inside an apparent hit.

Recall One-line self-test

Say the single sentence that separates a TLB miss from a page fault. Answer ::: A TLB miss means the translation isn't cached (page table still has it, cost = nanoseconds); a page fault means the page isn't in RAM (cost = milliseconds).