Operating Systems: Three Easy Pieces

To Everyone
To Educators
To Students
Acknowledgments
Final Words
References
A Dialogue on the Book
Introduction to Operating Systems
	Virtualizing The CPU
	Virtualizing Memory
	Concurrency
	Persistence
	Design Goals
	Some History
	Summary
	References
	Homework
Virtualization
	A Dialogue on Virtualization
	The Abstraction: The Process
		The Abstraction: A Process
		Process API
		Process Creation: A Little More Detail
		Process States
		Data Structures
		Summary
		References
		Homework (Simulation)
	Interlude: Process API
		The fork() System Call
		The wait() System Call
		Finally, The exec() System Call
		Why? Motivating The API
		Process Control And Users
		Useful Tools
		Summary
		References
		Homework (Code)
	Mechanism: Limited Direct Execution
		Basic Technique: Limited Direct Execution
		Problem #1: Restricted Operations
		Problem #2: Switching Between Processes
		Worried About Concurrency?
		Summary
		References
		Homework (Measurement)
	Scheduling: Introduction
		Workload Assumptions
		Scheduling Metrics
		First In, First Out (FIFO)
		Shortest Job First (SJF)
		Shortest Time-to-Completion First (STCF)
		A New Metric: Response Time
		Round Robin
		Incorporating I/O
		No More Oracle
		Summary
		References
		Homework (Simulation)
	Scheduling:  The Multi-Level Feedback Queue
		MLFQ: Basic Rules
		Attempt #1: How To Change Priority
		Attempt #2: The Priority Boost
		Attempt #3: Better Accounting
		Tuning MLFQ And Other Issues
		MLFQ: Summary
		References
		Homework (Simulation)
	Scheduling: Proportional Share
		Basic Concept: Tickets Represent Your Share
		Ticket Mechanisms
		Implementation
		An Example
		How To Assign Tickets?
		Why Not Deterministic?
		The Linux Completely Fair Scheduler (CFS)
		Summary
		References
		Homework (Simulation)
	Multiprocessor Scheduling (Advanced)
		Background: Multiprocessor Architecture
		Don't Forget Synchronization
		One Final Issue: Cache Affinity
		Single-Queue Scheduling
		Multi-Queue Scheduling
		Linux Multiprocessor Schedulers
		Summary
		References
		Homework (Simulation)
	Summary Dialogue on CPU Virtualization
	A Dialogue on Memory Virtualization
	The Abstraction: Address Spaces
		Early Systems
		Multiprogramming and Time Sharing
		The Address Space
		Goals
		Summary
		References
		Homework (Code)
	Interlude: Memory API
		Types of Memory
		The malloc() Call
		The free() Call
		Common Errors
		Underlying OS Support
		Other Calls
		Summary
		References
		Homework (Code)
	Mechanism: Address Translation
		Assumptions
		An Example
		Dynamic (Hardware-based) Relocation
		Hardware Support: A Summary
		Operating System Issues
		Summary
		References
		Homework (Simulation)
	Segmentation
		Segmentation: Generalized Base/Bounds
		Which Segment Are We Referring To?
		What About The Stack?
		Support for Sharing
		Fine-grained vs. Coarse-grained Segmentation
		OS Support
		Summary
		References
		Homework (Simulation)
	Free-Space Management
		Assumptions
		Low-level Mechanisms
		Basic Strategies
		Other Approaches
		Summary
		References
		Homework (Simulation)
	Paging: Introduction
		A Simple Example And Overview
		Where Are Page Tables Stored?
		What's Actually In The Page Table?
		Paging: Also Too Slow
		A Memory Trace
		Summary
		References
		Homework (Simulation)
	Paging: Faster Translations (TLBs)
		TLB Basic Algorithm
		Example: Accessing An Array
		Who Handles The TLB Miss?
		TLB Contents: What's In There?
		TLB Issue: Context Switches
		Issue: Replacement Policy
		A Real TLB Entry
		Summary
		References
		Homework (Measurement)
	Paging: Smaller Tables
		Simple Solution: Bigger Pages
		Hybrid Approach: Paging and Segments
		Multi-level Page Tables
		Inverted Page Tables
		Swapping the Page Tables to Disk
		Summary
		References
		Homework (Simulation)
	Beyond Physical Memory: Mechanisms
		Swap Space
		The Present Bit
		The Page Fault
		What If Memory Is Full?
		Page Fault Control Flow
		When Replacements Really Occur
		Summary
		References
		Homework (Measurement)
	Beyond Physical Memory: Policies
		Cache Management
		The Optimal Replacement Policy
		A Simple Policy: FIFO
		Another Simple Policy: Random
		Using History: LRU
		Workload Examples
		Implementing Historical Algorithms
		Approximating LRU
		Considering Dirty Pages
		Other VM Policies
		Thrashing
		Summary
		References
		Homework (Simulation)
	Complete Virtual Memory Systems
		VAX/VMS Virtual Memory
		The Linux Virtual Memory System
		Summary
		References
	Summary Dialogue on Memory Virtualization
Concurrency
	A Dialogue on Concurrency
	Concurrency: An Introduction
		Why Use Threads?
		An Example: Thread Creation
		Why It Gets Worse: Shared Data
		The Heart Of The Problem: Uncontrolled Scheduling
		The Wish For Atomicity
		One More Problem: Waiting For Another
		Summary: Why in OS Class?
		References
		Homework (Simulation)
	Interlude: Thread API
		Thread Creation
		Thread Completion
		Locks
		Condition Variables
		Compiling and Running
		Summary
		References
		Homework (Code)
	Locks
		Locks: The Basic Idea
		Pthread Locks
		Building A Lock
		Evaluating Locks
		Controlling Interrupts
		A Failed Attempt: Just Using Loads/Stores
		Building Working Spin Locks with Test-And-Set
		Evaluating Spin Locks
		Compare-And-Swap
		Load-Linked and Store-Conditional
		Fetch-And-Add
		Too Much Spinning: What Now?
		A Simple Approach: Just Yield, Baby
		Using Queues: Sleeping Instead Of Spinning
		Different OS, Different Support
		Two-Phase Locks
		Summary
		References
		Homework (Simulation)
	Lock-based Concurrent Data Structures
		Concurrent Counters
		Concurrent Linked Lists
		Concurrent Queues
		Concurrent Hash Table
		Summary
		References
		Homework (Code)
	Condition Variables
		Definition and Routines
		The Producer/Consumer (Bounded Buffer) Problem
		Covering Conditions
		Summary
		References
		Homework (Code)
	Semaphores
		Semaphores: A Definition
		Binary Semaphores (Locks)
		Semaphores For Ordering
		The Producer/Consumer (Bounded Buffer) Problem
		Reader-Writer Locks
		The Dining Philosophers
		Thread Throttling
		How To Implement Semaphores
		Summary
		References
		Homework (Code)
	Common Concurrency Problems
		What Types Of Bugs Exist?
		Non-Deadlock Bugs
		Deadlock Bugs
		Summary
		References
		Homework (Code)
	Event-based Concurrency (Advanced)
		The Basic Idea: An Event Loop
		An Important API: select() (or poll())
		Using select()
		Why Simpler? No Locks Needed
		A Problem: Blocking System Calls
		A Solution: Asynchronous I/O
		Another Problem: State Management
		What Is Still Difficult With Events
		Summary
		References
		Homework (Code)
	Summary Dialogue on Concurrency
Persistence
	A Dialogue on Persistence
	I/O Devices
		System Architecture
		A Canonical Device
		The Canonical Protocol
		Lowering CPU Overhead With Interrupts
		More Efficient Data Movement With DMA
		Methods Of Device Interaction
		Fitting Into The OS: The Device Driver
		Case Study: A Simple IDE Disk Driver
		Historical Notes
		Summary
		References
	Hard Disk Drives
		The Interface
		Basic Geometry
		A Simple Disk Drive
		I/O Time: Doing The Math
		Disk Scheduling
		Summary
		References
		Homework (Simulation)
	Redundant Arrays of Inexpensive Disks (RAIDs)
		Interface And RAID Internals
		Fault Model
		How To Evaluate A RAID
		RAID Level 0: Striping
		RAID Level 1: Mirroring
		RAID Level 4: Saving Space With Parity
		RAID Level 5: Rotating Parity
		RAID Comparison: A Summary
		Other Interesting RAID Issues
		Summary
		References
		Homework (Simulation)
	Interlude: Files and Directories
		Files And Directories
		The File System Interface
		Creating Files
		Reading And Writing Files
		Reading And Writing, But Not Sequentially
		Shared File Table Entries: fork() And dup()
		Writing Immediately With fsync()
		Renaming Files
		Getting Information About Files
		Removing Files
		Making Directories
		Reading Directories
		Deleting Directories
		Hard Links
		Symbolic Links
		Permission Bits And Access Control Lists
		Making And Mounting A File System
		Summary
		References
		Homework (Code)
	File System Implementation
		The Way To Think
		Overall Organization
		File Organization: The Inode
		Directory Organization
		Free Space Management
		Access Paths: Reading and Writing
		Caching and Buffering
		Summary
		References
		Homework (Simulation)
	Locality and The Fast File System
		The Problem: Poor Performance
		FFS: Disk Awareness Is The Solution
		Organizing Structure: The Cylinder Group
		Policies: How To Allocate Files and Directories
		Measuring File Locality
		The Large-File Exception
		A Few Other Things About FFS
		Summary
		References
		Homework (Simulation)
	Crash Consistency: FSCK and Journaling
		A Detailed Example
		Solution #1: The File System Checker
		Solution #2: Journaling (or Write-Ahead Logging)
		Solution #3: Other Approaches
		Summary
		References
		Homework (Simulation)
	Log-structured File Systems
		Writing To Disk Sequentially
		Writing Sequentially And Effectively
		How Much To Buffer?
		Problem: Finding Inodes
		Solution Through Indirection: The Inode Map
		Completing The Solution: The Checkpoint Region
		Reading A File From Disk: A Recap
		What About Directories?
		A New Problem: Garbage Collection
		Determining Block Liveness
		A Policy Question: Which Blocks To Clean, And When?
		Crash Recovery And The Log
		Summary
		References
		Homework (Simulation)
	Flash-based SSDs
		Storing a Single Bit
		From Bits to Banks/Planes
		Basic Flash Operations
		Flash Performance And Reliability
		From Raw Flash to Flash-Based SSDs
		FTL Organization: A Bad Approach
		A Log-Structured FTL
		Garbage Collection
		Mapping Table Size
		Wear Leveling
		SSD Performance And Cost
		Summary
		References
		Homework (Simulation)
	Data Integrity and Protection
		Disk Failure Modes
		Handling Latent Sector Errors
		Detecting Corruption: The Checksum
		Using Checksums
		A New Problem: Misdirected Writes
		One Last Problem: Lost Writes
		Scrubbing
		Overheads Of Checksumming
		Summary
		References
		Homework (Simulation)
		Homework (Code)
	Summary Dialogue on Persistence
	A Dialogue on Distribution
	Distributed Systems
		Communication Basics
		Unreliable Communication Layers
		Reliable Communication Layers
		Communication Abstractions
		Remote Procedure Call (RPC)
		Summary
		References
		Homework (Code)
	Sun's Network File System (NFS)
		A Basic Distributed File System
		On To NFS
		Focus: Simple And Fast Server Crash Recovery
		Key To Fast Crash Recovery: Statelessness
		The NFSv2 Protocol
		From Protocol To Distributed File System
		Handling Server Failure With Idempotent Operations
		Improving Performance: Client-side Caching
		The Cache Consistency Problem
		Assessing NFS Cache Consistency
		Implications On Server-Side Write Buffering
		Summary
		References
		Homework (Measurement)
	The Andrew File System (AFS)
		AFS Version 1
		Problems with Version 1
		Improving the Protocol
		AFS Version 2
		Cache Consistency
		Crash Recovery
		Scale And Performance Of AFSv2
		AFS: Other Improvements
		Summary
		References
		Homework (Simulation)
	Summary Dialogue on Distribution
	General Index
	Asides
	Tips
	Cruces