Paging & the MMU

Before paging, the obvious way to give a program memory was to hand it one contiguous chunk of RAM. That works until programs start and stop at different times. You end up with free memory scattered in awkward gaps — 100 MB free here, 40 MB there — and a program that needs 120 MB contiguous cannot run even though 140 MB is free in total. That waste is called external fragmentation, and it is the disease paging was invented to cure.

The cure is to stop insisting on contiguity. Paging cuts the virtual address space into fixed-size pieces called pages, and cuts physical memory into pieces of exactly the same size called frames. A page is typically 4 KB. Because pages and frames are identical in size, any page can be placed in any free frame — the fit is always perfect, so a free frame is never the wrong shape. The program still sees a clean, contiguous address space; underneath, its pages can be sprinkled across physical RAM in any order at all.

Page

A fixed-size block of the virtual address space — commonly 4 KB. The unit the OS maps and protects.

Frame (page frame)

A fixed-size block of physical RAM, the same size as a page. The slot a page actually lives in.

Paging

Mapping virtual pages onto physical frames so that any page may occupy any frame, in any order.

External fragmentation

Free memory broken into scattered gaps too small to satisfy a request — the problem paging eliminates.

Paging does trade one problem for a milder one. If your data does not exactly fill its last page, the leftover space inside that page is wasted — a program using 5 KB occupies two 4 KB pages and wastes 3 KB. That is internal fragmentation: on average about half a page per allocation. It is bounded, predictable, and small, which is a far better deal than the unbounded scattering of external fragmentation.

The bookkeeping that records which page lives in which frame is the page table. Conceptually it is a simple array: index it by the virtual page number and it hands you back the physical frame number. One entry per page of the virtual address space, one lookup per translation. That is the whole data structure at its heart — an array from page numbers to frame numbers.

Crucially, every process gets its own page table. That is exactly how the private-address-space illusion is enforced: process A’s page 0 and process B’s page 0 are the same virtual address, but each table maps that page to a different physical frame, so the two processes cannot see each other’s memory even though they name identical addresses. When the OS switches from A to B, part of what it does is point the MMU at B’s page table (on x86, by loading the table’s base address into the CR3 register).

• ▸The page table maps a virtual page number (VPN) to a physical frame number (PFN) — plus a bundle of status bits we meet next.
• ▸There is one entry for every page in the virtual address space, whether or not that page is currently in use.
• ▸Each process has its own page table, so identical virtual addresses in different processes point to different physical memory.
• ▸The MMU is told where the current process’s table lives via a base register the OS reloads on every context switch.

Here is the mechanical heart of paging, and it is pure arithmetic. A virtual address is not two separate numbers the program supplies — it is a single integer that the hardware splits in two by position. The low bits are the offset: how far into the page you are. The high bits are the page number: which page you are in. Because page size is a power of two, this split is free — it is just picking bits, no division required.

The offset needs exactly enough bits to address every byte in one page. A 4 KB page is 2^12 bytes, so the offset is 12 bits. Whatever bits are left over form the page number. On a 32-bit machine that leaves 32 − 12 = 20 bits of page number, which means 2^20 ≈ 1.05 million pages in the space. The beautiful part: translation only replaces the page-number half. The offset is copied straight through untouched, because a byte’s position inside its page is identical to its position inside the frame.

Given:
  address size = 32 bits        virtual address = 0x00002A5C
  page size    = 4 KB = 2^12 bytes

Step 1 — how many bits for each field?
  offset bits = log2(page size) = log2(4096)   = 12 bits
  VPN bits    = 32 - 12                         = 20 bits

Step 2 — split the address by bit position
  0x00002A5C = 0000 0000 0000 0000 0010  1010 0101 1100
               |------ VPN: 20 bits -----||-- offset --|
  VPN    = high 20 bits = 0x00002        = 2
  offset = low  12 bits = 0xA5C          = 2652
  check: VPN*4096 + offset = 2*4096 + 2652 = 10844 = 0x2A5C  OK

Step 3 — look up the VPN in the page table
  page table[2] -> frame 5   (PFN = 5)

Step 4 — form the physical address: PFN glued to the SAME offset
  phys = PFN*4096 + offset = 5*4096 + 2652 = 23132 = 0x00005A5C
  note: offset 0xA5C is unchanged; only the top field 0x2 -> 0x5

Read step 4 twice — it is the payoff. The frame number 5 replaces the page number 2, but the offset 0xA5C rides along unchanged, so the physical address is 0x00005A5C. This is why the offset field never passes through the page table: only the page-to-frame part needs translating, and the hardware does that field swap on every single memory access, billions of times a second.

A page-table entry, or PTE, holds much more than a frame number. Alongside the PFN sits a small set of flag bits, and those bits are where a lot of the operating system’s power lives — protection, demand paging, replacement policy, and the user/kernel divide all ride on them. The MMU reads these bits on every access; the OS and sometimes the CPU write them.

Frame number (PFN)

The physical frame this page maps to — the actual translation result, the bulk of the entry.

Valid / present bit

Is this mapping usable right now? If 0, touching the page traps to the kernel as a page fault (the subject of the next chapter).

Protection bits (R/W, X/NX)

What operations are allowed: readable, writable, executable. A store to a read-only page, or a jump into a no-execute page, faults.

User/supervisor bit

Whether user-mode code may touch this page at all, or only the kernel — this is what keeps user code out of kernel memory.

Dirty bit

Set by the CPU when the page is written. Tells the OS the frame differs from its backing copy on disk and must be written back before eviction.

Accessed / referenced bit

Set by the CPU when the page is read or written. The OS samples and clears it to guess which pages are hot — fuel for page-replacement algorithms.

Two of these bits are set by the hardware as a side effect of your program running, and they exist purely to feed OS decisions later. The accessed bit lets the OS approximate "which pages have been used recently" without watching every access itself — it periodically clears the bits and comes back to see which got set again. The dirty bit is an optimisation for eviction: a clean page (dirty = 0) already has an identical copy on disk, so the OS can drop it for free, while a dirty page must be written out first. We lean on both heavily in the page-replacement chapter.

Now let us run one translation from start to finish, the way the MMU does it on every access. The CPU produces a virtual address — because your instruction said to load, store, or fetch from it — and hands it to the MMU. Everything that follows happens in hardware, invisibly, before the access completes.

• ▸Split: the MMU carves the virtual address into its VPN (high bits) and offset (low bits), exactly the slice from section 03.
• ▸Index: it computes the address of the relevant PTE as page-table-base-register + VPN × entry-size, and reads that entry from memory.
• ▸Check valid: if the present/valid bit is 0, there is no usable mapping — the MMU raises a page fault, trapping into the kernel instead of completing the access.
• ▸Check protection: if the access violates the entry’s bits (a write to a read-only page, user code touching a supervisor page), the MMU faults instead of proceeding.
• ▸Form the physical address: on success it takes the PFN from the entry, concatenates the untouched offset, and issues that physical address to RAM.

Notice that a normal, successful translation costs at least one extra memory reference: the MMU has to read the PTE from memory before it can read the data you actually wanted. That is the hidden tax of paging, and it is exactly the problem the TLB later solves. Notice too that the interesting failures — invalid page, protection violation — do not crash your program directly; they trap into the kernel, which gets to decide what happens.

That trap on an invalid entry is called a page fault, and it is not always an error. Sometimes the page genuinely is not mapped and the kernel kills the process with the familiar segmentation fault. But very often the fault is expected and useful: the page exists logically but has not been loaded yet, or was paged out to disk, and the kernel quietly brings it in and restarts your instruction as if nothing happened. That whole machinery — demand paging, page faults, and page replacement — is the subject of the next chapter. Here, just hold the hook: an invalid PTE means "stop and ask the kernel", not "give up".

The single-level array we have been drawing is conceptually perfect and practically doomed. The trouble is that it has one entry for every page in the entire virtual address space, whether or not that page is ever used — and the address space is enormous. Let us do the arithmetic that kills the naive design.

32-bit address space, 4 KB pages, 4-byte PTEs:
  pages          = 2^32 / 2^12          = 2^20  (~1.05 million)
  table size     = 2^20 entries x 4 B  = 4 MB   per process
  100 processes  = 100 x 4 MB          = 400 MB just for tables

64-bit machine, using 48-bit addresses, 4 KB pages, 8-byte PTEs:
  pages          = 2^48 / 2^12          = 2^36  (~68.7 billion)
  table size     = 2^36 entries x 8 B  = 2^39 B = 512 GB  per process

A single process cannot afford a 512 GB table -- larger than RAM itself.

Four megabytes per process on a 32-bit machine is already wasteful when you have hundreds of processes. But the 64-bit number is not merely wasteful — it is impossible: a flat table would need 512 GB per process, larger than the physical RAM it is supposed to manage. And the deepest insult is that almost all of it would be empty. A real process uses a little code near the bottom, a heap growing up, a stack growing down, and vast untouched voids in between. A flat table dutifully allocates an entry for every page in those voids anyway.

The fix is to make the page table a tree instead of a flat array. Rather than one giant table indexed by the whole page number, we split the page number itself into several fields and use each field to index one level of a hierarchy. The top-level table has an entry per large region; each entry points to a next-level table only if that region is used. Unused regions get a single null entry at the top and cost nothing below — no sub-tables are allocated for the empty voids at all. Sparse address spaces suddenly become cheap.

x86-64 is the canonical example, with a four-level table. It uses 48-bit virtual addresses, a 12-bit offset, and splits the remaining 36 bits into four 9-bit indices — one per level. Why nine bits? Because a table is designed to fit in exactly one 4 KB frame: 4096 bytes ÷ 8 bytes per entry = 512 entries = 2^9, so each level is indexed by 9 bits. The levels have names — PML4, PDPT, PD, PT — and the CPU’s CR3 register points at the top one.

Layout of the 48-bit virtual address (4 KB pages):
  [ PML4 : 9 ][ PDPT : 9 ][ PD : 9 ][ PT : 9 ][ offset : 12 ]
   9 + 9 + 9 + 9 + 12 = 48 bits         (each 9-bit index = 512 entries)

Walk (start from CR3, follow one pointer per level):
  CR3            -> base of PML4 table
  PML4[ idx0 ]   -> base of PDPT table       (memory read 1)
  PDPT[ idx1 ]   -> base of PD   table        (memory read 2)
  PD  [ idx2 ]   -> base of PT   table        (memory read 3)
  PT  [ idx3 ]   -> PTE with frame number     (memory read 4)
  physical address = frame << 12 | offset

Cost: up to 4 memory references BEFORE the real access -- per translation.
Win : an unused PML4 entry means 512 GB of address space costs 1 empty slot.

The trade-off is stark and worth stating plainly. Multi-level tables turn an impossible 512 GB flat table into a handful of 4 KB tables that follow the shape of what the process actually uses — an enormous space win. But they cost time: a full walk now takes up to four dependent memory reads before the MMU can even issue the access you asked for. A translation that was one extra reference is now four. If every memory access paid that, paging would be unbearably slow. Something has to make the common case fast — which is exactly what the next section is.

The Translation Lookaside Buffer is a small, extremely fast hardware cache that sits inside the MMU and remembers recent VPN → PFN translations. On every access the MMU checks the TLB first. If the translation is there — a TLB hit — it gets the frame number in a single cycle and skips the entire page-table walk. Only on a miss does it fall through to the multi-level walk we just traced, and then it caches the result so the next access to that page is a hit.

A cache this tiny — often just dozens to a couple of thousand entries — has no business working as well as it does, and the reason it works is locality of reference. Programs do not touch memory randomly; they hammer the same few pages over and over (a loop’s code, the current stack frame, a hot array) before moving on. So a handful of cached translations covers the overwhelming majority of accesses, and TLB hit rates above 99% are normal. The rare miss pays for the walk; the common hit pays almost nothing. That is the whole reason paging is affordable.

TLB hit

The needed VPN → PFN translation is already cached; the frame is produced in about a cycle, the page-table walk skipped entirely.

TLB miss

The translation is not cached; the MMU performs the full page-table walk, then installs the result in the TLB.

Locality of reference

The tendency of programs to reuse the same nearby pages repeatedly — what lets a tiny TLB cover almost all accesses.

ASID / PCID

An address-space tag stored with each TLB entry, marking which process it belongs to, so entries survive a context switch.

The TLB has a sharp edge that ties straight back to the cost of a context switch. Each process has its own mappings, so a translation cached for process A is meaningless — and dangerous — for process B. The simple fix is to flush the whole TLB on every context switch, but that means the newly scheduled process starts cold and suffers a burst of misses while its working set is re-cached. This is a real, measurable slice of the context-switch cost we weighed earlier in the course. Modern CPUs soften it with ASIDs (Intel calls them PCIDs): each TLB entry is tagged with an address-space ID, so entries from different processes coexist and no flush is needed on an ordinary switch.

There is one more structural idea worth naming. A multi-level table is sized by the virtual address space, and there is one per process — so total table memory grows with the number of processes. An inverted page table flips the design: keep a single system-wide table with one entry per physical frame, recording which process and virtual page currently occupy it. Its size is bounded by physical RAM, not by the huge virtual space, and it does not multiply per process. The catch is that you can no longer index it by VPN, so lookups go through a hash of the (process, VPN) pair. It is the road less travelled — used on some architectures like PowerPC — but it is a clean illustration that the page table is a design choice, not a law of nature.

Step back and hold the whole chapter in one view. Paging chops the address space into pages and RAM into equal frames; a per-process page table maps VPN to PFN; the MMU splits each address, walks the table (multi-level, to stay small), checks the bits, and swaps VPN for PFN while the offset rides through unchanged; and the TLB caches recent translations so the common case is nearly free. Page faults on invalid entries hand control to the kernel — the hook into the next chapter.

• ▸Huge pages (2 MB or 1 GB) let one PTE map a far larger region, so one TLB entry covers vastly more memory — databases and JVMs enable them precisely to cut TLB misses on big heaps. A preview of the tuning knob, explained fully later.
• ▸Page faults and TLB misses are real, measurable line items in a profiler (perf’s page-faults, dTLB-load-misses). When "the same" code runs slower on bigger inputs, translation overhead is a prime suspect, not just data-cache behaviour.
• ▸Access patterns that respect locality — sequential, row-major, cache- and page-friendly — keep both the data cache and the TLB hot. Random or column-major striding over a large array thrashes both and can be many times slower for identical work.