The Cost of Virtual Memory: TLBs and Effective Memory Access Time

Virtual memory provides every user process with a private, uniform address space protected from neighboring applications.

However, address translation incurs an inherent architectural penalty: every memory reference requires translating a virtual address into a physical address.

---

1. The Two-Access Penalty

Because the Page Table is itself a data structure stored in main memory (RAM):

1. Access 1: The MMU reads the Page Table entry in RAM to translate the Virtual Page Number (VPN) into a Physical Frame Number (PFN).
2. Access 2: The CPU accesses the actual data byte at the physical address.

Without hardware acceleration, virtual memory doubles the latency of every instruction! In 64-bit systems with 4-level paging, a naive lookup requires 5 sequential memory accesses per operation.

---

2. The Translation Lookaside Buffer (TLB)

To eliminate this bottleneck, the Memory Management Unit (MMU) incorporates a small, high-speed associative hardware cache: the Translation Lookaside Buffer (TLB).

• Associative Search: All TLB entries are compared simultaneously in parallel, resolving in sub-nanosecond time (c).
• TLB Hit: The VPN is cached in the TLB. The physical frame number is returned immediately, requiring only 1 main memory access.
• TLB Miss: The translation is absent. The MMU must walk the Page Table in RAM, requiring 2 main memory accesses (or k+1 for k-level paging).

---

3. Effective Memory Access Time (EMAT) Formula

Let:

• h = TLB Hit Ratio
• c = TLB Lookup Time
• m = Main Memory Access Time

EMAT = h · (c + m) + (1 - h) · (c + 2m)

Worked Example:

Assume main memory access time m = 100ns, TLB lookup time c = 10ns, and hit ratio h = 98\%:

EMAT = 0.98 · (10 + 100) + 0.02 · (10 + 200)

EMAT = 0.98 · 110 + 0.02 · 210 = 107.8 + 4.2 = 112ns

Despite paging overhead, the Effective Memory Access Time is only 12ns higher than raw physical RAM!

Explore interactive virtual address translation rails at Binary Dose.