The TLB, and a look at segmentation

Paging fixed fragmentation and quietly doubled the cost of every memory access. Read the page table at 100 ns, then read the data at 100 ns. 200 ns per access, forever.

The Nova-14's CPU makes hundreds of millions of memory accesses per second. Doubling all of them is not a small tax.

But look at what a program actually does. It runs a loop. The loop lives on one page. It reads an array. The array spans two or three pages.

The same handful of page numbers, over and over.

Why & what

The TLB. The translation lookaside buffer is a small, very fast cache inside the MMU that holds recently used page-to-frame translations.

It is small — a few hundred entries — for a reason. It is searched associatively, meaning every entry is compared at once, in parallel, in hardware. That is what makes it take 10 ns instead of 100. Doubling its size would slow the search down, so small is a design choice, not a limitation. The two paths.

• TLB hit — the translation is in the TLB. Look it up (10 ns), then read the data (100 ns). 110 ns.
• TLB miss — not in the TLB. Look (10 ns), read the page table (100 ns), read the data (100 ns), and add this translation to the TLB for next time. 210 ns. Effective access time. Interviews ask you to compute this. With a 90% hit rate:

EAT = 0.90 × 110 + 0.10 × 210 = 99 + 21 = 120 ns

Compare that with 200 ns without a TLB. Ten percent of accesses pay a small penalty and the other ninety percent make it almost free. Real hit rates are usually above 95%.

Why the hit rate is so high. Because of locality of reference: programs reuse the same small set of pages over short periods. Loops repeat the same instructions; arrays are walked in order. Locality is the single assumption that makes caches of every kind work, and Module 7 leans on it even harder.

The context switch cost, finally explained. The TLB holds translations for one process. Switch processes and those entries are wrong, so the TLB is flushed. The new process starts with an empty TLB and runs slowly until it fills back up. This is the hidden cost behind the 5 µs figure from Topic 2.3 — the copying was never the expensive part.

Segmentation, briefly. Paging cuts memory into equal pieces that mean nothing to the programmer. Page 2 is not "the stack"; it is just page 2.

Segmentation cuts memory along meaningful lines instead: one segment for code, one for the stack, one for the heap. An address becomes a segment number plus an offset. Because segments have meaning, protection can be meaningful too — the code segment can be marked read-only as a whole.

The catch is that segments are variable size, which brings external fragmentation straight back. That is why pure segmentation lost. Real systems use paging, sometimes with a thin layer of segmentation on top.

How it works

1. The CPU emits a logical address. The MMU splits off the page number as before.
2. It searches the TLB — all entries compared simultaneously, about 10 ns.
3. On a hit, it takes the frame number straight from the TLB and goes to RAM once. Done in 110 ns.
4. On a miss, it reads the page table from RAM, gets the frame number, and copies the entry into the TLB, replacing an old one. 210 ns this time, 110 ns next time.
5. On a context switch, the TLB is flushed, because its entries belong to the outgoing process.

Common confusion

"The TLB stores data." It stores translations — page number to frame number. The data cache is a separate thing entirely. A TLB hit still requires a trip to RAM to fetch the actual bytes.

"A bigger TLB would be better." Only up to a point. The parallel search is what makes it fast, and searching more entries at once costs both time and power. Beyond a few hundred entries the lookup starts to slow down and the benefit disappears.

"Segmentation is obsolete, so it is not worth knowing." It is still asked about, precisely because comparing it with paging tests whether you understand why fixed sizes matter. The comparison is the point.

Interview angle

"What is a TLB and why does it exist?" A small associative cache of recent translations, existing because paging otherwise doubles every memory access. Give the two paths with numbers.

"Compute the effective access time." This is a guaranteed numerical question. The shape is always the same: hit rate × hit cost + miss rate × miss cost. The trap is forgetting that a miss includes the TLB lookup you already paid for — a miss is 10 + 100 + 100, not 100 + 100.

"Paging versus segmentation?" Answer with the piece size and what follows from it: paging uses fixed pieces so it has internal fragmentation and no external; segmentation uses variable pieces that match the program's structure, so it has external fragmentation but meaningful protection.