Skip to main content

Source: Operating Systems: Three Easy Pieces (OSTEP) — Chapter 19, Arpaci-Dusseau & Arpaci-Dusseau

Paging: Faster Translations (TLBs)

Paging needs a mapping for every page — usually in memory — so a naive design does an extra memory lookup before every fetch/load/store. That is prohibitively slow.

Crux: how speed up address translation and avoid that extra reference? What hardware help? What OS involvement?

The TLB​

A translation-lookaside buffer (TLB) is a small, fast hardware cache of popular VPN→PFN translations inside the MMU (better name: address-translation cache) [CG68, C95].

On each virtual reference:

  1. Extract VPN
  2. TLB_Lookup(VPN)
  3. Hit → check protect bits → form PA → AccessMemory
  4. Miss → find PTE (hardware walk or OS trap) → TLB_Insert → retry the instruction

Hits are cheap (near the core). Misses re-impose paging’s cost. Goal: high hit rate.

Quiz

Rank the sequence

1 / 1

Order the steps of a successful (hit) TLB translation on a virtual reference (top = first).

OrderDrag the handle to rearrange — top should be first.

  1. 1Look up the VPN in the TLB
  2. 2Check protection bits and access memory using the cached PFN
  3. 3On a miss, find the PTE, insert it into the TLB, and retry
  4. 4Extract the VPN from the virtual address

Drag items into the correct order (or use ↑↓), then check.

Hardware-managed vs software-managed​

StyleOn missExample
Hardware-managedMMU walks page table via PTBR, fills TLB, retriesx86 (CR3)
Software-managedRaise TLB_MISS; OS handler fills TLB with privileged ops; return-from-trap retries same PCMIPS R10k, SPARC v9

Software-managed: OS can use any page-table structure; hardware stays simple. Watch out for infinite miss loops in the handler — keep handlers unmapped/physical or use wired TLB slots always resident.

TLB valid ≠ page-table valid

PTE invalid → page not allocated; usually kill the process.
TLB valid → this cache slot holds a usable translation. Empty at boot; filled as programs run. Clearing valid bits also flushes the TLB on a context switch.

Example: accessing an array​

10× 4-byte ints starting at VA 100. 8-bit VA space, 16-byte pages → 4-bit VPN + 4-bit offset.

ElementsVPN
a[0]…a[2]06
a[3]…a[6]07
a[7]…a[9]08

Trace for sum += a[i]: miss, hit, hit, miss, hit, hit, hit, miss, hit, hit → 70% hit rate on the first pass — spatial locality (dense packing on pages). Larger pages → fewer misses. A second pass can approach 100% if translations stay cached — temporal locality.

Use caching when possible

Caches exploit temporal (re-access soon) and spatial (nearby addresses) locality. Physics limits size: big → slow. Keep TLBs small and fast.

What’s in a TLB entry?​

Typically 32–128 entries, fully associative (any translation anywhere; parallel search):

VPN | PFN | valid | protect | ASID? | dirty? | …

Context switches​

Translations are per-process. P1 VPN10→PF100 and P2 VPN10→PF170 cannot both sit unlabeled in one TLB.

ApproachIdeaCost
FlushClear all valid bits on switchSafe; next process cold-misses
ASIDTag entries with address-space IDShare TLB across processes; OS sets current ASID

Shared code pages: different VPNs / ASIDs can map to the same PFN (read-execute).

Replacement policy​

On insert, evict someone:

  • LRU — good with locality
  • Random — simple; avoids LRU’s pathology (loop over n+1 pages with TLB size n → LRU misses every time)

Exceeding TLB coverage (working set of pages > TLB entries) → many misses. Larger pages raise coverage (next chapter).

A real entry (MIPS R4000)​

Software-managed TLB: VPN, PFN, G (global — ignore ASID), ASID, cache coherency bits, dirty, valid; wired slots reserved for the OS. Privileged ops: TLBP, TLBR, TLBWI, TLBWR.

Culler’s Law — RAM isn’t always RAM

Random access across more pages than the TLB covers can be much slower than sequential access within a few pages — even though “it’s all RAM.”

Interactive​

Try: hit/miss flow · array spatial-locality trace · context switch / ASID · replacement.

Check your understanding​

Quiz

TLBs

1 / 6

A TLB primarily caches…

Pick an answer to see if you are right.

Coding challenges​

Homework lab: measure the TLB​

Measurement homework (Saavedra-Barrera style [SB92]): time touching N pages in a loop and watch cost jumps as you exceed TLB capacity. Run on a real machine — not in the Piston sandbox.

Lab

Homework: measure TLB size & miss cost

0/7 started

Loading lab…

Summary​

IdeaOne line
TLBOn-chip cache of VPN→PFN translations
Hit / missHit skips page-table memory; miss walks or traps
LocalitySpatial + temporal → high hit rates
HW vs SW missWalk in hardware vs OS trap handler
Context switchFlush or ASID-tag entries
ReplacementLRU vs random; watch TLB coverage
Culler’s LawRandom page access can thrash the TLB

Previous: Paging Introduction

Next: Smaller Page Tables — multi-level tables, hybrids, and other space-saving tricks.

Further Reading​