Understanding Virtual Memory and Paging

Virtual memory is one of the most important abstractions in operating systems. It gives each process the illusion of having a large, private, contiguous address space while the physical RAM is shared and fragmented underneath. This abstraction simplifies programming, enforces protection between processes, and enables efficient use of memory through paging.

How Paging Works

Physical memory is divided into fixed-size frames (typically 4 KiB). Each process’s virtual address space is divided into pages of the same size. A page table maps virtual page numbers (VPNs) to physical frame numbers (PFNs). When a process accesses memory, the CPU’s Memory Management Unit (MMU) consults the page table to translate the virtual address to a physical one.

// Virtual address structure (32-bit, 4 KiB pages)
// |   VPN (20 bits)  | Offset (12 bits) |
//    0xfffff             0xfff

// Page table entry structure
struct page_table_entry {
    unsigned int pfn      : 20;  // physical frame number
    unsigned int present  : 1;   // page in RAM?
    unsigned int writable : 1;   // can write?
    unsigned int user     : 1;   // user-mode accessible?
    unsigned int accessed : 1;   // recently accessed (for LRU)
    unsigned int dirty    : 1;   // modified since load
    unsigned int reserved : 8;   // unused
};

// Address translation
void *translate(void *virt_addr) {
    uintptr_t addr = (uintptr_t)virt_addr;
    unsigned int vpn = addr >> 12;           // top 20 bits
    unsigned int offset = addr & 0xFFF;      // bottom 12 bits
    struct page_table_entry pte = page_table[vpn];

    if (!pte.present) {
        handle_page_fault(vpn);
        pte = page_table[vpn];  // retry after fault
    }
    pte.accessed = 1;
    return (void *)((pte.pfn << 12) | offset);
}

Multi-Level Page Tables

A flat page table for a 64-bit address space would be enormous (2⁵² entries on x86-64). Modern systems use hierarchical page tables — a tree structure where only the levels needed for mapped regions are allocated. On x86-64 with 4 KiB pages, a 4-level page table reduces the in-memory footprint from petabytes to just a few kilobytes per process.

// x86-64 4-level page table walk (pseudo-assembly)
// CR3 holds the top-level (PML4) table address
void *walk_page_table(void *virt_addr) {
    uint64_t addr = (uint64_t)virt_addr;
    uint64_t *pml4 = read_cr3();
    int idx;

    // Level 4: PML4 (bits 47:39)
    idx = (addr >> 39) & 0x1FF;
    uint64_t *pdp = (uint64_t *)(pml4[idx] & PAGE_MASK);

    // Level 3: Page Directory Pointer (bits 38:30)
    idx = (addr >> 30) & 0x1FF;
    uint64_t *pd = (uint64_t *)(pdp[idx] & PAGE_MASK);

    // Level 2: Page Directory (bits 29:21)
    idx = (addr >> 21) & 0x1FF;
    uint64_t *pt = (uint64_t *)(pd[idx] & PAGE_MASK);

    // Level 1: Page Table (bits 20:12)
    idx = (addr >> 12) & 0x1FF;
    uint64_t pte = pt[idx];

    if (!(pte & PRESENT_BIT))
        handle_page_fault(virt_addr);

    return (void *)((pte & PAGE_MASK) + (addr & 0xFFF));
}

The Translation Lookaside Buffer (TLB)

Walking a 4-level page table on every memory access would be prohibitively slow — each walk requires up to 4 memory reads. The TLB is a hardware cache that stores recently used virtual-to-physical mappings. A TLB hit completes translation in a single cycle; a miss triggers a page walk that can take dozens of cycles. Modern CPUs have separate TLBs for instructions (i-TLB) and data (d-TLB), plus multi-level TLBs (L1 small/fast, L2 larger/slower).

// Simulated TLB with LRU eviction
class TLB:
    def __init__(self, size=64):
        self.size = size
        self.entries = []  # list of (vpn, pfn, last_access)

    def lookup(self, vpn, cycle):
        for i, (v, pfn, _) in enumerate(self.entries):
            if v == vpn:
                self.entries[i] = (vpn, pfn, cycle)
                return pfn
        return None  # TLB miss

    def insert(self, vpn, pfn, cycle):
        if len(self.entries) >= self.size:
            # Evict least recently used
            lru = min(range(len(self.entries)), key=lambda i: self.entries[i][2])
            self.entries.pop(lru)
        self.entries.append((vpn, pfn, cycle))

    def flush(self):
        self.entries.clear()  # called on context switch

Demand Paging and Page Faults

Pages are loaded lazily — only when first accessed. When a process references a page that is not in RAM, the CPU raises a page fault. The kernel's fault handler locates the page (from the swap file, executable file, or zero-fill), allocates a physical frame, updates the page table, and resumes the process. This mechanism also enables:

• Copy-on-write (CoW): After fork(), parent and child share the same physical pages marked read-only. When either writes, the fault handler copies the page and gives each process its own writable copy.
• Memory-mapped files: mmap() maps file content into a process's address space. Page faults bring in file data lazily.
• Swapping: When physical memory is full, the page replacement algorithm (Linux uses a variant of LRU with active/inactive lists) selects victim pages to evict to swap space.

// Page fault handler (simplified Linux-like)
void handle_page_fault(struct task_struct *task, void *addr) {
    struct vm_area_struct *vma = find_vma(task->mm, addr);

    if (!vma) {
        // Address not mapped — SIGSEGV
        force_sig(SIGSEGV, task);
        return;
    }

    unsigned long vpn = (unsigned long)addr >> PAGE_SHIFT;

    if (vma->flags & VM_IO) {
        // Memory-mapped I/O
        map_io_page(vma, vpn);
    } else if (vma->flags & VM_SHARED) {
        // Shared mapping — load from file
        filemap_fault(vma, vpn);
    } else if (vma->flags & VM_ANON) {
        // Anonymous page — zero-fill or CoW
        do_anonymous_page(task, vma, vpn);
    }

    // Update page table and return to process
    flush_tlb_entry(vpn);
}

Performance Considerations

TLB reach — the amount of memory accessible without a TLB miss — is critical for performance. With 64 TLB entries and 4 KiB pages, only 256 KiB is covered. Huge pages (2 MiB or 1 GiB on x86-64) dramatically increase TLB reach. Databases, VMs, and scientific workloads explicitly request huge pages to reduce TLB miss rates. Modern CPUs also support PCID (Process Context Identifiers) to avoid flushing the TLB on every context switch, and simultaneous multi-threading (SMT) shares the TLB between hardware threads.

# Check TLB reach and huge page usage on Linux
$ grep . /sys/kernel/mm/hugepages/hugepages-*/nr_hugepages
/sys/kernel/mm/hugepages/hugepages-2048kB/nr_hugepages:1024
/sys/kernel/mm/hugepages/hugepages-1048576kB/nr_hugepages:0

# Enable transparent huge pages
$ echo always > /sys/kernel/mm/transparent_hugepage/enabled

# Measure TLB miss rate with perf
$ perf stat -e dTLB-load-misses,dTLB-loads ./myapp

Summary

Virtual memory and paging are the foundation of process isolation, efficient memory utilization, and the programmer-friendly flat address space model. Understanding page tables, TLB behavior, and page fault handling helps you optimize database engines, runtime systems, and any memory-intensive application.