Virtual Memory#

Virtual memory extends the basic paging model into a complete system for managing address spaces larger than physical RAM. It encompasses the page table structures, swap management, memory overcommit policies, and hardware-aware optimizations like NUMA and huge pages.

Virtual vs Physical Addresses#

Process A sees:          Physical RAM:          Process B sees:
┌──────────┐             ┌──────────┐           ┌──────────┐
│ 0x0000   │────────┐    │ Frame 0  │     ┌─────│ 0x0000   │
│ 0x1000   │──┐     └───▶│ Frame 1  │     │     │ 0x1000   │
│ 0x2000   │  │          │ Frame 2  │◀────┘     │ 0x2000   │
└──────────┘  └─────────▶│ Frame 3  │           └──────────┘
                          │ Frame 4  │◀──── Process B page 1
                          └──────────┘

Page Table Structures#

A flat page table for a 48-bit address space with 4KB pages would require 2^36 entries × 8 bytes = 512 GB. Clearly impractical. Real systems use hierarchical or inverted page tables.

Multi-Level Page Tables#

Break the virtual address into multiple index fields, creating a tree of page tables:

x86-64 4-level page table (48-bit virtual address):

┌────────┬────────┬────────┬────────┬────────────┐
│ PML4   │ PDPT   │  PD    │  PT    │  Offset    │
│ (9 bit)│ (9 bit)│ (9 bit)│ (9 bit)│  (12 bit)  │
└────┬───┴────┬───┴────┬───┴────┬───┴────────────┘
     │        │        │        │
     ▼        ▼        ▼        ▼
  ┌─────┐  ┌─────┐  ┌─────┐  ┌─────┐
  │PML4 │─▶│PDPT │─▶│ PD  │─▶│ PT  │─▶ Frame + Offset
  │Table│  │Table│  │Table│  │Table│
  └─────┘  └─────┘  └─────┘  └─────┘
  (512     (512      (512     (512
  entries) entries)  entries)  entries)

Advantage: Only allocate page table pages for address ranges actually used. A process using 1 GB needs ~2 MB of page tables rather than 512 GB.

5-Level Page Tables (x86-64, Linux 4.14+)#

Extends to 57-bit virtual addresses (128 PB) for machines with more than 256 TB of physical RAM.

Inverted Page Table#

One global table with one entry per physical frame:

┌─────────────────────────────────┐
│ Frame 0 │ pid=3, page=0x1A     │
│ Frame 1 │ pid=7, page=0x05     │
│ Frame 2 │ pid=3, page=0x2F     │
│ ...     │ ...                   │
│ Frame N │ pid=1, page=0x00     │
└─────────────────────────────────┘

Used by: PowerPC, IA-64, some MIPS systems. x86 does NOT use inverted page tables.

Swap Space#

When physical memory is full, the OS writes infrequently used pages to a dedicated disk area called swap:

RAM (full)                    Swap (on disk)
┌──────────┐                  ┌──────────┐
│ Active   │                  │ Evicted  │
│ pages    │ ──evict──────▶  │ page A   │
│          │                  │ page B   │
│          │ ◀──swap in────  │ page C   │
└──────────┘                  └──────────┘

Swap Configuration#

Linux Swappiness#

# Range: 0-200 (default: 60)
# Lower = prefer evicting file cache, keep anonymous pages in RAM
# Higher = more willing to swap out anonymous pages
cat /proc/sys/vm/swappiness

Copy-on-Write (COW)#

When fork() creates a child process, it would be wasteful to copy all memory immediately. COW shares pages until one process writes:

After fork():
Parent page table ──┐
                    ├──▶ Shared frame (read-only)
Child page table  ──┘

After child writes:
Parent page table ────▶ Original frame
Child page table  ────▶ NEW frame (copy made on write)

Implementation:

1. fork() marks all pages read-only in both parent and child
2. On write attempt → page fault (protection violation)
3. Fault handler allocates new frame, copies content, updates PTE
4. Original process keeps original frame (now writable)

Impact: fork() is O(page table size), not O(memory size). A process with 1GB of mapped memory forks in microseconds.

Memory Overcommit#

Linux allows processes to allocate more virtual memory than physically available:

// This succeeds even if system has 4GB RAM:
void *p = malloc(8 * 1024 * 1024 * 1024L);  // 8 GB
// Pages aren't actually allocated until written

Overcommit Modes (/proc/sys/vm/overcommit_memory)#

Why Overcommit?#

• fork() + exec() pattern: child duplicates parent’s address space but immediately replaces it
• Sparse arrays: program allocates large array but uses small portion
• Memory-mapped files: mapped but rarely fully read

OOM Killer#

When overcommit leads to actual memory exhaustion, the Out-Of-Memory (OOM) killer selects and terminates a process:

Scoring Algorithm#

oom_score = (process_memory_usage / total_memory) × 1000
            + adjustments for:
              - child process count
              - CPU time (established processes scored lower)
              - nice value
              - oom_score_adj (-1000 to +1000)

# Protect a critical process from OOM killer:
echo -1000 > /proc/$(pidof my-critical-app)/oom_score_adj

# Make a process the preferred OOM victim:
echo 1000 > /proc/$(pidof my-expendable-worker)/oom_score_adj

Huge Pages#

Standard 4KB pages mean large page tables and many TLB entries. Huge pages reduce this overhead:

Linux Huge Page Options#

# Reserve 1000 huge pages (2MB each = 2GB total):
echo 1000 > /proc/sys/vm/nr_hugepages

# Application uses them:
mmap(NULL, size, PROT_READ|PROT_WRITE,
     MAP_PRIVATE|MAP_ANONYMOUS|MAP_HUGETLB, -1, 0);

When to Use Huge Pages#

NUMA (Non-Uniform Memory Access)#

Modern multi-socket systems have memory physically attached to specific CPUs:

┌──────────────────┐          ┌──────────────────┐
│     Socket 0     │          │     Socket 1     │
│  ┌────┐ ┌────┐  │          │  ┌────┐ ┌────┐  │
│  │CPU0│ │CPU1│  │          │  │CPU2│ │CPU3│  │
│  └────┘ └────┘  │          │  └────┘ └────┘  │
│       │          │◀──QPI──▶│          │       │
│  ┌────┴──────┐  │ (slow)   │  ┌──────┴────┐  │
│  │  Local    │  │          │  │   Local    │  │
│  │  Memory   │  │          │  │   Memory   │  │
│  │ (fast)    │  │          │  │  (fast)    │  │
│  └───────────┘  │          │  └────────────┘  │
└──────────────────┘          └──────────────────┘

NUMA-Aware Memory Allocation#

#include <numa.h>

// Allocate on specific node:
void *p = numa_alloc_onnode(size, node);

// Prefer local node:
numa_set_preferred(node);

// Bind process to node:
numa_run_on_node(node);

Linux NUMA Policies#

# Run process with NUMA policy:
numactl --membind=0 --cpunodebind=0 ./my_app

# View NUMA statistics:
numastat

Key Takeaways#

• Multi-level page tables make large virtual address spaces practical by only allocating table pages for used regions
• Swap extends memory beyond physical RAM but at disk speed — it’s a safety net, not a performance strategy
• Copy-on-write makes fork() nearly free and enables efficient process creation
• Memory overcommit is a pragmatic choice that works well for typical workloads but requires the OOM killer as a backstop
• Huge pages dramatically reduce TLB pressure for memory-intensive workloads (databases, VMs, HPC)
• NUMA topology means memory access time is non-uniform — placement matters for performance on multi-socket systems