The Translation Lookaside Buffer (TLB)

Why the TLB exists

A multi-level page-table walk requires multiple memory accesses for a single data access. Five-level paging (as in the 2025 exam) means six memory accesses per logical access — five PTE fetches plus the data. Without caching, this multiplies memory latency by a factor of 5–6.

The TLB (Translation Lookaside Buffer) is a small, fast, fully-associative cache inside the CPU that stores recently-used virtual-to-physical translations. On each memory access, the CPU first checks the TLB. If the translation is cached (TLB hit), the physical address is available immediately — no page-table walk.

TLB organisation

The TLB is typically small: tens to hundreds of entries (the Intel L1 D-TLB has 64 entries for 4 KB pages). Each entry contains:

• A tag (part of the virtual page number)
• The physical frame number
• Permission bits (R/W, U/S, NX)
• A process identifier (PCID or ASID) so entries for different processes can coexist without flushing

The TLB is fully associative (or set-associative with high associativity), meaning that the virtual page number is compared against all entries in parallel (content-addressable memory, CAM). This makes TLB lookup fast — typically 1 CPU cycle — but limits TLB size (CAM is power-hungry and area-expensive).

Effective Access Time (EAT)

Without paging, memory access time is simply $T_\text{mem}$. With paging and a TLB:

$\text{EAT} = \alpha \cdot (T_\text{tlb} + T_\text{mem}) + (1 - \alpha) \cdot (T_\text{tlb} + k \cdot T_\text{mem} + T_\text{mem})$

where:

• $\alpha$ = TLB hit rate
• $T_\text{tlb}$ = TLB lookup time (typically ≤ 1 cycle)
• $T_\text{mem}$ = memory access time
• $k$ = number of page-table levels that must be walked on a miss

The hit-rate $\alpha$ is typically 0.99 or better, so the TLB miss penalty is amortised to near-zero. For the 2025 paper question: $T_\text{mem} = 40$ ns, $T_\text{tlb} = 5$ ns, $\alpha = 0.99$, $k = 5$:

$\text{EAT} = 0.99 \times (5 + 40) + 0.01 \times (5 + 5 \times 40 + 40)$ $= 0.99 \times 45 + 0.01 \times 245$ $= 44.55 + 2.45 = 47 \text{ ns}$

Without a TLB, every access would cost $6 \times 40 = 240$ ns. The TLB reduces this to 47 ns — a 5× improvement.

TLB reach

The TLB reach is the total amount of memory that can be addressed from TLB-resident translations without a miss:

$\text{TLB reach} = \text{TLB entries} \times \text{page size}$

A TLB with 64 entries and 4 KB pages covers $64 \times 4\text{ KB} = 256\text{ KB}$. This is much smaller than a typical working set (tens to hundreds of MB). TLBs cope because of spatial and temporal locality — a process repeatedly accesses a small set of pages over short intervals.

Larger page sizes (2 MB huge pages, 1 GB gigantic pages) dramatically increase TLB reach without adding TLB entries. A single huge-page entry covers 512× the memory of a 4 KB page, which is why huge pages are crucial for applications with large working sets (databases, VMs).

TLB shootdowns

When the kernel modifies a page-table entry (e.g., unmaps a page, changes its permissions), the TLB may contain a stale translation. The kernel must invalidate the corresponding TLB entry (using the INVLPG instruction on x86). On a multi-core system, the kernel must also send an inter-processor interrupt (IPI) to other cores whose TLBs may have the same entry — a TLB shootdown. Shootdowns are expensive and a source of scalability bottlenecks.

Summary

• The TLB caches virtual-to-physical translations, avoiding page-table walks on hits.
• EAT formula weighs hit latency against miss penalty; typical hit rates exceed 99%.
• TLB reach (entries × page size) limits the working set that fits in the TLB; huge pages extend reach.
• TLB shootdowns are expensive inter-core synchronisation operations required when page tables change.