Lecture 24: Virtual Memory

What this lecture covers

This lecture, guest-taught by a SAFARI research group PhD student, answers a basic question: why don't programs ever see real physical memory addresses, and how does the system fake it for them? It sits in the course's memory-system arc, right after the caching material, and treats physical memory itself as a kind of cache for data that ultimately lives on disk.

By the end you should be able to explain why virtual memory exists, walk through how a virtual address is translated to a physical one using a multi-level page table, describe what happens on a page fault, and explain how TLBs and memory protection (including the Row Hammer attack) fit into the same hardware-software system.

Key ideas

• Virtual memory: an abstraction that gives each process the illusion of a large, private, contiguous address space, while the operating system and hardware cooperatively map it onto a much smaller physical memory.
• Page and frame: the virtual address space is split into fixed-size pages; the physical address space is split into frames of the same size. A page table maps pages to frames.
• Page table: a per-process data structure, conceptually a dictionary, that stores the virtual-to-physical mapping plus a validity bit and permission bits for each page.
• Multi-level page table: instead of one huge flat table, the table is organized as a tree of smaller tables so that unused parts of the virtual address space cost nothing in physical memory.
• Page fault: what happens when a page table entry is invalid; a minor fault just needs a free physical frame, a major fault also needs to fetch the page from disk.
• TLB (translation lookaside buffer): a small hardware cache inside the memory management unit that stores recently used translations so most accesses skip the page table walk.
• Memory protection: page tables also carry read/write/execute permissions, which is what keeps one process from touching another process's memory or overwriting shared library code.

Walkthrough

Why programs need virtual memory (3:49)

The lecture opens with the ideal a programmer wants: free, infinite, zero-cost memory. Reality is a small, finite physical memory shared by multiple programs. If programs addressed physical memory directly, the programmer would have to worry about whether code and data fit, where to place them so two processes don't collide, and how to relocate or share data safely. Virtual memory removes this burden by giving each process its own address space and letting the system, not the programmer, decide where data actually lives.

Address translation and the page table (11:58)

The lecture works through a worked example: a 2 GB virtual address space, a much smaller physical memory, and 4 KB pages. It shows how to split an address into a virtual page number and a page offset, and how the page offset stays untranslated because it only locates data within a page. A page table entry supplies a validity bit and the physical frame number; if the entry is invalid, the requested page is on disk rather than in memory. Several example addresses are translated by hand to show the lookup.

Multi-level page tables (29:17)

A flat page table for a 64-bit address space would need an infeasible amount of memory per process. The fix is a hierarchical, tree-shaped page table: a top-level table with a fixed size points to second-level tables only for the parts of the address space actually in use. In x86-64, four levels of nine bits each are walked from a base register (CR3) down to a leaf entry, so an unused region of the address space never needs its lower-level tables allocated at all.

Page faults and the operating system's role (39:26)

When a virtual page is touched for the first time, the OS must "fault it in": find free physical memory and update the page table. A minor fault (an anonymous allocation with no backing file) is cheap. A major fault, where the data is backed by a file on disk, is expensive: the OS signals an I/O controller, which uses direct memory access (DMA) to move the block from disk into memory without involving the processor, and then the page table entry is updated and execution resumes. The lecture also covers the clock algorithm, a cheap approximation of least-recently-used, for choosing which page to evict when memory is full.

Memory protection and the Row Hammer attack (1:07:37)

Beyond translation, page tables carry access permissions per page, enforced at the same time as translation, which is what isolates processes and lets code pages be marked read-only. This section connects that mechanism to Row Hammer: repeatedly activating a DRAM row can flip bits in physically neighboring rows. An attacker can spray physical memory with page tables so that a flipped bit is likely to land inside one, turning a hardware reliability issue into a way to gain unauthorized access to physical memory.

Speeding up translation: TLBs and the MMU (1:22:50)

Since every memory access would otherwise need an extra access just to read the page table, modern cores include a memory management unit (MMU) with a translation lookaside buffer (TLB) that caches recent translations, page-table caches for intermediate tree levels, and a hardware page table walker. The lecture contrasts hardware-managed TLB misses (fast, but with a fixed page table format) against software-managed ones, as used in MIPS, which need an expensive exception but let the OS define its own page table layout.

Virtual memory overheads and current research (1:37:59)

The lecture closes with the presenter's own research: measuring how much time real workloads spend on memory allocation and address translation. Short-running workloads like LLM inference can spend around 32% of execution time simply allocating memory, and data-intensive workloads with irregular access patterns can spend around 26% of execution time on address translation because they overwhelm the TLB. These overheads motivate ongoing work on rethinking virtual memory for GPUs, unified CPU-GPU memory, and disaggregated memory systems.

Before you watch

• Review the caching lectures earlier in the course; the page table is explicitly presented as a cache-like structure for pages that may live on disk.
• Be comfortable converting between bits, bytes, and powers of two, since the lecture derives page table sizes from address-space arithmetic.
• Know what a process and an address space are from earlier systems material; the lecture assumes you already understand basic process isolation.

Check your understanding

1. Why can't a program simply use physical addresses directly, even on a system with more than enough physical memory for all running programs?
2. Walk through what happens, step by step, when a virtual address is not found valid in any level of a four-level page table.
3. Why does a multi-level page table save space compared to a single flat page table, and what has to be true for that saving to be large?
4. What is the difference between a minor and a major page fault, and why is DMA used to service the major one?
5. How does the Row Hammer attack turn a DRAM reliability problem into a way to compromise the page table?