Virtual Memory and Paging

Each process sees its own large, private, contiguous virtual address space.

Concept

Why Virtual Memory Each process sees its own large, private, contiguous virtual address space. The hardware MMU translates virtual addresses to physical addresses on every access, using page tables managed by the kernel. This gives:

Isolation — a process can't even name another process's memory.

Simplicity — every program is linked for the same address layout.

Overcommit and demand paging — memory is only backed by physical RAM when touched.

Sharing — the same physical page (a shared library, a copy-on-write page) can appear in several address spaces.

Protection — per-page read/write/execute permissions.

Pages and Page Tables Memory is divided into fixed-size pages (4 KB typically; huge pages 2 MB/1 GB) mapped to physical frames. A virtual address splits into virtual page number (VPN) + offset. A page table entry (PTE) holds the frame number and bits: present, writable, user, executable (NX), accessed, dirty.

A flat table for a 48-bit address space would be huge, so tables are multi-level (x86-64: 4 levels, 9 bits each + 12-bit offset; newer CPUs 5 levels). Only the parts in use exist.

The translation lookaside buffer is a small cache of recent translations inside the MMU (dozens to a few thousand entries). A TLB miss costs a page-table walk (several memory accesses, often cached). Huge pages cover more memory per entry, reducing TLB misses. Switching address spaces invalidates translations unless entries are tagged with an address-space ID (PCID/ASID).

A page fault occurs when the translation is missing or the access violates permissions. The kernel decides:

First touch of anonymous memory Minor fault: allocate a zeroed frame, map it Page of a file not in memory Major fault: read it from disk Write to a copy-on-write page Copy the page, map the copy writable Page swapped out Read it back from swap (major fault) Invalid address or permission Deliver SIGSEGV

Thrashing: when the working sets of running processes exceed physical memory, the system spends its time paging instead of computing.

mmap maps a file (or anonymous memory) into the address space; reads and writes become memory accesses, and the page cache is shared with ordinary read/write.

flowchart LR
    VA["Virtual address"] --> TLB{"TLB hit?"}
    TLB -->|"yes"| PA["Physical address"]
    TLB -->|"no"| WALK["Page-table walk: CR3 -> L4 -> L3 -> L2 -> L1"]
    WALK -->|"present"| FILL["Fill TLB"]
    FILL --> PA
    WALK -->|"not present"| PF["Page fault -> kernel"]
    PF --> PA

Why It Matters

Virtual memory explains why a program can malloc more than the machine's RAM, why the first touch of memory is slower, why fork is fast, how shared libraries share RAM, why segfaults happen, and why huge pages and TLB behaviour matter for databases and VMs.

Syntax

mmap, munmap, mprotect, madvise Map, unmap, change permissions, give hints getrusage → ru_minflt, ru_majflt Page fault counts /proc/<pid>/maps, /proc/<pid>/smaps Mappings and their resident sizes

/proc/<pid>/status → VmRSS, VmSize Resident vs virtual size

Example

19.1 Demand paging, page faults, copy-on-write and page protection

19.2 Address translation with a two-level page table and a TLB

#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/resource.h>
#include <sys/wait.h>

static long minor_faults(void) { struct rusage r; getrusage(RUSAGE_SELF, &r); return r.ru_minflt; }

static long rss_kb(void)
{
    FILE *f = fopen("/proc/self/status", "r");
    char line[128]; long kb = -1;
    while (fgets(line, sizeof line, f)) if (sscanf(line, "VmRSS: %ld kB", &kb) == 1) break;
    fclose(f);
    return kb;
}

int main(void)
{
    long page = sysconf(_SC_PAGESIZE);
    printf("page size: %ld bytes\n", page);

    size_t size = 1UL << 30;                                  /* reserve 1 GB of virtual memory */
    long rss0 = rss_kb(), f0 = minor_faults();
    char *p = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    long f1 = minor_faults(), rss1 = rss_kb();
    printf("before mmap:          RSS %6ld KB\n", rss0);
    printf("after mmap(1 GB):     RSS %6ld KB, page faults +%ld\n", rss1, f1 - f0);

    f0 = minor_faults();
    for (size_t i = 0; i < 64UL << 20; i += page) p[i] = 1;   /* touch 64 MB, one byte per page */
    long faults = minor_faults() - f0;
    p
…

"""Address translation with a two-level page table and a small TLB (32-bit addresses, 4 KB pages).
   virtual address = [ directory index : 10 | table index : 10 | offset : 12 ]"""

PAGE = 4096
page_directory = {                     # directory index -> page table
    0x000: {0x001: 0x2A3, 0x002: 0x2A4},
    0x001: {0x000: 0x7F0},
}
tlb = {}                               # virtual page number -> physical frame
TLB_SIZE = 2
stats = {"tlb_hit": 0, "tlb_miss": 0, "fault": 0}


def translate(va):
    vpn, offset = va >> 12, va & 0xFFF
    if vpn in tlb:
        stats["tlb_hit"] += 1
        frame, how = tlb[vpn], "TLB hit"
    else:
        stats["tlb_miss"] += 1
        d, t = vpn >> 10, vpn & 0x3FF
        table = page_directory.get(d)
        if table is None or t not in table:
            stats["fault"] += 1
            return f"{va:#010x}: dir {d:#05x} table {t:#05x} -> PAGE FAULT (not mapped)"
        frame = table[t]
        if len(tlb) == TLB_SIZE:
            tlb.pop(next(iter(tlb)))        # evict the oldest TLB entry
        tlb[vpn] = frame
        how = "TLB miss, 2 page-table reads"
    return f"{va:#010x}: vpn {vpn:#07x} offset {offset:#05x} -> frame {frame:#x} -> physic
…

Expected Result

Reserving 1 GB of virtual memory cost no page faults and almost no resident memory — it is only a promise.

Touching 64 MB caused exactly 16 384 minor page faults, one per 4 KB page, and the resident set grew by 64 MB.

Touching the same pages again caused no faults: they were mapped.

After fork, the child's first write to each of 4 096 inherited pages faulted: the kernel copied the page (copy-on-write); the parent's data stayed unchanged.

mprotect changed the first page to read-only (r--p).

The first access to a page misses in the TLB and walks two table levels; the second access to the same page (0x1ff0) hits. With only 2 TLB entries, 0x00001000 missed again because its entry had been evicted. An unmapped page produced a page fault.

page size: 4096 bytes
before mmap:          RSS   1616 KB
after mmap(1 GB):     RSS   1744 KB, page faults +0
after touching 64 MB: RSS  67344 KB, page faults +16384 (64 MB / 4 KB = 16384 pages)
touching them again:  page faults +0
child wrote 16 MB of inherited pages: page faults +4096 (copy-on-write)
parent still sees p[0] = 2
first page of the mapping is now r--p (writes would raise SIGSEGV)

0x00001234: vpn 0x00001 offset 0x234 -> frame 0x2a3 -> physical 0x002a3234 (TLB miss, 2 page-table reads)
0x00001ff0: vpn 0x00001 offset 0xff0 -> frame 0x2a3 -> physical 0x002a3ff0 (TLB hit)
0x00002008: vpn 0x00002 offset 0x008 -> frame 0x2a4 -> physical 0x002a4008 (TLB miss, 2 page-table reads)
0x00400010: vpn 0x00400 offset 0x010 -> frame 0x7f0 -> physical 0x007f0010 (TLB miss, 2 page-table reads)
0x00001000: vpn 0x00001 offset 0x000 -> frame 0x2a3 -> physical 0x002a3000 (TLB miss, 2 page-table reads)
0x00003000: dir 0x000 table 0x003 -> PAGE FAULT (not mapped)
{'tlb_hit': 1, 'tlb_miss': 5, 'fault': 1}

Common Mistakes

Believing malloc returning non-NULL means the memory is physically available (Linux overcommits; the OOM killer may strike later).

Confusing virtual size (VSZ) with resident size (RSS).

Assuming all page faults are errors — most are normal minor faults.

Using huge heaps with random access and ignoring TLB misses.

Best Practices

Touch or mlock memory in advance in real-time code to avoid page-fault latency.

Use mmap for large read-mostly files; use huge pages (transparent or explicit) for large, hot data sets.

Monitor major faults and swap activity — they indicate memory pressure.

Interview Relevance

Very high: "what is virtual memory?", "explain paging and page tables", "what is a TLB?", "what happens on a page fault?", "minor vs major fault?", "what is thrashing?", "how does copy-on-write work?", "why multi-level page tables?".

Practice Questions

With 4 KB pages and 32-bit addresses, how many entries does a single-level page table need, and how big is it with 4-byte entries?

Split the x86-64 virtual address 0x00007f1234567abc into its four 9-bit indexes and the offset.

Map a file with mmap, modify it, and verify the change with cat.

Allocate more memory than the machine has, touch it gradually and watch free -m.

Quick Quiz

Q1. (Multiple choice) What does the TLB cache? A) Data B) Instructions C) Virtual-to-physical translations D) Page files Answer: C.

Q2. (Predict the output) How many page faults does touching 64 MB of fresh anonymous memory with 4 KB pages cause?

Answer: 16 384 minor faults (verified).

Q3. (True/False) mmap of 1 GB immediately allocates 1 GB of physical RAM.

Answer: False. Frames are allocated on first touch (verified: RSS barely changed).

Q4. (Find the bug) A real-time control loop has occasional 50 µs spikes the first time it uses a new buffer.

Answer: First-touch page faults; pre-fault the buffers at start-up (write to every page or use mlockall(MCL_CURRENT | MCL_FUTURE)).

Coding Challenge

Given 4 KB pages, write a program that splits a 48-bit x86-64 virtual address into its four 9-bit page-table indexes (PML4, PDPT, PD, PT) and the 12-bit offset, and apply it to 0x00007f1234567abc.

#include <stdio.h>
#include <stdint.h>

int main(void)
{
    uint64_t va = 0x00007f1234567abcULL;
    unsigned offset = va & 0xFFF;
    unsigned pt = (va >> 12) & 0x1FF, pd = (va >> 21) & 0x1FF, pdpt = (va >> 30) & 0x1FF, pml4 = (va >> 39) & 0x1FF;
    printf("va 0x%016llx -> PML4 %u, PDPT %u, PD %u, PT %u, offset 0x%03x\n",
           (unsigned long long)va, pml4, pdpt, pd, pt, offset);
    return 0;
}