</>EmbeddedInterview

What is a TLB, and how do you calculate the effective memory access time?

MediumOperating System Concepts

Short answer: The TLB (Translation Lookaside Buffer) is a small, fast cache inside the MMU that holds recent virtual-to-physical translations. On a hit, the translation is available immediately; on a miss, the hardware (or OS) must walk the page tables in memory first. Effective access time = hit rate × (time on a hit) + miss rate × (time on a miss).

Worked example 1

  • Memory access: 100 ns. TLB lookup: assume it overlaps with the cache access (≈ 0 ns).
  • Two-level page table: a miss needs 2 extra memory reads.
  • Hit rate 98%.
EAT = 0.98 × 100 + 0.02 × (2 × 100 + 100)
    = 98 + 6 = 104 ns       (4% slower than with no translation at all)

With a 4-level table, a miss costs 500 ns: 0.98 × 100 + 0.02 × 500 = 108 ns.

Worked example 2 (required hit rate)

A page-table walk takes 40 times as long as a TLB lookup t. What hit rate keeps the average translation time at 2t?

h·t + (1 − h)·(t + 40t) = 2t
t + (1 − h)·40t        = 2t
(1 − h)                = 1/40  →  h = 97.5 %

TLB facts worth mentioning

  • Typical sizes: an L1 data TLB of 32–64 entries and a unified L2 TLB of 512–2048 entries. Cortex-A53, for example, has small micro-TLBs per side plus a 512-entry main TLB.
  • TLB reach = entries × page size. 1024 entries × 4 KB = 4 MB. With 2 MB huge pages, the same 1024 entries cover 2 GB. That is why databases, JVMs and VMs benefit from huge pages.
  • ASIDs (ARM) / PCIDs (x86) tag entries with the process, so a context switch does not require flushing the TLB. ARM also tags with VMID for virtual machines.
  • When the kernel changes a mapping, it must invalidate the stale TLB entries (TLBI instructions on ARM64, broadcast to other cores in the inner-shareable domain), which is called a TLB shootdown on x86.

Follow-up: "Why is the TLB hit rate usually so high?" Locality: programs access the same pages repeatedly (loops, stack, hot data), and one entry covers 4096 bytes of consecutive addresses.