Virtual Memory, Demand Paging & Page Replacement

Every process lives in its own virtual address space. On a 64-bit Linux system, this is nominally 2^48 bytes (128 TiB on x86-64, split roughly 50/50 between user and kernel). These addresses are purely logical — the CPU issues them, but before any memory access actually happens, the Memory Management Unit (MMU) translates them to physical addresses using a structure called the page table.

Memory is divided into fixed-size chunks called pages (typically 4 KiB on x86-64, though 2 MiB and 1 GiB "huge pages" also exist). The page table is a multi-level tree — on x86-64 it is four levels deep (PGD → PUD → PMD → PTE). Each entry at the leaf (the Page Table Entry, or PTE) holds a physical frame number plus permission bits: Present, Writable, User-accessible, Execute-Disable, Dirty, Accessed.

The hardware walks this tree on every memory access. To avoid doing this on every single instruction, the CPU caches recent translations in the Translation Lookaside Buffer (TLB), a small, extremely fast associative cache. A TLB hit costs ~1 cycle; a full page table walk costs 10–100+ cycles depending on cache state. This is why huge pages matter for performance: one TLB entry covers 512× more memory.

The key insight: the Present bit in the PTE is what makes demand paging possible. If Present=0, the hardware raises a page fault exception and hands control to the OS. The OS can then decide what to do: fetch the page from disk, allocate a zero page, kill the process — anything. This single bit is the hook on which all of virtual memory's magic hangs.

/* Read the CR3 register (page table base) on x86-64 — kernel context only */
#include <asm/processor.h>

unsigned long read_cr3(void)
{
    unsigned long cr3;
    asm volatile("mov %%cr3, %0" : "=r"(cr3));
    return cr3;  /* Physical address of PGD | PCID */
}

/* A PTE on x86-64 is a 64-bit integer. Key bits: */
#define _PAGE_PRESENT   (1UL << 0)   /* page is in RAM */
#define _PAGE_RW        (1UL << 1)   /* page is writable */
#define _PAGE_USER      (1UL << 2)   /* accessible from userspace */
#define _PAGE_ACCESSED  (1UL << 5)   /* hardware sets on read */
#define _PAGE_DIRTY     (1UL << 6)   /* hardware sets on write */
#define _PAGE_NX        (1UL << 63)  /* not executable (NX bit) */

Naive virtual memory might load an entire program into RAM before letting it run. Demand paging rejects this: a page is only brought into physical memory when the process actually touches it. Until then, its PTE has Present=0.

Consider execve. When the kernel loads a new executable, it does not read the binary into RAM. Instead it sets up a set of Virtual Memory Areas (VMAs) — struct vm_area_struct in Linux — that describe what should be at each address range: "at 0x400000–0x401000 you'll find the text segment from this ELF file at offset 0". The PTEs are left empty (Present=0). The moment the CPU tries to fetch the first instruction at the entry point, it raises a page fault. The kernel's fault handler sees "this VMA is backed by this file at this offset", reads 4 KiB from the ELF binary into a free physical frame, installs the PTE, and returns. The CPU retries the instruction — it now succeeds.

This is enormously efficient:

• Programs that have dead code paths never load those pages.
• Startup time is reduced because you don't wait for the full binary to be read.
• Multiple processes running the same binary share the same physical frames for read-only text/data pages.

The cost is the fault overhead on first access — typically a few microseconds for a minor fault (page in RAM, just needs a PTE installed) or hundreds of microseconds for a major fault (page must be read from disk).

/proc/pid/status shows VmRSS (physical pages resident) vs VmSize (total virtual size). It is completely normal for VmSize to dwarf VmRSS.

/* Demonstrate demand paging: allocate 1 GiB but touch only 4 KiB */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
    const size_t GB = 1UL << 30;
    /* malloc + mmap succeed immediately — no physical RAM allocated yet */
    char *buf = malloc(GB);
    if (!buf) { perror("malloc"); return 1; }

    printf("Allocated 1 GiB virtually. Check /proc/%d/status (VmRSS)\n",
           getpid());
    getchar();   /* pause: VmRSS will be tiny here */

    buf[0] = 'A';   /* page fault #1: 4 KiB loaded */
    buf[4096] = 'B'; /* page fault #2 */

    printf("Touched 8 KiB. VmRSS should now be ~8 KiB larger.\n");
    getchar();

    free(buf);
    return 0;
}

A page fault is a hardware exception (interrupt vector 14 on x86) raised when a memory access cannot be satisfied by the TLB and page table walk. The CPU saves registers, switches to kernel mode, and calls the kernel's page fault handler — do_page_fault on x86 Linux (ultimately handle_mm_fault).

The handler classifies the fault:

Minor fault (soft fault): The page is somewhere in RAM (perhaps in the page cache, or just needs a PTE installed), but no disk I/O is needed. Cost: microseconds. Examples: first access to an anonymous page (zeroed on demand), accessing a file-backed page that another process already loaded, copy-on-write.

Major fault (hard fault): The page must be read from disk — either from the filesystem (file-backed page) or from swap. Cost: hundreds of microseconds to milliseconds. This is the expensive case.

Invalid (segfault): The address is not within any VMA, or the access violates permissions (writing to a read-only page, executing a non-executable page, user code accessing kernel memory). The kernel sends SIGSEGV to the process.

You can count faults with getrusage() (ru_minflt, ru_majflt) or /proc/pid/stat fields 10 and 12, or with perf stat -e page-faults,major-faults ./program.

The fault handler path in Linux:

1. do_page_fault (arch-specific entry)
2. handle_mm_fault (generic mm/)
3. handle_pte_fault — decides minor/major/anon/file
4. For file-backed: filemap_fault → page_cache_read → submit I/O
5. Install PTE, flush TLB entry, return to userspace
6. CPU retries the faulting instruction.

/* Measure major vs minor faults with getrusage */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/resource.h>

static void print_faults(const char *label)
{
    struct rusage r;
    getrusage(RUSAGE_SELF, &r);
    printf("%s: minor=%ld major=%ld\n",
           label, r.ru_minflt, r.ru_majflt);
}

int main(void)
{
    print_faults("start");

    /* mmap 64 MiB anonymous memory */
    char *p = calloc(1, 64 * 1024 * 1024);  /* triggers minor faults */
    print_faults("after calloc 64MiB");

    /* Touch every page sequentially */
    for (size_t i = 0; i < 64 * 1024 * 1024; i += 4096)
        p[i] = 1;
    print_faults("after touching all pages");

    free(p);
    return 0;
}

Peter Denning's working set model (1968) is one of the most important ideas in operating systems theory. It observes that real programs do not access memory uniformly — they exhibit temporal locality (recently accessed data is likely to be accessed again) and spatial locality (nearby memory is likely to be accessed soon). At any moment in time, a process actively uses only a small subset of its pages: this is its working set W(t, Δ) — the set of distinct pages referenced in the time window [t−Δ, t].

The working set model gives us a concrete criterion for multiprogramming:

• If a process's working set fits in available RAM, it runs efficiently.
• If the OS tries to give a process fewer frames than its working set size, the process will page-fault constantly — every page it needs will require evicting a page it will need again soon.

The working set size is not static. During a phase transition — for example, when a program switches from parsing input to running a graph algorithm — the working set changes. There's a brief spike in page faults as the new working set is loaded. This is normal and unavoidable.

You can observe working set behavior with Linux's smem tool or by reading /proc/pid/smaps_rollup which gives Pss (proportional set size). For a deeper view, perf record -e page-faults + perf report shows exactly which code paths are causing faults.

# Observe a process's resident set over time (Linux)
# Run your program, note its PID, then:
watch -n 0.5 'grep -E "VmRSS|VmSize|VmSwap" /proc/$(pgrep myprogram)/status'

# Or use smem for a system-wide view of working sets:
# sudo apt install smem
smem -t -k  # shows USS/PSS/RSS per process

# Count page faults for a specific command:
perf stat -e page-faults,major-faults ls /usr/bin 2>&1 | grep faults

Thrashing is the catastrophic failure mode of virtual memory. It happens when the OS has too many processes competing for too few physical frames, and the combined working sets exceed available RAM. The system spends more time handling page faults and doing I/O than actually running user processes.

The vicious cycle:

1. Process A needs page X, which was evicted to make room for process B.
2. Fetching X evicts a page that process B needs.
3. Process B page-faults, evicting a page that process A needs.
4. Repeat forever.

CPU utilization collapses: the CPU is always waiting for I/O, so the scheduler thinks "CPU is idle, I should add more processes" — making things worse. This is the classic example of a positive feedback loop in OS design.

Denning's working set model is the theoretical solution: only allow a process to run if its working set fits in the available RAM. Linux's actual approach is more pragmatic:

• kswapd: a kernel thread that runs in the background to keep a pool of free frames available. It scans the LRU lists and reclaims cold pages before memory runs out.
• OOM killer: when all else fails, the kernel calculates an "OOM score" for each process and kills the highest scorer to free memory.
• Memory overcommit (discussed below): allows the system to give more virtual memory than physical RAM, banking on the fact that not all of it will be used at once.

You can see kswapd activity with vmstat 1 — watch the si (swap in) and so (swap out) columns. If both are consistently non-zero, you're in or near thrashing territory.

# Observe thrashing with vmstat (1-second intervals)
# Columns: r=runnable, b=blocked, si=swap-in KB/s, so=swap-out KB/s
vmstat 1 10

# Check if OOM killer has fired:
dmesg | grep -i 'oom\|killed process'

# See current OOM scores for all processes:
for pid in /proc/[0-9]*/; do
    score=$(cat "${pid}oom_score" 2>/dev/null)
    comm=$(cat "${pid}comm" 2>/dev/null)
    [ -n "$score" ] && printf "%5d %s\n" "$score" "$comm"
done | sort -rn | head -20

When RAM is full and a new page must be brought in, the OS must choose a victim page to evict. This is the page replacement problem. The goal: evict the page least likely to be needed soon, minimizing future page faults.

Optimal (OPT / Bélády's Algorithm): Evict the page that will not be used for the longest time in the future. This is provably optimal but requires knowing the future — it's used only as a benchmark.

FIFO (First In, First Out): Evict the page that has been in memory the longest. Simple to implement (just a queue), but suffers from Bélády's anomaly: adding more frames can increase page faults with FIFO. Unintuitive and dangerous in practice.

LRU (Least Recently Used): Evict the page that was used least recently. Based on the temporal locality principle — if a page hasn't been used recently, it's less likely to be needed soon. LRU is optimal among algorithms that use only past access history. However, true LRU requires tracking the exact time of last access for every page, which is expensive in hardware (a timestamp per page, sorted list updates on every access).

Clock (Second-Chance / CLOCK): The practical approximation of LRU used in most real OSes including Linux. Pages are arranged in a circular list. Each page has a reference bit (the hardware Accessed bit in the PTE). The "clock hand" sweeps around:

• If the hand points to a page with reference bit = 1: clear the bit, advance (give it a second chance).
• If the hand points to a page with reference bit = 0: evict this page.

The intuition: on the first pass, every recently-used page gets its bit cleared but survives. A page that was genuinely unused long enough gets evicted on the second pass.

Linux uses a two-list (active/inactive LRU) variant: pages start on the active list; when their reference bits are cleared by kswapd, they migrate to the inactive list; pages on the inactive list are reclaim candidates.

/* Simulate FIFO and Clock page replacement — educational */
#include <stdio.h>
#include <string.h>

#define FRAMES 3
#define N 12

/* Reference string from Silberschatz textbook */
const int refs[N] = {7,0,1,2,0,3,0,4,2,3,0,3};

int fifo_replace(void)
{
    int frames[FRAMES], head = 0, faults = 0;
    memset(frames, -1, sizeof(frames));
    for (int i = 0; i < N; i++) {
        int hit = 0;
        for (int j = 0; j < FRAMES; j++)
            if (frames[j] == refs[i]) { hit = 1; break; }
        if (!hit) {
            frames[head] = refs[i];
            head = (head + 1) % FRAMES;
            faults++;
        }
    }
    return faults;
}

int clock_replace(void)
{
    int frames[FRAMES], ref_bit[FRAMES];
    int hand = 0, faults = 0;
    memset(frames, -1, sizeof(frames));
    memset(ref_bit, 0, sizeof(ref_bit));

    for (int i = 0; i < N; i++) {
        int hit = 0;
        for (int j = 0; j < FRAMES; j++) {
            if (frames[j] == refs[i]) {
                ref_bit[j] = 1;  /* set reference bit on hit */
                hit = 1; break;
            }
        }
        if (!hit) {
            /* Sweep until we find ref_bit == 0 */
            while (ref_bit[hand]) {
                ref_bit[hand] = 0;
                hand = (hand + 1) % FRAMES;
            }
            frames[hand] = refs[i];
            ref_bit[hand] = 1;
            hand = (hand + 1) % FRAMES;
            faults++;
        }
    }
    return faults;
}

int main(void)
{
    printf("FIFO faults: %d\n", fifo_replace());  /* 9 */
    printf("Clock faults: %d\n", clock_replace()); /* 8 */
    return 0;
}

When the OS decides to evict a dirty anonymous page (one that has been written to and has no file backing — heap, stack, mmap(MAP_ANONYMOUS)), it needs somewhere to put it. It cannot simply discard it because the data would be lost. The answer is swap space: a dedicated disk partition or file that acts as overflow storage for physical RAM.

The swap lifecycle:

1. kswapd (or direct reclaim under memory pressure) selects a victim page.
2. If the page is clean and file-backed (e.g., a read-only code page): simply discard it. It can be re-read from the original file on next access.
3. If the page is dirty anonymous: write it to swap, record the swap slot location in the PTE (Present=0, swap entry encoded in remaining PTE bits), free the physical frame.
4. When the page is accessed again: page fault → read from swap → install fresh PTE.

Swap is expensive because disk (even NVMe) is orders of magnitude slower than RAM. Linux tries hard to avoid it by preferring clean page cache reclaim, but swap is essential for correctness under heavy load.

zswap is a Linux kernel feature that compresses swap pages in RAM before they reach disk, trading CPU time for reduced I/O. zram goes further: creates a RAM-based block device with compression, so "swap" never hits disk at all — useful on memory-constrained systems like phones and embedded devices.

Useful commands:

• swapon --show: list swap devices and usage
• cat /proc/swaps: same from procfs
• vmstat -s | grep swap: swap statistics
• /proc/pid/smaps: per-VMA breakdown including Swap: field

# See swap usage and configuration
swapon --show

# Create a 2 GiB swapfile (if you don't have a swap partition)
sudo fallocate -l 2G /swapfile
sudo chmod 600 /swapfile
sudo mkswap /swapfile
sudo swapon /swapfile

# Check how much swap a specific process is using
grep Swap /proc/$(pgrep firefox | head -1)/smaps | awk '{s+=$2} END{print s" kB"}'

# Linux swappiness: 0=avoid swap, 100=swap aggressively (default 60)
sysctl vm.swappiness
sudo sysctl -w vm.swappiness=10  # prefer keeping RAM, evict page cache first

Copy-on-write is one of the most beautiful optimizations in operating systems. The idea: instead of copying data immediately, share it and only make a private copy the moment someone tries to modify it.

The canonical example is fork(). When a process calls fork(), creating a child process, the naive approach would copy all of the parent's memory — potentially gigabytes. With COW:

1. The kernel creates a new page table for the child, but points its PTEs to the same physical frames as the parent.
2. Both parent and child PTEs are marked read-only, even for pages that were writable.
3. Both processes continue running, sharing all pages. If they only read, no copying ever occurs.
4. The moment either process writes to a shared page, a write-protection fault fires. The fault handler sees this is a COW page (not a genuine permission violation), allocates a new physical frame, copies the page content, installs the new PTE as writable for the faulting process, and decrements the reference count on the shared frame.

This makes fork() + exec() (the Unix process creation model) extremely fast. The child process immediately calls exec(), which replaces the address space — so the parent's pages were never actually needed and never get copied.

COW also underlies:

• Linux's mmap(MAP_PRIVATE) for file-backed regions: modifications are private COW copies.
• Container/VM snapshot systems: the disk image is shared read-only, modifications are COW.
• btrfs and zfs copy-on-write filesystems (same concept applied to disk blocks).

You can watch COW in action: after fork(), check both processes' VmRSS — it will be tiny initially, then grow as each writes to its heap.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/wait.h>

/* Demonstrate COW: parent and child share pages until a write */
static long get_rss_kb(void)
{
    FILE *f = fopen("/proc/self/status", "r");
    char line[128]; long rss = 0;
    while (fgets(line, sizeof(line), f))
        if (sscanf(line, "VmRSS: %ld", &rss) == 1) break;
    fclose(f);
    return rss;
}

int main(void)
{
    const size_t SZ = 64 * 1024 * 1024;  /* 64 MiB */
    char *buf = malloc(SZ);
    memset(buf, 'A', SZ);  /* force pages into RAM */

    printf("parent RSS before fork: %ld KB\n", get_rss_kb());

    pid_t pid = fork();
    if (pid == 0) {
        /* Child: RSS is still small (COW, no copies yet) */
        printf("child  RSS after fork (no writes): %ld KB\n", get_rss_kb());
        /* Now write: triggers COW faults, RSS grows */
        memset(buf, 'B', SZ);
        printf("child  RSS after writing 64 MiB: %ld KB\n", get_rss_kb());
        free(buf);
        _exit(0);
    }
    wait(NULL);
    printf("parent RSS after child exited: %ld KB\n", get_rss_kb());
    free(buf);
    return 0;
}

Here is a surprising fact: on Linux with default settings, you can malloc far more memory than your system has RAM + swap combined, and malloc will happily return a non-NULL pointer. This is memory overcommit.

The reasoning: most programs allocate far more memory than they ever actually use. A web server might malloc a 1 GiB pool as a precaution but only ever touch 50 MiB. If the kernel allocated physical RAM for every byte of virtual memory ever requested, RAM would run out almost immediately. Instead, the kernel says: "I'll promise you this memory. I'll only back it with real RAM when you actually touch it."

This works almost all the time, for the same reason that airlines overbook flights: not everyone shows up. But occasionally, everyone does show up — processes touch more memory than the system can provide. When physical RAM plus swap are exhausted and a page fault cannot be satisfied, the kernel invokes the OOM killer, which picks a process to terminate based on a score (combination of memory usage, runtime, privilege level, /proc/pid/oom_score_adj).

Linux has three overcommit modes (/proc/sys/vm/overcommit_memory):

• 0 (default): Heuristic overcommit. Allow obviously unreasonable requests, reject obviously bad ones.
• 1: Always overcommit. Never fail malloc. Maximally aggressive. Used on some HPC systems.
• 2: Never overcommit. Fail malloc if total committed memory would exceed swap + a fraction of RAM. Conservative; malloc can return NULL even with "free" RAM.

The right choice depends on workload. For a database or real-time system, mode 2 provides predictability. For a typical workstation or server, mode 0 or 1 maximizes utilization.

/* Demonstrate overcommit: allocate more than RAM+swap */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
    /* Try to allocate 1 TiB — will succeed on systems with overcommit */
    const size_t TB = 1ULL << 40;
    char *p = malloc(TB);
    if (!p) {
        printf("malloc failed — overcommit disabled (mode 2?)\n");
        return 1;
    }
    printf("malloc(1 TiB) succeeded! Virtual address: %p\n", (void*)p);
    printf("No RAM used yet — check /proc/%d/status VmRSS\n", getpid());

    /* Touch one page: THIS uses 4 KiB of real RAM */
    p[0] = 1;
    printf("Touched one page. VmRSS grew by 4 KiB.\n");

    /* If we tried to touch all 1 TiB, the OOM killer would fire */
    free(p);
    return 0;
}

/* Check and set overcommit policy:
   cat /proc/sys/vm/overcommit_memory
   sudo sysctl -w vm.overcommit_memory=2
*/

The page cache is the OS's unified buffer for file data in RAM. When any process reads a file — via read(), mmap(), or by executing a binary — the kernel stores the data in the page cache. If another process reads the same file, it gets the same physical frames. This is why shared libraries work: libc.so is loaded into RAM once and mapped (read-only) into hundreds of processes simultaneously.

mmap(fd, ...) is the low-level interface to this. It creates a VMA backed by a file, so pages are faulted in on demand from the file (via the page cache). This is how Linux implements:

• Executable loading: the ELF binary is mmap'd, text segment is MAP_PRIVATE (so writes COW-copy, though writes to text are disallowed by NX).
• Shared memory (MAP_SHARED): writes go back to the file/page cache, visible to all mappings.
• Private mappings (MAP_PRIVATE): reads come from the file, writes are COW-private — no changes reach the file.
• Database buffer pools: many databases use mmap to let the OS manage caching; others (PostgreSQL) prefer to manage their own buffer pool.

Unlike anonymous pages, file-backed clean pages can be evicted for free — the data is already on disk. This is why Linux preferentially keeps page cache over anonymous pages, and why free -h shows a large "buff/cache" column that isn't "wasted" — it's opportunistic caching that yields to application demand immediately.

The mincore(2) syscall tells you which pages of an mmap'd region are currently resident in RAM — useful for debugging latency spikes caused by page faults.

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

int main(int argc, char **argv)
{
    if (argc < 2) { fprintf(stderr, "usage: %s <file>\n", argv[0]); return 1; }

    int fd = open(argv[1], O_RDONLY);
    struct stat st;
    fstat(fd, &st);
    size_t len = st.st_size;

    /* Map the file read-only — no data is read yet */
    char *data = mmap(NULL, len, PROT_READ, MAP_PRIVATE, fd, 0);
    close(fd);

    /* Query residency: which 4 KiB pages are already in RAM? */
    size_t npages = (len + 4095) / 4096;
    unsigned char *vec = malloc(npages);
    mincore(data, len, vec);  /* vec[i] & 1 == 1 if page i is resident */

    size_t resident = 0;
    for (size_t i = 0; i < npages; i++)
        if (vec[i] & 1) resident++;

    printf("%zu / %zu pages resident (%.1f%%)\n",
           resident, npages, 100.0 * resident / npages);

    /* Touch every page sequentially (warm the page cache) */
    volatile char c = 0;
    for (size_t i = 0; i < len; i += 4096) c = data[i];

    munmap(data, len);
    free(vec);
    return 0;
}