Skip to content
Tutorials Center
My learning

Topics

Lesson 40 of 66 ยท Memory Management

The TLB and Multilevel Page Tables

Speed up address translation with the TLB, calculate effective access time from the hit ratio, and shrink page tables with two-level, hashed and inverted designs.

Paging has two practical problems. First, a page table kept in memory doubles the cost of every access: one read to get the frame number, another for the data. Second, the page table itself can be enormous. The TLB fixes the first problem; multilevel, hashed and inverted page tables fix the second.

The translation look-aside buffer (TLB)

The TLB is a small, very fast cache inside the MMU that stores recent page-to-frame translations. It is an associative memory: the page number is compared with all entries at the same time.

On each memory access:

  1. The MMU looks up the page number in the TLB.
  2. TLB hit: the frame number is right there; the access takes a single memory reference.
  3. TLB miss: the MMU (or the OS, depending on the CPU) reads the page table in memory, then loads the entry into the TLB, replacing an old one, and the access continues.
flowchart TD
    A["Logical address (p, d)"] --> B{"p in TLB?"}
    B -- hit --> C["frame f from TLB"]
    B -- miss --> D["read page table in memory"] --> E["store entry in TLB"] --> C
    C --> F["physical address (f, d)"]

Most accesses take the short left path, because programs reuse the same pages.

TLBs typically hold 64 to 1,536 entries yet reach hit ratios above 99%, thanks to locality of reference: programs touch the same few pages repeatedly. On a context switch the old process's translations are meaningless for the new one, so the TLB is either flushed or, on better hardware, entries are tagged with an address-space identifier (ASID) so several processes can share the TLB without flushing.

Effective access time

Let the memory access time be m, the TLB lookup time t, and the hit ratio h. A hit costs t + m. A miss costs t + m + m (the extra m reads the page table). So

EAT = h x (t + m) + (1 - h) x (t + 2m)

With m = 100 ns, t = 10 ns:

  • h = 80%: EAT = 0.8 x 110 + 0.2 x 210 = 130 ns (30% slower than a bare access).
  • h = 99%: EAT = 0.99 x 110 + 0.01 x 210 = 111 ns (11% slower).
Python A TLB in action

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With locality, even a tiny TLB works well once it can hold the hot pages; for a program that jumps randomly over many pages, a big TLB is needed and the extra memory access remains frequent. This is why data-structure layout (arrays instead of pointer-chasing) matters for performance, and why very large programs use huge pages: a 2 MB page covers 512 normal pages with one TLB entry.

The page table is too big

A 32-bit address space with 4 KB pages has 2^20 pages; with 4-byte entries that is a 4 MB page table per process, mostly for addresses the process never uses. For a 64-bit address space a flat table is impossible (2^52 entries). Three solutions are used in practice.

Hierarchical (multilevel) page tables

Page the page table: split the page number into several parts. In a two-level scheme with a 32-bit address and 4 KB pages, the address is split into 10 + 10 + 12 bits:

Field Bits Role
p1 10 Index into the outer page table (the directory)
p2 10 Index into an inner page table
d 12 Offset within the page

The outer table points to inner tables, and an inner table is only created if some page in its 4 MB range is used. A small program with code, heap and stack uses only three or four inner tables instead of 1,024.

Python How much memory does a two-level table save?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two-level table needs 20 KB (the 4 KB directory plus four 4 KB inner tables; the stack region happens to straddle a 4 MB boundary, so it needs two) instead of 4 MB. The price: a TLB miss now costs more memory reads (one per level), which is why the TLB matters even more. x86-64 uses four or five levels (9 bits each), because a 48-bit address space has 2^36 pages.

Hashed page tables

For sparse address spaces larger than 32 bits, the page number is hashed into a table whose entries are linked lists of (page, frame) pairs. Look-up: hash the page number, walk the chain comparing page numbers. Clustered variants store several consecutive pages per entry.

Inverted page tables

Instead of one table per process, keep one table for the whole system with one entry per physical frame. Each entry says "this frame holds page p of process pid". The table size depends on physical memory, not on how many processes exist or how large their address spaces are. The catch: translation needs a search by (pid, page), usually accelerated with a hash table, and sharing frames between processes is harder, because a frame can appear only once. PowerPC and UltraSPARC used this design.

Python An inverted page table with a hash index

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Which design wins?

Design Table size grows with Lookup cost Used by
Flat Address-space size 1 memory read Small systems
Multilevel Pages actually used One read per level x86, x86-64, ARM, RISC-V
Hashed Pages actually used Hash + chain walk Some 64-bit systems
Inverted Physical memory Hash search PowerPC, UltraSPARC (older)

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is stored in the TLB?

    The TLB caches recent translations so most accesses avoid the extra page-table read.
  2. 2. m = 200 ns, TLB lookup t = 20 ns, hit ratio 90%. What is the effective access time?

    EAT = 0.9 x (20 + 200) + 0.1 x (20 + 400) = 198 + 42 = 240 ns.
  3. 3. Why does a context switch need special handling of the TLB?

    Entries are valid only for the address space they were loaded for; flush them or tag them with an address-space identifier.
  4. 4. Why does a two-level page table save memory?

    Unused regions of the address space need no inner table, only an empty slot in the directory.
  5. 5. What determines the size of an inverted page table?

    There is one entry per physical frame.

Summary

  • The TLB caches translations; with hit ratio h, EAT = h(t + m) + (1 - h)(t + 2m). Locality makes hit ratios above 99% typical.
  • Flush the TLB on context switches, or tag entries with ASIDs.
  • Multilevel page tables allocate inner tables only for used regions (x86-64 uses four or five levels).
  • Hashed tables suit sparse large address spaces; inverted tables have one entry per frame and need a search.

Next: Segmentation