Skills101

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:

  1. Read the page table entry (one memory access) to get the frame number.
  2. 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 address translation: the CPU looks up page p in the TLB; on a hit it gets the frame at once and reads the data; on a miss it reads the page table in RAM first. Hit costs TLB time plus one memory access; miss costs TLB time plus two memory accesses

  • 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.

Two-level paging for a 32-bit address with 4 KB pages: 10 bits index the outer table, 10 bits index an inner table, and 12 bits are the offset; each table has 1024 entries of 4 bytes, exactly one 4 KB page, instead of a 4 MB single-level table

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 pEAT
1 in 1,0000.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 typeSize depends onLookup
Single-levelvirtual address space (per process)one index — fast
Multi-levelthe memory a process actually usesone read per level
Invertedphysical 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.

Practice what you learned

📝 Quiz: TLB and Effective Access Time5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →