How Virtual Memory Works

Every process on a modern operating system believes it has a contiguous, private address space starting at address zero. None of it is true. The physical memory is shared across all processes, fragmented into pages, and managed by the kernel's virtual memory subsystem. The illusion is so complete that most engineers never think about it — until a process gets killed for using too much memory, or a page fault takes 10 milliseconds instead of 100 nanoseconds, and the entire performance model collapses.

The illusion: contiguous private address space

When your program reads variable x at address 0x7ffe8a3b1c40, it does not read from physical address 0x7ffe8a3b1c40. The CPU translates the virtual address to a physical address using a page table — a data structure maintained by the kernel and hardware:

virtual address                    physical address
0x7ffe8a3b1c40     ──→  page table  ──→  0x1a3f4000
 
┌──────────────────┐
│ page table       │
│ ┌──────┬───────┐ │
│ │ VPN  │ PFN   │ │
│ ├──────┼───────┤ │
│ │ 0x7f │ 0x1a3 │ │
│ │ 0x80 │ 0x2b1 │ │
│ │  ... │  ...  │ │
│ └──────┴───────┘ │
└──────────────────┘
 
VPN = Virtual Page Number
PFN = Physical Frame Number

Every process has its own page table. The same virtual address in two different processes maps to different physical addresses. This is how processes are isolated — process A cannot read process B's memory because the page table entries don't exist.

Pages and page tables

Memory is divided into fixed-size pages (typically 4 KB on x86-64). The virtual address is split into a page number and an offset within the page:

64-bit virtual address:
┌─────────────────────┬──────────┐
│ Virtual Page Number  │ Offset   │
│ (top 52 bits)       │ (12 bits)│
└─────────────────────┴──────────┘
        │
        ▼  page table lookup
┌─────────────────────┬──────────┐
│ Physical Frame Number│ Offset   │
│ (top 52 bits)       │ (12 bits)│
└─────────────────────┴──────────┘
        │
        ▼
physical address

A single-level page table for 64-bit addresses would be impossibly large (2^52 entries × 8 bytes = 32 PB). No machine has that much RAM. The solution is multi-level page tables — a hierarchy of tables where unused regions of the address space don't require entries:

Level 1 (PML4)    → 512 entries × 8 bytes = 4 KB (one page)
Level 2 (PDPT)    → 512 entries × 8 bytes = 4 KB per L1 entry
Level 3 (PD)      → 512 entries × 8 bytes = 4 KB per L2 entry
Level 4 (PT)      → 512 entries × 8 bytes = 4 KB per L3 entry
 
total: 4 levels × 512 entries = covers 2^48 bytes = 256 TB

A process using only 4 GB of memory needs: 1 PML4 entry, a handful of PDPT entries, some PD entries, and the actual page table entries for the 4 GB. The rest of the page table hierarchy is not allocated. This is why page tables are not 32 PB — unused address space costs nothing.

The TLB: the hardware cache that makes it fast

Every memory access requires a page table lookup — 4 memory accesses for x86-64. At 100 nanoseconds per access, that's 400 nanoseconds per memory read. Worse than useless.

The Translation Lookaside Buffer (TLB) is a hardware cache that stores recently used virtual-to-physical translations:

memory access:
1. Check TLB (fast, ~1 ns)
   ├─ TLB hit: use cached translation → 1 ns total
   └─ TLB miss: walk page table (slow, ~100-400 ns)
              → store result in TLB → next access is fast

The TLB is small (64–1536 entries on modern CPUs) but extremely effective. A typical program has a working set of a few hundred pages, and the TLB covers most of them. The TLB hit rate is typically 99%+.

When the TLB misses — a TLB miss — the CPU walks the page table in hardware. This costs 4–5 memory accesses (~400–500 ns). If the page table itself is not in L1/L2 cache (which it usually is for hot pages), the cost increases.

The performance impact of TLB misses is enormous. A database with a 100 GB buffer pool and 4 KB pages has 25 million pages. The TLB cannot cover them all. The database pays TLB miss overhead on every access to a cold page — which is exactly the pages that are most expensive to access anyway (they're cold because they were just loaded from disk).

Large pages (2 MB or 1 GB) reduce TLB misses by covering more address space per entry. A 2 MB page covers 512× more memory than a 4 KB page, so the TLB's 64 entries cover 128 MB instead of 256 KB. Databases and JVMs use large pages explicitly for this reason.

Demand paging: the lazy allocation trick

The kernel does not allocate physical memory when a process requests it. It allocates a virtual mapping — a page table entry that says "this virtual page should map to physical memory, but I haven't decided which physical page yet."

The actual allocation happens on first access — the page fault:

process accesses virtual page 0x7ffe8a3b1
  → page table entry is "not present"
  → CPU triggers page fault
  → kernel handler:
      1. allocate a physical frame
      2. update the page table entry
      3. zero the frame (security: no old data)
      4. resume the instruction
  → process continues, unaware of the fault

This is demand paging — physical memory is allocated only when the process actually uses it. A process that allocates 1 GB of memory but touches only 4 KB uses only 4 KB of physical memory. The rest is virtual — a promise, not a commitment.

This is why malloc (or new) never fails immediately. The virtual address space is virtually unlimited (256 TB on x86-64). The physical memory is limited. The OS gives every process a generous virtual address space and relies on demand paging to defer the physical cost.

Page replacement: when memory is full

When physical memory is full and a new page must be allocated, the kernel must evict an existing page — choosing which page to remove is the page replacement problem:

The kernel maintains an active list (recently accessed pages) and an inactive list (candidates for eviction). Pages age from active to inactive over time. When a page in the inactive list is accessed, it is promoted back to active. This is called the clock algorithm or two-handed clock and is how Linux actually manages page replacement.

The swap space is a dedicated partition or file on disk that holds evicted pages. When a swapped-out page is accessed, the kernel must read it back from disk — this is a major page fault and costs 5–20 milliseconds (disk seek + rotation + transfer). A minor page fault (allocating a new frame) costs ~1 microsecond. The difference is 1,000–20,000×.

Copy-on-write: the fork optimization

When a process calls fork(), the kernel does not copy the entire address space. Instead, it marks all pages as copy-on-write (COW) — shared between parent and child with the "read-only" flag set:

fork():
parent page table ──→ physical frame 0x1a3  (read-only)
child page table  ──→ physical frame 0x1a3  (read-only, same frame)
 
child writes to page:
  → page fault (COW triggered)
  → kernel copies the frame to a new frame
  → both page tables now point to different frames
  → child continues writing to its copy

COW makes fork() nearly free — the only cost is duplicating the page tables (a few kilobytes), not the process's entire memory. This is why fork() + exec() (the Unix process creation pattern) is fast: the child forks, immediately execs a new program, and discards the parent's pages without ever copying them.

Without COW, every fork() would copy the entire address space — a 4 GB process would take 4 GB of memory and hundreds of milliseconds to fork. With COW, the fork takes microseconds and shares physical memory until divergence.

What this means for your code

1. malloc is not allocation — it is a promise. The cost is deferred to the first write, which triggers a page fault. Pre-touching pages (writing to every page) forces the kernel to allocate physical frames immediately, making the actual access predictable.

2. TLB misses are the hidden cost of large data structures. A hash table that spans millions of pages pays TLB miss overhead on every access. Large pages (2 MB) reduce this dramatically.

3. Swapping kills performance. A process that uses more physical memory than available RAM triggers swapping — disk I/O on every page access. Monitor vmstat for si/so (swap in/out). If either is non-zero, your process is thrashing.

4. fork() is fast because of COW, but exec() is what you usually want. If you fork without exec, both processes share pages until one writes — then you pay the copy cost. The fork + exec pattern avoids the copy entirely.

5. Memory overcommit is the default. Linux allows processes to allocate more virtual memory than physical RAM exists (vm.overcommit_memory=1). This works until it doesn't — when the OOM killer fires, it kills the process with the highest RSS, not the one that caused the overcommit. vm.overcommit_memory=2 limits overcommit to the swap space, which is safer for production.