Virtual Memory and Paging

Definition: A memory management capability that gives each process the illusion of a large, private, contiguous address space, while the OS maps virtual addresses to physical RAM pages behind the scenes via page tables.

How It Works

Virtual address space is divided into fixed-size pages, typically 4KB on x86/ARM (larger “huge pages,” 2MB or 1GB, are available for workloads that benefit from fewer translation entries). Physical RAM is divided into equal-size page frames.
The MMU (Memory Management Unit), a piece of CPU hardware, translates every virtual address a running program uses into a physical address by walking the current process’s page table, a structure the OS maintains and the MMU consults on every memory access.
The TLB (Translation Lookaside Buffer) is a small, fast hardware cache of recent virtual-to-physical translations inside the CPU. Most memory accesses hit the TLB and skip the full page table walk entirely; a TLB miss is what forces the slower walk.
A page fault is triggered when a program accesses a virtual address whose page isn’t currently mapped to physical RAM, either because it’s never been touched, has been swapped out to disk, or the access violates a permission bit (writing to a read-only page). The CPU traps into the kernel’s page fault handler, which decides whether to fetch the page from disk/swap, allocate a fresh page, or deliver a segmentation fault if the access was genuinely invalid.
Each page table entry also carries permission bits, readable, writable, executable, and a present bit indicating whether the page is currently backed by physical RAM at all. These bits are what let the OS enforce W^X (a page is never simultaneously writable and executable) and per-process memory isolation.

Under the Hood

On x86-64, page tables are a 4-level (or 5-level, with 5-level paging on newer CPUs) radix tree: a virtual address is sliced into indices for the PML4, PDPT, PD, and PT levels plus a page offset, and the MMU walks down through each level, following a pointer from one table to the next, until it reaches a page table entry holding the actual physical frame number. Each process has its own top-level table (pointed to by the CR3 register on x86), which is exactly why switching between processes requires reloading CR3, and why that reload invalidates most cached TLB entries for the outgoing process, a real cost captured in Process and Thread’s discussion of context switch overhead.

Demand paging means pages aren’t loaded into RAM until they’re actually accessed for the first time; a freshly mmap()’d region or a newly exec()’d program’s code segment exists as page table entries marked “not present, backed by this file/swap,” and the very first access to each page triggers a page fault that the kernel resolves by reading the actual content in. This is why a process’s virtual memory footprint can be far larger than its resident set size, most of that virtual space is simply never touched.

Copy-on-write, used heavily by fork(), marks shared physical pages read-only in both the parent’s and child’s page tables after a fork; a write from either side triggers a page fault, and the kernel responds by allocating a private copy of just that one page and updating only the writer’s page table entry, not by copying the whole address space upfront.

History

Early systems used segmentation instead of paging, dividing memory into variable-size, logically meaningful chunks (code, data, stack) with base and limit registers. It mapped naturally onto how programs are structured, but variable-size segments suffer external fragmentation the same way variable-size heap allocations do.
Paging emerged in the 1960s (notably in the Atlas computer and later Multics) specifically to fix that fragmentation problem, by making every unit of allocation the same fixed size, at the cost of losing the “logical unit” meaning a segment naturally had.
Some systems (early x86 in particular) combined both, segmented paging, dividing the address space into segments that were each further paged, largely as a transitional/compatibility feature. Essentially no modern general-purpose OS uses segmentation as a primary memory management mechanism today; x86-64 mode removed most of the classic segmentation machinery entirely.
Demand paging and swapping became standard as systems needed to run programs larger than physical RAM, evolving from purely swapping entire processes in and out (early time-sharing systems) to today’s fine-grained, per-page demand loading.

Debugging Workflow

Diagnosing thrashing or unexpected memory pressure starts with distinguishing “using a lot of memory” from “actively swapping,” which are very different problems:

$ vmstat 1
procs -----------memory---------- ---swap-- -----io----
 r  b   swpd   free   buff  cache   si   so    bi    bo
 4  2  102400  51200  8200 380000  512  480   600   550

Non-zero, sustained si/so (swap in/out) alongside a nonzero b (blocked) column is the thrashing signature: processes are blocked waiting on pages that are actively being swapped in and out, not just sitting in a large-but-stable working set.

$ cat /proc/<pid>/smaps | grep -A2 "^7f"      # per-mapping resident/shared/swap detail
$ cat /proc/<pid>/status | grep -E "VmRSS|VmSwap"
$ perf stat -e dTLB-load-misses ./app          # TLB miss rate for a specific workload

/proc/<pid>/smaps breaks down exactly which mapped region (a specific library, the heap, a memory-mapped file) is resident versus swapped, which turns “the process uses too much memory” into “this specific 400MB mapping is the one growing,” a much more actionable finding. A high TLB miss rate from perf stat on a CPU-bound workload with otherwise-idle-looking memory usage is the signal that huge pages or better memory access locality, not more RAM, is the actual fix needed.

Why It Matters

Provides strict memory isolation between processes: two processes’ identical-looking virtual addresses map to entirely different physical RAM, so one process cannot accidentally, or maliciously, read or write another’s memory without going through the kernel’s controlled IPC mechanisms.
Allows running programs whose total virtual memory usage exceeds physical RAM, since inactive pages can be evicted to swap (or simply discarded, if they’re backed by a file and unmodified) and re-fetched on demand.
Simplifies memory allocation for both the OS and applications: a process’s address space can look contiguous even when the physical frames backing it are scattered anywhere in RAM, which is what makes a simple linear heap/stack layout possible without the OS needing to find one giant contiguous block of physical memory.

Common Pitfalls

Thrashing: when a process’s (or the whole system’s) working set exceeds available RAM, the kernel spends more time evicting and re-fetching pages than doing actual work, cratering throughput. Visible in vmstat as high si/so (swap in/out) activity alongside low CPU utilization.
Assuming allocated (virtual) memory equals used (physical) memory. malloc() reserving a large virtual region doesn’t consume physical RAM until the pages are actually touched, which is why VSZ and RSS in ps/top can differ by orders of magnitude.
Dereferencing a null or wild pointer typically hits an unmapped page and produces a SIGSEGV, a page fault the kernel determines is not a legitimate demand-paging case, rather than silently corrupting arbitrary memory, one of the practical safety benefits of paging-based isolation.
Ignoring TLB pressure in performance-sensitive code. Randomly scattering memory accesses across many pages causes frequent TLB misses and full page-table walks; huge pages reduce this by covering far more address space per TLB entry, at the cost of coarser-grained allocation.
Confusing paging with segmentation. Paging maps fixed-size pages transparently to the program; segmentation (largely a legacy x86 feature now) divides memory into variable-size, logically meaningful segments (code, data, stack) with their own base/limit, a different, mostly obsolete approach to the same isolation problem.

Page Replacement

When physical RAM is full and a page fault needs a free frame, the kernel must choose an existing page to evict. The theoretically optimal choice, evict the page that won’t be needed for the longest time, isn’t computable without knowing the future, so real systems approximate it:

LRU (Least Recently Used): evict the page that hasn’t been accessed in the longest time, on the assumption that recent access predicts near-future access. True LRU is expensive to track exactly for every page, so most kernels approximate it.
Clock / Second-Chance: pages are arranged in a circular list with a reference bit set by the hardware on access. A “clock hand” sweeps the list; a page with its reference bit set gets a second chance (bit cleared, hand moves on) instead of being evicted immediately, approximating LRU far more cheaply than tracking exact access order.
Linux uses a refinement of this idea, two page lists (active and inactive) that pages move between based on recent access, roughly approximating LRU behavior while remaining cheap to maintain at scale.

Comparison

	Paging	Segmentation	Swap / Page File
Unit size	Fixed (e.g., 4KB)	Variable, logical (code/data/stack)	Fixed pages written to disk
Fragmentation	Internal only	External (variable sizes)	N/A
Transparent to program	Yes	Mostly (legacy x86 exposes segment registers)	Yes
Modern relevance	Universal (Linux, Windows, macOS)	Largely obsolete on x86-64	Universal, but SSD-era systems favor avoiding heavy use
Address translation hardware	MMU + page tables + TLB	Segment base/limit registers	N/A (storage mechanism, not translation)
Typical failure mode	Page fault, thrashing under memory pressure	External fragmentation	Thrashing if working set exceeds RAM

Multi-Level Translation Walkthrough

A 48-bit x86-64 virtual address is sliced into five fields: bits 47-39 index the PML4, 38-30 index the PDPT, 29-21 index the PD, 20-12 index the PT, and bits 11-0 are the offset within the final 4KB page. The MMU reads CR3 to find the PML4 table’s physical address, uses the first 9-bit field to pick an entry pointing to a PDPT, repeats for the PDPT and PD to find the PT, then uses the PT entry to get the actual physical frame number, and finally appends the 12-bit offset to land on the exact byte. Each level is a fresh memory access unless cached, which is exactly why a TLB hit that skips all four lookups is so much faster than a full walk, and why TLB miss rate is a real performance metric profilers track.

Example

Accessing a null pointer (address 0x0) hits an unmapped page and the MMU’s page fault handler determines the access is invalid, delivering a segmentation fault rather than allowing the read:

int *p = NULL;
int x = *p;         // dereference: MMU looks up virtual address 0x0
                     // page table: no valid mapping / permission denied
                     // -> page fault -> kernel decides it's not a legitimate case
                     // -> SIGSEGV delivered to the process

/proc/<pid>/smaps on Linux breaks down a process’s exact memory mappings, showing which regions are resident, shared, or swapped, and vmstat 1 shows live system-wide paging and swap activity, the standard first check when diagnosing thrashing.

FAQ

Does more RAM mean the page table gets bigger? Not directly, page table size scales with the size of a process’s virtual address space and how much of it is actually mapped, not with total system RAM. But more RAM does mean fewer pages need to be evicted to swap, reducing page fault frequency under load.

Why do 64-bit systems need multi-level page tables instead of one big flat table? A single-level table covering a full 64-bit address space would need to be astronomically large even though almost all of that space is unused by any given process. Multi-level tables only allocate the branches actually needed for the regions a process has mapped, leaving unused portions of the address space costing nothing.

Is swap always bad? No. Swap lets the kernel evict genuinely cold, rarely touched pages to free RAM for active work, which can improve overall throughput. It becomes a problem specifically when the actively used working set itself exceeds RAM, forcing constant back-and-forth reloading, which is thrashing.

Referenced by

Dig deeper

Spot an error in this note?