Virtual Memory: Concept and Motivation

A virtual address is the address a running program computes and uses — the address a load or store instruction issues, or the value of a pointer. A physical address is the address that actually goes out on the DRAM's address pins, identifying a real byte of installed memory. Address translation is the mapping from virtual to physical addresses, performed by hardware and managed by the operating system, so that the same virtual address in two different processes can map to two completely different physical locations, and so that not every virtual address needs to map to a physical location at all times. The address space is divided into fixed-size chunks called pages (the physical-memory-side chunks are sometimes called page frames). A typical page size is 4 KiB, though modern systems also support "huge pages" of 2 MiB or 1 GiB to reduce translation overhead for large-memory workloads. Splitting memory into pages rather than tracking arbitrary byte ranges is what makes the mapping tractable: instead of storing a translation for every byte, the system stores one translation per page and reuses it for every byte inside that page. Because DRAM is far smaller than the total virtual memory demanded by all processes combined, and because disk (or flash) is far larger but far slower, the operating system keeps only the currently useful pages resident in DRAM and leaves the rest on the backing store. This is demand paging: a page is fetched from disk only when it is actually referenced, not in advance. When a program touches a virtual address whose page is not currently in DRAM, the hardware signals a page fault, trapping into the operating system, which locates the page on disk (or allocates a fresh zeroed page, for stack/heap growth), loads it into a free page frame, updates the mapping, and resumes the faulting instruction. The program is unaware this happened except for the time it took.

The conceptual pipeline of virtual memory has four ingredients that mirror ordinary caching almost exactly, with one crucial difference in policy execution: 1. Address space partitioning — both virtual and physical memory are divided into equal-size pages/frames. 2. A mapping structure — per process, a table (foreshadowing Page Tables and Address Translation) records, for every virtual page, either the physical frame it currently occupies, or a marker that it is not present (paged out to disk, or never yet allocated). 3. A hardware fast path — on every memory reference, hardware consults the mapping (accelerated by a The Translation Lookaside Buffer, foreshadowed but not detailed here) to translate virtual page number to physical frame number, then appends the unchanged page offset. 4. A software slow path (the page fault handler) — invoked when the mapping says "not present"; it is pure operating-system logic, since a disk access is far too slow to handle in hardware. The key architectural move is recognizing that a memory reference decomposes cleanly into a page number and a page offset: ``` virtual address = [ virtual page number (VPN) | page offset ] physical address = [ physical frame number (PFN) | page offset ] ``` The offset (the low-order bits, sized so that 2^offset_bits = page size) is copied unchanged. Only the page number needs translating, and translating whole pages at once is what makes the mapping table small enough to be practical — one entry per page, not per byte. Here is the demand-paging algorithm as the hardware/OS pair implements it. The hardware attempt is fast and always runs first; the OS handler only runs on a fault. ``` // Hardware fast path — attempted on every load/store function TRANSLATE(virtual_address): vpn = HIGH_BITS(virtual_address) // virtual page number offset = LOW_BITS(virtual_address) // page offset, unchanged entry = PAGE_TABLE_LOOKUP(current_process, vpn) if entry.present: physical_address = (entry.frame_number, offset) return physical_address // fast: nanoseconds else: raise PAGE_FAULT(vpn) // trap to OS // Software slow path — the OS page-fault handler function HANDLE_PAGE_FAULT(vpn): if NOT valid_reference(vpn): terminate_process("segmentation fault") // illegal address return if free_frame_exists(): frame = allocate_free_frame() else: victim_frame = SELECT_VICTIM(current_frames) // replacement policy if victim_frame.dirty: WRITE_BACK(victim_frame, disk) // flush modified page INVALIDATE_MAPPING(victim_frame.owner_vpn) frame = victim_frame disk_location = find_backing_store(vpn) READ_FROM_DISK(disk_location, into = frame) // slow: milliseconds UPDATE_PAGE_TABLE(current_process, vpn, frame, present = true) return // hardware re-executes the faulting instruction ``` Two details matter for correctness. First, on a fault the instruction is restarted, not resumed mid-execution — this requires the architecture to guarantee that page faults are restartable, meaning partial side effects of a faulted instruction can be undone or the instruction can be safely re-issued. Second, the victim selection (`SELECT_VICTIM`) is a replacement policy exactly analogous to cache replacement, but because a wrong choice costs a disk access (roughly 10^5–10^6 times an L1 hit), operating systems invest in far more sophisticated approximations of optimal replacement (e.g., variants of LRU such as the clock algorithm) than hardware caches typically can afford.

Space. The per-process mapping structure needs one entry per virtual page, not per byte. If the virtual address space is $V$ bytes and the page size is $P$ bytes, a direct (single-level) table needs $V/P$ entries. For a 64-bit address space with 4 KiB pages this is astronomically large in the naive form, which is precisely why real systems use multi-level or hashed structures — the subject of Page Tables and Address Translation. The point to internalize here is only the ratio: page-granularity mapping shrinks the bookkeeping by a factor of $P$ compared to byte-granularity mapping, at the cost of internal fragmentation (a process using 1 byte of a page still consumes the whole page).

Time — the fast path. Translation of an already-mapped address is, in principle, a single table lookup: $O(1)$ additional work per memory access beyond the lookup's own structure (which may itself be $O(\log n)$ or $O(1)$ depending on the table organization introduced later). Because this lookup happens on every memory reference, hardware caches recent translations in a TLB, making the common case a single cheap hardware step — this is the seed of The Translation Lookaside Buffer.

Time — the slow path (page fault). A page fault costs a full disk (or SSD) access: for a spinning disk this is on the order of $10^6$–$10^7$ ns (milliseconds), versus roughly 1 ns for a DRAM access. This asymmetry — five to six orders of magnitude — is the entire reason demand-paging policy differs from L1/L2 cache policy: the miss penalty is so catastrophic that software (with access to rich information: reference history, process priorities, disk layout) is used to pick victims and prefetch, rather than a small hardwired hardware state machine.

Why demand paging is efficient — the locality argument. Demand paging is only a good idea because of the same principle of locality that justifies caching in general: at any instant, a program's memory references cluster into a small working set of pages. If $W$ pages, $W \ll V/P$, cover almost all references during any interval, then keeping only $W$ frames resident captures almost all hits, and misses (faults) are rare. This is exactly the argument used for Cache Performance and Average Memory Access Time: define an analogous "average memory access time" for the virtual-memory layer,

where $t_{\text{DRAM}}$ is the (translated) DRAM access time, $P_{\text{fault}}$ is the page fault rate, and $t_{\text{disk}}$ is disk latency. Because $t_{\text{disk}} / t_{\text{DRAM}}$ is on the order of $10^5$–$10^6$, even a fault rate as low as $10^{-6}$ can double the effective access time — which is why operating systems work so hard to keep $P_{\text{fault}}$ near zero via good replacement policy and adequate physical memory.

Correctness argument. Two invariants must hold for the system to behave correctly: 1. Mapping consistency invariant — at every instant, if a process's page table marks virtual page $v$ as present with frame $f$, then frame $f$'s physical contents are exactly the correct, current data for $v$ (not stale, not another process's data). This is maintained by: invalidating the old process's entry before reassigning a frame during eviction, and by write-back before eviction if the evicted page is dirty (modified since it was loaded). 2. Fault transparency invariant — after `HANDLE_PAGE_FAULT` returns, re-executing the faulting instruction with the now-updated page table produces exactly the result the program would have gotten had the page always been resident. This requires that faults are precise: the processor state at the fault is exactly as if the faulting instruction had not yet begun, so re-issuing it is safe and produces no double side effects. Given these invariants, demand paging is observationally indistinguishable from running with all pages permanently resident — the program's semantics never depend on when a fault occurs, only its timing does. This is the correctness property that lets application programmers ignore the entire mechanism.

Honest tradeoffs. Demand paging buys a huge working set illusion at the cost of unpredictable latency spikes (a fault can stall a thread for milliseconds — unacceptable for hard real-time systems, which often disable paging or lock pages in memory). It also introduces thrashing: if the sum of active processes' working sets exceeds physical DRAM, the system spends most of its time faulting rather than computing, and throughput collapses. Recognizing and avoiding thrashing (via admission control, working-set estimation, or simply adding RAM) is a first-order operating-systems concern that flows directly from this model.

Consider a toy system with an 8 KiB virtual address space per process, 2 KiB pages (so 4 virtual pages, numbered 0–3), and only 3 physical frames of DRAM (6 KiB) shared system-wide, of which frames 0–1 currently belong to this process and frame 2 is free. Initial state:

The program executes a sequence of memory references. Trace them:

Notice what happened between steps 5 and 7: evicting VP1 to make room for VP3 caused a subsequent reference back to VP1 to fault again — a direct illustration of thrashing when the working set (VP1, VP2, VP3 all wanted "at once") exceeds available frames (only 2 usable after VP0 is pinned). If a fourth frame had been available, step 7's fault would never occur. This single trace demonstrates the entire chain: address decomposition, table lookup, fault handling, victim selection, write-back consideration (VP1 and VP2 were both clean here, so no write-back was needed — had VP1 been dirty, step 5 would have required writing it to disk before reuse), and the performance cliff caused by an undersized resident set.

Every general-purpose operating system kernel — Linux, Windows, macOS, BSD, and the Linux-derived kernels inside Android and iOS's XNU relative — relies on virtual memory to multiplex many processes safely onto shared DRAM. Database systems and language runtimes (JVM, V8, CPython) build their own memory managers on top of virtual memory's guarantees, trusting the OS to isolate their heaps from other processes. Containers and virtual machines (Docker, KVM, Hyper-V) extend the same idea one level further: a hypervisor virtualizes physical memory itself, giving each guest OS what looks like real physical memory but is itself another layer of paging. Memory-mapped files (`mmap`), copy-on-write process forking, and swap space all are direct applications of demand paging's fault-and-fetch mechanism. Even security features — address space layout randomization (ASLR), guard pages that deliberately fault to catch buffer overflows, and per-process sandboxing — depend on the isolation and page-fault machinery introduced here. Anywhere a system needs to run more work than fits in physical memory, or needs to guarantee one buggy program cannot corrupt another's memory, virtual memory is the underlying mechanism.

:::quiz[In the virtual address decomposition [ VPN | offset ], what happens to the offset bits during translation?]

• They are translated using the same table as the VPN
• They are discarded and recomputed from the physical frame number
• They are copied unchanged into the physical address ✓
• They are XORed with the frame number for scrambling

Ask the tutor: How do multi-level page tables keep the translation structure small enough to fit in memory for a 64-bit address space?