Two loose ends — which entry to evict, and what a real TLB entry looks like — then the bill of remaining worries.
19.6 Issue: Replacement Policy
Installing a new entry means evicting an old one.
The Crux: How To Design TLB Replacement Policy
Which TLB entry should be replaced when we add a new one? The goal: minimize the miss rate and improve performance.The usual first answer is least-recently-used (LRU) lru Least-recently-used replacement: evict the entry idle longest, betting on locality — sensible until a loop over n+1 pages meets an n-entry TLB and EVERY access misses (random replacement dodges such corner cases). Studied in depth with swapping. defined in ch. 19 — open in glossary — exploit locality, evict the entry idle longest. The usual second answer is random — simple, and immune to corner cases. Here is the corner case, live:
virtual address
0
VPN 0 · offset 0
MMU: TLB first, page table only on a miss
no access yet — click a preset (or ▶ access)
| TLB slot | VPN | PFN | valid | note |
|---|---|---|---|---|
| 0 | — | — | 0 | |
| 1 | — | — | 0 | |
| 2 | — | — | 0 | |
| 3 | — | — | 0 |
Loop over n+1 pages with an n-entry TLB and LRU self-destructs: inserting page 4 evicts page 0 — exactly the page the loop needs next; fetching page 0 evicts page 1; and so on, forever. The "reasonable" policy behaves quite unreasonably. Watch the trace: M M M M M M M M M M.
virtual address
0
VPN 0 · offset 0
MMU: TLB first, page table only on a miss
no access yet — click a preset (or ▶ access)
| TLB slot | VPN | PFN | valid | note |
|---|---|---|---|---|
| 0 | — | — | 0 | |
| 1 | — | — | 0 | |
| 2 | — | — | 0 | |
| 3 | — | — | 0 |
Random sometimes evicts a page the loop won't need for a while — so hits leak through where LRU managed zero. Its virtues: simplicity, and immunity to exactly this kind of corner-case rhythm.
(Deeper study of replacement policies waits for the swapping chapters, where the same question returns with disks attached.)
19.7 A Real TLB Entry
The MIPS R4000 — a modern, software-managed design. Its (slightly simplified) 64-bit entry, Figure 19.4:
Figure 19.4: a MIPS TLB entry (hover the fields; gray = unused)
Details worth savoring: only 19 VPN bits (user code owns just half the 32-bit space); a 24-bit PFN (64GB of physical memory); a global bit that bypasses the ASID for pages shared by everyone; a page mask (not shown) enabling multiple page sizes. MIPS TLBs hold 32–64 entries, a few of them wired — a register tells the hardware how many slots to reserve for OS translations that must never miss (the miss handler, above all). And since the TLB is software-managed, there are instructions to manage it:
| what it does | |
|---|---|
| TLBP | probe: is a particular translation in the TLB? |
| TLBR | read a TLB entry into registers |
| TLBWI | write (replace) a specific indexed entry |
| TLBWR | write (replace) a random entry |
Privileged, of course — imagine what a user process could do if it could write TLB entries (hint: just about anything, including taking over the machine, running its own malicious “OS”, or making the Sun disappear).
Tip: RAM Isn’t Always RAM (Culler’s Law)
Random-access memory implies every access costs the same. But if the pages you touch exceed what your TLB maps, “random” access turns expensive — the machine quietly walks page tables beneath you. Named for David Culler, who pointed at the TLB as the source of many a performance mystery.19.8 Summary
The TLB makes the common case — a cached translation — cost almost nothing, so programs mostly run as if memory weren’t virtualized at all: an excellent achievement, and essential to paging’s viability. Two clouds remain. Exceed the TLB coverage tlb coverage The total memory the TLB's entries can map at once; touch more pages than that in a short window and misses dominate (Culler's Law: RAM isn't always RAM). Larger pages stretch it. defined in ch. 19 — open in glossary — touch more pages in a short window than the TLB can map — and misses dominate; one remedy is larger pages (a favorite of DBMSs with big, randomly-accessed structures), which the next chapter’s machinery accommodates. And the TLB sits on the CPU’s critical path: with a physically-indexed cache, translation must finish before the cache lookup starts, which is why architects flirt with virtually-indexed caches and their own attendant headaches.
Homework (Measurement): tlb.c
Measure your own TLB à la Saavedra-Barrera: touch one int per page across N pages, time millions of iterations, and plot time-per-access as N grows. Jumps in the curve reveal the hierarchy — on the book’s machine, ~5ns until ≈16 pages (L1 TLB), ~20ns until ≈512 (L2), ~70ns beyond: a 14× swing. Mind the traps: timer precision, compilers deleting your loop, CPU migration (pin the thread!), and demand-zero first touches. Get it at ostep-homework.Check yourself
1.A program loops repeatedly over 5 pages; the TLB holds 4 entries. Compare LRU and random replacement.
2.The MIPS R4000 supports a 32-bit address space with 4KB pages, yet its TLB entry has only a 19-bit VPN. Where did the missing bit go?
3.What is the MIPS wired register for?
4.MIPS exposes TLBP, TLBR, TLBWI, and TLBWR to manage TLB contents. Why must these be privileged instructions?
5.The homework's measurement (Fig 19.5) shows access times stepping 5ns → 20ns → 70ns as the touched-page count grows past ~16 and ~1024. What's the reading?