Chapter 27 of 38

Page Tables & TLB

On this page

In the previous chapter, Paging, we learned that every logical address is translated through a page table. That idea is simple and elegant, but it leaves us with two serious practical problems:

  1. Speed: the page table lives in RAM, so every memory access by a program becomes two memory accesses: one to read the page-table entry and one to read the actual data. A program would run at half speed.

  2. Size: a flat page table for a 32-bit address space with 4 KB pages has 220 entries, about 4 MB per process. For a 64-bit address space a flat table is simply impossible.

This chapter is about how real systems solve both problems. For speed, the CPU uses a small, very fast cache called the TLB. For size, the OS uses smarter page-table structures: multi-level (hierarchical), hashed and inverted page tables. We will also look closely at what is stored inside a page-table entry, because later chapters (Virtual Memory & Demand Paging and Page Replacement Algorithms) depend on those bits.


Where Does the Page Table Live?

The page table is far too big to keep inside the CPU, so it is stored in main memory. The CPU only holds a pointer to it:

  • Page-Table Base Register (PTBR) → physical address where the current process's page table starts. On x86 this is the CR3 register; on ARM64 it is TTBR0_EL1/TTBR1_EL1.

  • Some simple designs also have a Page-Table Length Register (PTLR) holding the number of valid entries, so out-of-range page numbers can be caught quickly.

This design makes switching between processes cheap: on a context switch (see Process Control Block & Context Switching) the OS does not copy any page table. It just loads the new process's page-table address into the PTBR.

Context switch from P1 to P2:

  PTBR = address of P1's page table
             │
             ▼  (save P1's state, load P2's state)
  PTBR = address of P2's page table

Every translation from now on uses P2's mappings.

Inside a Page-Table Entry (PTE)

A page-table entry stores much more than the frame number. A typical PTE contains:

Field

Purpose

Frame number

Which physical frame holds this page

Valid / Present bit

1 = mapping is usable and the page is in RAM. 0 = invalid page, or page not currently in memory (accessing it causes a trap / page fault)

Protection bits

Read / write / execute permissions, e.g. code pages are read-only

User / Supervisor bit

Whether user-mode code may access the page or only the kernel

Reference (Accessed) bit

Set by hardware whenever the page is read or written. Used by page-replacement algorithms

Dirty (Modified) bit

Set by hardware when the page is written. A dirty page must be written back to disk before its frame is reused

Caching bits

Control whether the page may be cached (important for memory-mapped device registers)

As a real example, an x86-64 PTE is 8 bytes (64 bits). Some of its bits are:

bit  0      P    Present
bit  1      R/W  Writable
bit  2      U/S  User accessible
bit  5      A    Accessed   (reference bit)
bit  6      D    Dirty
bit  8      G    Global     (do not flush from TLB on context switch)
bits 12-51       Physical frame number
bit  63     NX   No-Execute (data pages cannot be run as code)

Why the NX bit matters: many classic attacks wrote machine code into a buffer on the stack and then jumped to it. Marking stack and heap pages as non-executable stops that whole class of attack.


Problem 1: Two Memory Accesses per Access

Without any help, reading one variable looks like this:

CPU wants the byte at logical address A
   │
   ├─ Memory access 1: read page-table entry for page(A)    → get frame f
   │
   └─ Memory access 2: read physical address (f, offset)    → get the data

Total: 2 memory accesses for 1 useful access

Memory is already the slowest part of a typical instruction, so doubling it is unacceptable. The solution is a cache dedicated to translations.


The Translation Lookaside Buffer (TLB)

The Translation Lookaside Buffer (TLB) is a small, fast, associative hardware cache inside the MMU that stores recently used page-number → frame-number translations.

"Associative" means the TLB compares the page number against all its entries in parallel, so a lookup takes only about a cycle or so, and the CPU overlaps it with the start of the cache access. The price is that associative memory is expensive and power-hungry, so TLBs are small: typically from a few dozen entries (first level) up to a few thousand entries (second-level TLB) on modern CPUs.

How a Lookup Works

          logical address = (p, d)
                    │
                    ▼
            +---------------+
            |  TLB lookup p |
            +---------------+
              /           \
         TLB HIT          TLB MISS
            │                 │
            │                 ▼
            │        read page table in memory
            │        (the "page walk"), get frame f
            │                 │
            │        insert (p → f) into the TLB
            │        (evict an old entry if full)
            ▼                 ▼
         physical address = (f, d)  →  access memory
  • TLB hit: the frame number is found in the TLB. Only one memory access (for the data) is needed.

  • TLB miss: the page table must be read from memory, then the TLB is updated, then the data is read.

Who handles the miss?

  • Hardware-managed TLB (x86, ARM): the CPU has a built-in page walker that reads the page table itself. The OS only has to keep the page table in the format the hardware expects.

  • Software-managed TLB (classic MIPS, older SPARC): a TLB miss raises an exception and an OS routine fills the TLB. This is more flexible but slower.

Why the TLB Works So Well: Locality

A TLB with only a few hundred entries can serve a program using gigabytes of memory because programs show locality of reference:

  • Temporal locality: data used now is likely to be used again soon (loop counters, the current function's code).

  • Spatial locality: data near recently used data is likely to be used soon (array elements, the next instruction).

One TLB entry covers a whole 4 KB page, so walking through an int array touches 1024 elements before needing a new translation. Hit ratios of 99% and more are normal.


Effective Access Time (EAT) with a TLB

This is a favourite numerical in exams. Let:

  • t = TLB lookup time

  • m = one main-memory access time

  • h = TLB hit ratio (fraction of lookups that hit)

For a single-level page table:

EAT = h × (t + m)  +  (1 − h) × (t + m + m)
        └── hit ──┘        └──── miss: TLB, page table, data ──┘

Some textbooks treat the TLB lookup time as negligible and drop t. Always read the question carefully to see whether TLB time is given and whether it should be counted.

Worked Example

TLB lookup = 10 ns, memory access = 100 ns, single-level page table.

Hit cost  = 10 + 100        = 110 ns
Miss cost = 10 + 100 + 100  = 210 ns

Hit ratio h

EAT = h × 110 + (1 − h) × 210

Slowdown vs 100 ns

No TLB at all

100 + 100 = 200 ns

100%

0.80

0.8 × 110 + 0.2 × 210 = 130 ns

30%

0.90

0.9 × 110 + 0.1 × 210 = 120 ns

20%

0.99

0.99 × 110 + 0.01 × 210 = 111 ns

11%

Even a 99% hit ratio costs 11% here, but 10 ns of that is the TLB lookup itself (which real CPUs overlap with other work). The miss penalty only adds 1 ns on average.

Reverse Question: Required Hit Ratio

With the same numbers, what hit ratio is needed so that EAT is at most 115 ns?

EAT = 110h + 210(1 − h) = 210 − 100h

210 − 100h ≤ 115
     100h ≥ 95
        h ≥ 0.95   → at least 95% of lookups must hit

With a Multi-Level Page Table

If the page table has k levels (explained below), a TLB miss needs k memory accesses for the walk, plus one for the data:

EAT = h × (t + m)  +  (1 − h) × (t + k·m + m)

For a 4-level table (like x86-64), t = 10 ns, m = 100 ns:

Miss cost = 10 + 4×100 + 100 = 510 ns

h = 0.90 → 0.90 × 110 + 0.10 × 510 = 150 ns
h = 0.99 → 0.99 × 110 + 0.01 × 510 = 114 ns

Deep page tables make misses very expensive, which is why a high TLB hit ratio is critical. (Real CPUs also cache upper levels of the page table in special "paging-structure caches" to shorten the walk.)


TLBs and Context Switches

The TLB holds translations of the current process. Page 5 of process A and page 5 of process B map to completely different frames. So what happens on a context switch?

Option 1: Flush the TLB

Simply invalidate every entry. It is correct, but the new process then starts with a "cold" TLB and suffers many misses.

Option 2: Address-Space Identifiers (ASIDs)

Each TLB entry is tagged with an ASID that identifies the process (address space). A lookup hits only if both the page number and the ASID match. Entries of several processes can then live in the TLB together and nothing needs flushing on a switch.

TLB with ASIDs
+------+------+-------+
| ASID | page | frame |
+------+------+-------+
|  7   |  5   |  42   |   ← process with ASID 7
|  9   |  5   |  13   |   ← process with ASID 9, same page number, different frame
|  7   |  6   |  80   |
+------+------+-------+

On x86-64 this feature is called PCID (Process-Context Identifier); ARM has ASIDs. Pages shared by all processes, like kernel pages, can additionally be marked global so they survive flushes.

TLB Shootdown

On a multi-core machine, every core has its own TLB. If the OS changes or removes a mapping (for example when unmapping memory or changing permissions), stale copies may sit in other cores' TLBs. The OS must send an inter-processor interrupt asking the other cores to invalidate that entry. This is called a TLB shootdown, and it is one reason why frequently calling munmap() or mprotect() in a multi-threaded program can be slow.


TLB Reach and Huge Pages

TLB reach = number of TLB entries × page size. It is the amount of memory that can be accessed without any TLB miss.

64 entries   × 4 KB pages = 256 KB
64 entries   × 2 MB pages = 128 MB
1536 entries × 4 KB pages = 6 MB
1536 entries × 2 MB pages = 3 GB

Programs that work on large amounts of data (databases, scientific code, virtual machines) blow past a 4 KB TLB reach easily. Using huge pages increases the reach by a factor of 512 (2 MB / 4 KB), which can noticeably speed them up. This is the main motivation for Linux's Transparent Huge Pages mentioned in the previous chapter.


Problem 2: Page Tables Are Too Big

Recall the numbers from Paging:

32-bit address, 4 KB pages, 4-byte PTE:
  2^20 entries × 4 B = 4 MB per process, and it must be contiguous

64-bit (48-bit used), 4 KB pages, 8-byte PTE:
  2^36 entries × 8 B = 512 GB per process   ← impossible

Yet most processes use only a tiny fraction of their address space: some code at the bottom, a heap above it, a stack near the top, and a huge unused gap in between. A flat table wastes almost all of its entries on that gap. There are three classic solutions.


Solution 1: Hierarchical (Multi-Level) Paging

The trick is to page the page table itself. Split the big page table into page-sized pieces, and keep a small outer page table that points to those pieces. Pieces that would contain only invalid entries are simply not allocated.

Two-Level Paging for 32-bit Addresses

With 4 KB pages and 4-byte entries, one page can hold 4096 / 4 = 1024 = 210 entries. So the 20-bit page number is split into two 10-bit parts:

   32-bit logical address
  +------------+------------+--------------+
  |    p1      |    p2      |   offset d   |
  +------------+------------+--------------+
     10 bits      10 bits       12 bits

  p1 → index into the OUTER page table (page directory)
  p2 → index into one INNER page table
  d  → offset inside the final page
  PTBR
   │
   ▼
 +-------------+         +-------------+
 | Outer table |  p1 ──► | entry → ────┼──► +-------------+
 | (1 page)    |         +-------------+    | Inner table |  p2 ──► frame f
 +-------------+                            | (1 page)    |
                                            +-------------+
                              physical address = (f, d)

This is exactly the classic 32-bit x86 design: the outer table is called the page directory.

Splitting a Real Address

Take the address 0x00403A7C from the previous chapter:

0x00403A7C in binary (32 bits):
0000 0000 0100 0000 0011 1010 0111 1100

p1     = top 10 bits     = 00 0000 0001          = 1
p2     = next 10 bits    = 00 0000 0011          = 3
offset = low 12 bits     = 1010 0111 1100        = 0xA7C

→ outer table entry 1 → inner table → entry 3 → frame f
→ physical address = f × 4096 + 0xA7C

How Much Memory Does It Save?

Each inner table maps 1024 pages × 4 KB = 4 MB of address space. Suppose a process uses 8 MB at the bottom of its address space (code, data, heap) and 8 MB at the top (stack), and nothing in between.

Inner tables needed = 8 MB / 4 MB + 8 MB / 4 MB = 2 + 2 = 4
Outer table         = 1

Total = 5 pages × 4 KB = 20 KB

Flat page table     = 4 MB

20 KB instead of 4 MB: about 200 times smaller. The saving comes entirely from not allocating inner tables for the unused middle of the address space.

64-bit Systems: Four or Five Levels

x86-64 uses 8-byte entries, so one 4 KB page holds 512 = 29 entries, i.e. 9 index bits per level. Current CPUs use 48-bit virtual addresses:

  48-bit virtual address (x86-64, 4-level paging)
 +-------+-------+-------+-------+------------+
 | PML4  | PDPT  |  PD   |  PT   |   offset   |
 +-------+-------+-------+-------+------------+
   9 bits  9 bits  9 bits  9 bits   12 bits      9×4 + 12 = 48

 Address space = 2^48 bytes = 256 TB

Newer Intel and AMD processors also support 5-level paging, adding one more 9-bit level for 57-bit virtual addresses (257 bytes = 128 PB). Linux supports it on such hardware.

Huge pages fit in naturally: if the walk stops one level early, the remaining 9 + 12 = 21 bits become the offset, giving a 221 = 2 MB page. Stopping two levels early gives 30 bits of offset, a 1 GB page.

Numerical: How Many Levels?

A system has 46-bit virtual addresses, 8 KB pages and 4-byte PTEs. Each page table must fit in one page. How many levels of paging are needed?

Offset bits            = log2(8 KB)          = 13
Bits left for indexing = 46 − 13             = 33
Entries per page       = 8 KB / 4 B = 2048   = 2^11  → 11 bits per level
Levels                 = ceil(33 / 11)       = 3

The Cost of Levels

Every extra level adds one memory access to a TLB miss (see the EAT example above). Multi-level paging trades memory space for miss time, which is acceptable only because the TLB makes misses rare.


Solution 2: Hashed Page Tables

Instead of indexing a big array, hash the virtual page number into a hash table. Each bucket holds a linked list of entries, each with three fields:

hash(page number) → bucket
bucket → [ page q | frame | next ] → [ page p | frame | next ] → null

Lookup: walk the chain until the stored page number equals p,
        then use its frame number. If none matches → page fault/trap.
  • The table size depends on the number of pages in use, not on the size of the address space, so it suits large (64-bit) sparse address spaces.

  • Collisions make lookups slower; long chains hurt.

  • A variation, the clustered page table, stores mappings for several consecutive pages (e.g. 16) in each entry, which works well for programs with spatial locality.


Solution 3: Inverted Page Tables

All the tables so far have one entry per page of each process. An inverted page table flips that around: it has exactly one entry per physical frame, and there is only one table for the whole system.

Inverted page table (index = frame number)

 frame | process id | page number
 ------+------------+------------
   0   |     —      |     —        (kernel / free)
   1   |    P7      |     12
   2   |    P3      |      0
   3   |    P7      |      4
  ...

Lookup for (pid, p): find the entry i where (pid, page) matches.
                     The INDEX i is the frame number.

Size Example

A machine with 16 GB of RAM, 4 KB frames and 8-byte entries:

Frames      = 16 GB / 4 KB = 4,194,304
Table size  = 4,194,304 × 8 B = 32 MB   (for the entire system, any number of processes)

Pros and Cons

  • Pro: memory used for translation is proportional to physical memory, not to the number of processes or their address-space sizes.

  • Con: lookup is a search through the table, not a direct index. In practice a hash table is placed in front of it, and the TLB handles most lookups anyway.

  • Con: sharing memory is awkward, because each frame has only one (pid, page) slot, so two processes cannot easily map the same frame at the same time.

Inverted and hashed designs were used by IBM's PowerPC/POWER and by Intel's Itanium (IA-64). Mainstream x86-64 and ARM64 use multi-level tables.


Comparison of Page-Table Structures

Structure

Size depends on

Lookup on TLB miss

Good for

Main drawback

Flat (single-level)

Size of logical address space

1 memory access

Small address spaces

Huge for 32/64-bit

Multi-level

Parts of address space actually used

1 access per level

Sparse address spaces (x86-64, ARM64)

Slower misses

Hashed

Number of pages in use

Hash + chain walk

Very large sparse spaces

Collisions

Inverted

Physical memory size (one table total)

Search (usually via hash)

Saving translation memory

Slow search, hard sharing


Common Mistakes

  • Thinking the TLB stores data. The TLB stores translations (page → frame). The CPU data caches (L1/L2/L3) store data. They are different hardware.

  • Forgetting the extra memory accesses in EAT. A miss costs one memory access per page-table level plus one for the data.

  • Adding TLB time when the question says to ignore it (or the opposite). Check the question.

  • Believing multi-level paging is faster. It saves memory; it makes TLB misses slower, not faster.

  • Saying an inverted page table has one entry per page. It has one entry per frame, and one table for the whole system.

  • Ignoring the TLB on a context switch. Without ASIDs/PCIDs the TLB must be flushed; otherwise the new process would use the old process's translations.


Interview Questions

What is a TLB and why is it needed?

A small, fast, associative cache in the MMU that stores recent page → frame translations. Without it, every memory access would need an extra memory access to read the page table, roughly halving performance.

What happens on a TLB miss?

The page table is walked (by hardware on x86/ARM, by an OS handler on software-managed TLBs) to find the frame number. The translation is inserted into the TLB, replacing an old entry if needed, and the access proceeds. If the page-table entry is invalid or not present, a page fault occurs instead.

How do you compute effective access time with a TLB?

EAT = h × (t + m) + (1 − h) × (t + k·m + m), where h is the hit ratio, t the TLB time, m the memory time and k the number of page-table levels. For a single level, a miss costs t + 2m.

What is an ASID / PCID?

An address-space identifier stored in each TLB entry. A lookup matches only if both the page number and the ASID match, so translations from several processes can coexist and the TLB does not need flushing on every context switch.

Why use multi-level page tables?

To avoid allocating a huge contiguous table for a mostly empty address space. Inner tables are only created for regions that are actually used, so memory for page tables shrinks dramatically.

What is an inverted page table?

A single system-wide table with one entry per physical frame, storing (process id, page number). It saves memory because its size depends only on RAM, but lookups require a search (usually via hashing) and sharing pages is difficult.

What is TLB reach and how do huge pages help?

TLB reach is entries × page size, the memory accessible without TLB misses. Huge pages (2 MB or 1 GB) multiply the reach by 512 or more per entry, reducing misses for large-memory workloads.

What is a TLB shootdown?

When a mapping changes on a multi-core system, the OS interrupts other cores so they invalidate stale TLB entries for that mapping. It keeps all TLBs consistent but is costly.


Summary

  • The page table lives in main memory; the PTBR (CR3 on x86) points to the current process's table and is reloaded on each context switch.

  • A PTE holds the frame number plus control bits: valid/present, protection, user/supervisor, reference, dirty, and on x86-64 the NX bit.

  • The TLB caches translations so most accesses need only one memory access. Locality gives hit ratios of 99% or more.

  • EAT = h(t + m) + (1 − h)(t + k·m + m). With t = 10 ns, m = 100 ns and one level: 90% → 120 ns, 99% → 111 ns.

  • ASIDs/PCIDs avoid TLB flushes on context switches; TLB shootdowns keep multi-core TLBs consistent.

  • Multi-level paging pages the page table so unused regions cost nothing. x86-64 uses 4 levels (48-bit) or 5 levels (57-bit) with 9 index bits per level.

  • Hashed page tables suit sparse 64-bit spaces; inverted page tables have one entry per frame and one table for the whole system.

  • Next, Segmentation looks at a different way of dividing memory: by logical units such as code, data and stack instead of fixed-size pages.