The Engineer's Loom

What a process is

A process has three kinds of state. Its address space is the memory it can see: the program's code, its global data, a heap that grows as it allocates, a stack for each thread, and any files or libraries mapped in (chapter 17 of The Engineer's Mill). Its CPU state is the program counter, the stack pointer and the other registers; while the process isn't running, these are saved in the kernel. Its kernel state is the rest: a process ID, its parent's ID, the user and group it runs as, a table of open files, a current directory, how it handles each signal, and its resource limits. The kernel keeps all of this in one record per process, the process control block. On Linux it's a structure called task_struct, several kilobytes long.

On Linux you can read much of this directly. /proc/<pid>/maps lists a process's address space region by region, /proc/<pid>/fd lists its open files, and /proc/<pid>/status shows its state, memory use and owner. ps and top are mostly ways of reading /proc. On macOS, ps, lsof and vmmap show the same things.

Each process sees its own memory

Addresses in a program are virtual. When two processes both use address 0x601000, each reaches its own memory, because the kernel gives each process its own map from virtual addresses to physical memory. Part IV explains how that map works and what it costs. For now, the consequence is the one that matters: one process can't read or overwrite another's memory by accident, and a crash in one leaves the rest running.

fork, exec and wait

Unix creates processes in two steps. fork() makes a copy of the calling process. The copy, the child, has the same code, a copy of the same memory, the same open files and the same position in the program. It differs in its process ID and in one value: fork() returns 0 in the child and the child's ID in the parent, which is how each knows which it is. exec() then replaces the program running in a process with a new one, keeping the process ID and the open files. The parent calls wait() to learn when the child has finished, and how.

Splitting creation into two calls looks odd, but it's what makes the shell simple. Between fork and exec, the child is still running the shell's code, so it can rearrange its own file descriptors, change directory, set limits or drop privileges, and the program it then runs inherits the result. That's how ls > out.txt works (chapter 3). Windows takes the other approach: CreateProcess creates a process and starts a program in one call, with parameters for everything a Unix child would set up itself. POSIX also offers posix_spawn, which does the same.

The example forks a child that changes a value, shows that the parent's copy is untouched although the address is the same, and collects the child's exit status. It then runs echo through fork and exec, and reads the exit statuses of four commands, one of which doesn't exist.

import os, sys

# 1. fork() returns twice: 0 in the child, the child's process ID in the parent
account = [100]                                  # one object, at one virtual address
address = id(account)
reader, writer = os.pipe()                       # a pipe, so the child can report back
sys.stdout.flush()                               # empty Python's buffer, or the child inherits a copy of it
pid = os.fork()
if pid == 0:                                     # ---- the child ----
    account[0] -= 30                             # changes the child's copy only
    os.write(writer, f"{account[0]} {id(account)}".encode())
    os._exit(3)                                  # exit status 3, without running the parent's cleanup
_, status = os.waitpid(pid, 0)                   # ---- the parent waits for it ----
child_value, child_address = map(int, os.read(reader, 100).split())
print(f"fork returned the child's pid to the parent: {pid > 0}")
print(f"child's account: {child_value}; parent's account: {account[0]}")
print(f"same virtual address in both processes: {child_address == address}")
print(f"child's exit status, collected by waitpid: {os.waitstatus_to_exitcode(status)}")

# 2. exec() replaces the running program; the process, and its pid, stay the same
sys.stdout.flush()
pid = os.fork()
if pid == 0:
    os.execvp("echo", ["echo", "now running echo, inside the process that fork made"])
    os._exit(127)                                # only reached if exec failed
os.waitpid(pid, 0)

# 3. Exit statuses: 0 means success; anything else is an error code for the parent to read
for cmd in (["true"], ["false"], ["sh", "-c", "exit 7"], ["no-such-program"]):
    sys.stdout.flush()
    pid = os.fork()
    if pid == 0:
        try:
            os.execvp(cmd[0], cmd)
        except FileNotFoundError:
            os._exit(127)                        # the shell's convention for "command not found"
    _, status = os.waitpid(pid, 0)
    print(f"{' '.join(cmd):16} exited with status {os.waitstatus_to_exitcode(status)}")

fork returned the child's pid to the parent: True
child's account: 70; parent's account: 100
same virtual address in both processes: True
child's exit status, collected by waitpid: 3
now running echo, inside the process that fork made
true             exited with status 0
false            exited with status 1
sh -c exit 7     exited with status 7
no-such-program  exited with status 127

Two details in the code matter in any language. The child ends with os._exit, which leaves at once, instead of returning into the parent's code or running the parent's clean-up handlers twice. And the parent empties Python's output buffer before each fork, for a reason exercise 1.2 explains.

fork has critics. Copying a process with a large address space is slow even with the tricks of chapter 13, and forking a process that runs several threads copies only the thread that called it, which can leave locks held forever by threads that don't exist in the child. Baumann and colleagues argued in 2019 that fork no longer belongs in operating systems. Python 3.14 stopped using it by default for multiprocessing on Linux for this reason. Shells and servers still use it everywhere, so it's worth understanding precisely.

The life of a process

A process moves between a few states. It's running while a core is executing it, ready while it could run but is waiting for a core, and blocked while it waits for something else: a disk read, a network packet, a timer, a lock. Chapters 4 to 6 are about the move from ready to running. A process that has exited but whose parent hasn't yet called wait is a zombie. Its memory and files are gone, but the kernel keeps its process ID and exit status until the parent collects them. In ps output these states appear as R, S (sleeping, blocked), D (blocked in a way signals can't interrupt, usually disk I/O), T (stopped) and Z.

Two rules follow. A parent should wait for every child, or tell the kernel it doesn't care, by setting SIGCHLD to be ignored, so that children are reaped automatically. Otherwise zombies accumulate until no process IDs are left. And if a parent exits first, its children are orphans: the kernel hands them to process 1, init or systemd, which waits for them. Exit statuses follow a convention shells rely on: 0 means success, small numbers are errors chosen by the program, 126 means a file couldn't be executed, 127 that the command wasn't found, and 128 plus n that the process was killed by signal n.

Two modes

Every modern processor runs in at least two modes. In user mode, the mode programs run in, some instructions are forbidden: those that talk to devices, change the page tables, switch off interrupts or halt the machine. In kernel mode everything is allowed. On x86 the modes are called rings 3 and 0; on ARM they're exception levels EL0 and EL1. A user program that tries a privileged instruction doesn't get to run it. The processor traps into the kernel, which normally kills the program.

This is what lets the operating system run programs directly on the hardware, at full speed, and still stay in charge. OSTEP calls it limited direct execution. The program's instructions run on the real processor with no interpreter in the way, but there are only three ways back into the kernel: the program asks, with a system call; the program does something it can't, such as dividing by zero or touching unmapped memory, which raises an exception; or a device or the timer raises an interrupt. The timer interrupt is the one that guarantees the kernel can always take the processor back, even from a program stuck in a loop (chapter 5).

Crossing the boundary

From Python, os.write(fd, data) calls the C library's write function, which is a thin wrapper. On Linux on x86-64, it puts the system call's number, 1 for write, in the rax register and the three arguments in rdi, rsi and rdx, then executes the syscall instruction. On 64-bit ARM the instruction is svc #0 and the number goes in x8. The processor switches to kernel mode and jumps to an entry point the kernel registered at boot. Nothing else about the jump is up to the program.

The kernel's entry code saves the program's registers, switches to a stack that belongs to the kernel, and looks the number up in the system call table, about 450 entries on Linux. The handler checks its arguments before trusting them. A pointer from user space must point into the caller's own memory, and the kernel copies data in and out with special functions instead of following the pointer directly, because a malicious program could pass the address of kernel memory. When the work is done, the result goes back in a register and the processor returns to user mode. On failure the kernel returns a negative error number, and the C library turns it into a return value of −1 with the number in errno. Python turns it into an exception: ENOENT becomes FileNotFoundError, EACCES becomes PermissionError, EAGAIN becomes BlockingIOError.

What a crossing costs

A system call costs far more than a function call. The mode switch, saving and restoring registers, the checks, and on some processors the mitigations added after the Meltdown and Spectre attacks of 2018 (chapter 13 of The Engineer's Mill) all take time, and the kernel's code and data push the program's out of the caches. The example times the smallest system call there is, getppid, then one that does real work, and then writes a million bytes three ways. The timings are one recorded run on an Apple M1 Pro.

import io, os, time

def per_call(fn, n):
    best = float("inf")
    for _ in range(5):                                   # best of five runs, to skip noise
        t0 = time.perf_counter()
        fn(n)
        best = min(best, time.perf_counter() - t0)
    return best / n * 1e9                                # nanoseconds per call

def nothing(): return 0
def calls(n):
    for _ in range(n): nothing()                         # an ordinary function call: no kernel
def getppid(n):
    for _ in range(n): os.getppid()                      # the smallest real system call
def stat(n):
    for _ in range(n): os.stat("/")                      # a system call that does some work

N = 200_000
base = per_call(calls, N)
print(f"Python function call      {base:6.0f} ns")
print(f"os.getppid() system call  {per_call(getppid, N):6.0f} ns")
print(f"os.stat('/') system call  {per_call(stat, N):6.0f} ns")

# Writing a million bytes to /dev/null: one write per byte, a buffered file, or one big write
fd = os.open(os.devnull, os.O_WRONLY)
SIZE = 1_000_000
def unbuffered(_):
    for _ in range(SIZE): os.write(fd, b"x")            # a million system calls
def buffered(_):
    with open(os.devnull, "wb") as f:                    # Python collects bytes in a buffer...
        for _ in range(SIZE): f.write(b"x")              # ...and calls write() when it fills
def one_write(_):
    os.write(fd, b"x" * SIZE)                            # one system call
print(f"\nwriting {SIZE:,} bytes (Python's buffer is {io.DEFAULT_BUFFER_SIZE:,} bytes):")
for name, fn, syscalls in (("one write() per byte", unbuffered, SIZE),
                           ("buffered file object", buffered, -(-SIZE // io.DEFAULT_BUFFER_SIZE)),
                           ("one write() of everything", one_write, 1)):
    ms = per_call(fn, 1) / 1e6
    print(f"   {name:26} {ms:9.3f} ms   {syscalls:>9,} system call{'s' if syscalls > 1 else ''}")

Python function call          29 ns
os.getppid() system call     161 ns
os.stat('/') system call    1301 ns

writing 1,000,000 bytes (Python's buffer is 131,072 bytes):
   one write() per byte         573.625 ms   1,000,000 system calls
   buffered file object          39.286 ms           8 system calls
   one write() of everything      0.037 ms           1 system call

Even from Python, where an ordinary function call costs about 29 ns, the cheapest system call costs over five times as much, and from C the ratio is closer to a hundred. Writing a byte at a time made a million system calls and took over half a second. A buffered file object made 8, because Python collects bytes in a 128 KiB buffer and calls write only when it fills; its 39 ms are almost all the cost of a million calls to f.write in Python, not of the kernel. A single write of the whole megabyte took 0.04 ms. The per-call overhead, not the bytes, was the cost.

Fewer, bigger crossings

That result is behind a whole family of techniques. Buffering, in C's stdio and in every language's file objects, turns many small writes into a few large ones. readv and writev move several buffers in one call. sendfile and copy_file_range move data from one file descriptor to another without bringing it into the process at all. mmap maps a file into memory so that reading it needs no system calls, only page faults (chapter 13). epoll returns many ready connections from one call (chapter 18), and Linux's io_uring lets a program queue hundreds of operations and collect their results through memory shared with the kernel.

Some calls don't need the kernel at all. Reading the clock is so common that Linux maps a small read-only page of kernel data and code, the vDSO, into every process. clock_gettime runs there, in user mode, and costs about as much as a function call. macOS does the same with its commpage.

Watching system calls

On Linux, strace prints every system call a program makes, with its arguments and result. strace -c counts them and totals their time, and strace -e trace=openat shows only the files a program opens, which is often the fastest way to find out why it can't find its configuration. perf trace does the same with less overhead. On macOS, dtruss and Instruments do the same job, though system integrity protection limits what they can trace. A program that's slow without using much CPU is often blocked in a system call, and these tools show which one.

def write_all(fd, data):
    view = memoryview(data)
    while view:
        n = os.write(fd, view)     # may take only part of it
        view = view[n:]

File descriptors 0, 1 and 2

Every process starts with three open file descriptors: 0 for standard input, 1 for standard output and 2 for standard error. A program writes to descriptor 1 without knowing whether it leads to a terminal, a file or another program. Whoever started the program decided that, and that's the trick behind redirection. open always returns the lowest free descriptor, and dup2(old, new) makes descriptor new refer to the same open file as old, closing whatever new referred to before. To run ls > out.txt, the shell forks, and the child opens out.txt, calls dup2 to put it on descriptor 1, closes the original descriptor, and execs ls. ls writes to descriptor 1 as always and never learns the difference.

Redirections are applied left to right, each one a dup2. 2>&1 means "make descriptor 2 a copy of whatever descriptor 1 is now". So cmd > file 2>&1 first points 1 at the file and then copies that to 2, sending both to the file. cmd 2>&1 > file copies 1, still the terminal, to 2 first, and only then points 1 at the file.

Pipes

pipe() creates a buffer in the kernel and returns two descriptors: bytes written to one can be read from the other, in order. The buffer is small, 64 KiB by default on Linux, so a fast writer blocks until the reader catches up, and a reader blocks until there's something to read. That keeps a pipeline's memory use bounded however much data flows through it. A read returns end-of-file only when every write end of the pipe is closed, and a write to a pipe with no readers left sends the writer SIGPIPE, which kills it by default. That's how yes | head -1 ends: head exits after one line and yes dies on its next write.

For a pipeline the shell creates one pipe between each pair of stages and forks one child per stage. Each child moves the right pipe ends onto its descriptors 0 and 1 with dup2, closes every other pipe descriptor it inherited, and execs its program. The parent closes its copies too. Each of those closes matters. A reader sees end-of-file only when every copy of the write end is closed, including copies left open by mistake in the parent or a sibling.

A shell in forty lines

The example's start function does what a real shell does for a pipeline with redirections, and wait_all waits for every stage and reports the status of the last, which is the status a shell reports for a pipeline. It runs the pipeline in the figure, writes a file through a redirection and reads it back through another, and shows that true | false fails while false | true succeeds. The second half starts sleep 30 | sleep 30, suspends it, resumes it and interrupts it, the way Ctrl-Z, fg and Ctrl-C would, and then catches a signal sent to itself.

import os, sys, shlex, signal, tempfile

def start(line):
    """Start a pipeline like 'a | b < in > out' in its own process group; return the child pids."""
    stages = [shlex.split(part) for part in line.split("|")]
    pids, pgid, prev_read = [], 0, None
    exec_r, exec_w = os.pipe()               # close-on-exec: every child's copy closes when it execs
    for i, argv in enumerate(stages):
        infile = outfile = None
        if "<" in argv: k = argv.index("<"); infile = argv[k + 1]; del argv[k:k + 2]
        if ">" in argv: k = argv.index(">"); outfile = argv[k + 1]; del argv[k:k + 2]
        read_end, write_end = os.pipe() if i < len(stages) - 1 else (None, None)
        sys.stdout.flush()
        pid = os.fork()
        if pid == 0:                                            # the child: wire up fds, then exec
            os.setpgid(0, pgid)                                 # join the pipeline's process group
            signal.signal(signal.SIGINT, signal.SIG_DFL)        # undo Python's Ctrl-C handler, as shells do
            if prev_read is not None: os.dup2(prev_read, 0)     # stdin from the previous stage
            if write_end is not None: os.dup2(write_end, 1)     # stdout into the next stage
            if infile: os.dup2(os.open(infile, os.O_RDONLY), 0)
            if outfile: os.dup2(os.open(outfile, os.O_WRONLY | os.O_CREAT | os.O_TRUNC, 0o644), 1)
            for fd in (prev_read, read_end, write_end, exec_r): # close the originals, or readers
                if fd is not None: os.close(fd)                 # never see end-of-file
            try: os.execvp(argv[0], argv)
            except OSError: os._exit(127)                       # never fall back into the shell's code
        pgid = pgid or pid                                      # the first child leads the group
        try: os.setpgid(pid, pgid)                              # set it here too, to avoid a race
        except PermissionError: pass                            # (the child got there first and exec'd)
        if prev_read is not None: os.close(prev_read)
        if write_end is not None: os.close(write_end)
        prev_read = read_end
        pids.append(pid)
    os.close(exec_w)
    os.read(exec_r, 1)                       # returns only when every child has exec'd (or died)
    os.close(exec_r)
    return pids

def wait_all(pids):
    """Wait for every stage; like a shell, report the status of the last one."""
    statuses = [os.waitpid(pid, 0)[1] for pid in pids]
    last = statuses[-1]
    if os.WIFSIGNALED(last): return f"killed by {signal.Signals(os.WTERMSIG(last)).name}"
    return f"exit status {os.waitstatus_to_exitcode(last)}"

def run(line):
    print(f"$ {line}"); return wait_all(start(line))

work = tempfile.mkdtemp()
os.chdir(work)
run("printf 'pear\\napple\\nfig\\napple\\n' | sort | uniq")
run("printf 'beta\\nalpha\\n' | sort > sorted.txt")
run("tr a-z A-Z < sorted.txt")
for line in ("true | false", "false | true"):
    print(f"$ {line:13} -> {wait_all(start(line))}")

# Signals: a whole pipeline in one process group can be stopped, resumed or killed together
pids = start("sleep 30 | sleep 30")
os.killpg(pids[0], signal.SIGSTOP)                              # what Ctrl-Z sends: suspend the job
os.killpg(pids[0], signal.SIGCONT)                              # what 'fg' sends: resume it
os.killpg(pids[0], signal.SIGINT)                               # what Ctrl-C sends: interrupt it
print(f"\nsleep 30 | sleep 30, after SIGSTOP, SIGCONT and SIGINT to its group: {wait_all(pids)}")

# A process can catch most signals and decide what to do; SIGKILL and SIGSTOP can't be caught
signal.signal(signal.SIGTERM, lambda signum, frame: print("caught SIGTERM: cleaning up before exit"))
os.kill(os.getpid(), signal.SIGTERM)
try:
    signal.signal(signal.SIGKILL, lambda signum, frame: None)
except OSError as e:
    print(f"installing a SIGKILL handler fails: {e.strerror}")

$ printf 'pear\napple\nfig\napple\n' | sort | uniq
apple
fig
pear
$ printf 'beta\nalpha\n' | sort > sorted.txt
$ tr a-z A-Z < sorted.txt
ALPHA
BETA
$ true | false  -> exit status 1
$ false | true  -> exit status 0

sleep 30 | sleep 30, after SIGSTOP, SIGCONT and SIGINT to its group: killed by SIGINT
caught SIGTERM: cleaning up before exit
installing a SIGKILL handler fails: Invalid argument

One detail took longer to get right than the rest. The parent must not signal the pipeline until both children have called exec: a child interrupted while still running Python would handle the signal as Python, not as sleep. The example waits on an extra pipe that Python creates with the close-on-exec flag. Each child's copy closes automatically when that child execs, so the parent's read returns only when all of them have. Shells solve the same race in their own ways, and it's a good example of how much of systems programming is about the order in which things happen.

Signals

A signal is a small asynchronous notification sent to a process by the kernel or by another process. The common ones: SIGINT, sent by Ctrl-C; SIGTERM, the polite request to exit that kill sends by default; SIGKILL, which ends the process at once; SIGTSTP, sent by Ctrl-Z, and SIGSTOP, which suspend it; SIGCONT, which resumes it; SIGCHLD, sent to a parent when a child exits or stops; SIGPIPE; SIGSEGV, for an invalid memory access; and SIGHUP, sent when the terminal goes away and, by convention, used to ask a daemon to reload its configuration.

For each signal a process chooses the default action, which for most signals is to terminate, to ignore the signal, or to run a handler. SIGKILL and SIGSTOP can't be caught or ignored, which is what makes them reliable; the example's attempt to install a SIGKILL handler fails. A handler can run between any two instructions of the program, so in C it may only call functions that are safe at any moment: not malloc and not printf, which may be halfway through updating their own state. The usual pattern is for the handler to set a flag, or write a byte to a pipe that the main loop watches, and let the main program do the work. Python does this for you: its C-level handler only records the signal, and your Python handler runs in the main thread at the next safe point.

Job control

A shell puts each pipeline in its own process group, with setpgid, so the whole job can be signalled at once with killpg. The terminal driver tracks one foreground process group. When you press Ctrl-C, the terminal sends SIGINT to every process in that group, and the shell itself, which is in another group, is untouched. Ctrl-Z sends SIGTSTP; the shell notices that the job has stopped (through waitpid with the WUNTRACED flag), takes the terminal back, and prints a prompt. fg hands the terminal to the job again and sends SIGCONT; bg sends SIGCONT without handing the terminal over. The same mechanisms run production systems. When a container or a systemd service is stopped, its main process gets SIGTERM, a grace period, 10 seconds by default in Docker and 30 in Kubernetes, and then SIGKILL. A service that handles SIGTERM by finishing its current requests and exiting shuts down cleanly. One that doesn't is killed in the middle of them.

Processes and threads

Each thread has its own program counter and registers, its own stack, its own thread-local variables (in C, errno is one) and its own signal mask. Everything else belongs to the process and is shared by all its threads: the code, the global variables, the heap, the open file descriptors, the current directory, the user ID and the process ID. A pointer created in one thread works in every other. On Linux a thread is simply a task, like a process, created with clone and flags that ask it to share the parent's memory, files and signal handlers. Each thread has its own thread ID, and ps -L or top -H lists them.

Threads are cheaper than processes to create and to switch between, because there's no address space to copy or change, and they communicate through ordinary memory. Processes are safer: a crash, a memory leak or a corrupted heap in one process leaves the others alone, while a bad pointer in any thread brings down the whole process. Browsers run each site in its own process for that reason, and databases such as PostgreSQL use a process per connection. Most servers written in Java, Go or C++ run many threads in one process.

What a context switch does

A context switch moves a core from one thread to another. It starts in the kernel, either because the running thread made a system call that blocks, such as a read with no data waiting, or because a timer interrupt fired and the scheduler decided the thread's turn was over. The kernel saves the running thread's registers and stack pointer, picks the next thread (chapters 5 and 6), loads that thread's stack pointer and registers, and returns to it as if from an interrupt. If the next thread belongs to a different process, the kernel also switches address spaces by loading a new page-table root, CR3 on x86 or TTBR0 on ARM. Tagging TLB entries with an address-space ID, PCID on x86 and ASID on ARM, means the switch doesn't have to throw away every cached translation (chapter 13).

The direct cost is a microsecond or two. The indirect cost is often larger: the new thread finds the caches and the TLB full of the old thread's data, and runs slowly until it has warmed them up again. That's why a scheduler doesn't switch as often as it could, and why a server that keeps thousands of threads busy can spend a surprising share of its time switching.

Measured

The example first shows the difference in sharing: four threads appending to one list fill it, while four forked processes each append to their own copy. It then times creating a thread against forking a process, and measures a handover with a ping-pong over two pipes, in which each side blocks until the other replies, so every round trip forces two wake-ups and two switches. The timings are one recorded run on an Apple M1 Pro.

import os, sys, threading, time

# 1. Threads share one address space; forked processes each get a copy
results = []
def work(name):
    for i in range(1000): results.append((name, i))
threads = [threading.Thread(target=work, args=(n,)) for n in range(4)]
for t in threads: t.start()
for t in threads: t.join()
print(f"4 threads appended to one list: it now holds {len(results):,} items")
results.clear()
pids = []
for n in range(4):
    sys.stdout.flush()
    pid = os.fork()
    if pid == 0: work(n); os._exit(0)            # appends to the child's own copy
    pids.append(pid)
for pid in pids: os.waitpid(pid, 0)
print(f"4 forked processes appended to 'the same' list: the parent's holds {len(results):,}")

# 2. What creating each costs
def timed(fn, n):
    t0 = time.perf_counter(); fn(n); return (time.perf_counter() - t0) / n * 1e6
def make_threads(n):
    for _ in range(n):
        t = threading.Thread(target=lambda: None); t.start(); t.join()
def make_processes(n):
    for _ in range(n):
        pid = os.fork()
        if pid == 0: os._exit(0)
        os.waitpid(pid, 0)
print(f"\nstart and join a thread:      {timed(make_threads, 2000):6.1f} µs")
print(f"fork and wait for a process:  {timed(make_processes, 500):6.1f} µs")

# 3. A context switch, measured by ping-pong: each side blocks until the other answers
def ping_pong(n, use_threads):
    a_r, a_w = os.pipe(); b_r, b_w = os.pipe()
    def echo():
        for _ in range(n): os.write(b_w, os.read(a_r, 1))
    if use_threads:
        other = threading.Thread(target=echo); other.start()
    else:
        sys.stdout.flush()
        pid = os.fork()
        if pid == 0: echo(); os._exit(0)
    t0 = time.perf_counter()
    for _ in range(n):
        os.write(a_w, b"x"); os.read(b_r, 1)     # hand over, then wait to be handed back
    elapsed = time.perf_counter() - t0
    other.join() if use_threads else os.waitpid(pid, 0)
    for fd in (a_r, a_w, b_r, b_w): os.close(fd)
    return elapsed / n / 2 * 1e6                 # two handovers per round trip
N = 20_000
print(f"\none handover between two processes: {ping_pong(N, False):5.1f} µs")
print(f"one handover between two threads:   {ping_pong(N, True):5.1f} µs")
print(f"(this machine has {os.cpu_count()} cores; a handover includes a wake-up, a switch and a pipe)")

4 threads appended to one list: it now holds 4,000 items
4 forked processes appended to 'the same' list: the parent's holds 0

start and join a thread:        41.8 µs
fork and wait for a process:   904.5 µs

one handover between two processes:   2.1 µs
one handover between two threads:     1.7 µs
(this machine has 8 cores; a handover includes a wake-up, a switch and a pipe)

Starting and joining a thread took about 42 µs, and forking and waiting for a process about 0.9 ms, over twenty times as long, because the kernel had to duplicate the page tables of a whole Python process. Each handover took about 2 µs, and that includes waking a thread blocked on a pipe, scheduling it, and the pipe read and write, so the switch itself is only part of it. Linux on a typical server gives similar orders of magnitude, with a faster fork. The practical lessons: create threads ahead of time and reuse them, which is what a thread pool does, and don't design a system that needs a context switch for every small piece of work.

Kernel threads and user threads

The threads above are kernel threads: the kernel knows about each one and schedules it. That's the model of POSIX threads in C, of Java's platform threads and of Rust's standard library, one language thread per kernel thread. Each needs a kernel stack and a user stack, 8 MiB of reserved address space by default on Linux, of which typically only tens of kilobytes are ever touched, and every switch between them goes through the kernel.

Many runtimes instead multiplex many lightweight user threads onto a few kernel threads, switching between them in user space for a few hundred nanoseconds. Go's goroutines start with 2 KiB stacks that grow as needed, and the Go runtime runs them on roughly one kernel thread per core. Java added virtual threads on the same model in JDK 21, and Erlang has always worked this way. The difficulty is blocking: when a user thread makes a system call that blocks, it blocks the kernel thread under it, and every user thread scheduled there. These runtimes therefore use non-blocking I/O internally (chapter 18) and hand blocking calls to spare kernel threads.

Python's threads

CPython's threads are real kernel threads, but in the standard build a global interpreter lock, the GIL, lets only one of them run Python code at a time. A thread releases it while waiting for I/O, so threads work well for programs that spend their time waiting on networks and disks, and do nothing for programs that spend it computing in Python. The example's thread handover includes passing the GIL. For CPU-bound work, use processes (multiprocessing or concurrent.futures.ProcessPoolExecutor), or libraries such as NumPy whose C code releases the lock. A free-threaded build without the GIL became an officially supported option in Python 3.14, which makes the data races of chapter 7 real for Python code too.

What a scheduler optimises

Chapters 2 and 4 covered the mechanism: the timer interrupt that hands control back to the kernel, and the context switch that moves a core to another thread. This chapter is about policy, the rule for which thread runs next. Two measures dominate. A job's turnaround time is how long it takes from arriving to finishing, which matters for batch work such as a build or a report. Its response time is how long it waits before it first runs, which is what a person at a keyboard or a client waiting on a request feels. Throughput, the work finished per second, and fairness, whether each job gets its share, complete the list. No policy wins on all of them.

First come, first served, and the convoy

The simplest policy runs jobs in the order they arrive, each to completion. Its weakness shows as soon as a long job arrives first. With A needing 100 ms and B and C 10 ms each, B and C wait behind A like cars behind a truck, the convoy effect, and the average turnaround is 110 ms. Running the shortest job first brings it down to 50 ms, and when all jobs arrive together, shortest job first is provably the best possible order for average turnaround.

Shortest job first has two problems. It needs to know how long each job will run, which a general-purpose operating system never does. And if it's non-preemptive, letting each job run until it finishes, it's helpless when short jobs arrive just after a long one has started: in the example's second workload B and C arrive 10 ms after A and wait 90 ms for it, and the average turnaround goes back up to 103 ms. The preemptive version, shortest time to completion first, interrupts A when they arrive and brings the average back to 50 ms.

Round robin and response time

Round robin gives each ready job a fixed time slice in turn and puts it at the back of the queue when the slice ends. It needs to know nothing about the jobs, and it's excellent for response time: with 1 ms slices every job runs within 2 ms of arriving. It's poor for turnaround, because it stretches every job out to near the end. The slice length is the dial between the two. Short slices give quick responses but spend more time switching, and with 20 CPU-bound threads ready, a 100 ms slice means each waits up to 1.9 seconds for its turn. Desktop and server kernels use slices of a few milliseconds.

# A scheduler simulator in 1 ms ticks. Each job: (name, arrival time, CPU time needed).
def simulate(jobs, policy, quantum=None):
    left = {n: run for n, _, run in jobs}
    arrive = {n: at for n, at, _ in jobs}
    first, done, queue, t, current, used = {}, {}, [], 0, None, 0
    while len(done) < len(jobs):
        queue += [n for n, at, _ in jobs if at == t]                 # newly arrived jobs join
        if current and policy == "STCF":                              # preempt for a shorter job
            queue.append(current); current = None
        if current and policy == "RR" and used == quantum:            # time slice over: requeue
            queue.append(current); current = None
        if current is None and queue:
            if policy in ("SJF", "STCF"): queue.sort(key=lambda n: left[n])  # shortest first
            current, used = queue.pop(0), 0
            first.setdefault(current, t)
        if current:
            left[current] -= 1; used += 1
            if left[current] == 0: done[current] = t + 1; current = None
        t += 1
    turnaround = sum(done[n] - arrive[n] for n in done) / len(jobs)
    response = sum(first[n] - arrive[n] for n in first) / len(jobs)
    return turnaround, response

def table(title, jobs, policies):
    print(title)
    for label, policy, q in policies:
        ta, rs = simulate(jobs, policy, q)
        print(f"   {label:28} average turnaround {ta:6.1f} ms   average response {rs:5.1f} ms")

table("A needs 100 ms, B and C 10 ms each, all arriving at time 0:",
      [("A", 0, 100), ("B", 0, 10), ("C", 0, 10)],
      [("FIFO", "FIFO", None), ("shortest job first", "SJF", None), ("round robin, 1 ms slice", "RR", 1)])
table("\nA arrives at 0; B and C arrive at 10 ms:",
      [("A", 0, 100), ("B", 10, 10), ("C", 10, 10)],
      [("shortest job first", "SJF", None), ("shortest time to completion", "STCF", None),
       ("round robin, 10 ms slice", "RR", 10)])

# A multi-level feedback queue: a 10 ms time slice, demotion after 10 ms of CPU at a level
def mlfq(jobs, ticks=3000, levels=3, boost_every=None, charge_blocked=True):
    """jobs: name -> (burst, io): run `burst` ms, then wait `io` ms for I/O, forever (io=0: CPU-bound)."""
    level = dict.fromkeys(jobs, 0); used = dict.fromkeys(jobs, 0); burst = dict.fromkeys(jobs, 0)
    wake = dict.fromkeys(jobs, 0); queued = dict.fromkeys(jobs, 0); cpu = dict.fromkeys(jobs, 0)
    worst = dict.fromkeys(jobs, 0); waited = dict.fromkeys(jobs, 0); runs = dict.fromkeys(jobs, 0)
    current, slice_used = None, 0
    for t in range(ticks):
        if boost_every and t and t % boost_every == 0:
            for n in jobs: level[n], used[n] = 0, 0                    # everyone back to the top
        ready = [n for n in jobs if wake[n] <= t and n != current]
        if current and any(level[n] < level[current] for n in ready):  # a higher-priority job woke up
            queued[current] = t; current = None
        if current is None and ready:                                  # highest level, then longest waiting
            current = min(ready, key=lambda n: (level[n], max(queued[n], wake[n])))
            w = t - max(queued[current], wake[current])
            worst[current] = max(worst[current], w); waited[current] += w; runs[current] += 1
            slice_used = 0
        if current is None: continue
        n = current
        cpu[n] += 1; used[n] += 1; slice_used += 1; burst[n] += 1
        b, io = jobs[n]
        if io and burst[n] == b:                                       # gives up the CPU for I/O
            burst[n] = 0; wake[n] = t + 1 + io; current = None
            if not charge_blocked: used[n] = 0                         # the old rule: forget its usage
        if used[n] >= 10 and level[n] < levels - 1:                    # used up its allotment: demote
            level[n] += 1; used[n] = 0
            if current: queued[n] = t + 1; current = None
        elif current and slice_used == 10:                             # slice over: back of the queue
            queued[n] = t + 1; current = None
    for n in jobs:                                                     # still waiting at the end?
        if n != current and wake[n] <= ticks:
            worst[n] = max(worst[n], ticks - max(queued[n], wake[n]))
    return {n: (cpu[n] / ticks, waited[n] / runs[n], worst[n]) for n in jobs}

def show(title, result):
    print(title)
    for n, (share, mean, worst) in result.items():
        print(f"   {n:12} {share:6.1%} of the CPU   "
              f"waits to run: {mean:5.1f} ms on average, {worst:4d} ms at most")

mix = {"interactive": (1, 9), "batch-1": (100, 0), "batch-2": (100, 0)}
print()
show("Round robin, 10 ms slices: an interactive job (1 ms of CPU, then 9 ms of I/O) and two batch jobs:",
     mlfq(mix, levels=1))
show("\nThe same jobs under MLFQ with three levels and a boost every 100 ms:",
     mlfq(mix, boost_every=100))
game = {"gamer": (9, 1), "batch-1": (100, 0), "batch-2": (100, 0)}
show("\nA job that yields after 9 ms, every time, when blocking resets its allotment:",
     mlfq(game, boost_every=100, charge_blocked=False))
show("\nThe same job when the scheduler counts all the CPU it used:",
     mlfq(game, boost_every=100))
crowd = {**{f"chatty-{i}": (1, 4) for i in range(5)}, "batch": (100, 0)}
show("\nFive chatty jobs fill the top level (old rule, no boost):",
     mlfq(crowd, charge_blocked=False))
show("\nThe same mix with a boost every 100 ms:",
     mlfq(crowd, charge_blocked=False, boost_every=100))

A needs 100 ms, B and C 10 ms each, all arriving at time 0:
   FIFO                         average turnaround  110.0 ms   average response  70.0 ms
   shortest job first           average turnaround   50.0 ms   average response  10.0 ms
   round robin, 1 ms slice      average turnaround   59.7 ms   average response   1.0 ms

A arrives at 0; B and C arrive at 10 ms:
   shortest job first           average turnaround  103.3 ms   average response  63.3 ms
   shortest time to completion  average turnaround   50.0 ms   average response   3.3 ms
   round robin, 10 ms slice     average turnaround   50.0 ms   average response   3.3 ms

Round robin, 10 ms slices: an interactive job (1 ms of CPU, then 9 ms of I/O) and two batch jobs:
   interactive    4.8% of the CPU   waits to run:  10.9 ms on average,   11 ms at most
   batch-1       47.7% of the CPU   waits to run:  10.9 ms on average,   11 ms at most
   batch-2       47.6% of the CPU   waits to run:  11.0 ms on average,   11 ms at most

The same jobs under MLFQ with three levels and a boost every 100 ms:
   interactive    8.9% of the CPU   waits to run:   1.2 ms on average,   11 ms at most
   batch-1       45.6% of the CPU   waits to run:   8.7 ms on average,   11 ms at most
   batch-2       45.5% of the CPU   waits to run:   8.7 ms on average,   11 ms at most

A job that yields after 9 ms, every time, when blocking resets its allotment:
   gamer         72.9% of the CPU   waits to run:   2.3 ms on average,   19 ms at most
   batch-1       13.6% of the CPU   waits to run:  18.9 ms on average,   19 ms at most
   batch-2       13.5% of the CPU   waits to run:  19.0 ms on average,   19 ms at most

The same job when the scheduler counts all the CPU it used:
   gamer         27.0% of the CPU   waits to run:  13.9 ms on average,   20 ms at most
   batch-1       36.5% of the CPU   waits to run:  14.1 ms on average,   19 ms at most
   batch-2       36.5% of the CPU   waits to run:  14.1 ms on average,   19 ms at most

Five chatty jobs fill the top level (old rule, no boost):
   chatty-0      19.9% of the CPU   waits to run:   0.0 ms on average,   10 ms at most
   chatty-1      19.9% of the CPU   waits to run:   0.0 ms on average,   10 ms at most
   chatty-2      19.9% of the CPU   waits to run:   0.0 ms on average,   10 ms at most
   chatty-3      19.9% of the CPU   waits to run:   0.0 ms on average,   10 ms at most
   chatty-4      19.9% of the CPU   waits to run:   0.0 ms on average,   10 ms at most
   batch          0.3% of the CPU   waits to run:   5.0 ms on average, 2985 ms at most

The same mix with a boost every 100 ms:
   chatty-0      18.0% of the CPU   waits to run:   0.6 ms on average,   10 ms at most
   chatty-1      18.0% of the CPU   waits to run:   0.6 ms on average,   10 ms at most
   chatty-2      18.0% of the CPU   waits to run:   0.6 ms on average,   10 ms at most
   chatty-3      18.0% of the CPU   waits to run:   0.6 ms on average,   10 ms at most
   chatty-4      18.0% of the CPU   waits to run:   0.6 ms on average,   10 ms at most
   batch         10.0% of the CPU   waits to run:  87.0 ms on average,   90 ms at most

Not knowing the future: the multi-level feedback queue

A real scheduler has to favour short, interactive jobs without being told which they are. The multi-level feedback queue (MLFQ), introduced by Fernando Corbató for MIT's CTSS time-sharing system in 1962, learns it from behaviour. There are several priority levels. A job at a higher level always runs before one at a lower level, and jobs at the same level share it round robin. Every new job starts at the top. A job that uses up its allotment of CPU time at a level moves down a level, so CPU-bound jobs sink, while a job that runs briefly and then waits for I/O stays near the top.

The example shows the effect. An interactive job that wants 1 ms of CPU every 10 ms competes with two CPU-bound batch jobs. Under plain round robin it waits about 11 ms every time it wakes, behind the batch jobs' slices, and gets only 4.8% of the CPU instead of the 10% it needs. Under MLFQ it waits 1.2 ms on average, because by then the batch jobs have sunk below it, and it gets 8.9%.

The rules need two refinements. The first version of the demotion rule reset a job's allotment whenever it gave up the CPU for I/O. A program that does a tiny I/O just before its allotment runs out then never sinks. The example's "gamer" yields after 9 ms of every 10 and takes 72.9% of the CPU from two jobs that should share it equally. Counting all the CPU a job uses at a level, however it's split up, demotes the gamer like anyone else, and the three jobs then get roughly equal shares. The second refinement fixes starvation. Five chatty jobs that together keep the top level busy leave a batch job at the bottom with 0.3% of the CPU and a wait of almost 3 seconds. A periodic priority boost that moves every job back to the top fixes that: with a boost every 100 ms, the batch job gets 10% and never waits more than 90 ms. The boost also helps a job whose behaviour changes, such as a compiler that turns into an editor.

Variants of MLFQ schedule Windows threads and macOS threads, and FreeBSD's ULE scheduler scores each thread's interactivity from how much it sleeps. Linux took a different path, fair queuing, which chapter 6 covers.

Proportional share

In proportional-share scheduling each thread holds a weight, and when threads compete each gets CPU time in proportion to its weight. Carl Waldspurger and William Weihl's lottery scheduling (1994) did it with tickets and chance: at every time slice, draw a ticket at random, and the holder runs. A thread with 75 of 100 tickets wins 75% of the draws in the long run. Lottery is simple, needs no global state, and handles new threads instantly, but it's only fair on average. Over short windows the shares wander, which is exactly when a user notices. Waldspurger's stride scheduling (1995) removes the randomness. Each thread has a "pass" value that grows by a stride, inversely proportional to its tickets, every time it runs, and the scheduler always picks the thread with the smallest pass.

Virtual runtime

Linux's Completely Fair Scheduler, CFS, written by Ingo Molnar and in use from 2007, applies the stride idea to time itself. Each thread has a virtual runtime: a clock that advances while the thread runs, at a rate inversely proportional to its weight. The scheduler always runs the thread with the smallest virtual runtime, kept in a red-black tree so the smallest is quick to find. A thread at the default weight's virtual clock runs at real speed; a thread with a third of the weight has a clock that runs three times as fast, so it reaches the front of the queue a third as often.

Weights come from a thread's nice value, from −20 to 19, through a fixed table in the kernel: nice 0 is 1024, and each step changes the weight by about a quarter, so that each step moves about 10% of the CPU between two competing threads. One detail matters for interactive programs. A thread that has been asleep has a small virtual runtime, and if it kept it, it would monopolise the processor on waking until it caught up. So on waking, its virtual runtime is moved up to just below the smallest of the running threads, a few milliseconds of credit and no more. In Linux 6.6, in 2023, Peter Zijlstra replaced CFS's selection rule with EEVDF, earliest eligible virtual deadline first. It keeps the virtual clocks but also gives each thread a deadline based on how far it's behind and how long a slice it asks for, so latency-sensitive threads can request short slices and run sooner without getting more CPU in total.

import random

# 1. Weighted fair queueing, as Linux's CFS does it: always run the task with the least virtual
#    runtime, and charge each task's virtual clock at 1024 / weight times real time.
WEIGHT = {-5: 3121, 0: 1024, 5: 335, 10: 110, 19: 15}             # from the kernel's nice-to-weight table
def fair(tasks, ms=3000, asleep_until=None):
    asleep_until = asleep_until or {}
    vruntime = dict.fromkeys(tasks, 0.0); cpu = dict.fromkeys(tasks, 0)
    for t in range(ms):
        awake = [n for n in tasks if asleep_until.get(n, 0) <= t]
        for n in awake:
            others = [vruntime[m] for m in awake if m != n]
            if t and asleep_until.get(n, 0) == t and others:            # just woke up: no banked credit,
                vruntime[n] = max(vruntime[n], min(others) - 3)         # only a 3 ms head start
        n = min(awake, key=lambda n: (vruntime[n], n))
        cpu[n] += 1
        vruntime[n] += 1024 / WEIGHT[tasks[n]]
    return {n: cpu[n] / ms for n in tasks}

print("three CPU-bound tasks, nice 0, 0 and 5:",
      ", ".join(f"{n} {s:.1%}" for n, s in fair({"a": 0, "b": 0, "c": 5}).items()))
print("expected from the weights 1024 : 1024 : 335:",
      ", ".join(f"{w / 2383:.1%}" for w in (1024, 1024, 335)))
print("nice -5 against nice 19:", ", ".join(f"{n} {s:.1%}" for n, s in fair({"x": -5, "y": 19}).items()))
woke = fair({"a": 0, "b": 0}, ms=2000, asleep_until={"b": 1000})
print(f"b sleeps for the first second, then competes: a {woke['a']:.1%}, b {woke['b']:.1%} "
      f"(once awake, b gets half, not a second of catch-up)")

# 2. Lottery against stride scheduling: 75 and 25 tickets, measured over short windows
random.seed(6)
def lottery(slices):
    return sum(random.random() < 0.75 for _ in range(slices)) / slices    # A's share of the window
def stride(slices):
    passes, a = {"A": 0.0, "B": 0.0}, 0
    for _ in range(slices):
        n = min(passes, key=lambda n: (passes[n], n))
        a += n == "A"
        passes[n] += 1 / (75 if n == "A" else 25)                      # stride = 1 / tickets
    return a / slices
lot = [lottery(20) for _ in range(10)]
strd = [stride(20) for _ in range(10)]
print(f"\nA's share in ten windows of 20 time slices, lottery: {' '.join(f'{x:.0%}' for x in lot)}")
print(f"A's share in ten windows of 20 time slices, stride:  {' '.join(f'{x:.0%}' for x in strd)}")

# 3. Many cores: five equal jobs on four cores, with and without migration between cores
def cores(jobs=5, n=4, ms=1000, migrate=False):
    cpu = [0] * jobs
    for t in range(ms):
        if migrate:
            running = sorted(range(jobs), key=lambda j: (cpu[j], j))[:n]   # balance: least-served first
        else:
            queues = [[j for j in range(jobs) if j % n == c] for c in range(n)]   # pinned at start
            running = [q[t % len(q)] for q in queues]                     # round robin on each core
        for j in running: cpu[j] += 1
    return [c / ms for c in cpu]
print(f"\nfive jobs on four cores, never migrated: {' '.join(f'{s:.0%}' for s in cores())}")
print(f"five jobs on four cores, balanced:       {' '.join(f'{s:.0%}' for s in cores(migrate=True))}")

three CPU-bound tasks, nice 0, 0 and 5: a 43.0%, b 43.0%, c 14.1%
expected from the weights 1024 : 1024 : 335: 43.0%, 43.0%, 14.1%
nice -5 against nice 19: x 99.5%, y 0.5%
b sleeps for the first second, then competes: a 75.0%, b 25.1% (once awake, b gets half, not a second of catch-up)

A's share in ten windows of 20 time slices, lottery: 70% 65% 80% 70% 80% 75% 70% 80% 55% 60%
A's share in ten windows of 20 time slices, stride:  75% 75% 75% 75% 75% 75% 75% 75% 75% 75%

five jobs on four cores, never migrated: 50% 100% 100% 100% 50%
five jobs on four cores, balanced:       80% 80% 80% 80% 80%

The simulated shares match the weights to the decimal: 43.0%, 43.0% and 14.1% for nice 0, 0 and 5, and 99.5% to 0.5% for nice −5 against nice 19. The task that slept for a second got half the CPU once it woke, not a second of catch-up. The lottery's windows of 20 slices gave A anywhere from 55% to 80% of a share that should be 75%; stride gave exactly 75% every time.

Many cores

With several cores, the scheduler also decides where each thread runs. A single shared run queue would be fair but slow, because every core would contend for its lock, so kernels keep a run queue per core and balance them: periodically, and whenever a core goes idle and steals work from a busy one. Balancing fights with cache affinity. A thread that moves to another core leaves its warm caches behind, and on machines with several memory controllers, NUMA machines, it may end up far from its memory. The example's five equal jobs on four cores show what happens without balancing: the two jobs that share a core get 50% each while the other three get a whole core, and balancing gives all five 80%. Programs can restrict where a thread may run with sched_setaffinity or taskset, which helps for a latency-critical thread on a dedicated core and hurts when it overrides a balancer that knew better.

Priorities, real time and inversion

Above the fair classes, Linux has real-time classes. A SCHED_FIFO thread runs until it blocks or a higher-priority real-time thread wakes, and always ahead of every normal thread; SCHED_RR adds time slices among equals, and SCHED_DEADLINE schedules by declared runtimes and deadlines. A real-time thread stuck in a loop could freeze the machine, so by default Linux reserves 5% of each second for normal threads.

Strict priorities have a famous failure, priority inversion. In July 1997 the Mars Pathfinder lander began resetting itself every few days. A low-priority task held a mutex that a high-priority bus task needed. Medium-priority tasks, which needed neither, kept preempting the low-priority one, so it never released the mutex, and the high-priority task missed its deadline and a watchdog reset the system. The fix was priority inheritance: while a thread holds a lock that a higher-priority thread is waiting for, it runs at the waiter's priority. The engineers turned on the option, already in the operating system, VxWorks, by patching the software from Earth.

Containers apply the same ideas to groups of threads. A cgroup's cpu.weight divides CPU between groups in proportion, exactly like nice values between threads, and cpu.max sets a hard quota (chapter 20). In Kubernetes, a container's CPU request becomes its weight and its CPU limit becomes its quota.

A race in three instructions

count += 1 looks like one operation, but the processor does it in three: load count into a register, add one, store the register back. Each thread has its own registers, so if two threads both load before either stores, both store the same value and one increment is lost. Code that touches shared data and must not be interleaved with another thread's is a critical section, and a race condition is a bug whose outcome depends on how threads happen to interleave. When two threads access the same memory, at least one of them writes, and nothing orders the accesses, the program has a data race. In C and C++ that is undefined behaviour, so the compiler may assume it never happens and the program may do anything.

Every order at once

Running a racy program a thousand times proves little, because the bad interleavings are rare. The example instead treats each thread as a list of steps and tries every order in which the steps could run. Two threads of three steps each can interleave in 20 ways, and only the 2 that run one thread entirely before the other give the right answer. With two increments per thread there are 924 orders, and the count ends at 4 in only 6 of them. An atomic fetch-and-add, one indivisible instruction, gives 4 in every order. The last part of the example checks a balance before debiting it, and two withdrawals of 80 from 100 leave the account at −60 in 4 of the 6 orders.

from collections import Counter

# A thread is a list of steps. Each step reads or writes shared memory or the thread's own registers,
# and the scheduler may switch threads between any two steps. We try every possible order.
def interleavings(threads, shared, regs=None, pcs=None, trace=()):
    regs = regs or [dict() for _ in threads]
    pcs = pcs or [0] * len(threads)
    if all(pc == len(t) for pc, t in zip(pcs, threads)):
        yield dict(shared), trace
        return
    for i, t in enumerate(threads):
        if pcs[i] < len(t):
            label, step = t[pcs[i]]
            s2, r2 = dict(shared), [dict(r) for r in regs]
            step(s2, r2[i])
            p2 = list(pcs); p2[i] += 1
            yield from interleavings(threads, s2, r2, p2, trace + (f"T{i + 1} {label}",))

def load(s, r):  r["x"] = s["count"]                  # count += 1 compiles to three instructions
def add(s, r):   r["x"] += 1
def store(s, r): s["count"] = r["x"]
increment = [("load", load), ("add", add), ("store", store)]

runs = list(interleavings([increment, increment], {"count": 0}))
outcomes = Counter(final["count"] for final, _ in runs)
print(f"two threads each run count += 1 once: {len(runs)} possible orders")
for value, n in sorted(outcomes.items()):
    print(f"   final count {value}: {n:2} orders")
lost = next(trace for final, trace in runs if final["count"] == 1)
print("   one order that loses an update: " + ", ".join(lost))

runs = list(interleavings([increment * 2, increment * 2], {"count": 0}))
outcomes = Counter(final["count"] for final, _ in runs)
print(f"\ntwo threads each run count += 1 twice: {len(runs)} orders, final count "
      + ", ".join(f"{v} in {n}" for v, n in sorted(outcomes.items())))

def fetch_add(s, r): s["count"] += 1                  # one indivisible instruction, like x86 LOCK XADD
runs = list(interleavings([[("fetch_add", fetch_add)] * 2] * 2, {"count": 0}))
finals = {final["count"] for final, _ in runs}
print(f"the same with an atomic fetch-and-add: {len(runs)} orders, final count always {finals.pop()}")

# Check-then-act: two withdrawals of 80 from a balance of 100, each checking first
def check(s, r):  r["ok"] = s["balance"] >= 80
def debit(s, r):
    if r["ok"]: s["balance"] -= 80
withdraw = [("check", check), ("debit", debit)]
runs = list(interleavings([withdraw, withdraw], {"balance": 100}))
outcomes = Counter(final["balance"] for final, _ in runs)
print(f"\ntwo withdrawals of 80 from 100: " + ", ".join(f"balance {v} in {n} of {len(runs)} orders"
                                                     for v, n in sorted(outcomes.items())))

two threads each run count += 1 once: 20 possible orders
   final count 1: 18 orders
   final count 2:  2 orders
   one order that loses an update: T1 load, T1 add, T2 load, T1 store, T2 add, T2 store

two threads each run count += 1 twice: 924 orders, final count 2 in 702, 3 in 216, 4 in 6
the same with an atomic fetch-and-add: 6 orders, final count always 4

two withdrawals of 80 from 100: balance -60 in 4 of 6 orders, balance 20 in 2 of 6 orders

In a real program the bad orders are rare because the window is tiny: a few nanoseconds between a load and a store, against time slices of milliseconds. A race can survive every test and still fire in production, under load, on more cores, or after an unrelated change shifts the timing. That's why races are found with tools, not luck. ThreadSanitizer, enabled with -fsanitize=thread in Clang and GCC, and Go's -race flag instrument memory accesses and report any two that aren't ordered, even when the run happened to produce the right answer. Model checkers go further and explore interleavings systematically, as the example does. Rust's loom crate does this for real concurrent code, and TLA+ does it for designs.

Check, then act

The withdrawal bug has a name, time of check to time of use (TOCTOU), and it's everywhere. "If the file doesn't exist, create it" races with another process creating it in between; open with O_CREAT | O_EXCL does both atomically and fails if the file exists. "If the user may access this path, open it" races with an attacker replacing the path with a symbolic link; open first and check the descriptor you got. In databases, reading a balance in one statement and updating it in another races with every other client; UPDATE accounts SET balance = balance - 80 WHERE id = 7 AND balance >= 80 makes the check and the change a single atomic step, and the number of rows it changed says whether it succeeded.

Atomic instructions

Processors provide instructions that read, modify and write a memory location as one indivisible step, even with many cores. Fetch-and-add (LOCK XADD on x86) increments and returns the old value. Compare-and-swap (LOCK CMPXCHG on x86, CAS on recent ARM) writes a new value only if the location still holds an expected one, and reports whether it did. With compare-and-swap you can make any update atomic: read the value, compute the new one, and retry if someone else changed it in between. Languages expose these as atomic types: std::atomic in C++, AtomicInteger in Java, sync/atomic in Go, AtomicU64 in Rust. Uncontended, an atomic operation costs a few tens of cycles. When many cores hammer the same location, its cache line bounces between them and each operation can take a hundred nanoseconds or more.

Memory models

There's a second reason plain variables can't coordinate threads: neither the compiler nor the processor promises to perform memory operations in program order. A compiler may keep a variable in a register and never reload it, or move a store past a load. Processors reorder too. On x86 a store can wait in a store buffer while later loads go ahead, so another core sees the store late. ARM, used in Apple silicon and AWS Graviton, allows much more reordering. The memory model of a language or processor says which reorderings are allowed, and atomic operations carry ordering guarantees, such as acquire, release or sequentially consistent, that rule them out where it matters. Chapter 8's model checker shows the consequence: Peterson's algorithm, provably correct with plain loads and stores, fails once store buffers are modelled, and a fence fixes it.

Python is not exempt. In the standard build, the GIL means only one thread runs Python code at a time, but count += 1 is several bytecodes and a thread switch can fall between them, so updates can still be lost. In the free-threaded build of Python 3.14 the threads really run in parallel. The rule is the same in every language: protect shared data with a lock, or use an operation documented to be atomic.

What a lock must do

A lock has two operations, acquire and release, and three requirements. Mutual exclusion: at most one thread is between acquire and release at any time. Progress: if the lock is free and threads want it, one of them gets it; they don't all wait forever. Bounded waiting: no thread is passed over indefinitely while others take the lock again and again. Then there's performance, which matters because locks sit on the hottest paths in a program. In code, the critical section should always be written so that the release can't be skipped: with lock: in Python, a scoped guard in C++ and Rust, defer mu.Unlock() in Go.

Building one from loads and stores

The obvious lock checks a variable and, if it's free, sets it. The example's model checker finds the flaw in four steps: both threads see the lock free before either sets it, and both walk in. Giving each thread its own flag, raised before waiting for the other's to drop, keeps them out of each other's way and introduces a new failure: if both raise their flags at once, each waits for the other forever. That's a deadlock. Gary Peterson's algorithm of 1981 adds one shared variable, turn. Each thread raises its flag, then gives the turn to the other, then waits while the other's flag is up and it's the other's turn. If both arrive together, whoever wrote turn last waits. The checker confirms it in all 26 reachable states: never two threads in the critical section, and never a state where neither can move.

from collections import deque

# A model checker. Two threads run a lock algorithm in a loop: entry code, critical section, exit code.
# Each instruction is (description, action); an action takes (i, read, write) and returns the next pc,
# or None to spin in place. We explore every reachable state and look for two threads in the critical
# section at once, or a state where neither thread can ever move again.
def check(name, program, init, crit, store_buffers=False):
    def successors(state):
        pcs, mem, bufs = state
        for i in (0, 1):
            if store_buffers and bufs[i]:                          # the hardware drains a buffered store
                (var, val), rest = bufs[i][0], bufs[i][1:]
                m = dict(mem); m[var] = val
                drained = tuple(rest if k == i else bufs[k] for k in (0, 1))
                yield (pcs, tuple(sorted(m.items())), drained), f"T{i + 1}'s {var}={val} reaches memory"
            desc, act = program[pcs[i]]
            m, b = dict(mem), [list(x) for x in bufs]
            def read(var):                                         # a thread sees its own buffered stores
                for v, val in reversed(b[i]):
                    if v == var: return val
                return m[var]
            def write(var, val):
                if store_buffers: b[i].append((var, val))
                else: m[var] = val
            if desc == "fence" and b[i]: continue                  # a fence waits for the buffer to drain
            nxt = act(i, read, write)
            if nxt is None: continue                               # spinning: no change of state
            p = list(pcs); p[i] = nxt % len(program)
            yield (tuple(p), tuple(sorted(m.items())), tuple(tuple(x) for x in b)), f"T{i + 1} {desc}"
    start = ((0, 0), tuple(sorted(init.items())), ((), ()))
    parent, todo, stuck = {start: None}, deque([start]), None
    while todo:
        s = todo.popleft()
        if s[0] == (crit, crit):
            path = []
            while parent[s]: s, step = parent[s]; path.append(step)
            print(f"{name}: BOTH IN THE CRITICAL SECTION after {len(path)} steps "
                  f"({len(parent)} states searched)")
            for step in reversed(path): print(f"   {step}")
            return
        nexts = list(successors(s))
        if not nexts and stuck is None: stuck = s
        for n, step in nexts:
            if n not in parent: parent[n] = (s, step); todo.append(n)
    if stuck:
        path, s = [], stuck
        while parent[s]: s, step = parent[s]; path.append(step)
        print(f"{name}: mutual exclusion holds, but it can DEADLOCK: " + "; ".join(reversed(path)))
    else:
        print(f"{name}: mutual exclusion holds and no deadlock, in all {len(parent)} reachable states")

other = lambda i: f"flag{1 - i}"
naive = [("sees lock free",  lambda i, r, w: 1 if r("lock") == 0 else None),
         ("sets lock",       lambda i, r, w: (w("lock", 1), 2)[1]),
         ("in critical section", lambda i, r, w: 3),
         ("clears lock",     lambda i, r, w: (w("lock", 0), 0)[1])]
flags = [("raises its flag", lambda i, r, w: (w(f"flag{i}", 1), 1)[1]),
         ("passes the wait (other flag down)", lambda i, r, w: 2 if r(other(i)) == 0 else None),
         ("in critical section", lambda i, r, w: 3),
         ("lowers its flag", lambda i, r, w: (w(f"flag{i}", 0), 0)[1])]
peterson = [("raises its flag", lambda i, r, w: (w(f"flag{i}", 1), 1)[1]),
            ("gives the turn away", lambda i, r, w: (w("turn", 1 - i), 2)[1]),
            ("passes the wait (other flag down, or its turn)",
             lambda i, r, w: 3 if r(other(i)) == 0 or r("turn") == i else None),
            ("in critical section", lambda i, r, w: 4),
            ("lowers its flag", lambda i, r, w: (w(f"flag{i}", 0), 0)[1])]
def test_and_set(i, r, w):                                         # one atomic instruction
    old = r("lock"); w("lock", 1)
    return 1 if old == 0 else None
tas = [("test-and-set", test_and_set),
       ("in critical section", lambda i, r, w: 2),
       ("clears lock", lambda i, r, w: (w("lock", 0), 0)[1])]
fenced = peterson[:2] + [("fence", lambda i, r, w: 3)] + peterson[2:]

check("check-then-set lock", naive, {"lock": 0}, crit=2)
check("two flags", flags, {"flag0": 0, "flag1": 0}, crit=2)
check("Peterson's algorithm", peterson, {"flag0": 0, "flag1": 0, "turn": 0}, crit=3)
check("atomic test-and-set", tas, {"lock": 0}, crit=1)
print()
both = {"flag0": 0, "flag1": 0, "turn": 0}
check("Peterson with store buffers", peterson, both, crit=3, store_buffers=True)
check("Peterson with buffers and a fence", fenced, both, crit=4, store_buffers=True)

check-then-set lock: BOTH IN THE CRITICAL SECTION after 4 steps (14 states searched)
   T1 sees lock free
   T2 sees lock free
   T1 sets lock
   T2 sets lock
two flags: mutual exclusion holds, but it can DEADLOCK: T1 raises its flag; T2 raises its flag
Peterson's algorithm: mutual exclusion holds and no deadlock, in all 26 reachable states
atomic test-and-set: mutual exclusion holds and no deadlock, in all 5 reachable states

Peterson with store buffers: BOTH IN THE CRITICAL SECTION after 6 steps (97 states searched)
   T1 raises its flag
   T1 gives the turn away
   T1 passes the wait (other flag down, or its turn)
   T2 raises its flag
   T2 gives the turn away
   T2 passes the wait (other flag down, or its turn)
Peterson with buffers and a fence: mutual exclusion holds and no deadlock, in all 53 reachable states

Real hardware breaks it

Peterson's proof assumes that a store is visible to the other thread as soon as it happens. On a real multicore processor it isn't. Each core puts its stores in a store buffer and carries on, and the stores reach the shared cache, and so the other core, a little later (chapter 7). The example models that, and the checker finds a run in six steps with no store reaching memory at all. Each thread raises its flag and gives the turn away into its own buffer, then reads the other's flag from memory, sees 0, and enters.

The fix is a fence, an instruction that makes a core wait until its buffered stores are visible before it performs later loads: MFENCE on x86, DMB on ARM. With a fence between giving the turn away and reading the other's flag, the checker again finds no bad state. In practice nobody writes Peterson's algorithm; it handles only two threads, and the atomic instructions of chapter 7 make locks much simpler. The lesson is the method: reasoning about concurrent code means reasoning about every interleaving and about the memory model, and a model checker is the only reliable way to do either for anything beyond a few lines.

Test-and-set and spinning

An atomic test-and-set writes 1 to the lock and returns the old value in one indivisible step, so exactly one thread sees the old 0 and gets the lock. The checker confirms it in 5 states. A lock that loops on test-and-set until it succeeds is a spinlock. Two refinements are standard. Test and test-and-set spins on an ordinary read and attempts the atomic only when the lock looks free, because every atomic write steals the cache line from the other cores, while plain reads let every waiting core spin on its own cached copy. And a ticket lock gives each arriving thread a number from a fetch-and-add and serves them in order, which guarantees bounded waiting. Spinlocks make sense when critical sections are a few hundred nanoseconds and the lock holder can't be descheduled, which is why kernels use them with preemption disabled. In user space, the holder can be preempted at any moment, and every spinner then burns its entire time slice waiting for a thread that isn't running.

Sleeping instead of spinning: the futex

A lock that puts waiters to sleep needs the kernel, but going to the kernel for every acquire would cost a system call each time (chapter 2). Linux's futex, a "fast user-space mutex", added in 2002, avoids that. The lock is an ordinary integer in the process's memory. An uncontended acquire or release is a single atomic instruction in user space, about 20 ns, with no system call. Only when a thread finds the lock taken does it call futex(FUTEX_WAIT) to sleep until the value changes, and the releasing thread calls futex(FUTEX_WAKE) only if someone is waiting. glibc's pthread_mutex, Go's sync.Mutex, Rust's standard mutex and Python's threading.Lock all work this way on Linux; macOS has an equivalent primitive in os_unfair_lock. Most of them are adaptive: they spin briefly in case the holder is about to release, then sleep.

Locks at scale

A lock turns its critical section into serial code, and Amdahl's law (chapter 15 of The Engineer's Mill) then caps the speed-up. If 10% of the work happens under one lock, no number of cores makes the program more than 10 times faster, and contention makes it worse: the lock's cache line bounces between cores and waiters pile up in the kernel. The remedies are to hold locks for less time, never across I/O or calls into unknown code; to split one lock into many, such as one per hash bucket or per account, which is lock striping; to give each thread its own data and combine it only when needed, as per-thread counters do; and to choose structures built for concurrent reading, such as read-copy-update in the Linux kernel. Reader-writer locks look like an easy win and often aren't, because every reader still writes to the lock's shared counter. Finer locking also creates more ways to deadlock, the subject of chapter 10.

Waiting for a condition

A consumer that finds a queue empty has to wait. Spinning on the queue wastes a core; sleeping for 10 ms and checking again adds up to 10 ms of delay and still wastes wake-ups. A condition variable lets a thread sleep until another thread says the state may have changed. It's always used with a lock and a condition on shared state. A thread holding the lock checks the condition; if it's false, it calls wait, which atomically releases the lock and puts the thread to sleep, and reacquires the lock before returning. Another thread that changes the state, under the same lock, calls signal (notify in Python and Java) to wake one waiter, or broadcast (notify_all) to wake them all.

The atomic release-and-sleep is the whole point. If a thread checked the condition, released the lock and then went to sleep in three separate steps, another thread could change the state and signal in between, the signal would find no one waiting and be lost, and the first thread would sleep forever (exercise 9.1).

Mesa semantics, and why the check goes in a loop

When a waiting thread is signalled, it doesn't run immediately. It becomes ready, and it must win the lock back like any other thread. In between, another thread can take the lock and change the state again. This is called Mesa semantics, after the language in which Butler Lampson and David Redell described it in 1980, and it's what POSIX threads, Java, Python and Go all provide. The alternative, Hoare semantics, hands the lock straight to the woken thread, which is easier to reason about and slower to implement, and almost no real system uses it. Under Mesa semantics a signal is only a hint that the condition may now be true. POSIX even allows spurious wake-ups, from wait returning with no signal at all. So the condition must be checked again after every wake-up, in a loop: while not condition: cv.wait().

Checked, then run

The example models one producer that puts two items and two consumers that take one each, through a buffer that holds one item, with a mutex and condition variables that follow Mesa semantics. With if and one condition variable, the checker finds the trace in the figure in 14 steps. With while and one condition variable it finds a different bug: a deadlock with every thread asleep. With while and two condition variables it checks all 139 reachable states and finds nothing. The correct version then runs for real with Python's threading.Condition, 30,000 items through a four-slot buffer to three consumers, and every item arrives exactly once.

import textwrap, threading
from collections import deque

# A bounded buffer holding one item: one producer puts 2 items, two consumers take one each.
# The checker models a mutex and condition variables with the semantics real systems use
# (Mesa semantics): signal() only wakes a waiter, which must then win the lock again.
def program(role, check, cvs):
    full, empty = ("cv", "cv") if cvs == 1 else ("fill", "space")
    if role == "producer":
        one = [("lock",), (check, lambda n: n == 1, empty), ("put",), ("signal", full), ("unlock",)]
        return one * 2
    return [("lock",), (check, lambda n: n == 0, full), ("get",), ("signal", empty), ("unlock",)]

def explore(check, cvs):
    label = f"{check:5} with {cvs} condition variable{'s' if cvs > 1 else ''}"
    def show(steps): print(textwrap.indent(textwrap.fill("; ".join(steps), 92), "   "))
    progs = [program(role, check, cvs) for role in ("producer", "consumer", "consumer")]
    names = ["P", "C1", "C2"]
    # state: (pcs, status per thread, item count, lock holder, waiters per condition variable)
    start = ((0, 0, 0), ("run",) * 3, 0, None, ())
    parent, todo = {start: None}, deque([start])
    def trace(s):
        path = []
        while parent[s]: s, step = parent[s]; path.append(step)
        return list(reversed(path))
    while todo:
        s = todo.popleft()
        pcs, status, count, holder, waiters = s
        moves = []
        for i, prog in enumerate(progs):
            if pcs[i] == len(prog): continue
            op, st = prog[pcs[i]], status[i]
            def go(pc=pcs[i] + 1, stat="run", cnt=count, hold=holder, wait=waiters, note=""):
                p = list(pcs); p[i] = pc; t = list(status); t[i] = stat
                moves.append(((tuple(p), tuple(t), cnt, hold, wait), f"{names[i]} {note or op[0]}"))
            if st.startswith("waiting"): continue                              # asleep until signalled
            if st == "woken":                                                  # must win the lock back
                if holder is None:
                    again = pcs[i] if op[0] == "while" else pcs[i] + 1         # while: re-check; if: go on
                    go(pc=again, hold=i, note="wakes and takes the lock")
                continue
            if op[0] == "lock" and holder is None: go(hold=i, note="takes the lock")
            elif op[0] == "unlock": go(hold=None, note="releases the lock")
            elif op[0] in ("if", "while"):
                if op[1](count): go(pc=pcs[i], stat="waiting", hold=None,
                                    wait=tuple(sorted(waiters + ((op[2], i),))), note=f"waits on {op[2]}")
                else: go(note="can go ahead")
            elif op[0] == "put": go(cnt=count + 1, note="puts an item")
            elif op[0] == "get":
                if count == 0:
                    print(f"{label}: BUG, a consumer took from an empty buffer")
                    show(trace(s) + [f"{names[i]} takes from the empty buffer"])
                    return
                go(cnt=count - 1, note="takes the item")
            elif op[0] == "signal":
                sleepers = [w for w in waiters if w[0] == op[1]]
                if not sleepers: go(note=f"signals {op[1]} (no one waiting)")
                for w in sleepers:                                             # the system picks any waiter
                    t = list(status); t[w[1]] = "woken"
                    p = list(pcs); p[i] += 1
                    moves.append(((tuple(p), tuple(t), count, holder, tuple(x for x in waiters if x != w)),
                                  f"{names[i]} signals {op[1]}, waking {names[w[1]]}"))
        if not moves and any(pc < len(pr) for pc, pr in zip(pcs, progs)):
            print(f"{label}: DEADLOCK, everyone left is asleep")
            show(trace(s))
            return
        for n, step in moves:
            if n not in parent: parent[n] = (s, step); todo.append(n)
    print(f"{label}: correct in all {len(parent):,} reachable states")

explore("if", 1)
explore("while", 1)
explore("while", 2)

# The correct version, run for real: Python's threading.Condition has the same Mesa semantics
buf, CAP = deque(), 4
lock = threading.Lock(); has_item = threading.Condition(lock); has_space = threading.Condition(lock)
def producer(items):
    for x in items:
        with lock:
            while len(buf) == CAP: has_space.wait()
            buf.append(x); has_item.notify()
totals = [0, 0, 0]
def consumer(k, n):
    for _ in range(n):
        with lock:
            while not buf: has_item.wait()
            totals[k] += buf.popleft(); has_space.notify()
threads = [threading.Thread(target=producer, args=(range(1, 30_001),))] + \
          [threading.Thread(target=consumer, args=(k, 10_000)) for k in range(3)]
for t in threads: t.start()
for t in threads: t.join()
print(f"\nreal threads, 3 consumers sharing 30,000 items through a 4-slot buffer: sum {sum(totals):,} "
      f"(expected {30_000 * 30_001 // 2:,})")

if    with 1 condition variable: BUG, a consumer took from an empty buffer
   C1 takes the lock; C1 waits on cv; P takes the lock; P can go ahead; P puts an item; P
   signals cv, waking C1; P releases the lock; C2 takes the lock; C2 can go ahead; C2 takes the
   item; C2 signals cv (no one waiting); C2 releases the lock; C1 wakes and takes the lock; C1
   takes from the empty buffer
while with 1 condition variable: DEADLOCK, everyone left is asleep
   C1 takes the lock; C1 waits on cv; C2 takes the lock; C2 waits on cv; P takes the lock; P
   can go ahead; P puts an item; P signals cv, waking C1; P releases the lock; P takes the
   lock; P waits on cv; C1 wakes and takes the lock; C1 can go ahead; C1 takes the item; C1
   signals cv, waking C2; C1 releases the lock; C2 wakes and takes the lock; C2 waits on cv
while with 2 condition variables: correct in all 139 reachable states

real threads, 3 consumers sharing 30,000 items through a 4-slot buffer: sum 450,015,000 (expected 450,015,000)

One condition variable or two

The deadlock is subtler than the if bug. Producers wait for space and consumers wait for items, and with only one condition variable they all wait on the same one. In the trace, both consumers wait, the producer puts an item, signals, and then waits itself because the buffer is full. Consumer 1 takes the item and signals, intending to wake the producer, but the signal wakes consumer 2 instead, which finds the buffer empty and goes back to sleep. Now all three are asleep and nobody will ever signal. A signal must wake a thread that can act on it, so threads waiting for different conditions need different condition variables: one for "there's space", one for "there's an item". notify_all also fixes it, because it wakes everyone, but it does so at the cost of waking every waiter for every change, the thundering herd.

Semaphores

Edsger Dijkstra introduced the semaphore in 1965: an integer with two atomic operations, P (wait, or down), which decrements it and blocks while it would go negative, and V (signal, or up), which increments it and wakes a waiter. A semaphore that starts at 1 is a lock. One that starts at n admits n threads at a time, which is a natural limit on a pool of resources, such as ten database connections or four concurrent downloads. Unlike a condition variable, a semaphore remembers: a V with no one waiting isn't lost but raises the count for the next P. A bounded buffer of n slots needs three semaphores: slots starting at n, items starting at 0, and a mutex starting at 1 for the buffer itself. The order of the waits matters, as exercise 9.2 shows.

In practice, write condition-variable code rarely, and reach for the tools built from these primitives: blocking queues such as Python's queue.Queue and Java's BlockingQueue; channels (chapter 11); barriers, which make a group of threads wait until all of them arrive, as chapter 10's example does; countdown latches; and futures. The thread pool in this stage's deliverable is a blocking queue of tasks and a fixed set of threads taking from it.

The dining philosophers

Dijkstra's puzzle from 1965: philosophers sit at a round table with one fork between each pair, and each needs both neighbouring forks to eat. If every philosopher picks up the left fork and then the right, there's a moment when all of them hold a left fork and wait for a right one that their neighbour is holding, and they wait forever. The example's checker explores every order in which the philosophers can act and finds that state after 14 states with three philosophers and 82 with five. Then it makes one change: every philosopher picks up the lower-numbered of their two forks first. Now the last philosopher, whose forks are numbered n − 1 and 0, reaches for fork 0 first, the circle is broken, and the checker finds no deadlock in any reachable state.

import random, threading
from collections import deque

# 1. Dining philosophers: each picks up one fork, then the other, eats, and puts both down.
def dine(n, ordered):
    def forks(p):                                            # left fork p, right fork p+1 (mod n)
        a, b = p, (p + 1) % n
        return (min(a, b), max(a, b)) if ordered else (a, b) # ordered: always the lower number first
    start = ((0,) * n, (None,) * n)                          # (step of each philosopher, fork owners)
    seen, todo = {start}, deque([start])
    while todo:
        steps, owner = todo.popleft()
        moves = []
        for p in range(n):
            first, second = forks(p)
            o = list(owner); s = list(steps)
            if steps[p] == 0 and owner[first] is None: o[first] = p; s[p] = 1        # pick up first fork
            elif steps[p] == 1 and owner[second] is None: o[second] = p; s[p] = 2    # pick up second
            elif steps[p] == 2: o[first] = o[second] = None; s[p] = 0                # eat, put both down
            else: continue
            moves.append((tuple(s), tuple(o)))
        if not moves:
            return f"DEADLOCK, found after {len(seen)} states: everyone holds one fork, waiting for another"
        for m in moves:
            if m not in seen: seen.add(m); todo.append(m)
    return f"no deadlock in any of the {len(seen)} reachable states"
for n in (3, 5):
    print(f"{n} philosophers, left fork first:   {dine(n, ordered=False)}")
    print(f"{n} philosophers, lower fork first:  {dine(n, ordered=True)}")

# 2. Detecting a deadlock after the fact: a cycle in the graph of who waits for whom
holds = {"L1": "T1", "L2": "T2", "L3": "T3", "L4": "T4"}
waits = {"T1": "L2", "T2": "L3", "T3": "L1", "T4": "L1"}
def find_cycle(start):
    path, t = [], start
    while t in waits and t not in path:
        path.append(t); t = holds[waits[t]]
    return path[path.index(t):] if t in path else None
cycle = next(c for c in (find_cycle(t) for t in waits) if c)
print("\nwait-for cycle: " + " -> ".join(f"{t} waits for {waits[t]} (held by {holds[waits[t]]})"
                                        for t in cycle))
print("T4 is stuck too, but only because it waits on the cycle; breaking the cycle frees it")

# 3. Real threads, real locks, opposite order. A barrier makes both take their first lock first.
A, B = threading.Lock(), threading.Lock()
both_hold_one, both_tried = threading.Barrier(2), threading.Barrier(2)
report = {}
def worker(name, first, second, align):
    with first:
        if align: both_hold_one.wait()                       # make the bad timing certain
        got = second.acquire(timeout=0.5)                    # give up after half a second
        report[name] = "got both locks" if got else "timed out waiting: deadlock"
        if got: second.release()
        if align: both_tried.wait()                          # neither lets go before both have tried
for label, orders, align in (("opposite order", ((A, B), (B, A)), True),
                             ("same order", ((A, B), (A, B)), False)):
    ts = [threading.Thread(target=worker, args=(f"T{k + 1}", *orders[k], align)) for k in range(2)]
    for t in ts: t.start()
    for t in ts: t.join()
    print(f"\n{label}: " + "; ".join(f"{k} {v}" for k, v in sorted(report.items())))

# 4. Livelock: on a conflict each thread politely lets go and retries. In lockstep, forever.
def polite(backoff, rounds=50):
    random.seed(10)
    delay = [0, 0]
    for r in range(rounds):
        trying = [t for t in (0, 1) if delay[t] == 0]
        if len(trying) == 1: return f"thread {trying[0] + 1} got both locks in round {r + 1}"
        for t in (0, 1): delay[t] = max(0, delay[t] - 1)
        if len(trying) == 2 and backoff:                     # both collided: each waits a random time
            for t in trying: delay[t] = random.randint(0, 3)
    return f"no one finished in {rounds} rounds: both busy, no progress"
print(f"\nlivelock, retrying at once:      {polite(False)}")
print(f"livelock, with random backoff:   {polite(True)}")

3 philosophers, left fork first:   DEADLOCK, found after 14 states: everyone holds one fork, waiting for another
3 philosophers, lower fork first:  no deadlock in any of the 12 reachable states
5 philosophers, left fork first:   DEADLOCK, found after 82 states: everyone holds one fork, waiting for another
5 philosophers, lower fork first:  no deadlock in any of the 70 reachable states

wait-for cycle: T1 waits for L2 (held by T2) -> T2 waits for L3 (held by T3) -> T3 waits for L1 (held by T1)
T4 is stuck too, but only because it waits on the cycle; breaking the cycle frees it

opposite order: T1 timed out waiting: deadlock; T2 timed out waiting: deadlock

same order: T1 got both locks; T2 got both locks

livelock, retrying at once:      no one finished in 50 rounds: both busy, no progress
livelock, with random backoff:   thread 1 got both locks in round 2

The four conditions

Edward Coffman and his colleagues showed in 1971 that a deadlock needs four conditions at once. Mutual exclusion: a resource can be held by only one thread. Hold and wait: a thread holds one resource while waiting for another. No preemption: a resource can't be taken away from the thread holding it. Circular wait: a cycle of threads, each waiting for a resource the next one holds. Remove any one and deadlock is impossible.

In practice, circular wait is the condition to break. Give every lock a place in one global order and always acquire locks in that order, as the philosophers did with fork numbers. When the locks belong to objects, order them by something stable such as an ID: a transfer between two accounts locks the account with the lower ID first, whichever direction the money flows. Hold and wait can be broken by acquiring every lock a task needs in one step, which is hard when the set isn't known in advance. No preemption can be broken by trying for a lock with a timeout, or with a non-blocking try-lock, and releasing everything held on failure before trying again. Dijkstra's banker's algorithm avoids deadlock by refusing any request that could lead to one, but it needs to know every thread's maximum demand in advance, so general-purpose systems don't use it.

Finding a deadlock

The alternative to preventing deadlocks is detecting them. Record which thread holds each lock and which lock each thread waits for, and look for a cycle, as the example's find_cycle does. Databases work this way, because transactions lock rows in whatever order the queries touch them. PostgreSQL waits a second, checks for a cycle, and aborts one transaction with "deadlock detected" so the others can continue. Runtimes help with diagnosis too: jstack reports a Java-level deadlock in a thread dump, Go's runtime stops with "all goroutines are asleep - deadlock!", and py-spy dump shows every Python thread's stack. The Linux kernel goes further with lockdep, which records the order in which locks are taken while the kernel runs and reports an order that could deadlock the first time it occurs, before any deadlock has happened.

The example also builds a real deadlock with two Python locks taken in opposite orders. A barrier makes sure each thread holds its first lock before either asks for its second, so the bad timing is certain instead of rare. Each thread asks for its second lock with a timeout and gives up after half a second, a simple form of detection. With both threads taking the locks in the same order, both finish.

Livelock and starvation

In a livelock the threads aren't blocked. They keep reacting to each other, and nothing gets done. Two threads that each take one lock, find the other taken, politely release theirs and retry at once can repeat that dance indefinitely if they stay in step, which the example's lockstep simulation does for 50 rounds. The fix is to break the symmetry with randomness: on a collision, each waits a random time before retrying, and doubles the range after each further collision. That's exponential backoff with jitter, the same rule Ethernet used for colliding transmissions and that well-behaved clients use for retrying failed requests. With it, one thread wins in the second round.

In starvation, the system makes progress but one thread never does, because the rules always favour someone else: readers that keep a reader-writer lock busy so a writer never gets in, an unfair lock that the same thread keeps winning, a low-priority job behind an endless stream of high-priority ones. The fixes are fairness and aging, such as serving waiters in order or boosting a waiter's priority as it waits, as the multi-level feedback queue's boost did in chapter 5.

def transfer(a, b, amount):
    first, second = (a, b) if a.id < b.id else (b, a)
    with first.lock, second.lock:      # lower ID first, whichever way the money moves
        a.balance -= amount
        b.balance += amount

Concurrency without threads

A server handling ten thousand connections spends almost all its time waiting: for a request to arrive, for a database to answer, for a slow client to accept its reply. With a thread per connection, each wait holds a thread, with its stack and its share of context switches (chapter 4). An event loop handles all of them on one thread. It keeps a queue of work that's ready to run and a list of timers, asks the kernel which connections have data with a single call such as epoll_wait or kevent (chapter 18), and runs the code waiting for each. No code ever blocks; code that would wait instead registers interest and returns to the loop. nginx, Redis and Node.js are built this way.

Early event-driven code was written as callbacks, functions to run when an event happens, and deeply nested callbacks are hard to read and harder to debug. Promises, or futures, made them composable, and async/await made them look like ordinary sequential code: C# added it in 2012, Python in 2015, JavaScript in 2017 and Rust in 2019. An async function is a coroutine, and each await is a point where it can pause and hand control back to the loop until the thing it's waiting for is ready.

An event loop in a dozen lines

The example's loop is the idea with nothing else in the way. Each task is a Python generator. When it would wait, it yields a request to the loop, here "wake me in 0.3 seconds", and the loop keeps a heap of timers ordered by when they're due. The loop pops the earliest, advances its clock to that time, and resumes that task until it yields again. Three requests that wait 0.3, 0.1 and 0.2 seconds all start at once and finish in order of their waits, and the whole thing takes 0.3 seconds, not 0.6.

A real loop such as asyncio adds the other kind of waiting: instead of timers alone, it registers sockets with the kernel and asks which are readable or writable, then resumes the coroutines waiting on them. The example's second part runs a ticker and a worker under asyncio. When the worker waits with await asyncio.sleep, the ticker keeps ticking in between. When it calls time.sleep instead, which blocks the thread, nothing else runs until it returns.

import asyncio, heapq, queue, threading, time

# 1. An event loop from scratch. Tasks are generators; each `yield` hands control back to the loop
#    with a request: ("sleep", seconds). The loop keeps a clock and a heap of timers. No threads.
now = 0.0
def loop(tasks):
    global now
    timers, n = [], 0
    for task in tasks: heapq.heappush(timers, (0.0, (n := n + 1), task))
    while timers:
        now, _, task = heapq.heappop(timers)            # jump the clock to the next thing that's due
        try:
            kind, arg = next(task)                      # run the task until it yields again
            heapq.heappush(timers, (now + arg, (n := n + 1), task))
        except StopIteration:
            pass
    return now
log = []
def fetch(name, seconds):
    log.append(f"   t = {now:.1f} s   {name} sends its request")
    yield ("sleep", seconds)                            # waiting for the network: let others run
    log.append(f"   t = {now:.1f} s   {name} gets its reply")
total = loop([fetch("A", 0.3), fetch("B", 0.1), fetch("C", 0.2)])
print("three requests on one thread, waiting 0.3, 0.1 and 0.2 s for replies:")
print("\n".join(log))
print(f"finished at t = {total:.1f} s: the waits overlap, so the total is the longest wait, not their sum")

# 2. asyncio is the same idea. A blocking call inside a coroutine stalls every other task.
async def ticker(events):
    for i in range(3):
        events.append(f"tick {i}"); await asyncio.sleep(0.02)
async def worker(events, blocking):
    events.append("worker starts")
    if blocking: time.sleep(0.1)                        # blocks the whole thread, and so the loop
    else: await asyncio.sleep(0.1)                      # yields to the loop while it waits
    events.append("worker done")
async def main(blocking):
    events = []
    await asyncio.gather(ticker(events), worker(events, blocking))
    return ", ".join(events)
print(f"\nwith await asyncio.sleep: {asyncio.run(main(False))}")
print(f"with time.sleep:          {asyncio.run(main(True))}")

# 3. An actor owns its state and handles one message at a time from its mailbox: no locks needed
def account(mailbox, replies):
    balance = 0
    while (msg := mailbox.get()) != "stop":
        kind, amount = msg
        if kind == "deposit": balance += amount
        elif kind == "withdraw" and balance >= amount: balance -= amount
    replies.put(balance)
mailbox, replies = queue.Queue(), queue.Queue()
actor = threading.Thread(target=account, args=(mailbox, replies)); actor.start()
senders = [threading.Thread(target=lambda: [mailbox.put(("deposit", 1)) for _ in range(10_000)])
           for _ in range(4)]
for s in senders: s.start()
for s in senders: s.join()
mailbox.put("stop"); actor.join()
print(f"\nfour threads sent 10,000 deposits each to one actor: balance {replies.get():,}")

# 4. Channels connect stages that share nothing: numbers -> squares -> a running total
async def pipeline():
    squares_in, totals_in = asyncio.Queue(maxsize=1), asyncio.Queue(maxsize=1)   # maxsize=1: a hand-off
    async def numbers():
        for x in range(1, 6): await squares_in.put(x)
        await squares_in.put(None)
    async def squarer():
        while (x := await squares_in.get()) is not None: await totals_in.put(x * x)
        await totals_in.put(None)
    async def summer():
        total, seen = 0, []
        while (x := await totals_in.get()) is not None: total += x; seen.append(total)
        return seen
    _, _, seen = await asyncio.gather(numbers(), squarer(), summer())
    return seen
print(f"running totals of squares through two channels: {asyncio.run(pipeline())}")

three requests on one thread, waiting 0.3, 0.1 and 0.2 s for replies:
   t = 0.0 s   A sends its request
   t = 0.0 s   B sends its request
   t = 0.0 s   C sends its request
   t = 0.1 s   B gets its reply
   t = 0.2 s   C gets its reply
   t = 0.3 s   A gets its reply
finished at t = 0.3 s: the waits overlap, so the total is the longest wait, not their sum

with await asyncio.sleep: tick 0, worker starts, tick 1, tick 2, worker done
with time.sleep:          tick 0, worker starts, worker done, tick 1, tick 2

four threads sent 10,000 deposits each to one actor: balance 40,000
running totals of squares through two channels: [1, 5, 14, 30, 55]

The price: cooperation

An event loop is cooperative: a task runs until it chooses to yield, so one task that doesn't yield stops all the others. A blocking call, a slow library that does synchronous network or file I/O, or a long computation inside a coroutine freezes every connection on that loop, which is why Node.js documentation repeats "don't block the event loop". The fixes are to use asynchronous libraries throughout, and to move blocking or heavy work to a thread or process with asyncio.to_thread or run_in_executor. Async also spreads through a program: a function that awaits must itself be async, so its callers must be too. Bob Nystrom called this the problem of function colour.

In return, code between two awaits runs without interruption, so there are no data races within a single loop. But interleaving hasn't gone away; it's just confined to the await points. A check, then an await, then an act is the chapter 7 race again (exercise 11.1).

Actors

An actor is a unit of computation that owns its state outright and communicates only by messages. It has a mailbox, handles one message at a time, and may change its state, send messages and create other actors in response. Carl Hewitt proposed the model in 1973. Erlang, designed at Ericsson in 1986 for telephone switches, made it practical, and Akka brought it to the JVM. Because only the actor touches its state, no lock is needed: the example's account actor takes 40,000 deposits from four threads, one at a time, and ends with exactly 40,000. Erlang adds the other half of the idea: actors are isolated, so one that crashes takes nothing else with it, and a supervisor actor restarts it in a known state. That's how Erlang systems stay up for years.

Channels

A channel is a typed pipe between concurrent tasks. Tony Hoare described communicating sequential processes, CSP, in 1978, and Go made channels a core feature, with the advice "don't communicate by sharing memory; share memory by communicating". An unbuffered channel is a rendezvous: the sender waits until a receiver takes the value. A buffered channel is a bounded queue. Either way, a fast stage blocks when the next one falls behind, which is backpressure: the whole pipeline runs at the speed of its slowest stage, with bounded memory. The example's pipeline passes numbers through two channels with room for one item each, to a stage that squares them and on to one that keeps a running total. Go's select waits on several channels at once, and closing a channel tells its readers that no more values are coming, as the example's None does.

None of these models wins everywhere. Threads and locks suit shared in-memory structures and CPU-bound parallel work. Event loops suit many connections that mostly wait. Actors suit long-lived stateful entities that should fail independently, and channels suit pipelines. Real systems mix them: Go runs goroutines, which are threads, connected by channels; a Node.js server runs an event loop with a pool of worker threads behind it; a Python service runs asyncio with a thread pool for blocking calls.

Why translate

Translation solves several problems at once. Isolation: a process can reach only the memory its tables map, so it can't read or corrupt another's. Relocation: every program can be linked to run at the same addresses, wherever its memory physically is. Sparseness: a 64-bit address space is huge, and a process uses a few scattered regions of it, code at the bottom and stacks near the top, without paying for the gaps. Sharing: the same physical memory can appear in many processes, as a shared library's code does, or as a parent's pages do after fork (chapter 13). And overcommitment: the kernel can promise memory and supply it only when it's touched, or take it back by moving it to disk.

Early machines translated with a single base and limit per process, which was simple but required each process's memory to be one contiguous piece. Segmentation used several such pieces and suffered external fragmentation, chapter 15's problem. Paging, used by every modern system, cuts both virtual and physical memory into fixed-size pages, 4 KiB on x86, and lets any virtual page map to any physical frame. ARM processors support 4, 16 and 64 KiB pages, and Apple silicon uses 16 KiB.

Splitting an address

On x86-64, a virtual address has 48 significant bits; newer processors and kernels can enable a fifth level and 57 bits. The low 12 bits are the offset within a 4 KiB page and pass through translation unchanged. The 36 bits above them are the virtual page number, and the hardware uses them as four 9-bit indices, one per level of a tree of tables. Each table is exactly one page: 512 entries of 8 bytes. An entry holds the physical frame number of the next table, or, at the last level, of the page itself, plus permission and status bits: present, writable, accessible from user mode, no-execute, and the accessed and dirty bits that the hardware sets when the page is used or written.

Walking the tables

The kernel loads the physical address of a process's top-level table into CR3 (on ARM, TTBR0) when it switches to that process, which is how a context switch changes address spaces (chapter 4). The memory management unit then walks the tree on every access, four dependent memory reads before the program's own read can even start. That would make every load five times slower, so processors cache recent translations in the TLB, the subject of chapter 13. The example builds the tree as nested dictionaries that exist only where something is mapped, maps three pages with different permissions, and translates five accesses.

# x86-64 paging: a 48-bit virtual address is four 9-bit table indices and a 12-bit offset
PAGE = 4096
def split(va):
    return [(va >> shift) & 0x1FF for shift in (39, 30, 21, 12)], va & 0xFFF

class PageTables:
    """Four levels of 512-entry tables. Only the tables a process actually uses exist."""
    def __init__(self):
        self.root, self.tables, self.next_frame = {}, 1, 0x1000
    def map(self, va, frame, perms):
        (i1, i2, i3, i4), _ = split(va)
        node = self.root
        for i in (i1, i2, i3):
            if i not in node: node[i] = {}; self.tables += 1        # allocate a table on demand
            node = node[i]
        node[i4] = (frame, perms)
    def translate(self, va, access):
        (i1, i2, i3, i4), offset = split(va)
        node, reads = self.root, 0
        for i in (i1, i2, i3, i4):
            reads += 1                                              # each level is a memory read
            if i not in node: return f"page fault (no mapping; {reads} table reads)"
            node = node[i]
        frame, perms = node
        if access not in perms: return f"protection fault: {access!r} not allowed on a {perms} page"
        return f"physical 0x{frame * PAGE + offset:09x} ({reads} table reads)"

va = 0x7F3A1C2B5E10
idx, off = split(va)
print(f"0x{va:012x} -> table indices {idx}, offset 0x{off:03x}")

pt = PageTables()
pt.map(0x400000, 0x2A1, "r-x")                                     # program code
pt.map(0x601000, 0x3F7, "rw-")                                     # global data
pt.map(0x7FFFFFFDE000, 0x0B2, "rw-")                               # top of the stack
for va, access, what in ((0x400123, "x", "run code"), (0x601010, "w", "write data"),
                         (0x7FFFFFFDEFF8, "w", "push onto the stack"), (0x400123, "w", "write to code"),
                         (0x0, "r", "read address 0 (a null pointer)")):
    print(f"   {what:32} {pt.translate(va, access)}")

# What the page tables themselves cost
print(f"\nthree mapped pages need {pt.tables} page tables: {pt.tables * PAGE // 1024} KiB")
flat = 2 ** 36 * 8                                                  # one 8-byte entry for every page
print(f"one flat table for all 48 bits: 2^36 entries x 8 bytes = {flat // 2 ** 30} GiB, for every process")
big = PageTables()
for page in range(0x10000000 // PAGE, (0x10000000 + 2 ** 30) // PAGE):   # map 1 GiB, contiguous
    big.map(page * PAGE, page, "rw-")
print(f"mapping 1 GiB with 4 KiB pages: {2 ** 30 // PAGE:,} entries in {big.tables} tables "
      f"({big.tables * PAGE / 2 ** 20:.1f} MiB, {big.tables * PAGE / 2 ** 30:.2%} overhead)")
print(f"mapping 1 GiB with 2 MiB pages: {2 ** 30 // 2 ** 21} entries, one level fewer to walk")

0x7f3a1c2b5e10 -> table indices [254, 232, 225, 181], offset 0xe10
   run code                         physical 0x0002a1123 (4 table reads)
   write data                       physical 0x0003f7010 (4 table reads)
   push onto the stack              physical 0x0000b2ff8 (4 table reads)
   write to code                    protection fault: 'w' not allowed on a r-x page
   read address 0 (a null pointer)  page fault (no mapping; 3 table reads)

three mapped pages need 8 page tables: 32 KiB
one flat table for all 48 bits: 2^36 entries x 8 bytes = 512 GiB, for every process
mapping 1 GiB with 4 KiB pages: 262,144 entries in 516 tables (2.0 MiB, 0.20% overhead)
mapping 1 GiB with 2 MiB pages: 512 entries, one level fewer to walk

Faults

When the walk finds an entry that isn't present, the processor raises a page fault and the kernel takes over, with the faulting address in a register. The kernel then decides what the fault means. If the address belongs to a region the process is entitled to, such as heap memory it allocated but never touched, a file it mapped, or a page that was moved out to disk, the kernel supplies the page, fixes the entry and resumes the instruction, and the program never knows. If the address belongs to nothing, the kernel sends SIGSEGV, the segmentation fault. Page zero is left unmapped on purpose, so a null pointer is caught at once: the example's read of address 0 stops after three table reads, because no level 1 table exists for that region.

A protection fault is an access the entry forbids: a write to a read-only page, user-mode access to a kernel page, or an instruction fetch from a page marked no-execute. The example's write to its code page is one. Sometimes the kernel treats it as legitimate, which is how copy-on-write works (chapter 13), and otherwise the result is again SIGSEGV. Marking pages writable or executable but never both, a policy called W^X, is one of the defences against injected code from chapter 18 of The Engineer's Mill.

What the tables cost

A single flat table covering 48 bits would need 2³⁶ entries of 8 bytes, 512 GiB for every process, which is why the table is a tree. The example's process maps three pages and needs only 8 tables, 32 KiB in all, because a table exists only where something below it is mapped. A densely mapped gigabyte needs 516 tables, 2 MiB, which is 0.2% overhead. Larger pages shrink this further: a 2 MiB page is mapped by a level 2 entry directly, skipping the last level, and a 1 GiB page by a level 3 entry. Chapter 13 shows the bigger benefit, for the TLB.

Every process's address space has two halves. The lower half holds the program; the upper half, which user mode can't access, maps the kernel, so that a system call or interrupt doesn't need to switch tables. Since the Meltdown attack of 2018, kernels on affected processors keep most of that upper half unmapped while user code runs, a technique called kernel page-table isolation, which is one reason system calls got slower. On Linux, /proc/<pid>/maps lists every region of a process's lower half, and /proc/<pid>/smaps shows how much of each is actually in memory.

The TLB

The translation lookaside buffer is a small cache of recent translations, each one a virtual page number, its physical frame and its permission bits. It's looked up on every memory access, in parallel with the first-level cache, and a hit costs about a cycle. Modern cores have two levels: a first-level data TLB of around 64 entries and a second-level TLB of 1,500 to 2,000 entries shared by code and data. A miss means a page walk. The processor does it in hardware on x86 and ARM, helped by caches of the upper levels of the tree, and it costs from a dozen cycles, when the tables are in cache, to hundreds, when they're not. How much memory the TLB can cover at once, its reach, is the number of entries times the page size.

Four access patterns

The example models a 1,536-entry TLB with least-recently-used replacement and runs 300,000 accesses in four patterns. Reading 8-byte values in order misses once per 512 accesses, 0.2%, because each 4 KiB page holds 512 of them. Touching one value every 4 KiB misses every time. Random reads in 64 MiB miss 91% of the time, because 64 MiB is 16,384 pages and the TLB holds 1,536; in 1 GiB, 99%. With 2 MiB pages every pattern misses at most 0.2% of the time, because the same TLB now reaches 3 GiB instead of 6 MiB.

import random
from collections import OrderedDict

# A TLB caches recent page translations. Model a 1,536-entry TLB with LRU replacement,
# the size of the second-level TLB on recent x86 cores.
def tlb_misses(addresses, page_size, entries=1536):
    tlb, misses = OrderedDict(), 0
    for a in addresses:
        page = a // page_size
        if page in tlb: tlb.move_to_end(page)
        else:
            misses += 1                                           # a page walk: up to 4 memory reads
            tlb[page] = True
            if len(tlb) > entries: tlb.popitem(last=False)
    return misses / len(addresses)

KiB, MiB, GiB = 2 ** 10, 2 ** 20, 2 ** 30
N = 300_000
random.seed(13)
patterns = {
    "sequential 8-byte reads": [i * 8 for i in range(N)],
    "one read every 4 KiB": [i * 4 * KiB for i in range(N)],
    "random reads in 64 MiB": [random.randrange(64 * MiB) for _ in range(N)],
    "random reads in 1 GiB": [random.randrange(GiB) for _ in range(N)],
}
print(f"{f'TLB misses per access, {N:,} accesses each:':49} {'4 KiB pages':>11}   {'2 MiB pages':>11}")
for name, addrs in patterns.items():
    print(f"   {name:46} {tlb_misses(addrs, 4 * KiB):11.2%}   {tlb_misses(addrs, 2 * MiB):11.2%}")
print(f"TLB reach: 1,536 x 4 KiB = {1536 * 4 * KiB / MiB:.0f} MiB; "
      f"1,536 x 2 MiB = {1536 * 2 * MiB / GiB:.0f} GiB")

# Copy-on-write fork: share every page read-only, copy a page only when someone writes to it
def fork(parent_pages, written_by_child):
    child = dict(parent_pages)                                    # copies only the page table
    frames_shared = set(parent_pages.values())
    copies = 0
    for page in written_by_child:
        if child[page] in frames_shared:                          # write fault on a shared page
            child[page] = ("copy", page); copies += 1
    return copies
pages = {p: ("frame", p) for p in range(25_600)}                  # a 100 MiB process, 4 KiB pages
print()
for label, writes in (("calls exec at once", []),
                      ("writes to 1% of its pages", range(0, 25_600, 100)),
                      ("rewrites everything", range(25_600))):
    print(f"fork of a 100 MiB process, child {label:26} {fork(pages, writes):6,} of 25,600 pages copied")

# What faults cost: the average access time with a 100 ns memory, when faults are served from storage
print(f"\n{'average time per memory access':38} {'faults from an SSD':>22} {'faults from a disk':>22}")
print(f"{'':38} {'(100 µs each)':>22} {'(5 ms each)':>22}")
for rate in (1e-6, 1e-4, 1e-3):
    ssd, disk = ((1 - rate) * 100 + rate * cost for cost in (100_000, 5_000_000))
    print(f"   one fault per {1 / rate:>9,.0f} accesses   {ssd:9,.1f} ns ({ssd / 100:5.2f}x) "
          f"{disk:11,.1f} ns ({disk / 100:5.2f}x)")

TLB misses per access, 300,000 accesses each:     4 KiB pages   2 MiB pages
   sequential 8-byte reads                              0.20%         0.00%
   one read every 4 KiB                               100.00%         0.20%
   random reads in 64 MiB                              90.68%         0.01%
   random reads in 1 GiB                               99.44%         0.17%
TLB reach: 1,536 x 4 KiB = 6 MiB; 1,536 x 2 MiB = 3 GiB

fork of a 100 MiB process, child calls exec at once              0 of 25,600 pages copied
fork of a 100 MiB process, child writes to 1% of its pages     256 of 25,600 pages copied
fork of a 100 MiB process, child rewrites everything        25,600 of 25,600 pages copied

average time per memory access             faults from an SSD     faults from a disk
                                                (100 µs each)            (5 ms each)
   one fault per 1,000,000 accesses       100.1 ns ( 1.00x)       105.0 ns ( 1.05x)
   one fault per    10,000 accesses       110.0 ns ( 1.10x)       600.0 ns ( 6.00x)
   one fault per     1,000 accesses       199.9 ns ( 2.00x)     5,099.9 ns (51.00x)

Programs that jump around large amounts of memory, such as hash tables, graph algorithms, databases and garbage-collected heaps, can spend a large share of their time on TLB misses, and huge pages often speed them up by several to tens of percent. Linux offers them explicitly, through hugetlbfs or mmap with MAP_HUGETLB, and transparently, by promoting suitable regions automatically. Transparent huge pages have a cost of their own: assembling a 2 MiB physical region can require compacting memory at awkward moments, so latency-sensitive services such as Redis recommend turning them off.

The TLB across switches

TLB entries belong to one address space. When the kernel switches to another process, entries for the old one must not be used, so older processors flushed the whole TLB on every switch, and the new process started with every access missing. Tagging each entry with an address-space ID, called PCID on x86 and ASID on ARM, lets entries from several processes coexist and survive switches. The opposite problem arises when a mapping changes. If one thread unmaps memory, every core that might have cached the translation must drop it, so the kernel interrupts those cores with a TLB shootdown. Multithreaded programs that map and unmap memory constantly, as some allocators do, can spend real time on these.

Demand paging

malloc for a large block, and mmap of anonymous memory, only reserve virtual addresses. No physical memory is assigned until the program first touches each page. That first touch faults, and the kernel finds a free frame, zeroes it, maps it and resumes: a minor fault, costing around a microsecond. A file mapped with mmap works the same way. If the file's page is already in memory, in the kernel's page cache, the fault just maps it, another minor fault. If it isn't, the kernel reads it from storage, a major fault, which costs a disk access. This is why a process's resident size grows as it runs, why a freshly started program is slower than a warm one, and why /usr/bin/time -v and perf stat -e page-faults report fault counts.

Copy-on-write

fork would be ruinously slow if it copied a large process's memory, so it doesn't. It copies only the page tables, and marks every page in both parent and child read-only and shared. As long as both only read, they share the same physical pages. When either one writes to a page, the protection fault goes to the kernel, which sees a copy-on-write page, copies just that one, maps the copy writable for the writer, and resumes. In the example, a child that calls exec straight away copies none of a 100 MiB parent's 25,600 pages, and one that writes to 1% of them copies 256. Redis takes its snapshots this way: it forks, and the child writes the frozen view of memory to disk while the parent keeps serving. The memory cost depends on how many pages the parent writes during the snapshot (exercise 13.2).

What faults cost

The example's last table turns fault rates into an average memory access time, assuming memory takes 100 ns. One fault per million accesses costs almost nothing. One per ten thousand costs 10% when the faults are served from an SSD at 100 µs, and makes memory six times slower when they're served from a disk at 5 ms. One per thousand, from disk, makes it 51 times slower. A machine in that state is barely running, which is the subject of chapter 14.

Swapping

Physical memory is a cache for the pages processes have touched. When it's full, the kernel picks a victim page. A clean page, one that matches a copy on disk such as the code of a program or a file read through the page cache, can simply be dropped and read back if needed. A dirty page, such as modified heap memory, must first be written to swap space, a partition or file reserved for it, or for file data, back to its file. The entry for the page in the process's page table is then marked not present, and the next access faults and reads it back: a major fault (chapter 13). Linux reclaims memory in the background with a kernel thread, kswapd, which starts when free memory falls below a low watermark, so that most allocations find a free page without waiting.

Choosing a victim

The ideal policy, which László Belady described in 1966, evicts the page that won't be needed for the longest time. It's optimal and impossible, since it needs to know the future, but it's the yardstick: the example's OPT computes it from the whole reference string. FIFO evicts the page that has been in memory longest, which is simple and ignores how much the page is used. LRU, least recently used, evicts the page whose last use is furthest in the past, betting that the recent past predicts the near future. Exact LRU would mean updating an ordering on every memory access, far too expensive in hardware, so kernels approximate it.

The clock algorithm is the classic approximation. The processor sets a page's accessed bit in its page-table entry whenever the page is used. The kernel arranges the frames in a circle and moves a hand around it. If the page under the hand has its bit set, the kernel clears the bit and moves on, giving the page a second chance; the first page found with its bit clear is the victim. Pages in active use keep getting their bits set and survive, while pages nobody has touched since the last sweep go. Linux uses a refinement with two lists, active and inactive, and a page must be used twice to be promoted, so a single large scan doesn't flush everything useful.

import random
from collections import OrderedDict

def faults(refs, frames, policy):
    memory, n, hand = OrderedDict(), 0, 0          # memory: page -> referenced bit (for CLOCK)
    order = []                                      # CLOCK's circular list of pages
    nxt, last = [len(refs)] * len(refs), {}         # OPT: when each reference's page is next used
    for i in range(len(refs) - 1, -1, -1):
        nxt[i] = last.get(refs[i], len(refs)); last[refs[i]] = i
    when = {}
    for i, page in enumerate(refs):
        when[page] = nxt[i]
        if page in memory:
            if policy == "LRU": memory.move_to_end(page)
            memory[page] = 1                        # hardware sets the referenced bit on every use
            continue
        n += 1                                      # a page fault
        if len(memory) == frames:
            if policy in ("FIFO", "LRU"):
                victim = next(iter(memory))         # oldest arrival, or least recently used
            elif policy == "OPT":                   # Belady's optimum: the page needed furthest ahead
                victim = max(memory, key=lambda p: when[p])
            elif policy == "CLOCK":                 # sweep the hand, giving used pages a second chance
                while memory[order[hand]]:
                    memory[order[hand]] = 0; hand = (hand + 1) % len(order)
                victim = order[hand]
            del memory[victim]
            if policy == "CLOCK": order[hand] = page; hand = (hand + 1) % len(order)
        elif policy == "CLOCK":
            order.append(page)
        memory[page] = 1
    return n

refs = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
print(f"reference string {' '.join(map(str, refs))}")
for policy in ("FIFO", "LRU", "OPT"):
    three, four = faults(refs, 3, policy), faults(refs, 4, policy)
    print(f"   {policy:5} faults with 3 frames: {three:2}   with 4 frames: {four:2}")
print("   FIFO faults more with more memory: Belady's anomaly. LRU and OPT never do.")

# A loop over 5 pages with 4 frames: recency is exactly the wrong guide
loop = [1, 2, 3, 4, 5] * 20
print(f"\nlooping over 5 pages with 4 frames, {len(loop)} references:")
for policy in ("FIFO", "LRU", "CLOCK", "OPT"):
    print(f"   {policy:5} {faults(loop, 4, policy):3} faults")

# Real programs have locality: most references go to a small working set that drifts slowly
random.seed(14)
refs, hot = [], list(range(20))
for _ in range(20_000):
    if random.random() < 0.02: hot[random.randrange(20)] = random.randrange(1000)   # working set drifts
    refs.append(random.choice(hot) if random.random() < 0.9 else random.randrange(1000))
print("\n20,000 references with 90% going to a working set of 20 pages, out of 1,000:")
print("   frames " + "".join(f"{f:>8}" for f in (10, 20, 30, 40, 60)))
for policy in ("FIFO", "CLOCK", "LRU", "OPT"):
    rates = [faults(refs, f, policy) / len(refs) for f in (10, 20, 30, 40, 60)]
    print(f"   {policy:6}" + "".join(f"{r:8.1%}" for r in rates))

reference string 1 2 3 4 1 2 5 1 2 3 4 5
   FIFO  faults with 3 frames:  9   with 4 frames: 10
   LRU   faults with 3 frames: 10   with 4 frames:  8
   OPT   faults with 3 frames:  7   with 4 frames:  6
   FIFO faults more with more memory: Belady's anomaly. LRU and OPT never do.

looping over 5 pages with 4 frames, 100 references:
   FIFO  100 faults
   LRU   100 faults
   CLOCK 100 faults
   OPT    28 faults

20,000 references with 90% going to a working set of 20 pages, out of 1,000:
   frames       10      20      30      40      60
   FIFO     61.4%   34.8%   23.5%   18.8%   15.1%
   CLOCK    60.9%   29.9%   15.7%   12.4%   11.6%
   LRU      60.0%   27.0%   13.4%   11.8%   11.5%
   OPT      32.5%   12.4%   10.6%    9.9%    9.1%

Belady's anomaly, and the loop

Belady also found something stranger. On the reference string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO makes 9 faults with three frames and 10 with four: giving it more memory makes it worse. LRU and OPT can't behave this way. They're stack algorithms: the pages they'd keep with n frames are always a subset of those they'd keep with n + 1, so more memory never hurts. FIFO's choice depends on arrival order, which changes in unrelated ways when memory grows.

The second part of the example is the access pattern that defeats recency. A program loops over 5 pages with room for 4. Each page is evicted just before it's needed again, so FIFO, LRU and CLOCK fault on every one of the 100 references, while OPT faults on 28. The same pattern hit chapter 10 of The Engineer's Mill in caches, and it's common in practice: a sequential scan of a file larger than memory evicts everything else and gains nothing from it. Databases defend against it with scan-resistant buffer pools, and Linux's two-list design exists for the same reason.

Working sets

Real programs have locality. At any moment they use a small working set of pages heavily, and it drifts slowly as the program moves through its work, an idea Peter Denning formalised in 1968. The example's last workload sends 90% of its references to a working set of 20 pages out of 1,000, replacing one of them now and then. The figure plots its fault rate against memory size for all four policies.

Two things stand out. The curves have a knee near the working-set size: memory below it is nearly useless, and memory beyond it buys little, because the remaining faults are the 10% of references to random pages, which no policy can avoid. And CLOCK, with one bit per page, stays close to exact LRU, while FIFO, which ignores use altogether, needs noticeably more memory for the same fault rate.

Thrashing

When the working sets of all running processes add up to more than physical memory, every process keeps faulting on pages another process's faults just evicted. The disk becomes the bottleneck, the processor sits idle waiting for it, and almost no work gets done. This is thrashing, and chapter 13's arithmetic shows why it's so severe: a fault per thousand accesses served from a disk makes memory 51 times slower. Early systems responded by reducing the number of programs running, suspending some until the rest fit, which is the right idea. Today, servers often run with little or no swap and let the out-of-memory killer end a process rather than letting the whole machine thrash. Linux's pressure stall information, in /proc/pressure/memory, reports how much time tasks spend waiting for memory, and tools such as systemd-oomd act on it before the machine locks up. Phones mostly avoid swapping to flash storage: iOS and Android compress memory instead, ask apps to release what they can, and then terminate background apps.

From pages to objects

A process gets memory from the kernel in large pieces: brk to grow the heap, and mmap for big blocks and for allocators that manage their own regions. The C library's malloc and free, or a replacement such as jemalloc, tcmalloc or mimalloc, carve those pieces into objects. The allocator must find space for each request quickly, return freed space for reuse, and keep two kinds of waste low. External fragmentation is free memory broken into holes too small for the requests that arrive. Internal fragmentation is space wasted inside allocated blocks, because a request was rounded up.

Free lists and placement

A simple allocator keeps a list of free blocks. To allocate, it finds a free block large enough, splits off what's needed and keeps the rest on the list. To free, it returns the block and coalesces it with free neighbours, so that small holes merge back into large ones. The placement policy decides which free block to use. First fit takes the first one that's large enough, which is fast. Best fit takes the smallest that fits, to keep large blocks intact. Worst fit takes the largest, on the theory that the leftover piece will be big enough to be useful.

The example runs 4,000 random allocations and frees, in sizes from 16 bytes to 2 KiB, through a 64 KiB heap with each policy. First fit and best fit fill the heap almost completely; their failures come when it's full, with a few kilobytes left in holes. Worst fit fails more than twice as often, with more than half the heap still free, because it has broken that space into 83 holes of which the largest is 1,136 bytes. It splits the large blocks first, which leaves no room for the large requests. Studies of real programs' allocation traces agree: best fit and first fit waste similar, small amounts, and worst fit does badly.

import gc, random, weakref

# 1. A free-list allocator over a 64 KiB heap, with coalescing of neighbouring free blocks
class Heap:
    def __init__(self, size, fit):
        self.free, self.fit, self.used = [(0, size)], fit, {}      # free: sorted (start, length)
    def malloc(self, n):
        fits = [b for b in self.free if b[1] >= n]
        if not fits: return None
        start, length = {"first": fits[0], "best": min(fits, key=lambda b: b[1]),
                         "worst": max(fits, key=lambda b: b[1])}[self.fit]
        self.free.remove((start, length))
        if length > n: self.free.append((start + n, length - n))   # split off the remainder
        self.free.sort(); self.used[start] = n
        return start
    def release(self, start):
        self.free.append((start, self.used.pop(start))); self.free.sort()
        merged = []
        for s, l in self.free:                                     # coalesce adjacent free blocks
            if merged and merged[-1][0] + merged[-1][1] == s:
                merged[-1] = (merged[-1][0], merged[-1][1] + l)
            else: merged.append((s, l))
        self.free = merged

def workload(fit, seed=15):
    rng, heap, live, failed = random.Random(seed), Heap(65536, fit), [], 0
    for step in range(4000):
        if live and rng.random() < 0.48:                           # free a random live block
            heap.release(live.pop(rng.randrange(len(live))))
        else:
            size = rng.choice([16, 24, 32, 48, 64, 128, 256, 1024, 2048])
            p = heap.malloc(size)
            if p is None: failed += 1
            else: live.append(p)
    free = sum(l for _, l in heap.free)
    largest = max(l for _, l in heap.free)
    return failed, free, largest, len(heap.free)
print("4,000 random mallocs and frees in a 64 KiB heap:")
for fit in ("first", "best", "worst"):
    failed, free, largest, holes = workload(fit)
    print(f"   {fit:5} fit: {failed:3} requests failed; {free:6,} bytes free in {holes:3} holes, "
          f"largest {largest:6,} ({1 - largest / free:.0%} external fragmentation)")

# 2. Rounding up: a buddy allocator uses powers of two; size classes round much less
rng = random.Random(2)
sizes = [int(2 ** rng.uniform(4.1, 12)) for _ in range(10_000)]    # small requests are the most common
classes = [16, 32, 48, 64, 80, 96, 112, 128, 160, 192, 224, 256, 320, 384, 448, 512,
           640, 768, 896, 1024, 1280, 1536, 1792, 2048, 2560, 3072, 3584, 4096]   # like jemalloc's
buddy = sum(1 << (s - 1).bit_length() for s in sizes)
classed = sum(next(c for c in classes if c >= s) for s in sizes)
asked = sum(sizes)
print("\ninternal fragmentation on 10,000 requests between 17 bytes and 4 KiB:")
print(f"   powers of two (buddy):     {buddy / asked - 1:.1%} wasted")
print(f"   28 size classes:           {classed / asked - 1:.1%} wasted")

# 3. Garbage collection: reference counting frees at once, but not cycles
class Node:
    def __init__(self, name): self.name, self.other = name, None
freed = []
a = Node("a"); weakref.finalize(a, freed.append, "a")
del a
print(f"\nreference counting: after `del a`, freed {freed}")
b, c = Node("b"), Node("c"); b.other, c.other = c, b               # a cycle: b -> c -> b
weakref.finalize(b, freed.append, "b"); weakref.finalize(c, freed.append, "c")
del b, c
print(f"a cycle b <-> c after `del b, c`: freed {freed}  (each still has a reference from the other)")
gc.collect()
print(f"after the cycle collector runs: freed {sorted(freed)}")

# 4. Mark and sweep, from scratch: mark everything reachable from the roots, sweep the rest
heap = {"main": ["config", "users"], "config": [], "users": ["alice", "bob"], "alice": [], "bob": ["alice"],
        "temp1": ["temp2"], "temp2": ["temp1"], "old_cache": ["config"]}
roots, marked, todo = ["main"], set(), ["main"]
while todo:
    obj = todo.pop()
    if obj not in marked: marked.add(obj); todo.extend(heap[obj])
print(f"\nmark and sweep from root 'main': keeps {sorted(marked)}")
print(f"   frees {sorted(set(heap) - marked)}, the cycle included")

4,000 random mallocs and frees in a 64 KiB heap:
   first fit:  42 requests failed;  6,144 bytes free in  42 holes, largest  1,024 (83% external fragmentation)
   best  fit:  36 requests failed;  3,504 bytes free in  26 holes, largest  1,024 (71% external fragmentation)
   worst fit:  87 requests failed; 37,688 bytes free in  83 holes, largest  1,136 (97% external fragmentation)

internal fragmentation on 10,000 requests between 17 bytes and 4 KiB:
   powers of two (buddy):     39.3% wasted
   28 size classes:           9.2% wasted

reference counting: after `del a`, freed ['a']
a cycle b <-> c after `del b, c`: freed ['a']  (each still has a reference from the other)
after the cycle collector runs: freed ['a', 'b', 'c']

mark and sweep from root 'main': keeps ['alice', 'bob', 'config', 'main', 'users']
   frees ['old_cache', 'temp1', 'temp2'], the cycle included

Rounding: buddies and size classes

A buddy allocator manages blocks whose sizes are powers of two. A request is rounded up to the next power, and a block is split in halves, its "buddies", until one of the right size appears; when both halves are free again they merge. Finding a buddy is a single bit operation on the address, so splitting and merging are fast, and the Linux kernel allocates physical pages this way. The cost is rounding. In the example, 10,000 requests between 17 bytes and 4 KiB, with small sizes the most common, waste 39% of the memory they're given.

User-space allocators instead use size classes: a fixed list of sizes spaced roughly a quarter apart, and a separate pool of same-sized slots for each, carved out of pages. A request goes to the smallest class that fits, so rounding waste is bounded, 9% in the example with 28 classes, and since every slot in a pool is the same size, allocating and freeing are a pop and a push on a list, with no searching and no external fragmentation within a pool. jemalloc, tcmalloc and mimalloc all work this way, add per-thread caches so that most allocations take no lock, and hand very large requests straight to mmap. The Linux kernel does the same for its own objects with its slab allocator.

Garbage collection: reference counting

In C and C++ the programmer calls free, or a destructor does, and the bugs are leaks, double frees and use after free. Garbage-collected languages instead free an object automatically when the program can no longer reach it. The simplest way is reference counting: every object counts the references to it, and when the count drops to zero, it's freed immediately. CPython works this way, as do Swift and Objective-C, and C++'s shared_ptr and Rust's Rc. It's predictable, and memory is reclaimed promptly. It has two costs. Every assignment updates counts, which in multithreaded code must be atomic. And it can't free a cycle: in the example, two objects that refer to each other keep each other's count above zero after the program drops its own references, so neither is freed until CPython's separate cycle collector runs.

Tracing collectors

A tracing collector instead starts from the roots, which are global variables, the stacks of every thread and the registers, and follows every reference to find everything reachable. Mark and sweep marks each reachable object, then sweeps the heap and frees everything unmarked, cycles included, as the example's last part does. A copying collector moves the live objects into a fresh region instead, which compacts the heap and makes allocation a pointer increment, at the cost of needing space to copy into. Most programs follow the generational hypothesis: most objects die young. So collectors in the JVM, .NET and JavaScript engines collect a small young generation often and cheaply, and the old generation rarely.

The price of tracing is the pause, or the work needed to avoid it. A simple collector stops the program while it traces. Concurrent collectors such as Java's ZGC and Go's collector do most of the work while the program runs, using write barriers to track changes, and keep pauses to around a millisecond or less in exchange for some throughput and extra memory. Tracing collectors also typically need more memory than the live data, often twice as much, to run efficiently.

Three layers

A file descriptor is a small integer, an index into the process's own table of open files. Each entry points to an open file description in the kernel, which holds the current offset and the mode the file was opened with. Each open file description points to an inode, the file itself. Two calls to open on the same file create two open file descriptions, each with its own offset. dup creates a second descriptor for the same description, and so does fork, for every descriptor the child inherits. Those share one offset, so a read through one moves the other.

The example opens one file twice and duplicates one of the descriptors. Reading 4 bytes through each gives "0123" twice, from the two independent offsets, and then "4567" through the duplicate, which shares the first offset. A forked child reads one more byte through the inherited descriptor, and the parent's next read starts after it.

import os, sys, tempfile

os.chdir(tempfile.mkdtemp())
with open("notes.txt", "w") as f: f.write("0123456789")

# 1. A file descriptor is an index into the process's table of open files; each open has an offset
a = os.open("notes.txt", os.O_RDONLY)
b = os.open("notes.txt", os.O_RDONLY)                 # a second, independent open
c = os.dup(a)                                         # a second descriptor for the SAME open
print(f"read 4 via a: {os.read(a, 4)}, then 4 via b: {os.read(b, 4)}, then 4 via c: {os.read(c, 4)}")
sys.stdout.flush()
if os.fork() == 0:                                    # a child inherits the parent's open files
    os.read(a, 1); os._exit(0)                        # ...and moves the shared offset
os.wait()
print(f"after a child read 1 byte through a, the parent's next read via a gets {os.read(a, 4)}")
for fd in (a, b, c): os.close(fd)

# 2. Names are just directory entries pointing at an inode, which holds the data and metadata
os.link("notes.txt", "hard.txt")                      # a second name for the same inode
os.symlink("notes.txt", "soft.txt")                   # a small file containing a path
n, h, s = os.stat("notes.txt"), os.stat("hard.txt"), os.lstat("soft.txt")
print(f"\nhard link: same inode {n.st_ino == h.st_ino}, link count {n.st_nlink}")
print(f"symbolic link: same inode {n.st_ino == s.st_ino}, its own content is the path "
      f"{os.readlink('soft.txt')!r}")
os.unlink("notes.txt")                                # removes one name; the inode survives
print(f"after unlinking notes.txt: hard.txt still reads {open('hard.txt').read()!r} "
      f"(link count {os.stat('hard.txt').st_nlink})")
print(f"soft.txt now dangles: exists {os.path.exists('soft.txt')}, the link itself exists "
      f"{os.path.lexists('soft.txt')}")

# 3. An open file outlives its last name: the space is freed only when the last descriptor closes
fd = os.open("hard.txt", os.O_RDONLY)
os.unlink("hard.txt")
print(f"\nunlinked while open: directory now holds {sorted(os.listdir('.'))}, "
      f"but the open descriptor still reads {os.read(fd, 10)!r}")
os.close(fd)

# 4. Sizes and blocks: a sparse file reports 1 GiB but stores almost nothing
with open("sparse.bin", "wb") as f:
    f.seek(2 ** 30 - 1); f.write(b"\0")
st = os.stat("sparse.bin")
print(f"sparse.bin: size {st.st_size:,} bytes; disk space used is under 1 MiB: "
      f"{st.st_blocks * 512 < 2 ** 20}")
os.remove("sparse.bin")

# 5. The classic Unix inode: 12 direct block pointers, then single, double and triple indirect blocks
block, ptrs = 4096, 4096 // 4                         # 4 KiB blocks, 4-byte block numbers
reach = [("12 direct pointers", 12 * block), ("single indirect", ptrs * block),
         ("double indirect", ptrs ** 2 * block), ("triple indirect", ptrs ** 3 * block)]
def human(n):
    for unit in ("bytes", "KiB", "MiB", "GiB", "TiB"):
        if n < 1024: return f"{n:.4g} {unit}"
        n /= 1024
total = 0
print("\nhow far each part of an ext2-style inode reaches, with 4 KiB blocks:")
for name, size in reach:
    total += size
    print(f"   {name:20} adds {human(size):>7}, for files up to {human(total)}")

read 4 via a: b'0123', then 4 via b: b'0123', then 4 via c: b'4567'
after a child read 1 byte through a, the parent's next read via a gets b'9'

hard link: same inode True, link count 2
symbolic link: same inode False, its own content is the path 'notes.txt'
after unlinking notes.txt: hard.txt still reads '0123456789' (link count 1)
soft.txt now dangles: exists False, the link itself exists True

unlinked while open: directory now holds ['soft.txt'], but the open descriptor still reads b'0123456789'
sparse.bin: size 1,073,741,824 bytes; disk space used is under 1 MiB: True

how far each part of an ext2-style inode reaches, with 4 KiB blocks:
   12 direct pointers   adds  48 KiB, for files up to 48 KiB
   single indirect      adds   4 MiB, for files up to 4.047 MiB
   double indirect      adds   4 GiB, for files up to 4.004 GiB
   triple indirect      adds   4 TiB, for files up to 4.004 TiB

Names and inodes

An inode holds everything about a file except its name: its type, size, owner, permissions, timestamps, link count, and where its data is. A directory is a special file whose contents map names to inode numbers. That separation explains links. A hard link is a second directory entry for the same inode, so after os.link the two names are equally real and the link count is 2; ls -i shows the shared inode number. A symbolic link is a separate small file whose content is a path, followed when the link is opened, so it can point across file systems or at nothing at all. unlink removes a name and decrements the link count. The inode and its data are freed only when the count reaches zero and no process has the file open.

That last condition explains a common incident. A disk fills up, someone deletes a huge log file, and no space comes back, because the process writing the log still has it open and keeps writing to an inode with no name. The example does the same: after unlinking the last name, the directory is empty of it, but the open descriptor still reads the whole file. lsof +L1 lists open files with no links left, and the space returns when the process closes the file or exits.

Finding the blocks

The classic Unix inode, used by ext2 and ext3, holds 12 direct block pointers, enough for the first 48 KiB of a file in 4 KiB blocks. After them come a single indirect pointer, to a block full of 1,024 further pointers, which adds 4 MiB; a double indirect pointer, adding 4 GiB; and a triple indirect pointer, adding 4 TiB. Small files, which are most files, need no extra blocks at all, and large files cost one extra read per level. Modern file systems, ext4, XFS, Btrfs and APFS, use extents instead: each entry describes a run of contiguous blocks with a start and a length, so a large file stored contiguously needs a handful of entries instead of millions of pointers.

Because an inode records where data is, not merely how big the file is, a file can have holes. The example seeks to just before 1 GiB and writes one byte. The file's size is 1 GiB, but the file system stores only the block that was written, and reads of the hole return zeros. Virtual machine images and database files are often sparse, which is why ls -l and du can disagree by gigabytes.

Layout, caching and the VFS

Where blocks go on the disk matters. The Berkeley Fast File System, in 1984, divided the disk into groups and placed each file's inode near its data and the files of a directory near each other, which multiplied throughput on spinning disks; ext4's block groups follow the same idea. Reads and writes don't go straight to the disk anyway. They go through the page cache, the kernel's cache of file data in otherwise unused memory: a read of cached data is a memory copy, and a write normally just updates the cache and marks the page dirty, to be written back seconds later. Chapter 17 is about what that delay means when the power fails.

On Linux, all of this sits behind the virtual file system layer, which gives ext4, XFS, Btrfs, network file systems and in-memory ones such as tmpfs the same open, read and write. It's also how files that aren't on any disk work: /proc and /sys generate their contents when read, which is what "everything is a file" means in practice.

One append, three writes

Appending one block to a file touches three structures on disk. The bitmap of free blocks must mark the new block used. The file's inode must record the new size and point to the block. And the data block itself must be written. They live in different places, so they're separate writes, and nothing guarantees that all three complete, or in which order. The example tries all eight combinations of which writes reached the disk before a crash, and asks what a file-system checker would conclude about each.

import itertools, os, tempfile

# Appending one block to a file needs three writes to different places on the disk. The disk may
# complete them in any order, and the power can fail at any moment. Try every combination.
OLD = {"bitmap": {4}, "inode": {"size": 1, "blocks": [4]}, "block5": "????"}     # before the append
WRITES = {"bitmap": {4, 5}, "inode": {"size": 2, "blocks": [4, 5]}, "block5": "new data"}

def fsck(disk):
    """What a file-system checker would conclude about this disk."""
    pointed = set(disk["inode"]["blocks"]); used = disk["bitmap"]
    if pointed - used: return "INCONSISTENT: the inode points at a block marked free"
    if used - pointed: return "space leak: a block marked used belongs to no file"
    if 5 in pointed and disk["block5"] == "????": return "consistent, but the file now ends in garbage"
    if 5 in pointed: return "consistent: the append happened"
    return "consistent: as if the append never happened"

print("crash during an append, without a journal; which writes reached the disk:")
for k in range(4):
    for done in itertools.combinations(WRITES, k):
        disk = {**OLD, **{w: WRITES[w] for w in done}}
        print(f"   {' + '.join(done) or 'none':24} {fsck(disk)}")

# With a journal: write the three blocks, then a commit record, to the log; then write them home.
# Recovery replays a transaction only if its commit record reached the disk. (A write barrier
# keeps the commit from landing before the blocks it covers.)
STEPS = ["log bitmap", "log inode", "log block5", "log commit",
         "home bitmap", "home inode", "home block5", "free the log"]
def journaled(crash_after):
    disk, log = {**OLD}, {}
    for step in STEPS[:crash_after]:
        kind, what = step.split(" ", 1)
        if kind == "log": log[what] = True
        elif kind == "home": disk[what] = WRITES[what]
        else: log = {}
    if log.get("commit"): disk = {**disk, **WRITES}          # recovery after reboot: replay the log
    return fsck(disk)
print("\nwith a journal, crash after each step:")
for n in range(9):
    print(f"   {'(before any write)' if n == 0 else STEPS[n - 1]:24} {journaled(n)}")

# The same problem one level up: replacing a file's contents safely
def overwrite_in_place(crash_at):                    # open(path, "w") truncates first, then writes
    states = ["old contents", "", "new con", "new contents"]
    return states[min(crash_at, 3)]
def write_then_rename(crash_at):                     # write a temporary file, fsync it, rename over
    return "new contents" if crash_at >= 3 else "old contents"
print("\nsaving a file, crash at every point:")
for name, save in (("overwrite in place:", overwrite_in_place),
                   ("write, fsync, then rename:", write_then_rename)):
    print(f"   {name:27} " + ", ".join(repr(x) for x in dict.fromkeys(save(c) for c in range(4))))

# The rename pattern, for real
def atomic_write(path, data):
    tmp = path + ".tmp"
    with open(tmp, "wb") as f:
        f.write(data); f.flush()
        os.fsync(f.fileno())                         # the data is on the disk before the rename
    os.replace(tmp, path)                            # atomic: readers see the old file or the new one
    dir_fd = os.open(os.path.dirname(path), os.O_RDONLY)
    os.fsync(dir_fd); os.close(dir_fd)               # make the rename itself durable
path = os.path.join(tempfile.mkdtemp(), "settings.json")
atomic_write(path, b'{"theme": "dark"}')
atomic_write(path, b'{"theme": "light"}')
print(f"   after two atomic writes the file holds {open(path).read()}; "
      f"the directory holds {os.listdir(os.path.dirname(path))}")

crash during an append, without a journal; which writes reached the disk:
   none                     consistent: as if the append never happened
   bitmap                   space leak: a block marked used belongs to no file
   inode                    INCONSISTENT: the inode points at a block marked free
   block5                   consistent: as if the append never happened
   bitmap + inode           consistent, but the file now ends in garbage
   bitmap + block5          space leak: a block marked used belongs to no file
   inode + block5           INCONSISTENT: the inode points at a block marked free
   bitmap + inode + block5  consistent: the append happened

with a journal, crash after each step:
   (before any write)       consistent: as if the append never happened
   log bitmap               consistent: as if the append never happened
   log inode                consistent: as if the append never happened
   log block5               consistent: as if the append never happened
   log commit               consistent: the append happened
   home bitmap              consistent: the append happened
   home inode               consistent: the append happened
   home block5              consistent: the append happened
   free the log             consistent: the append happened

saving a file, crash at every point:
   overwrite in place:         'old contents', '', 'new con', 'new contents'
   write, fsync, then rename:  'old contents', 'new contents'
   after two atomic writes the file holds {"theme": "light"}; the directory holds ['settings.json']

Only three outcomes are clean: all three writes, none of them, or only the data block, written into a block nobody points to. A bitmap update alone leaks a block that belongs to no file. An inode update without the bitmap points at a block the bitmap says is free, so a later allocation can give the same block to a second file, and the two files then overwrite each other. The bitmap and inode without the data leave a consistent file system with garbage at the end of the file: whatever was in that block before, possibly another user's deleted data. No checker can detect that last case, because the metadata is perfectly consistent.

Early Unix systems handled crashes by running fsck at boot: read every inode and bitmap, cross-check them, and repair what's inconsistent. It works, but it reads the whole file system, which on a large disk takes hours, and it can't recover data that was never written.

Journaling

A journal, or write-ahead log, makes the update atomic. Before touching the real structures, the file system writes everything it's about to change into a reserved log area, followed by a commit record. Only once the commit is on disk does it write the blocks to their home locations, the checkpoint, and finally it frees the log space. After a crash, recovery reads the log. A transaction with a commit record is replayed, which is safe to do twice, since replaying writes the same blocks again; a transaction without one is discarded. Either way the file system ends up entirely before or entirely after the update, which is what the example's second table shows for every crash point.

The order is enforced with write barriers, or cache flushes, because a disk with a write cache might otherwise write the commit before the blocks it describes. ext3, ext4, XFS and NTFS all journal. Writing every data block twice, once to the log and once home, halves write bandwidth, so ext4's default ordered mode journals only metadata, and writes a file's data blocks to their home locations before committing the metadata that points to them. That still rules out pointers to garbage. Copy-on-write file systems, ZFS, Btrfs and APFS, take another route: they never overwrite live blocks, write new versions elsewhere, and switch to them with a single atomic update of a root pointer.

What fsync promises

A write that returns has only copied the data into the page cache. Linux writes dirty pages back on its own schedule, typically within 30 seconds, and a crash before then loses them however consistent the file system stays. fsync(fd) blocks until the file's data and metadata are on stable storage, including telling the device to flush its own volatile cache; fdatasync skips metadata that isn't needed to read the data back, such as timestamps. On macOS, fsync does not force the drive to flush its cache, and durability across a power cut needs fcntl(fd, F_FULLFSYNC), which SQLite and other databases use there.

fsync is also where errors surface. In 2018 PostgreSQL's developers discovered that when Linux failed to write back dirty pages, fsync reported the error once and then marked the pages clean, so a retry would succeed and the data was simply gone. Since then PostgreSQL treats an fsync failure as fatal and recovers from its own log. The lesson for every program is that an fsync error means the data may be lost, not that it should try again. And fsync is slow: from around a hundred microseconds on a server SSD that can protect its cache against power loss, to several milliseconds on consumer drives and ten on spinning disks. That's why databases group commit, making many transactions durable with one fsync (exercise 17.2).

Saving a file safely

The same problem appears one level up. Opening a file with "w" truncates it first and then writes the new contents, so a crash in between leaves the old contents, an empty file, a partial one or the new one; the example lists all four. The safe pattern writes the new contents to a temporary file in the same directory, calls fsync on it, then uses rename to replace the original, and finally calls fsync on the directory so that the rename itself is durable. POSIX guarantees that rename replaces the target atomically, so every reader and every crash sees either the complete old file or the complete new one. The example's atomic_write does exactly this. When ext4 introduced delayed allocation in 2009, applications that skipped the fsync began leaving zero-length configuration files after crashes, and ext4 added a heuristic to protect them. Code that wants its data to survive shouldn't depend on heuristics.

Blocking

By default, a read on a socket with no data waiting puts the calling thread to sleep until data arrives. That's the simplest model to program: the code reads a request, handles it and writes a reply, in order, as if nothing else existed. To serve many clients, give each connection its own thread or process, which is how Apache's original servers and PostgreSQL work. Around 1999 Dan Kegel named the limit of that design the C10K problem: serving ten thousand connections at once with a thread each costs a great deal of memory, and every one of them needs scheduling. Most of those threads are idle, waiting for a slow client, and the waiting itself is what costs.

Non-blocking, and readiness

A descriptor in non-blocking mode, set with O_NONBLOCK, never sleeps: a read with nothing to read fails at once with EAGAIN, "try again". On its own that's only useful for checking, since a program that keeps retrying burns a core. Combined with a way to learn when a descriptor is ready, it becomes the basis of every high-performance server. select, from 4.2BSD in 1983, takes sets of descriptors and blocks until at least one is readable or writable. poll lifted select's limit of 1,024 descriptors, but both still pass the whole set to the kernel on every call and scan it, so their cost grows with the number of connections, not with the number that are active. Linux's epoll, from 2002, and FreeBSD's kqueue, from 2000 and also used by macOS, fix that: a program registers each descriptor once, and each wait returns only the ones that are ready.

The example uses Python's selectors module, which picks epoll on Linux and kqueue on macOS. A non-blocking read on an empty socket raises BlockingIOError, Python's name for EAGAIN. Then a hundred socket pairs stand in for a hundred client connections. When ten clients send a request, one call reports exactly those ten as ready and one thread answers them; when all hundred send, one call reports a hundred. A client that hangs up is reported as ready too, and its read returns an empty result, end-of-file, which tells the server to close and unregister it.

import selectors, socket

# 1. Blocking and non-blocking reads. A socketpair is two connected sockets in one process.
client, server = socket.socketpair()
server.setblocking(False)
try:
    server.recv(100)                                  # nothing has been sent yet
except BlockingIOError as e:
    print(f"non-blocking recv with no data: {type(e).__name__} (EAGAIN): try again later")
client.send(b"ping")
print(f"after the client sends: recv returns {server.recv(100)!r}")
client.close(); server.close()

# 2. One thread, many connections: ask the kernel which sockets are ready, then serve only those.
#    DefaultSelector uses epoll on Linux and kqueue on macOS and the BSDs.
sel = selectors.DefaultSelector()
pairs = [socket.socketpair() for _ in range(100)]
for i, (c, s) in enumerate(pairs):
    s.setblocking(False)
    sel.register(s, selectors.EVENT_READ, data=i)

def serve_once():
    ready = sel.select(timeout=0)                     # which of the 100 sockets have data waiting?
    for key, _ in ready:
        msg = key.fileobj.recv(100)
        key.fileobj.send(msg.upper())                 # small replies: the send buffer has room
    return len(ready)

for c, _ in pairs[:10]: c.send(b"hello")              # only 10 clients have said anything
print(f"\n100 connections, 10 clients sent a request: select() reports {serve_once()} ready")
got = [c.recv(100) for c, _ in pairs[:10]]
print(f"   replies: {len(got)} x {got[0]!r}")
print(f"   nothing pending now: select() reports {serve_once()} ready")
for i, (c, _) in enumerate(pairs): c.send(f"req {i}".encode())
print(f"all 100 clients send: select() reports {serve_once()} ready, all served by one thread")
replies = [c.recv(100) for c, _ in pairs]
print(f"   replies received: {len(replies)}, first {replies[0]!r}, last {replies[-1]!r}")

# 3. A closed connection is "ready" too: the read returns b"" (end of file)
c, s = pairs[0]
c.close()
for key, _ in sel.select(timeout=0):
    data = key.fileobj.recv(100)
    print(f"\nclient {key.data} hung up: select() reports it ready, and recv returns {data!r}")
    sel.unregister(key.fileobj); key.fileobj.close()
for c, s in pairs[1:]: c.close(); s.close()
sel.close()

# 4. Why not a thread per connection? Rough costs per idle connection.
print()
for n in (1_000, 10_000, 100_000):
    threads = n * 64 * 1024                           # ~64 KiB of stack and kernel state actually used
    loop = n * 4 * 1024                               # ~4 KiB of buffers and bookkeeping in an event loop
    print(f"{n:>7,} idle connections: thread per connection ~{threads / 2 ** 20:6,.0f} MiB, "
          f"event loop ~{loop / 2 ** 20:5,.0f} MiB")

non-blocking recv with no data: BlockingIOError (EAGAIN): try again later
after the client sends: recv returns b'ping'

100 connections, 10 clients sent a request: select() reports 10 ready
   replies: 10 x b'HELLO'
   nothing pending now: select() reports 0 ready
all 100 clients send: select() reports 100 ready, all served by one thread
   replies received: 100, first b'REQ 0', last b'REQ 99'

client 0 hung up: select() reports it ready, and recv returns b''

  1,000 idle connections: thread per connection ~    62 MiB, event loop ~    4 MiB
 10,000 idle connections: thread per connection ~   625 MiB, event loop ~   39 MiB
100,000 idle connections: thread per connection ~ 6,250 MiB, event loop ~  391 MiB

The details that bite

Readiness notification comes in two styles. Level-triggered, the default, reports a descriptor every time you ask, as long as it's readable. Edge-triggered, an option in epoll, reports it only when it becomes readable, which saves wake-ups but requires reading until EAGAIN every time, or the rest of the data sits unnoticed (exercise 18.1). Writes need the same care as reads: a send on a non-blocking socket can accept only part of the data when the buffer is full, so the server keeps the rest and asks to be told when the socket is writable again. It should ask only while it has something to write, because an idle socket is almost always writable, and waiting for writability on every connection turns the event loop into a busy loop.

Regular files don't fit this model at all. A file is always reported readable, because the kernel's notion of readiness doesn't cover waiting for the disk, so a read can still block on a page-cache miss (chapter 13). Event-loop runtimes such as libuv, behind Node.js, therefore send file operations to a small pool of threads.

Completion: io_uring

Readiness tells a program when an operation won't block, and the program then makes the system call itself. Completion-based I/O inverts that: the program describes the operation, the kernel performs it, and the program collects the result later. Windows has worked this way since its I/O completion ports in the 1990s. Linux's io_uring, by Jens Axboe, added in 2019, uses two rings in memory shared between process and kernel: the program writes requests into the submission ring and reads results from the completion ring, so a single system call can submit and collect hundreds of operations, and in polling mode none at all. It handles files and sockets alike, which solves the file problem above. It has also had a long series of security flaws, and some environments, including Docker's default security profile and Google's production servers, disable it.

Choosing

The example's last lines put rough numbers on the trade-off. An idle connection costs perhaps 64 KiB of stack and kernel state with a thread each, and a few kilobytes of buffers with an event loop, so at 100,000 connections the difference is about 6 GiB against a few hundred MiB. Under load, readiness-based servers also avoid most context switches. Few programs use these interfaces directly, though, because language runtimes build on them. Go's network poller runs goroutines over epoll or kqueue, so code that looks blocking is multiplexed underneath. Java has NIO and Netty, Rust has tokio, and Python has asyncio. Knowing what's underneath explains their behaviour: why a blocking call inside them hurts (chapter 11), why file I/O goes to a thread pool, and why a server can hold far more connections than it has threads.

Pipes and named pipes

A pipe (chapter 3) is a one-way byte stream through a kernel buffer, and a read returns end-of-file once every writer has closed its end. An anonymous pipe exists only as two descriptors, so it can connect only processes that inherited them from a common ancestor. A named pipe, or FIFO, created with mkfifo, has a name in the file system, so unrelated processes can find it, and permissions decide who may open it. Opening a FIFO blocks until the other end is opened too, which makes it a simple rendezvous between two programs.

Sockets

Unix domain sockets use the same API as network sockets, socket, bind, connect, send and recv, with an address that's a path in the file system instead of a host and port. They're bidirectional, faster than TCP over the loopback interface because they skip the network stack, and protected by file permissions; a server can also ask the kernel for the user ID of the process at the other end. The Docker daemon, PostgreSQL's local connections, systemd and the display servers of Linux desktops all listen on them.

A socket comes in kinds. A stream socket, SOCK_STREAM, carries bytes with no message boundaries: three sends can arrive as one read, as in the example, or one send as three reads. A datagram socket, SOCK_DGRAM, keeps each send as a separate message; for Unix sockets it's reliable and ordered, unlike UDP. A protocol on a stream must therefore mark where each message ends, which is framing. The example prefixes each message with its length in four bytes and reads exactly that many back, the method used by many binary protocols; text protocols such as HTTP and Redis's use delimiters instead (exercise 19.1).

import mmap, os, socket, struct, sys, tempfile

def child(fn):
    """Run fn in a forked child process and wait for it to finish."""
    sys.stdout.flush()
    pid = os.fork()
    if pid == 0:
        fn(); os._exit(0)
    os.waitpid(pid, 0)

# 1. A pipe: a one-way byte stream between related processes. Reading returns b"" at end of file.
r, w = os.pipe()
child(lambda: (os.close(r), os.write(w, b"rows 1-500 done\n"), os.write(w, b"rows 501-1000 done\n")))
os.close(w)
chunks = []
while (data := os.read(r, 4096)): chunks.append(data)
print(f"pipe: the parent read {b''.join(chunks)!r}, then end of file")

# 2. A named pipe (FIFO) has a name in the file system, so unrelated processes can find it
fifo = os.path.join(tempfile.mkdtemp(), "jobs.fifo")
os.mkfifo(fifo)
sys.stdout.flush()
if os.fork() == 0:
    with open(fifo, "wb") as f: f.write(b"job 42")              # opening blocks until a reader arrives
    os._exit(0)
with open(fifo, "rb") as f: print(f"FIFO at {os.path.basename(fifo)}: read {f.read()!r}")
os.wait()

# 3. Streams have no message boundaries; datagram sockets keep them
for kind, name in ((socket.SOCK_STREAM, "stream socket:"), (socket.SOCK_DGRAM, "datagram socket:")):
    a, b = socket.socketpair(socket.AF_UNIX, kind)
    for msg in (b"first", b"second", b"third"): a.send(msg)
    b.setblocking(False)
    got = []
    try:
        while True: got.append(b.recv(1024))                   # read until nothing is left
    except BlockingIOError: pass
    print(f"{name:18} 3 sends arrive as {len(got)} read{'s' if len(got) > 1 else ''}: {got}")
    a.close(); b.close()
def send_msg(sock, data): sock.sendall(struct.pack("!I", len(data)) + data)   # length-prefix framing
def recv_msg(sock):
    size = struct.unpack("!I", sock.recv(4, socket.MSG_WAITALL))[0]
    return sock.recv(size, socket.MSG_WAITALL)
a, b = socket.socketpair()
for msg in (b"first", b"second", b"third"): send_msg(a, msg)
print(f"{'stream + framing:':18} 3 sends arrive as 3 messages: {[recv_msg(b) for _ in range(3)]}")
a.close(); b.close()

# 4. Shared memory: a MAP_SHARED mapping is the same physical pages in both processes
shared = mmap.mmap(-1, 4096, flags=mmap.MAP_SHARED)
private = mmap.mmap(-1, 4096, flags=mmap.MAP_PRIVATE)
child(lambda: (shared.write(b"written by the child"), private.write(b"written by the child")))
print(f"\nMAP_SHARED after the child wrote:  {shared[:20]!r}")
print(f"MAP_PRIVATE after the child wrote: {private[:20].rstrip(bytes(1))!r}  "
      f"(nothing: the child wrote to its own copy-on-write copy)")

# 5. Passing an open file descriptor over a Unix socket: the receiver gets the open file itself
secret = os.path.join(tempfile.mkdtemp(), "only-the-child-opens-this.txt")
with open(secret, "w") as f: f.write("token 7f3a")
parent_sock, child_sock = socket.socketpair(socket.AF_UNIX, socket.SOCK_STREAM)
def give_fd():
    fd = os.open(secret, os.O_RDONLY)
    socket.send_fds(child_sock, [b"here"], [fd])
child(give_fd)
msg, fds, _, _ = socket.recv_fds(parent_sock, 100, 1)
print(f"\nreceived {msg!r} and a descriptor; reading it gives {os.read(fds[0], 100)!r}")

pipe: the parent read b'rows 1-500 done\nrows 501-1000 done\n', then end of file
FIFO at jobs.fifo: read b'job 42'
stream socket:     3 sends arrive as 1 read: [b'firstsecondthird']
datagram socket:   3 sends arrive as 3 reads: [b'first', b'second', b'third']
stream + framing:  3 sends arrive as 3 messages: [b'first', b'second', b'third']

MAP_SHARED after the child wrote:  b'written by the child'
MAP_PRIVATE after the child wrote: b''  (nothing: the child wrote to its own copy-on-write copy)

received b'here' and a descriptor; reading it gives b'token 7f3a'

Shared memory

Every message through a pipe or socket is copied twice: from the sender into the kernel, and from the kernel into the receiver. Shared memory avoids both copies by mapping the same physical pages into both processes. A mapping created with mmap and MAP_SHARED before a fork is shared with the child; unrelated processes can share a named object from shm_open or a file mapped by both. In the example, the child writes into a shared mapping and the parent reads the child's words straight out of memory, while the same write to a MAP_PRIVATE mapping lands in the child's copy-on-write copy (chapter 13) and the parent sees nothing.

Shared memory is the fastest form of communication and the most dangerous, because it brings back every race of chapters 7 to 10, now between processes. The usual answer is a structure designed for it, such as a ring buffer with atomic head and tail indices, or a mutex created as process-shared, which on Linux is a futex in the shared page. Databases put their buffer caches in shared memory, as PostgreSQL does, and browsers use it to pass rendered frames between processes. Python's multiprocessing.shared_memory wraps the same mechanism.

Passing descriptors

A Unix socket can carry more than bytes. With an SCM_RIGHTS message, a process sends open file descriptors, and the receiver gets new descriptors for the same open files, sharing their offsets, as if it had inherited them. In the example the child opens a file and sends the descriptor, and the parent reads the file through it without ever opening it. The kernel checked permissions when the child opened the file, not when the parent used it, which makes this a tool for privilege separation: a small privileged helper opens what's needed and hands the descriptors to an unprivileged worker. It's also how servers restart without dropping connections. The old process passes its listening socket to the new one, which starts accepting while the old one finishes its current requests, and systemd's socket activation passes listening sockets to services in the same way.

Choosing

Other mechanisms fill the gaps: POSIX message queues, which keep message boundaries and priorities; the older System V IPC calls; eventfd for one process to wake another; and on Linux desktops, D-Bus, a message bus built on Unix sockets. In practice, the choice usually comes down to a few questions. A one-way stream between a parent and a child is a pipe. A local service with requests and replies is a Unix socket, or local TCP or HTTP if it may move to another machine one day, at a cost of tens of microseconds per request. Large volumes of data at a high rate, such as video frames or tensors, go in shared memory with a carefully designed queue. And the kernel's permission checks apply to all of them, so a socket that's writable by everyone is an open door: access to Docker's socket is equivalent to root.

Virtual machines

A hypervisor, or virtual machine monitor, runs operating systems as guests, each believing it controls real hardware. The classic technique is trap and emulate: run the guest kernel in user mode, so that every privileged instruction it executes traps to the hypervisor, which performs the instruction's effect on the guest's virtual state and resumes it. Gerald Popek and Robert Goldberg showed in 1974 that this works if every instruction that could reveal or change the machine's privileged state traps. For a long time x86 failed that test: a few instructions behaved differently in user mode without trapping. VMware worked around it in 1999 by rewriting guest kernel code on the fly, and Xen in 2003 by modifying guest kernels to call the hypervisor directly, which is paravirtualisation.

Since Intel's VT-x and AMD-V, in 2005 and 2006, the processor supports virtualisation directly. A guest runs in a special mode at full speed, kernel and all, and certain events cause a VM exit to the hypervisor: some privileged instructions, accesses to emulated devices, and interrupts. Linux's KVM, added to the kernel in 2007, turns Linux itself into a hypervisor, with QEMU emulating devices; most clouds run KVM or a close relative. A VM exit saves the guest's state, runs the hypervisor and resumes the guest, about a microsecond or two, and the example's last table shows why exits must be kept rare: 500,000 a second would take three quarters of a core. Paravirtual devices such as virtio, which batch requests through shared memory rings, and direct assignment of hardware devices to guests are the usual cures.

Memory for guests

A guest kernel has page tables that map its virtual addresses to what it believes are physical addresses. Those are really guest-physical addresses, which the hypervisor maps to the host's real memory with page tables of its own. With nested paging, Intel's EPT and AMD's NPT, the hardware walks both. Each of the guest's table pointers is itself a guest-physical address that needs a host walk, so a TLB miss walks a two-dimensional grid: up to (4 + 1) × (4 + 1) − 1 = 24 memory reads with four-level tables in both, against 4 natively, and 35 with five levels. TLBs and huge pages in the host matter even more for virtual machines than for processes, and hypervisors back guest memory with large pages whenever they can.

A container is a process

The Linux kernel has no "container" object. A container is an ordinary set of processes that the kernel shows a restricted view and holds to limits, using features added separately over a decade. Namespaces give a group of processes its own instance of a global resource: a PID namespace with its own process 1, which the host sees under some other number; a mount namespace with its own file-system tree; a network namespace with its own interfaces, addresses and ports; and namespaces for host name, users, IPC and cgroups. Cgroups limit and account for what the group uses: CPU, memory, I/O and the number of processes. On top of these come dropped capabilities, so that root inside the container lacks most of root's powers, and a seccomp filter that blocks system calls the workload shouldn't need. Docker, containerd and Kubernetes assemble all this from a container image, following the Open Container Initiative's specifications.

Images and layers

A container image is a stack of file-system layers, each a set of changes on top of the one below: a base distribution, then installed packages, then the application. overlayfs presents them as one directory tree. Looking up a path takes the topmost layer that has it, so a container sees its image's files without any of them being copied. The layers are read-only and shared by every container started from the image, and each container adds one thin writable layer on top. Writing to a file from a lower layer first copies the whole file up into the writable layer, copy-up, and deleting one leaves a whiteout entry that hides it. In the example, a container changes a configuration file and deletes the shell, and its neighbour, started from the same image, still sees both untouched.

# 1. A container image is a stack of read-only layers; each container adds one writable layer on top.
#    A lookup takes the topmost layer that has the path. Writes copy the file up; deletes leave a
#    "whiteout" marker that hides the lower copy.
WHITEOUT = object()
base = {"/bin/sh": "shell", "/etc/os-release": "Debian 13", "/usr/lib/libc.so": "libc"}
app = {"/app/server.py": "print('hi')", "/etc/app.conf": "port=8080"}
class Container:
    def __init__(self, *layers): self.layers, self.upper = layers, {}
    def read(self, path):
        for layer in (self.upper, *reversed(self.layers)):
            if path in layer:
                return None if layer[path] is WHITEOUT else layer[path]
        return None
    def write(self, path, data): self.upper[path] = data           # copy-up: the lower copy is untouched
    def delete(self, path): self.upper[path] = WHITEOUT
    def listing(self):
        paths = set().union(*self.layers, self.upper)
        return sorted(p for p in paths if self.read(p) is not None)

web1, web2 = Container(base, app), Container(base, app)            # two containers, one image
web1.write("/etc/app.conf", "port=9090")
web1.delete("/bin/sh")
print(f"web1 reads /etc/os-release: {web1.read('/etc/os-release')!r} (from the base layer)")
print(f"web1 reads /etc/app.conf:   {web1.read('/etc/app.conf')!r} (its own copy)")
print(f"web2 reads /etc/app.conf:   {web2.read('/etc/app.conf')!r} (the image is unchanged)")
print(f"web1 sees: {web1.listing()}")
print(f"web2 sees: {web2.listing()}")
print(f"web1's writable layer holds {len(web1.upper)} entries; both containers share the 2 image layers")

# 2. A cgroup CPU limit: cpu.max = "50000 100000" allows 50 ms of CPU per 100 ms period.
#    A burst of parallel work uses the whole quota early in the period, then waits for the next one.
def finish_time(cpu_ms_needed, threads, quota=50, period=100):
    t, used, done = 0, 0, 0.0
    while done < cpu_ms_needed:
        if t % period == 0: used = 0                               # a new period: the quota refills
        if used < quota:
            run = min(threads, quota - used, cpu_ms_needed - done)  # ms of CPU in this 1 ms tick
            used += run; done += run
        t += 1
    return t
print("\na request needing 120 ms of CPU, in a container limited to half a CPU:")
for threads in (1, 4):
    label = f"{threads} thread{'s' if threads > 1 else ''}:"
    print(f"   {label:10} finishes after {finish_time(120, threads):3} ms "
          f"(unlimited, on idle cores: {120 // threads} ms)")

# 3. Virtual machines and page tables: with nested paging, every guest table pointer must itself be
#    translated through the host's tables, so a TLB miss walks a two-dimensional grid of tables.
print()
for levels in (4, 5):
    nested = (levels + 1) * (levels + 1) - 1
    print(f"{levels}-level tables in the guest and the host: a TLB miss reads up to {nested:2} "
          f"table entries (native: {levels})")

# 4. What VM exits cost: each one saves the guest, runs the hypervisor and resumes (~1-2 µs)
print()
for exits_per_s in (1_000, 50_000, 500_000):
    share = exits_per_s * 1.5e-6
    print(f"   {exits_per_s:>7,} VM exits per second at 1.5 µs each: {share:6.2%} of a core")

web1 reads /etc/os-release: 'Debian 13' (from the base layer)
web1 reads /etc/app.conf:   'port=9090' (its own copy)
web2 reads /etc/app.conf:   'port=8080' (the image is unchanged)
web1 sees: ['/app/server.py', '/etc/app.conf', '/etc/os-release', '/usr/lib/libc.so']
web2 sees: ['/app/server.py', '/bin/sh', '/etc/app.conf', '/etc/os-release', '/usr/lib/libc.so']
web1's writable layer holds 2 entries; both containers share the 2 image layers

a request needing 120 ms of CPU, in a container limited to half a CPU:
   1 thread:  finishes after 220 ms (unlimited, on idle cores: 120 ms)
   4 threads: finishes after 205 ms (unlimited, on idle cores: 30 ms)

4-level tables in the guest and the host: a TLB miss reads up to 24 table entries (native: 4)
5-level tables in the guest and the host: a TLB miss reads up to 35 table entries (native: 5)

     1,000 VM exits per second at 1.5 µs each:  0.15% of a core
    50,000 VM exits per second at 1.5 µs each:  7.50% of a core
   500,000 VM exits per second at 1.5 µs each: 75.00% of a core

Limits: CPU quotas and throttling

Cgroups offer two kinds of CPU control. cpu.weight shares the processor in proportion when groups compete, like nice values (chapter 6). cpu.max sets a hard quota per period, such as 50 ms of CPU time every 100 ms, half a core. A quota counts CPU time across all of a container's threads, so a parallel burst can use the whole quota early in a period and then sit throttled until the next one starts. In the example, a request that needs 120 ms of CPU finishes in 220 ms on one thread, and still takes 205 ms on four threads, although four idle cores could finish it in 30. Throttling like this shows up as unexplained latency spikes on services that are nowhere near their average limit, which is why many teams running Kubernetes set CPU requests, which become weights, and leave CPU limits off. A related trap is a runtime that sizes its thread pool from the host's core count rather than the container's limit; the JVM has read cgroup limits since Java 10, and Go's GOMAXPROCS since Go 1.25. Memory limits are harder still: a container that exceeds memory.max is killed by the out-of-memory killer.

How strong is the wall?

A virtual machine's guest reaches the host only through the hypervisor and its virtual devices, a small and heavily scrutinised interface. A container's processes call straight into the host kernel, with its hundreds of system calls, and a single kernel bug can let one escape. Containers are therefore excellent for packaging and for running trusted workloads side by side, and need more care for untrusted code. Two families of projects bridge the gap. gVisor intercepts a container's system calls and serves them from its own user-space kernel. Kata Containers and Firecracker run each container in a lightweight virtual machine: Firecracker, built for AWS Lambda, boots a microVM in about 125 ms with under 5 MiB of overhead, which gives virtual-machine isolation with container-like speed.