Operating Systems: Three Easy Pieces

Description

OSTEP ("oh step"), or the "the comet book", represents the culmination of years of teaching intro to operating systems to both undergraduates and graduates at the University of Wisconsin-Madison Computer Sciences department for nearly 20 years.The book is organized around three concepts fundamental to OS construction: virtualization (of CPU and memory), concurrency (locks and condition variables), and persistence (disks, RAIDS, and file systems).The material, if combined with serious project work and homeworks, will lead students to a deeper understanding and appreciation of modern OSes.The authors, Remzi and Andrea Arpaci-Dusseau, are both professors of Computer Sciences at the University of Wisconsin-Madison. They have been doing research in computer systems for over 20 years, working together since their first graduate operating systems class at U.C. Berkeley in 1993.Since that time, they have published over 100 papers on the performance and reliability of many aspects of modern computer systems, with a special focus on file and storage systems. Their work has been recognized with numerous best-paper awards, and some of their innovations can be found in the Linux and BSD operating systems today. 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