Virtual Memory: Paging, TLBs, and Demand Paging Explained

Virtual memory is one of the most important abstractions in computer science. It gives every process the illusion of having its own private, contiguous address space, potentially larger than physical memory, while the operating system and hardware manage the translation and selective loading of pages behind the scenes. Without virtual memory, modern multiprogramming, process isolation, and demand-paged execution would be impossible. This guide examines the mechanisms — page tables, TLBs, demand paging, page replacement — that make virtual memory work.

The Abstraction: Virtual Address Spaces

Every process on a 64-bit x86 Linux system sees a 48-bit virtual address space (256 TB), split into user space (lower half, addresses 0x0000000000000000 to 0x00007FFFFFFFFFFF) and kernel space (upper half, addresses 0xFFFF800000000000 to 0xFFFFFFFFFFFFFFFF). The kernel maps itself into every process’s address space — this is why system calls are fast: the kernel page tables are already mapped, so no TLB flush is needed on kernel entry (on x86-64 with PTI — Page Table Isolation — this is modified for Meltdown mitigation, but the principle holds for performance-sensitive paths).

User-space programs see addresses 0 through some maximum (typically 47 bits). The program allocates memory with malloc() (which calls brk() or mmap()), accesses it with load/store instructions, and never needs to know where the data physically resides. The illusion is maintained by the MMU and maintained by the OS.

Multi-Level Page Tables

The page table is the data structure that maps virtual page numbers (VPNs) to physical frame numbers (PFNs). A naive flat page table for a 48-bit virtual address space with 4 KB pages would require 2^36 entries — each process would need 512 GB of page tables, which is obviously unacceptable.

Multi-level page tables solve this by storing only the table entries that correspond to allocated virtual memory regions. The x86-64 architecture specifies a 4-level page table:

Each entry is 8 bytes. A 4 KB page at L4 holds 512 entries. A process that uses 8 MB of memory needs approximately 19 pages for its page tables (1 PML4, 1 PDPT, 1 PD, 16 PT) — around 76 KB, a dramatic savings over the flat approach.

With 5-level paging (Ice Lake and later), a fifth level (PML5) extends the virtual address space to 57 bits (128 PB), with each PML5 entry covering 256 TB.

Each page table entry contains not just the PFN but also permission bits (readable, writable, executable), accessed and dirty flags (set by hardware on each access/write), cacheability controls, and the present bit. If the present bit is 0, the MMU raises a page fault, and the OS handles the missing page.

The Translation Lookaside Buffer (TLB)

Every instruction fetch and every data load/store accesses the page tables. A 4-level page table walk requires 4 sequential memory reads — approximately 20–50 nanoseconds on a cache-hot system and much more if the page table pages are not cached. If every memory access required a page table walk, virtual memory would be prohibitively slow.

The TLB is a hardware cache that stores recently used VPN→PFN translations. A TLB lookup completes in a single CPU cycle (0.25–0.5 ns). On x86-64, the L1 TLB typically has 64 entries for data and 64 for instructions. The L2 TLB (unified) has approximately 1,500 entries. A TLB hit delivers the translation with zero additional latency. A TLB miss triggers the hardware page walker (a dedicated state machine in modern CPUs) that performs the 4-level table walk and refills the TLB.

TLB Reach and Huge Pages

TLB reach is the total amount of memory that can be referenced without TLB misses:

TLB reach = TLB_entries × page_size

With 64 L1 TLB entries and 4 KB pages, reach is only 256 KB. Most application working sets exceed this, so TLB misses on hot data paths are a primary source of performance degradation.

Huge pages increase reach dramatically. A 2 MB page covers 512× the memory of a 4 KB page per TLB entry. With 64 TLB entries and 2 MB pages, reach is 128 MB. With 1 GB pages, reach is 64 GB. Databases (PostgreSQL, Oracle, MySQL with large buffer pools), Java VMs (with large heaps), and virtual machine monitors all benefit significantly from huge pages.

Linux supports transparent huge pages (THP), which automatically promotes groups of 4 KB pages to 2 MB pages when contiguous physical memory is available. Explicit huge pages are managed via hugetlbfs.

Demand Paging and Page Fault Handling

Demand paging loads pages from disk only when they are accessed. When the program is first loaded, the kernel does not load the entire executable into memory — it records the file mapping in the process’s page tables with the present bit cleared. When the program accesses its first instruction, the MMU raises a page fault.

The page fault handler runs:

1. The faulting virtual address is read from the CR2 register (on x86-64).
2. The handler determines the fault type: a protection violation (writing to a read-only page) or a missing page (not-present).
3. For a missing page, the handler identifies the backing store — the file on disk (for executable code, memory-mapped files) or the swap device (for anonymous memory).
4. The handler allocates a physical page frame (from the free list, or by evicting a page).
5. It schedules I/O to read the page content from disk.
6. The handler updates the page table entry with the physical frame number and sets the present bit.
7. It restarts the faulting instruction.

Demand paging enables processes with large virtual address spaces to use only a fraction of physical memory. A web browser with 2 GB of virtual address space may only have 200 MB actively resident. The rest exists on disk (swap or file backing).

Prefetching and Read-Ahead

The kernel also implements page cache read-ahead: when a process reads a file sequentially, the kernel prefetches the next several pages. For a 4 KB read, the kernel may read 16 KB (4 pages) in anticipation of sequential access. The Linux read-ahead algorithm (mm/readahead.c) dynamically adjusts the read-ahead window based on observed access patterns, doubling the window on sequential access and halving it on random access.

Page Replacement Algorithms

When the system runs low on free pages, the kernel must evict pages to make room. The choice of eviction victim substantially affects performance.

LRU Approximation: The Clock Algorithm

True LRU (maintaining a fully ordered access list) is too expensive. The Clock algorithm approximates it efficiently. Page frames are arranged in a circular list. Each frame has a reference bit (accessed bit), set by the MMU hardware on any access. The page replacement code sweeps a pointer (the clock hand) around the circle:

• If the current page’s reference bit is 1, clear it and advance the hand.
• If the reference bit is 0, evict this page.
• If the page is dirty (modified bit set), schedule writeback before eviction — many algorithms give dirty pages a second chance to avoid immediate I/O.

The Linux kernel uses a variant called the multi-generational LRU (MGLRU, merged in Linux 6.1), which maintains multiple LRU lists (active, inactive, and per-generation lists) to better distinguish frequently accessed pages from one-time accessed pages. MGLRU substantially reduces page reclaim overhead on memory-intensive workloads.

Working Set Model

Peter Denning’s working set model (1968) is the theoretical foundation for page replacement. The working set is the set of pages a process has referenced in the last Δ units of virtual time (the working set window). If the working set of all processes exceeds physical memory, the system thrashs — page faults occur so frequently that the CPU is mostly waiting for disk I/O.

The Linux kernel detects thrashing through the page fault rate: when scanning for pages to evict, if it finds pages that are referenced again immediately, it reduces the scanning rate. If it scans many pages without finding evictable pages, memory pressure is high.

Memory-Mapped Files

Memory-mapped files unify file I/O and virtual memory. A file (or portion of a file) is mapped into the process’s virtual address space with mmap(). Accessing the mapped region as memory causes the kernel to fault in the corresponding file pages. This is more efficient than read()/write() because:

• The kernel manages caching transparently — file data lives in the page cache, shared across all processes that map the same file.
• No explicit I/O system calls are needed — data is transferred on page faults.
• Multiple processes can share the same physical pages for shared libraries or interprocess communication (MAP_SHARED).

Executable loading uses mmap: the kernel maps each segment of the ELF binary into the process’s address space with the appropriate permissions (code segment: read+execute; data segment: read+write). The pages are faulted in on demand.

FAQ

What is the difference between virtual memory and physical memory?

Virtual memory is the address space a process sees — a continuous range starting from 0, managed by the OS, and translated by the MMU. Physical memory is the actual DRAM installed in the system. The virtual memory system maps virtual pages to physical frames; pages not currently needed may reside on disk (swap) and are loaded on demand. This allows processes to use more virtual memory than physical RAM exists.

How does swapping differ from paging?

Paging transfers individual pages (4 KB or larger) between memory and disk. Swapping transfers entire processes between memory and a swap device. When a process is swapped out, all of its pages are written to the swap device, freeing all its physical frames. Swapping is coarser-grained than paging and is used primarily when the system is critically low on memory. Linux performs swapping as a last resort, preferring page-level demand paging and reclaim.

Why do large pages (huge pages) improve performance for databases?

Databases manage large buffer pools (typically 10–100 GB of cached data) with regular access patterns. With 4 KB pages, querying 10 GB of random data requires TLB entries for 2.5 million pages — far exceeding the TLB’s capacity. With 2 MB huge pages, only 5,120 TLB entries are needed, dramatically reducing TLB miss rates. PostgreSQL recommends configuring huge pages for instances with shared_buffers over 1 GB.

What happens on a TLB miss?

The hardware page walker (a dedicated state machine in modern x86 CPUs) traverses the multi-level page table: reading the PML4 entry, then the PDPT entry, then the PD entry, then the PT entry, using the page table base address from CR3. The resulting translation is written to the TLB, and the faulting instruction is restarted. In 4-level paging, a TLB miss costs approximately 4–12 memory accesses (level tables may be cached in L2/L3). Software-managed TLB fills (used on MIPS and some SPARC architectures) raise a TLB miss exception and let the OS fill the TLB.

How does virtual memory affect security?

Virtual memory provides process isolation — Process A cannot access Process B’s virtual pages because the page tables map different physical frames. Page Table Isolation (PTI, KPTI) separates kernel and user page tables to mitigate Meltdown: user-mode page tables contain only the minimal kernel information needed for system call entry/exit. ASLR (Address Space Layout Randomization) randomizes the base addresses of stack, heap, and mmap regions to make exploitation harder by preventing attackers from predicting address locations.

The Memory Management Guide provides the broader context covering physical memory allocation and the buddy allocator. The File Systems Guide explains the page cache integration with the VFS layer. The Linux kernel source in mm/ contains the complete implementations; Documentation/admin-guide/mm/ provides tuning documentation. The classic theoretical treatment is Denning’s “Virtual Memory” in Computing Surveys (1970). Silberschatz, Galvin, and Gagne, Operating System Concepts (10th ed.), Chapter 9, provides comprehensive textbook coverage.