Chapter 5: Memory Management I: Paging and Segmentation

Why this matters

Every process behaves as though it has its own private, contiguous block of memory starting at address zero — which is a complete fiction the OS maintains on its behalf. Understanding how that fiction is maintained explains memory isolation between processes, why a segmentation fault happens, and sets up the vocabulary (pages, frames, page tables) that virtual memory and page replacement (Chapter 6) build directly on top of.

The core concept: why not just give each process real contiguous memory?

[BEGINNER] The naive approach — giving each process a real, contiguous chunk of physical RAM — has a fatal flaw: as processes start and stop over time, physical memory gets carved into a patchwork of used and free chunks of varying sizes (external fragmentation), and eventually there can be enough total free memory to satisfy a new request, but no single contiguous chunk large enough, wasting available capacity.

Physical RAM, after several processes start/stop:
[Process A: 4MB][free: 1MB][Process B: 2MB][free: 1MB][Process C: 3MB][free: 2MB]
Total free: 4MB. But the largest CONTIGUOUS free chunk is only 2MB —
a new process needing 3MB contiguous can't be placed, despite 4MB being free overall.

Paging: breaking memory into fixed-size chunks

[BEGINNER] Paging solves this by dividing a process's memory into fixed-size pages (typically 4 KB on Linux/x86) and physical RAM into same-sized frames. A process's pages don't need to be contiguous in physical memory at all — the OS maintains a page table that maps each virtual page number to whatever physical frame currently holds it.

Process's virtual address space (what the process believes it has):
Page 0 | Page 1 | Page 2 | Page 3   (appears contiguous to the process)

Page Table (maintained by the OS, per-process):
Page 0 -> Frame 7
Page 1 -> Frame 2      (physically scattered — doesn't matter, the mapping hides it)
Page 2 -> Frame 15
Page 3 -> Frame 4

Physical RAM (actual layout — scattered, and that's fine):
[Frame 2: Page1][Frame 4: Page3][Frame 7: Page0]...[Frame 15: Page2]

Because pages and frames are the same fixed size, external fragmentation is eliminated entirely — any free frame can hold any page. A small amount of internal fragmentation remains (a page that needs only 100 bytes still consumes a full 4 KB frame), but this waste is bounded and predictable, unlike external fragmentation's unbounded, unpredictable waste.

Translating a virtual address, conceptually:

Virtual address = [ Page Number | Offset within page ]

1. CPU looks up Page Number in the page table -> gets Frame Number
2. Physical address = [ Frame Number | same Offset ]
3. That physical address is what actually goes out to the memory bus

This translation happens on every single memory access a program makes — which is far too frequent to do via a slow, full page-table lookup each time. Real CPUs cache recent translations in a small, extremely fast hardware cache called the Translation Lookaside Buffer (TLB) — this is exactly the cache invalidation cost referenced in Chapter 2's discussion of why process context switches are more expensive than thread context switches: switching to a different process's page table invalidates the TLB's cached translations, since they're no longer valid for the new address space.

Segmentation: the alternative (and complementary) approach

[BEGINNER] Segmentation divides memory not into fixed-size chunks, but into logically meaningful, variable-sized segments — typically code, data (globals), heap, and stack — each segment potentially a different size, matching the program's actual logical structure rather than an arbitrary fixed page size.

Process's segmented view:
+----------------+   +----------------+   +----------------+   +----------------+
|  Code segment  |   |  Data segment  |   |  Heap segment  |   | Stack segment  |
|   (2 KB)       |   |   (512 bytes)  |   |  (grows up)    |   |  (grows down)  |
+----------------+   +----------------+   +----------------+   +----------------+

[SENIOR INSIGHT] Segmentation's logical structure is genuinely more meaningful to a programmer (and enables per-segment protection — code segments read-only/executable, data segments read-write, stack non-executable — which is directly relevant to real security mechanisms like NX/DEP), but pure segmentation reintroduces the exact external fragmentation problem paging solved, since segments are variable-sized. Modern systems use paged segmentation, or (like x86-64 Linux) mostly abandon true multi-segment memory in favor of a flat address space managed entirely through paging, while keeping segmentation's logical categories (code/data/heap/stack) as page-table permission attributes rather than as the actual memory-layout mechanism.

What actually causes a segmentation fault

[IN PRACTICE] A segmentation fault ("segfault") is the OS's response to a process accessing memory its page table says it isn't allowed to access — either an address with no valid page-table entry at all, or an address whose entry exists but disallows the attempted operation (writing to a read-only code page, executing a non-executable data page).

int main() {
    int *ptr = NULL;
    *ptr = 42; // Attempts to write to virtual address 0.
    // The page table has no valid mapping for address 0 (deliberately, by OS convention,
    // exactly so that NULL pointer dereferences are reliably caught this way) —
    // the CPU's memory management unit signals a page fault, the OS recognizes it as
    // invalid (not a legitimate "not yet loaded" case, see Chapter 6), and sends SIGSEGV.
    return 0;
}

This is precisely why dereferencing a NULL pointer reliably crashes rather than silently corrupting arbitrary memory — the OS deliberately leaves the first page of virtual address space unmapped for exactly this reason, turning a whole class of pointer bugs into an immediate, debuggable crash instead of silent corruption.

Common mistakes

1. Confusing a segmentation fault with "the program ran out of memory." A segfault means an invalid access (wrong permissions, or no mapping at all) — it can happen with plenty of free memory available; it's a protection violation, not a capacity issue.
2. Assuming paging eliminates fragmentation entirely. It eliminates external fragmentation but introduces bounded internal fragmentation (unused space within a page) — a real, if much smaller, cost.
3. Thinking a process's memory addresses are physical addresses. Every address a userspace program works with is a virtual address; the translation to a physical frame happens transparently via the page table and TLB on every access.
4. Not connecting TLB invalidation to the process-vs-thread context-switch cost discussed in Chapter 2 — this chapter's page table mechanism is the concrete "why" behind that earlier chapter's claim.

Checklist: reasoning about paging and segmentation

1. Remember every userspace memory address is virtual — physical memory layout is an implementation detail the page table hides, and it's normal (and expected) for a process's pages to be scattered across physical RAM.
2. When debugging a segfault, think "invalid access" (wrong permission or unmapped address), not "out of memory" — check what the code was actually trying to do at that address (write to read-only memory, dereference NULL/an already-freed pointer, etc.).
3. Remember paging trades unbounded external fragmentation for small, bounded internal fragmentation — a page size choice (e.g., 4 KB vs. huge pages) is itself a trade-off between internal fragmentation and page-table/TLB overhead.
4. Connect page-table switches to context-switch cost (Chapter 2) when reasoning about why process switches are more expensive than thread switches.

Discussion / interview questions

1. "What problem does paging solve that a naive contiguous-memory-per-process approach doesn't?" Strong answer: External fragmentation — over time, contiguous-allocation schemes leave free memory scattered in chunks too small to satisfy new requests even when total free memory would suffice; paging's fixed-size pages/frames mean any free frame can hold any page, eliminating this.

2. "What actually causes a segmentation fault?" Strong answer: An invalid memory access as determined by the page table — either no valid mapping exists for the address, or the mapping exists but disallows the attempted operation (e.g., writing to a read-only page) — not "the program used too much memory."

3. "Why does dereferencing a NULL pointer reliably crash instead of corrupting memory silently?" Strong answer: The OS deliberately leaves the first page of virtual address space unmapped, specifically so that any access through a NULL (or near-NULL) pointer triggers an immediate, catchable page fault rather than accessing arbitrary, possibly valid, memory.

4. "What's the difference between paging and segmentation, and why do most modern systems favor paging?" Strong answer: Paging divides memory into fixed-size chunks (eliminating external fragmentation, at the cost of bounded internal fragmentation); segmentation divides memory into logically meaningful, variable-sized chunks (more meaningful to programmers and permissions, but reintroduces external fragmentation) — most modern systems use paging as the actual memory-layout mechanism while keeping segmentation's logical categories as page permission attributes.

Chapter summary / cheat sheet

• Naive contiguous memory allocation suffers external fragmentation — paging fixes this by dividing memory into fixed-size pages/frames, at the cost of bounded internal fragmentation.
• A page table (per process) maps virtual pages to physical frames; the TLB caches recent translations for speed, and invalidating it on a process switch is why process context switches cost more than thread switches (Chapter 2).
• Segmentation divides memory into logically meaningful, variable-sized regions (code/data/heap/stack) — more meaningful to programmers and permissions, but reintroduces external fragmentation if used as the sole mechanism; modern systems mostly keep it only as a logical/permission layer on top of paging.
• A segmentation fault is an invalid memory access per the page table (unmapped or disallowed), not an out-of-memory condition — and NULL pointer dereferences crash reliably specifically because the OS deliberately leaves address zero unmapped.

---