Paging & the TLB — Address Translation & Effective Access Time
Why Paging Works — Airport Lockers
Your belongings are a process's pages; the identical lockers are physical frames; the reference card is the page table. Because all frames are the same size and a page can go in any free frame, memory never breaks into unusable gaps — the flaw that plagued contiguous allocation.
Pages, Frames & the Page Table
The program sees pages 0, 1, 2, 3 in order; the page table sends them to frames 1, 4, 3 and 7 — wherever RAM had room. A common page (and frame) size is 4 KB. The page table has one entry per page and is the only thing the hardware needs to translate an address.
Bit-Slicing a Logical Address
Because page size is a power of two (2ⁿ), the hardware never divides. The low n bits are the offset; the rest are the page number. Only the page number is translated through the table; the offset is copied straight into the physical address — which is why translation is effectively free.
Translating Address 13 (page size 4)
With a 4-byte page (2 offset bits), address 13 = 01101₂ splits into page 3 and offset 1. The table maps page 3 → frame 7, so the physical address is 7 × 4 + 1 = 29 — or just glue the bits: 111·01 = 11101. Same answer, no arithmetic.
Fragmentation — The Trade Paging Makes
Uniform frames mean a page fits any free frame, so external fragmentation vanishes. The only waste is internal: the last page is rarely full. A 15 KB process needs 4 pages (16 KB) and wastes 1 KB — on average half a page per process. Smaller pages waste less but grow the page table.
The Cost — Two Memory Accesses
The page table lives in RAM, so a plain paged reference costs two memory accesses: one to read the table entry, one to fetch the data. That halves effective memory speed. The fix is a tiny, fast cache of recent translations — the TLB.
The TLB in Action
The TLB holds 64–1024 recent (page → frame) pairs and compares them all in parallel in a single cycle. A hit skips the page table entirely; a miss falls back to memory and caches the result, evicting the LRU entry when full. This cold run hits only 37.5%, but a running program's TLB quickly warms to 99%+.
Translation With the TLB
The MMU checks the TLB first. On a hit the frame is known instantly and only the data read remains — one access. On a miss it reads the page table (a second access) and caches the translation so the next reference to that page is a hit. On a context switch the OS must flush the TLB or tag entries with an ASID, since each process has its own page table.
Effective Access Time (EAT)
# Galvin's Effective Access Time EAT = α × (T_TLB + T_mem) + (1 − α) × (T_TLB + 2 × T_mem) = α × 120 + (1 − α) × 220 # with T_TLB=20 ns, T_mem=100 ns
α is the TLB hit ratio. A hit pays one memory access plus the TLB probe; a miss pays two memory accesses plus the probe. As α → 1, EAT approaches raw memory time (≈ 120 ns) — the TLB is what makes paging cheap.
EAT at 80% vs 98% Hit Ratio
Given T_mem = 100 ns, T_TLB = 20 ns → hit cost 120 ns, miss cost 220 ns.
| Hit ratio α | EAT working | EAT | Slowdown |
|---|---|---|---|
| 0.80 | 0.80 × 120 + 0.20 × 220 = 96 + 44 | 140 ns | 1.40× |
| 0.98 | 0.98 × 120 + 0.02 × 220 = 117.6 + 4.4 | 122 ns | 1.22× |
| 1.00 (ideal) | 1 × 120 | 120 ns | 1.20× |
| No TLB | 2 × 100 | 200 ns | 2.00× |
Raising the hit ratio from 80% to 98% cuts EAT from 140 ns to 122 ns — overhead drops from 40% to 22%. Without any TLB, every reference costs 200 ns (100% overhead). Real TLBs run at 99%+, so paging's real-world cost is a few percent.
Five Address Translations
Page size 1024 B, 8 pages (max address 8191). Page table: 0→8, 1→3, 2→1, 3→5, 4→6, 5→7, 6→2, 7→4. Formula: p = L ÷ 1024, d = L mod 1024, physical = frame × 1024 + d.
| Logical L | p, d | frame | Physical = f×1024 + d |
|---|---|---|---|
| 1500 | p=1, d=476 | 3 | 3×1024 + 476 = 3548 |
| 2049 | p=2, d=1 | 1 | 1×1024 + 1 = 1025 |
| 6000 | p=5, d=880 | 7 | 7×1024 + 880 = 8048 |
| 1023 | p=0, d=1023 | 8 | 8×1024 + 1023 = 9215 |
| 8191 | p=7, d=1023 | 4 | 4×1024 + 1023 = 5119 |
Split the logical address into page and offset, look the page up in the table for its frame, then rebuild: frame × page_size + offset. Note L = 8191 is the very last legal byte (page 7, offset 1023) — one more and it would overflow the 8-page space.
Protection, Sharing & Copy-on-Write
Paging in the Real World
Eight Rules for Paging & the TLB
Fixed-Size Frames, Cached Translations
From the page-table map and bit-slicing, through fragmentation and the two-access problem, to the TLB, the EAT formula and copy-on-write — you can translate any address by hand and compute how fast paged memory really runs.
Paging plus a valid/invalid bit is the gateway to virtual memory — demand paging, page-fault handling and page-replacement algorithms (FIFO, LRU, Optimal), where a process runs with only part of it in RAM. That's the next tutorial.
📑 End of tutorial · Press ← to review, or click Restart