AdvancedOperating Systems · Lesson 17 of 17 · Updated ·
TLB and Effective Access Time — Page Table Size, Multi-Level Paging and Page-Fault Numericals
Paging (lesson 6) has a hidden cost: before the CPU can read a byte, it must find out which frame holds the page — and the page table itself lives in RAM. This lesson measures that cost, shows how the TLB hides it, and solves the effective-access-time (EAT) questions that appear in nearly every OS exam.
1. The problem: two memory reads for one
With a single-level page table in RAM, every memory access becomes:
- Read the page table entry (one memory access) to get the frame number.
- Read the data (a second memory access).
If one memory access takes 100 ns, every load or store now takes 200 ns — paging has made memory twice as slow.
2. The TLB
The TLB (Translation Lookaside Buffer) is a small, very fast cache inside the CPU that remembers recent page → frame translations. It usually holds from a few dozen to a few thousand entries and is searched in parallel, so a lookup takes about one CPU cycle.
- TLB hit: TLB time + 1 memory access.
- TLB miss: TLB time + 1 access for the page table + 1 for the data. The translation is then put into the TLB.
Programs have locality — they keep using the same few pages — so hit ratios are usually very high.
3. Effective access time with a TLB
With hit ratio h, TLB lookup time t and memory access time m:
EAT = h × (t + m) + (1 − h) × (t + 2m)
Worked example. t = 20 ns, m = 100 ns, h = 80%.
- Hit: 20 + 100 = 120 ns.
- Miss: 20 + 100 + 100 = 220 ns.
- EAT = 0.8 × 120 + 0.2 × 220 = 96 + 44 = 140 ns.
Compared with 200 ns without a TLB, that is a big saving, and a better hit ratio helps more:
def eat(hit, tlb, mem, levels=1):
on_hit = tlb + mem # translation found in the TLB
on_miss = tlb + levels * mem + mem # walk the page table(s), then the data
return hit * on_hit + (1 - hit) * on_miss
for h in (0.80, 0.90, 0.98):
print(f"hit {h:.0%}: one level {eat(h, 20, 100):6.1f} ns two levels {eat(h, 20, 100, 2):6.1f} ns")
print("no TLB, one level:", 2 * 100, "ns")
hit 80%: one level 140.0 ns two levels 160.0 ns
hit 90%: one level 130.0 ns two levels 140.0 ns
hit 98%: one level 122.0 ns two levels 124.0 ns
no TLB, one level: 200 ns
Two exam variations to watch for:
- Some questions say the TLB is searched in parallel with memory, or ignore the TLB time. Then a hit costs just m and a miss 2m. Read the question.
- Reverse question: "What hit ratio gives an EAT of 130 ns?" Solve 120h + 220(1 − h) = 130 → 220 − 100h = 130 → h = 0.9.
4. How big is a page table?
Number of entries = 2^(logical address bits) / page size. Size = entries × entry size.
32-bit addresses, 4 KB (2¹²) pages, 4-byte entries:
- Entries = 2³² / 2¹² = 2²⁰ = 1,048,576.
- Size = 2²⁰ × 4 B = 4 MB — for every process, even one that uses only a few pages.
On a 64-bit machine using 48-bit virtual addresses with 8-byte entries, a single flat table would need 2³⁶ × 8 B = 512 GB. Impossible. That is why page tables are split into levels.
5. Two-level (multi-level) paging
Split the page number into two parts. The outer page table points to inner page tables, and inner tables are created only for the parts of memory the process actually uses.
Why 10 + 10 + 12? The offset needs 12 bits for 4 KB pages. A page-sized table holds 4096 / 4 = 1024 = 2¹⁰ entries, so each level uses 10 bits. 10 + 10 + 12 = 32.
Space saved. A small program using 3 regions of memory needs 1 outer table + 3 inner tables = 4 × 4 KB = 16 KB instead of 4 MB.
Time cost. A TLB miss now needs two page-table reads before the data. With the same numbers (t = 20, m = 100):
- 80% hits: 0.8 × 120 + 0.2 × (20 + 200 + 100) = 96 + 64 = 160 ns.
- 98% hits: 124 ns — almost the same as one level.
So multi-level tables save huge amounts of memory, and the TLB hides most of the extra time. 64-bit x86 processors use four levels (and newer ones optionally five).
6. Effective access time with page faults
If the page is not in RAM at all, a page fault must load it from disk — millions of times slower than RAM. With page-fault rate p, memory access time m and page-fault service time s:
EAT = (1 − p) × m + p × s
Example. m = 200 ns, s = 8 ms = 8,000,000 ns.
| Fault rate p | EAT |
|---|---|
| 1 in 1,000 | 0.999 × 200 + 0.001 × 8,000,000 = 8199.8 ns (about 41× slower) |
| 1 in 100,000 | ≈ 280 ns (40% slower) |
How rare must faults be to stay within 10% of 200 ns? Need 200 + p × (8,000,000 − 200) < 220 → p < 20 / 7,999,800 ≈ 2.5 × 10⁻⁶ — fewer than one fault in about 400,000 accesses. This is why thrashing (lesson 7) is so damaging: even a small rise in the fault rate ruins performance.
7. Inverted page tables
Instead of one table per process with one entry per page, an inverted page table has one entry per physical frame for the whole system, each saying "this frame holds page p of process id". Its size depends on RAM size, not on the address space. The downside: to translate an address you must search for (process, page), so it is combined with hashing — and with a TLB, of course.
| Page table type | Size depends on | Lookup |
|---|---|---|
| Single-level | virtual address space (per process) | one index — fast |
| Multi-level | the memory a process actually uses | one read per level |
| Inverted | physical memory (one table in total) | search / hash |
Common mistakes
- Charging only one memory access on a TLB miss — a miss needs the page-table read and the data read.
- Forgetting the extra level on a miss with two-level paging.
- Mixing ns and ms in the page-fault formula — convert everything to ns first.
- Computing page-table entries from the physical address size instead of the logical one.
- Thinking multi-level paging makes every access slower — with a good TLB hit ratio the difference is small.
Quick recap
- No TLB: every access costs 2 memory reads with one-level paging.
- EAT = h(t + m) + (1 − h)(t + (levels + 1)m).
- Page table entries = 2^(address bits) / page size; 32-bit, 4 KB, 4 B entries → 4 MB.
- Multi-level tables store only the parts in use; each level adds one read on a TLB miss.
- With page faults: EAT = (1 − p)m + p·s, so p must be tiny.