Virtual Memory and Paging

Virtual memory is the operating system's grandest illusion: every process sees a private, contiguous address space, while the OS and hardware translate, share, and swap the underlying physical frames. It is the mechanism behind process isolation, memory-mapped files, copy-on-write forking, and the performance cliffs that appear when the illusion gets expensive.

Address translation and page tables

Memory is divided into fixed-size pages (4 KB baseline). A virtual address splits into (virtual page number, offset); the page table maps VPN → physical frame, with per-page permission bits (read/write/execute — the substrate of W^X protections) and a present bit. Flat tables would be enormous, so real tables are multi-level radix trees (four levels on x86-64), walked on demand — sparse address spaces cost only the levels they touch. Each process has its own root, swapped on context switch: that one register swap is memory isolation.

The TLB: why translation is usually free

A page-table walk costs several memory accesses, so a Translation Lookaside Buffer caches recent translations; hit rates above 99% make translation effectively free. The consequences engineers actually feel:

TLB misses are a hidden tax on scattered access patterns — part of why pointer-chasing structures lose to arrays beyond cache effects.
Huge pages (2 MB / 1 GB) multiply TLB reach; databases and JVMs with large heaps enable them for real wins.
Context switches historically flushed the TLB; address-space identifiers and tagged TLBs reduce that cost — but the Meltdown-era page-table isolation work made kernel/user transitions more expensive again, a rare case of security walking back a performance optimization.

Page faults, demand paging, and replacement

Accessing a non-present page traps to the OS — a page fault. Minor faults allocate or map a page (demand paging: nothing is loaded until touched; malloc'd memory is typically zero-filled lazily). Major faults read from disk — orders of magnitude slower. When physical memory is full, a replacement policy picks a victim:

OPT (evict the page used farthest in the future) — unimplementable, the yardstick.
LRU — good but too expensive to track exactly per-access, so real kernels approximate with the clock/second-chance algorithm: a circular scan clearing hardware referenced-bits, evicting pages not re-referenced in a full sweep. Two-list variants (active/inactive in Linux) refine it.
Bélády's anomaly — FIFO can fault more with more memory; the classroom proof that plausible policies can be perverse.

When the sum of working sets exceeds RAM, the system thrashes — all page-fault service, no progress. The working-set model gives the vocabulary: keep each process's recently-touched page set resident or don't run it. Modern practice prefers the OOM killer and cgroup memory limits to swapping into oblivion; on servers, meaningful sustained major-fault rates are an alert, not a tuning opportunity.

The tricks the mechanism enables

Copy-on-write: fork() shares all pages read-only; only writes fault and copy — why forking a large process is cheap and why redis-style fork-and-snapshot works.
Memory-mapped files (mmap): file I/O through page faults; the file cache is memory. Databases and language runtimes build on it, with the caveat that error handling (SIGBUS on truncation) and writeback control are subtler than read/write.
Shared memory and libraries: one physical copy of libc mapped everywhere.
Overcommit: the OS promises more virtual memory than exists, betting most is never touched — usually right, and the reason the OOM killer exists for when it is wrong.
Swap as spillover: with fast NVMe and compressed in-RAM swap (zswap), modest swapping of truly-cold pages is cheap insurance rather than a performance emergency.

What this explains for the working engineer

Why your process's RSS differs from virtual size (demand paging + overcommit); why the first pass over a big allocation is slow (fault-in) and the second is fast; why JVM heap sizing interacts with container memory limits (the OOM killer counts pages, not promises); and why sequential access is kind to every layer of the illusion at once — caches, TLB, prefetchers, and readahead all reward it.