2.5 — Memory Management

We have leaned on a claim for three chapters without justifying it: every process has its own private memory, a full address space it owns, invisible to and protected from every other process (2.2). That claim should trouble you. Your machine has, say, 16 GB of physical RAM — one set of memory chips. Yet a hundred processes each believe they own a vast, private address space starting at address 0, and none can see another's data. How? They can't all literally have their own copy of address 0 in the same RAM. The resolution is virtual memory, and it is, without exaggeration, one of the most ingenious and consequential abstractions in all of computing — the invisible machinery that makes multitasking, process isolation, security, and even running programs bigger than your RAM all possible at once. This chapter builds it from the ground up: the illusion, the page table that implements it, the hardware that makes it fast, and the ways it can go wrong.

1. The problem virtual memory solves

Imagine, briefly, a world without virtual memory, where programs use physical RAM addresses directly (this was real — early computers and simple embedded systems work this way). Three miseries follow immediately:

1. No isolation. If your program writes to address 5000 and mine also uses address 5000, we clobber each other. Any process could read or overwrite any other's data — your banking app's secrets, sitting at addresses any game could poke. Security is impossible.
2. No safety from fragmentation. Programs need contiguous chunks of memory. As they start and stop, free RAM breaks into scattered holes; a program needing 100 MB contiguous might fail even with 200 MB free but fragmented. And the programmer would have to know, at compile time, exactly which physical addresses were free — impossible when many programs share a machine.
3. No running programs bigger than RAM. If a program needs more memory than physically exists, it simply can't run.

Virtual memory dissolves all three with one idea: give each process its own private set of addresses — "virtual" addresses — and put a translator between those and physical RAM. The process only ever sees and uses virtual addresses; it thinks it owns a giant, contiguous, private memory. Behind the scenes, the OS and hardware translate each virtual address the process uses into some actual physical address in RAM — and they're free to scatter it anywhere, keep two processes' identical virtual addresses mapped to different physical locations, or even keep some of it not in RAM at all. The process is blissfully unaware.

Figure 1 — The virtual memory illusion. Each process has its own tidy virtual address space. A translation layer maps virtual addresses to scattered physical RAM — and never maps two processes to the same physical memory (unless deliberately shared), which is exactly what enforces isolation.

2. Paging: the mechanism

To make translation manageable, memory isn't mapped byte by byte (that would need a translation entry per byte — absurd). Instead, both virtual and physical memory are divided into fixed-size blocks. A block of virtual memory is a page; a block of physical RAM is a page frame; both are the same size, almost universally 4 KB. Translation then happens at page granularity: "virtual page 7 lives in physical frame 219." Everything within a page keeps its relative position (the offset), so only the page number needs translating.

The lookup table that stores these mappings — one entry per virtual page, saying which physical frame it's in — is the page table, and every process has its own (which is why the same virtual address in two processes maps to different physical frames — different tables). To translate a virtual address, the hardware splits it into a page number (the high bits — which page?) and an offset (the low bits — how far into the page?). It looks up the page number in the page table to get the physical frame, then combines that frame with the offset to get the real physical address:

Figure 2 — Address translation. The virtual page number indexes the page table to find the physical frame; the offset is carried through unchanged. The page table is the heart of the whole system.

Crucially, the page table entry stores more than a frame number — it stores permission bits: is this page readable? writable? executable? present in RAM at all? This is where a lot of protection lives: the read-only text segment (2.2) is enforced here (its pages are marked non-writable, so a stray write to code faults). Marking data pages non-executable (the "NX bit") is a major defense against attacks that inject code (Part 8). The page table is thus not just a map — it's a per-page permission checkpoint the hardware consults on every memory access.

3. Making it fast: the TLB

There's an obvious performance catastrophe lurking. If every memory access by a program must first consult the page table — which itself lives in memory — then every load or store becomes (at least) two memory accesses: one to read the page table, one to get the actual data. Memory is already the slow part (1.6); doubling every access would be ruinous. (It's worse than doubling: modern 64-bit page tables are multi-level — a hierarchy of tables to avoid one impossibly huge flat table — so a translation can cost four or five memory accesses.)

The rescue is a small, specialised, blazingly-fast hardware cache dedicated entirely to translations: the Translation Lookaside Buffer (TLB). It caches recent virtual-page → physical-frame mappings right on the CPU. Now the flow is: the hardware checks the TLB first; on a TLB hit (the mapping is cached — the common case, thanks to locality from 1.6, since programs keep touching the same pages), translation is nearly instant; only on a TLB miss does the hardware do the slow multi-level page-table walk — and it caches the result in the TLB for next time. The TLB is why virtual memory is nearly free in practice despite the theoretical overhead. It's also a hidden reason 2.2's context switches cost more than they appear: switching to a different process means a different page table, so much of the TLB is now stale and must be flushed and slowly refilled — part of why too much switching hurts, and why features like tagged TLBs and "huge pages" (2 MB or 1 GB pages, fewer entries to cache) exist to relieve this pressure.

4. Demand paging: the illusion of infinite memory

Now the third miracle. Because the page table can mark a page as "not present in RAM," the OS can pull a beautiful trick: don't load a page into RAM until the program actually touches it. This is demand paging. When a program accesses a virtual page that isn't currently in physical RAM, the hardware detects it (the present-bit is off) and raises a page fault — a trap into the kernel, much like a syscall but involuntary. The kernel's page-fault handler figures out where that page's data really is, finds a free frame (or frees one), loads the data in, updates the page table, and resumes the program exactly where it left off. The program never knows it briefly stalled; it just accessed memory.

This unlocks running programs larger than physical RAM. When RAM fills up, the OS takes pages that haven't been used recently and writes them out to disk — to a swap area (a swap file/partition on Linux, the page file on Windows) — freeing their frames for other pages. If the program later touches a swapped-out page, that's a page fault that loads it back from disk. So RAM acts as a cache for a larger virtual memory backed by disk — the 1.6 hierarchy again, one level down. This is how you can have programs whose total memory exceeds your RAM: the rarely-used parts live on disk.

But there's a cliff, and it has a name every engineer should know: thrashing. Disk is ~100,000× slower than RAM (1.6). If the active working set of your programs genuinely exceeds physical RAM, the OS is forced to constantly evict a page someone needs, only to fault it right back in, evicting another needed page — a death spiral where the machine spends all its time swapping pages to and from disk and almost none doing real work. The symptom is unmistakable and terrifying: the disk light pins solid, and the whole machine grinds to a crawl, sometimes for minutes, often needing a hard reboot. Thrashing is why adding RAM dramatically speeds up a machine that was swapping, and why servers are configured to keep their working set comfortably within RAM. The OS chooses which page to evict using a page replacement policy — approximating "evict the least-recently-used page" (LRU), betting on temporal locality, exactly as caches do.

5. mmap and allocators: how programs actually get memory

Two practical layers sit on top, worth knowing because you use them constantly, often unknowingly.

The kernel hands out memory to a process in whole pages, via system calls — chiefly mmap ("memory map"). mmap asks the kernel to map a region of pages into the process's address space. It has two superpowers. First, it backs your general dynamic memory (the heap grows via mmap/brk). Second, and elegantly, it can map a file directly into memory (memory-mapped files): after mapping, you access the file's contents as if it were an array in memory — reading address X is reading byte X of the file, with the kernel transparently paging file data in on demand (page faults!) and writing changes back. This is how databases and language runtimes read huge files efficiently without explicit read() syscalls, and how shared libraries are loaded once into RAM and mapped into many processes (each process's virtual pages pointing at the same physical frames — shared, read-only — which is also how 2.2's copy-on-write fork works: parent and child page tables point at the same frames until a write triggers a fault that copies the page).

But mmap deals in 4 KB pages, while your program allocates objects of a few bytes to a few kilobytes constantly (malloc, new, every object a language creates). Making a syscall for each tiny allocation would be absurdly slow (2.1). So a memory allocator (like malloc/glibc's allocator, jemalloc, or tcmalloc) sits in user space between your code and the kernel: it requests memory from the kernel in big chunks (via mmap/brk), then hands out small pieces from those chunks to your program, tracking what's free and reusing freed space — amortising the expensive syscalls over thousands of cheap allocations. The allocator is why malloc is fast, why memory fragmentation is its problem to manage, and why choosing a better allocator can measurably speed up an allocation-heavy program. When you call free (or a garbage collector reclaims an object — Part 3), memory returns to the allocator's pool, not usually to the kernel.

6. The expert lens

Virtual memory is the foundation of all process isolation and much of security. Everything that keeps processes apart traces back to this: because each process has its own page table, it literally cannot name another process's physical memory — there's no virtual address in its space that maps there. This is the enforcement mechanism behind 2.1's isolation, behind why a compromised process can't read another's secrets, and — scaled up — behind container and VM isolation (Chapter 2.9). The page table's permission bits add another security layer: making the stack and heap non-executable (NX) defeats classic code-injection attacks, forcing attackers into far harder techniques (return-oriented programming), and ASLR (address space layout randomization) shuffles where things land in the virtual space so attackers can't predict addresses. Virtual memory isn't just a convenience; it's one of the walls holding up the security model.

A "segfault" is now fully explained. 2.1 said a bad pointer traps and kills your process; you can now see the exact machinery. When a program dereferences a pointer to a virtual address that its page table has no valid mapping for (or writes to a read-only page), the hardware raises a page fault, the kernel checks and finds the access illegal (not a swapped-out page to load, but genuinely invalid), and sends SIGSEGV (2.2), terminating the process. A segmentation fault is a page fault the kernel decided was a bug, not a demand-paging opportunity — same mechanism, different verdict. Understanding this is understanding the single most common crash in systems programming.

Performance lives and dies by locality — at yet another level. You met cache locality in 1.6; virtual memory adds TLB locality and page locality. Code that touches memory in a scattered pattern doesn't just miss the CPU cache — it can miss the TLB (forcing slow page-table walks) and, worse, fault pages in and out of RAM. This is why the same O(n) algorithm can be orders of magnitude slower with a bad memory-access pattern, why "keep your working set small and dense" is a mantra, and why data-structure layout (arrays vs pointer-chasing) matters at every level of the hierarchy. A production system that starts swapping thrashes and effectively dies — so capacity planning is often "keep the working set in RAM" above all.

Next chapter: we've been vague about "the disk" that swap and files live on. What is a file, how does the OS turn "open report.pdf" into the right bytes on a physical drive, and why can WizTree scan an entire disk in seconds when Explorer takes minutes? Chapter 2.6 opens up the file system.

Recall

• Virtual memory gives every process its own private virtual address space; a translation layer maps virtual addresses to scattered physical RAM. This is what enforces process isolation (different page tables → can't even name another's memory), enables running programs larger than RAM, and underlies security.
• Memory is divided into fixed-size pages (virtual) and page frames (physical), usually 4 KB. The page table (one per process) maps page → frame and holds permission bits (read/write/execute/present) checked on every access.
• Translating on every access would be ruinous, so the TLB caches recent translations on the CPU; a TLB hit is near-instant, a miss walks the multi-level page table. Context switches flush TLB entries — part of their cost.
• Demand paging loads pages only when touched; a missing page raises a page fault, and unused pages can be swapped to disk — so RAM is a cache for a larger virtual memory. Exceeding the working set causes thrashing (constant swapping, machine crawls).
• mmap maps pages (and files) into the address space; allocators (malloc) request big chunks from the kernel and hand out small pieces, amortising syscalls. A SIGSEGV is a page fault the kernel ruled an illegal access.

Self-test: What three problems does virtual memory solve? Walk a virtual address through translation to a physical one. Why does the TLB exist, and what happens on a miss? What is a page fault, and how can it be either normal (demand paging) or fatal (segfault)? What is thrashing and why does more RAM fix it?

Quiz Bank

FoundationalWhat is virtual memory and what problems does it solve?

Virtual memory gives each process its own private set of ("virtual") addresses, with a hardware+OS translation layer mapping them to physical RAM. It solves three problems at once: isolation (each process has its own page table, so it can't even address another's memory — the basis of protection and security), flexible placement (a process sees a clean contiguous space while its pages are scattered across physical RAM, avoiding fragmentation and fixed addresses), and capacity (pages not in use can live on disk, so programs can use more memory than physically exists). The process is unaware any translation happens.

FoundationalWhat are pages, frames, and the page table?

Memory is divided into fixed-size blocks: a page is a block of virtual memory, a page frame is a block of physical RAM, both typically 4 KB. The page table is a per-process structure mapping each virtual page to the physical frame holding it, plus permission bits (readable/writable/executable/present). To translate a virtual address, hardware splits it into a page number (index into the page table → frame) and an offset (carried through unchanged into the frame).

AppliedWhy does the TLB exist, and what happens on a TLB miss?

Without help, every memory access would require first reading the page table (itself in memory) to translate the address — doubling (or, with multi-level tables, 4–5×-ing) memory traffic. The Translation Lookaside Buffer (TLB) is a small, fast on-CPU cache of recent virtual→physical translations, so the common case (a TLB hit) translates almost instantly, exploiting locality. On a TLB miss, the hardware performs the slow multi-level page-table walk to find the mapping, then caches it in the TLB. Because a context switch changes the page table, TLB entries are invalidated — a hidden cost of switching processes.

AppliedWhat is a page fault, and how can the same mechanism be both routine and fatal?

A page fault is a hardware trap raised when a program accesses a virtual page that isn't present in RAM (or violates its permissions). The kernel's handler inspects it. Routine case (demand paging/swap): the page is valid but not currently in RAM (never loaded yet, or swapped to disk) — the kernel loads it into a frame, updates the page table, and resumes the program transparently. Fatal case (segfault): the access is genuinely illegal — no valid mapping, or a write to a read-only page — so the kernel sends SIGSEGV and terminates the process. Same trap, different verdict: a demand-paging opportunity vs a bug.

InterviewWhat is thrashing, and why does adding RAM fix it?

Thrashing happens when the combined active working set of running programs exceeds physical RAM. The OS must keep evicting pages that are still needed to make room for others, only to fault them back in moments later — a swap death-spiral where the machine spends nearly all its time moving pages between RAM and disk (~100,000× slower) and almost none doing useful work; the system grinds to a near halt. Adding RAM fixes it because once the working set fits in physical memory, pages stop being evicted and re-faulted — the constant disk swapping stops. It's why a swapping server is dramatically faster after a RAM upgrade, and why capacity planning aims to keep the working set within RAM.

InterviewWhat is the role of a memory allocator like malloc, versus the kernel's mmap?

The kernel hands out memory only in whole pages (4 KB) via syscalls like mmap/brk — and syscalls are expensive (2.1). But programs allocate objects of a few bytes to kilobytes constantly. A memory allocator (malloc, jemalloc, tcmalloc) lives in user space: it requests large chunks from the kernel, then subdivides them into the small allocations your code asks for, tracking free/used regions and reusing freed memory — amortising one expensive syscall over thousands of cheap mallocs. So malloc is fast because it usually just carves from an already-obtained pool; fragmentation management and returning memory to the OS are the allocator's concerns.

StaffA production service runs fine for hours, then latency suddenly spikes 100× and the host's disk I/O saturates though the app isn't doing disk work. Diagnose using this chapter.

The pattern — sudden 100× latency, saturated disk I/O, no app-level disk activity — strongly indicates the host has begun swapping and is thrashing. Over hours the process's memory footprint (a leak, an unbounded cache, or simply growing load) pushed the active working set past physical RAM; the OS started evicting pages to the swap area and faulting them back on demand, so ordinary memory accesses now intermittently hit disk (~100,000× slower than RAM), which both explains the latency cliff and the disk saturation that isn't "the app doing I/O" (it's the kernel paging). Confirm by checking swap usage and major page-fault rates (e.g. vmstat, si/so columns; free; per-process RSS). Fixes, short and long: immediately, reduce memory pressure (restart/scale the leaking process, cap its memory, add RAM, or move load off the host); structurally, find why the footprint grew — a memory leak (Part 3 GC/leaks), an unbounded in-memory cache lacking eviction (1.6), or under-provisioned RAM for the real working set — and size the host so the working set stays in RAM with headroom. The staff framing: this isn't a code-latency bug, it's a memory-capacity failure surfacing as latency, and the fix is capacity/working-set management, not micro-optimisation.

Flashcards

FlashWhat virtual memory gives each process

Its own private virtual address space, translated to physical RAM via a per-process page table — enforcing isolation and enabling more memory than RAM.

FlashPage vs page frame

Page = a fixed-size (usually 4 KB) block of virtual memory; frame = the same-size block of physical RAM it maps to.

FlashWhat the TLB does

Caches recent virtual→physical page translations on the CPU so most memory accesses skip the slow page-table walk.

FlashPage fault

A trap when a program touches a page not present in RAM; kernel loads it (demand paging/swap) or, if the access is illegal, sends SIGSEGV.

FlashThrashing

Working set exceeds RAM → constant swapping to/from disk → machine spends all time paging, nearly no real work. Fixed by more RAM / smaller working set.

Flashmmap vs malloc

mmap: kernel maps whole pages (or files) into the address space. malloc: user-space allocator subdivides big kernel chunks into small fast allocations.

FlashHow copy-on-write fork uses paging

Parent and child page tables point at the same physical frames (read-only); a write triggers a page fault that copies just that page.

Scenario Drill

DrillYou need to process a 50 GB file on a machine with 16 GB of RAM. A colleague loads the whole file into memory and it crashes or crawls. Using this chapter, give two approaches that work and explain why.

Loading 50 GB into 16 GB of RAM forces the OS to swap constantly — the working set (the whole file) vastly exceeds physical RAM, so it thrashes (or the allocator fails outright). Two approaches that respect the memory hierarchy: (1) Stream it. Read and process the file in bounded chunks (say a few MB at a time), never holding more than a small window in memory — so the working set stays tiny and constant regardless of file size. This is the streaming model (Node streams, generators, buffered readers — Part 3), ideal when processing is sequential and each part is independent.

(2) Memory-map it (mmap). Map the file into the address space with memory-mapped files; you then access it like a giant array, and the kernel uses demand paging to bring in only the pages you actually touch, evicting them under pressure — so at any moment only your active pages occupy RAM, not the whole 50 GB. This shines for random access into the file (databases do exactly this) because you let the OS's paging machinery act as an automatic cache over the file. Both work by the same principle:

never make the working set exceed RAM — either by explicitly bounding it (streaming) or by letting virtual memory page in only what's used (mmap). The naïve "load it all" ignores that RAM is finite and that virtual memory will paper over the gap with catastrophically slow disk swapping.