Virtual Memory

Purpose of Virtual Memory

Virtual memory provides each process with its own private, contiguous address space, independent of physical DRAM layout. It enables:

• Protection — processes cannot read/write each other's memory
• Isolation — a crash in one process doesn't corrupt others
• Abstraction — programs can be larger than physical RAM (demand paging)
• Sharing — pages can be mapped read-only into multiple processes (shared libraries)
• Simplified linking — programs can assume fixed load addresses

Address Translation

Every memory access uses a virtual address (VA). The MMU translates it to a physical address (PA):

Virtual Address          Page Table           Physical Address
[ VPN | page offset ] ──────────────► [ PPN | page offset ]
                          (MMU)

• VPN = Virtual Page Number
• PPN (or PFN) = Physical Page Number / Frame Number
• Page offset = unchanged; same in VA and PA
• Page size = 2^(offset bits). Common: 4 KB (12-bit offset), 2 MB, 1 GB (huge pages)

Address Space Example (x86-64, 4 KB pages)

64-bit VA: [ 16 sign-ext | 9 PML4 | 9 PDP | 9 PD | 9 PT | 12 offset ]

• 4-level page table on x86-64 (PML4 → PDPT → PD → PT → page) → 48-bit VA
• Bits 63:48 must equal bit 47 (canonical addresses — sign-extended); non-canonical access faults (#GP)
• 5-level paging (LA57): adds a PML5 level → 57-bit VA (128 PiB); shipping on Ice Lake+ servers, enabled per boot
• Each table has 2⁹ = 512 entries × 8 bytes = 4 KB per table
• ARM uses a similar structure (PGD → PUD → PMD → PTE)

Page Table Entry (PTE) Fields (x86-64)

Page Fault Types

TLB (Translation Lookaside Buffer)

The page table walk is expensive (3–5 memory accesses for a 4-level table). The TLB is a small cache of recent VA→PA translations — L1 TLBs are fully or highly associative; larger L2 TLBs are set-associative (4–8-way) on modern cores.

TLB hit: ~1 cycle extra latency (parallel with cache lookup) TLB miss: ~20–50+ cycles (hardware page-table walk, PTW)

Typical TLB Parameters

TLB Shootdown

When the OS modifies a PTE (e.g., unmaps a page), it must invalidate any TLB entry holding that VA across all cores using that address space:

1. OS modifies PTE
2. OS sends IPI (Inter-Processor Interrupt) to other cores
3. Each core executes INVLPG <va> (x86) or TLBI (ARM)
4. Originating core waits for acknowledgements
5. Flushing continues

TLB shootdowns are expensive — minimize mappings changes (mmap/munmap) in hot paths.

Page Replacement Policies

When a page fault occurs and physical memory is full, the OS must evict a page:

Linux does not use classic clock — it approximates LRU with two lists (active/inactive) per memory cgroup, promoting/demoting pages between them (multi-gen LRU since 6.1).

NRU Classes

Huge Pages

Linux: Transparent Huge Pages (THP) automatically promotes 4 KB pages to 2 MB when contiguous. hugetlbfs for explicit huge-page allocation.

Memory Protection

Segmentation (legacy)

x86 originally used segments (base + limit per logical address region) before paging. Modern x86-64 uses flat segmentation (all segments base=0, limit=2⁶⁴) — paging is the real protection mechanism. Segments still exist for fs and gs as thread-local storage pointers.

Copy-on-Write (CoW) in fork()

Parent calls fork():
  - Child gets a copy of parent's page table
  - All pages marked read-only in both parent and child
  - Physical pages are shared

First write by either process:
  - Protection fault
  - OS allocates new page, copies content
  - Updates faulting process's PTE to new page, marks R/W
  - Other process still references original (now also R/W)

CoW makes fork() + exec() extremely cheap — only modified pages are actually copied.