The TLB: Making Translation Fast

The hidden tax on every access

Guide 2 built the whole machine of address translation: the CPU produces a logical address, the hardware splits it into a (page number, offset) pair, looks the page number up in the page table to find a frame, and glues the frame to the offset to get the real physical address. It is a book's index: look up the entry, read off where the thing really lives. Clean and correct — but it hides a cost we now have to face head-on.

Here is the sting. The page table lives in RAM, and the hardware finds it through the page-table base register. So to translate one address, the CPU must first read the page table — that is one trip to memory just to learn where the data is. Only then can it make the second trip to fetch the data the program actually wanted. Every single memory access has quietly become two. The program reads twice as much memory as it asked for, half of it pure bookkeeping. If a flat table cost you double, a multi-level table (the subject of guide 4) costs you triple or worse — one extra trip per level.

Sticky notes for the pages you just used

The rescue is a small, very fast cache that sits inside the CPU's memory-management unit and holds the handful of translations you have used most recently. It is the translation lookaside buffer, or TLB. Picture sticky notes stuck to the edge of your desk. Looking a name up in the book's index (the page table) takes a full trip to the shelf; but the few pages you keep flipping back to, you scribble on a sticky note — "page 5 lives in frame 87" — and from then on you just glance at the note. The TLB is exactly that: a tiny table of recent (page number to frame) mappings, kept right next to the CPU so a lookup is essentially free.

Two design facts make the TLB special. First, it is tiny — typically only dozens to a few hundred entries — because it is built from expensive, fast hardware. You cannot fit the whole page table here, only the working set of pages in active use. Second, it is searched in a way that compares all of its entries at once, in parallel, rather than checking them one by one. That parallel-search hardware is what makes a glance at the sticky notes near-instant, and it is also why the TLB has to stay small: comparing thousands of entries at once would be too costly to build.

Why does keeping just a handful of notes help at all? Because of locality of reference — the deep, reliable habit of real programs. A program almost never scatters its accesses uniformly across memory. It pounds the same loop, walks down the same array, touches the same stack frame thousands of times in a row. So the same few pages get used over and over in any short window, and a cache that remembers just those few wins the overwhelming majority of the time. Locality is the quiet assumption under the entire TLB; without it, a tiny cache would almost never hold the page you want.

A hit, a miss, step by step

Now watch the hardware translate a single address with the TLB in the path. The CPU has just produced a logical address; it splits off the page number and presents it to the TLB. Everything hinges on whether that page number is on a sticky note — a TLB hit — or not — a TLB miss. Follow both branches:

Split and present. The hardware carves the logical address into (page number, offset) and hands the page number to the TLB. No memory touched yet.
TLB hit (the common case). The TLB compares all its entries at once and finds the page number, handing back the frame immediately. Glue the frame to the offset and do the one real memory access for the data. Total: zero page-table trips — the table was never touched.
TLB miss (the rare case). The page number is not on any note. Now the hardware falls back to the slow path: go to the page-table base register, read the page table in RAM to find the frame. That is the extra memory trip we were trying to avoid.
Write the new note. Having paid for the slow lookup, the hardware stores this fresh (page number to frame) mapping into the TLB so the next access to this page is a hit. If the TLB is full, it evicts an old entry to make room — usually the least-recently-used note.
Finish the access. With the frame now known, glue it to the offset and do the real memory access for the data — the same final step as a hit, just reached the long way.

Hold the shape of that fork in your head, because it is the whole point. On the hit branch the page table is never opened — one memory access, straight to the data. On the miss branch you pay one extra access to read the table, then leave a sticky note so the very next access to that page becomes a hit. The two branches reconverge at the same final step: frame plus offset gives the physical address, and one real access fetches the data. The TLB does not replace the page table; it just lets you skip the trip to it on the overwhelming majority of accesses.

Does it actually pay? The arithmetic

Analogies persuade, but numbers prove. The honest measure is the effective access time — the average time a memory access takes once you blend the fast hits and the slow misses by how often each happens. The recipe is just a weighted average: multiply each path's cost by its probability and add. Let one memory access cost 100 nanoseconds, and assume the TLB lookup itself is so fast we round it to zero. A hit costs one memory access (100 ns). A miss costs two (one to read the page table, one to fetch the data), so 200 ns.

Now plug in a realistic hit ratio. Thanks to locality, real TLB hit ratios are wonderfully high — often 99% or better. So with a 99% hit ratio: effective access time = 0.99 times 100 + 0.01 times 200 = 99 + 2 = 101 ns. Read that again: the average access costs 101 ns against an ideal of 100 ns. The whole double-access disaster from section one has shrunk to a 1% overhead. The TLB did not make memory faster; it made the page table almost never appear in the critical path.

Let one memory access = 100 ns; TLB lookup ~ 0 ns.

  hit  cost = 1 access  = 100 ns   (page table NOT read)
  miss cost = 2 accesses = 200 ns  (read table, then data)

  EAT = (hit ratio)x(hit cost) + (miss ratio)x(miss cost)

  at 99% hits: EAT = 0.99(100) + 0.01(200)
                   =   99      +   2
                   = 101 ns        --> only +1% over ideal

  at 80% hits: EAT = 0.80(100) + 0.20(200) = 120 ns  (+20%)

Effective access time is a weighted average of the hit and miss paths. A high hit ratio (the gift of locality) crushes the overhead toward nothing; a poor ratio brings the double-access tax roaring back.

The honest fine print

The TLB has a sharp edge, and it bites on a context switch. Each process has its own page table, so "page 5" means frame 87 for one process and a completely different frame for another. When the OS switches from process A to process B, A's sticky notes are now lies — same page numbers, wrong frames. The blunt fix is to flush the TLB on every switch: throw all the notes away. Correct, but costly — the new process starts with an empty TLB and suffers a burst of misses while it warms back up. This is one more reason context switches are not free.

Modern hardware softens this with an address-space identifier (ASID): each TLB entry is tagged with which process it belongs to, so notes from A and B can coexist without confusion, and a switch no longer has to throw everything away. It is the difference between scrapping all your sticky notes versus colour-coding them by project. The TLB also has to stay honest in other ways the OS manages carefully: if it ever changes a page table — say it pages something out — it must invalidate the matching TLB entry, or the stale note would point at a frame that no longer holds that page.