Skip to main content

Virtual Memory & Paging

Overview​

Every process behaves as if it owns the entire address space and as if its memory is one large, contiguous block — neither is physically true. Virtual memory is the hardware/OS collaboration that creates this illusion: each process gets its own private virtual address space, which the CPU's memory-management hardware transparently translates to real physical RAM addresses (or to disk, if the data isn't resident) on every access.

Core Concepts​

TermMeaning
Virtual addressThe address a program uses; meaningful only within that process's address space.
Physical addressThe real address of a byte in RAM.
PageA fixed-size chunk (commonly 4 KB) of virtual (or physical) address space — the unit virtual memory manages.
Page tableA per-process data structure mapping virtual page numbers to physical frame numbers.
MMU (Memory Management Unit)CPU hardware that performs virtual-to-physical translation on every memory access, walking the page table when needed.
TLB (Translation Lookaside Buffer)A small, fast hardware cache of recent virtual-to-physical translations inside the MMU, so most accesses skip the full page-table walk.
Page faultA trap raised when the MMU can't complete a translation (page not present, or access not permitted) — handled by the OS, not the MMU itself.

Architecture / Mechanism​

Why virtual memory exists​

  • Isolation: each process has its own address space, so one process cannot read or corrupt another's memory (or the kernel's) just by using an address — the MMU enforces the boundary on every access.
  • Illusion of contiguous memory: a process's logically contiguous address space can be backed by scattered, even non-resident, physical pages — programs don't need to know or care where their data physically lives.
A process's contiguous virtual address space with dashed arrows mapping its pages to scattered frames in RAM and to a disk, with another process's memory occupying RAM in between
One process's flat, contiguous address space (left) scattered across whatever physical frames were free (right) — with another process's memory sitting in between, and some pages not in RAM at all. Wikimedia Commons, CC BY-SA 3.0

Two things in that picture do all the work. The arrows cross over each other, so contiguous in virtual space implies nothing about physical adjacency. And one arrow lands on the disk rather than in RAM — the process cannot tell the difference, which is the whole trick.

Address translation path​

On every memory access, the CPU first checks the TLB — a small, fully-associative-style cache of recent translations right in the MMU. A TLB hit turns translation into effectively free; a TLB miss forces the MMU to walk the page table in memory (itself one or more extra memory accesses) to find the mapping, which is then cached in the TLB for next time. If the page table says the page isn't currently in physical memory at all — or the access violates permissions — the MMU raises a page fault, trapping into the OS to decide what to do (bring the page in from disk, extend the heap, or terminate the process for an invalid access).

What "walks the page table" means concretely is that the address itself is cut into index fields:

A 32-bit linear address split into a 10-bit page directory index, a 10-bit page table index, and a 12-bit offset, with CR3 pointing at the page directory
Classic 32-bit x86 paging. CR3 points at the page directory; bits 31–22 index it, bits 21–12 index the page table it names, and bits 11–0 are the byte offset that never gets translated at all. Wikimedia Commons, CC BY-SA 3.0
This diagram is the 32-bit version, for legibility

64-bit x86 uses the same idea with four levels (PML4 → PDPT → PD → PT), each consuming 9 bits, plus a 12-bit offset — 48 address bits in total, extended to five levels and 57 bits on recent server parts. The structure is identical; there are simply more levels to walk, which is exactly why a TLB miss is expensive and why huge pages (2 MB, 1 GB), which stop the walk a level or two early, are a real optimization.

Practical Usage​

Programs rarely manipulate page tables directly, but the cost of translation shows up in real workloads:

// Sequential access over a large buffer: touches relatively few
// distinct pages per unit of data processed, so the TLB's cached
// translations cover most accesses (good TLB locality).
for (int i = 0; i < n; ++i) {
    sum += data[i];
}

// Pointer-chasing over widely scattered allocations: each dereference
// may land on a different page, increasing TLB misses (and full page
// walks) on top of any cache misses already incurred.
for (Node* node = head; node != nullptr; node = node->next) {
    sum += node->value;
}

This is the same locality-of-reference idea that drives CPU cache performance (see CPU Caches), one level higher up: poor locality costs you both cache misses and TLB misses.

Edge Cases & Pitfalls​

TLB misses are a real, measurable cost

A TLB miss doesn't just cost a lookup — it can trigger a full multi-level page-table walk, which is several extra memory accesses before the original access can even proceed. Workloads that scatter accesses across many pages (large sparse data structures, huge hash tables) can suffer noticeably from TLB pressure even when the CPU cache hit rate looks fine.

  • Page faults are not all equally bad: a minor fault (page not mapped into the TLB/page table yet but the data is already in RAM, e.g. lazily-allocated memory) is cheap; a major fault (the data must be read from disk/swap) is orders of magnitude slower.
  • Page-replacement policy — deciding which resident page to evict when physical memory is full — is an OS-level decision (e.g., approximations of LRU), not something the MMU/TLB decides; see Operating Systems for how the OS manages memory at that level.
  • Larger page sizes ("huge pages") reduce the number of TLB entries needed to cover a given amount of memory, cutting TLB misses for large workloads — but waste memory when allocations are small and don't need a full huge page.

Comparisons​

ConceptManaged byTypical cost when it misses
CPU cache lineHardware (cache controller)Tens to hundreds of cycles (fetch from a lower cache level or DRAM)
TLB entryHardware (MMU)A page-table walk — multiple extra memory accesses
Page (in physical memory)OS + hardware togetherA page fault — potentially a disk/swap read, orders of magnitude slower

References​

Books & Videos​

  • Bryant & O'Hallaron, Computer Systems: A Programmer's Perspective — "Virtual Memory" chapter covers paging, the MMU, and the TLB in depth.
  • Ulrich Drepper, "What Every Programmer Should Know About Memory" — includes a section on TLB behavior and its performance impact.