7. Memory Management

Every program you run believes it owns a private, contiguous stretch of memory starting at a low address — and that belief is a lie maintained jointly by the compiler, the operating system, and a piece of hardware called the MMU. This chapter explains how that illusion is built: how a symbolic name in source code becomes a physical location in a DRAM chip, how the OS packs many processes into one physical memory without letting them touch each other, and how paging replaced contiguous allocation because fragmentation made the simple approach untenable. It is the foundation for Chapter 8, which removes the last constraint by allowing a process to use more memory than physically exists.

<a id="71-main-memory-fundamentals"></a>

7.1 Main Memory Fundamentals

This section establishes the machinery every later scheme relies on: when an address is decided, what the two kinds of address are, the hardware that translates between them, the minimal protection scheme, and the two techniques — dynamic linking and swapping — that let memory hold more than it otherwise could.

Address Binding

Theory

You write int counter; and later counter++. At some point that name must become a number: a specific location in a specific memory chip. The question of when that decision is made is called address binding, and it is the single choice that determines how flexible the entire memory system can be.

A program travels through several stages before it runs, and binding can happen at any of three of them:

1. Compile time. If the compiler knows in advance where in physical memory the program will live, it can emit final physical addresses directly. The output is called absolute code. This is fast — no translation at run time — but the program is nailed to one address forever. Move it and it breaks. MS-DOS .COM files worked this way (always loaded at offset 0x100), and embedded firmware still does, because on a microcontroller there is exactly one program and its address is known by the linker script.

2. Load time. If the starting location is unknown at compile time, the compiler emits relocatable code: addresses expressed as offsets from the beginning of the module, plus a relocation table listing every place needing fixing. The loader adds the real base address to each entry as it copies the program into memory. The program can now be placed anywhere — but only once. After loading, the addresses are physical and the process cannot be moved.

3. Execution time. The program keeps using its own internal addresses forever, and hardware translates each one at the moment of access. Binding is deferred to the last possible instant, which means the OS may relocate a process at any time — mid-execution, between two instructions — simply by changing what the translation hardware is told. Every general-purpose OS does this, because it is what makes swapping, compaction, paging, and shared libraries possible.

The analogy that fits is postal addressing. Compile-time binding is engraving a street address into the building's foundation. Load-time binding is stamping the address on the building once, when it is erected. Execution-time binding is giving the building a PO box: mail is addressed to the box, and the post office maintains a table saying where the box currently forwards to. The occupant can move house without anyone re-learning the address.

The cost of deferral is hardware. Execution-time binding requires a translation step on every memory reference — instruction fetches included — so it can only be done at a price acceptable if it is done in silicon.

Example

   THE PATH FROM SOURCE TO A RUNNING IMAGE, AND WHERE BINDING CAN OCCUR

   source.c
      |  compiler
      v
   source.o          <-- symbolic names resolved to MODULE-RELATIVE offsets
      |                  [ COMPILE-TIME binding possible here if the final
      |                    location is known: emit absolute addresses ]
      |  linker  (+ other .o files, + static libraries)
      v
   a.out             <-- one address space, still relative to 0
      |                  [ LOAD-TIME binding: loader adds base to every
      |                    entry in the relocation table ]
      |  loader
      v
   in-memory image
      |                  [ EXECUTION-TIME binding: addresses stay relative,
      v                    MMU adds/translates on every single access ]
   running process

   BINDING TIME vs WHAT IT COSTS AND BUYS

   Binding at      Relocatable after?   Translation cost   Typical user
   -----------     ------------------   ----------------   -------------------
   compile time    never                zero               firmware, .COM
   load time       before start only    zero               old embedded loaders
   execution time  at any instant       MMU on every ref   every modern OS

/* Demonstrating that modern binaries do NOT hard-code their addresses.
   Compile twice and compare:
     gcc -no-pie prog.c -o prog_fixed   -> addresses fixed at link time
     gcc  -pie   prog.c -o prog_pie     -> position-independent, relocated
                                           at load time by the dynamic loader */
#include <stdio.h>

int global_var = 42;                  /* lives in .data          */

int main(void) {
    int stack_var = 0;                /* lives on the stack       */
    printf("code   (main)   : %p\n", (void *)main);
    printf("global (.data)  : %p\n", (void *)&global_var);
    printf("stack           : %p\n", (void *)&stack_var);
    return 0;
}

# Run the PIE build twice. ASLR gives different addresses each time:
# only execution-time binding makes this possible.
./prog_pie ; ./prog_pie
# code   (main)   : 0x55c3f2a01139
# code   (main)   : 0x5605b8e2d139     <- moved, and the program did not care

# Turn ASLR off for one command and the addresses become reproducible:
setarch $(uname -m) -R ./prog_pie

Key takeaways

• Address binding is the question of when a symbolic name becomes a concrete address: compile time, load time, or execution time.
• Compile-time and load-time binding produce addresses that are physical from then on; the process can never be moved afterwards.
• Execution-time binding keeps program addresses independent of physical placement, which is the precondition for swapping, compaction, paging, and sharing.
• Deferring to execution time requires hardware translation on every memory reference — the reason MMUs exist.

🧪 Practice

1. A program is compiled with absolute addresses assuming it loads at 0x8000, but the loader places it at 0xC000. Describe precisely what happens on the first call to a function, and why the failure is usually a crash rather than a wrong answer.
2. Write the relocation step by hand: given a module with a jump to relative address 0x120 and a base of 0x40000, compute the patched address. Then explain why a relocation table must distinguish absolute references from PC-relative ones.
3. Interview-style: "Why can ASLR only exist on systems that bind addresses at execution time or load time?" Hint: think about what ASLR changes between two runs of the same unmodified binary file on disk, and who would otherwise have had to be told about the change.

Logical vs Physical Address Space

Theory

Once binding is deferred to execution time, a program's addresses and memory's addresses stop being the same thing, and it becomes essential to name them separately.

A logical address (also called a virtual address) is what the CPU generates when executing a process's instructions. It is what a pointer holds, what a debugger prints, what a jmp targets. A physical address is what appears on the memory bus and selects a row and column in a DRAM chip. The set of all logical addresses a process can generate is its logical address space; the set of physical addresses that exist in the machine is the physical address space.

Under compile- and load-time binding these two are identical. Under execution-time binding they diverge, and the divergence is the whole point: every process can be given the same logical address space. Two processes can both hold a pointer with the value 0x400000 and refer to entirely different bytes of DRAM. Neither can name the other's memory, because naming happens in the logical space and the translation is controlled by the OS.

The sizes are unrelated. A 64-bit process on Linux has a 47-bit user-visible logical space (128 TiB) on a machine that might have 16 GiB of RAM. The logical space is a namespace, not an inventory — most of it is never mapped to anything at all, and touching an unmapped part is precisely what produces a segmentation fault.

The analogy is a hotel. Guests know their room number ("logical address"): room 101 exists in every hotel of the chain. The building itself has physical positions — third floor, north wing, second door. The front desk maps one to the other. Two guests in two hotels both correctly say "I am in 101" without any conflict, because the number means nothing outside the mapping.

Example

   TWO PROCESSES, ONE PHYSICAL MEMORY

   Process A logical space        Physical memory        Process B logical space
   (0 .. max)                     (0 .. installed)       (0 .. max)

   0x0000 +-------------+                                +-------------+ 0x0000
          |    code     |-----\      +---------+   /-----|    code     |
   0x1000 +-------------+      \---> | 0x7000  | <-/     +-------------+ 0x1000
          |    data     |----\       +---------+         |    data     |
   0x2000 +-------------+     \----> | 0x3000  |         +-------------+ 0x2000
          |    stack    |            +---------+  <------|    stack    |
          +-------------+            | 0x9000  |         +-------------+
                                     +---------+
   SAME logical addresses            DIFFERENT physical locations
   -> total isolation, and neither process can even express the other's address

# Why "the same address" in two processes is not a contradiction:
# the mapping is per-process state held by the kernel.

PAGE = 0x1000

# Each process gets its own translation table. Identical keys, different values.
proc_a = {0x0: 0x7000, 0x1000: 0x3000, 0x2000: 0x9000}
proc_b = {0x0: 0xE000, 0x1000: 0xB000, 0x2000: 0x5000}

def translate(table, logical):
    page, offset = logical & ~(PAGE - 1), logical & (PAGE - 1)
    if page not in table:
        raise MemoryError(f"segmentation fault at {logical:#x}")  # unmapped
    return table[page] + offset

print(hex(translate(proc_a, 0x1004)))   # 0x3004
print(hex(translate(proc_b, 0x1004)))   # 0xb004  <- same logical, other byte
translate(proc_a, 0x8000)               # MemoryError: unmapped region

# Inspect a real logical address space: every line is a mapped region,
# and everything between the lines is unmapped and will fault.
cat /proc/self/maps
# 55a1... r-xp  /usr/bin/cat        <- code, executable, not writable
# 55a1... rw-p  /usr/bin/cat        <- data, writable, not executable
# 7ffd... rw-p  [stack]

Key takeaways

• A logical (virtual) address is generated by the CPU; a physical address selects real storage on the memory bus.
• Under execution-time binding the two spaces are decoupled, letting every process reuse the same logical addresses in isolation.
• The logical address space is a namespace, usually far larger than installed RAM and mostly unmapped.
• A reference to an unmapped part of the logical space is exactly what a segmentation fault reports.

🧪 Practice

1. A 32-bit process has a 4 GiB logical space on a machine with 512 MiB of RAM. Explain how the process can allocate and successfully use a 1 GiB array, and what limits how much of it can be resident at once.
2. Run cat /proc/self/maps twice and compare. Which regions moved, which stayed, and what does that tell you about how each region is bound?
3. Interview-style: "Two processes print the same pointer value. Can they be writing to the same physical byte?" Hint: the answer is 'usually no, but sometimes yes' — think about what fork and shared libraries do to the mapping tables.

Memory Management Unit

Theory

If every memory reference has to be translated, the translation cannot be done in software. A modern core issues on the order of a billion memory references per second; a software translation costing even ten instructions would make the machine roughly ten times slower than the hardware it runs on. The Memory Management Unit (MMU) is the hardware that performs translation at the speed of the pipeline.

The MMU sits between the CPU core and the memory bus. The core emits a logical address; the MMU converts it to a physical address and forwards that to the cache and memory system. The core never emits a physical address, and — critically — never can: there is no instruction that says "read physical byte 0x3F00". That structural inability is what makes isolation enforceable rather than merely conventional.

The MMU does three jobs on every access, in parallel:

1. Translate — apply the mapping the OS installed for the current process.
2. Check — verify the access is permitted (mapped at all, writable if writing, executable if fetching, accessible from the current privilege level).
3. Record — set the accessed and dirty bits that later chapters' page-replacement algorithms depend on.

If the check fails, the MMU cannot resolve the situation itself; it raises a fault, which is a trap to the kernel. The kernel then either fixes the situation and re-executes the instruction (a page fault on a valid but non-resident page — Chapter 8) or kills the process (a genuine protection violation).

The MMU is configured, not commanded. The OS writes a pointer to the current process's translation data into a privileged register — CR3 on x86-64, TTBR0_EL1 on ARM64 — and from then on the hardware works autonomously. Context switching a process's memory view is therefore one register write, plus the consequences described under TLBs later in this chapter.

Example

   WHERE THE MMU SITS

   +---------+  logical  +---------+  physical  +--------+     +---------+
   |   CPU   |---------->|   MMU   |----------->| Cache  |---->|  DRAM   |
   |  core   |  0x1004   | + TLB   |   0x3004   | (phys- |     |         |
   +---------+           +----+----+            | tagged)|     +---------+
                              |                 +--------+
                              | on failure
                              v
                        TRAP TO KERNEL
                    (page fault / protection fault)

   The core has no path around the MMU. Privileged registers select
   WHICH mapping is active:  x86-64 CR3   |   ARM64 TTBR0_EL1

   PER-ACCESS WORK, ALL IN ONE PIPELINE STAGE (on a TLB hit)
     translate  ->  check permissions  ->  set accessed/dirty bits

/* The MMU's per-access logic, written as C to make it explicit.
   In reality this is combinational logic finishing in ~1 cycle on a TLB hit. */

typedef struct { unsigned present:1, writable:1, user:1, no_exec:1,
                          accessed:1, dirty:1; unsigned long frame; } pte_t;

unsigned long mmu_translate(unsigned long vaddr, int is_write,
                            int is_fetch, int is_user_mode) {
    pte_t *e = lookup(vaddr);                 /* TLB, else walk in hardware */

    if (!e->present)      trap(PAGE_FAULT);   /* not resident: kernel may fix */
    if (is_write  && !e->writable) trap(PROT_FAULT);
    if (is_fetch  &&  e->no_exec)  trap(PROT_FAULT);  /* NX: blocks shellcode */
    if (is_user_mode && !e->user)  trap(PROT_FAULT);  /* kernel page from user */

    e->accessed = 1;                          /* used by replacement algos */
    if (is_write) e->dirty = 1;               /* dirty pages must be written back */

    return (e->frame << 12) | (vaddr & 0xFFF);   /* frame + offset */
}

# Evidence of the MMU on a live Linux system.
grep -c . /proc/self/maps          # number of distinct mapped regions
grep VmPTE /proc/self/status       # bytes of page tables the MMU walks for us
# VmPTE:    68 kB

# Faults are counted per process: minor = fixed by the kernel without I/O,
# major = required a disk read.
/usr/bin/time -v ls >/dev/null
#   Minor (reclaiming a frame) page faults: 312
#   Major (requiring I/O) page faults: 0

Key takeaways

• The MMU translates every logical address to a physical one in hardware, because software translation would be orders of magnitude too slow.
• The core cannot emit a physical address directly, which is what makes isolation structural rather than advisory.
• Each access is simultaneously translated, permission-checked, and recorded (accessed/dirty bits).
• The OS controls the MMU by writing a privileged base register (CR3, TTBR0_EL1); the hardware then operates on its own.

🧪 Practice

1. List which of these are handled entirely by the MMU, and which require a trap into the kernel: a normal read of a mapped page, a write to a read-only page, a read of a page currently on disk, the very first write to a copy-on-write page.
2. Suppose the MMU did not set the accessed bit. Name one algorithm from Chapter 8 that becomes impossible to implement efficiently, and explain what the OS would have to do instead.
3. Interview-style: "Why does the CPU cache sit after the MMU on most designs, and what would change if it sat before?" Hint: consider what happens to cached data belonging to process A when process B is scheduled and reuses the same virtual addresses.

Base and Limit Registers

Theory

Before paging, protection had a much simpler form — and it is worth studying because it is the minimal solution, it is still used in embedded MPUs today, and it makes the cost/benefit of everything more elaborate obvious.

Give the CPU two registers. The base register holds the smallest physical address the process may touch. The limit register holds the size of its region. Every logical address a generated by the process is checked and translated in one step:

if (a < limit)  physical = base + a
else            trap: addressing error

Two properties fall out immediately. First, the process's memory is contiguous in physical memory — it must be, since a single base and a single length describe it. Second, the logical address space is [0, limit), so every process again starts at zero and is isolated from every other.

The base register doubles as the relocation register: it is the mechanism by which execution-time binding is achieved. To move a process, the OS copies its bytes elsewhere and updates the base. The process cannot tell.

The security of the whole scheme rests on one rule: loading the base and limit registers is a privileged instruction, executable only in kernel mode. If user code could set its own base, it could point it anywhere and the protection would be decorative. This is the concrete instance of the general dual-mode principle from Chapter 1 — a protection mechanism is only as strong as the privilege required to reconfigure it.

The scheme's limitations are what drive the rest of the chapter. One base/limit pair per process means: memory must be contiguous (so external fragmentation is inevitable), the whole process must be resident (no demand paging), growing the heap or stack means finding a bigger hole and copying, and two processes cannot share a region without sharing everything.

Example

   BASE AND LIMIT IN ACTION

   Physical memory                      Registers for the running process
   0        +---------------+
            |     OS        |             base  = 300040
   300040   +---------------+  <--------   limit = 120900
            |               |
            |  process P    |            Legal physical range:
            |  (120900 B)   |              [300040, 420940)
   420940   +---------------+
            |  process Q    |
            +---------------+

   TRANSLATION AND CHECK, EVERY ACCESS

     logical 0        --> 300040          OK
     logical 120899   --> 420939          OK (last legal byte)
     logical 120900   --> TRAP            >= limit
     logical -1       --> TRAP            unsigned compare catches it

                 +-------+  yes  +-----------+
     CPU  addr ->| <limit|------>| + base    |--> physical address
                 +---+---+       +-----------+
                     | no
                     v
              trap to OS: addressing error (SIGSEGV)

/* The check, and why the ORDER matters. */
unsigned long access(unsigned long logical, unsigned long base,
                     unsigned long limit) {
    /* Compare FIRST, add SECOND. Adding first could overflow past the
       top of the address space and wrap into someone else's memory. */
    if (logical >= limit)
        trap_addressing_error();
    return base + logical;
}

/* Privileged, kernel-mode only -- called from the context switch path. */
void switch_to(struct pcb *p) {
    load_base_register(p->base);       /* privileged instruction */
    load_limit_register(p->limit);     /* privileged instruction */
}

# Why one base/limit pair forces contiguity, and what that costs.
# A process needs 120 KB; free space exists but is scattered.

holes = [("A", 50_000), ("B", 40_000), ("C", 60_000)]   # total 150 KB free
need = 120_000

fits = [name for name, size in holes if size >= need]
print(fits)          # []  -> allocation FAILS despite 150 KB being free
# This is external fragmentation (Section 7.2), and it is unavoidable
# whenever a process must occupy one contiguous physical run.

Key takeaways

• Base plus limit is the minimum viable protection: one compare and one add per access.
• The base register is the relocation register — changing it moves a process without the process noticing.
• Loading these registers must be privileged, or the protection is meaningless.
• One pair per process forces a single contiguous region, which causes external fragmentation and blocks sharing, growth, and partial residency.

🧪 Practice

1. Given base = 0x20000 and limit = 0x8000, state the physical address or the fault for logical 0x0, 0x7FFF, 0x8000, and 0x1234.
2. Extend the scheme to allow two processes to share a read-only library. What minimum hardware would you need to add, and what does that tell you about why segmentation was invented?
3. Interview-style: "The limit register holds a length, not the highest legal address. Why is that the better choice?" Hint: write out both versions of the comparison and consider a process with a zero-length region, plus how each version behaves at the top of the address space.

Dynamic Loading and Linking

Theory

Two independent techniques share the word "dynamic", and both exist to stop memory being filled with code that is never executed.

Dynamic loading defers bringing a routine into memory until it is first called. The program starts with only its main body resident. Each call goes through a stub; the first time the stub runs, it loads the routine, patches itself to point at the real code, and jumps there. Subsequent calls cost nothing extra. The payoff is largest exactly where you would hope: error handlers, obscure features, and format converters that a typical run never touches occupy no memory at all. Dynamic loading needs no OS support — it is a library/linker technique — though the OS usually provides a better version of it via demand paging (Chapter 8), which achieves the same effect at page granularity, automatically, for all code.

Dynamic linking defers the binding of a library to load time or run time rather than link time. With static linking, the linker copies the library's code into every executable that uses it. Fifty programs using printf means fifty copies on disk and, if they run together, fifty copies in memory. With dynamic linking, the executable records only a reference: "I need libc.so.6". At load time the dynamic linker (ld.so) maps that library into the process's address space — and because the library's code pages are identical for every process, the OS maps the same physical frames into all of them. One copy of printf in RAM serves every process on the system.

The mechanism requires execution-time binding and indirection. Since the library may land at a different address in each process, calls into it cannot be hard-coded. Instead:

• The GOT (Global Offset Table) holds the resolved addresses of external symbols, filled in by the dynamic linker.
• The PLT (Procedure Linkage Table) holds a small stub per function; the first call goes through the dynamic linker and updates the GOT ("lazy binding"), later calls jump straight through it.

The costs are real: an extra indirection per cross-library call, startup work to resolve symbols, and the versioning problem — upgrade a shared library and every dependent program's behaviour changes at once. That is the fix (one security patch protects everything) and the hazard ("DLL hell") in the same property. Programs can also link explicitly at run time with dlopen/dlsym, which is how plugin systems work.

Example

   STATIC vs DYNAMIC LINKING, IN MEMORY

   STATIC                                DYNAMIC
   proc A [ code | libc copy ]           proc A [ code ]---\
   proc B [ code | libc copy ]           proc B [ code ]----> [ ONE libc,
   proc C [ code | libc copy ]           proc C [ code ]---/    shared frames ]

   3 copies on disk and in RAM           1 copy, mapped 3 times
   patch = rebuild all 3                 patch = replace one file

   A CALL TO printf UNDER DYNAMIC LINKING (lazy binding)

   first call:  call printf@PLT --> PLT stub --> ld.so resolves symbol
                                                 writes address into GOT
                                                 jumps to real printf
   later calls: call printf@PLT --> PLT stub --> jmp *GOT[n] --> real printf
                                                 (one extra indirection)

/* Explicit dynamic linking: loading code the program was not linked against.
   This is dynamic LOADING and LINKING at once, and it is how plugins work.
   Build with: gcc main.c -ldl */
#include <dlfcn.h>
#include <stdio.h>

int main(void) {
    void *h = dlopen("./plugin.so", RTLD_NOW);   /* map it in NOW           */
    if (!h) { fprintf(stderr, "%s\n", dlerror()); return 1; }

    /* Symbol -> address. The cast is required: dlsym returns void*.        */
    double (*area)(double) = dlsym(h, "area");
    if (!area) { fprintf(stderr, "%s\n", dlerror()); return 1; }

    printf("%f\n", area(2.0));   /* code that did not exist at link time */
    dlclose(h);                  /* unmap; frames freed if last user      */
    return 0;
}

# See the difference concretely.
gcc  hello.c -o hello_dyn            # default: dynamic
gcc  hello.c -o hello_static -static # everything copied in
ls -l hello_dyn hello_static
# -rwxr-xr-x  16000    hello_dyn      <- references libc
# -rwxr-xr-x  900000   hello_static   <- contains libc

ldd hello_dyn                        # what will be mapped at load time
# libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f2a...)

# Prove the sharing: run many copies, then compare RSS (per-process pages,
# shared frames counted in each) with PSS (shared frames divided among users).
grep -E '^(Rss|Pss):' /proc/self/smaps_rollup

Key takeaways

• Dynamic loading brings a routine into memory on first call; unused code costs nothing. It needs no OS support, and demand paging largely subsumes it.
• Dynamic linking binds libraries at load or run time, so one physical copy of a library serves every process that maps it.
• It requires position-independent code plus indirection through the GOT/PLT, paid as one extra jump per cross-library call.
• One shared copy means one place to patch — the same property that makes a bad library upgrade break every dependent program.

🧪 Practice

1. A system runs 200 processes, each using a 2 MB shared library. Compute the physical memory used with static versus dynamic linking, and state what assumption about the library's code makes the sharing safe.
2. Compare ldd output and binary size for a statically and dynamically linked build of the same program. Then explain why a container image might deliberately choose static linking despite the memory cost.
3. Interview-style: "Lazy binding resolves each symbol on first use. Why would a security-sensitive deployment set LD_BIND_NOW=1 and make the GOT read-only?" Hint: think about what a writable table of function pointers offers an attacker who already has an arbitrary-write primitive.

Swapping

Theory

Sometimes the processes you want to run need more memory than you have. Swapping is the blunt answer: move a process's memory out to a backing store to free space, and bring it back later.

In standard (whole-process) swapping, an entire process image is written to a dedicated area of disk and its frames are released. The process is swapped out; it cannot run at all in that state. Later the OS swaps it in — to any free region, since execution-time binding makes the new location irrelevant — and it resumes as if nothing happened.

The economics are dominated by transfer time, not by anything clever. A 100 MB process on a device delivering 500 MB/s takes 200 ms to write out and 200 ms to read back: 400 ms of pure overhead, during which nothing useful runs for that process. Compare that to a context switch of a few microseconds and the conclusion is unavoidable — whole-process swapping is a heavyweight tool, appropriate only for relieving genuine memory pressure, never for ordinary multiprogramming. Two consequences follow: swap only what is actually resident (transfer time is proportional to memory used, not memory allocated), and never swap a process with pending asynchronous I/O, since the device may DMA into frames that now belong to someone else.

For this reason no modern general-purpose system does standard swapping. Instead they use paging-based swapping: individual pages, not whole processes, are moved out — usually as page-out driven by memory pressure, with pages brought back one at a time on demand (Chapter 8). The granularity changes the economics completely: the unit is 4 KB, not 100 MB, and the process keeps running throughout. The term "swapping" survives in names (swapon, "swap partition", kswapd) even though the mechanism is paging.

Mobile systems make a different trade. iOS has no swap file at all: flash has limited write endurance and modest random-write throughput, so instead of swapping, the OS asks applications to release memory voluntarily and terminates those that will not. Android historically behaved similarly, and both now compress pages in RAM (zram, "compressed memory") as a middle path — cheaper than writing to flash, slower than not paging at all.

Example

   STANDARD SWAPPING: WHOLE PROCESS, DISK ROUND TRIP

   Main memory                       Backing store (swap area)
   +-------------+                   +---------------------+
   |    OS       |                   |                     |
   +-------------+   swap out  P1    |   [ P1 image ]      |
   | process P1  | ================> |                     |
   +-------------+                   |                     |
   | process P2  | <================ |   [ P2 image ]      |
   +-------------+   swap in   P2    +---------------------+

   COST MODEL (transfer dominates; seek/latency is noise by comparison)

     resident size 100 MB, device 500 MB/s
     out : 100 / 500 = 0.200 s
     in  : 100 / 500 = 0.200 s
     total 0.400 s of dead time  ->  ~1000x a normal context switch

   PAGING-BASED SWAPPING: 4 KB AT A TIME, PROCESS KEEPS RUNNING
     evict one page: 4 KB / 500 MB/s = ~8 us, and only if it is dirty

# Why swapping is sized by RESIDENT memory, not allocated memory --
# and why the decision is made on a rate, not on a snapshot.

def swap_time_ms(resident_mb, device_mb_s):
    return (resident_mb / device_mb_s) * 1000

for dev, speed in [("HDD", 120), ("SATA SSD", 500), ("NVMe", 3000)]:
    out_in = 2 * swap_time_ms(100, speed)      # round trip for 100 MB
    print(f"{dev:9} 100 MB round trip: {out_in:7.1f} ms")
# HDD       100 MB round trip:  1666.7 ms
# SATA SSD  100 MB round trip:   400.0 ms
# NVMe      100 MB round trip:    66.7 ms
# Faster devices shrink the penalty but never make it comparable to RAM
# (~100 ns): even NVMe is roughly a 100,000x slowdown per access.

# Swap on a real system.
swapon --show
# NAME      TYPE      SIZE USED PRIO
# /dev/sda2 partition   8G 1.2G   -2

free -h                       # the Swap row is the pressure indicator
vmstat 1 5                    # si/so columns: pages swapped in/out per second
#  si and so consistently > 0 means THRASHING, not healthy use of swap

# Bias the kernel away from swapping anonymous pages (0 = last resort):
sysctl vm.swappiness=10

# Compressed RAM swap: no flash writes, costs CPU instead of I/O.
zramctl

Key takeaways

• Swapping frees memory by moving a process (or, in practice, individual pages) to backing store; execution-time binding lets it return anywhere.
• Cost is dominated by transfer time and is proportional to resident size, making whole-process swapping thousands of times more expensive than a context switch.
• Modern systems swap at page granularity as part of demand paging; the process never stops running.
• A process with pending asynchronous I/O must not be swapped out, or DMA will write into frames that now belong to someone else.
• Mobile systems mostly refuse to swap to flash, using voluntary memory release, termination, or in-RAM compression instead.

🧪 Practice

1. A process has 2 GB allocated but only 300 MB resident. On a 500 MB/s device, compute its swap-out time and explain which figure matters and why.
2. vmstat shows si and so steady at several thousand pages per second while CPU utilisation is 8%. Diagnose the system state and name two fixes at different levels (configuration and workload).
3. Interview-style: "Why does iOS terminate background apps rather than swap them out?" Hint: consider the physical properties of NAND flash and what a user actually notices — a slow app or a restarted one.

<a id="72-contiguous-allocation"></a>

7.2 Contiguous Allocation

If each process must occupy one unbroken run of physical memory, the OS's job becomes a placement problem: which hole to use, what to do with the leftovers, and how to cope when the leftovers become useless. This section works through that problem and arrives at the reason paging exists.

Fixed and Variable Partitions

Theory

Contiguous allocation means dividing physical memory into regions and giving each process exactly one. There are two ways to draw the boundaries.

Fixed partitions (MFT). Split memory into a set number of regions when the system boots — say four regions of 8 MB, 8 MB, 16 MB, and 32 MB. Each holds one process. The bookkeeping is trivial: a table of partitions, each free or occupied, and the degree of multiprogramming is capped by the partition count. Two flaws follow directly. A 9 MB process cannot use an 8 MB partition even if two of them are free and adjacent, and a 9 MB process placed in the 32 MB partition wastes 23 MB that no one else can touch. That wasted space inside an allocation is internal fragmentation.

Variable partitions (MVT). Do not pre-divide. Treat memory as one large hole and carve out exactly what each process requests, when it requests it. When a process exits, its region becomes a hole again, and holes adjacent to other holes are coalesced into one larger hole. The OS maintains a free list of holes with their addresses and sizes.

Variable partitioning eliminates internal fragmentation — you get exactly what you asked for — but introduces a worse problem. Over time, allocation and release cut memory into an alternating pattern of used regions and small holes. The total free space can be large while no single hole is big enough for the next request. That is external fragmentation, and it is the defining failure of contiguous allocation.

The analogy is a car park. Fixed partitions are painted bays: a motorbike in a truck bay wastes the bay, and a truck cannot use two motorbike bays. Variable partitioning is an unpainted lot where each vehicle takes exactly its length — until cars come and go and you are left with twenty gaps of 3 metres and a bus that needs 12.

The OS therefore keeps, for each hole, its start and size, and answers three questions on each event: on allocation, which hole to split; on release, which neighbours to merge with; and when nothing fits, whether to compact, swap something out, or refuse.

Example

   FIXED PARTITIONS (MFT)             VARIABLE PARTITIONS (MVT)

   0   +--------------+ OS            0   +--------------+ OS
       +--------------+                   +--------------+
       | P1  6/8 MB   | 2 MB wasted       | P1  6 MB     | exact fit
       +--------------+ (internal)        +--------------+
       | free   8 MB  |                   | P2  9 MB     |
       +--------------+                   +--------------+
       | P2  9/16 MB  | 7 MB wasted       | hole  3 MB   |
       +--------------+                   +--------------+
       | P3  4/32 MB  | 28 MB wasted      | P3  4 MB     |
       +--------------+                   +--------------+
                                          | hole  22 MB  |
   waste is INSIDE partitions             +--------------+
   (internal fragmentation)           waste is BETWEEN them
                                      (external fragmentation)

   HOW HOLES APPEAR AND COALESCE (MVT over time)

   t0  [ P1 ][ P2 ][ P3 ][    free    ]
   t1  [ P1 ][////][ P3 ][    free    ]      P2 exits -> hole
   t2  [ P1 ][ P4 ][ P3 ][    free    ]      P4 (smaller) reuses part
   t3  [ P1 ][ P4 ][//][//][    free  ]      P3 exits: TWO adjacent holes
   t4  [ P1 ][ P4 ][  merged hole     ]      coalescing joins them

# A variable-partition allocator: allocation splits a hole,
# release coalesces with adjacent neighbours.

class MemoryMap:
    def __init__(self, size):
        # Sorted list of (start, size, owner-or-None)
        self.blocks = [(0, size, None)]

    def allocate(self, pid, size):
        for i, (start, sz, owner) in enumerate(self.blocks):
            if owner is None and sz >= size:
                self.blocks[i] = (start, size, pid)
                if sz > size:                        # split: leftover is a hole
                    self.blocks.insert(i + 1, (start + size, sz - size, None))
                return start
        return None                                  # no single hole fits

    def free(self, pid):
        self.blocks = [(s, z, None if o == pid else o) for s, z, o in self.blocks]
        self._coalesce()

    def _coalesce(self):
        merged = []
        for start, size, owner in self.blocks:
            # Merge only with an immediately preceding FREE block.
            if merged and owner is None and merged[-1][2] is None:
                ps, pz, _ = merged.pop()
                merged.append((ps, pz + size, None))
            else:
                merged.append((start, size, owner))
        self.blocks = merged

    def free_total(self):
        return sum(z for _, z, o in self.blocks if o is None)

    def largest_hole(self):
        return max((z for _, z, o in self.blocks if o is None), default=0)

m = MemoryMap(100)
for pid, sz in [("P1", 20), ("P2", 30), ("P3", 20)]:
    m.allocate(pid, sz)
m.free("P2")
print(m.free_total(), m.largest_hole())   # 60 30 -> 60 free, but max run is 30
print(m.allocate("P4", 40))               # None: fails despite 60 MB free

Key takeaways

• Contiguous allocation gives each process exactly one unbroken physical region.
• Fixed partitions are simple and bound the degree of multiprogramming, but waste whatever a process does not use inside its partition (internal fragmentation).
• Variable partitions fit exactly, but repeated allocation and release scatter free space into unusable holes (external fragmentation).
• The allocator's core operations are split (on allocate) and coalesce (on free); coalescing is what keeps the free list from degenerating.

🧪 Practice

1. Memory is 256 MB with the OS taking 32 MB. Processes of 60, 40, and 80 MB arrive and then the 40 MB one exits. Draw the memory map, list the holes, and state whether a new 50 MB process fits.
2. Modify the MemoryMap class above so free also merges with the following free block, and construct a sequence where the current version leaves two adjacent holes unmerged.
3. Interview-style: "Fixed partitions waste memory inside allocations, variable partitions waste it between them. Which is worse?" Hint: ask which kind of waste can be recovered without moving anything, and which requires copying live data.

First-Fit, Best-Fit, Worst-Fit

Theory

When several holes can satisfy a request, the allocator must choose. The three classical strategies differ only in that choice, but they produce measurably different fragmentation.

First-fit. Scan the free list from the start and take the first hole large enough. It is the fastest to decide, because it stops as soon as it succeeds rather than examining every hole. A refinement, next-fit, resumes scanning where the last search ended, spreading allocations out instead of hammering the low end of memory.

Best-fit. Examine every hole and take the smallest one that fits. The intuition — waste as little as possible — is appealing, and it does leave the largest holes intact for large future requests. The flaw is what it leaves behind: the leftover from the tightest fit is by construction the smallest possible sliver, and slivers are exactly the fragments too small ever to be used again. Best-fit therefore manufactures fragmentation while trying to avoid it.

Worst-fit. Take the largest hole. The reasoning is the mirror image: leave a big, still-usable remainder rather than a sliver. In practice it performs the worst of the three, because it destroys the large holes needed for large allocations.

Simulation studies since the 1960s consistently show first-fit and best-fit outperforming worst-fit, with first-fit generally faster and comparable in space efficiency. That result is worth internalising: the greedy-looking heuristic (best-fit) is not the best one, and the cheap heuristic wins.

None of them solves the underlying problem. The 50-percent rule (Knuth) says that with first-fit at steady state, for every N allocated blocks about 0.5N blocks are lost to fragmentation — roughly one third of memory unusable. No placement policy escapes this, because the cause is contiguity itself, not the choice of hole.

Real allocators keep the vocabulary but change the data structures: glibc malloc uses size-segregated bins (approximating best-fit in O(1)), buddy allocators split and merge power-of-two blocks so coalescing is a single address XOR, and slab allocators sidestep the problem by keeping caches of same-sized objects.

Example

   ONE REQUEST, THREE DECISIONS

   Free list (in address order):
     H1: 100 KB    H2: 500 KB    H3: 200 KB    H4: 300 KB

   Request: 212 KB

   first-fit -> H2 (first that fits)      leftover 288 KB   scanned 2 holes
   best-fit  -> H4 (smallest that fits)   leftover  88 KB   scanned 4 holes
   worst-fit -> H2 (largest)              leftover 288 KB   scanned 4 holes

   WHY BEST-FIT BACKFIRES, TWO REQUESTS LATER

   after best-fit:  100 | 500 | 200 | 88     <- 88 KB is likely dead space
   after first-fit: 100 | 288 | 200 | 300    <- every hole still usable

# The three policies over the same request stream, scored on outcome
# rather than on intuition.

def allocate(holes, size, policy):
    """holes: list of sizes. Returns (index, holes-after) or (None, holes)."""
    candidates = [(i, h) for i, h in enumerate(holes) if h >= size]
    if not candidates:
        return None, holes
    if policy == "first":
        i, _ = candidates[0]                       # stops at the first match
    elif policy == "best":
        i, _ = min(candidates, key=lambda c: c[1])  # smallest sufficient
    else:  # worst
        i, _ = max(candidates, key=lambda c: c[1])  # largest available
    out = holes[:]
    out[i] = holes[i] - size                       # leftover stays as a hole
    return i, out

requests = [212, 417, 112, 426]
for policy in ("first", "best", "worst"):
    holes, failures = [100, 500, 200, 300], 0
    for r in requests:
        idx, holes = allocate(holes, r, policy)
        if idx is None:
            failures += 1
    print(f"{policy:6} leftovers={holes} failures={failures}")
# first  leftovers=[100, 288, 88, 300] failures=1
# best   leftovers=[100, 83, 88, 0]    failures=1
# worst  leftovers=[100, 71, 200, 0]   failures=1
# Note best-fit's 83/88 KB slivers: small, numerous, and effectively dead.

Policy	Search cost	Leftover shape	Typical result
First-fit	Stops early; fastest	Varied	Best overall in practice
Next-fit	Fastest; spreads load	Varied	Slightly worse than first-fit
Best-fit	Scans whole list	Minimal slivers	Comparable space, slower, sliver-prone
Worst-fit	Scans whole list	Large remainders	Worst: destroys big holes

Key takeaways

• All three policies answer one question: which of the sufficient holes to use.
• First-fit is fastest and, empirically, no worse in space than best-fit; worst-fit loses on both counts.
• Best-fit's leftovers are the smallest possible fragments, so it creates the unusable slivers it was trying to avoid.
• The 50-percent rule: roughly one third of memory is lost to external fragmentation regardless of policy — the problem is contiguity, not placement.

🧪 Practice

1. Holes are 300, 600, 350, 200, 750, 125 KB (address order). Place requests of 115, 500, 358, and 200 KB under each of first-fit, best-fit, and worst-fit. State which requests fail under which policy.
2. Extend the simulator above with next-fit (resume scanning from the previous position) and compare its failure count over a random request stream of 200 operations.
3. Interview-style: "glibc malloc uses size-segregated bins. Which classical policy does that approximate, and what does the bin structure fix about it?" Hint: the criticism of that policy was the cost of scanning; think about what a per-size-class list changes.

Internal Fragmentation

Theory

Internal fragmentation is memory that has been allocated to a process but is not used by it, and cannot be given to anyone else because it lies inside someone else's allocation.

It exists because allocators do not hand out arbitrary byte counts. They round up, for three reasons:

1. Alignment. Hardware requires (or strongly prefers) that objects sit at addresses that are multiples of their size. Allocators therefore round every request up to at least 8 or 16 bytes of alignment.
2. Fixed granularity. Fixed partitions allocate a whole partition; paging allocates a whole page frame; file systems allocate a whole block. Ask for one byte more than a unit and you consume two units.
3. Metadata and bin sizes. Real allocators store a header with each block and round sizes to bin boundaries, so a 33-byte request may consume 48 or 64 bytes.

Crucially, internal fragmentation is predictable and bounded, which makes it the tamer of the two fragmentation types. With a unit size U and requests independent of U, the expected waste is about U/2 per allocation. You can compute it in advance, and you control it by choosing U.

That choice is the classic tension. Small units mean little internal waste but many units to track — more page-table entries, more metadata, more allocator work. Large units mean cheap bookkeeping and fewer TLB entries but more waste per allocation. A 4 KB page wastes on average 2 KB per region; a 2 MB huge page wastes on average 1 MB per region, which is exactly why huge pages are used for large contiguous heaps and not for small mappings.

Note the sharpest case: a process needing n·U + 1 bytes consumes (n+1)·U, wasting almost a whole unit. This is why a file of 1 byte still occupies a full 4 KB block, and why storing millions of tiny files wastes enormous space.

Example

   INTERNAL FRAGMENTATION AT THREE GRANULARITIES

   Request: 5000 bytes

   4 KB pages :  |####|####|#...|          2 pages = 8192 B, waste 3192 B
   8 KB blocks:  |########|                1 block = 8192 B, waste 3192 B
   2 MB huge  :  |################...|     1 page  = 2097152 B, waste ~2.09 MB

   THE UNIT/WASTE TRADE-OFF

   unit size   avg waste per alloc   entries for 1 GB   TLB reach (64 entries)
   ---------   -------------------   ----------------   ----------------------
   4 KB        2 KB                  262144             256 KB
   2 MB        1 MB                  512                128 MB
   1 GB        512 MB                1                  64 GB

/* Internal fragmentation you can measure. malloc_usable_size reports what
   the allocator actually reserved, which is >= what you asked for. */
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

int main(void) {
    size_t sizes[] = {1, 8, 17, 24, 25, 33, 100, 4096};
    size_t asked = 0, given = 0;

    for (int i = 0; i < 8; i++) {
        void *p = malloc(sizes[i]);
        size_t real = malloc_usable_size(p);   /* rounded to a bin boundary */
        printf("asked %5zu  got %5zu  wasted %4zu\n",
               sizes[i], real, real - sizes[i]);
        asked += sizes[i]; given += real;
        free(p);
    }
    printf("overhead: %.1f%%\n", 100.0 * (given - asked) / asked);
    return 0;
}
/* asked     1  got    24  wasted   23     <- header + minimum bin
   asked    17  got    24  wasted    7
   asked    25  got    40  wasted   15
   asked  4096  got  4104  wasted    8 */

# Choosing a page size is choosing an expected waste. Model it directly.
def expected_waste(region_sizes, unit):
    total = sum(-(-s // unit) * unit - s for s in region_sizes)   # ceil-div
    return total

regions = [1024, 5000, 65536, 100, 2_000_000]          # a mixed workload
for unit, name in [(4096, "4 KB"), (2 << 20, "2 MB")]:
    print(f"{name}: wasted {expected_waste(regions, unit):,} bytes")
# 4 KB: wasted 8,436 bytes
# 2 MB: wasted 6,225,352 bytes   <- huge pages are wrong for small mappings

Key takeaways

• Internal fragmentation is unused space inside an allocated unit; no other process can use it.
• It comes from rounding up: alignment, fixed granularity (partition, page, block), and allocator metadata.
• Expected waste is about half a unit per allocation, so it is bounded and predictable — unlike external fragmentation.
• Unit size is the control knob: larger units cut bookkeeping and improve TLB reach but multiply waste per allocation.

🧪 Practice

1. A file system uses 4 KB blocks. Compute the space consumed and the waste for 10,000 files averaging 1.5 KB. Then repeat for 64 KB blocks and state what the file system gains in exchange.
2. Run the C program above on your machine and record where the bin boundaries fall. Explain why malloc(1) does not return 1 usable byte.
3. Interview-style: "Transparent huge pages sometimes make a program slower and fatter. Why?" Hint: consider what happens when the OS backs a sparsely-touched 2 MB region with a single huge page, and how much of it is actually resident.

External Fragmentation

Theory

External fragmentation is free memory that cannot be used because it is scattered into pieces, none large enough for the pending request. The memory is available, and it is unusable — which makes it more insidious than internal fragmentation, because the totals look healthy right up until an allocation fails.

The mechanism is simple. Processes of differing sizes are allocated and released in an order unrelated to their sizes. Each release creates a hole where a process used to be; each allocation splits a hole and leaves a remainder. Over time the number of holes grows and their average size shrinks. Eventually you have plenty of free bytes and no free run.

Knuth's 50-percent rule quantifies the steady state for first-fit: if N blocks are allocated, roughly 0.5N blocks are lost to holes, meaning about one third of memory is unusable. This is not a bug in the allocator; it is the equilibrium behaviour of splitting and coalescing under mixed sizes.

Three responses exist, and it is worth being clear that only one is a real solution:

• Compaction — move live data to squeeze holes together. Expensive, and impossible unless binding is at execution time (next topic).
• Better placement policies — reduce the constant factor, never the phenomenon.
• Abandon contiguity — let a process's memory be scattered in fixed-size units. This is paging, and it eliminates external fragmentation entirely, at the cost of some internal fragmentation and a translation table.

The last is why Section 7.3 exists. It is a rare case in systems design where a problem is not mitigated but structurally deleted: if every free unit is interchangeable and every request is a whole number of units, "no hole is big enough" cannot occur.

External fragmentation has not disappeared from modern systems, though. It reappears wherever contiguity is still required: physical memory for DMA buffers that need contiguous frames, huge-page allocation (a 2 MB huge page needs 512 contiguous, aligned free frames), and long-running heaps in user space. Linux's compact_memory and the buddy allocator's merging exist precisely to fight it.

Example

   EXTERNAL FRAGMENTATION DEVELOPING

   t0  [ 100 free                                        ]
   t1  [P1 20][P2 30][P3 20][ 30 free                    ]
   t2  [P1 20][//30//][P3 20][ 30 free                   ]   P2 exits
   t3  [P1 20][P4 10][/20/][P3 20][ 30 free              ]   P4 uses part
   t4  [P1 20][P4 10][/20/][//20//][ 30 free             ]   P3 exits

       free total  = 70 units
       largest run = 30 units
       request for 40 units FAILS with 70 units free

   THE SHAPE OF THE PROBLEM

     usable free memory  =  largest hole,  NOT  sum of holes

# Simulating the 50-percent rule: random sizes, random lifetimes, first-fit.
import random

def simulate(mem=1_000_000, rounds=20_000, seed=7):
    random.seed(seed)
    blocks = [(0, mem, None)]                       # (start, size, owner)
    live, next_id = [], 0

    def first_fit(size, owner):
        for i, (s, z, o) in enumerate(blocks):
            if o is None and z >= size:
                blocks[i] = (s, size, owner)
                if z > size:
                    blocks.insert(i + 1, (s + size, z - size, None))
                return True
        return False

    def coalesce():
        i = 0
        while i < len(blocks) - 1:
            (s1, z1, o1), (s2, z2, o2) = blocks[i], blocks[i + 1]
            if o1 is None and o2 is None:
                blocks[i:i + 2] = [(s1, z1 + z2, None)]   # merge neighbours
            else:
                i += 1

    for _ in range(rounds):
        if live and random.random() < 0.5:                 # free something
            victim = live.pop(random.randrange(len(live)))
            for i, (s, z, o) in enumerate(blocks):
                if o == victim:
                    blocks[i] = (s, z, None)
            coalesce()
        else:                                              # allocate something
            size = random.randint(1000, 20_000)
            next_id += 1
            if first_fit(size, next_id):
                live.append(next_id)

    free = sum(z for _, z, o in blocks if o is None)
    largest = max((z for _, z, o in blocks if o is None), default=0)
    holes = sum(1 for _, _, o in blocks if o is None)
    return free, largest, holes

free, largest, holes = simulate()
print(f"free={free:,}  largest hole={largest:,}  holes={holes}")
print(f"unusable for a 100 KB request: {free - largest:,} bytes")
# Typical: tens of holes, largest hole a small fraction of total free space.

# External fragmentation of PHYSICAL memory on Linux: buddy-allocator
# free counts per order (order n = 2^n contiguous pages).
cat /proc/buddyinfo
# Node 0, zone Normal  4812  2201  980  310  88  12  3  0  0  0  0
#                       ^4KB              ^64KB          ^2MB and up
# Trailing zeros at high orders = no huge page can be allocated,
# even if the low-order counts show gigabytes free.

sysctl -w vm.compact_memory=1     # ask the kernel to compact physical memory

Key takeaways

• External fragmentation is free memory made unusable by being scattered; the metric that matters is the largest hole, not total free space.
• First-fit at steady state loses roughly a third of memory (the 50-percent rule); no placement policy avoids it.
• Compaction mitigates it; only abandoning contiguity (paging) eliminates it.
• It persists in modern systems wherever contiguity is still required: DMA buffers, huge pages, and user-space heaps.

🧪 Practice

1. Memory holds allocations and holes as follows (KB): [P1 40][hole 20][P2 60][hole 30][P3 10][hole 25]. State total free, largest hole, and the largest request that can be satisfied. Then show that compaction changes the answer.
2. Run cat /proc/buddyinfo on a machine that has been up for a while and interpret the high-order columns. What would you expect immediately after boot, and why?
3. Interview-style: "A long-running server's RSS keeps growing even though it frees everything it allocates. Is this a leak?" Hint: distinguish memory the program has lost track of from memory the allocator holds but cannot return to the OS, and think about what free() can do with a hole in the middle of the heap.

Compaction

Theory

If external fragmentation is caused by holes being in the wrong places, compaction is the direct remedy: move the live allocations so that all the free space ends up in one contiguous run.

The prerequisite is absolute. Compaction is only possible when binding happens at execution time. If a process's addresses were fixed at compile or load time, moving its bytes would invalidate every pointer inside it — return addresses on the stack, pointers in its data structures, jump targets. With execution-time binding, moving a process is copy-the-bytes plus update-the-base-register, and the process cannot observe the change.

The cost is dominated by copying. Compaction is memory-bandwidth-bound: at 10 GB/s, compacting 4 GB of live data takes roughly 400 ms — during which affected processes must be stopped, because a process must not read memory that is halfway through being moved. That "stop the world" property is what makes compaction a last resort rather than routine maintenance.

There is also a choice of how much to move. Full compaction pushes everything to one end and yields one maximal hole, but copies the most data. Partial compaction moves only enough to open a hole of the required size — often far cheaper, since moving one small process may join two adjacent holes. Choosing the minimal-cost move is itself a small optimisation problem, and simple heuristics (move the smallest process adjacent to the largest hole) capture most of the benefit.

The idea did not die with contiguous allocation. Compacting garbage collectors (Java's G1 and ZGC, Go's allocator to a lesser degree) do exactly this for heap objects, and use read/write barriers or brief pauses to keep references valid while objects move. Linux's memory compaction relocates physical pages to assemble contiguous runs for huge pages. Both are the same idea one level up: relocation is possible only because there is an indirection (an object reference, a page table entry) that can be updated.

Example

   COMPACTION: THREE VALID OUTCOMES, DIFFERENT COSTS

   Before                                       free = 70, largest = 30
   [ P1 20 ][/10/][ P2 30 ][/20/][ P3 20 ][/40/]

   (a) FULL COMPACTION -- move P2 and P3 down
   [ P1 20 ][ P2 30 ][ P3 20 ][///// 70 /////]     copied: 50 units

   (b) PARTIAL -- move only P2 down
   [ P1 20 ][ P2 30 ][//// 20+20 ////][P3][/40/]   copied: 30 units
       (joins two holes into 40 -- enough for a 40-unit request)

   (c) PARTIAL -- move only P3 up
   [ P1 20 ][/10/][ P2 30 ][//// 60 ////][ P3 20 ] copied: 20 units, hole 60

   Cheapest move that satisfies the request wins. (c) copies least.

   WHAT MUST HAPPEN ATOMICALLY PER MOVED PROCESS
     1. suspend process        2. copy bytes to new location
     3. update base register   4. resume  (process observes nothing)

# Cost-aware compaction: pick the single move that opens a big enough hole
# for the least copying.

def cheapest_move(layout, needed):
    """layout: list of (name-or-None, size), None = hole. Returns best plan."""
    best = None
    for i, (name, size) in enumerate(layout):
        if name is None:
            continue
        # Moving this process merges the holes on either side of it.
        left  = layout[i - 1][1] if i > 0 and layout[i - 1][0] is None else 0
        right = layout[i + 1][1] if i + 1 < len(layout) and layout[i + 1][0] is None else 0
        merged = left + right
        if merged >= needed:                        # this single move suffices
            if best is None or size < best[1]:      # cost == bytes copied
                best = (name, size, merged)
    return best

layout = [("P1", 20), (None, 10), ("P2", 30), (None, 20), ("P3", 20), (None, 40)]
print(cheapest_move(layout, 40))
# ('P3', 20, 60)  -> move 20 units, open a 60-unit hole. Full compaction
#                    would have copied 50 units for the same effect.

def compaction_ms(live_bytes, bandwidth_gbs=10):
    # Copying is read + write, so effective bandwidth is roughly halved.
    return (live_bytes / (bandwidth_gbs * 1e9 / 2)) * 1000

print(f"{compaction_ms(4 * 2**30):.0f} ms to compact 4 GB")   # ~859 ms

Key takeaways

• Compaction relocates live allocations to merge scattered holes into one usable run.
• It requires execution-time binding; with earlier binding, moving a process breaks every address inside it.
• Cost is memory-bandwidth-bound and requires stopping the affected processes, so it is a last resort.
• Partial compaction — the cheapest single move that opens a sufficient hole — usually beats full compaction.
• The same idea survives in compacting garbage collectors and in kernel page compaction for huge pages.

🧪 Practice

1. For the layout [P1 100][hole 60][P2 200][hole 40][P3 150][hole 90], find the cheapest single move that satisfies a 130-unit request, and compare its copy cost to full compaction.
2. A system has 8 GB of live data and 12 GB/s of memory bandwidth. Estimate the compaction pause and argue whether it is acceptable for (a) a batch analytics job, (b) a game rendering at 60 fps.
3. Interview-style: "Paging removes the need for compaction of process memory, yet Linux still has a memory compaction daemon. Why?" Hint: paging makes virtual contiguity unnecessary, but ask what a 2 MB huge page or a DMA buffer requires of physical frames.

<a id="73-paging"></a>

7.3 Paging

Paging is the answer to external fragmentation: stop requiring that a process's memory be contiguous in physical memory, and the problem of "no hole is big enough" ceases to exist. This section builds the scheme from its address arithmetic up through the hardware and data structures that make it fast enough to use.

Pages and Frames

Theory

The core idea is a change of unit. Divide physical memory into fixed-size frames and the logical address space into pages of exactly the same size — typically 4 KB. Now any page can go in any frame. A process's pages may be scattered arbitrarily across physical memory, and because all frames are interchangeable and every request is a whole number of pages, an allocation fails only when no frames remain, never because the free ones are in the wrong places.

External fragmentation is gone. What remains is internal fragmentation in the last page of each region — on average half a page, which for 4 KB pages is 2 KB per region. That is a bargain, and it is a deliberate trade: a bounded, predictable waste replaces an unbounded, unpredictable one.

The address arithmetic is what makes it cheap. Choose the page size to be a power of two, 2^n. Then a logical address splits with no arithmetic at all — just wire-splitting in hardware:

• The low n bits are the offset within the page.
• The remaining high bits are the page number.

Translation replaces the page number with a frame number and leaves the offset untouched. For a 32-bit address with 4 KB pages: 12 offset bits, 20 page-number bits, so 2^20 pages per process and up to 2^20 frames of 4 KB each.

The key insight is that the offset never changes. A page and its frame have the same size and the same alignment, so byte 137 of page 3 is byte 137 of whatever frame holds it. Only the top part of the address is translated.

The analogy is a book split into numbered sheets and a filing cabinet of numbered slots, one sheet per slot. An index says "sheet 3 is in slot 27". To find line 12 of sheet 3, consult the index for the slot, then count 12 lines in. The line number — the offset — is unaffected by which slot the sheet ended up in.

Page size is a genuine trade-off: smaller pages waste less in the last page but need more page-table entries and give the TLB less reach; larger pages do the reverse. 4 KB has been the standard for decades, with 2 MB and 1 GB "huge pages" available for large, densely-used regions.

Example

   LOGICAL ADDRESS SPLIT (32-bit address, 4 KB pages)

    31                    12 11               0
   +------------------------+------------------+
   |   page number  p (20)  |   offset d (12)  |
   +------------------------+------------------+
              |                      |
              | page table           | unchanged
              v                      v
   +------------------------+------------------+
   |   frame number f (20)  |   offset d (12)  |
   +------------------------+------------------+
    31                    12 11               0

   SCATTERED PLACEMENT: THE WHOLE POINT

   Logical (process view)        Page table       Physical memory
   page 0 [ A ]  -------------->  0 -> 5          frame 0 [ D ]
   page 1 [ B ]  -------------->  1 -> 2          frame 1 [   ]
   page 2 [ C ]  -------------->  2 -> 7          frame 2 [ B ]
   page 3 [ D ]  -------------->  3 -> 0          frame 3 [   ]
                                                  frame 4 [   ]
   CONTIGUOUS to the process                      frame 5 [ A ]
   SCATTERED in reality                           frame 6 [   ]
                                                  frame 7 [ C ]

   Any free frame will do -> allocation fails only when frames run out.

# Paging address arithmetic: shifts and masks, no division.
PAGE_BITS = 12                       # 4 KB pages
PAGE_SIZE = 1 << PAGE_BITS
OFFSET_MASK = PAGE_SIZE - 1

def split(addr):
    return addr >> PAGE_BITS, addr & OFFSET_MASK     # (page, offset)

page_table = {0: 5, 1: 2, 2: 7, 3: 0}                # page -> frame

def translate(addr):
    p, d = split(addr)
    if p not in page_table:
        raise MemoryError(f"page fault: page {p}")
    return (page_table[p] << PAGE_BITS) | d          # frame, same offset

for a in (0x0000, 0x1004, 0x2FFF, 0x3ABC):
    p, d = split(a)
    print(f"{a:#07x} -> page {p} offset {d:#05x} -> {translate(a):#07x}")
# 0x00000 -> page 0 offset 0x000 -> 0x05000
# 0x01004 -> page 1 offset 0x004 -> 0x02004    <- offset preserved
# 0x02fff -> page 2 offset 0xfff -> 0x07fff
# 0x03abc -> page 3 offset 0xabc -> 0x00abc

# Page sizes available on this machine.
getconf PAGESIZE                 # 4096
grep Hugepagesize /proc/meminfo  # Hugepagesize: 2048 kB

# Internal fragmentation is real but bounded: compare a process's
# virtual size (VmSize) to its resident size (VmRSS).
grep -E 'VmSize|VmRSS' /proc/self/status

Key takeaways

• Paging fixes external fragmentation by making every allocation unit interchangeable: any page fits any frame.
• Pages and frames are the same power-of-two size, so an address splits into page number and offset by bit position alone.
• Translation replaces the page number and preserves the offset exactly.
• The remaining waste is internal fragmentation in the final page — on average half a page per region.
• Page size trades internal waste against page-table size and TLB reach.

🧪 Practice

1. For a 16-bit logical address space with 1 KB pages, give the number of offset bits, the number of page-number bits, and the page and offset for address 0x2C5A.
2. A process needs 26,000 bytes with 4 KB pages. How many pages, how much internal fragmentation, and what is the answer with 2 MB pages?
3. Interview-style: "Why must page size be a power of two?" Hint: write out what the hardware would have to do to split an address if the page size were 3000 bytes, and compare that to wiring bits to two separate buses.

Page Tables

Theory

The page table is the data structure that maps page numbers to frame numbers. It is per-process — that is what gives each process its own address space — and it is what the OS installs in the MMU on every context switch.

The simplest form is a flat array indexed by page number, each entry holding a frame number plus status bits. The hardware needs one register, the page-table base register (PTBR; CR3 on x86-64), pointing at the current table's physical address. Context switching the address space is then a single write to that register.

Two problems follow immediately, and the rest of this section is about solving them.

Problem 1: speed. The page table lives in memory. So every logical memory reference needs two physical accesses: one to read the page-table entry, one to read the data. Memory access is effectively halved — a 100% slowdown on the machine's most frequent operation. The fix is the TLB, next topic.

Problem 2: size. A flat table has one entry per possible page, whether or not the page is used. For a 32-bit space with 4 KB pages: 2^20 entries × 4 bytes = 4 MB of page table per process. With 100 processes that is 400 MB of tables for programs that may each be using 2 MB of memory. In 64-bit it is absurd: with a 48-bit address space, 2^36 entries × 8 bytes = 512 GB per process. A flat table is simply not an option. The fixes are hierarchical, hashed, and inverted tables, covered below.

A page-table entry (PTE) is not just a frame number. On x86-64 it is 64 bits: the frame number plus present, writable, user/supervisor, write-through, cache-disable, accessed, dirty, page-size, global, and no-execute bits. Those bits are how protection, replacement, and sharing are all implemented — they are covered under memory protection bits later.

One subtlety worth noting: page tables themselves are stored in physical frames, and the PTBR holds a physical address. It must, or translating an address would require translating an address, without end. The kernel's own mappings are the base case of the recursion.

Example

   FLAT PAGE TABLE AND ITS TWO PROBLEMS

   CPU  logical addr [ p | d ]
              |
              +--> PTBR + p*4 ------> MEMORY ACCESS 1: read PTE
              |                                |
              |                                v  frame f
              +--------------------------> [ f | d ] --> MEMORY ACCESS 2: data

   Every reference costs two: ~100 ns becomes ~200 ns.

   SIZE OF A FLAT TABLE, PER PROCESS

   Address bits   Page size   Entries      Entry size   Table size
   ------------   ---------   ----------   ----------   -------------
   32             4 KB        2^20         4 B          4 MB
   32             4 MB        2^10         4 B          4 KB
   48 (x86-64)    4 KB        2^36         8 B          512 GB   <- impossible
   64             4 KB        2^52         8 B          32 PB    <- absurd

   A 64-BIT PTE (x86-64), THE BITS THAT MATTER

    63  62..52   51 ................ 12   11..9   8  7  6  5   4   3   2  1  0
   +---+-------+------------------------+-------+---+--+--+--+---+---+---+--+--+
   |NX | avail |     frame number       | avail | G |PS| D| A|PCD|PWT|U/S|R/W|P|
   +---+-------+------------------------+-------+---+--+--+--+---+---+---+--+--+
    NX=no-execute  G=global  PS=page size  D=dirty  A=accessed  P=present

/* A page-table entry and the walk a flat scheme performs.
   Compare this to the hierarchical walk in the next topic. */

#define PAGE_SHIFT 12
#define PRESENT    (1UL << 0)
#define WRITABLE   (1UL << 1)
#define USER       (1UL << 2)

typedef unsigned long pte_t;

static pte_t *page_table;                /* PTBR points here (physical) */

unsigned long translate(unsigned long vaddr, int writing) {
    unsigned long p = vaddr >> PAGE_SHIFT;          /* index */
    unsigned long d = vaddr & ((1UL << PAGE_SHIFT) - 1);

    pte_t e = page_table[p];                        /* MEMORY ACCESS 1 */

    if (!(e & PRESENT))                trap(PAGE_FAULT);
    if (writing && !(e & WRITABLE))    trap(PROTECTION_FAULT);

    unsigned long frame = e >> PAGE_SHIFT;          /* strip the flag bits */
    return (frame << PAGE_SHIFT) | d;               /* caller does ACCESS 2 */
}

# Why flat tables do not scale, in one calculation.
def flat_table_bytes(addr_bits, page_kb, entry_bytes=8):
    page_bits = (page_kb * 1024).bit_length() - 1
    return (1 << (addr_bits - page_bits)) * entry_bytes

for bits, pkb in [(32, 4), (32, 4096), (48, 4), (48, 2048), (57, 4)]:
    b = flat_table_bytes(bits, pkb)
    print(f"{bits}-bit, {pkb} KB pages: {b / 2**30:>18,.3f} GiB per process")
# 32-bit,    4 KB pages:              0.008 GiB per process
# 32-bit, 4096 KB pages:              0.000 GiB per process
# 48-bit,    4 KB pages:            512.000 GiB per process   <- fatal
# 48-bit, 2048 KB pages:              1.000 GiB per process
# 57-bit,    4 KB pages:         262144.000 GiB per process

Key takeaways

• The page table maps page numbers to frame numbers and is per-process; the PTBR selects the active one, so a context switch is one register write.
• A flat table doubles the cost of every memory reference (one access for the PTE, one for the data).
• A flat table's size is proportional to the address space, not to memory used — 4 MB per 32-bit process, 512 GB per 48-bit process.
• A PTE carries protection and status bits (present, writable, user, NX, accessed, dirty), not just a frame number.
• Page tables are stored in physical frames and referenced by physical address, to stop translation recursing forever.

🧪 Practice

1. Compute the flat page-table size per process for a 36-bit address space with 8 KB pages and 4-byte entries. Then compute total memory for 50 processes.
2. Given the PTE layout above, write the C expression that extracts the frame number and the one that tests the NX bit, assuming 4 KB pages.
3. Interview-style: "Why does the page-table base register hold a physical address rather than a virtual one?" Hint: trace what the MMU would have to do to translate the address of the structure it needs in order to translate addresses.

Translation Lookaside Buffer

Theory

The page table solves correctness and destroys performance: two memory accesses per reference instead of one. The fix is the observation that programs exhibit locality — over any short interval they touch a small number of distinct pages, over and over. So cache the translations.

The TLB is a small, fully-associative, very fast cache of page-number-to-frame-number mappings, built into the MMU. Typical sizes are 64 to 1536 entries per level, with access latency around one cycle. On a TLB hit, translation is free — the physical address is available in the same cycle the address is generated. On a TLB miss, the hardware (on x86-64 and ARM64) or the OS (on MIPS, SPARC) walks the page table, installs the result in the TLB, and retries.

Because a handful of entries covers the working set of a typical loop, hit rates of 98-99% are routine. The effective access time shows why that is enough:

EAT = hit_ratio × (memory) + miss_ratio × (page_table_walk + memory)

With 100 ns memory, a 99% hit ratio, and a one-access walk: 0.99 × 100 + 0.01 × 200 = 101 ns. A 1% slowdown instead of 100%.

Two design problems arise from having a per-process mapping in a shared cache:

Context switches. The next process has different mappings for the same page numbers. If nothing is done, stale entries would translate incorrectly — a correctness disaster. The naive fix is to flush the whole TLB on every context switch, which is correct but costly: the new process starts cold and pays hundreds of misses. The real fix is an ASID (address-space identifier), a tag stored with each entry, so entries from different processes coexist and only matching-ASID entries can hit. Some entries are marked global (kernel mappings, identical in every process) and survive regardless.

TLB shootdown. On a multiprocessor, each core has its own TLB. If one core changes a page-table entry — unmapping a page, revoking write permission — other cores may still hold the old translation. The kernel must send an inter-processor interrupt to every core that might have it cached and wait for acknowledgement. This is expensive (microseconds), which is why operations like munmap and mprotect are far costlier than they look, and why batching them matters.

Example

   TLB ON THE CRITICAL PATH

                     +-------------------+
   logical [p|d] --->|  TLB (assoc.)     |
                     |  p3 -> f7  ASID 1 |
                     |  p0 -> f5  ASID 1 |--- hit ---> [f|d] (0 extra accesses)
                     |  p1 -> f2  ASID 4 |
                     +---------+---------+
                               | miss
                               v
                     walk page table in memory  (1..4 extra accesses)
                     install entry, retry

   EFFECTIVE ACCESS TIME (memory = 100 ns, walk = 1 access)

   hit ratio   EAT             slowdown vs raw memory
   ---------   -------------   ----------------------
   50%         150 ns          50%
   80%         120 ns          20%
   98%         102 ns           2%
   99.5%       100.5 ns         0.5%

   TLB REACH = entries x page size
     64 x 4 KB   =   256 KB   <- a 1 MB working set thrashes the TLB
     64 x 2 MB   =   128 MB   <- same entries, 512x the coverage

# EAT, and the reach calculation that explains huge pages.
def eat_ns(hit_ratio, mem_ns=100, walk_accesses=1, tlb_ns=0):
    hit  = tlb_ns + mem_ns
    miss = tlb_ns + walk_accesses * mem_ns + mem_ns
    return hit_ratio * hit + (1 - hit_ratio) * miss

for h in (0.5, 0.8, 0.98, 0.995):
    print(f"hit {h:6.1%}  4-level walk: {eat_ns(h, walk_accesses=4):6.1f} ns")
# hit  50.0%  4-level walk:  300.0 ns    <- x86-64 misses cost FOUR accesses
# hit  80.0%  4-level walk:  180.0 ns
# hit  98.0%  4-level walk:  108.0 ns
# hit  99.5%  4-level walk:  102.0 ns

def reach(entries, page_bytes):
    return entries * page_bytes

print(reach(1536, 4096) / 2**20, "MiB with 4 KB pages")     # 6.0 MiB
print(reach(1536, 2 << 20) / 2**30, "GiB with 2 MB pages")  # 3.0 GiB

# Measure TLB behaviour rather than guessing at it.
perf stat -e dTLB-loads,dTLB-load-misses,iTLB-load-misses ./workload
#  1,204,338,201  dTLB-loads
#     31,882,915  dTLB-load-misses   #  2.65% of all dTLB cache accesses
#  A few percent is normal; double digits means the working set exceeds reach.

# Give a large heap huge pages and re-measure: fewer entries, far more reach.
grep -i huge /proc/meminfo
echo always > /sys/kernel/mm/transparent_hugepage/enabled

Key takeaways

• The TLB caches recent page-to-frame translations, making translation free on a hit; locality gives hit rates of 98-99%.
• Effective access time is a weighted average — even a 98% hit ratio keeps the overhead in the low single digits.
• ASIDs tag entries per address space so a context switch need not flush the TLB; global entries hold kernel mappings across switches.
• TLB reach (entries × page size) determines how large a working set can be covered; huge pages multiply reach without more entries.
• On multiprocessors, changing a mapping requires a TLB shootdown — an IPI to every core that may hold the stale entry.

🧪 Practice

1. Memory access is 80 ns, TLB access 2 ns, and the page table is two-level. Compute EAT at hit ratios of 90% and 99%, and state the percentage slowdown for each.
2. A machine has a 512-entry data TLB with 4 KB pages. Compute its reach, and determine the minimum page size needed to cover a 1 GB working set with the same entry count.
3. Interview-style: "Why is munmap on a busy multithreaded process much more expensive than mmap?" Hint: think about which operation must invalidate state that other cores are already holding, and what it costs to reach those cores.

Hierarchical Page Tables

Theory

A flat page table's fatal property is that it is sized by the address space rather than by usage — 2^36 entries for a 48-bit space, almost all of them describing pages that will never exist. The fix is to page the page table itself.

A two-level scheme splits the page number into two parts. The top part indexes an outer page table (a page directory), whose entries point to inner page tables; the bottom part indexes the inner table, which holds the frame number. The win is that inner tables are allocated only for regions of the address space that are actually used. A process using 8 MB of a 4 GB space needs the directory plus a couple of inner tables — a few pages, not 4 MB.

For 32-bit x86 with 4 KB pages, the split is 10 / 10 / 12: 1024 directory entries, each covering 1024 pages of 4 KB (4 MB per directory entry). Each table is exactly one page, which is not a coincidence — it means page tables can themselves be paged and allocated by the ordinary frame allocator.

For 64-bit the same trick is applied more times. x86-64 uses four levels over a 48-bit address (9 / 9 / 9 / 9 / 12): PML4, PDPT, PD, PT, with 512 entries each (512 × 8 bytes = one 4 KB page). Newer chips support a fifth level (LA57) for 57-bit addresses. ARM64 is similar with configurable levels.

The cost is walk depth. A TLB miss on x86-64 requires four memory accesses before the data access — the reason a TLB miss is genuinely expensive and the reason CPUs cache intermediate levels of the walk in dedicated structures (page-walk caches).

The scheme also carries protection and huge-page support elegantly. A directory entry with the page-size bit set terminates the walk early and maps a 2 MB page directly (or a 1 GB page one level up), which is exactly how huge pages are implemented: fewer levels, fewer entries, much greater TLB reach.

The analogy is a library catalogue. A flat table is one card per possible book in a universe of billions. A hierarchical table is: catalogue of floors, each floor's catalogue of rooms, each room's catalogue of shelves. Empty floors need no room catalogues at all, and finding a book takes three lookups instead of one — sparse storage bought with extra indirections.

Example

   TWO-LEVEL (32-bit x86, 4 KB pages): 10 / 10 / 12

    31          22 21          12 11            0
   +-------------+--------------+---------------+
   |   p1 (10)   |   p2 (10)    |   offset (12) |
   +------+------+------+-------+-------+-------+
          |             |               |
          v             |               |
   page directory       |               |
   [0] ---> null        |               |     <- unused 4 MB region:
   [1] ---> inner ------+               |        NO inner table allocated
   [2] ---> null        v               |
   ...             inner table          |
   [1023] -> inner  [0..1023] -> frame -+---> [ frame | offset ]

   FOUR-LEVEL (x86-64, 48-bit VA): 9 / 9 / 9 / 9 / 12

    47      39 38      30 29      21 20      12 11       0
   +---------+----------+----------+----------+----------+
   |  PML4   |   PDPT   |    PD    |    PT    |  offset  |
   +----+----+-----+----+-----+----+-----+----+----------+
        |          |          |          |
     CR3+  ----> table ---> table ---> table ---> frame
     access 1    access 2   access 3   access 4   access 5 = the data

   EARLY TERMINATION = HUGE PAGES
     PD entry with PS=1   -> maps a 2 MB page  (walk stops, offset is 21 bits)
     PDPT entry with PS=1 -> maps a 1 GB page  (offset is 30 bits)

   SPACE FOR A PROCESS USING 8 MB OF A 4 GB SPACE (two-level)
     directory 4 KB + 2 inner tables 8 KB = 12 KB   (flat would be 4 MB)

# A four-level walk, and the space saving that motivates it.

LEVEL_BITS, OFFSET_BITS = 9, 12
IDX_MASK = (1 << LEVEL_BITS) - 1

def indices(vaddr):
    """Split a 48-bit virtual address into 4 table indices + offset."""
    off = vaddr & ((1 << OFFSET_BITS) - 1)
    rest = vaddr >> OFFSET_BITS
    idx = []
    for _ in range(4):
        idx.append(rest & IDX_MASK)     # extract 9 bits per level
        rest >>= LEVEL_BITS
    return list(reversed(idx)), off     # [PML4, PDPT, PD, PT], offset

class Walker:
    def __init__(self):
        self.root, self.tables = {}, 1          # count allocated tables

    def map(self, vaddr, frame):
        idx, _ = indices(vaddr)
        node = self.root
        for level in idx[:-1]:
            if level not in node:               # allocate ONLY on first use
                node[level] = {}
                self.tables += 1
            node = node[level]
        node[idx[-1]] = frame

    def translate(self, vaddr):
        idx, off = indices(vaddr)
        node = self.root
        for level in idx[:-1]:                  # 3 pointer chases...
            node = node.get(level)
            if node is None:
                raise MemoryError("page fault")
        frame = node.get(idx[-1])               # ...then the leaf: 4 accesses
        if frame is None:
            raise MemoryError("page fault")
        return (frame << OFFSET_BITS) | off

w = Walker()
for i in range(2048):                            # map 8 MB at 0x400000
    w.map(0x400000 + i * 4096, 0x1000 + i)
print(w.tables, "tables =", w.tables * 4096, "bytes")
# 7 tables = 28672 bytes   (a flat 48-bit table would be 512 GB)
print(hex(w.translate(0x400abc)))

# Real numbers for the page-table overhead of a live process.
grep VmPTE /proc/self/status         # VmPTE:  76 kB  <- all levels combined

# Watch the walk depth matter: page-walk cycles are a distinct perf event.
perf stat -e dtlb_load_misses.walk_active,dtlb_load_misses.walk_completed ./app

Key takeaways

• Hierarchical tables page the page table, so storage is proportional to address space used, not address space possible.
• Each level is sized to exactly one page, letting page tables be allocated and paged like any other memory.
• x86-64 uses four levels over 48 bits (9/9/9/9/12), with a fifth for 57-bit addresses.
• The cost is walk depth: a TLB miss becomes four memory accesses plus the data access.
• An entry with the page-size bit set terminates the walk early, which is how 2 MB and 1 GB huge pages are implemented.

🧪 Practice

1. For a 32-bit address space with 4 KB pages and a 10/10/12 split, compute the total page-table memory for a process using 12 MB spread over three separate 4 MB-aligned regions.
2. Given the x86-64 split, compute the four indices and the offset for virtual address 0x00007F3A_1B2C_D000.
3. Interview-style: "A four-level walk costs four memory accesses. Why isn't the TLB miss penalty simply four times a memory access in practice?" Hint: the page-table entries are themselves ordinary memory, and there are other caches between the MMU and DRAM — plus dedicated page-walk caches.

Hashed and Inverted Page Tables

Theory

Hierarchical tables scale well when the address space is used in a few dense clusters. They scale badly when it is sparse and wide — many levels of mostly-empty tables — and they scale poorly with process count, since every process pays for its own tree. Two alternative organisations attack this differently.

Hashed page tables. Instead of indexing by page number, hash it. The table has a fixed number of buckets; each bucket holds a chain of entries (page number, frame number, next). Lookup hashes the page number, walks the chain, and compares stored page numbers until one matches. Table size is now chosen by the implementer and is independent of address-space width, which is why this design was used on 64-bit architectures where a tree would be unreasonably deep.

The refinement that makes it practical is clustered page tables: each entry maps a block of consecutive pages (say 16) rather than one. This exploits the fact that mappings come in runs — a memory region is mapped as a range, not page by page — and cuts both entries and chain lengths by an order of magnitude. Clustered tables are effective for sparse address spaces with scattered, run-structured mappings.

Inverted page tables. Turn the question around. Rather than one table per process indexed by page, keep one global table indexed by frame, with one entry per physical frame recording which (process, page) currently occupies it. The size is now fixed by installed RAM — a 16 GB machine with 4 KB frames needs 4M entries, a handful of megabytes total, regardless of how many processes run or how wide their address spaces are. PowerPC, UltraSPARC, and IA-64 used this design.

The price is severe: lookup is now a search. Given (pid, page) you must find the entry containing it, which means scanning — so inverted tables are always paired with a hash table over (pid, page) to make lookup practical, and always paired with a TLB to avoid doing it often. Worse, the structure has one entry per frame and therefore cannot naturally express shared pages: two processes mapping the same frame need two entries for one frame, which the table has no room for. Implementations handle this with side structures or by restricting sharing — a real loss, given how much modern systems depend on sharing.

Scheme	Size scales with	Lookup cost	Sharing	Used by
Flat	Address space, per process	1 access	Easy	Toy/small embedded
Hierarchical	Address space used, per process	Levels (4 on x86-64)	Easy	x86-64, ARM64, RISC-V
Hashed / clustered	Chosen; independent of width	Hash + chain walk	Easy	64-bit PA-RISC, IA-64
Inverted	Physical memory, system-wide	Hash + search	Hard	PowerPC, UltraSPARC

Example

   HASHED PAGE TABLE                     INVERTED PAGE TABLE

   virtual page p                        virtual page p, process pid
        |                                     |
     hash(p)                               hash(pid, p)
        |                                     |
        v                                     v
   +----------+                          +----------+
   | bucket 3 |-> (p=17,f=2) -> (p=91,f=8)| bucket 6 |-> index 4
   +----------+     compare p, follow    +----+-----+
                    chain until match         |
                                              v
                                    +---+-------------------+
   ONE TABLE PER PROCESS            | 0 | pid=2  page=7     |  <- indexed
   Size = implementer's choice      | 1 | pid=5  page=1     |     BY FRAME
                                    | 2 | free              |
                                    | 3 | pid=2  page=8     |
                                    | 4 | pid=9  page=44    |  <- match: frame 4
                                    +---+-------------------+

                                    ONE TABLE FOR THE WHOLE SYSTEM
                                    Size = installed RAM / frame size
                                    Problem: one entry per FRAME means
                                    two processes sharing a frame do not fit.

# Both schemes side by side, with their characteristic costs made visible.

PAGE_BITS = 12

class HashedPageTable:
    def __init__(self, buckets=1024):
        self.buckets = [[] for _ in range(buckets)]

    def map(self, page, frame):
        self.buckets[hash(page) % len(self.buckets)].append((page, frame))

    def translate(self, vaddr):
        page, off = vaddr >> PAGE_BITS, vaddr & ((1 << PAGE_BITS) - 1)
        chain = self.buckets[hash(page) % len(self.buckets)]
        for p, f in chain:                     # cost = chain length
            if p == page:
                return (f << PAGE_BITS) | off
        raise MemoryError("page fault")

class InvertedPageTable:
    def __init__(self, frames):
        self.entries = [None] * frames         # one slot PER FRAME
        self.index = {}                        # (pid,page) -> frame; required

    def map(self, pid, page, frame):
        self.entries[frame] = (pid, page)
        self.index[(pid, page)] = frame        # without this, lookup is O(n)

    def translate(self, pid, vaddr):
        page, off = vaddr >> PAGE_BITS, vaddr & ((1 << PAGE_BITS) - 1)
        frame = self.index.get((pid, page))
        if frame is None:
            raise MemoryError("page fault")
        return (frame << PAGE_BITS) | off

ipt = InvertedPageTable(frames=8)
ipt.map(pid=2, page=7, frame=0)
ipt.map(pid=9, page=44, frame=4)
print(hex(ipt.translate(9, (44 << PAGE_BITS) | 0xABC)))    # 0x4abc

# The sharing problem, concretely: both processes want the SAME frame.
ipt.map(pid=3, page=100, frame=0)      # overwrites entries[0] = (2,7)
print(ipt.entries[0])                  # (3, 100) -- process 2's record is gone

# Why inverted tables were attractive: size, in one comparison.
def hierarchical_total(procs, per_proc_kb=76):
    return procs * per_proc_kb * 1024

def inverted_total(ram_gb, frame_kb=4, entry_bytes=16):
    return (ram_gb * 2**30 // (frame_kb * 1024)) * entry_bytes

print(hierarchical_total(2000) / 2**20, "MiB for 2000 processes")  # 148.4 MiB
print(inverted_total(16) / 2**20, "MiB, fixed regardless of processes")  # 64.0

Key takeaways

• Hashed page tables index by a hash of the page number, decoupling table size from address-space width; clustered variants map runs of pages per entry.
• Inverted page tables keep one system-wide table with one entry per physical frame, so size depends on installed RAM, not on process count or address width.
• Inverted tables turn lookup into a search, requiring an auxiliary hash table and heavy TLB reliance.
• One entry per frame makes shared pages awkward to represent — a serious drawback given how much modern systems share.
• Mainstream 64-bit architectures chose hierarchical tables; these designs are the alternatives that lost, for reasons worth knowing.

🧪 Practice

1. A 32 GB machine uses 4 KB frames and 16-byte inverted-table entries. Compute the table size, and compare it to 500 processes each with a 76 KB hierarchical table.
2. Explain, with a concrete two-process example, why a plain inverted page table cannot represent a shared library mapped by both, and sketch one way an implementation could work around it.
3. Interview-style: "Hashed page tables have unbounded worst-case lookup time. Why was that ever acceptable in hardware?" Hint: consider what fraction of translations actually reach the table, and what a good hash plus clustering does to expected chain length.

Memory Protection Bits

Theory

The page table entry has room for more than a frame number, and the spare bits are where protection lives. Because the MMU already consults the PTE on every access, checking a few bits costs nothing extra — protection becomes free, and can be specified at page granularity.

The essential bits:

• Valid / present. Is this page mapped at all? Invalid means the address is not part of the process's address space (or is not currently resident — Chapter 8 distinguishes these). Access traps.
• Read / write. Writable or read-only. Enforced on every store. This one bit implements copy-on-write, read-only text segments, and read-only data (const in a linker section).
• User / supervisor. May user-mode code touch this page? Kernel pages are mapped into every process's address space (so system calls need no page-table switch) but marked supervisor-only. A user access traps rather than reads.
• Execute / no-execute (NX, XD, XN). May instructions be fetched from this page? Introduced in the early 2000s specifically to stop stack- and heap-based code injection: an attacker who writes shellcode into a data page cannot execute it, because the page is marked NX.
• Accessed and dirty. Set by hardware, cleared by the OS. Accessed says "referenced since I last cleared this" and drives page-replacement algorithms; dirty says "modified since it was loaded" and determines whether eviction needs a write-back.

The design principle running through this is W^X (write XOR execute): no page should be both writable and executable at the same time. Code is R-X, data is RW-, and anything that must generate code at run time (a JIT) maps a page W first, writes into it, then remaps it X — never both. Modern hardened systems enforce this, and a violation is now a common source of "permission denied" from mmap.

A protection violation and a page fault use the same trap mechanism but mean different things. The kernel's fault handler inspects the faulting address and the error code to decide: fix it silently (page not resident, or a copy-on-write page needing a private copy), or deliver SIGSEGV.

Example

   PROTECTION BITS IN A PTE, AND WHAT EACH BLOCKS

   +-------+---+---+---+---+---+---------------------------+
   | frame | P |R/W|U/S| A | D | NX |                      |
   +-------+---+---+---+---+---+---------------------------+
              |   |   |   |   |   |
              |   |   |   |   |   +-- instruction fetch -> blocks shellcode
              |   |   |   |   +------ set on write  -> eviction needs write-back
              |   |   |   +---------- set on access -> drives LRU approximations
              |   |   +-------------- user access   -> blocks kernel-memory reads
              |   +------------------ store         -> enables COW, RO text
              +---------------------- any access    -> page fault

   A PROCESS'S SEGMENTS AND THEIR PERMISSIONS (from /proc/PID/maps)

   r-xp   text        code        execute, never write     (W^X)
   r--p   rodata      constants   neither write nor execute
   rw-p   data/bss    globals     write, never execute     (W^X)
   rw-p   heap        malloc      write, never execute
   rw-p   stack       frames      write, never execute     (NX stack)
   r-xp   libc        shared      execute, shared frames, never write

   FAULT DECISION TREE IN THE KERNEL

   fault -> address mapped in the VMA list?
              no  -> SIGSEGV
              yes -> permission compatible?
                       no, and it is a COW write -> copy frame, mark writable, retry
                       no, otherwise             -> SIGSEGV
                       yes, page not resident    -> page in, retry (Chapter 8)

/* Protection bits, observed from user space. mprotect changes PTE bits
   for a range; the effect is immediate and enforced by hardware.
   Build: gcc -o prot prot.c */
#include <stdio.h>
#include <string.h>
#include <sys/mman.h>
#include <unistd.h>

int main(void) {
    size_t len = sysconf(_SC_PAGESIZE);

    /* Writable, NOT executable: the W half of W^X. */
    unsigned char *page = mmap(NULL, len, PROT_READ | PROT_WRITE,
                               MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

    /* x86-64: mov eax, 42 ; ret  -- a function, byte by byte. */
    unsigned char code[] = {0xB8, 0x2A, 0x00, 0x00, 0x00, 0xC3};
    memcpy(page, code, sizeof code);          /* legal: page is writable  */

    /* Flip to executable and drop write: the X half. Never both at once. */
    if (mprotect(page, len, PROT_READ | PROT_EXEC) != 0) { perror("mprotect"); return 1; }

    int (*fn)(void) = (int (*)(void))page;
    printf("%d\n", fn());                     /* 42 -- legal: page is now X */

    page[0] = 0x90;                           /* SIGSEGV: page is read-only */
    return 0;
}

# Read the permission column: this is the PTE bits, surfaced.
grep -E 'r-xp|rw-p' /proc/self/maps | head -5
# 55e0a1c00000-55e0a1c21000 r-xp  /usr/bin/grep     <- code: R+X, no W
# 55e0a1e22000-55e0a1e23000 rw-p  /usr/bin/grep     <- data: R+W, no X

# Confirm the stack is non-executable in a binary's program headers.
readelf -l /bin/ls | grep -A1 GNU_STACK
#   GNU_STACK  0x0 0x0 0x0 0x0 0x0 RW   0x10        <- RW, not RWE

Key takeaways

• Protection bits ride in the PTE, so the MMU enforces them on every access at no extra cost, at page granularity.
• Valid, read/write, user/supervisor, and no-execute are the four enforcement bits; accessed and dirty are hardware-set status bits for the OS.
• NX exists to defeat code injection: data pages cannot be executed even if an attacker writes code into them.
• W^X is the governing rule — a page is writable or executable, never both; JITs flip permissions between phases.
• Page faults and protection faults share a trap path; the kernel's handler decides between fixing silently and delivering SIGSEGV.

🧪 Practice

1. For each, name the bit that stops it and the resulting signal: writing to a string literal, executing a buffer on the stack, a user program reading kernel memory, dereferencing NULL.
2. Modify the C program above to call the function before mprotect and explain the exact failure. Then explain why a JIT compiler cannot simply map the page PROT_WRITE | PROT_EXEC on a hardened system.
3. Interview-style: "The dirty bit is set by hardware but cleared by software. Why that split?" Hint: think about who knows that a page's contents have been safely written to disk, and what a hardware-only policy would have to assume.

Shared Pages

Theory

Once memory is addressed by page-table entries rather than by physical position, sharing becomes almost free: map the same frame from two processes' page tables and both can reach it. This is not a niche optimisation — it is how modern systems fit hundreds of processes into finite RAM.

Three distinct uses:

1. Shared code (reentrant code). All processes running the same program or linked against the same library map identical text pages. One physical copy of libc's text serves every process. The requirement is that the code be reentrant: read-only and holding no per-process mutable state, so that concurrent execution by many processes is safe. The read-only PTE bit is what enforces this. Note the frame is shared while the virtual address need not be — each process may map it at a different address, which is exactly why position-independent code exists.

2. Copy-on-write (COW). fork() should duplicate a process's address space, but copying gigabytes only for the child to immediately exec() would be absurd. Instead the kernel maps the parent's frames into the child, marks every writable page read-only in both, and records that the page is COW. Reads proceed at full speed with no copying. The first write traps; the kernel allocates a fresh frame, copies the single page, marks it writable in the writer's table, and re-executes the instruction. Only pages actually modified are ever copied, so fork becomes nearly free and shares whatever is never written.

3. Explicit shared memory. Two unrelated processes deliberately map the same object — POSIX shm_open plus mmap, or MAP_SHARED on a file. This is the fastest IPC available (Chapter 2): after setup, communication is plain loads and stores with no kernel involvement and no copying. It is also the one where the processes must supply their own synchronisation, since the hardware provides none.

Accounting becomes ambiguous once sharing is pervasive. RSS counts every resident page of a process, charging a shared frame fully to each user, so RSS over all processes can far exceed installed RAM. PSS divides a shared frame's cost among its users, which is the honest per-process figure. Confusing the two is the standard error in memory-usage reports.

Kernels also share opportunistically: identical anonymous pages across virtual machines can be merged by KSM (kernel same-page merging), which scans, deduplicates, and marks the survivors COW — trading CPU for memory, and introducing a well-known side-channel risk.

Example

   SHARED LIBRARY: ONE PHYSICAL COPY, THREE MAPPINGS

   proc A page table            physical frames        proc B page table
   0x7f00 -> frame 42 (r-x) --> +-----------+ <-- 0x7a30 -> frame 42 (r-x)
                                | libc text |
   0x7f10 -> frame 55 (rw-) --> +-----------+     0x7a40 -> frame 91 (rw-)
                                | A's data  |                  |
                                +-----------+                  v
                                | B's data  | <----------------+
                                +-----------+
   Text: SHARED, read-only, possibly at DIFFERENT virtual addresses.
   Data: PRIVATE, one frame per process.

   COPY-ON-WRITE THROUGH A fork()

   before fork          after fork (no copying)     after child writes page 1
   parent  child        parent   child              parent   child
   p0 -> f7            p0 -> f7  p0 -> f7  (RO)     p0 -> f7  p0 -> f7  (RO)
   p1 -> f8            p1 -> f8  p1 -> f8  (RO)     p1 -> f8  p1 -> f9  (RW)
   p2 -> f9            p2 -> f9  p2 -> f9  (RO)     p2 -> f9  p2 -> f9  (RO)
                                                          ^ only ONE frame
                                                            was ever copied

   ACCOUNTING
     frame 42 is 2 MB, mapped by 100 processes
       RSS  : 2 MB charged to EACH -> 200 MB "used" (double counting)
       PSS  : 20 KB charged to each -> 2 MB total   (the truth)

/* Copy-on-write, observed. The child sees the parent's data without a copy;
   the first write triggers one. */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/wait.h>
#include <unistd.h>

int main(void) {
    size_t n = 64 * 1024 * 1024;              /* 64 MB */
    char *buf = malloc(n);
    memset(buf, 'A', n);                      /* force it resident */

    if (fork() == 0) {                        /* child */
        printf("child reads: %c (no copy made)\n", buf[0]);
        buf[0] = 'B';                         /* WRITE -> COW fault, 1 page copied */
        printf("child wrote: %c\n", buf[0]);
        _exit(0);
    }
    wait(NULL);
    printf("parent still: %c\n", buf[0]);     /* 'A' -- isolation preserved */
    free(buf);
    return 0;
}
/* The child's memory grows by ONE page (4 KB), not 64 MB. */

# Shared memory as IPC: no copying, no system calls after setup.
from multiprocessing import shared_memory, Process
import numpy as np

def worker(name, shape):
    shm = shared_memory.SharedMemory(name=name)     # maps the SAME frames
    arr = np.ndarray(shape, dtype=np.int64, buffer=shm.buf)
    arr[:] += 1                                     # plain stores, no kernel
    shm.close()

if __name__ == "__main__":
    shm = shared_memory.SharedMemory(create=True, size=8 * 5)
    arr = np.ndarray((5,), dtype=np.int64, buffer=shm.buf)
    arr[:] = [1, 2, 3, 4, 5]

    p = Process(target=worker, args=(shm.name, (5,)))
    p.start(); p.join()

    print(arr)          # [2 3 4 5 6] -- the child's writes are visible
    shm.close(); shm.unlink()
    # NOTE: no synchronisation here. With concurrent writers you MUST add a
    # lock in shared memory too -- the hardware gives you sharing, not safety.

# Honest per-process memory accounting.
grep -E '^(Rss|Pss|Shared_Clean|Private_Dirty):' /proc/self/smaps_rollup
# Rss:  15234 kB    <- shared frames charged in full
# Pss:   4102 kB    <- shared frames divided among users
# Private_Dirty: 2900 kB  <- what this process would actually free if it exited

Key takeaways

• Mapping the same frame into several page tables gives sharing at no cost; the read-only bit makes shared code safe.
• Shared text requires reentrant (read-only, no per-process state) code, and each process may map it at a different virtual address.
• Copy-on-write makes fork cheap: pages are shared read-only and copied individually only when first written.
• Explicit shared memory is the fastest IPC, but supplies no synchronisation — that remains the programmer's job.
• RSS double-counts shared frames; PSS (or private-dirty) is the figure to use when attributing memory to a process.

🧪 Practice

1. Fifty processes run the same 40 MB binary, of which 30 MB is text. Compute total physical memory with and without shared text, and state what property of the text makes sharing legal.
2. Run the COW program above under /usr/bin/time -v with and without the child's write, and explain the difference in minor page faults.
3. Interview-style: "A monitoring dashboard sums RSS across all processes and reports 40 GB used on a 16 GB machine. What went wrong, and what should it report?" Hint: work out what happens to a 2 MB shared library frame when a hundred processes each map it, and which metric divides that cost.

<a id="74-segmentation"></a>

7.4 Segmentation

Paging solves the OS's problem — fragmentation — but imposes a view of memory that no programmer holds. Segmentation is the alternative that matches how people actually think about a program's memory, and this section covers the model, its hardware, its combination with paging, and an honest comparison of all three schemes.

Segmentation Model

Theory

Ask a programmer to describe their program's memory and nobody says "page 0 through page 2047". They say: there is the code, the globals, the heap, the stack, this array, that library. Memory is a collection of variable-length logical units, each with a purpose and a natural size. Paging discards that structure entirely — a page boundary falls wherever the arithmetic puts it, possibly in the middle of a function or across the end of an array.

Segmentation preserves it. The logical address space is a collection of segments, each a contiguous region with its own name (number) and its own length. A logical address is a pair:

<segment number, offset within segment>

Segments are not required to be the same size, and are not required to be adjacent in the logical address space; each is its own little address space starting at zero.

The benefits follow from the unit matching the program's structure:

• Protection is meaningful. A code segment can be execute-only, a constants segment read-only, a stack segment read-write. With paging, permissions apply to arbitrary 4 KB chunks that may span two logical objects; with segments, the boundary is the object.
• Bounds checking is exact. An array in its own segment traps on the very first out-of-range index, because the segment length is the array length. Under paging, an overrun that stays within the last page is invisible.
• Sharing is natural. Share a segment and you have shared exactly one logical unit — a library, a table — not a rounded-up page range.
• Growth is expressible. A stack segment can be marked as growing downward and extended on demand, since the segment's length is explicit.

The cost is that segments are variable-length, which means they must be placed in variable-length holes in physical memory — and that returns us, exactly, to Section 7.2. Segmentation reintroduces external fragmentation, requires compaction, and needs a placement policy. It solved the programmer's problem by reviving the OS's problem, which is why pure segmentation lost and the combined scheme won.

Example

   THE PROGRAMMER'S VIEW, PRESERVED

   Logical address space (segments)        Physical memory
   +--------------------+
   | seg 0: main code   | 8 KB  ---------> +--------------+ 0x4000
   +--------------------+                  | seg 0 (8 KB) |
   | seg 1: sqrt library| 4 KB  ---\       +--------------+ 0x6000
   +--------------------+           \      | hole         |
   | seg 2: stack       | 16 KB -\   \     +--------------+ 0x7000
   +--------------------+         \   \--> | seg 1 (4 KB) |
   | seg 3: symbol table| 2 KB -\  \       +--------------+ 0x8000
   +--------------------+        \  \----> | seg 2 (16KB) |
                                  \        +--------------+ 0xC000
   No fixed sizes, no fixed order   \      | hole         |
   Each segment starts at offset 0   \---> | seg 3 (2 KB) |
                                           +--------------+
   ADDRESSING IS A PAIR                VARIABLE SIZES -> holes reappear
     <2, 0x1F4>  = byte 500 of the stack segment
     <3, 0x900>  = TRAP: 0x900 >= 0x800, past the end of the symbol table

   WHY BOUNDS CHECKING IS EXACT

   segment for int arr[100]  (length 400 bytes)
     arr[99]  -> offset 396  OK
     arr[100] -> offset 400  TRAP immediately
   under paging, arr sits inside a 4096-byte page:
     arr[100] -> still inside the page -> silently corrupts a neighbour

/* Segmented addressing, spelled out. Contrast with paging: the offset is
   NOT concatenated with a base -- it is ADDED, and it is bounds-checked
   against a per-segment length, not masked to a fixed page size. */

struct segment { unsigned long base, limit; int r, w, x; };

struct segment table[] = {
    /* 0 code  */ { .base = 0x4000, .limit = 0x2000, .r=1, .w=0, .x=1 },
    /* 1 lib   */ { .base = 0x7000, .limit = 0x1000, .r=1, .w=0, .x=1 },
    /* 2 stack */ { .base = 0x8000, .limit = 0x4000, .r=1, .w=1, .x=0 },
    /* 3 table */ { .base = 0xC000, .limit = 0x0800, .r=1, .w=1, .x=0 },
};

unsigned long translate(int seg, unsigned long off, int writing) {
    if (seg < 0 || seg >= 4)            trap(SEG_FAULT);
    if (off >= table[seg].limit)        trap(SEG_FAULT);   /* EXACT bound */
    if (writing && !table[seg].w)       trap(PROT_FAULT);
    return table[seg].base + off;                          /* add, not concat */
}

# The trade laid bare: segments fit the program, but their variable sizes
# recreate external fragmentation.

segments = {"code": 8192, "lib": 4096, "stack": 16384, "symtab": 2048}

# Place them in physical memory with first-fit over variable holes.
holes = [(0x4000, 0x2000), (0x7000, 0x1000), (0x8000, 0x4000), (0xC000, 0x1000)]
free_after = [0, 0, 0, 0x1000 - 2048]     # leftovers are new holes

print(f"total free: {sum(free_after)} bytes")     # 2048
print(f"largest hole: {max(free_after)} bytes")   # 2048
# A new 4 KB segment does not fit, even though free space exists elsewhere:
# this is Section 7.2's problem, returned unchanged.

Key takeaways

• Segmentation makes the unit of memory a logical program object of variable length, not a fixed-size block.
• A logical address is <segment number, offset>, and each segment is its own zero-based space.
• Protection, bounds checking, sharing, and growth all become exact because the boundary matches the object.
• Variable-length segments must be placed in variable-length holes, so external fragmentation and compaction return.

🧪 Practice

1. A program has segments: code 12 KB, constants 3 KB, heap 40 KB, stack 8 KB. Draw a plausible physical layout, then describe an allocation sequence that fragments it enough to block a 10 KB heap extension.
2. Explain why a buffer overflow within a 4 KB page is invisible under paging but caught immediately under segmentation, using a concrete array size.
3. Interview-style: "Segmentation gives exact bounds checking, yet no mainstream 64-bit OS uses it. What replaced it?" Hint: think about where bounds checking moved to — compilers, allocators, and hardware features like guard pages and memory tagging — and what segmentation cost the OS in return.

Segment Tables

Theory

Segmentation needs hardware just as paging does, and the structure is a direct generalisation of the base/limit registers from Section 7.1: instead of one pair per process, there is one pair per segment.

The segment table holds, for each segment number, a base (its physical starting address) and a limit (its length), plus protection bits. Translation of <s, d> is:

if (s >= STLR)   trap                 /* segment number out of range */
if (d >= limit[s]) trap               /* offset past the end        */
physical = base[s] + d

Two registers locate and bound the table itself: the segment-table base register (STBR) points to the table in memory, and the segment-table length register (STLR) gives the number of valid segments. Both are privileged to load, for the same reason base/limit were.

Note the structural difference from paging. In paging, the frame number and offset are concatenated — no addition is needed and no bounds check per-entry is needed, because every page is exactly the page size. In segmentation, translation requires a comparison against a per-segment limit and an addition. That is more hardware on the critical path, and it is why segment descriptors are cached in registers rather than looked up per access.

x86 is the canonical real implementation. Six segment registers (CS, DS, SS, ES, FS, GS) each hold a selector — an index into a descriptor table (GDT or LDT) plus a requested privilege level. Loading a selector causes the CPU to fetch the 8-byte descriptor (base, limit, type, DPL, granularity) into a hidden register, so subsequent accesses use the cached descriptor with no memory reference. Every instruction implicitly names a segment: code fetches use CS, stack operations use SS, ordinary data uses DS.

In 64-bit long mode, most of this was removed: CS, DS, SS, and ES are forced to base 0 with no limit — a flat model — because the OS uses paging for everything and segmentation only got in the way. The survivors are FS and GS, whose bases are still usable and are used for exactly one thing each: thread-local storage in user space (FS on Linux) and the per-CPU data pointer in the kernel (GS). It is a good illustration of a mechanism reduced to its one irreplaceable use.

Example

   SEGMENT TABLE AND THE TWO-STEP CHECK

   logical <s, d>
       |
       | s >= STLR ? --------------------> TRAP (bad segment number)
       v
   +---------------------------+
   | seg | base   | limit | RWX|      STBR --> table in memory
   +-----+--------+-------+----+      STLR --> 4 valid entries
   |  0  | 0x4000 | 0x2000| r-x|
   |  1  | 0x7000 | 0x1000| r-x|
   |  2  | 0x8000 | 0x4000| rw-|
   |  3  | 0xC000 | 0x0800| rw-|
   +-----+--------+-------+----+
       |
       | d >= limit[s] ? ------------------> TRAP (offset out of range)
       v
   physical = base[s] + d          <- ADD, unlike paging's concatenation

   WORKED EXAMPLES
     <0, 0x100>  -> 0x4100          OK
     <2, 0x3FFF> -> 0xBFFF          OK (last byte of the stack)
     <3, 0x800>  -> TRAP            0x800 >= 0x800
     <7, 0x0>    -> TRAP            7 >= STLR

   x86 SEGMENT SELECTOR (16 bits) AND WHAT LONG MODE KEPT

    15 .................. 3   2    1 0
   +-------------------------+---+-----+
   |        index (13)       |TI | RPL |    TI: 0=GDT 1=LDT
   +-------------------------+---+-----+    RPL: requested privilege level

   64-bit long mode:  CS DS SS ES -> base 0, no limit (flat)
                      FS -> thread-local storage base   (kept)
                      GS -> per-CPU kernel data base    (kept)

/* Segment table translation, including the checks in the required order. */

struct seg_desc { unsigned long base, limit; unsigned r:1, w:1, x:1; };

struct seg_desc *STBR;      /* segment-table base register  */
unsigned         STLR;      /* segment-table length register */

unsigned long seg_translate(unsigned s, unsigned long d,
                            int writing, int fetching) {
    if (s >= STLR)                       trap(SEG_FAULT);   /* check 1 */
    struct seg_desc *sd = &STBR[s];
    if (d >= sd->limit)                  trap(SEG_FAULT);   /* check 2 */
    if (writing  && !sd->w)              trap(PROT_FAULT);
    if (fetching && !sd->x)              trap(PROT_FAULT);
    return sd->base + d;
}

/* The one piece of segmentation still doing real work in 64-bit user space:
   FS-relative addressing for thread-local storage.
   Compile with: gcc -O1 tls.c -S -o -   and read the generated assembly. */
#include <stdio.h>
#include <pthread.h>

__thread int per_thread_counter;      /* one instance PER THREAD */

void *work(void *arg) {
    per_thread_counter = (int)(long)arg;    /* becomes: mov %eax, %fs:offset */
    printf("thread sees %d\n", per_thread_counter);
    return NULL;
}

int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, work, (void *)1L);
    pthread_create(&t2, NULL, work, (void *)2L);
    pthread_join(t1, NULL); pthread_join(t2, NULL);
    /* Same virtual "address" in the source, different bytes per thread,
       because FS holds a different base in each thread. */
    return 0;
}

Key takeaways

• A segment table holds a base and a limit per segment; STBR locates the table and STLR bounds it, both privileged to load.
• Translation is compare-then-add, versus paging's concatenate — more work per access, which is why descriptors are cached in registers.
• On x86, segment registers hold selectors indexing the GDT/LDT, and the CPU caches the descriptor in a hidden register on load.
• 64-bit long mode flattens CS/DS/SS/ES to base 0, keeping only FS (thread-local storage) and GS (per-CPU kernel data).

🧪 Practice

1. Given the table in the diagram, resolve <1, 0xFFF>, <1, 0x1000>, <2, 0x0>, and <4, 0x10>, stating the physical address or the specific trap.
2. Compare the per-access hardware needed for segmentation versus paging (comparators, adders, table lookups) and explain which is cheaper to pipeline.
3. Interview-style: "x86-64 removed almost all of segmentation but kept FS and GS. Why those two?" Hint: consider what a thread needs that is at the same source-level address in every thread but must resolve differently, and what the kernel needs per core.

Segmentation with Paging

Theory

Pure segmentation gives a good programmer's model with a bad allocation problem. Pure paging gives good allocation with no logical structure. The obvious move is to combine them: keep segments as the logical unit, but page each segment rather than placing it contiguously.

The scheme works in two stages. A logical address <s, d> is first resolved through the segment table, but the segment descriptor no longer holds a physical base — it holds the address of a page table for that segment. The offset d is then split into a page number and a page offset and translated through that page table. Each segment gets exactly as many pages as its length requires.

Every problem dissolves:

• Segments no longer need contiguous physical memory, so external fragmentation is gone.
• Internal fragmentation is limited to the last page of each segment.
• Protection and bounds checking stay at the segment level, where they are meaningful.
• Segments can grow by adding pages, without moving anything.
• Sharing works at either granularity: a whole segment or an individual page.

MULTICS pioneered this in the 1960s, with a segment table that was itself paged because it could be enormous. Intel's 80386 implemented it as the standard mode for protected-mode x86: logical address to linear address via segmentation, then linear address to physical via two-level paging.

And then the industry quietly stopped using the segmentation half. Modern operating systems on x86 set all segment bases to 0 and all limits to maximum, making the logical and linear addresses identical, and rely entirely on paging. In 64-bit long mode the hardware enforces this. The reasons are worth stating plainly: paging alone was sufficient for the OS's needs; segmentation's per-access compare-and-add cost real cycles; portability across architectures that never had segmentation mattered more than a feature only x86 offered; and compilers and allocators took over fine-grained bounds checking.

So the model to carry forward is: the combined scheme is the theoretically best design, and the industry chose flat paging anyway — a genuine case of a good idea losing to simplicity and portability. Segmentation's descendants live on as FS/GS bases, guard pages, and hardware memory tagging (ARM MTE, SPARC ADI), which restore fine-grained bounds checking by a different route.

Example

   TWO-STAGE TRANSLATION: SEGMENT SELECTS A PAGE TABLE

   logical <s, d>
      |
      +--> s --> segment table [ limit | page-table pointer | RWX ]
      |               |
      |          d >= limit ? -> TRAP    <- bounds check at the LOGICAL unit
      |               |
      +--> d = [ p | offset ]
                     |
                     v
             segment s's page table --> frame f
                     |
                     v
             physical = [ f | offset ]   <- concatenation, no contiguity needed

   x86 PROTECTED MODE, THE FULL PATH

   logical (seg:offset)  --segmentation-->  linear  --paging-->  physical
        CS:0x1000            base + off      0x8001000           frame|off

   What every modern OS does with the first stage:
        base = 0, limit = 4 GB   ->   linear == logical   ->   FLAT MODEL

   WHAT THE COMBINATION FIXES

   property                pure seg   pure paging   segmented paging
   ---------------------   --------   -----------   ----------------
   external fragmentation  yes        no            no
   internal fragmentation  no         last page     last page of each segment
   logical bounds checks   exact      no            exact
   growth without moving   no         yes           yes
   contiguous physical     required   not required  not required

# Segmented paging: bounds-check against the segment, then page the offset.

PAGE_BITS = 12
PAGE_SIZE = 1 << PAGE_BITS

class Segment:
    def __init__(self, limit, writable):
        self.limit = limit                 # exact logical length in bytes
        self.writable = writable
        self.page_table = {}               # page-within-segment -> frame

class SegmentedPaging:
    def __init__(self):
        self.segments = []

    def add_segment(self, limit, writable, frames):
        seg = Segment(limit, writable)
        # One entry per page the segment actually needs -- and the frames
        # need not be contiguous or even close together.
        for page, frame in enumerate(frames):
            seg.page_table[page] = frame
        self.segments.append(seg)
        return len(self.segments) - 1

    def translate(self, s, d, writing=False):
        if s >= len(self.segments):
            raise MemoryError("segment fault: bad segment number")
        seg = self.segments[s]
        if d >= seg.limit:                             # STAGE 1: exact bound
            raise MemoryError(f"segment fault: offset {d} >= limit {seg.limit}")
        if writing and not seg.writable:
            raise MemoryError("protection fault")
        page, off = d >> PAGE_BITS, d & (PAGE_SIZE - 1)  # STAGE 2: paging
        frame = seg.page_table.get(page)
        if frame is None:
            raise MemoryError(f"page fault: segment {s} page {page}")
        return (frame << PAGE_BITS) | off

mm = SegmentedPaging()
code = mm.add_segment(limit=5000, writable=False, frames=[9, 3])   # scattered
data = mm.add_segment(limit=3000, writable=True,  frames=[7])

print(hex(mm.translate(code, 0x100)))    # 0x9100
print(hex(mm.translate(code, 0x1000)))   # 0x3000  <- page 1, a distant frame
mm.translate(code, 5000)                 # MemoryError: exact segment bound

Key takeaways

• Segmented paging keeps segments as the logical unit but stores each segment as pages, so no segment needs contiguous physical memory.
• External fragmentation disappears; internal fragmentation is limited to the last page of each segment.
• Bounds checking and protection remain at the segment level, where they correspond to real program objects.
• MULTICS pioneered it and the 80386 implemented it, but modern OSes flatten segmentation away and use paging alone.
• The reasons flat paging won are simplicity, per-access cost, and portability — not that the combined scheme was worse in theory.

🧪 Practice

1. Segment 2 has a limit of 9000 bytes and page table {0: 12, 1: 40, 2: 7} with 4 KB pages. Translate offsets 0, 4096, 8999, and 9000.
2. Compute the page-table memory for a process with segments of 12 KB, 3 KB, 40 KB, and 8 KB (4 KB pages, 4-byte entries), and compare it to a flat 32-bit page table.
3. Interview-style: "If segmented paging is theoretically superior, why does Linux on x86-64 use a flat model?" Hint: count the mechanisms an OS must implement and port if it uses both, and ask what segmentation provides that page-level permissions plus compiler checks do not.

Comparison of Schemes

Theory

With all the mechanisms on the table, it is worth setting them side by side, because each one exists as a response to a specific defect in the one before it.

The chain of reasoning runs:

1. Contiguous allocation is simple and needs only base and limit registers, but forces each process into one physical run — producing external fragmentation and blocking sharing, growth, and partial residency.
2. Segmentation breaks the process into several logical runs, which fixes sharing, per-object protection, and exact bounds checking. But the runs are still variable-length and still contiguous, so external fragmentation survives.
3. Paging makes every unit the same fixed size, which deletes external fragmentation outright at the cost of a small, bounded internal waste, a translation table, and the loss of any logical structure.
4. Segmented paging combines the last two and has the best properties of both, at the cost of two mechanisms to build and maintain.
5. Flat paging is what everyone actually ships, because paging alone was sufficient and portable.

The key evaluation axes:

Property	Contiguous	Segmentation	Paging	Segmented paging
Unit	Whole process	Logical object	Fixed-size page	Object, stored as pages
Unit size	Variable	Variable	Fixed	Variable (paged)
External fragmentation	Severe	Severe	None	None
Internal fragmentation	None	None	Half a page per region	Half a page per segment
Hardware needed	Base + limit	Segment table (compare + add)	Page table + TLB	Both
Translation cost	1 add	1 compare + 1 add	Table walk (TLB-cached)	Segment check + walk
Table size overhead	2 registers	Small (few segments)	Large (many pages)	Both
Bounds checking	Whole process	Exact, per object	Page granularity only	Exact, per object
Sharing granularity	All or nothing	Per segment	Per page	Per segment or page
Supports partial residency	No	Per segment (coarse)	Per page (ideal)	Per page
Growth	Requires moving	Requires moving/compaction	Add a page anywhere	Add a page anywhere
Programmer's view	Flat	Matches program structure	Flat	Matches program structure
Used today	Embedded/MPU	FS/GS only	Everywhere	Hardware exists, unused

Two conclusions deserve emphasis. First, fixed-size units are what kill external fragmentation — not clever placement, not compaction, not better free lists. Any scheme with variable-length contiguous allocation has the problem; any scheme with interchangeable fixed-size units does not. Second, paging is what makes demand paging possible, which is the real reason it won. Fixed-size, interchangeable, individually relocatable units are precisely what you need to move memory between RAM and disk one piece at a time. Segmentation could never do that gracefully, because moving a 40 MB segment is a 40 MB operation. That is the bridge into Chapter 8.

Example

   THE SAME PROCESS UNDER EACH SCHEME
   (code 8 KB, data 6 KB, stack 4 KB; 4 KB pages)

   CONTIGUOUS                  SEGMENTATION
   one 18 KB run               three runs of 8 KB, 6 KB, 4 KB
   [########## 18 KB ########]  [#8KB#] ... [#6KB#] ... [#4KB#]
   fails if no 18 KB hole       fails if no 8 KB hole
   ext frag: yes                ext frag: yes (smaller pieces help a little)
   int frag: none               int frag: none

   PAGING                                 SEGMENTED PAGING
   5 pages, any 5 free frames             3 segments, paged: 2 + 2 + 1 frames
   [f9][f3][f17][f2][f44]                 code -> [f9][f3]   limit 8192
   never fails while frames exist         data -> [f17][f2]  limit 6144
   ext frag: none                         stack-> [f44]      limit 4096
   int frag: 2 KB (last page of the       ext frag: none
             single flat region)          int frag: 2 KB + 2 KB + 0 (per segment)
   bounds: page granularity only          bounds: EXACT per segment

   THE DECIDING PROPERTY FOR CHAPTER 8

     Can one unit be moved to disk independently and cheaply?
       contiguous   : no  (the unit is the whole process)
       segmentation : barely (a 40 MB segment is a 40 MB transfer)
       paging       : YES (4 KB, uniform, interchangeable)  <- demand paging

# Score the schemes on the same workload instead of arguing about them.

PAGE = 4096
regions = {"code": 8192, "data": 6144, "stack": 4096}
total = sum(regions.values())

def ceil_div(a, b):
    return -(-a // b)

# Contiguous: one run; internal waste zero, but needs one hole of `total`.
contiguous = {"largest_hole_needed": total, "internal": 0, "external_risk": "high"}

# Segmentation: several runs; needs a hole per segment.
segmentation = {"largest_hole_needed": max(regions.values()),
                "internal": 0, "external_risk": "medium"}

# Paging: no hole requirement at all; waste is the tail of the flat region.
pages = ceil_div(total, PAGE)
paging = {"largest_hole_needed": PAGE, "internal": pages * PAGE - total,
          "external_risk": "none"}

# Segmented paging: per-segment tails, but still no contiguity requirement.
seg_pages = {k: ceil_div(v, PAGE) for k, v in regions.items()}
seg_paging = {"largest_hole_needed": PAGE,
              "internal": sum(seg_pages[k] * PAGE - v for k, v in regions.items()),
              "external_risk": "none"}

for name, s in [("contiguous", contiguous), ("segmentation", segmentation),
                ("paging", paging), ("segmented paging", seg_paging)]:
    print(f"{name:18} hole needed {s['largest_hole_needed']:>6} B | "
          f"internal waste {s['internal']:>5} B | external {s['external_risk']}")
# contiguous         hole needed  18432 B | internal waste     0 B | external high
# segmentation       hole needed   8192 B | internal waste     0 B | external medium
# paging             hole needed   4096 B | internal waste  2048 B | external none
# segmented paging   hole needed   4096 B | internal waste  4096 B | external none

Key takeaways

• Each scheme is a response to the previous one's defect: contiguous to nothing, segmentation to sharing and protection, paging to external fragmentation, segmented paging to both.
• Fixed-size interchangeable units are the only thing that eliminates external fragmentation; placement policy only changes the constant.
• Segmentation's advantage is the logical model — exact bounds and per-object protection — which flat paging gives up.
• Segmented paging is theoretically strongest, yet flat paging is universal, for reasons of simplicity, per-access cost, and portability.
• Paging won decisively because uniform, individually movable units are the precondition for demand paging, the subject of Chapter 8.

🧪 Practice

1. Fill in the comparison table from memory for external fragmentation, internal fragmentation, bounds-checking granularity, and hardware required, then check it against the table above.
2. A process has segments of 100 KB, 3 KB, and 700 KB on a system with 4 KB pages. Compute the internal fragmentation under flat paging and under segmented paging, and explain the difference.
3. Interview-style: "Which single property of paging made virtual memory practical, and why could segmentation not provide it?" Hint: focus on the size and uniformity of the unit that has to be transferred to and from disk, and what happens to transfer time when that unit is variable and large.

---

<a id="8-virtual-memory"></a>