Operating Systems: Three Easy Pieces

Citation

Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. (2018–2023). Operating Systems: Three Easy Pieces (version 1.10). Arpaci-Dusseau Books. Free official edition: https://pages.cs.wisc.edu/~remzi/OSTEP/

Chapter Summary

The book is organised around three themes, virtualization, concurrency and persistence, each introduced by a short dialogue between a professor and a student and followed by chapters that usually open with a boxed "crux of the problem". An introduction comes first; a distributed-systems section and a set of security chapters by Peter Reiher (UCLA) follow the three main parts; appendices cover virtual machine monitors, monitors, a C tutorial and lab ideas.

Chapters 1–2: A Dialogue on the Book; Introduction to Operating Systems

The opening dialogue explains the title (a nod to Feynman's lectures) and the three themes. Chapter 2 starts from the von Neumann model of a running program and shows how an operating system virtualizes the CPU and memory, copes with concurrency and stores data persistently. It closes with design goals such as abstraction, performance, protection and reliability, and a short history of operating systems.

Chapters 3–6: Processes and Limited Direct Execution

After the dialogue on virtualization, Chapter 4 defines the process and its states, creation and bookkeeping structures. Chapter 5 is the first "interlude", a practical chapter on the UNIX process API: fork(), wait(), exec(), and why they are separated. Chapter 6 explains limited direct execution: user and kernel mode, system calls and traps, and how timer interrupts let the OS regain the CPU for a context switch.

Chapters 7–11: CPU Scheduling

Chapter 7 builds scheduling up from stated workload assumptions and metrics (turnaround and response time) through FIFO, shortest job first, shortest time-to-completion first and round robin, then adds I/O. Chapter 8 develops the multi-level feedback queue in successive attempts. Chapter 9 covers lottery and stride scheduling and the Linux Completely Fair Scheduler. Chapter 10 is an advanced chapter on multiprocessor scheduling (cache affinity, single and multiple queues). Chapter 11 is a summary dialogue.

Chapters 12–17: Address Spaces, Translation and Free Space

Chapter 13 introduces the address space and its goals. Chapter 14 is an interlude on malloc() and free() and common memory errors. Chapter 15 introduces base-and-bounds translation, Chapter 16 generalises it to segmentation, and Chapter 17 treats free-space management for variable-sized allocations.

Chapters 18–24: Paging and Virtual Memory

Chapter 18 introduces paging and page tables, Chapter 19 TLBs, and Chapter 20 smaller page tables (bigger pages, hybrid approaches, multi-level and inverted tables). Chapters 21 and 22 cover swapping mechanisms and replacement policies including OPT, FIFO, random, LRU and clock-style approximations, with thrashing. Chapter 23 describes two complete systems, VAX/VMS and Linux. Chapter 24 is the summary dialogue.

Chapters 25–34: Concurrency

Chapter 26 motivates threads and shows how shared data and uncontrolled scheduling produce races. Chapter 27 is the thread API interlude. Chapter 28 builds locks from hardware support (test-and-set, compare-and-swap, load-linked/store-conditional, fetch-and-add) and then adds yielding and queues. Chapter 29 applies locks to concurrent counters, lists, queues and hash tables. Chapters 30 and 31 cover condition variables and semaphores through producer/consumer, reader-writer locks and dining philosophers. Chapter 32 surveys non-deadlock and deadlock bugs, and Chapter 33 presents event-based concurrency with select() and asynchronous I/O. Chapter 34 summarises.

Chapters 35–46: Persistence

Chapter 36 covers I/O devices, interrupts, DMA and drivers; Chapters 37 and 38 hard disk drives (with disk scheduling) and RAID. Chapter 39 is the files-and-directories interlude. Chapter 40 builds a simple file system with inodes and directories. Chapter 41 turns to the Fast File System, Chapter 42 to crash consistency (fsck and journaling) and Chapter 43 to log-structured file systems. Chapter 44 explains flash-based SSDs, and Chapter 45 data integrity with checksums and scrubbing.

Chapters 47–51: Distribution

A short sequence on distributed systems: communication layers and RPC (Chapter 48), then two case studies of distributed file systems, NFS (Chapter 49) and AFS (Chapter 50), the first built around stateless servers and idempotent operations, the second around whole-file caching and callbacks, with summary dialogue (Chapter 51).

Chapters 52–57: Security

Peter Reiher's chapters introduce security goals and policies (Chapter 53), authentication (54), access control with ACLs and capabilities (55), cryptography including public-key methods, hashes and at-rest encryption (56), and securing distributed systems with TLS (57).

Appendices

Short appendices treat virtual machine monitors (virtualizing the CPU and memory), monitors as a higher-level synchronization construct (with Java examples), a tutorial on compiling, debugging and building C programs, and ideas for systems programming and xv6 labs.

Key Concepts

Chapters 1–11: CPU Virtualization

• Process: a running program, whose state the OS saves and restores.
• Limited direct execution: running programs directly on the CPU while the OS keeps control through privilege modes, traps and timer interrupts.
• Scheduling metrics: turnaround time versus response time, which different policies optimize.
• Multi-level feedback queue: a scheduler that infers job behaviour from history.

Chapters 12–24: Memory Virtualization

• Address space: each process's private view of memory.
• Paging and the TLB: fixed-size translation units and the hardware cache that makes them fast.
• Multi-level page table: a structure that avoids storing translations for unused address space.
• Page replacement: the policy deciding what to evict when memory is full.

Chapters 25–34: Concurrency

• Race condition and critical section: the bug pattern and the code region that locks protect.
• Condition variable and semaphore: primitives for waiting on, and signalling, state changes.
• Deadlock: a cycle of waits that the book analyses by its four conditions.

Chapters 35–46: Persistence

• Inode: the per-file structure at the heart of a UNIX-style file system.
• Crash consistency and journaling: write-ahead logging so that metadata survives a crash.
• Log-structured file system: turning all writes into sequential writes.
• Checksum: the basic detector of silent corruption.

Chapters 47–57: Distribution and Security

• Idempotent operation and stateless server: the NFS design for easy crash recovery.
• Access control list and capability: two ways to record who may do what.
• Public-key cryptography and TLS: the tools for securing communication between machines.

Critical Analysis

Strengths

• Short, problem-driven chapters. Almost every chapter states a crux, builds a solution in stages (for example the three "attempts" of the multi-level feedback queue and the successive lock designs) and ends with a summary. Chapters are short enough to be read in one sitting.
• Concurrency after virtualization. The authors defend delaying threads until address spaces, processes and context switches are understood; the order makes the origin of races clear.
• Real code and runnable homework. Examples are in C rather than pseudocode, with code on GitHub. Many chapters end with simulator-based homework whose random seeds generate new problems, and some with measurement or coding tasks.
• History and sources. Chapters point to the original papers and name the people behind the ideas, which suits readers who plan to read the research literature next.
• Free to read. The chapters are free as PDFs, so the book can be assigned or read without cost.

Limitations

• Prerequisites are assumed. The introduction expects the reader to know what a running program does (it recommends Patt and Patel, or Bryant and O'Hallaron, as background), and the code is in C.
• Examples lean on UNIX. The process, file and thread APIs are UNIX/POSIX, and the complete-system case study covers VAX/VMS and Linux virtual memory.
• Selective coverage. The book follows one course design. Topics such as networking stacks, graphics, or mobile and embedded systems are outside it; the distributed-systems and security parts are brief next to the three main pieces.
• Dialogues and humour are a matter of taste. The dialogues are optional and some readers find them dispensable.

Where It Fits in the Course

This is a compact route through a full operating-systems course: three themes, short chapters, and code and homework to match. Operating System Concepts is the long, broad textbook with examples from many commercial systems and programming projects; Modern Operating Systems is a standard textbook with extended Linux, Android and Windows case studies. Either gives wider coverage of the same material, while this book gives a more narrative explanation of how and why the mechanisms work.

How Linux Works is a practical guide to a real Linux system and is a useful companion for seeing the concepts on a live machine. Principles of Computer System Design is not an operating-systems textbook as such but a book about design principles that cut across operating systems, networks and fault tolerance; it suits a reader who has finished this book and wants to generalise.

How to Use This Book

The book is for readers who can program in C and know roughly how a program executes on a processor, typically in a second- or third-year operating-systems course or in self-study.

A practical plan:

• Core: Chapters 2, 4–9 (CPU virtualization), 13–22 (memory), 26–32 (concurrency) and 36–40, 42 (devices, file systems and crash consistency). The authors note that the course divides fairly well into a 15-week semester.
• Optional or advanced: Chapter 10 (multiprocessor scheduling), Chapter 23, Chapter 33 (event-based concurrency), the SSD, LFS and data-integrity chapters, and the distributed-systems and security sections.
• Dialogues: read them for orientation; they can be skipped.

Type in and run the code in the interludes, and do the simulator homeworks after each chapter, using fresh random seeds until the answers come reliably. For deeper practice, take on the systems-programming or xv6 project ideas listed in the appendices. Return to the cited papers for any topic you want to study more closely.

Edition and Sources

This guide covers the free online edition at https://pages.cs.wisc.edu/~remzi/OSTEP/, which the authors cite as version 1.00 (August 2018), 1.01 (July 2019) and 1.10 (October 2023); the chapter files read carry version 1.10 and 1.20 headers. It is based on the free text: the preface, the table of contents, the dialogues, the opening and crux of every chapter, and the section headings of all chapters, including the security chapters and appendices.