🪭Operating Systems

From First Transistor to Distributed Systems & Security

About this note

This is a single, self-contained Obsidian vault note covering Operating Systems from the ground up - starting with how a computer physically works, through the three OS pillars (Virtualization, Concurrency, Persistence - the OSTEP framework), and extending into Distributed Systems and Security/Cryptography.

• Built on top of personal OSTEP (Operating Systems: Three Easy Pieces) chapter notes, merged, corrected, and heavily expanded.
• Missing foundational material (computer architecture basics, OS history, boot process, real-world kernels, extra diagrams, cheat-sheets) has been added.
• Uses Obsidian-flavored Markdown: callouts (> [!note]), Mermaid diagrams, and native LaTeX ($...$ inline, $$...$$ block).
• Designed to be read top to bottom (beginner → advanced) or jumped into via the Table of Contents below.

How to use this in Obsidian

1. Save as a .md file inside your vault (e.g. Operating Systems.md).
2. Install the Mermaid support (built-in since Obsidian 0.16+) - diagrams render automatically.
3. Turn on Settings → Editor → “Strict line breaks: off” for cleanest rendering of tables/lists.
4. Use Ctrl/Cmd + F outline, or the built-in Outline pane, to navigate headings - this file is long by design.
5. Consider splitting into linked notes later using Note Composer if you want a true multi-file vault; all headings are structured so that’s a clean cut.

---

🗺️ Table of Contents

• Part 0 - How a Computer Actually Works
• Part 1 - Introduction to Operating Systems
• Part 2 - Virtualizing the CPU
• Part 3 - Virtualizing Memory
• Part 4 - Concurrency
• Part 5 - Persistence (Storage & File Systems)
• Part 6 - Distributed Systems
• Part 7 - Security
• Part 8 - Real-World Operating Systems
• Part 9 - Cheat Sheets & Quick Reference
• Part 10 - Glossary
• Part 11 - Further Study

---

Part 0 - How a Computer Actually Works

Why start here?

An OS is a program that manages hardware. You cannot truly understand why an OS does what it does (traps, interrupts, page tables, DMA, caches) without a working mental model of the machine underneath it. This part builds that model from scratch.

0.1 What Is a Computer, Really?

At the lowest level, a computer is a machine built from transistors (tiny electrical switches) that are wired into logic gates (AND, OR, NOT, NAND, XOR…), which are combined into circuits that can:

1. Store a bit of information (flip-flops → registers → memory)
2. Compute on bits (adders, multiplexers, ALUs)
3. Move bits around (buses, wires)

Stacking abstractions upward:

Transistors  →  Logic Gates  →  Circuits (adders, muxes, registers)
     →  Datapath + Control  →  CPU (a "processor")
     →  CPU + Memory + I/O buses  →  A Computer
     →  Firmware + OS + Applications  →  A Usable System

The Big Idea

Every layer hides complexity from the layer above it. This idea - abstraction - is the single most important theme in all of computing, and it’s exactly what an Operating System does for hardware.

0.2 The von Neumann Architecture

Almost every general-purpose computer today follows the von Neumann model: a single memory stores both instructions (the program) and data, and the CPU fetches instructions from memory one at a time.

flowchart LR
    subgraph CPU["CPU (Central Processing Unit)"]
        CU["Control Unit\n(fetch/decode/dispatch)"]
        ALU["ALU\n(Arithmetic Logic Unit)"]
        REG["Registers\n(PC, SP, general-purpose)"]
        CU <--> ALU
        CU <--> REG
    end
    MEM[("Main Memory (RAM)\ninstructions + data")]
    IO["I/O Devices\n(disk, network, keyboard, GPU)"]

    CPU <--"Address Bus / Data Bus / Control Bus"--> MEM
    CPU <--"I/O Bus"--> IO

• CPU: executes instructions.
• Memory (RAM): holds the currently running program’s code and data (volatile - lost on power-off).
• I/O devices: everything else (disk, keyboard, network card, GPU, etc.).
• Buses: the “wires” connecting these - address bus (where), data bus (what), control bus (read/write signals).

The von Neumann Bottleneck

Because both instructions and data share the same bus to memory, the CPU can be starved waiting on memory - the CPU is almost always faster than memory. This single fact motivates an enormous amount of computer architecture (caches) and OS design (scheduling to hide I/O latency).

0.3 Inside the CPU

Component	Role
Program Counter (PC)	Holds the memory address of the next instruction to execute
Instruction Register (IR)	Holds the instruction currently being decoded/executed
General-Purpose Registers	Tiny, extremely fast storage (e.g., %rax, %rbx on x86-64) for operands/results
Stack Pointer (SP)	Points to the top of the current stack (function calls, local vars)
Status/Flags Register	Holds condition codes (zero, carry, overflow, sign) after ALU ops
ALU	Does arithmetic (add, sub, mul) and logic (and, or, xor, shift)
Control Unit	Orchestrates fetch → decode → execute; generates control signals
MMU (Memory Management Unit)	Translates virtual → physical addresses (crucial for OS memory virtualization, see [[#3.3 Mechanism - Address Translation

The Fetch–Decode–Execute Cycle

flowchart LR
    A["1. FETCH\ninstruction at address in PC\ninto Instruction Register"] --> B["2. DECODE\nfigure out opcode + operands"]
    B --> C["3. EXECUTE\nALU does the work /\nmemory is read or written"]
    C --> D["4. WRITEBACK\nstore result in register/memory"]
    D --> E["5. UPDATE PC\nPC = PC + instruction size\n(or jump target if branch)"]
    E --> A

This loop runs billions of times per second (a 3 GHz CPU completes ~3 billion cycles/sec; modern CPUs execute multiple instructions per cycle via pipelining and superscalar execution - beyond our scope here, but know the fetch-decode-execute idea still holds conceptually).

Why this matters for OS

A trap or interrupt (central to how OSes regain control of the CPU - see Limited Direct Execution) works by having hardware forcibly change the PC to jump into OS code, exactly like a special kind of instruction that hijacks step 5 above.

0.4 Number Systems & Data Representation

Computers only understand two voltage levels: 0 and 1 (a bit). Everything - numbers, text, images, instructions - is encoded in binary.

$$\text{1 nibble}=4\text{ bits}\text{1 byte}=8\text{ bits}\text{1 word}=4\text{ or }8\text{ bytes (32/64-bit systems)}$$

System	Base	Digits	Example
Binary	2	0,1	1010₂ = 10₁₀
Decimal	10	0-9	10
Hexadecimal	16	0-9,A-F	0xA = 10₁₀

Converting binary → decimal: for bits $b_{n-1}\dots b_1{b}_0$,

$$\text{value}=\sum _{i=0}^{n-1}{b}_i\cdot 2^i$$

Negative numbers are represented using two’s complement (invert bits, add 1) so hardware can use the same adder circuit for both addition and subtraction:

$$-x=\overline{x}+1$$

Floating point numbers (real numbers like 3.14) use the IEEE-754 standard: 1 sign bit, exponent bits, and mantissa (fraction) bits, representing:

$$\text{value}=(-1{)}^{\text{sign}}\times 1.\text{mantissa}\times 2^{\text{exponent}-\text{bias}}$$

Why programmers care

Integer overflow, 0.1 + 0.2 != 0.3 in most languages, and buffer sizes measured in bytes/KB/MB/GB - all trace back to these representations.

0.5 The Memory Hierarchy

Faster memory is more expensive and smaller; slower memory is cheap and huge. Systems are built as a hierarchy to get the illusion of memory that is both fast and large:

flowchart TD
    R["CPU Registers\n~ 1 KB · ~0.3 ns"] --> L1["L1 Cache\n~32-64 KB · ~1 ns"]
    L1 --> L2["L2 Cache\n~256KB-1MB · ~3-10 ns"]
    L2 --> L3["L3 Cache (shared)\n~8-32 MB · ~10-20 ns"]
    L3 --> RAM["Main Memory (DRAM)\n~8-128 GB · ~50-100 ns"]
    RAM --> SSD["SSD (Flash Storage)\n~256GB-4TB · ~10-100 µs"]
    SSD --> HDD["HDD (Spinning Disk)\n~1-16 TB · ~1-10 ms"]
    HDD --> NET["Network / Cloud Storage\n~unlimited · ~10-100+ ms"]

The key numbers to internalize ("Latency Numbers Every Programmer Should Know")

• L1 cache reference: ~1 ns
• Main memory reference: ~100 ns (100x slower than L1!)
• SSD random read: ~100 µs (1,000x slower than RAM)
• HDD seek: ~10 ms (100,000x slower than RAM)
• Round trip within same datacenter: ~500 µs

This enormous gap between CPU speed, memory speed, and disk speed is the reason OSes need: caching, buffering, scheduling, prefetching, and asynchronous I/O - nearly every OS mechanism you’ll study exists to hide or amortize this hierarchy’s latency.

Locality - why caching works at all

• Temporal locality: If you accessed data recently, you’ll likely access it again soon (e.g., loop variables).
• Spatial locality: If you accessed an address, you’ll likely access nearby addresses soon (e.g., iterating an array).

Every cache (CPU cache, disk buffer cache, browser cache, CDN) exploits one or both of these.

0.6 Buses, Motherboard, and Chipset

• Motherboard: the physical board connecting CPU, RAM, storage, and peripherals.
• Buses: shared communication pathways.
  • Front-Side Bus / Memory Bus: CPU ↔ RAM (very high speed).
  • PCIe Bus: CPU ↔ GPU, NVMe SSDs, network cards (high speed, point-to-point today).
  • SATA / USB / other peripheral buses: lower speed, external devices.
• Chipset: supporting circuitry that routes signals between CPU, memory, and peripheral controllers.

flowchart LR
    CPU((CPU)) ---|Memory Bus| RAM[(RAM)]
    CPU ---|PCIe| GPU[GPU]
    CPU ---|PCIe| NVME[(NVMe SSD)]
    CPU ---|DMI/Chipset| PCH[Chipset / PCH]
    PCH ---|SATA| HDD[(HDD/SSD)]
    PCH ---|USB| Periph[Keyboard/Mouse/USB]
    PCH ---|Ethernet| NIC[Network Card]

0.7 From Source Code to Running Program

Understanding this pipeline demystifies what “running a program” even means - essential background before Part 1’s discussion of processes.

flowchart LR
    SRC["Source Code\n(main.c)"] -->|"Compiler"| ASM["Assembly\n(main.s)"]
    ASM -->|"Assembler"| OBJ["Object File\n(main.o)\nmachine code + symbols"]
    OBJ -->|"Linker\n(+ libraries)"| EXE["Executable\n(a.out / .exe / ELF)"]
    EXE -->|"Loader\n(part of OS + exec())"| PROC["Running Process\nin memory"]

• Compiler: translates high-level source (C, Rust, Go…) into assembly for a target CPU architecture (x86-64, ARM, RISC-V).
• Assembler: turns human-readable assembly into raw machine code (binary opcodes).
• Linker: combines multiple object files + libraries (static or dynamic) into one executable, resolving symbol references (e.g., where is printf actually defined?).
• Loader: part of the OS; reads the executable format (e.g., ELF on Linux, PE on Windows, Mach-O on macOS), maps it into a fresh address space, and hands control to the CPU at the entry point - this is exactly what exec() does (see Process API).

Static vs Dynamic Linking

• Static linking: library code is copied directly into your executable at link time → bigger binary, no runtime dependency.
• Dynamic linking: your executable references a shared library (.so / .dll) that is loaded and linked at run time by the dynamic linker/loader → smaller binary, shared memory across processes using the same library, but requires the library to be present on the target system.

0.8 What Happens When You Turn On a Computer? (The Boot Process)

sequenceDiagram
    participant PWR as Power Button
    participant FW as Firmware (BIOS/UEFI)
    participant BL as Bootloader (GRUB/systemd-boot)
    participant KRN as OS Kernel
    participant INIT as init/systemd (PID 1)
    participant USR as User Space (login, apps)

    PWR->>FW: Power on → CPU starts executing firmware code at a fixed address
    FW->>FW: POST (Power-On Self Test): check CPU, RAM, devices
    FW->>BL: Locate boot device, load Bootloader into RAM
    BL->>BL: Present boot menu (if any), locate kernel image
    BL->>KRN: Load kernel + initial ramdisk into memory, jump to kernel entry
    KRN->>KRN: Initialize memory management, drivers, scheduler, filesystems
    KRN->>INIT: Mount root filesystem, start PID 1
    INIT->>USR: Start system services, login manager, shell/GUI

• Firmware (BIOS or modern UEFI): the very first code the CPU runs, stored in non-volatile flash chip on the motherboard. Performs POST, initializes essential hardware, then hands off to a bootloader.
• Bootloader (e.g., GRUB on Linux, Windows Boot Manager, systemd-boot): a small program whose only job is to locate and load the actual OS kernel into memory.
• Kernel initialization: the kernel sets up its own core data structures - memory allocator, interrupt tables, device drivers, the scheduler - and mounts the root filesystem.
• init / PID 1: the very first process the kernel starts (e.g., systemd on modern Linux, launchd on macOS). It starts every other system service and eventually a login prompt or GUI.

This is the moment the OS "takes over"

Before the kernel is loaded, there is no OS - just firmware directly controlling raw hardware. Everything this document covers from here on describes what the kernel does after this boot sequence completes.

---

Part 1 - Introduction to Operating Systems

1.1 What Is an Operating System?

Working definition

An Operating System (OS) is the software layer that sits between user applications and hardware. It manages hardware resources (CPU, memory, disk, devices) and provides convenient, safe abstractions so that programs don’t need to speak directly to hardware.

The OS has (at least) three jobs, matching the three parts of this document:

1. Virtualization - take a physical resource (CPU, memory) and transform it into a more general, powerful, and easy-to-use virtual version of itself.
2. Concurrency - safely manage many things happening “at once” (multiple programs, multiple threads sharing memory).
3. Persistence - reliably store data for the long term, even across crashes and power loss (files, file systems, disks).

mindmap
  root((Operating System))
    Virtualization
      CPU → Processes
      Memory → Address Spaces
    Concurrency
      Threads
      Locks / CVs / Semaphores
    Persistence
      Files & Directories
      File Systems
      Disks / SSDs / RAID
    Cross-cutting
      Security
      Distributed Systems
      Design goals

Design Goals of an OS

• Abstraction: hide hardware complexity behind clean interfaces (e.g., read()/write() instead of raw disk sector I/O).
• Performance: minimize overhead of virtualization (in time and space).
• Protection / Isolation: one buggy or malicious program should not be able to crash or spy on another.
• Reliability: the OS itself should not crash; it must run essentially forever.
• Energy-efficiency, security, mobility, etc., are modern additional goals.

1.2 The OS as a Resource Manager - and as an “Illusionist”

Classic view: the OS multiplexes (shares) hardware resources among competing programs, in time (e.g., CPU scheduling - who runs now) and in space (e.g., memory partitioning - who owns which bytes).

Modern view (OSTEP’s framing): the OS is a virtual machine builder. It takes physically limited, shared resources (one CPU, some RAM, one disk) and, via clever mechanisms and policies, presents each running program with the illusion that it has:

• Its own private CPU (via process virtualization + scheduling)
• Its own private, huge memory (via address space virtualization)
• Reliable, permanent storage (via file systems)

1.3 A Brief History of Operating Systems

Era	Approach	Key Idea
1940s-50s	No OS	Programmers directly operated hardware with switches/punch cards
Late 1950s	Batch systems	Jobs queued on tape/cards, run one after another by an operator/simple monitor program; no interactivity
1960s	Multiprogramming	Multiple jobs kept in memory at once; when one does I/O, CPU switches to another → better CPU utilization
Mid 1960s-70s	Time-sharing	Multiple interactive users share a machine, each getting the illusion of their own system (e.g., CTSS, Multics, and its successor UNIX, 1969-71, Bell Labs)
1980s	Personal Computers	Single-user OSes (MS-DOS) - initially simpler, later re-gained multiprogramming (Windows, classic Mac OS)
1990s-2000s	Modern multitasking OSes	Linux (1991), Windows NT, Mac OS X (built on BSD/Mach) - full protection, virtual memory, multiprocessing
2000s-2010s	Mobile & Cloud	Android, iOS (resource/battery-constrained); Hypervisors & VMs; containers (cgroups + namespaces)
2010s-present	Distributed & Specialized	Cloud-native OS design, microVMs (Firecracker), unikernels, serverless - the OS concepts you’re learning now applied at datacenter scale

Why UNIX matters

Much of what you’ll learn (fork(), exec(), the process model, hierarchical file systems, “everything is a file”) originates in UNIX (1969, Ken Thompson & Dennis Ritchie at Bell Labs) and lives on almost unchanged in Linux, macOS (BSD-derived), and even conceptually influences Windows.

1.4 Kernel Mode vs. User Mode - the Core Protection Mechanism

The CPU itself supports (at least) two privilege levels:

• User mode: restricted. Code cannot directly execute privileged instructions (e.g., directly touching disk controllers, changing page tables, halting the CPU) or access arbitrary memory.
• Kernel mode (a.k.a. supervisor mode): unrestricted. Only OS code runs here - full hardware access.

sequenceDiagram
    participant App as User Application (user mode)
    participant HW as CPU Hardware
    participant OS as OS Kernel (kernel mode)

    App->>HW: execute normal instructions
    App->>HW: system call (e.g. read()) → TRAP instruction
    HW->>HW: save user context, raise privilege, jump to trap table entry
    HW->>OS: control transferred into kernel mode
    OS->>OS: handle request (e.g. perform the actual disk read)
    OS->>HW: return-from-trap instruction
    HW->>HW: restore user context, lower privilege
    HW->>App: resume execution in user mode

This trap mechanism is how a user program asks the OS to do something on its behalf (a system call), and it’s also how hardware interrupts (timer, disk finished, keyboard press) and exceptions (divide by zero, page fault, illegal instruction) get the kernel’s attention. It’s covered in depth in Limited Direct Execution.

System Calls - the OS’s API

A system call looks like a normal function call from the programmer’s point of view (e.g., read(), write(), open(), fork()), but under the hood it executes a special trap instruction that switches the CPU into kernel mode so the OS can safely perform the privileged operation, then traps back.

// Looks like a normal call...
ssize_t n = read(fd, buffer, size);
// ...but under the hood: user code → trap → kernel handler → return-from-trap → user code

System call vs. library call

printf() is a library function; internally it eventually calls the write() system call. Not every function you use is a syscall - only ones that need privileged/kernel help (I/O, process control, memory mapping, etc.) are.

1.5 Kernel Architectures: Monolithic vs. Microkernel vs. Hybrid

flowchart TB
    subgraph Mono["Monolithic Kernel (e.g., Linux)"]
        direction TB
        M1["User Applications"] -.syscall.-> M2["Entire Kernel: scheduler, memory mgmt,\nfile systems, device drivers, network stack\n- all in one address space, kernel mode"]
    end
    subgraph Micro["Microkernel (e.g., Minix, QNX, seL4)"]
        direction TB
        U1["User Applications"] -.IPC.-> U2["Minimal Kernel:\nscheduling, IPC, basic memory mgmt only"]
        U2 -.IPC.-> U3["File System\n(user-space server)"]
        U2 -.IPC.-> U4["Device Drivers\n(user-space servers)"]
        U2 -.IPC.-> U5["Network Stack\n(user-space server)"]
    end

	Monolithic	Microkernel
Everything (drivers, FS, network)	Runs in kernel mode, one address space	Runs as separate user-mode servers
Performance	Faster (direct function calls)	Slower (message-passing/IPC overhead)
Reliability/Isolation	A buggy driver can crash the whole OS	A crashing driver/server can often be restarted without a full crash
Examples	Linux, traditional UNIX, (classic) Windows core	Minix 3, QNX, seL4, (historically) Mach
Hybrid	Windows NT and macOS/XNU are hybrid: microkernel-inspired design but with many services (like graphics, file systems) run in kernel space for performance.

1.6 Mechanisms vs. Policies - a Recurring Theme

This separation shows up everywhere in OS design and is one of the most important ideas in this entire document.

• Mechanism: the low-level “how” - the machinery that makes something possible. E.g., “how do we save and restore CPU registers to switch from running process A to process B?” (→ context switch).
• Policy: the high-level “which/what” - the decision-making logic on top of the mechanism. E.g., “which process should we run next?” (→ scheduling policy, like Round-Robin or MLFQ).

Separating these lets you change policy (e.g., swap in a smarter scheduler) without rewriting the underlying mechanism (context switching code stays the same). You’ll see this split explicitly in CPU scheduling and page-replacement policies later.

---

Part 2 - Virtualizing the CPU

The core question of this Part

How does the OS virtualize the CPU? A machine typically has a handful of physical CPU cores, yet it appears to run hundreds of programs “simultaneously.” The answer: time-sharing - running one process for a little while, then switching to another, over and over, so fast it creates the illusion of parallelism (even on a single core).

2.1 The Abstraction: The Process

What Is a Process?

Definition

A process is the OS’s abstraction for a running program. It bundles a program’s code and data with all the runtime state needed to execute it: registers, program counter, stack, heap, and OS-level bookkeeping (open files, etc.).

A program on disk is just static bytes. A process is that program brought to life: loaded into memory, given a stack and heap, and set running by the CPU.

The Process’s Machine State

To fully describe a process at any instant, the OS tracks:

• Memory (address space): the code, data, heap, and stack the process can address.
• Registers: general-purpose registers, plus special ones:
  • Program Counter (PC) - next instruction to execute.
  • Stack Pointer (SP) / Frame Pointer (FP) - manage the stack for function calls, local variables, return addresses.
• I/O information: list of open files, sockets, etc.

Process Creation, Step by Step

flowchart TD
    A["1. Load code + static data\nfrom disk into address space\n(lazily, via demand paging, in modern OSes)"] --> B["2. Allocate run-time stack\n(argc, argv, main()'s locals)"]
    B --> C["3. Allocate heap\n(small initially; grows via malloc/brk/sbrk)"]
    C --> D["4. Set up I/O\n(3 file descriptors opened by default:\nstdin=0, stdout=1, stderr=2)"]
    D --> E["5. Start execution at main()\n(OS jumps PC to the entry point)"]

Process States

stateDiagram-v2
    [*] --> Ready: created
    Ready --> Running: scheduled
    Running --> Ready: descheduled (preempted)
    Running --> Blocked: issues I/O / waits on event
    Blocked --> Ready: I/O completes
    Running --> [*]: exit

• Running: currently executing instructions on a CPU.
• Ready: could run, but the OS has chosen not to run it right now.
• Blocked: performed some operation (e.g., I/O) that makes it not ready until that event completes.

Moving processes between ready and running is entirely the scheduler’s decision (see §2.4). Moving to/from blocked is driven by I/O and other events.

The Process List / Process Control Block (PCB)

The OS keeps a process list (in Linux, a doubly-linked list of task_structs) - one entry per process - often called a Process Control Block (PCB). It holds the register context (when not running), state, PID, open file table, and more, so the OS can pause and later perfectly resume any process.

Linux tools to explore this yourself

• ps aux - list running processes and their states.
• top / htop - live view of CPU/memory usage per process.
• /proc/<pid>/status, /proc/<pid>/maps - deep inspection of a specific process.

2.2 Process API

The classic UNIX process API is deceptively small but very powerful:

Call	Purpose
fork()	Create a near-exact copy of the calling process (the “child”)
exec() family	Replace the calling process’s memory image with a new program
wait() / waitpid()	Block until a child process terminates, reap its exit status
exit()	Terminate the calling process
kill()	Send a signal (e.g., request termination) to another process

fork() - the Strange, Powerful Call

fork() creates a new process that is (almost) an exact copy of the caller: same code, same variable values, same open files - but a different, independent address space and PID from that point forward. Uniquely, fork() returns twice: once in the parent (returning the child’s PID), once in the child (returning 0).

#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>
 
int main() {
    printf("hello (pid:%d)\n", (int) getpid());
    int rc = fork();
    if (rc < 0) {
        // fork failed
        fprintf(stderr, "fork failed\n");
    } else if (rc == 0) {
        // child process
        printf("child (pid:%d)\n", (int) getpid());
    } else {
        // parent process
        int wc = wait(NULL);
        printf("parent of %d (rc_wait:%d) (pid:%d)\n", rc, wc, (int) getpid());
    }
    return 0;
}

Non-determinism

After fork(), the OS scheduler decides whether parent or child runs first - this is a genuinely non-deterministic race, and well-written code must not assume either order (unless synchronized, e.g. via wait()).

exec() - Replacing the Program Image

exec() (and variants execve, execvp, execl…) loads a new program’s code and static data, overwriting the current address space, and starts running it from main(). Critically: it does not create a new process - the PID stays the same. A successful exec() never returns (the old program is simply gone).

Why Separate fork() and exec()? - Enabling the Shell

This split (unique to UNIX; most other systems have a single “spawn” call) is what makes shell redirection and pipes possible: the shell can fork(), then in the child modify its own file descriptors (e.g., redirect stdout to a file) before calling exec(), leaving the parent shell untouched.

sequenceDiagram
    participant Shell
    participant Child
    participant Kernel

    Shell->>Kernel: fork()
    Kernel-->>Shell: returns child PID
    Kernel-->>Child: returns 0
    Child->>Child: modify fds (e.g., close(1); open("out.txt", O_WRONLY))
    Child->>Kernel: exec("wc", ["wc", "file.txt"])
    Kernel-->>Child: process image replaced by wc, output goes to out.txt
    Shell->>Kernel: wait()
    Kernel-->>Shell: returns when child exits

This is precisely how wc file.txt > out.txt and grep foo file | wc -l (pipes) are implemented - a beautiful, minimal design.

Signals

The OS can asynchronously notify a process of an event via signals (kill(), Ctrl-C → SIGINT, segfault → SIGSEGV). Processes can install signal handlers to intercept and react to signals instead of taking the default action (usually termination).

2.3 Mechanism - Limited Direct Execution

The Goal, and the Problem

We want processes to run directly on the CPU for performance (no per-instruction emulation/interpretation overhead) - this is called direct execution. But pure direct execution raises two hard problems:

1. Restricted operations: what stops a process from doing whatever it wants (e.g., issuing arbitrary disk I/O, or simply hogging the CPU forever)?
2. Switching between processes: if a process just runs directly on the CPU, how does the OS ever regain control to switch to another process?

Limited Direct Execution (LDE) is the solution: run the program directly on the CPU, but with hardware-enforced limits.

Problem 1: Restricted Operations → User/Kernel Mode + Traps

As covered in §1.4: privileged operations can only be performed via a system call, which executes a special trap instruction. This instruction:

1. Raises the hardware privilege level to kernel mode.
2. Jumps to a pre-configured, OS-installed handler (the process cannot pick an arbitrary jump target - this address is set up once, at boot, by the trusted kernel, via a trap table).

flowchart LR
    Boot["At Boot: OS installs\nTrap Table\n(syscall # → handler address)"] --> Run["Process runs in user mode"]
    Run -->|"trap (syscall)"| Handler["CPU looks up handler in\ntrap table, switches to\nkernel mode, jumps there"]
    Handler --> KCode["Kernel handles request"]
    KCode -->|"return-from-trap"| Run

Problem 2: Switching Between Processes → the Timer Interrupt + Context Switch

If a process is running directly on the CPU, a purely cooperative approach (trusting processes to periodically yield via system calls) is fragile - an infinite loop with no syscalls would hang the machine forever.

The real solution is a non-cooperative approach: a hardware timer device raises an interrupt at regular intervals (e.g., every few milliseconds), unconditionally transferring control to the OS - the process has no say in this. This guarantees the OS always regains control periodically.

When the OS regains control (via timer interrupt, or a process voluntarily traps/blocks), it may decide to switch to a different process - a context switch:

sequenceDiagram
    participant A as Process A (running)
    participant OS as OS (Kernel)
    participant B as Process B (was Ready)

    Note over A: A is executing normally
    A->>OS: Timer interrupt fires (hardware, forced)
    OS->>OS: save A's register state into A's PCB
    OS->>OS: scheduler picks next process = B
    OS->>OS: restore B's register state from B's PCB
    OS->>B: return-from-trap into B's context
    Note over B: B resumes exactly where it left off

A context switch is just: save current registers to the outgoing process’s PCB, restore saved registers from the incoming process’s PCB. Costs real time (microseconds) - cache/TLB effects make the indirect cost even larger, which is why context switching isn’t free and scheduling policy matters.

LDE Summary

• Baseline: run the program directly - fast.
• Restricted ops: handled via user/kernel mode + traps into a kernel-controlled trap table.
• Switching: handled via a timer interrupt (forces periodic OS control) + context switching (save/restore state).

2.4 Scheduling: Introduction

Once the OS can regain control at will, it needs a policy: given several ready processes, which one should run next? This is the scheduler’s job.

Workload Assumptions (to start simply)

1. Each job runs for the same amount of time.
2. All jobs arrive at the same time.
3. Once started, each job runs to completion.
4. All jobs only use the CPU (no I/O).
5. The run-time of each job is known in advance.

(These are relaxed one by one as the chapter - and real schedulers - progress.)

Scheduling Metrics

$$T_{turnaround}=T_{completion}-T_{arrival}$$ $$T_{response}=T_{firstrun}-T_{arrival}$$

• Turnaround time: total time from arrival to completion - a performance metric.
• Response time: time from arrival until first scheduled - critical for interactive systems.
• Fairness is often in direct tension with turnaround-time/performance optimization.

Scheduling Policies

FIFO (First In, First Out) - simplest possible; run jobs in arrival order.

The Convoy Effect

If a short job queues behind a long job, the short job’s turnaround time is terrible - like being stuck behind a slow truck (“convoy”) on a one-lane road.

SJF (Shortest Job First) - run the job with the shortest total run-time next. Optimal average turnaround time if all jobs arrive together, but if a short job arrives just after a long job has started, it must still wait (violates assumption 2).

STCF / PSJF (Shortest Time-to-Completion First) - preemptive version of SJF: whenever a new job arrives, if it has less remaining time than the currently running job, preempt and switch to it. Optimal for turnaround time, but can starve response time for a long job continuously interrupted by shorter arrivals.

Round Robin (RR) - run each job for a fixed time slice (a.k.a. scheduling quantum), then switch to the next job in the queue, cycling around.

$$\text{Response time (worst-ish)}\approx \frac{n-1}{n}\times q\text{for }n\text{ jobs, quantum }q$$

• Excellent for response time, terrible for turnaround time (each job takes longer overall since it’s constantly interrupted).
• The length of the time slice is a critical tradeoff: too short → excessive context-switch overhead; too long → poor responsiveness (degrades toward FIFO).

Policy	Good at	Bad at
FIFO	Simplicity	Convoy effect, poor turnaround with mixed job lengths
SJF / STCF	Turnaround time (avg)	Response time, starvation of long jobs, needs future knowledge
Round Robin	Response time, fairness	Turnaround time

Incorporating I/O

Real jobs alternate between CPU bursts and I/O. A good scheduler overlaps I/O of one process with CPU execution of another - treating each CPU burst as its own mini “job” (this is what makes STCF-like reasoning still useful with I/O in the mix).

The unsolved problem so far

STCF/SJF need to know the future (job lengths in advance) - unrealistic! This motivates MLFQ, next.

2.5 Scheduling: The Multi-Level Feedback Queue (MLFQ)

MLFQ tries to achieve two ideally-conflicting goals without any prior knowledge of job length:

1. Optimize turnaround time (like SJF/STCF).
2. Minimize response time (like Round Robin) - feel interactive/responsive.

It learns from the past to predict the future: by observing how a job behaves, it infers whether the job is interactive (short bursts, needs responsiveness) or CPU-bound (long bursts, less latency-sensitive).

Structure

Multiple distinct queues, each with a different priority level. A job at a higher-priority queue is always run before one at a lower-priority queue (Round Robin within the same-priority queue if multiple jobs share it).

flowchart TD
    Q1["Queue 1 (Highest Priority)\nshort time slice"] -->|"uses full slice"| Q2["Queue 2\nmedium time slice"]
    Q2 -->|"uses full slice"| Q3["Queue 3 (Lowest Priority)\nlong time slice"]
    Q1 -.->|"gives up CPU before slice ends (I/O)"| Q1
    Q3 -.->|"periodic priority boost"| Q1

The Basic Rules

• Rule 1: If Priority(A) > Priority(B), A runs.
• Rule 2: If Priority(A) = Priority(B), A & B run in round-robin.
• Rule 3: When a job enters the system, place it at the highest priority.
• Rule 4: Once a job uses up its time allotment at a given level (regardless of how many times it gave up the CPU), its priority is reduced (it moves down one queue). (Later refined rule, replacing separate Rule 4a/4b.)
• Rule 5: After some time period $S$, move all jobs in the system to the topmost queue (priority boost).

Why Each Rule Exists

• Rules 1-3 give new/short jobs great response time immediately (they start at the top).
• A CPU-bound job will quickly burn through its slice and get demoted - naturally separating interactive jobs (which yield quickly for I/O, staying high) from batch/CPU-bound jobs (which sink to low-priority queues) - without knowing job length in advance!
• Rule 5 (priority boost) prevents starvation: without it, a CPU-bound job could be permanently stuck behind a steady stream of interactive jobs. Periodically resetting everyone to the top guarantees forward progress.
• Using total time allotment accounting (rather than resetting priority just because a job yielded for I/O) prevents gaming the scheduler - a malicious/greedy process issuing a tiny I/O just before its slice ends to stay at high priority forever.

Tuning MLFQ

Real MLFQ implementations (e.g., historically in Solaris) use tables to tune time-slice length per level (short at top, long at bottom) and boost interval $S$ - these are pure empirical, workload-dependent parameters, a recurring theme in systems design.

2.6 Scheduling: Proportional Share (Fair-Share Scheduling)

Rather than optimizing turnaround/response time, a proportional-share (fair-share) scheduler guarantees each job gets a specific percentage of CPU time.

Lottery Scheduling

Each job holds a number of tickets; the scheduler holds a “lottery” every time slice, picking a random winning ticket - the job holding it runs next.

$$P(\text{job }i\text{ runs})=\frac{{\text{tickets}}_i}{{\sum }_j{\text{tickets}}_j}$$

• Probabilistic fairness: over the long run, each job gets CPU time proportional to its ticket share - but with no hard guarantee in the short term.
• Ticket currency: users can allocate their own tickets among their jobs in local “currency,” then convert to the global currency - enabling flexible sub-allocation.
• Ticket transfer: a process can temporarily hand its tickets to another (e.g., a client boosting a server it’s blocked waiting on - avoids priority-inversion-like problems).
• Ticket inflation: a (trusted) process can boost/deflate its own ticket count temporarily.

Randomness is the “engine”: it avoids the pathological worst-case behavior of many deterministic policies (e.g., starvation), at the cost of some short-term unfairness (which mostly washes out over many time slices).

Stride Scheduling - a Deterministic Alternative

Give each job a stride, inversely proportional to its tickets:

$${\text{stride}}_i=\frac{\text{large\_number}}{{\text{tickets}}_i}$$

Each job also has a pass value, starting at 0. The scheduler always picks the job with the lowest pass value, then increments that job’s pass value by its stride.

$${\text{pass}}_i+={\text{stride}}_i\text{(after job }i\text{ runs)}$$

Result: jobs with more tickets (smaller stride) get picked more often - perfectly deterministic proportional sharing, at the cost of needing global state (making it harder to have a new job join mid-stream fairly - lottery scheduling handles this more gracefully).

Linux's CFS (Completely Fair Scheduler)

Modern Linux uses CFS, conceptually similar in spirit to stride scheduling: it tracks each task’s virtual runtime (vruntime) and always picks the task with the smallest vruntime to run next, using a red-black tree for $O(\log n)$ selection. nice values weight how fast vruntime accumulates, implementing proportional share without needing literal “tickets.” See Real-World: Linux.

2.7 Multiprocessor Scheduling (Advanced)

Modern machines have multiple CPUs/cores, introducing new challenges beyond single-CPU scheduling.

Cache Coherence & Cache Affinity

Each CPU has its own cache. If a process migrates from CPU 0 to CPU 1, its data must be re-fetched into CPU 1’s cache (cold cache), costing performance. Good multiprocessor schedulers exhibit cache affinity: try to keep a process running on the same CPU when possible.

Cache coherence (a hardware problem, solved via protocols like MESI bus-snooping) ensures that if CPU 0 writes a value, CPU 1 doesn’t see a stale cached copy - necessary for correctness of any shared-memory concurrent program (see Part 4).

Single-Queue vs. Multi-Queue Scheduling

flowchart LR
    subgraph SQMS["Single-Queue Multiprocessor Scheduling (SQMS)"]
        Q[("One shared ready queue")]
        Q --> C0[CPU 0]
        Q --> C1[CPU 1]
        Q --> C2[CPU 2]
    end
    subgraph MQMS["Multi-Queue Multiprocessor Scheduling (MQMS)"]
        Q0[("Queue 0")] --> D0[CPU 0]
        Q1[("Queue 1")] --> D1[CPU 1]
        Q2[("Queue 2")] --> D2[CPU 2]
    end

• SQMS: simple, reuses single-CPU policy logic, naturally load-balanced - but needs locking for the shared queue (contention/scalability bottleneck at high core counts) and has poor cache affinity (jobs bounce between CPUs).
• MQMS: scales better (each queue is independently locked/managed), better cache affinity - but can suffer load imbalance (one CPU’s queue empties while another’s stays full), requiring migration to rebalance (e.g., work stealing, where an idle CPU “steals” a job from a busy CPU’s queue).

Real-world takeaway

Linux’s scheduler uses a multi-queue design (per-CPU run queues) with periodic load-balancing/work-stealing - this pattern (partition + rebalance) recurs across many systems, not just OS scheduling (e.g., distributed task queues).

---

Part 3 - Virtualizing Memory

The core question of this Part

How does the OS give every process the illusion of its own large, private, contiguous memory - while dozens of processes actually share one small, physical RAM chip?

3.1 The Abstraction: Address Spaces

From Physical Memory to Virtual Memory

Early systems: no abstraction at all - a single running program addressed physical memory directly, alongside OS code.

0KB  ┌──────────────────┐
     │ Operating System  │
     │  (code, data)     │
16KB ├──────────────────┤
     │  Current Program  │
     │ (code, data, etc.)│
64KB └──────────────────┘

As multiprogramming and time-sharing took hold, this broke down: multiple programs needed to reside in memory simultaneously, each protected from the others, without being rewritten to know their exact physical location. The solution: the address space.

The Address Space

Definition

The address space is a process’s view of memory in the system - a private abstraction containing all the memory state of a running program.

Classic (simplified) layout:

        High Address
     ┌───────────────────┐
     │       Stack        │   ← grows DOWNWARD
     │         ↓           │
     │                     │
     │      (free)         │
     │                     │
     │         ↑           │
     │        Heap         │   ← grows UPWARD
     ├───────────────────┤
     │   Data (globals)    │
     ├───────────────────┤
     │    Code (text)      │
     └───────────────────┘
        Low Address (0)

• Code: the program’s instructions - static, fixed-size.
• Heap: dynamically allocated memory (malloc/new) - grows as needed.
• Stack: local variables, function-call bookkeeping (return addresses, saved registers) - grows/shrinks with function calls/returns.

Stack and heap grow toward each other so either can use free space flexibly (in this simplified model - real modern layouts add guard pages, ASLR randomization, shared library mappings, memory-mapped files, etc. - see the pmap example below).

Goals of Virtual Memory

1. Transparency: the program shouldn’t notice it’s being virtualized - it behaves as if it owns all of memory, starting at address 0.
2. Efficiency: virtualization should be fast (time) and not waste too much memory (space) - achieved with hardware support (MMU, TLBs).
3. Protection: a process must not be able to read/write another process’s (or the OS’s) memory - isolation is the key benefit that lets the OS safely multiplex physical memory.

Every address a program generates is a virtual address; the OS (with hardware help) translates it to a physical address - this translation is invisible to the program itself.

Exploring this yourself on Linux

• free -h - total/used/free physical memory & swap on the system.
• pmap -x <pid> - detailed memory map of a process: you’ll see it’s far richer than “code/heap/stack” - shared libraries (libc.so), memory-mapped files, multiple anonymous regions, guard pages, etc. Modern address spaces are segmented into many independently-permissioned regions.

3.2 Interlude: Memory API

malloc() / free() and the Heap

#include <stdlib.h>
void *malloc(size_t size);  // allocate `size` bytes, return pointer (or NULL on failure)
void free(void *ptr);       // release previously-allocated memory

• malloc() returns a void*; the size of the allocation is tracked internally by the allocator (often in a small header just before the returned pointer) - free() doesn’t need you to re-specify the size.
• Underlying system calls: brk()/sbrk() (move the “break,” extending the heap) historically; modern large allocations often use mmap() directly.

Common Memory Bugs

Bug	Description
Forgetting to allocate (e.g., not malloc-ing before strcpy)	Writes into garbage/unallocated memory
Not allocating enough memory (buffer overflow)	Classic security vulnerability - can overwrite adjacent memory, return addresses (stack smashing)
Forgetting to initialize	Reading uninitialized memory → undefined/garbage values
Memory leak	Forgetting free() - memory usage grows unboundedly over time
Dangling pointer	Using memory after free()-ing it (use-after-free)
Double free	Calling free() twice on the same pointer - corrupts allocator metadata
Invalid free	Calling free() on a pointer that wasn’t returned by malloc()

Why this matters for security

Buffer overflows and use-after-free bugs are among the most common and most exploited security vulnerabilities in systems software (see Part 7). Tools like Valgrind, AddressSanitizer (ASan), and memory-safe languages (Rust) exist largely to combat this class of bug.

3.3 Mechanism - Address Translation

Hardware-based Address Translation

The CPU’s MMU (Memory Management Unit) transforms every virtual address the program generates into a physical address, on every single memory reference, with hardware support for speed. The OS’s job: set up and manage the data structures the MMU uses, and handle any exceptional cases (e.g., invalid addresses).

This follows the LDE philosophy from Part 2: let the hardware do the fast, common-case work directly; let the OS step in only when needed (setup, exceptions).

Dynamic Relocation (Base & Bounds)

The simplest hardware mechanism: each CPU has a base register and a bounds (limit) register per process.

$$\text{physical address}=\text{virtual address}+\text{base}$$

with a bounds check:

$$0\le \text{virtual address}<\text{bounds}\text{(else: raise a protection fault)}$$

flowchart LR
    VA["Virtual Address\n(generated by CPU)"] --> Check{"0 ≤ VA < Bounds?"}
    Check -->|No| Fault["Trap to OS:\nSegmentation Violation"]
    Check -->|Yes| Add["Physical Address =\nVA + Base"]
    Add --> Mem[("Physical Memory")]

The base and bounds registers are part of each process’s context - saved/restored on every context switch, just like general-purpose registers. Changing them requires privileged (kernel-mode) instructions - a process must not be able to change its own base/bounds and escape its sandbox!

Internal vs. External Fragmentation

Base & bounds requires each process’s entire address space to sit in one contiguous chunk of physical memory. This wastes memory two ways:

• Internal fragmentation: unused space within an allocated region (e.g., the free space between heap and stack in the address space still needs physical backing in this scheme).
• External fragmentation: free physical memory exists, but is broken into small chunks - no single chunk is big enough for a new request, even though the total free space would suffice.

3.4 Segmentation

Instead of one base/bounds pair for the whole address space, use one pair per logical segment (code, heap, stack) - allowing:

1. Sparse address spaces: unused space between heap and stack no longer needs physical backing (fixes a chunk of internal fragmentation).
2. Sharing: a protection bit per segment allows, e.g., sharing a read-only code segment across multiple processes running the same program (saves physical memory).

Segment  | Base  | Bounds | Grows
---------|-------|--------|-------
Code     | 32KB  | 2KB    | no
Heap     | 34KB  | 2KB    | up (+)
Stack    | 28KB  | 2KB    | down (-)

• The top bits of a virtual address select the segment; the remaining bits are the offset within it.
• Stack segments need a direction bit (grows downward - the hardware must subtract, not add, the offset, and check bounds accordingly).

Remaining problem: External Fragmentation

As variable-sized segments are allocated/freed over time, physical memory becomes checkered with free holes of varying (awkward) sizes. Solutions: compaction (pause everything, slide processes together to consolidate free space - expensive!) or smarter free-space allocators (next section).

3.5 Free-Space Management

Managing a free list of variable-sized chunks (heap allocators, or segmentation’s physical memory) is a classic, still-relevant problem.

Allocation Strategies

Strategy	Approach	Tradeoff
Best Fit	Search the whole list, pick the smallest free chunk that fits	Minimizes wasted space per allocation, but slow (full search) and creates many tiny unusable fragments
Worst Fit	Pick the largest free chunk	Leaves a large-ish leftover chunk, but empirically fragments badly too
First Fit	Pick the first chunk that fits	Fast, reasonable fragmentation behavior
Next Fit	Like First Fit, but resumes search from where the last search ended	Spreads out search overhead, similar fragmentation to First Fit

Reducing Fragmentation: Segregated Lists & Buddy Allocation

• Segregated free lists: keep separate free lists for popular fixed sizes (e.g., common object sizes) - very fast, avoids fragmenting between unrelated size classes. The slab allocator (used in the Linux/Solaris kernels for kernel object caches) is a refined version of this idea.
• Buddy Allocation: memory is recursively split into power-of-two-sized “buddy” halves. A request is rounded up to the nearest power of two and split down from the top until a good fit is found. Freeing is fast because a block’s “buddy” address is computable via simple bit-flip arithmetic, enabling quick coalescing back into larger free blocks.

$$\text{buddy}(\text{address},\text{size})=\text{address}\oplus \text{size}$$

Header metadata

Most allocators store a small header just before each returned pointer (size, magic number for corruption checks, sometimes a pointer for an embedded free list). This is why free(ptr) doesn’t need a size argument.

3.6 Paging: Introduction

Segmentation still deals in variable-sized chunks → still suffers external fragmentation. Paging solves this by dividing memory into small, fixed-size units.

• Virtual memory is divided into fixed-size pages.
• Physical memory is divided into same-size page frames.
• A per-process page table maps virtual pages → physical frames.

flowchart LR
    subgraph VAS["Virtual Address Space (process)"]
        VP0["Page 0"]
        VP1["Page 1"]
        VP2["Page 2"]
        VP3["Page 3"]
    end
    subgraph PT["Page Table (per process)"]
        E0["VPN 0 → PFN 3"]
        E1["VPN 1 → PFN 7 (invalid)"]
        E2["VPN 2 → PFN 1"]
        E3["VPN 3 → PFN 5"]
    end
    subgraph PM["Physical Memory (frames)"]
        F1["Frame 1"]
        F3["Frame 3"]
        F5["Frame 5"]
        F7["Frame 7"]
    end
    VP0 --> E0 --> F3
    VP2 --> E2 --> F1
    VP3 --> E3 --> F5

Splitting a Virtual Address

A virtual address splits into a Virtual Page Number (VPN) and an offset:

$$\text{VA}=\underset{\text{high bits}}{\underbrace{\text{VPN}}}\Vert \underset{{\log }_2(\text{page size})\text{ bits}}{\underbrace{\text{offset}}}$$

Translation: look up VPN in the page table → get Physical Frame Number (PFN); the offset is unchanged.

$$\text{PA}=\text{PFN}\Vert \text{offset}$$

Page Table Entries (PTE)

Beyond the PFN, each entry typically holds:

• Valid bit: is this virtual page actually in use by the process?
• Protection bits: read/write/execute permissions.
• Present bit: is the page currently in physical memory, or swapped to disk?
• Dirty bit: has the page been modified since being loaded?
• Reference/Accessed bit: has the page been recently accessed? (used by replacement policies)

Where Are Page Tables Stored?

Page tables are per-process and typically large - stored in physical memory itself (managed by the OS). A special hardware register, the Page Table Base Register (PTBR), points to the currently-running process’s page table; it’s switched on every context switch.

The cost of paging so far

A naive linear page table can be huge (e.g., a 32-bit address space with 4KB pages needs $2^{20}$ entries per process!) and every memory reference now needs an extra memory access just to read the page table entry - doubling memory access time. These two problems motivate TLBs (§3.7) and smaller table structures (§3.8).

3.7 Translation Look-aside Buffers (TLBs)

A TLB is a small, fast, fully-associative hardware cache of virtual-to-physical address translations, part of the MMU, exploiting the same locality principles as CPU caches (§0.5).

flowchart TD
    VA["Virtual Address"] --> Split["Split into VPN + offset"]
    Split --> Check{"VPN in TLB?"}
    Check -->|"TLB HIT (fast!)"| PA1["Combine cached PFN + offset\n→ Physical Address"]
    Check -->|"TLB MISS (slow)"| Walk["Walk page table in memory\n(hardware or OS, depending on architecture)\nto find PFN"]
    Walk --> Insert["Insert (VPN→PFN) into TLB"]
    Insert --> Retry["Retry the instruction"]

• TLB hit: translation found in the TLB - extremely fast, no extra memory access needed.
• TLB miss: must consult the full page table in memory (walking it, possibly multiple levels) - much slower. The result is then cached in the TLB for next time.

Who Handles a TLB Miss?

• Hardware-managed TLBs (e.g., x86): the CPU itself knows the page table format and walks it on a miss.
• Software-managed TLBs (e.g., MIPS, SPARC): a TLB miss raises a trap into the OS, which walks the page table in software and explicitly inserts the new mapping - more flexible (OS can use any page table structure) but requires very carefully-written trap handlers (e.g., the handler code itself must be TLB-resident/wired, to avoid infinite miss loops!).

TLB Context Switches - the ASID Problem

The TLB caches translations for whichever process is currently running. On a context switch, cached entries could incorrectly apply to the new process’s different address space! Solutions:

• Flush the TLB on every context switch (simple, but costly - all future accesses restart as misses).
• Address Space Identifiers (ASIDs): tag each TLB entry with the owning process’s ID so multiple processes’ entries can coexist in the TLB without flushing, and the hardware only matches entries with the current ASID.

Replacement Policy & Locality

When the TLB is full, an entry must be evicted - commonly LRU (Least Recently Used) or random. TLB performance depends heavily on a program’s locality: tight loops touching few pages → high hit rate; large-stride/random access patterns → poor hit rate (“TLB thrashing”).

3.8 Paging: Smaller Tables

Linear (single-level) page tables waste huge amounts of memory for sparse address spaces (most of the space between heap and stack is unused, yet still needs page table entries in a naive linear table).

Multi-Level Page Tables

Turn the page table itself into a tree. A page directory holds pointers to second-level page tables, which hold the actual PFNs. If an entire second-level table’s region is unused, the page-directory entry marks it invalid and no second-level table need exist at all - saving huge amounts of memory for sparse spaces.

flowchart TD
    PDBR["Page Directory\nBase Register"] --> PD["Page Directory\n(one entry per PT)"]
    PD -->|"valid"| PT1["Page Table 1"]
    PD -->|"invalid - not allocated!"| X["(no memory used)"]
    PD -->|"valid"| PT2["Page Table 2"]
    PT1 --> F1["Frame → data"]
    PT2 --> F2["Frame → data"]

$$\text{VA}=\underset{p_1}{\underbrace{\text{Page Directory Index}}}\Vert \underset{p_2}{\underbrace{\text{Page Table Index}}}\Vert \underbrace{\text{offset}}$$

Tradeoff: saves memory (sparse regions cost nothing), but a TLB miss now requires multiple sequential memory accesses (a “page table walk”) instead of one - time-space tradeoff, a very common systems theme. Real 64-bit architectures (x86-64) use 4-5 levels of page tables.

Other Approaches

• Hashed Page Tables: hash the VPN to find its entry in a fixed-size hash table (chained for collisions) - handles huge, sparse 64-bit address spaces well without deep multi-level trees.
• Inverted Page Tables: one single table for the entire system (not per-process!), with one entry per physical frame, recording which (process, VPN) currently occupies it. Saves enormous memory (size scales with physical RAM, not virtual address space × number of processes) but requires a fast associative/hashed lookup structure to search efficiently.

3.9 Beyond Physical Memory: Mechanisms (Swapping)

Physical memory is finite; the sum of all processes’ address spaces often exceeds it. Swapping lets the OS use disk as an overflow area for memory.

The Swap Space

A reserved region of disk (the swap space / swap partition / page file) where pages evicted from physical memory are written, and from which they’re read back when needed again.

The Present Bit & Page Faults

Each PTE has a present bit: if 1, the PFN field is valid and the page is in RAM. If 0, accessing that page triggers a page fault - a trap into the OS.

sequenceDiagram
    participant CPU
    participant MMU
    participant OS as OS (Page Fault Handler)
    participant Disk

    CPU->>MMU: access virtual address
    MMU->>MMU: page table lookup: present bit = 0
    MMU->>OS: PAGE FAULT (trap)
    OS->>OS: check: valid access? find free frame\n(evicting another page if necessary, §3.10)
    OS->>Disk: read the page from swap space
    Disk-->>OS: page data
    OS->>OS: update PTE: present=1, PFN=new frame
    OS->>CPU: retry the faulting instruction
    CPU->>MMU: access virtual address (again)
    MMU-->>CPU: TLB/page-table hit now - proceeds normally

• If no free frame exists, the OS must first evict some other page (write it to swap if dirty, then reuse its frame) - the eviction policy (which page to kick out) is the subject of §3.10.
• Because disk I/O is achingly slow (§0.5 latency numbers!), the OS typically switches to run a different, ready process while waiting for the page-in to complete - treating a page fault like any other blocking I/O.

"Beyond physical memory" ⇒ the illusion holds even under memory pressure

This mechanism is precisely what lets a process believe it has more memory than physically exists - the second half of the address-space illusion (§3.1) promised.

3.10 Beyond Physical Memory: Policies (Page Replacement)

When physical memory is full and a new page must be brought in, which victim page should be evicted? This is the OS analog of CPU cache replacement, and just as important.

The Optimal Policy (MIN) - an unreachable ideal

Evict the page that will be accessed furthest in the future. Provably optimal, but requires knowing the future - useful only as a theoretical baseline to measure real policies against.

FIFO

Evict the oldest-loaded page. Simple, but ignores usage patterns entirely, and suffers Belady’s Anomaly:

Belady's Anomaly

For FIFO (and some other policies), increasing the number of physical frames can sometimes increase the number of page faults - deeply counter-intuitive! This surprising result (discovered analyzing OS/360) is why stack-based algorithms (like LRU) - which guarantee monotonically non-increasing faults as frames increase - are theoretically preferred.

LRU (Least Recently Used)

Evict the page that hasn’t been used for the longest time - approximates MIN well by leveraging temporal locality (recently used ⇒ likely used again soon; the “past predicts the future” heuristic).

$$\text{LRU evicts }\arg \underset{p}{\max }(t_{now}-t_{lastaccess}(p))$$

Problem: exact LRU requires updating metadata (a timestamp, or moving to the head of a list) on every memory reference - far too expensive to do in software on every access.

Approximating LRU - the Clock Algorithm

Real systems use hardware use/reference bits (set to 1 by hardware whenever a page is accessed) and approximate LRU cheaply:

flowchart LR
    A["Clock hand points to a page"] --> B{"use bit = 1?"}
    B -->|Yes| C["Clear it to 0,\nadvance hand"]
    C --> A
    B -->|No| D["Evict this page!"]

This Clock algorithm (a.k.a. “second-chance”) sweeps through frames like a clock hand; a page with its use bit still set gets a “second chance” (bit cleared, skipped this round); a page found with use bit already 0 (i.e., not accessed since the hand last passed) is evicted.

Other Practical Considerations

• Dirty bit awareness: prefer evicting clean pages over dirty ones (a dirty page must be written back to disk before reuse - extra cost); many real algorithms are “enhanced clock” variants that factor in the dirty bit too.
• Page selection policy - when to fetch: demand paging (fetch only when actually needed, on fault) vs. prefetching (predictively fetch pages likely to be needed soon, e.g., sequential pages).
• Thrashing: when the total memory demand of active processes vastly exceeds physical memory, the system spends nearly all its time servicing page faults instead of doing useful work - throughput collapses. Solutions: admission control (don’t run more processes than memory can reasonably support) or the OS killing/suspending processes (e.g., Linux’s OOM killer).

3.11 Complete Virtual Memory Systems

Tying it all together - two illustrative real systems:

VAX/VMS (a classic, influential design)

• Simple segmented paging: address space split into regions (P0: user code/heap, P1: user stack, S: OS space).
• Small page size (512 bytes, small for its era) - traded off table size vs. internal fragmentation.
• Used a two-level page table and a software-managed TLB-like structure; included clever tricks for handling the OS’s own memory needs.

Linux Virtual Memory

• Full multi-level page tables (historically progressing from 2 → 3 → 4-5 levels on x86-64 as address space width grew).
• mmap(): generalizes memory mapping - maps files (or anonymous memory) directly into a process’s address space, unifying “loading a file’s contents” and “allocating memory” under one mechanism; the basis of shared libraries and efficient file I/O (memory-mapped files).
• Copy-on-Write (COW): when fork()ing, the child’s page table initially points at the same physical frames as the parent, marked read-only. Only when either process writes to a shared page does a page fault trigger an actual copy - a huge optimization, since most fork()s are immediately followed by exec() (which discards the copy entirely) or only touch a small fraction of memory.

sequenceDiagram
    participant P as Parent
    participant K as Kernel
    participant C as Child

    P->>K: fork()
    K->>K: create child page table,\nmap to SAME physical frames as parent,\nmark all shared pages READ-ONLY
    K-->>C: child process created (memory not actually copied yet!)
    C->>K: writes to a shared page
    K->>K: PAGE FAULT (write to read-only page)\n→ allocate new frame, copy data, update child's PTE to read-write
    K-->>C: resume - child now has its own private copy of just that page

• Transparent Huge Pages: use larger page sizes (e.g., 2MB instead of 4KB) for large contiguous allocations to reduce TLB misses and page-table overhead - a direct, practical answer to the time-space tradeoffs discussed in §3.8.
• /proc/<pid>/smaps, vmstat, top: real tools exposing exactly the concepts above (RSS, swap usage, page fault counts).

---

Part 4 - Concurrency

The core question of this Part

Once a process has multiple threads sharing the same address space, how do we coordinate them correctly and efficiently, given that the OS can interrupt execution at (almost) any instruction?

4.1 Concurrency: An Introduction

Threads vs. Processes

A thread is like a process, but multiple threads within the same process share the same address space (code, heap, global data) while each has its own program counter, registers, and stack.

flowchart TB
    subgraph Proc["One Process's Address Space"]
        Code["Code (shared)"]
        Data["Heap / Globals (shared)"]
        subgraph T1["Thread 1"]
            S1["Own Stack"]
            R1["Own Registers, PC"]
        end
        subgraph T2["Thread 2"]
            S2["Own Stack"]
            R2["Own Registers, PC"]
        end
    end

• Why threads? (1) Exploit multiple CPUs in parallel for one program (parallelism). (2) Avoid blocking the whole program on one slow operation, e.g., I/O (concurrency without process-creation overhead). (3) Cheaper to create/context-switch than full processes (no new address space needed).
• Multiple stacks live in the same address space, so - unlike the clean single-stack layout in §3.1 - each thread’s stack occupies its own smaller region (with guard pages to catch overflow), often requiring a fixed maximum stack size to be chosen up front.

The Fundamental Problem: Shared Data + Interruption = Race Conditions

Because a thread can be interrupted at any instruction (recall the timer interrupt from §2.3 - nothing about it changed just because we’re now inside a single process), two threads modifying shared data can interleave in dangerous ways.

The classic example - counter++ isn't atomic

counter++ compiles to (roughly) three machine instructions:

mov  counter, %eax   ; load counter into a register
add  $1, %eax          ; increment the register
mov  %eax, counter   ; store back to memory

If Thread A is interrupted between these instructions and Thread B runs the same three instructions, both threads’ increments can be lost - the final counter value depends on the precise interleaving (a race condition), and is therefore non-deterministic (an indeterminate program).

• Critical section: a piece of code that accesses a shared resource and must not be concurrently executed by more than one thread.
• Race condition: the outcome depends on the timing/interleaving of multiple threads.
• Mutual exclusion: the property that guarantees only one thread is ever inside a critical section at a time - this is exactly what locks (§4.3) provide.
• Atomicity: an “all-or-nothing” property - the hardware primitives underlying locks (§4.3) provide small atomic instructions; locks let programmers build arbitrarily large atomic-seeming regions out of those small primitives.

4.2 Interlude: Thread API (POSIX pthreads)

#include <pthread.h>
 
int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
                    void *(*start_routine)(void*), void *arg);
int pthread_join(pthread_t thread, void **retval);

#include <stdio.h>
#include <pthread.h>
 
void *mythread(void *arg) {
    printf("%s\n", (char *) arg);
    return NULL;
}
 
int main() {
    pthread_t p1, p2;
    pthread_create(&p1, NULL, mythread, "A");
    pthread_create(&p2, NULL, mythread, "B");
    pthread_join(p1, NULL);   // wait for p1 to finish
    pthread_join(p2, NULL);   // wait for p2 to finish
    return 0;
}

Never assume ordering

Just like fork(), the order in which p1 and p2 actually execute (and interleave) is up to the scheduler. Never write code assuming a specific interleaving unless you’ve explicitly synchronized it.

Other key parts of the API: pthread_mutex_t (locks, §4.3), pthread_cond_t (condition variables, §4.5), thread-local storage, and various attribute objects (stack size, detach state).

4.3 Locks

The Basic Idea

A lock is a variable holding state: available/unlocked or acquired/held (by some thread). Programmers wrap critical sections with lock()/unlock():

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
 
pthread_mutex_lock(&lock);
// --- critical section ---
balance = balance + 1;
// -------------------------
pthread_mutex_unlock(&lock);

lock() blocks (or spins) if the lock is already held, until it becomes free; then it atomically acquires it and proceeds. unlock() releases it, potentially waking a waiter.

Evaluating a Lock Implementation

1. Mutual exclusion: does it actually prevent >1 thread in the critical section? (Correctness - non-negotiable.)
2. Fairness: does every waiting thread eventually get the lock? Is starvation possible?
3. Performance: overhead in the no-contention case, contention on one CPU, contention across many CPUs.

Building Locks: Attempt 1 - Disabling Interrupts

void lock()   { DisableInterrupts(); }
void unlock() { EnableInterrupts();  }

Works on a single CPU (nothing can preempt the critical section if timer interrupts are off) but: (a) requires trusting any program with a highly privileged operation, (b) doesn’t work on multiprocessors (other CPUs are unaffected!), and (c) disabling interrupts for too long can cause lost/missed hardware interrupts. Used sparingly today, mostly inside the OS kernel itself for very short internal critical sections.

Building Locks: Attempt 2 - A Simple Flag (Software-Only) - Broken

// BROKEN - has a race condition!
void lock(lock_t *m) {
    while (m->flag == 1)   // spin-wait
        ; // do nothing
    m->flag = 1;           // <-- NOT ATOMIC with the check above!
}

Two threads can both pass the while check (both see flag == 0) before either sets flag = 1 - both then enter the critical section. The check-then-act sequence itself needs to be atomic, which plain loads/stores cannot provide alone.

Building Locks: Attempt 3 - Hardware Support

Real locks require a hardware-provided atomic instruction:

Test-And-Set (atomically):

int TestAndSet(int *old_ptr, int new) {
    int old = *old_ptr;   // fetch old value
    *old_ptr = new;       // set new value
    return old;           // return old value - ALL ATOMIC in hardware
}
 
void lock(lock_t *m) {
    while (TestAndSet(&m->flag, 1) == 1)
        ; // spin-wait ("spin lock")
}
void unlock(lock_t *m) { m->flag = 0; }

Compare-And-Swap (CAS):

int CompareAndSwap(int *ptr, int expected, int new) {
    int actual = *ptr;
    if (actual == expected)
        *ptr = new;
    return actual;   // ALL ATOMIC in hardware
}

More powerful than test-and-set - enables lock-free programming (retry loops that detect and redo concurrent conflicting updates), foundational for many concurrent data structures.

Load-Linked / Store-Conditional (an alternative pair, e.g., on MIPS/ARM/RISC-V): LL loads a value and “watches” the address; SC only succeeds (writes) if no other write happened to that address since the LL - otherwise it fails and the caller retries.

Fetch-And-Add: atomically increments a value, returns the old value - used to build ticket locks:

int FetchAndAdd(int *ptr) {
    int old = *ptr;
    *ptr = old + 1;
    return old;   // ATOMIC
}
 
void lock(lock_t *m) {
    int myturn = FetchAndAdd(&m->ticket);
    while (m->turn != myturn)
        ; // spin
}
void unlock(lock_t *m) { m->turn = m->turn + 1; }

Ticket locks guarantee every thread eventually gets served, in FIFO order - fixing the fairness weakness of plain test-and-set spin locks (which offer no ordering guarantee - a thread can theoretically spin forever while others repeatedly “cut in line”).

Too Much Spinning - Add OS Support

Pure spin locks waste CPU cycles when the lock holder is preempted or asleep (worst case: the OS schedules the spinning thread instead of the lock holder - comically wasteful). Solutions:

• yield(): a spinning thread voluntarily gives up the CPU instead of spinning - better than pure spinning, but still wasteful with many threads, and doesn’t prevent starvation.
• Queues + park()/unpark(), or Linux’s futex: put a waiting thread fully to sleep (off the run queue entirely) until the lock is released, at which point the OS explicitly wakes it. This needs OS support because only the OS can move a thread out of “ready” entirely.
• Two-Phase Locks: spin briefly first (cheap if the lock is released quickly), then fall back to sleeping if it’s still held after a threshold - a practical hybrid used in real mutex implementations (e.g., Linux futex-based pthread mutexes).

4.4 Lock-Based Concurrent Data Structures

Adding locks to a data structure (“just wrap every method with a single big lock”) gives a correct but coarse-grained solution - the goal beyond correctness is good performance under concurrency.

• Concurrent Counters: a single lock around increment() is correct, but scales poorly (all cores contend for one lock, cache-line ping-pong). Approximate/sloppy counters: each CPU keeps a local counter (cheap, uncontended updates) and periodically syncs to a global counter under lock - trades perfect real-time accuracy for massively better scalability.
• Concurrent Linked Lists: naive: one lock for the whole list. Better: hand-over-hand locking (lock next node before releasing current) allows more parallelism, at the cost of more lock acquisitions per operation (often not actually a net win - a classic lesson that finer-grained locking isn’t automatically faster).
• Concurrent Queues: the Michael-Scott queue uses two locks (one for the head/dequeue side, one for the tail/enqueue side) plus a dummy node, allowing enqueue and dequeue to proceed fully in parallel.
• Concurrent Hash Tables: typically one lock per bucket (rather than one global lock) - a simple technique yielding excellent scalability since operations on different buckets almost never contend.

General lesson

More locks ≠ automatically faster. Fine-grained locking adds overhead and complexity; only worth it when contention is actually a measured bottleneck. Measure before optimizing.

4.5 Condition Variables

Locks alone can’t express “wait until some condition becomes true” - busy-waiting (spinning) on a shared flag while holding no lock, or worse, while holding the lock, wastes CPU and can even deadlock.

A condition variable (CV) is an explicit queue threads can put themselves on to sleep, and be later woken when some condition might have changed.

pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
 
// Waiting thread:
pthread_mutex_lock(&lock);
while (ready == 0)                    // ALWAYS a `while`, not `if`! (see below)
    pthread_cond_wait(&cond, &lock);  // atomically: release lock + sleep;
                                       // on wake: re-acquire lock before returning
pthread_mutex_unlock(&lock);
 
// Signaling thread:
pthread_mutex_lock(&lock);
ready = 1;
pthread_cond_signal(&cond);           // wake ONE waiter (pthread_cond_broadcast wakes ALL)
pthread_mutex_unlock(&lock);

Why while, not if?

Between being woken and actually re-acquiring the lock/resuming, another thread may have run and changed the state again (Mesa semantics - signaling is only a hint, not a guarantee the condition still holds by the time the woken thread actually runs). Always re-check the condition in a loop after waking.

The Producer/Consumer (Bounded Buffer) Problem

The canonical CV example: producers add items to a fixed-size buffer, consumers remove them; producers must wait when the buffer is full, consumers must wait when it’s empty.

int buffer[MAX];
int fill_ptr = 0, use_ptr = 0, count = 0;
pthread_cond_t empty, fill;
pthread_mutex_t mutex;
 
void put(int value) { buffer[fill_ptr] = value; fill_ptr = (fill_ptr+1)%MAX; count++; }
int  get()           { int t = buffer[use_ptr];  use_ptr  = (use_ptr+1)%MAX;  count--; return t; }
 
void *producer(void *arg) {
    for (int i = 0; i < loops; i++) {
        pthread_mutex_lock(&mutex);
        while (count == MAX)                  // wait while FULL
            pthread_cond_wait(&empty, &mutex);
        put(i);
        pthread_cond_signal(&fill);            // wake a possibly-waiting consumer
        pthread_mutex_unlock(&mutex);
    }
}
void *consumer(void *arg) {
    for (int i = 0; i < loops; i++) {
        pthread_mutex_lock(&mutex);
        while (count == 0)                     // wait while EMPTY
            pthread_cond_wait(&fill, &mutex);
        int tmp = get();
        pthread_cond_signal(&empty);           // wake a possibly-waiting producer
        pthread_mutex_unlock(&mutex);
    }
}

Using two condition variables (empty, fill) instead of one avoids waking the wrong kind of thread unnecessarily - an important efficiency/correctness detail.

4.6 Semaphores

A semaphore is an integer-valued object with two atomic operations (Dijkstra’s original names in parentheses):

sem_wait(sem_t *s)  { /* (P / down) decrement s; if s < 0, block */ }
sem_post(sem_t *s)  { /* (V / up)   increment s; wake a waiter if any were blocked */ }

$$\text{Invariant: if }s<0,\text{ then }|s|\text{ = number of threads currently blocked waiting on it}$$

Semaphores are general enough to implement both locks and condition variables:

• Binary semaphore as a lock: initialize to 1; sem_wait() before critical section (acts as lock()), sem_post() after (acts as unlock()).
• Counting semaphore for ordering: initialize to 0; used to signal “this event has now happened $N$ times,” e.g., for producer/consumer or barriers.

Classic Problems Solved with Semaphores

• Producer/Consumer with semaphores: use empty (counts free slots) and full (counts filled slots) semaphores plus a binary mutex semaphore for the buffer’s mutual exclusion.
• Reader-Writer Locks: allow either many concurrent readers OR one exclusive writer, never both. Built from semaphores + a reader-count variable. Classic tension: naive implementations can starve writers if readers keep arriving.
• Dining Philosophers: $N$ philosophers around a table, each needing two forks (shared with neighbors) to eat. Naive “grab left fork, then right fork” can deadlock (everyone holds their left fork, waiting forever for their right). Fixed by breaking the symmetry - e.g., one philosopher picks up their forks in the opposite order, or using a resource-ordering / arbitrator approach (see deadlock prevention, §4.7).

Locks, CVs, and Semaphores - how they relate

• Locks ⇒ mutual exclusion only.
• Condition variables ⇒ waiting for a condition to become true, always paired with a lock.
• Semaphores ⇒ a single, more general primitive that can express both of the above (and more, e.g., counting resources), at the cost of being slightly less intuitive to reason about for beginners - many textbooks (including OSTEP) teach locks/CVs first as building blocks, since it’s easier to build semaphores from them (or vice versa) once both are understood.

4.7 Common Concurrency Bugs

Empirical bug studies (e.g., of MySQL, Apache, Mozilla) find most concurrency bugs fall into just a couple of categories:

Non-Deadlock Bugs

• Atomicity-violation bugs: a code region assumed to be atomic (executed without interruption) isn’t actually protected by a lock, allowing a harmful interleaving.

  // Thread 1                  // Thread 2
  if (thd->proc_info) {        thd->proc_info = NULL;
      fputs(thd->proc_info);   // ← may now be NULL! (crash)
  }

• Order-violation bugs: code assumes event A happens before event B, but no explicit enforcement (e.g., CV) guarantees that ordering, and the scheduler can violate it.

  // Thread 1: creates thread 2 assuming it will initialize `mThread` first
  void mMain() { mThread = PR_CreateThread(mFunc, ...); }
  // Thread 2: crashes if it runs before mThread is even assigned!
  void mFunc() { mState = mThread->State; }

  Fix: a condition variable (or semaphore) explicitly enforcing “wait until initialized.”

Deadlock Bugs

Deadlock

A situation where a set of threads are each waiting for a resource held by another thread in the set - a cycle of waiting - such that none can ever proceed.

The Four Necessary Conditions for Deadlock (Coffman conditions - all four must hold simultaneously):

1. Mutual exclusion: resources can’t be shared (must be held exclusively).
2. Hold-and-wait: a thread holds one resource while waiting for another.
3. No preemption: resources can’t be forcibly taken away - must be voluntarily released.
4. Circular wait: a cycle of threads, each waiting on a resource held by the next.

flowchart LR
    T1["Thread 1\n(holds Lock A)"] -->|"wants"| LB["Lock B"]
    T2["Thread 2\n(holds Lock B)"] -->|"wants"| LA["Lock A"]
    LB -.held by.-> T2
    LA -.held by.-> T1

Classic example: two threads acquiring the same two locks in opposite order.

// Thread 1:              // Thread 2:
lock(&L1);                lock(&L2);
lock(&L2);   // ← DEADLOCK if T2 got here first

Preventing / Avoiding / Detecting Deadlock

Breaking any one of the four Coffman conditions prevents deadlock:

Strategy	Breaks Condition	Notes
Total lock ordering	Circular wait	All code acquires multiple locks in the same global order (e.g., always by memory address) - simple and widely used, but requires whole-codebase discipline
Partial ordering	Circular wait	Order only where locks are actually acquired together
Acquire all locks at once (atomically)	Hold-and-wait	Use a “guard” master lock around acquiring the full set - reduces concurrency
trylock() + backoff	Hold-and-wait / No preemption	If a second lock can’t be acquired immediately, release everything held and retry (with randomized backoff to avoid livelock) - this is effectively how database transaction managers implement deadlock avoidance
Deadlock detection + recovery	(accept it can happen)	Periodically build a “waits-for” graph, detect cycles, and kill/rollback a thread to break the cycle (used by DBMSs)
Avoidance via scheduling (Banker’s Algorithm)	-	Only grant a resource request if the resulting state is still “safe” (some ordering exists where all threads can finish) - requires advance knowledge of maximum resource needs, rarely practical outside specialized/embedded systems

4.8 Event-Based Concurrency (Advanced)

An alternative to thread-based concurrency: a single-threaded event loop that waits for any of several events (using select()/poll()/epoll() on UNIX) and dispatches a handler for whichever is ready - avoiding locks entirely (since there’s only one thread!), at the cost of manually-managed program state (“callback hell” / manual state machines) and requiring all blocking calls to be replaced with non-blocking, asynchronous equivalents.

while (1) {
    int n = epoll_wait(epfd, events, MAX_EVENTS, -1);  // block until SOMETHING is ready
    for (int i = 0; i < n; i++) {
        handle_event(events[i]);   // dispatch - must not block!
    }
}

• select()/poll(): check readiness across a set of file descriptors - poll() scales a bit better than select()’s fixed-size bitmask, but both are $O(n)$ per call.
• epoll() (Linux, also kqueue on BSD/macOS): the kernel maintains persistent interest lists, so checking “what’s ready” is efficient even with thousands of file descriptors - $O(1)$-ish amortized, essential for high-concurrency servers (e.g., nginx, Node.js’s libuv, Redis).
• The blocking-call problem: a single blocked system call (e.g., blocking disk I/O) stalls the entire event loop, since there’s no other thread to pick up the slack - mitigated with asynchronous I/O (io_uring on modern Linux, or offloading to a small helper thread pool just for blocking operations).

Event-based vs. thread-based - a real, ongoing design choice

• Node.js: single-threaded event loop (JS callbacks / async/await), with a hidden thread pool for blocking OS calls (libuv).
• nginx: event-driven worker processes - extremely high concurrency per worker with minimal memory overhead (no per-connection thread/stack).
• Java/most app servers: thread-per-connection, relying on OS-level thread scheduling - simpler mental model, higher per-connection memory cost.
• Go: “goroutines” - extremely lightweight, OS-multiplexed user-level threads (an M:N threading model) that get most of the simplicity of thread-based code with much of the efficiency of event-based systems.

---

Part 5 - Persistence (Storage & File Systems)

The core question of this Part

How does the OS store data durably - surviving process exit, and even crashes/power loss - on slow, block-based devices, while giving programs a friendly read()/write()/file-hierarchy interface?

5.1 I/O Devices

The Canonical Device

Every device has: (1) a hardware interface (registers the OS can read/write: status, command, data), and (2) an internal structure (firmware, chips, mechanical parts - hidden behind the interface).

flowchart LR
    OS["OS Device Driver"] -->|"write to Command register"| DEV["Device Registers\n(Status / Command / Data)"]
    DEV --> Internal["Internal Device Logic\n(firmware, controller,\nmechanical/flash internals)"]

Interacting With Devices: Polling vs. Interrupts

• Polling: the CPU repeatedly checks (in a loop) the device’s status register to see if it’s ready - simple, but wastes CPU cycles if the device is slow (e.g., disk).
• Interrupts: the CPU issues a request then goes on to do other useful work (e.g., run another process); the device raises a hardware interrupt when it’s done, and the CPU’s interrupt handler is invoked to finish the operation - much better CPU utilization for slow devices.

Hybrid approach

For devices that are fast (respond in the time it’d take just to take the interrupt overhead), pure polling can actually be faster. Real systems often use a hybrid: poll briefly first, then fall back to interrupts if the device isn’t immediately ready - the same “spin-then-sleep” idea as two-phase locks (§4.3)!

DMA (Direct Memory Access)

Without DMA, the CPU itself must copy every byte between a device and memory (Programmed I/O), wasting CPU cycles on pure data movement. A DMA controller is a separate piece of hardware the CPU can command to perform a bulk memory-to-device (or device-to-memory) transfer independently; the CPU is only interrupted once, at completion - freeing it to do other work during the transfer.

The Device Driver - Abstracting Hardware Differences

The OS’s file system, block layer, etc. are written generically against an abstract interface (e.g., “generic block device”); a specific device driver translates those generic requests into the exact register-level protocol for a specific piece of hardware. This is why Linux (or any OS) can support thousands of different disk/network/GPU models: nearly all OS code is hardware-agnostic, with drivers as the only hardware-specific layer.

5.2 Hard Disk Drives (HDDs)

Geometry

An HDD stores data on one or more spinning platters, each with concentric tracks, divided into sectors (traditionally 512 bytes, now often 4KB - “Advanced Format”). A disk head (one per surface, all mounted on a single disk arm) reads/writes data.

flowchart TB
    subgraph Platter["Platter (top view)"]
        direction TB
        T0(("Track 0 (outer)"))
        T1(("Track 1"))
        T2(("Track N (inner)"))
    end

Where Does the Time Go? - the Three Components of I/O Time

$$T_{I/O}=T_{seek}+T_{rotation}+T_{transfer}$$

• Seek time: moving the disk arm to the correct track - involves acceleration, coasting, deceleration, settling; dominates cost for random access.
• Rotational latency: waiting for the desired sector to rotate under the head - on average, half a rotation.
• Transfer time: actually reading/writing the data once positioned - comparatively fast.

$$\text{Avg rotational latency}=\frac{1}{2}\times \frac{60}{\text{RPM}}\text{ seconds}$$

Why "sequential" beats "random" so dramatically on HDDs

Sequential access pays seek+rotational cost once, then streams data. Random access pays that overhead per request - this single fact motivates enormous amounts of file-system design (§5.6-5.8), aiming to keep related data physically close together on disk.

Disk Scheduling

Since seek time dominates, the OS’s I/O scheduler can dramatically improve throughput by reordering pending requests:

Algorithm	Idea	Weakness
FIFO	Service requests in arrival order	Ignores locality - lots of wasted seeking
SSTF (Shortest Seek Time First)	Always service the request closest to the current head position	Can starve requests far from the “hot” area
SCAN / “Elevator”	Sweep the head in one direction servicing all requests along the way, then reverse	Middle tracks serviced more often than edges
C-SCAN (Circular SCAN)	Sweep in one direction only; jump back to start without servicing on the return	More uniform wait-time distribution than SCAN

5.3 RAIDs (Redundant Array of Independent Disks)

RAID combines multiple physical disks into one logical unit for better performance, capacity, and/or reliability - completely transparent to the software above it.

Evaluating RAID: 3 Axes

1. Capacity: usable space vs. raw total space across all disks.
2. Reliability: how many disk failures can be tolerated without data loss.
3. Performance: sequential/random read/write throughput.

RAID Levels

flowchart TB
    subgraph R0["RAID 0 - Striping"]
        A0[Disk 0: A,C,E] 
        A1[Disk 1: B,D,F]
    end
    subgraph R1["RAID 1 - Mirroring"]
        B0[Disk 0: A,B,C]
        B1[Disk 1: A,B,C copy]
    end
    subgraph R4["RAID 4 - Dedicated Parity"]
        C0[Disk 0: A]
        C1[Disk 1: B]
        C2[Disk 2: Parity A⊕B]
    end
    subgraph R5["RAID 5 - Rotating Parity"]
        D0[Disk 0: A, Parity]
        D1[Disk 1: Parity, C]
        D2[Disk 2: B, D]
    end

Level	Idea	Capacity (N disks)	Fault Tolerance	Notes
RAID 0	Striping - spread blocks across disks, no redundancy	100% ($N\times$ disk)	None - any failure loses all data	Best performance, zero reliability
RAID 1	Mirroring - every block duplicated on 2 disks	50%	Survives 1 failure per mirror pair	Simple, fast reads, 2x write cost
RAID 4	Striping + one dedicated parity disk	$(N-1)/N$	Survives 1 disk failure	Parity disk is a write bottleneck (every write touches it)
RAID 5	Striping + parity rotated across all disks	$(N-1)/N$	Survives 1 disk failure	Fixes RAID 4’s parity-disk bottleneck
RAID 6	Like RAID 5, but two independent parity blocks	$(N-2)/N$	Survives 2 disk failures	Used when rebuild time on huge disks makes a 2nd failure during rebuild a real risk

Parity - How It Provides Redundancy

Parity uses XOR: given data blocks $D_0,D_1,\dots ,D_{n-1}$, parity is

$$P=D_0\oplus D_1\oplus \cdots \oplus D_{n-1}$$

If any single block (including $P$ itself) is lost, it can be reconstructed by XOR-ing all the remaining blocks - one extra disk’s worth of space protects against any single-disk failure, regardless of array width (much more space-efficient than mirroring at scale).

The Small-Write Problem (RAID 4/5)

Updating a single data block requires recomputing parity, which naively means reading all other blocks in the stripe. The optimization: read only the old value of the block and the old parity, then:

$$P_{new}=(D_{old}\oplus D_{new})\oplus P_{old}$$

• just 4 I/Os (read old data, read old parity, write new data, write new parity) instead of reading every disk in the stripe.

5.4 Files and Directories

The File & Inode Abstraction

A file is a linear array of bytes, with a low-level name (inode number) that user-friendly path names ultimately map to. The OS tracks file metadata in an inode (“index node”): size, permissions, owner, timestamps, and - critically - pointers to the data blocks on disk holding the file’s actual contents.

int fd = open("file.txt", O_RDONLY);   // returns a small integer: file descriptor
read(fd, buffer, size);
write(fd, buffer, size);
lseek(fd, offset, SEEK_SET);            // reposition the file's read/write pointer
close(fd);

• File descriptor: a small per-process integer index into the process’s open file table, which itself points into a system-wide open file table entry (tracking the current offset, reference count, etc.) - this indirection is why dup(), shared offsets after fork(), and redirection (§2.2) all work cleanly.
• Every process starts with fds 0 (stdin), 1 (stdout), 2 (stderr) already open.

Directories

A directory is just a special kind of file whose contents are a list of (name → inode number) mappings. Directories nest, forming the familiar tree-structured hierarchy (with the single root / on UNIX).

Links

• Hard link: link(old, new) creates a new name pointing at the same inode - both names are now equally “real”; the inode’s data isn’t deleted until its reference count reaches zero (all names removed via unlink()). Hard links cannot cross filesystems and (typically) cannot point at directories (to avoid cycles).
• Symbolic (soft) link: symlink(target, linkname) creates a tiny special file whose content is simply the path string of the target. Can cross filesystems and point to directories, but becomes a dangling link if the target is removed (unlike a hard link, which keeps the underlying data alive).

flowchart LR
    subgraph HardLink["Hard Link"]
        N1["/docs/report.txt"] --> I["inode #42 (data)"]
        N2["/backup/report_copy.txt"] --> I
    end
    subgraph SoftLink["Symbolic Link"]
        N3["/docs/report.txt"] --> I2["inode #42 (data)"]
        N4["/desktop/shortcut"] -->|"contains path string"| N3
    end

Permissions

UNIX-style permissions: three bits (read, write, execute) each for owner, group, and other, commonly shown as rwxr-xr-- or the numeric 754. Additional bits: setuid/setgid (run with the file owner’s/group’s privileges - security-relevant, see Access Control) and the sticky bit (e.g., on /tmp: only the file’s owner can delete it, even if the directory is world-writable).

5.5 File System Implementation (a simple example: VSFS)

On-Disk Structures

A simple file system divides the disk into fixed-size blocks and organizes:

flowchart LR
    SB["Superblock\n(FS metadata: block size,\ntotal blocks/inodes, magic #)"]
    IB["Inode Bitmap\n(free/used inodes)"]
    DB["Data Bitmap\n(free/used data blocks)"]
    IT["Inode Table\n(all inode structures)"]
    DR["Data Region\n(actual file/directory contents)"]
    SB --- IB --- DB --- IT --- DR

• Superblock: global metadata about the file system itself, read first on mount.
• Bitmaps: one bit per inode/block indicating free vs. in-use - simple, fast allocation tracking.
• Inode table: fixed-size array of inodes, each holding metadata + pointers to data blocks.
• Data region: the bulk of the disk, holding actual file and directory contents.

Inode Pointer Structures - Handling Files of Any Size

An inode has limited space, but files can be huge. Classic solution: multi-level index (like multi-level page tables, §3.8!):

• A handful of direct pointers (point straight at data blocks) - efficient for small files.
• One or more indirect pointers (point at a block that itself is full of more pointers to data blocks).
• Double/triple indirect pointers for very large files (a pointer to a block of pointers to blocks of pointers…).

$$\text{Max file size}\approx N_{direct}\cdot B+\frac{B}{p}\cdot B+{\left(\frac{B}{p}\right)}^2\cdot B+\dots$$

where $B$ = block size, $p$ = pointer size - this exact “extensible array via indirection” trick recurs throughout systems design.

Reading & Writing a File - Step by Step

sequenceDiagram
    participant App
    participant FS as File System
    participant Disk

    App->>FS: open("/foo/bar.txt")
    FS->>Disk: read root inode
    FS->>Disk: read root directory data → find "foo" → inode #
    FS->>Disk: read "foo" inode
    FS->>Disk: read "foo" directory data → find "bar.txt" → inode #
    FS->>Disk: read bar.txt's inode
    FS-->>App: return file descriptor (inode now cached in memory)
    App->>FS: read(fd, buf, size)
    FS->>Disk: read data block(s) pointed to by inode
    FS-->>App: data

Traversal cost

Opening a deeply-nested path requires reading an inode + directory data block for every path component - this is exactly why the OS maintains an in-memory directory cache (a.k.a. dentry cache on Linux) to avoid re-walking the disk on every single open().

5.6 Locality and the Fast File System (FFS)

The very first UNIX file system (“old UNIX FS”) performed poorly because it laid out data with no attention to locality - inodes clustered together at the start of the disk, far from their data blocks scattered elsewhere, causing lots of long seeks (§5.2) even for logically sequential access.

FFS’s key idea: Cylinder Groups (or Block Groups in ext-family filesystems) - divide the disk into regions, each with its own inodes, bitmaps, and data blocks, and try hard to keep related things physically close together:

• Keep a file’s data blocks in the same group as its inode.
• Keep all files in the same directory in the same group (typical use: files in a directory are often accessed together).
• Place large files’ data spread across multiple groups only once they exceed a threshold (to avoid one huge file monopolizing a group and starving other files’ locality).

flowchart LR
    G0["Cylinder Group 0\ninodes | bitmaps | data"] 
    G1["Cylinder Group 1\ninodes | bitmaps | data"]
    G2["Cylinder Group 2\ninodes | bitmaps | data"]
    G0 --- G1 --- G2

FFS also introduced practical UNIX features still used today: symbolic links, atomic rename() (crucial for crash-safe file replacement - see journaling next), and a reserved free-space margin (avoiding severe fragmentation as a disk nears 100% full).

5.7 Crash Consistency: FSCK and Journaling

The Problem

A single logical file-system update (e.g., “append a block to a file”) actually requires multiple separate disk writes (update the inode, update a bitmap, write the data block itself). If a crash (power loss, kernel panic) happens between these writes, the on-disk structures can be left in an inconsistent state.

A concrete inconsistency

Suppose appending a block requires writing (1) the new data, (2) the updated inode (with a new pointer), (3) the updated data bitmap. If only (1) and (3) complete before a crash, the bitmap now claims a block is in use, but no inode actually points to it - a space leak. Worse orderings can cause an inode to point at garbage data (whatever was previously in that block, from another file!) - a serious security and correctness problem.

fsck (File System Checker) - the Old Approach

After a crash, fsck scans the entire disk, cross-checking all metadata (inodes, bitmaps, directories) for consistency and repairing detected problems - a purely reactive, after-the-fact scan.

fsck's fatal flaw at scale

Scanning an entire multi-terabyte disk can take hours - completely impractical for modern disk sizes. This motivated journaling.

Journaling (Write-Ahead Logging) - the Modern Approach

Before making changes to the actual file-system structures in place, first write a description of the intended changes to a dedicated journal (log) region. If a crash happens, on reboot the OS just replays (or discards) journal entries - a fast, localized recovery, independent of total disk size.

sequenceDiagram
    participant App
    participant FS as File System
    participant Journal
    participant Disk as Main Disk Structures

    App->>FS: write/append operation
    FS->>Journal: write TxBegin + all pending updates (metadata + optionally data)
    FS->>Journal: write TxEnd (commit marker)
    Note over Journal: Transaction is now durably logged
    FS->>Disk: checkpoint - write the actual updates to their real locations
    FS->>Journal: mark transaction as "free" (can be reclaimed)

• Metadata journaling: only file-system metadata (inodes, bitmaps, directory entries) is journaled - data blocks are written directly. Faster, but a crash can still leave data (not metadata) in an inconsistent state (the classic “garbage data” problem can still occur in some orderings).
• Full data journaling: both metadata and data are journaled - strongest consistency guarantee, but roughly doubles write traffic (every byte is written twice: once to journal, once to final location).
• Ordered journaling (a common practical compromise, e.g., ext3/ext4 default): data is written to its final location before the metadata’s journal transaction commits - guarantees an inode never points at garbage, without the full 2x write cost of full data journaling.
• Recovery after a crash: replay any committed transactions found in the journal (those with both TxBegin and TxEnd) - this is called redo logging. Incomplete transactions (no TxEnd found) are simply discarded - the pre-crash state persists as if that transaction never started.

5.8 Log-Structured File Systems (LFS)

A more radical idea: never overwrite data in place - instead, buffer all updates (data and metadata) in memory, and when enough have accumulated, write them all sequentially to a free region of disk as one large batch (a segment), converting the disk workload into (mostly) fast sequential I/O even for random small writes - a huge win given HDD’s seek-dominated cost model (§5.2).

The Inode Map Problem

If inodes themselves move on every update (they’re just written wherever the log’s current tail is), how do you find an inode given its number? LFS adds an indirection: the inode map (imap), itself periodically written to the log, with its current location tracked via a fixed checkpoint region at a known disk address.

flowchart LR
    CR["Checkpoint Region\n(fixed location)"] --> IMAP["Inode Map\n(inode# → current disk location)"]
    IMAP --> INODE["Inode\n(current data block pointers)"]
    INODE --> DATA["Data blocks"]

Garbage Collection - the Cost of Never Overwriting

Since old versions of data are never overwritten in place, disk space fills with dead (stale, superseded) blocks. LFS must periodically run a cleaner: read a set of (mostly-dead) segments, copy out any still-live blocks, and rewrite them compactly, freeing the rest of the segment(s) for reuse. This garbage-collection cost is LFS’s central tradeoff - fast writes, but overhead later, conceptually very similar to garbage collection in managed programming languages, and to the wear-leveling/garbage collection SSDs must do internally (§5.9)!

5.9 Flash-Based SSDs

How Flash Differs from Disks

SSDs have no moving parts - data is stored in NAND flash cells, organized into pages (read/write unit, e.g., 4-16KB) grouped into blocks (erase unit, e.g., 128-256 pages).

The fundamental flash constraint

• Pages can be read or written individually.
• A page cannot be overwritten directly - it must first be erased, and erasure only works at the coarser block granularity (erasing wipes an entire block of many pages at once).
• Flash cells wear out: each block tolerates a limited number of erase cycles (thousands to tens of thousands, depending on flash type) before becoming unreliable.

The Flash Translation Layer (FTL)

Because of the above, SSDs never do simple in-place overwrites internally. An internal firmware layer, the FTL, presents a normal block-device interface (read(LBA), write(LBA)) to the OS, while internally:

• Remapping writes: a write to logical address $L$ is redirected to a fresh, already-erased physical page - a log-structured approach internally, directly analogous to LFS (§5.8)!
• Garbage collection: periodically reclaims blocks full of stale (overwritten) pages, just like LFS’s cleaner.
• Wear leveling: spreads erase cycles evenly across all physical blocks, so no single block wears out (and fails) far before the rest of the drive.

TRIM/discard - Letting the SSD Know About Deletes

Because the FTL doesn’t know which logical blocks the file system has actually freed (from the SSD’s point of view, old data still “looks” live until overwritten), the OS issues a TRIM command whenever it deletes/frees a block - telling the SSD “this data is now garbage, you may erase it during your next GC pass,” dramatically improving GC efficiency and drive lifespan.

Practical implications

• SSD random I/O is far faster than HDD (no seek/rotation) but write amplification (one logical write can trigger multiple physical page writes/erases due to GC) is a real, measurable cost.
• File systems designed with flash in mind (e.g., F2FS) lean directly into the log-structured approach rather than fighting it.

5.10 Data Integrity and Protection

Even with journaling, disks/SSDs can suffer silent data corruption - bits flipping due to hardware faults, firmware bugs, or “misdirected writes” (data written to the wrong physical location) - without the drive itself ever reporting an I/O error!

Checksums

A checksum is a small value computed from a data block’s contents (e.g., via Fletcher checksum, CRC, or cryptographic hashes for stronger guarantees), stored alongside it. On every read, the file system recomputes the checksum and compares - a mismatch reveals corruption, even though the drive reported a “successful” read.

$$\text{checksum}=h(\text{block contents})\text{stored separately from the data itself}$$

Where NOT to store a checksum

Storing a block’s checksum adjacent to the data it protects is dangerous - a single misdirected write could corrupt (or simply fail to update) both together, defeating the check. Robust designs store checksums separately (e.g., in the inode/metadata, or a dedicated checksum tree, as ZFS does).

Beyond Detection: Correction

Detecting corruption is only half the battle - redundancy (mirroring, RAID parity, or replicated checksummed copies of critical metadata) is what allows automatic repair once corruption is found, rather than just an error report.

Real-World Systems

• ZFS: end-to-end checksums for all data and metadata, arranged in a Merkle-tree-like structure (a block’s checksum is stored in its parent block, so verifying the root effectively verifies the whole tree); combines checksumming with its own RAID-like redundancy (RAID-Z) for automatic self-healing.
• ext4: adds checksums for its journal and some metadata structures (metadata_checksum feature), though less comprehensively than ZFS/Btrfs.
• Btrfs: similarly checksums data and metadata, with copy-on-write and built-in RAID-like redundancy options.

---

Part 6 - Distributed Systems

The core question of this Part

How do we extend OS concepts - communication, sharing, consistency - across multiple, independent machines connected only by an unreliable network?

6.1 Distributed Systems: An Introduction

Why Distribute?

Scale beyond one machine’s CPU/memory/disk limits, tolerate the failure of individual machines, and place data/computation close to users geographically.

The Core New Problem: Unreliable Communication

Unlike function calls or even disk I/O, a network message can be lost, delayed, duplicated, reordered, or corrupted - and crucially, the sender often cannot tell which of these happened when a reply doesn’t arrive.

flowchart LR
    A["Client sends request"] -->|"???"| N{"Network"}
    N -->|"Delivered OK"| B1["Server processes & replies"]
    N -->|"Lost"| B2["Request never arrives"]
    N -->|"Reply lost"| B3["Server processed it,\nbut client never finds out!"]

The fundamental ambiguity

If a client sends a request and gets no reply, it cannot distinguish between: (a) the request was lost, (b) the request arrived and was processed but the reply was lost, or (c) the server is just slow. This ambiguity is the root of most distributed-systems complexity (retries, idempotency, timeouts).

Reliable Communication on Top of Unreliable Networks: UDP → TCP

• UDP (User Datagram Protocol): minimal, unreliable, connectionless - send a packet (“datagram”) and hope; no guarantee of delivery, ordering, or duplicate-suppression. Very low overhead, useful when the application handles reliability itself (or doesn’t need it, e.g., some real-time media).
• TCP (Transmission Control Protocol): builds a reliable, ordered, connection-oriented byte stream on top of unreliable IP packets, using:
  • Sequence numbers: detect loss and reordering.
  • Acknowledgments (ACKs): the receiver confirms receipt.
  • Retransmission (timeouts): the sender resends unacknowledged data.
  • Checksums: detect corruption.
  • Flow control / congestion control: avoid overwhelming the receiver or the network.

sequenceDiagram
    participant C as Client
    participant S as Server
    C->>S: SYN (start connection)
    S->>C: SYN-ACK
    C->>S: ACK (handshake complete)
    C->>S: DATA (seq=1)
    S->>C: ACK (seq=1 received)
    Note over C,S: if ACK doesn't arrive in time,\nclient retransmits
    C->>S: FIN (close)
    S->>C: ACK

RPC (Remote Procedure Call)

RPC aims to make a network call look like a normal local function call - marshal (serialize) arguments, send over the network, unmarshal on the server, execute, marshal the result, send back.

RPC is a leaky abstraction

Network calls can fail in ways local calls never do (partial failure, timeouts, unreachable hosts) - pretending otherwise (fully hiding this from the programmer) has historically caused subtle bugs. Modern RPC frameworks (gRPC, Thrift) expose explicit timeouts/retries/error codes rather than fully hiding network reality.

6.2 Network File System (NFS)

NFS lets a client machine mount and access a file system that physically resides on a remote server, as if it were local.

Design Goal: Statelessness (Classic NFS, v2/v3)

Unlike a local file system’s open() (which creates in-memory state - the open file table entry, §5.4), classic NFS servers are (mostly) stateless: every request from the client (e.g., READ, WRITE) is self-contained, carrying a file handle identifying exactly which file and which byte range - the server doesn’t need to remember anything about “sessions” between requests.

flowchart LR
    Client["NFS Client\n(caches data, tracks 'open' state)"] -->|"self-contained RPC:\nfile handle + offset + length"| Server["NFS Server\n(mostly stateless)"]
    Server -->|"data or ack"| Client

Why statelessness matters: crash recovery

If a stateless server crashes and reboots, the client simply retries its last request - no lost session state to reconstruct! This dramatically simplifies failure recovery compared to a stateful server, at the cost of some semantic awkwardness (e.g., classic NFS’s weaker exclusive-open guarantees).

Idempotency

For “just retry on no-response” to be safe, operations should ideally be idempotent (performing them multiple times has the same effect as once). WRITE(offset, data) is naturally idempotent; but naive APPEND semantics are not - NFS’s design of explicit-offset writes (rather than “append to end”) is specifically chosen to preserve idempotency under retry.

Caching & Consistency Trade-offs

Clients cache file data/attributes locally for performance, but this risks staleness if another client modifies the file. Classic NFS uses simple, loose consistency: periodic re-validation against the server (checking modification timestamps), not the strict consistency a single local file system would provide - a deliberate performance/simplicity tradeoff, not a bug.

6.3 The Andrew File System (AFS)

AFS was designed for a very different goal than NFS: scalability to thousands of clients per server, prioritizing minimizing client-server traffic.

Whole-File Caching

Unlike NFS’s block-level access, AFS clients, on open(), fetch and cache the entire file locally, and all reads/writes happen against the local cached copy; only on close() is a modified file written back to the server - this is called session semantics (close()-to-open() consistency, rather than NFS’s near-immediate consistency).

Callbacks - Replacing Polling with Server-Pushed Invalidation

Rather than clients repeatedly polling the server “has this file changed?” (wasteful at scale - NFS’s approach), the AFS server issues a callback promise: “I’ll notify you if this file changes.” When another client updates the file, the server actively pushes an invalidation to all clients holding a callback for it.

sequenceDiagram
    participant C1 as Client 1
    participant S as AFS Server
    participant C2 as Client 2

    C1->>S: open("shared.txt")
    S-->>C1: file contents + CALLBACK PROMISE
    C1->>C1: cache file locally, read/write locally
    C2->>S: open("shared.txt"), then modifies + close() (writes back)
    S->>C1: CALLBACK BREAK (invalidation!) - "shared.txt has changed"
    C1->>C1: invalidate local cache
    Note over C1: next open() will re-fetch fresh copy from server

This dramatically reduces server load (no constant polling traffic) - a key reason AFS scaled far better per-server than early NFS, and a pattern (push invalidation vs. pull/poll validation) that reappears throughout distributed caching (CDNs, distributed databases, pub/sub systems) to this day.

NFS vs. AFS - Design Philosophy Comparison

	NFS	AFS
Consistency	Near-immediate (frequent re-validation)	Session semantics (open-to-close)
Server state	(Mostly) stateless	Stateful (tracks callbacks per client)
Caching granularity	Block-level	Whole-file
Update visibility	Polling (timestamp checks)	Push (callback invalidation)
Scalability	Good for LAN, moderate client counts	Designed explicitly for large-scale, WAN-friendly deployments

6.4 Beyond OSTEP: Core Distributed Systems Concepts

Extra material

These concepts extend past the OSTEP chapters but are essential for a complete modern understanding of distributed systems, which OS courses increasingly touch on.

The CAP Theorem

In the presence of a network Partition, a distributed system must choose between:

• Consistency: every read receives the most recent write (or an error).
• Availability: every request receives a (non-error) response, without guaranteeing it’s the most recent write.

$$\text{You can have at most 2 of {Consistency, Availability, Partition tolerance} - but partitions }\text{will}\text{ happen, so really it’s C vs. A under partition.}$$

Consistency Models (from strongest to weakest, roughly)

Model	Guarantee
Linearizability / Strong consistency	Every operation appears to happen instantaneously at some point between its start and end - strongest, most intuitive, most expensive
Sequential consistency	All operations appear in some total order consistent with each process’s own program order (but not necessarily real-time order)
Causal consistency	Causally-related operations are seen in the same order by everyone; unrelated (“concurrent”) operations may be seen in different orders
Eventual consistency	If no new updates occur, all replicas eventually converge to the same value - weakest, but most available/scalable

Consensus - Getting Distributed Nodes to Agree

Distributed systems often need multiple nodes to agree on a single value (e.g., “who is the leader,” “what is committed transaction #501”) despite node failures and network issues. Paxos (classic, notoriously hard to understand) and Raft (designed explicitly for understandability) are the two most famous consensus algorithms, underpinning systems like etcd, ZooKeeper, and CockroachDB.

• Leader election: nodes vote to elect a coordinator, who sequences operations.
• Log replication: the leader replicates an ordered log of operations to followers; an operation is considered committed once a majority (quorum) of nodes have durably stored it - tolerating up to $\lfloor (n-1)/2\rfloor$ node failures out of $n$.

Two-Phase Commit (2PC)

For distributed transactions spanning multiple nodes (e.g., a bank transfer touching two separate database shards), 2PC coordinates an all-or-nothing commit:

sequenceDiagram
    participant Coord as Coordinator
    participant P1 as Participant 1
    participant P2 as Participant 2

    Coord->>P1: PREPARE
    Coord->>P2: PREPARE
    P1-->>Coord: VOTE YES (ready, locked)
    P2-->>Coord: VOTE YES (ready, locked)
    Note over Coord: all voted YES → decide COMMIT
    Coord->>P1: COMMIT
    Coord->>P2: COMMIT

If any participant votes NO (or times out), the coordinator sends ABORT to all instead. Weakness: if the coordinator crashes after participants vote YES but before sending the final decision, participants can be blocked, holding locks indefinitely - motivating more advanced protocols (3PC, Paxos Commit) in critical systems.

---

Part 7 - Security

The core question of this Part

Given that an OS multiplexes shared hardware among mutually-untrusting users and programs, how does it enforce that isolation even against active, malicious attackers - not just accidental bugs?

7.1 Introduction to Operating System Security

The Threat Model

Security design always starts by asking: who is the attacker, what do they control, and what are we protecting? Common OS threat models include: a malicious local user trying to escalate privileges, a compromised process trying to break out of its sandbox, or a remote attacker exploiting a network-facing service.

Core Security Principles

• Principle of Least Privilege: every piece of code/user should have the minimum access necessary to do its job - nothing more. Limits the “blast radius” of any single compromise.
• Defense in Depth: layer multiple independent security mechanisms, so a failure in one doesn’t mean total compromise (e.g., memory-safe language + ASLR + sandboxing + access control, all at once).
• Fail-safe defaults: default to denying access; require explicit grants (not the reverse - defaulting to “allow” and trying to block bad things is much harder to get right).
• Complete mediation: every access to every resource must be checked - no exceptions, no cached “it was fine last time” shortcuts that could go stale.
• Economy of mechanism: keep security-critical code as small and simple as possible - smaller code is easier to audit and has fewer bugs (this is a major argument in favor of microkernels’ small trusted computing base, §1.5).
• Open design: security shouldn’t rely on the attacker not knowing how the system works (“security through obscurity” is not real security) - assume the attacker has full knowledge of the algorithm/design; secrecy should live only in keys, not designs (see Kerckhoffs’s Principle, §7.4).

The Trusted Computing Base (TCB)

The TCB is the set of all hardware + software components that must function correctly for the system’s security guarantees to hold - e.g., the kernel, the bootloader, certain firmware. The smaller the TCB, the smaller the attack surface and the easier it is to gain confidence in the system’s correctness (again favoring microkernel-style minimalism where feasible).

Classic Attack Categories

Attack	Idea
Buffer overflow	Writing past the end of an allocated buffer, overwriting adjacent memory - classically, overwriting a stack return address to hijack control flow
Privilege escalation	Exploiting a bug (often in a setuid program, §5.4) to gain higher privileges than intended
Race conditions (TOCTOU)	“Time-of-check to time-of-use” - a resource’s state changes between a permission check and the actual use, exploited to bypass the check
Injection attacks	Untrusted input is interpreted as code/commands (SQL injection, command injection) rather than pure data
Malware	Viruses (attach to & spread via other programs), worms (self-propagate over networks autonomously), trojans (disguise malicious code as legitimate software), ransomware (encrypt victim data for extortion)

7.2 Authentication

Authentication answers: “who are you?” - as opposed to authorization/access control (§7.3), which answers “what are you allowed to do?”

Password-Based Authentication

Storing passwords in plaintext is catastrophic if the password database ever leaks. The standard defense:

$$\text{stored\_value}=h(\text{password}\Vert \text{salt})$$

• Hashing: use a one-way cryptographic hash function (§7.4) - even with the stored hash, an attacker (in theory) can’t easily reverse it to recover the original password.
• Salting: a random, unique value (salt) is combined with the password before hashing, and stored alongside the hash. This defeats precomputed rainbow tables (huge lookup tables mapping common password hashes → plaintexts) and ensures two users with the same password get different stored hashes.
• Slow hash functions on purpose: general-purpose hashes (SHA-256) are too fast, making brute-force guessing cheap at scale. Password-specific KDFs like bcrypt, scrypt, and Argon2 are deliberately slow and/or memory-hard, making large-scale offline guessing far more expensive for an attacker.

Common password-system pitfalls

• Weak passwords / password reuse: the human factor is usually the weakest link, not the crypto.
• Online guessing: mitigated via rate-limiting, account lockouts, or CAPTCHAs.
• Offline guessing (attacker has the stolen hash database): mitigated by salting + slow hashing, as above.

Beyond Passwords: Multi-Factor Authentication (MFA)

Authentication factors are typically categorized as:

1. Something you know - password, PIN.
2. Something you have - phone (SMS/authenticator app codes), hardware security key (e.g., YubiKey, using public-key challenge-response).
3. Something you are - biometrics (fingerprint, face, iris).

MFA requires two or more independent factors - compromising a password alone is no longer sufficient. TOTP (Time-based One-Time Password) apps compute a code from a shared secret + the current time; hardware security keys (FIDO2/WebAuthn) use public-key cryptography to resist even sophisticated phishing (the key cryptographically verifies it’s talking to the real site’s domain).

Session Management

After successful authentication, systems typically issue a session token/cookie so the user doesn’t need to re-authenticate on every request - but this token becomes a new, sensitive secret in its own right (vulnerable to session hijacking if leaked, mitigated with short expiry, secure transport (HTTPS), and HttpOnly/Secure cookie flags in the web context).

7.3 Access Control

Once a user/process is authenticated, access control decides what it’s allowed to do to which resources.

Access Control Matrix - the Conceptual Model

	File A	File B	Process P
User 1	read, write	read	-
User 2	read	read, write, execute	signal

Storing this matrix directly (dense, mostly empty) is impractical at scale, so real systems store it sparsely in one of two complementary ways:

ACLs (Access Control Lists) - Store by Column (per-object)

Each resource stores a list of which subjects can access it, and how. Easy to answer “who can access this file?”; harder to answer “what can this user access?” (must scan every object).

file.txt: [ (alice, rw), (bob, r), (group:eng, rw) ]

Capabilities - Store by Row (per-subject)

Each subject holds a set of unforgeable tokens (capabilities), each granting specific rights to a specific object - possession of the capability itself is the authorization (no separate lookup needed). Easy to answer “what can this process access?”; harder to answer “who can access this object?” (capabilities may be scattered across many subjects, and can be delegated/copied, complicating revocation).

UNIX Permissions - a Practical, Simplified ACL

As covered in §5.4: owner/group/other × read/write/execute - a deliberately coarse-grained, simple approximation of full ACLs, easy to reason about, at the cost of limited expressiveness (can’t easily grant “these 3 specific users” access without creating a dedicated group).

DAC vs. MAC

• Discretionary Access Control (DAC): the resource owner decides who else gets access (classic UNIX permissions, ACLs) - flexible, but a compromised or careless owner/process can freely (mis)grant access.
• Mandatory Access Control (MAC): a system-wide security policy, set by an administrator and enforced by the OS/kernel, overrides individual users’ discretion - even the resource owner cannot override it. Used where strong, centrally-enforced guarantees matter (military/government systems; SELinux, AppArmor on Linux enforce MAC-style policies confining even root-owned processes).

The setuid Bit - Controlled Privilege Escalation

A setuid executable runs with the file owner’s privileges rather than the invoking user’s - e.g., /usr/bin/passwd is owned by root and setuid, letting an ordinary user modify the (root-only-writable) password database, but only through the constrained, audited logic inside passwd itself. A classic, deliberately narrow “escape hatch” through least-privilege, and historically a rich source of privilege-escalation vulnerabilities when such programs contain bugs.

Sandboxing & Modern Isolation

Beyond classic file permissions, modern systems isolate processes using: chroot/containers (namespace-based filesystem/process/network isolation, e.g., Docker via Linux namespaces + cgroups), seccomp (restrict which system calls a process may even invoke), and hardware virtualization (full VMs, hypervisors) for the strongest isolation boundary short of physically separate machines.

7.4 Cryptography

Cryptography provides the mathematical primitives underlying authentication, secure communication, and integrity-checking throughout the OS and network stack.

Kerckhoffs's Principle

A cryptographic system should be secure even if everything about it except the key is public knowledge. Never rely on secret algorithms (“security through obscurity”) - rely on mathematically-hard problems and secret keys only.

Symmetric-Key Cryptography

The same secret key is used to both encrypt and decrypt.

$$C=E_K(P)P=D_K(C)$$

where $P$ = plaintext, $C$ = ciphertext, $K$ = shared secret key, $E/D$ = encrypt/decrypt functions.

• AES (Advanced Encryption Standard): the dominant modern symmetric cipher - fast, hardware-accelerated on most CPUs (AES-NI).
• Strength: very fast, efficient for bulk data.
• Weakness: key distribution problem - both parties need the same secret key beforehand, and getting it to them securely (especially over an insecure channel) is itself a hard problem.

flowchart LR
    A["Alice"] -->|"Encrypt with shared key K"| C1["Ciphertext"]
    C1 -->|"sent over insecure network"| B["Bob"]
    B -->|"Decrypt with SAME key K"| P["Plaintext recovered"]

Asymmetric-Key (Public-Key) Cryptography

Each party has a key pair: a public key (freely shared) and a private key (kept secret). Data encrypted with the public key can only be decrypted with the matching private key.

$$C=E_{K_{pub}}(P)P=D_{K_{priv}}(C)$$

• RSA: based on the difficulty of factoring large numbers.
• ECC (Elliptic Curve Cryptography): based on the elliptic-curve discrete-logarithm problem - comparable security to RSA with much smaller keys, faster operations - widely preferred in modern systems.
• Solves the key-distribution problem: no shared secret needs to be exchanged in advance - Bob just needs Alice’s public key, which doesn’t need to be kept secret at all.
• Weakness: computationally much more expensive than symmetric crypto - impractical for encrypting large amounts of data directly.

Hybrid Systems - the Real-World Answer

Because asymmetric crypto is slow and symmetric crypto has the key-distribution problem, practically every real protocol (including TLS, which secures HTTPS) combines both: use asymmetric crypto once, briefly, to securely establish a shared symmetric session key, then switch to fast symmetric encryption for the actual bulk data.

sequenceDiagram
    participant C as Client
    participant S as Server

    C->>S: ClientHello
    S->>C: ServerHello + Certificate (contains server's public key)
    C->>C: verify certificate (via a trusted Certificate Authority)
    C->>S: encrypt a fresh random session key using SERVER'S PUBLIC KEY, send it
    S->>S: decrypt using its PRIVATE KEY → both sides now share the session key
    Note over C,S: Switch to fast SYMMETRIC encryption (e.g., AES)\nfor the rest of the connection

Cryptographic Hash Functions

A hash function $h$ maps arbitrary-length input to a fixed-length output (“digest”), with three critical security properties:

1. Pre-image resistance: given $h(x)$, hard to find any $x$ that produces it (one-way).
2. Second pre-image resistance: given $x$, hard to find a different $x^{\prime }$ with $h(x)=h(x^{\prime })$.
3. Collision resistance: hard to find any two distinct inputs $x\ne x^{\prime }$ with $h(x)=h(x^{\prime })$.

Used for: password storage (§7.2), data integrity checks (§5.10’s checksums, when cryptographic strength is needed), and as a building block for digital signatures. Modern choice: SHA-256/SHA-3 family (older MD5 and SHA-1 are now considered broken - practical collisions have been demonstrated - and should not be used for security purposes).

Digital Signatures

Using a private key to “sign” data (typically, sign a hash of the data for efficiency) lets anyone with the corresponding public key verify both authenticity (it really came from the claimed sender) and integrity (it wasn’t tampered with) - the cryptographic reverse of encryption (sign with private key, verify with public key, vs. encrypt with public, decrypt with private).

$$\text{Signature}={\text{Sign}}_{K_{priv}}(h(\text{message})){\text{Verify}}_{K_{pub}}(\text{message},\text{Signature})\to \text{true/false}$$

Where this shows up across the OS stack

• Code signing: OS verifies an app/driver’s publisher before running it (macOS Gatekeeper, Windows Driver Signing, Android APK signing).
• Secure Boot: firmware verifies a cryptographic signature on the bootloader/kernel before executing it - extending the “chain of trust” all the way from power-on (§0.8) through to a fully-verified OS.
• TLS certificates: a Certificate Authority’s digital signature vouches “this public key really belongs to this domain.”
• Package managers (apt, npm, etc.): verify signatures on downloaded packages to detect tampering/supply-chain attacks.

---

Part 8 - Real-World Operating Systems

Connecting theory to practice

Every mechanism above exists, in some recognizable form, in the OS you’re using right now. This part is a quick-reference tour.

8.1 Linux

• Kernel type: Monolithic (with loadable kernel modules for drivers/filesystems - giving some of microkernel’s flexibility without the IPC overhead).
• Scheduler: CFS (Completely Fair Scheduler) historically default for normal tasks (vruntime + red-black tree, §2.6); EEVDF scheduler has since become the default in newer kernels, refining the fairness/latency tradeoff further; real-time policies (SCHED_FIFO, SCHED_RR) available for latency-critical tasks.
• Memory: multi-level page tables (4-5 levels on x86-64), COW fork(), mmap()-centric design, Transparent Huge Pages, the OOM killer (kills a process, chosen via a heuristic “badness” score, when memory is critically low and thrashing/exhaustion looms).
• Concurrency primitives: futex (fast userspace mutex) underlies pthread mutexes; epoll for scalable event-driven I/O.
• File systems: ext4 (journaling, default on many distros), XFS (high-performance, scales well), Btrfs (copy-on-write, checksums, snapshots), F2FS (flash-optimized, log-structured).
• Process/resource isolation: namespaces (PID, network, mount, user, etc. - isolate what a process can see) + cgroups (control groups - limit/account resource usage: CPU, memory, I/O) - together, the literal foundation of containers (Docker, Kubernetes pods, etc.), without needing full hardware virtualization.
• Security: SELinux/AppArmor (MAC, §7.3), seccomp (syscall filtering), capabilities (fine-grained root-privilege splitting, distinct from the ACL-vs-capability access-control model in §7.3 but named similarly).

8.2 Windows (NT kernel family)

• Kernel type: Hybrid - a microkernel-inspired core (the “NT kernel,” with the HAL, or Hardware Abstraction Layer, isolating hardware differences) but with many subsystems (graphics historically, file systems, network) running in kernel mode for performance.
• Process model: a Windows “process” is a resource container; actual execution happens via threads (closer to OSTEP’s terminology than UNIX’s traditional process-centric view) - CreateProcess() is Windows’s rough (much heavier-weight) analog of fork()+exec() combined into one call, reflecting the lack of a native fork()-style split.
• Scheduler: priority-based, preemptive, with dynamic priority boosting for interactive/foreground applications (broadly similar goals to MLFQ, §2.5, different specifics).
• Memory: virtual memory with paging, similar multi-level translation concepts; the Working Set Manager actively tunes each process’s resident page count.
• File system: NTFS - journaling (metadata-only by default), ACL-based permissions (a much richer, more explicit ACL model than classic UNIX rwx, matching §7.3’s general ACL discussion closely), alternate data streams, built-in compression/encryption (EFS) support.
• Security: UAC (User Account Control - a practical least-privilege mechanism, running most apps with reduced privilege by default even for administrator accounts), Windows Defender, BitLocker (full-disk encryption).

8.3 macOS / iOS (XNU kernel)

• Kernel type: XNU - a genuine hybrid of the Mach microkernel (message-passing IPC, virtual memory, scheduling) and a BSD (UNIX) layer providing the POSIX process/file model, plus I/O Kit for driver development.
• Process API: full POSIX compliance - fork(), exec(), etc. work as described in §2.2, layered on top of Mach’s lower-level task/thread primitives.
• File system: APFS (Apple File System) - copy-on-write, native snapshots, strong encryption support, optimized for flash/SSD (§5.9).
• Security: Sandboxing (App Sandbox - mandatory, fine-grained per-app restriction, a strong real-world MAC example, §7.3), Gatekeeper (code-signing verification before running downloaded apps), System Integrity Protection (SIP) (even root cannot modify certain protected system files/directories - a deliberate, drastic reduction of the effective TCB attack surface for core OS files).
• iOS additionally adds: mandatory app sandboxing for all apps (no exceptions), a locked-down boot chain (Secure Enclave + Secure Boot chain of trust extending §0.8 and §7.4’s digital-signature discussion all the way to silicon), and no user-facing general-purpose filesystem access by default.

8.4 Mobile & Specialized: Android

• Kernel: a modified Linux kernel underneath (inherits the scheduler, memory management, and namespaces/cgroups foundation from §8.1) plus Android-specific additions (the Binder IPC mechanism, a specialized, more structured alternative to raw UNIX IPC, central to how Android apps/services communicate).
• Process model: every app runs as its own Linux user (UID), so classic UNIX permission isolation (§5.4, §7.3) becomes Android’s primary inter-app sandboxing mechanism - a clever, minimal-new-mechanism reuse of decades-old UNIX primitives for a completely new security goal.
• Memory management: aggressive process lifecycle management - background apps are frozen/killed under memory pressure far more proactively than a desktop OS’s OOM killer, since mobile devices have much tighter memory/battery budgets (directly motivated by §0.5’s memory-hierarchy cost/latency tradeoffs, applied under real energy constraints).

8.5 Virtualization & the Cloud: One More Layer of Abstraction

Modern infrastructure adds an entire additional virtualization layer below the OS.

flowchart TB
    subgraph HostHW["Physical Hardware"]
        direction TB
        HV["Hypervisor (Type 1, e.g. Xen, KVM, ESXi)\n- runs directly on hardware"]
        HV --> VM1["Guest OS 1\n(full kernel + apps)"]
        HV --> VM2["Guest OS 2\n(full kernel + apps)"]
    end

• Type 1 (bare-metal) hypervisor: runs directly on hardware (Xen, VMware ESXi, Microsoft Hyper-V, Linux KVM) - used pervasively in cloud datacenters (AWS EC2, etc.) to run many independent guest OS instances (VMs) on one physical machine, applying exactly the same virtualization philosophy from Part 2/3 (CPU and memory virtualization) but one level lower, virtualizing an entire OS instead of a single process.
• Type 2 (hosted) hypervisor: runs as an application on top of a normal host OS (VirtualBox, VMware Workstation, Parallels) - simpler to use, generally lower performance than Type 1.
• Containers vs. VMs: containers (§8.1) share the host kernel and isolate only at the process/namespace level - much lighter weight (no full guest kernel boot, near-native performance) but a weaker isolation boundary than a full VM (a kernel exploit can potentially escape a container; escaping a properly-configured VM typically requires a hypervisor-level vulnerability, a much rarer and higher-value bug class).
• microVMs (e.g., AWS Firecracker): a modern middle ground - minimal, purpose-built virtual machines with startup times and memory overhead approaching containers, but retaining VM-level hardware-enforced isolation - the technology underlying AWS Lambda’s serverless function isolation.

---

Part 9 - Cheat Sheets & Quick Reference

9.1 Formula Cheat Sheet

$$\begin{array}{rlr}{T}_{turnaround}& =T_{completion}-T_{arrival}& \text{(scheduling)}\\ T_{response}& =T_{firstrun}-T_{arrival}& \text{(scheduling)}\\ P(\text{job }i\text{ wins lottery})& =\frac{ticket{s}_i}{{\sum }_{j}ticket{s}_j}& \text{(lottery scheduling)}\\ strid{e}_i& =\frac{large\_number}{ticket{s}_i}& \text{(stride scheduling)}\\ \text{PA}& =\text{VA}+\text{base},0\le \text{VA}<\text{bounds}& \text{(dynamic relocation)}\\ \text{VA}& =\text{VPN}\Vert \text{offset}& \text{(paging)}\\ buddy(addr,size)& =addr\oplus size& \text{(buddy allocation)}\\ P& =D_0\oplus D_1\oplus \cdots \oplus D_{n-1}& \text{(RAID parity)}\\ P_{new}& =(D_{old}\oplus D_{new})\oplus P_{old}& \text{(RAID small-write optimization)}\\ T_{I/O}& =T_{seek}+T_{rotation}+T_{transfer}& \text{(disk I/O time)}\\ C& =E_K(P),P=D_K(C)& \text{(symmetric crypto)}\\ C& =E_{K_{pub}}(P),P=D_{K_{priv}}(C)& \text{(asymmetric crypto)}\end{array}$$

9.2 Process API Quick Reference

Call	Effect
fork()	Duplicate calling process; returns twice (0 in child, child PID in parent)
exec(path, args)	Replace current process image with a new program; doesn’t return on success
wait(status) / waitpid()	Block until a child exits; reap its exit status
exit(status)	Terminate calling process with given status code
kill(pid, sig)	Send a signal to another process
open/read/write/close	File I/O via file descriptors
pipe(fds)	Create an in-kernel unidirectional byte-stream channel between processes
mmap()	Map a file (or anonymous memory) directly into the address space

9.3 Concurrency Primitives Quick Reference

Primitive	Use it when…
Lock / Mutex	You need mutual exclusion around a critical section - nothing more
Condition Variable	A thread must wait until some condition becomes true (always paired with a lock, always re-check in a while)
Semaphore	You need to track a count of available resources, or want a single primitive that can express both mutual exclusion and ordering/signaling
Reader-Writer Lock	Many concurrent readers are safe, but writers need exclusive access
Atomic instructions (CAS, etc.)	You want a lock-free fast path for a very small, well-defined operation

9.4 Scheduling Policy Comparison

Policy	Optimizes	Needs future knowledge?	Preemptive?
FIFO	Simplicity	No	No
SJF	Turnaround (avg)	Yes	No
STCF	Turnaround (avg)	Yes	Yes
Round Robin	Response time	No	Yes
MLFQ	Both (approximated)	No - learns from history	Yes
Lottery / Stride / CFS	Proportional fairness	No	Yes

9.5 Page Replacement Policy Comparison

Policy	Idea	Belady’s Anomaly?
Optimal (MIN)	Evict page used furthest in future	No (theoretical baseline)
FIFO	Evict oldest-loaded page	Yes
LRU	Evict least-recently-used page	No
Clock / Second-Chance	Hardware-bit approximation of LRU	No (approximation of LRU)

9.6 File System Crash-Consistency Comparison

Approach	Recovery Time	Overhead
fsck (full scan)	Slow - scales with disk size	None during normal operation
Metadata journaling	Fast - scales with journal size	Moderate (metadata written twice)
Full data journaling	Fast	High (all data written twice)
Log-structured (LFS)	Fast	Ongoing garbage-collection overhead

9.7 RAID Levels at a Glance

Level	Redundancy	Usable Capacity	Tolerates
0	None	100%	0 failures
1	Mirroring	50%	1 per mirrored pair
4	Dedicated parity	(N-1)/N	1 disk
5	Rotating parity	(N-1)/N	1 disk
6	Double parity	(N-2)/N	2 disks

---

Part 10 - Glossary

Quick-lookup definitions

Terms are listed alphabetically; cross-reference the relevant Part above for full detail.

• ACL (Access Control List): per-resource list of who can access it and how.
• Address Space: a process’s private view of memory (code, heap, stack).
• ASLR: Address Space Layout Randomization - randomizes memory layout to make exploits harder.
• Atomicity: an operation that appears indivisible - either fully happens or not at all.
• Cache Coherence: hardware protocol ensuring all CPU cores see a consistent view of memory.
• Capability: an unforgeable token granting specific access rights to a specific object.
• Checksum: a small value derived from data, used to detect corruption.
• Concurrency: multiple tasks making progress during overlapping time periods.
• Context Switch: saving one process/thread’s CPU state and restoring another’s.
• Critical Section: code accessing shared state that must not run concurrently with itself.
• Deadlock: a cycle of threads each waiting on a resource held by another, with no progress possible.
• DMA: Direct Memory Access - hardware that moves data between device and memory without CPU involvement.
• Fork/Exec: UNIX process creation (fork) and program-loading (exec) primitives.
• Inode: on-disk structure holding a file’s metadata and data-block pointers.
• Interrupt: hardware-initiated transfer of control to the OS (e.g., timer, device completion).
• Journaling: write-ahead logging technique for fast crash recovery in file systems.
• Kernel: the core, privileged part of the OS.
• Lock (Mutex): synchronization primitive enforcing mutual exclusion.
• MLFQ: Multi-Level Feedback Queue scheduler.
• MMU: Memory Management Unit - hardware that translates virtual to physical addresses.
• Page: fixed-size unit of virtual memory (and its physical counterpart, a “frame”).
• Page Fault: trap raised when accessing a page not currently in physical memory.
• Page Table: per-process data structure mapping virtual pages to physical frames.
• Paging: memory virtualization scheme using fixed-size pages.
• Parity: redundant data (via XOR) enabling reconstruction of lost data (RAID).
• PCB (Process Control Block): OS data structure holding a process’s saved state.
• Persistence: durability of stored data across crashes/power loss.
• Process: OS abstraction for a running program.
• Race Condition: outcome depends on non-deterministic thread/process interleaving.
• RAID: Redundant Array of Independent Disks - combining disks for performance/reliability.
• RPC: Remote Procedure Call - making a network call resemble a local function call.
• Scheduler: OS component deciding which process/thread runs next.
• Segmentation: memory virtualization scheme using variable-sized logical segments.
• Semaphore: general-purpose synchronization primitive (integer + wait/post operations).
• Signal: asynchronous notification sent to a process.
• Superblock: file-system-wide metadata structure.
• Swap Space: disk area used as overflow for physical memory.
• System Call: a controlled request from user code into the kernel.
• Thread: an independent execution stream sharing an address space with sibling threads.
• TLB: Translation Look-aside Buffer - hardware cache of address translations.
• Trap: instruction that transfers control from user to kernel mode.
• Virtualization: presenting a limited physical resource as an abundant, private, virtual one.

---

Part 11 - Further Study

Where to go from here

• Book: Operating Systems: Three Easy Pieces (OSTEP) - free at ostep.org - this document’s primary structural backbone; read the original for full mathematical rigor, homework labs, and additional dialogues.
• Book: Modern Operating Systems by Andrew Tanenbaum - broader coverage, strong on microkernels and distributed systems.
• Book: The Design and Implementation of the FreeBSD Operating System - deep real-world implementation detail.
• Book: Designing Data-Intensive Applications by Martin Kleppmann - excellent follow-on for the distributed-systems material in Part 6.
• Source code: reading real kernel source (Linux kernel/sched/, mm/, fs/) is the single best way to move from “textbook understanding” to “systems engineer understanding.”
• Practice: build a tiny OS kernel (e.g., following the xv6 teaching OS from MIT, or the OSTEP projects/labs) - nothing cements these concepts like implementing a context switch or a page-fault handler yourself.
• CTFs / security labs: hands-on exploitation practice (e.g., buffer overflows, privilege escalation) makes Part 7’s security principles concrete.

You've now covered

How a computer works at the hardware level → what an OS is and why → CPU virtualization (processes, scheduling) → memory virtualization (address spaces, paging, swapping) → concurrency (threads, locks, races, deadlock) → persistence (disks, file systems, crash consistency) → distributed systems → security & cryptography → and how it all shows up in Linux, Windows, macOS, Android, and the cloud.

That is the complete arc of operating systems, beginner to advanced. 🎓