Virtual Memory & Demand Paging

Back in the introduction we made a bold promise on the OS's behalf: every process gets a huge, private, contiguous address space that starts at zero and stretches far beyond the physical memory installed in the machine. On a 64-bit system that space is astronomically large — terabytes — and obviously no single program's data is actually that big, nor could it fit in RAM if it were. Virtual memory is how the OS keeps that promise without lying: it decouples the size of the address space from the size of physical memory.

The trick is that a virtual page does not have to live in RAM to exist. A page can be in one of a few states: resident in a physical frame, sitting out on disk in a swap area or backing store, or not yet materialised at all (a freshly allocated but never-touched page). The page table records, for each page, which of these it is. As long as the MMU can find a page or trap to the OS when it cannot, the process experiences one seamless address space — even though its pages are scattered between RAM and disk at any moment.

Virtual memory

The illusion that each process has a large, private address space independent of how much physical RAM exists; pages live in RAM or on disk as needed.

Resident page

A virtual page that currently occupies a physical frame in RAM — its page-table entry is valid.

Backing store / swap

The disk area that holds pages which are not currently in RAM, so the OS can bring them back when touched.

Overcommit

Allowing the sum of all processes' address spaces to exceed physical RAM, on the bet that not all of it is needed at once.

The naive way to run a program is to load the whole thing into memory before it starts. Demand paging does the opposite: load nothing up front, and bring in each page only at the moment the program first refers to it — lazily, on demand. When the OS sets up a process's address space (during exec, say), it maps the pages to their locations on disk but marks every page-table entry as not present by clearing the valid bit. No RAM is committed yet. The very first instruction fetch touches a code page that is not resident, which faults, which pulls that one page in. Execution proceeds page by page, each one arriving just in time.

This is the same valid bit from the paging chapter, now doing real work. Then, an invalid entry meant "not mapped — probably a bug". Now it means one of two things: either the reference is genuinely illegal (a wild pointer, and the OS delivers a segmentation fault), or the page is legal but simply not in RAM yet (and the OS silently fetches it). The kernel tells them apart by checking the reference against the process's memory map: is this address inside a region the process is allowed to use?

• ▸Faster startup: a program begins running after only its first few pages are in, not after the whole binary is read from disk.
• ▸Less memory used: pages that a run never touches — error handlers, rarely-used features, a huge lookup table behind a branch you don't take — never occupy a single frame.
• ▸Overcommit becomes practical: because a process rarely needs all its pages resident at once, many processes can share limited RAM.

The page fault is the single most important mechanism in this chapter, and it is worth being able to recite. A page fault is not an error in the everyday sense — it is a hardware trap that says "the page you want is not present; someone in the kernel needs to deal with this before the instruction can complete". Here is the full round trip.

• ▸The CPU executes an instruction that references a virtual address; the MMU walks the page table to translate it.
• ▸The MMU finds the page-table entry with its valid bit clear. It cannot complete the translation, so it raises a page-fault trap — the CPU switches to kernel mode and jumps to the page-fault handler, saving enough state to resume later.
• ▸The handler first decides whether the reference is even legal by checking the faulting address against the process's memory regions. If it is bogus, the process gets a SIGSEGV. If it is legal, this is a real demand-paging fault and the handler continues.
• ▸The OS locates the page's contents on disk — in the swap area, or in the file that backs this mapping — and picks a physical frame to hold it. If no frame is free, it must evict a resident page to make room (that eviction decision is the whole of the next chapter).
• ▸The OS issues a disk read to copy the page into the chosen frame. Because disk is slow, the faulting process is blocked and the CPU is handed to some other ready process in the meantime — a page fault is a scheduling event as much as a memory event.
• ▸When the read completes, the OS updates the page-table entry to point at the frame and sets its valid bit, then returns from the trap.
• ▸Crucially, the CPU restarts the very instruction that faulted. This time the translation succeeds, the access completes, and the program continues with no idea anything unusual happened.

That final restart is the subtle, elegant part. The faulting instruction is not skipped or emulated — it is simply re-run from scratch now that its page is present. This is why the whole scheme is invisible to your program: from its point of view the memory access just took a while. It is also why instructions must be restartable, a constraint that shapes CPU design.

Not all page faults cost the same, and the difference is enormous. The OS and hardware both distinguish two kinds. A minor fault (also called a soft fault) happens when the page is already somewhere in physical memory — it just is not yet mapped into this process's page table. Maybe another process already loaded the same file page, maybe it is sitting in the page cache, maybe it is a copy-on-write page being shared. The handler only has to point a page-table entry at an existing frame and set the valid bit. No disk involved; the whole thing takes microseconds or less.

A major fault (a hard fault) is the expensive one: the page is not in RAM at all and must be read from disk — from the swap area or from a file. Now the process blocks on physical I/O, and even on a fast SSD that is orders of magnitude slower than a memory access; on a spinning disk it is worse still. The ratio between a memory access and a disk read is roughly a thousandfold or more, so a program's performance is dominated not by how many faults it takes but by how many of them are major.

This is not academic — you can measure it directly, and doing so is often the fastest way to diagnose a program that is mysteriously slow or that gets slower as memory pressure rises.

$ /usr/bin/time -v ./my_program
   ...
   Maximum resident set size (kbytes): 812304
   Major (requiring I/O) page faults: 12
   Minor (reclaiming a frame) page faults: 40213
   ...

# A live view across all processes: the "maj/min flt" columns.
$ ps -o pid,maj_flt,min_flt,cmd -p $(pgrep -n my_program)
  PID MAJFL   MINFL CMD
 4812   12   40213 ./my_program

Demand paging sounds like it should be catastrophically slow — surely a program constantly hitting pages that are not resident will spend all its time waiting on disk? It does not, and the reason is one of the most important empirical facts in computing: locality of reference. Programs do not touch their memory uniformly at random. Over any short window they touch a small, clustered set of pages, again and again.

Temporal locality

A page touched recently is likely to be touched again soon — loop bodies, hot data structures, the current stack frame.

Spatial locality

If a page is touched, nearby pages are likely to be touched too — sequential array scans, adjacent struct fields, instruction streams.

Working set

The set of pages a process has referenced in the recent past (a sliding time window); a good estimate of what it needs resident right now.

The working-set model turns locality into a strategy. If the OS keeps each process's working set resident in RAM, then the overwhelming majority of memory references hit pages that are already present — so faults are rare, and the ones that occur are cheap minor faults. Demand paging pays its startup cost once, warms up the working set, and then runs at near-full memory speed. This is precisely why loading a whole program up front is wasteful: most of it is never in the working set at any given moment.

The model also predicts exactly when things fall apart. If the combined working sets of the running processes exceed physical RAM, the OS cannot keep them all resident. Pages the processes actively need keep getting evicted and immediately faulted back in, and major faults explode. The system spends its time shuttling pages to and from disk instead of doing work — thrashing, which we devote a later chapter to. The working set is the boundary between "virtual memory is free money" and "virtual memory is killing us".

Back in the process chapters we met fork(), which creates a child process as a duplicate of its parent — same code, same data, same open files. Taken literally, that means copying the parent's entire address space, which for a large process could be gigabytes. And it is usually wasted work, because the very next thing the child does is often exec() a different program, throwing all those copied pages away. Copy-on-write (COW) is the optimisation that makes fork() cheap, and it is built entirely from the page-fault machinery.

When a process forks, the OS does not copy any data pages. Instead it gives the child its own page table whose entries point at the parent's existing frames — and marks every shared page read-only in both processes, tagging it internally as copy-on-write. As long as both processes only read, they happily share the same physical frames, and fork has cost almost nothing but a page table. The copy is deferred until it is actually needed.

The moment either process tries to write to a COW page, the read-only mapping causes a protection fault — a trap into the kernel. The handler recognises it as a COW fault, allocates a fresh frame, copies the one page into it, points the writing process's page-table entry at the private copy, and marks both copies writable again. The instruction restarts and the write succeeds. Only the pages actually written ever get duplicated; everything else stays shared for the life of the processes. This is why fork() followed by exec() is fast, and why forking a huge process is not the disaster it looks like.

Demand paging does not only pull pages from swap — it can pull them straight from a file, and that is what memory-mapped files expose to you directly. The mmap() system call maps a file (or part of one) into a range of your virtual address space. After that, you access the file's contents as ordinary memory: dereference a pointer to read a byte, assign through a pointer to write one. There is no read() or write() in the loop at all.

Under the hood it is pure demand paging. mmap sets up the mapping with every page marked not-present; it copies nothing. The first time you touch a page of the mapping, you take a page fault, and the OS reads the corresponding block of the file into a frame and maps it in — exactly the fault flow from earlier, with the file as the backing store instead of swap. Pages you never touch are never read. Two processes that map the same file can share the same physical frames, which is precisely how the OS loads shared libraries once and shares them across every program that uses them.

#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdio.h>

int main(int argc, char **argv) {
    int fd = open(argv[1], O_RDONLY);
    struct stat st; fstat(fd, &st);

    /* Project the whole file into our address space. No data read yet. */
    char *data = mmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
    if (data == MAP_FAILED) { perror("mmap"); return 1; }

    /* Touching data[i] faults the matching file page in on demand. */
    long spaces = 0;
    for (off_t i = 0; i < st.st_size; i++)
        if (data[i] == ' ') spaces++;

    printf("%ld spaces\n", spaces);
    munmap(data, st.st_size);
    close(fd);
    return 0;
}

This is not a toy. Program loaders map executables and shared libraries this way; language runtimes map large read-only data files; and databases lean on mmap (or the same underlying page-cache machinery) to treat on-disk files as if they were memory, letting the OS handle which parts are resident. It lets you work with a file far larger than RAM using nothing but pointers, and it avoids the extra copy that read() makes into your buffer — the file page in the cache is the memory you read.

Once you see file data flowing through frames on demand, a bigger picture snaps into focus. The OS does not let file pages evaporate after you use them — it keeps them in RAM in the page cache, so the next access to the same file data is served from memory with no disk I/O at all. Every read() and write(), not just mmap, goes through this cache. It is why the second time you grep a file it is instant, and why a freshly booted machine feels sluggish until the caches warm.

This is where the famous slogan comes from: unused RAM is wasted RAM. If you look at a healthy Linux box, almost none of its memory is "free" — the OS has filled the otherwise-idle RAM with cached file pages, because a cached page might save a disk read and an empty frame can never save anything. The page cache is not memory being hogged; it is memory being put to work, and the OS will hand any of it back the instant a process actually needs the frame. The page cache and process memory draw from the same physical pool, which is exactly why the memory picture blurs: the same demand-paging machinery, the same frames, the same eviction decisions serve both.

$ free -h
              total        used        free      shared  buff/cache   available
Mem:           15Gi       4.2Gi       0.4Gi       0.3Gi        11Gi        10Gi
#                                    ^ tiny         ^ page cache     ^ what a new
#                                    "free"         doing real work   process could get

For engineers this has a sharp consequence, and it is where this whole course is heading. A database keeps its own buffer pool — an in-process cache of disk pages — sitting on top of the OS page cache. The same file block can end up cached twice: once by Postgres in its shared buffers, once by the kernel in its page cache. That double-caching, and the tug-of-war over who should manage memory, is a recurring theme when you tune a database. We will pick it apart in the capstone; for now, just register that the OS-level virtual-memory machinery you have learned is the foundation the database's own memory management is built on top of.

Everything in this chapter comes down to one uncomfortable number, and it is worth working it out. Call the probability that a given memory access causes a page fault p — the page-fault rate. A normal access costs a memory-access time; a fault costs that plus the whole fault-service time, which is dominated by the disk read. The average, or effective access time, is a simple weighted sum.

EAT = (1 - p) * memory_access_time  +  p * page_fault_time

memory_access_time =        100 ns
page_fault_time    =        8 ms = 8,000,000 ns   (a disk read dominates)

p = 1/1000        EAT = 0.999*100 + 0.001*8,000,000   = ~8100 ns   (~81x slower)
p = 1/100,000     EAT = 100 + 8,000,000/100,000       = ~180 ns    (~1.8x slower)
p = 1/10,000,000  EAT = 100 + 8,000,000/10,000,000    = ~100.8 ns  (<1% slower)

Stare at those numbers. A fault every thousand accesses — which sounds rare — makes memory run roughly eighty times slower on average, because a single 8-millisecond disk read is worth eighty thousand 100-nanosecond memory accesses. To keep the slowdown under 10%, the fault rate has to fall below about one in 800,000. That is the tyranny of the disk gap: the fault penalty is so enormous that only an extremely low major-fault rate is tolerable. This is the quantitative reason locality matters so much — it is what drives p down to the tiny values that make virtual memory usable.

This calculation also tells you what failure looks like. Push memory demand past what RAM can hold and p climbs; EAT climbs with it; the system slows to a crawl while the disk light stays on solid. That is thrashing, the subject of a coming chapter. And when the OS cannot satisfy demand even by paging — when there is genuinely not enough memory plus swap — it stops being polite and invokes the OOM killer, terminating a process outright to reclaim its frames. Every backend engineer who has seen a container get "OOM-killed" under load has met the far end of this curve.

Effective access time (EAT)

The average cost of a memory access once you weight in the rare-but-huge cost of page faults.

Page-fault rate (p)

The fraction of memory accesses that fault; because the fault penalty is ~a thousandfold, p must be tiny to keep EAT near RAM speed.

Thrashing

The runaway state where working sets exceed RAM, p spikes, and the machine spends its time paging instead of computing (next-but-one chapter).

OOM killer

The OS's last resort when memory truly runs out: kill a process to reclaim frames rather than page forever.