A lecture-by-lecture reading of Stanford CS111: processes, threads, synchronization, virtual memory, file systems, and operating-system design trade-offs.
CS111 is Stanford's operating systems principles course, organized into concurrency, memory management and file systems, with nine assignments. All 28 lecture handouts, the nine assignment specs and three years of midterms and finals with solutions are public; the starter code requires a login on Stanford's myth machines, and the recordings are on Canvas.
Lecture 1 follows shared I/O cards in the 1940s, batch processing, multiprogramming, and personal computers to explain how OS responsibilities accumulated as hardware costs and user needs changed.
Lecture 2 defines shared and private process/thread state, then uses fork, execvp, waitpid, and thread creation to show how the kernel creates execution units.
Lecture 3 follows running, blocked, and ready transitions to show how PCBs, context save/restore, and the dispatcher complete one CPU-control handoff.
Lecture 4 defeats each Too Much Milk attempt with an explicit schedule, deriving race condition, atomicity, critical section, and synchronization requirements from concrete interleavings.
Lecture 5 uses an eight-slot circular Pipe to prove that a mutex supplies exclusion, while a condition variable atomically releases the lock and blocks when a predicate is false; under Mesa semantics, wait must return to a while loop that rechecks the predicate.
Lecture 6 evolves a one-core interrupt-masking lock through multicore version 5, tracking guard, lock, and wait-queue state to prevent races and lost wakeups.
Lecture 7 extracts four necessary deadlock conditions from request/ownership graphs, then compares detection, prevention, and lock ranking; breaking circular wait is common in practice, but every module must obey one global order.
Lecture 8 moves from FIFO and round robin through the unimplementable SRPT ideal to adaptive priority queues and the multicore conflict among queue contention, core affinity, and work conservation.
Lecture 9 follows source through assembly, object, executable, and process, explaining the linker's three passes and how a dynamic loader resolves shared-library addresses through a jump table at startup.
Lecture 10 moves from predictable LIFO stacks to heap free lists, first/best fit, and slabs, then compares reference counting with mark-and-sweep across dangling pointers, leaks, cycles, and fragmentation.
Lecture 11's official PDF is byte-identical to Lecture 10; this article preserves that artifact gap and focuses on reachability, dangling pointers, leaks, reference-count cycles, and mark/compact garbage collection.
Lecture 12 defines trust as voluntary vulnerability, separates over-trust from untrustworthiness, and applies assumption, inference, and substitution to the Linux TCB, the xz attack, and AI-code policy.
Lecture 13 starts from the failures of single-tasking and load-time relocation, uses an MMU with base/bound to create isolated virtual and physical address spaces and traps, then introduces segmentation to escape one contiguous region.
Lecture 14's official PDF is byte-identical to Lecture 13; this article records the gap and focuses on how multiple base/bound/protection entries enable growth, sharing, and compaction while retaining fixed-count, fragmentation, and rigid-layout limits.
Lecture 15 uses fixed pages to remove inter-process external fragmentation, then connects x86-64's four-level walk, sharing and aliasing, and the TLB to trade-offs among translation speed, sparse tables, context switches, and page size.
Demand paging loads pages only when needed; present bits, precise exceptions, and restartable instructions let the kernel safely fill them from executables, zero-fill, or backing store.
Lecture 17 separates demand paging into fetching and replacement: MIN cannot know the future, exact LRU is too expensive, and Clock uses reference/dirty bits to find a page old enough to evict; when active working sets exceed RAM, even a 1% fault rate can cause an approximately 1,000-fold slowdown.
A disk hides mechanical seek and rotation behind a linear block API; modern I/O then uses memory-mapped registers, DMA queues, and interrupts so the CPU mainly issues commands and receives completions.
A file system maps durable byte collections onto disk blocks; contiguous, linked, and FAT allocation trade locality, growth, random access, and metadata cost.
The 4.3BSD inode uses direct, single-indirect, and double-indirect tiers so lookup depth scales with file size; FIFO, SPTF, SCAN, and CSCAN then trade seek cost, fairness, and wait time.
Block cache retains hot indexes, bitmap slack preserves placement choices, and fragments plus delayed allocation trade later, better information for locality.
Directories map text names to file-system-local inode numbers; hard links share inode identity and reference counts, while symlinks store paths and permit cross-filesystem references with loops and dangling targets.
A single file-system operation updates several blocks, but a crash can occur between any two writes; this lecture compares how fsck, ordered writes, and write-ahead logging trade recovery time, performance, durability, and consistency.
Lecture 24 continues from the WAL entry point into transactions, idempotent replay, and checkpoints, showing why consistency is not durability and why a journal does not replace fsync or backups.
Lecture 25 separates assumption, inference, and substitution as ways to establish trust, then examines how social recommendations, generative AI, and synthetic media amplify over-trust; the response is preserved provenance, independent validation, and coordinated responsibility.
Flash programs pages but erases whole units; an FTL hides the asymmetry with out-of-place mapping, then manages amplification through garbage collection, temperature segregation, wear leveling, and TRIM.
A VM expands the process interface into a machine interface; the hypervisor directly executes ordinary instructions, traps privileged operations, and virtualizes interrupts, I/O, and two-stage address translation.
Lecture 28 reduces the semester to concurrency, memory, and storage, then uses four ideas—virtualization, atomicity, locality, and layering—to explain how operating systems manage shared resources.