Operating Systems: Three Easy Pieces PDF Download – Arpaci-Dusseau (Version 1.10) BSCS

BSCS, BSIT and BSSE students can read and download the complete Operating Systems textbook “Operating Systems: Three Easy Pieces” by Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau of the University of Wisconsin–Madison. The book is free from its official source and covers the full Operating Systems course taught at Pakistani universities.

The authors organise the whole subject around three ideas — virtualization, concurrency and persistence — and every chapter opens with a “crux” question the chapter then answers. Version 1.10 has 57 chapters plus appendices, each available as its own PDF, and the book is paired with free homework simulators and xv6 lab projects. Because the chapters are short and self-contained, it works equally well as a semester textbook and as revision material the night before a paper.

Book Overview

Course	Operating Systems
Degree Programs	BSCS, BSIT, BSSE
Level	University / Undergraduate
Version	Version 1.10 (November 2023)
Authors	Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-Dusseau (Security chapters with Peter Reiher)
Publisher	Arpaci-Dusseau Books, University of Wisconsin–Madison
Language	English
Total Chapters	57 chapters in five parts, plus appendices
Format	PDF — free per chapter or as a full book

Chapter List

Introduction: The Three Easy Pieces (Chapter 2)

Difficulty: Easy · Key topics: virtualization, concurrency, persistence, the operating system as a resource manager

The opening chapter explains what an operating system actually does and sets up the plan for the rest of the book. A running program does one simple thing — fetch, decode, execute — and the job of the OS is to make that easy, correct and efficient when many programs want the machine at once. The chapter introduces virtualization as the central technique: the OS takes a physical resource such as the CPU, memory or a disk and turns it into a more general, easier-to-use virtual form. It then previews the three pieces the book is named after, and closes with the design goals every later chapter is judged against.

Key Points:

• The operating system is a resource manager: it shares the CPU, memory and disks among many programs.
• Virtualization means turning one physical resource into many easier-to-use virtual ones.
• The three easy pieces are virtualization, concurrency and persistence — the three parts of the book.
• The OS exports its functions to programs through system calls, which form the standard library of the machine.
• Design goals: convenient abstractions, high performance (low overhead), protection and isolation, reliability, energy efficiency and security.

Memory Tip: Remember the three pieces as three questions: who gets the CPU (virtualization), what happens when two things run at once (concurrency), and what survives a power cut (persistence). Every chapter in the book answers one of these three.

Common Mistake: Treating this chapter as a preface and skipping it. The words “crux”, “virtualization” and “mechanism versus policy” are used from here on without being defined again.

Important Questions:

• What is an operating system? The layer of software that manages the hardware, virtualizes the CPU, memory and storage, and gives programs a safe and convenient interface to them through system calls.
• What are the three easy pieces? Virtualization, concurrency and persistence — the three ideas around which the whole book is organised.

Processes and the Process API (Chapters 4–6)

Difficulty: Medium · Key topics: process abstraction, process states, fork(), exec(), wait(), limited direct execution, context switch

These three chapters build the CPU half of virtualization. A process is defined as a running program, and its machine state — memory, registers, program counter, stack pointer and open files — is what the OS saves and restores. The process moves between running, ready and blocked, and the OS tracks it in a process list holding one process control block each. The API chapter covers the UNIX calls: fork() creates a near-copy of the caller, exec() replaces the caller’s program image, and wait() lets a parent pause until the child finishes. The separation of fork and exec is what makes shell redirection and pipes possible. Chapter 6 explains limited direct execution: run the program directly on the CPU for speed, but use user mode, trap instructions and a timer interrupt so the OS can keep control.

Key Points:

• A process is a running program; its state is its address space, registers, program counter, stack pointer and open files.
• Process states: running, ready and blocked — a blocked process is not schedulable until its I/O completes.
• fork() returns 0 in the child and the child’s PID in the parent, which is how the two are told apart.
• exec() does not return on success: it overwrites the calling process with a new program.
• Limited direct execution runs user code on the CPU directly, but restricts it with user mode and traps.
• A timer interrupt is what lets the OS regain the CPU from a program that never yields.
• A context switch saves the registers of the running process and restores those of the next one.

Practice Tip: Write a five-line C program that calls fork(), prints the return value, then calls wait() in the parent. Nothing explains the two return values faster than watching your own program print two different numbers from the same printf line.

Common Mistake: Assuming the child always runs before the parent. Without wait(), the order is decided by the scheduler and can differ on each run.

Important Questions:

• What is the difference between a program and a process? A program is the code sitting on disk; a process is that program while it is running, together with its memory, registers and open files.
• Why does UNIX separate fork() and exec() instead of using one call? Because it leaves a gap between creating the child and loading the new program, and the shell uses that gap to set up redirection and pipes for the child.

CPU Scheduling (Chapters 7–10)

Difficulty: Medium · Key topics: FIFO, SJF, STCF, round robin, turnaround time, response time, MLFQ, lottery scheduling, multiprocessor scheduling

Once the OS can switch between processes, it has to decide which one runs next. The scheduling chapters build policies one problem at a time. FIFO is simple but suffers the convoy effect when a long job arrives first; SJF fixes turnaround time if all jobs arrive together; STCF adds preemption for jobs that arrive later. Round robin then trades turnaround time for good response time by running each job for a short time slice. The Multi-Level Feedback Queue learns from the past: new jobs start at the highest priority and drop as they use up their time allotment, with periodic priority boosts to prevent starvation. Lottery and stride scheduling give proportional shares using tickets. The final chapter moves to multiple CPUs, where cache affinity, cache coherence and lock contention change the problem, and compares single-queue and multi-queue designs.

Key Points:

• Turnaround time = completion time − arrival time; response time = first-run time − arrival time.
• SJF and STCF are optimal for turnaround time but need job lengths, which the OS does not know in advance.
• Round robin gives excellent response time and poor turnaround time — the two goals conflict.
• MLFQ rules: higher priority runs first; equal priority runs round robin; a job that uses its whole allotment moves down; all jobs are boosted to the top periodically.
• Lottery scheduling assigns tickets and picks a random winner, so shares are proportional over time.
• Multiprocessor scheduling adds cache affinity and cache coherence; multi-queue designs need load balancing by migration.

Memory Tip: Keep one contrast in your head: shortest-job-first wins on turnaround time, round robin wins on response time, and MLFQ exists because a real OS wants both without being told the job lengths.

Common Mistake: Forgetting the arrival time when computing average turnaround time in a numerical. Turnaround is measured from when the job arrived, not from when it started running.

Important Questions:

• Why can a real operating system not simply use shortest-job-first? Because SJF requires knowing how long each job will run, and the OS has no such knowledge when the job arrives.
• How does MLFQ prevent starvation of long-running jobs? By periodically boosting every job back to the highest priority queue, so a job pushed to the bottom eventually gets the CPU again.

Address Spaces and the Memory API (Chapters 13–14)

Difficulty: Easy · Key topics: address space, transparency, protection, malloc(), free(), stack versus heap, memory errors

This pair begins the memory half of virtualization. Early machines gave one program all of physical memory; multiprogramming and time sharing forced the OS to keep several programs in memory at once, which immediately raised the protection problem. The answer is the address space: the abstraction of memory each process sees, containing code, a heap that grows downward and a stack that grows upward. Every address a program prints is a virtual address, and the OS with hardware help translates it. The goals are transparency (the program should not know), efficiency (translation must be fast) and protection (one process must not touch another’s memory). The API chapter is practical: stack memory is managed automatically by the compiler, heap memory is yours through malloc() and free(), and the chapter lists the classic errors — forgetting to allocate, allocating too little, dangling pointers, double frees and memory leaks.

Key Points:

• The address space holds code, static data, the heap and the stack; the heap and stack grow toward each other.
• Every address a user program sees is virtual; the OS and hardware translate it to a physical address.
• Goals of virtualizing memory: transparency, efficiency and protection (isolation between processes).
• Stack memory is allocated and freed automatically; heap memory needs malloc() and free().
• malloc() takes a size in bytes — use sizeof(), and remember a string of n characters needs n+1 bytes.
• Classic bugs: buffer overflow, use after free (dangling pointer), double free and memory leak.

Practice Tip: Compile a small program with a deliberate memory leak and run it under valgrind. Reading the tool’s own report of your bug teaches the difference between a leak and a dangling pointer much faster than the definitions do.

Common Mistake: Using strlen(s) as the size for malloc() when copying a string. It leaves no room for the terminating null character and corrupts the byte after your buffer.

Important Questions:

• What is an address space? The abstraction of memory that the OS gives each process — its code, static data, heap and stack, laid out in virtual addresses that are private to it.
• What is a memory leak? Memory allocated on the heap that is never freed, so the program’s memory use grows over time even though the memory is no longer in use.

Address Translation, Segmentation and Free-Space Management (Chapters 15–17)

Difficulty: Hard · Key topics: base and bounds, dynamic relocation, MMU, segments, protection bits, external fragmentation, best fit, buddy allocation

Here the book explains how translation actually works. The simplest hardware support is dynamic relocation: a base register holds where the process’s address space starts in physical memory and a bounds register holds its size, so the memory management unit computes physical = virtual + base and traps if the address exceeds the bounds. It is fast, but it wastes the whole unused gap between the heap and the stack. Segmentation gives each logical piece — code, heap, stack — its own base and bounds pair, so only the used parts occupy physical memory, and adds protection bits so a read-only code segment can be shared safely between processes. The cost is external fragmentation: variable-sized segments leave holes. Chapter 17 studies free-space management on its own, covering splitting and coalescing, the free list, and the classic strategies best fit, worst fit, first fit, next fit, segregated lists and the buddy allocator.

Key Points:

• Dynamic relocation: physical address = virtual address + base, with a trap if the address is beyond the bounds.
• The MMU is the hardware unit that performs translation and the bounds check on every memory reference.
• Segmentation uses one base and bounds pair per segment, so the unused gap between heap and stack costs nothing.
• Protection bits per segment allow read-only code segments to be shared between processes.
• External fragmentation is free physical memory broken into holes too small to be useful; compaction is expensive.
• Best fit searches for the smallest sufficient hole, worst fit the largest, first fit the first that works; coalescing merges neighbouring free blocks.

Memory Tip: Do the offset arithmetic slowly the first time. For a segment whose virtual range begins at 4KB, virtual address 4200 is offset 104 — you subtract the segment’s start before adding the base. Getting this once removes most of the confusion in segmentation numericals.

Common Mistake: Adding the raw virtual address to the segment base instead of the offset within the segment. The result is a legal-looking physical address that points to the wrong place.

Important Questions:

• What is the difference between internal and external fragmentation? Internal fragmentation is unused space inside an allocated block; external fragmentation is free memory split into holes that are individually too small to satisfy a request.
• Why is segmentation better than a single base and bounds pair? Because each segment is placed separately, the large unused region between the heap and the stack does not have to occupy physical memory.

Paging and Translation Lookaside Buffers (Chapters 18–20)

Difficulty: Hard · Key topics: pages and frames, page table, PTE, VPN and offset, TLB, spatial locality, multi-level page tables

Paging replaces variable-sized segments with fixed-size pages, which removes external fragmentation and makes free-space management trivial: any free frame will do. A virtual address splits into a virtual page number and an offset; the page table maps the VPN to a physical frame number, and the page table entry also carries valid, present, protection, dirty and reference bits. The obvious problem is that every memory reference now needs an extra memory reference to read the page table, so Chapter 19 adds the TLB — a small hardware cache of recent translations. A TLB hit costs almost nothing; a miss requires walking the page table and installing the entry. Because programs reuse the same pages, spatial and temporal locality make hit rates high. Chapter 20 attacks the size of the page table itself with bigger pages, hybrid paging with segmentation, multi-level page tables that page the page table, and inverted page tables.

Key Points:

• A virtual address = virtual page number (VPN) + offset; the offset is not translated.
• With a 4KB page the offset is 12 bits, because 2 raised to 12 is 4096.
• The page table lives in physical memory; the page table base register tells the hardware where the current process’s table is.
• A page table entry holds the physical frame number plus valid, present, protection, dirty and reference bits.
• The TLB is a fully associative hardware cache of translations; it turns two memory accesses back into roughly one.
• Sequential access through an array gives a high TLB hit rate because many array elements share one page.
• A multi-level page table only allocates the parts of the table that are actually used, at the cost of an extra lookup on a TLB miss.

Memory Tip: Fix the page size arithmetic once and the rest is easy: offset bits = log2(page size), and the remaining address bits are the VPN. For a 32-bit address with 4KB pages that is 12 offset bits and 20 VPN bits, so a flat page table has one million entries per process.

Common Mistake: Translating the offset. Only the page number is looked up in the page table; the offset is carried across to the physical address unchanged.

Important Questions:

• Why does paging remove external fragmentation? Because all pages and frames are the same fixed size, so any free frame can hold any page and no unusable holes are created.
• What is a TLB and why is it needed? A small hardware cache of recent virtual-to-physical translations; without it every program memory reference would need an extra memory reference to read the page table.

Swapping: Mechanisms, Policies and Real Systems (Chapters 21–23)

Difficulty: Hard · Key topics: swap space, present bit, page fault, replacement policy, FIFO, LRU, clock algorithm, thrashing

These chapters let the address space be larger than physical memory. Part of the disk is reserved as swap space, and the present bit in a page table entry says whether the page is currently in memory. If it is not, the hardware raises a page fault, the OS page-fault handler finds the page in swap, reads it into a free frame, updates the entry and retries the instruction. Because memory is limited, the OS also needs a policy for which page to evict. The chapters compare the optimal policy (evict the page needed furthest in the future — not implementable, but the benchmark), FIFO, random, LRU and approximations of LRU using the reference bit and the clock algorithm, plus the dirty bit so clean pages are evicted more cheaply. Thrashing — when the working set exceeds memory and the system spends its time paging — is explained along with the swap daemon and high and low watermarks. Chapter 23 walks through VAX/VMS and Linux as complete real systems.

Key Points:

• Swap space is disk space reserved for pages that do not fit in physical memory.
• The present bit indicates whether a page is in memory; if it is clear, the hardware raises a page fault.
• Effective access time depends heavily on the hit rate, because a disk access is orders of magnitude slower than memory.
• The optimal policy evicts the page used furthest in the future; it cannot be implemented but sets the upper bound.
• LRU works well because of locality; the clock algorithm approximates it using the hardware reference bit.
• A dirty page must be written back before eviction, so clean pages are preferred victims.
• Thrashing occurs when the active working set exceeds physical memory and the system spends its time swapping.

Memory Tip: Do one page-replacement trace by hand for FIFO, LRU and optimal on the same reference string. Seeing FIFO evict a page that is needed on the very next reference is what makes Belady’s anomaly stick.

Common Mistake: Confusing a page fault with an error. A page fault is a normal, expected event that the OS handles by fetching the page; only an invalid access is an error.

Important Questions:

• What happens on a page fault? The hardware traps to the OS, the page-fault handler locates the page in swap space, reads it into a free frame, updates the page table entry and restarts the faulting instruction.
• What is thrashing? A state in which the processes’ combined working set exceeds physical memory, so the system spends almost all its time swapping pages in and out instead of doing useful work.

Concurrency and Threads (Chapters 26–27)

Difficulty: Medium · Key topics: thread, shared address space, race condition, critical section, mutual exclusion, atomicity, pthread API

The concurrency part opens by adding a second point of execution inside one process. Threads share the address space — code, heap and globals — but each has its own registers, program counter and stack, which is why a multi-threaded address space has several stacks in it. Context switching between threads uses a thread control block and does not require switching the page table. The chapter then demonstrates the central problem with a counter incremented by two threads: the single line counter = counter + 1 compiles into a load, an add and a store, and an untimely context switch between them loses an update. That is a race condition; the code region is a critical section, and the fix is mutual exclusion. Chapter 27 is the practical API: pthread_create, pthread_join, mutex lock and unlock, and condition variables with pthread_cond_wait and pthread_cond_signal.

Key Points:

• Threads in one process share code, heap and globals, but each has its own stack and registers.
• A race condition happens when the result depends on the timing of thread execution.
• A critical section is code that accesses a shared resource and must not be run by more than one thread at a time.
• counter = counter + 1 is three machine instructions, so it is not atomic.
• Mutual exclusion guarantees that only one thread is inside the critical section at a time.
• Always check the return value of every pthread call, and always pass pthread_cond_wait a locked mutex.

Practice Tip: Write the two-thread counter program yourself and run it with a large loop count. Watching the printed total come out different on each run — and never equal to the expected value — is the fastest possible proof that a race condition is real.

Common Mistake: Believing that a single line of C is atomic. Atomicity is a property of machine instructions, not of source lines.

Important Questions:

• What is the difference between a process and a thread? Processes have separate address spaces; threads live inside one process and share its address space, keeping only their own stack and registers.
• What is a race condition? A situation in which two or more threads access shared data at the same time and the final result depends on the order in which their instructions happen to interleave.

Locks and Locked Data Structures (Chapters 28–29)

Difficulty: Hard · Key topics: mutex, spin lock, test-and-set, compare-and-swap, fetch-and-add ticket lock, fairness, concurrent counters and lists

If mutual exclusion is the goal, the lock is the tool. The chapter states three criteria for evaluating any lock — correctness, fairness and performance — and then works up through implementations. Disabling interrupts works only on a single processor and is unsafe in user code. A simple flag variable fails because testing and setting the flag is itself a race. Real locks therefore need an atomic hardware instruction: test-and-set, compare-and-swap, load-linked and store-conditional, or fetch-and-add, which gives the ticket lock and with it fairness. Spinning wastes a whole time slice on a single CPU, so the chapter adds yield() and then sleeping queues, ending with two-phase locks that spin briefly before sleeping. Chapter 29 applies locks to data structures: a counter (and the scalable approximate counter with per-CPU local counters), a concurrent linked list, queue and hash table, showing that finer-grained locking is only worth the complexity if measurement proves it.

Key Points:

• A lock is evaluated on three things: correctness (mutual exclusion), fairness (no starvation) and performance (overhead).
• test-and-set atomically returns the old value and sets the new one, which is enough to build a spin lock.
• compare-and-swap updates a value only if it still equals the expected old value.
• The ticket lock uses fetch-and-add and guarantees every waiting thread eventually gets its turn.
• A spin lock wastes CPU while waiting; sleeping locks use a queue and a park/unpark mechanism instead.
• The approximate counter keeps a local counter per CPU and transfers to the global counter periodically, trading exactness for scalability.
• More concurrency is not automatically faster — measure before making the locking finer-grained.

Memory Tip: Tie each atomic instruction to the lock it enables: test-and-set gives the basic spin lock, compare-and-swap gives lock-free updates, and fetch-and-add gives the fair ticket lock. Three instructions, three consequences.

Common Mistake: Thinking a spin lock is simply bad. On a multiprocessor where the critical section is very short, spinning is cheaper than the cost of putting a thread to sleep and waking it up.

Important Questions:

• Why is an atomic instruction needed to build a lock? Because checking whether a lock is free and then acquiring it must happen as one indivisible step; otherwise two threads can both see it free and both enter the critical section.
• What advantage does a ticket lock have over a simple spin lock? Fairness — threads are served in the order they arrived, so no waiting thread can be starved indefinitely.

Condition Variables and Semaphores (Chapters 30–31)

Difficulty: Hard · Key topics: condition variable, wait and signal, producer-consumer, bounded buffer, semaphore, binary semaphore, reader-writer lock, dining philosophers

Locks solve mutual exclusion, but threads often need to wait for something to become true, and spinning on a condition is wasteful. A condition variable is a queue of threads waiting on a state change: wait() atomically releases the lock and sleeps, and signal() wakes one waiter. The chapter builds the producer-consumer problem step by step and derives two rules the hard way: always hold the lock while calling wait or signal, and always re-check the condition in a while loop rather than an if, because the state can change between the signal and the waiter running. The bounded-buffer solution then needs two condition variables, one for empty slots and one for full ones. Chapter 31 introduces the semaphore, a counter with atomic wait and post, shows a binary semaphore acting as a lock, solves producer-consumer, reader-writer locks and the dining philosophers, and finally implements semaphores using locks and condition variables.

Key Points:

• wait() atomically releases the mutex and puts the caller to sleep; on waking it re-acquires the mutex.
• Always hold the lock when calling wait or signal, and always wrap wait in a while loop, not an if.
• A semaphore initialised to 1 behaves exactly like a lock (a binary semaphore).
• In producer-consumer, the two condition variables (empty and full) must be separate or threads wake the wrong ones.
• A reader-writer lock allows many concurrent readers but only one writer, and can starve writers if readers keep arriving.
• The dining philosophers deadlock is broken by making one philosopher pick up the forks in the opposite order.

Memory Tip: For semaphore initial values, ask what the counter means: a lock means one thread may enter, so initialise to 1; ordering (parent waits for child) means nothing is available yet, so initialise to 0. Get the meaning first and the number follows.

Common Mistake: Using if instead of while when checking the condition after wait(). It works in a two-thread test and fails as soon as a third thread can consume the state in between.

Important Questions:

• Why must a condition be re-checked in a while loop after wait() returns? Because between the signal and the waiting thread actually running, another thread may have changed the state, so the condition that caused the signal may no longer hold.
• What is the difference between a mutex and a semaphore? A mutex enforces mutual exclusion for one thread at a time; a semaphore is a counter that can allow a set number of threads through and can also be used purely for ordering.

Concurrency Bugs and Event-based Concurrency (Chapters 32–33)

Difficulty: Medium · Key topics: atomicity-violation bug, order-violation bug, deadlock, the four conditions, deadlock prevention and avoidance, event loop, non-blocking I/O

This pair covers what goes wrong and one way to avoid the whole problem. A study of real software found that most concurrency bugs are non-deadlock bugs, and they fall into two groups: atomicity violations, where a sequence that should have been atomic was not, and order violations, where a required ordering between two threads was not enforced. Both are usually fixed with a lock or a condition variable. Deadlock gets its own treatment: it requires all four of mutual exclusion, hold-and-wait, no preemption and circular wait, and the practical fix is to remove one of them — total lock ordering being the most common. The chapter also covers livelock and the trylock-and-back-off approach. Chapter 33 presents event-based concurrency: a single thread runs an event loop over select() or poll() and handles each ready event, so there are no locks at all — but a blocking call stalls everything, and the code fragments into callbacks with manual state management.

Key Points:

• Non-deadlock bugs are more common than deadlocks; the two kinds are atomicity violations and order violations.
• All four conditions must hold for deadlock: mutual exclusion, hold-and-wait, no preemption and circular wait.
• Enforcing a total ordering on lock acquisition removes circular wait and is the most practical prevention.
• Livelock is different from deadlock: threads keep running but make no progress; random back-off helps.
• Event-based concurrency uses one thread and an event loop, so no locks are needed.
• Any blocking system call inside an event loop stalls the whole server — asynchronous I/O is required.
• Splitting logic across callbacks is called manual stack management, and it makes event-based code hard to read.

Memory Tip: The four deadlock conditions are easy to recall as a short story: a resource cannot be shared (mutual exclusion), you hold one while asking for another (hold-and-wait), nobody can take it from you (no preemption), and everyone is waiting in a circle (circular wait). Break any single link and deadlock cannot form.

Common Mistake: Listing only three conditions for deadlock in an exam. All four are required together, and the standard follow-up question asks which one your proposed fix removes.

Important Questions:

• What are the four conditions necessary for deadlock? Mutual exclusion, hold-and-wait, no preemption and circular wait — all four must hold at the same time.
• What is the main advantage of event-based concurrency? A single thread handles many connections through an event loop, so there are no locks and no race conditions between threads.

I/O Devices, Hard Disk Drives and RAID (Chapters 36–38)

Difficulty: Medium · Key topics: canonical device protocol, polling versus interrupts, DMA, device driver, seek and rotational delay, disk scheduling, RAID levels 0, 1, 4 and 5

The persistence part starts with hardware. A canonical device exposes status, command and data registers, and the OS drives it by polling until ready, writing the data, issuing the command and polling for completion — simple but wasteful. Interrupts let the OS run another process while the device works, though for very fast devices the cost of a context switch makes polling better. DMA removes the CPU from the data copying itself. Device drivers hide all of this behind a generic interface. Chapter 37 opens the disk: platters, tracks, sectors, seek time, rotational delay and transfer, which is why sequential access is far faster than random. Disk scheduling policies SSTF, elevator/SCAN and SPTF follow. Chapter 38 builds RAID over multiple disks and evaluates capacity, reliability and performance for striping (RAID-0), mirroring (RAID-1), parity (RAID-4) and rotated parity (RAID-5), including the small-write problem.

Key Points:

• A device is controlled through status, command and data registers, using either polling or interrupts.
• Interrupts are not always better than polling: for a fast device the context-switch cost dominates.
• DMA lets the device transfer data to memory directly; the CPU only sets it up and handles the completion interrupt.
• Disk I/O time = seek time + rotational delay + transfer time; seek and rotation dominate for random access.
• SSTF serves the nearest request first and can starve far requests; SCAN (the elevator) sweeps across the disk instead.
• RAID-0 striping gives capacity and speed but no redundancy; RAID-1 mirroring gives redundancy at half the capacity.
• RAID-4 uses a dedicated parity disk which becomes a bottleneck; RAID-5 rotates parity across all disks to fix it.

Memory Tip: Remember RAID by what each level costs: 0 costs reliability, 1 costs half your capacity, 4 costs you one bottleneck disk, and 5 fixes that bottleneck by spreading the parity around. Levels 0, 1 and 5 are the ones exams ask about most.

Common Mistake: Saying RAID-0 improves reliability. It has no redundancy at all — losing any one disk loses the whole array.

Important Questions:

• What are the components of hard disk access time? Seek time to move the head to the right track, rotational delay to wait for the sector to come under the head, and transfer time to read or write the data.
• What is the difference between RAID-4 and RAID-5? RAID-4 stores all parity on one dedicated disk, which becomes a write bottleneck; RAID-5 rotates the parity blocks across all disks so writes are spread evenly.

Files, Directories and File System Implementation (Chapters 39–40)

Difficulty: Hard · Key topics: file, directory, inode, file descriptor, hard link and symbolic link, superblock, bitmaps, multi-level index, mount

Chapter 39 gives the user’s view: a file is an array of bytes with a low-level name called an inode number, and a directory is simply a file whose contents are name-to-inode mappings, which is what builds the directory tree. The system call interface follows — open, read, write, lseek, close, fsync, rename, stat, unlink, mkdir, opendir and readdir — along with file descriptors, the open file table, hard links versus symbolic links, permission bits, and mounting a file system into the tree. Chapter 40 builds a very simple file system from the inside: the disk is divided into a superblock, an inode bitmap, a data bitmap, an inode table and a data region. An inode holds the file’s metadata and pointers to its data blocks, with indirect and double-indirect pointers forming a multi-level index for large files. The chapter then traces the exact reads and writes for opening, reading and writing a file, and explains caching and buffering.

Key Points:

• A file’s low-level name is its inode number; the human-readable name lives in a directory entry.
• A directory is a file whose data is a list of (name, inode number) pairs.
• The on-disk layout is superblock, inode bitmap, data bitmap, inode table, then the data region.
• An inode stores size, ownership, permissions, timestamps and pointers to data blocks — not the file’s name.
• Indirect pointers let a small inode address a large file; this is a multi-level index.
• unlink() removes a directory entry and decrements the link count; the file is deleted only when the count reaches zero.
• A hard link points to the same inode and cannot cross file systems; a symbolic link is a separate file containing a path.

Memory Tip: Keep the difference between the two links straight with one sentence: a hard link is another name for the same inode, a symbolic link is a file that stores a path. Delete the original and the hard link still works, while the symbolic link becomes dangling.

Common Mistake: Thinking the file name is stored in the inode. The name is stored only in the directory entry, which is exactly why one file can have several hard links.

Important Questions:

• What is an inode and what does it contain? The on-disk structure holding a file’s metadata — size, owner, permissions, timestamps and pointers to its data blocks — identified by an inode number rather than a name.
• What is the difference between a hard link and a symbolic link? A hard link is an extra directory entry pointing to the same inode; a symbolic link is a separate file whose contents are the path to another file, so it breaks if the target is removed.

Fast File System and Crash Consistency (Chapters 41–42)

Difficulty: Hard · Key topics: cylinder groups, locality heuristics, large-file exception, crash consistency, fsck, journaling, write-ahead logging, ordered journaling

The original UNIX file system reached only about two per cent of disk bandwidth because it ignored where things were placed. FFS fixed this by treating the disk as a set of cylinder groups, each with its own inode and data bitmaps, inodes and data blocks, and then applying one rule: keep related things together. Directories go into a group with few directories and many free inodes; a file’s data goes in the same group as its inode; files in the same directory go together. Large files are the exception and are deliberately spread in chunks so they do not fill one group. Chapter 42 tackles what happens when the power fails mid-update. fsck scans the whole file system after the fact and is unusably slow on large disks. Journaling instead writes what it intends to do into a log first, then performs the update — write-ahead logging — and after a crash simply replays the log. Data journaling logs the data too; ordered metadata journaling writes data first and logs only metadata, which is what Linux ext3 and ext4 do by default.

Key Points:

• FFS divides the disk into cylinder groups and places related files and their inodes in the same group.
• The large-file exception spreads big files across groups so one file cannot monopolise a single group.
• The crash-consistency problem: a single logical update touches several blocks and a crash can land between them.
• fsck scans and repairs the whole file system after a crash; it is correct but far too slow for large disks.
• Write-ahead logging writes the intended update to a journal before applying it to the file system.
• Journal recovery replays committed transactions and discards incomplete ones.
• Ordered metadata journaling writes data blocks first and journals only metadata, roughly halving the write traffic.

Memory Tip: Journaling is the same idea as writing your steps down before doing them. If the power fails you read your own note and either finish the job or ignore an unfinished note — that is exactly what “replay committed transactions, discard incomplete ones” means.

Common Mistake: Assuming journaling makes a crash lossless. It guarantees the file system stays consistent, not that every recent write survives — with ordered journaling, data written just before the crash can still be lost.

Important Questions:

• What problem does the Fast File System solve? Poor performance caused by ignoring disk geometry; FFS uses cylinder groups and locality heuristics to keep related data close together and reduce seeks.
• How does journaling ensure crash consistency? The file system writes the intended update to a log and commits it before updating the real structures, so after a crash it replays committed transactions and discards incomplete ones.

LFS, Flash-based SSDs and Data Integrity (Chapters 43–45)

Difficulty: Hard · Key topics: log-structured file system, segments, inode map, checkpoint region, garbage collection, flash pages and blocks, flash translation layer, wear levelling, checksums, silent corruption

The last storage chapters cover the modern designs. The log-structured file system buffers all updates in memory and writes them out sequentially as one large segment, which turns random writes into sequential ones and gets close to peak disk bandwidth. Because nothing is ever overwritten in place, inodes move, so LFS adds an inode map to find them and a checkpoint region at a fixed location to find the inode map. Old versions become garbage, and a cleaner reads partly used segments, keeps the live blocks and frees the rest. Recovery uses the checkpoint plus roll-forward. Chapter 44 shows why flash behaves the same way: a page can be programmed only after its whole block is erased, so the flash translation layer log-structures writes, maintains a mapping table, performs garbage collection and spreads writes through wear levelling. Chapter 45 covers data integrity — latent sector errors, silent block corruption, checksums, and the misdirected and lost write problems.

Key Points:

• LFS never overwrites in place: it buffers updates and writes full segments sequentially.
• The inode map maps inode numbers to their current disk locations; the checkpoint region points to the inode map.
• The cleaner compacts partly used segments and frees space, using segment summary information to identify live blocks.
• Flash is written in pages but erased in blocks, so a page cannot be overwritten without erasing its block.
• The flash translation layer log-structures writes and keeps a mapping table from logical to physical pages.
• Write amplification is the extra flash traffic caused by garbage collection; wear levelling spreads erases evenly.
• Checksums detect corruption but not misdirected or lost writes; physical identity and write verification handle those.

Memory Tip: Notice that LFS and the SSD’s flash translation layer are the same idea applied twice — never overwrite, always append, then clean up later. Learn LFS properly and the SSD chapter costs almost no extra effort.

Common Mistake: Thinking an SSD overwrites a page like a disk sector. It cannot: the block must be erased first, which is exactly why the FTL and garbage collection exist.

Important Questions:

• Why does a log-structured file system need a cleaner? Because old copies of blocks are left behind whenever data is rewritten, so the cleaner must reclaim that space by compacting live blocks into new segments.
• What is the flash translation layer? The SSD firmware layer that maps logical block addresses to physical flash pages, log-structures writes, and performs garbage collection and wear levelling.

Distributed Systems: NFS and AFS (Chapters 48–50)

Difficulty: Medium · Key topics: distributed systems, RPC, failure handling, stateless protocol, file handle, idempotent operations, client caching, flush-on-close, callbacks

The final systems chapters put the file system on a network. Chapter 48 covers the basics: communication is unreliable, so protocols need acknowledgements, timeouts and retries, and remote procedure call is presented as the standard abstraction along with its stubs and marshalling. Chapter 49 studies Sun’s NFSv2, whose central design goal was fast and simple server crash recovery. NFS achieves that by being stateless: the server keeps no client state, every request carries a file handle made of volume identifier, inode number and generation number, and most operations are idempotent so a client can simply retry after a timeout. Client-side caching then creates a consistency problem, which NFS handles with flush-on-close and attribute caching with a short timeout. Chapter 50 covers AFS, which caches whole files on the client’s local disk and uses server callbacks to notify clients when a file changes, giving stronger consistency and much better scale for large files.

Key Points:

• A stateless protocol keeps no per-client state on the server, which makes crash recovery simple.
• An NFS file handle contains a volume identifier, an inode number and a generation number.
• Idempotent operations can be safely repeated, so a client just retries when a reply is lost.
• NFS uses flush-on-close plus attribute caching with a timeout, so consistency is approximate, not exact.
• AFS caches whole files on the client’s local disk and uses callbacks so the server tells clients when a file changes.
• AFS scales better than NFS for large files because it avoids repeated block-by-block server traffic.

Memory Tip: Compare the two systems on one axis — who is responsible for noticing a change. In NFS the client keeps asking the server (attribute cache with a timeout); in AFS the server promises to tell the client (callback). Almost every difference between them follows from that one choice.

Common Mistake: Reading “stateless” as “nothing is remembered anywhere”. The client still keeps plenty of state; it is only the server that keeps none, and that is the whole point.

Important Questions:

• Why is the NFS protocol stateless? So that a server crash requires no recovery of client state — when the server restarts, clients simply retry their requests and continue.
• What is the cache consistency problem in NFS? Different clients may cache different versions of the same file; NFS reduces it with flush-on-close and by revalidating cached data with the server after a short timeout.

Security: Authentication, Access Control and Cryptography (Chapters 53–57)

Difficulty: Medium · Key topics: confidentiality, integrity, availability, principle of least privilege, authentication, passwords, access control lists, capabilities, symmetric and public key cryptography, hashes, signatures

The security part asks what the OS must protect and how. The goals are confidentiality, integrity and availability, and the guiding rule is the principle of least privilege: give every user and process only the permissions it actually needs. The OS is trusted with everything, so its own mechanisms — system calls, virtual memory and the mode bit — are the enforcement points, and policy has to be configured deliberately rather than assumed from defaults. Authentication covers passwords, hashed and salted password files, multi-factor authentication and biometrics. Access control compares access control lists, which store permissions with the object, against capabilities, which store them with the subject, and explains UNIX permission bits and setuid. The cryptography chapter separates symmetric ciphers from public key cryptography, adds cryptographic hashes and digital signatures, and shows how the OS uses them for full-disk encryption and secure network communication, while noting that no encryption protects you from an OS that already holds the key.

Key Points:

• The three security goals are confidentiality, integrity and availability.
• The principle of least privilege limits the damage from both attacks and honest mistakes.
• Password files store salted hashes, never the passwords themselves; the salt defeats precomputed tables.
• An access control list stores permissions with the object; a capability stores them with the subject.
• Symmetric cryptography uses one shared key; public key cryptography uses a public and a private key pair.
• A cryptographic hash is one-way and detects tampering; a digital signature proves origin and integrity.
• Encryption protects data at rest and in transit, but not from an operating system that holds the key in memory.

Memory Tip: Remember the three goals as the CIA triad — confidentiality, integrity, availability — and remember that the OS is trusted with all three. Almost every exam question in this part is really asking which of the three is being violated.

Common Mistake: Believing a strong algorithm is enough. Nearly every real-world failure is key management or a weak policy, not a broken cipher.

Important Questions:

• What is the principle of least privilege? Every user, process and program should be given only the minimum permissions needed to do its job, so that a compromise or a mistake causes the least possible damage.
• What is the difference between an access control list and a capability? An ACL is attached to the object and lists who may use it; a capability is held by the subject and is an unforgeable token granting access to a particular object.

---

Download Operating Systems: Three Easy Pieces PDF (Free)

This book is free from its official source at the University of Wisconsin–Madison. You can download the complete book as a single PDF or take any chapter on its own. Click below to open the official page.

↓ Download PDF

---

How to Study This Book

Start with Chapter 2, then read the CPU part in order: Processes and the Process API (Chapters 4–6) followed by CPU Scheduling (Chapters 7–10). These are the chapters that appear in every mid-term paper and they are the easiest marks in the course, especially the scheduling numericals.

Memory is the part students lose marks on, so give it the most time. Read address spaces and translation (Chapters 13–17) before paging (Chapters 18–20); paging will not make sense until segmentation and its fragmentation problem are clear. Swapping and page replacement (Chapters 21–23) usually finish the mid-term syllabus.

After the mid-term, concurrency is the highest-value part: threads (Chapters 26–27), locks (Chapters 28–29), condition variables and semaphores (Chapters 30–31) and concurrency bugs (Chapters 32–33). Do not read these passively — write the small pthread programs, because concurrency questions in the final are usually “what output is possible and why”.

Persistence comes last: I/O and disks (Chapters 36–38), then files and file system implementation (Chapters 39–40), then FFS and journaling (Chapters 41–42). The inode and directory chapters carry the most marks in this part.

Read the modern storage chapters (Chapters 43–45), distributed file systems (Chapters 48–50) and security (Chapters 53–57) according to your own course outline — many Pakistani universities cover only some of them, and LFS makes the SSD chapter almost free once you have read it.

The nine Dialogue chapters are short conversations, not extra syllabus. Read them for intuition when a topic feels abstract, and skip them when you are revising.

Finally, use the free homework simulators from the official page. Running the scheduling and paging simulators and checking your own hand-worked answers is the fastest way to prepare for numerical questions.

---

Used In These Programs

This book is part of the Operating Systems course in: BS Computer Science · BS Information Technology · BS Software Engineering. Browse all Operating Systems books or all Computer Science books.

Who Should Read This

This book is written for undergraduate students taking their first Operating Systems course, usually in the fourth or fifth semester of BSCS, BSIT or BSSE. It assumes you can read C and have covered basic data structures, but it does not assume any prior systems knowledge. Students who prefer worked examples and clear explanations over dense formal text will find it easier than most standard textbooks, and the free simulators make it a strong choice for self-study. It is also useful for anyone preparing for technical interviews or competitive exams, since the scheduling, paging, concurrency and file system chapters cover exactly the topics those tests draw from. If you have not written much C yet, or you want the intuition before the formal treatment, read Think OS first — it is far shorter, every concept comes with runnable C code, and it prepares you for the memory and concurrency chapters here.

---

Applicable Universities

This book is widely used at Pakistani universities offering BSCS, BSIT and BSSE including Punjab University, Virtual University, COMSATS, FAST, UET, NUST, and other HEC-recognized institutions.

FAQs

Related Books

• Think OS – Allen B. Downey (Version 0.7.4)
• Operating Systems and Networks – IT Series BSCS
• Database Management System – BSCS University
• Object Oriented Programming Using C++ – IT Series BSCS

Operating Systems: Three Easy Pieces is one of the few free textbooks that a university can adopt without compromise. Its three-part structure, short chapters and honest explanations make a difficult subject approachable, and the free simulators and lab projects turn it into a complete course. Browse more Computer Science books for the rest of your semester.

Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau, Arpaci-Dusseau Books. The authors make the book free in PDF form; all rights remain with the authors. Official source: https://pages.cs.wisc.edu/~remzi/OSTEP/