TLB & Effective Access Time
Scenario
Imagine having to look up a friend's phone number in a massive physical phone book every single time you want to text them. That's exactly what standard paging forces the CPU to do.
Mental model
The TLB is a sticky-note on your monitor with your most frequently dialed numbers, saving you a trip to the phone book.
Translation Lookaside Buffer (TLB) is a small, ultra-fast hardware cache specifically for page table entries. If the page you need is in the TLB, you get the physical address instantly. If not, you pay the penalty of going to the main memory 'phone book'.
Explanation
To understand the Translation Lookaside Buffer (TLB), we must first recognize the massive performance flaw in standard paging. Because page tables are stored in main memory, every memory access requested by the CPU actually requires *two* memory accesses: one to read the page table entry to find the physical frame, and a second to actually read or write the data at that physical address. Since memory access is notoriously slow compared to CPU speed, this effectively halves the computer's performance.
To solve this, hardware designers introduced the TLB, a specialized hardware cache located inside the Memory Management Unit (MMU). The TLB stores a small number of recent virtual-to-physical address translations. When the CPU generates a virtual address, the MMU first checks the TLB in parallel. If the translation is found (a TLB hit), the physical address is produced immediately, skipping the page table lookup entirely. If the translation is missing (a TLB miss), the MMU must walk the page table in memory, retrieve the physical address, and then cache that mapping in the TLB for future use.
The performance impact of the TLB is measured using Effective Access Time (EAT). Instead of a rigid formula, think of EAT as a weighted average of two scenarios: hitting the TLB versus missing it. If you hit the TLB, the time taken is just the TLB search time plus one memory access for the data. If you miss, the time taken is the TLB search time, plus a memory access for the page table, plus a memory access for the data. By multiplying these times by the probability of a hit or miss, we arrive at the average time it takes to access memory in practice.
Because of the principle of locality—programs tend to access the same memory locations repeatedly or access contiguous memory blocks—the TLB hit rate is typically extraordinarily high, often above 95%. This means that despite being very small (usually only storing 64 to 1024 entries), the TLB successfully hides the overhead of paging almost all the time. However, when the OS switches between different processes (a context switch), the virtual-to-physical mappings change, meaning the TLB must be 'flushed' or wiped clean, leading to a temporary spike in memory access times as the new process builds up its own TLB entries.
Key points
- Hardware Cache: The TLB is specialized associative memory (hardware) built directly into the MMU, making it fundamentally different from software caches.
- Locality of Reference: The TLB relies heavily on spatial and temporal locality; without locality, the small size of the TLB would render it useless.
- Context Switching Overhead: Flushing the TLB during a context switch is a significant source of performance overhead in modern operating systems.
Common mistakes
- Confusing TLB with CPU Cache: This is a common source of confusion.
- Ignoring TLB lookup time in EAT calculations: This is a common source of confusion.
Glossary
- Translation Lookaside Buffer (TLB)
- A super-fast, tiny hardware cache inside the CPU that memorizes recent memory translations to avoid looking them up the slow way.
- page tables
- The master directory stored in RAM that tells the computer exactly where each piece of a program's virtual memory is physically located.
- physical frame
- A small, fixed-size chunk of actual hardware RAM where a piece of a program's data is stored.
Recall questions
- Why is the TLB necessary in a paged memory system?
- What happens to the TLB during a context switch?
- If TLB hit rate is 90%, TLB access is 10ns, and memory access is 100ns, what is the Effective Access Time?
Questions & answers
A system has a TLB hit ratio of 80%. It takes 20ns to search the TLB and 100ns to access main memory. What is the EAT?
140ns
Approach: Hit scenario: TLB (20ns) + Memory (100ns) = 120ns. Miss scenario: TLB (20ns) + PT in Memory (100ns) + Data in Memory (100ns) = 220ns. EAT = (0.80 * 120) + (0.20 * 220) = 96 + 44 = 140ns.
Which hardware component is primarily responsible for holding the TLB?
The Memory Management Unit (MMU).
Approach: Recall that address translation happens in hardware on the fly. The MMU is the chip (or part of the CPU) that handles this, so the TLB lives there for maximum speed.
Continue learning
Previous: Paging & Page Tables