O perating s ystems t hree e asy p ieces

Document Outline

• 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
• 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
  • Interlude: Process API
    • The fork() System Call
    • Adding wait() System Call
    • Finally, the exec() System Call
    • Why? Motivating the API
    • Other Parts of the API
    • Summary
    • References
  • 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)
    • Round Robin
    • Incorporating I/O
    • No More Oracle
    • Summary
    • References
    • Homework
  • 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
  • Scheduling: Proportional Share
    • Basic Concept: Tickets Represent Your Share
    • Ticket Mechanisms
    • Implementation
    • An Example
    • How To Assign Tickets?
    • Why Not Deterministic?
    • Summary
    • References
    • Homework
  • 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
  • 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
  • Interlude: Memory API
    • Types of Memory
    • The malloc() Call
    • The free() Call
    • Common Errors
    • Underlying OS Support
    • Other Calls
    • Summary
    • References
  • Mechanism: Address Translation
    • Assumptions
    • An Example
    • Dynamic (Hardware-based) Relocation
    • OS Issues
    • Summary
    • References
    • Homework
  • 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
  • Free-Space Management
    • Assumptions
    • Low-level Mechanisms
    • Basic Strategies
    • Other Approaches
    • Summary
    • References
  • Paging: Introduction
    • Where Are Page Tables Stored?
    • What's Actually In The Page Table?
    • Paging: Also Too Slow
    • A Memory Trace
    • Summary
    • References
    • Homework
  • 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
  • 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
  • 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
  • The VAX/VMS Virtual Memory System
    • Background
    • Memory Management Hardware
    • A Real Address Space
    • Page Replacement
    • Other Neat VM Tricks
    • Summary
    • References
  • Summary Dialogue on Memory Virtualization
• Concurrency
  • A Dialogue on Concurrency
  • Concurrency: An Introduction
    • 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
  • Interlude: Thread API
    • Thread Creation
    • Thread Completion
    • Locks
    • Condition Variables
    • Compiling and Running
    • Summary
    • References
  • Locks
    • Locks: The Basic Idea
    • Pthread Locks
    • Building A Lock
    • Evaluating Locks
    • Controlling Interrupts
    • Test And Set (Atomic Exchange)
    • Building A Working Spin Lock
    • Evaluating Spin Locks
    • Compare-And-Swap
    • Load-Linked and Store-Conditional
    • Fetch-And-Add
    • Summary: So Much Spinning
    • A Simple Approach: Just Yield, Baby
    • Using Queues: Sleeping Instead Of Spinning
    • Different OS, Different Support
    • Two-Phase Locks
    • Summary
    • References
  • Lock-based Concurrent Data Structures
    • Concurrent Counters
    • Concurrent Linked Lists
    • Concurrent Queues
    • Concurrent Hash Table
    • Summary
    • References
  • Condition Variables
    • Definition and Routines
    • The Producer/Consumer (Bound Buffer) Problem
    • Covering Conditions
    • Summary
    • References
  • Semaphores
    • Semaphores: A Definition
    • Binary Semaphores (Locks)
    • Semaphores As Condition Variables
    • The Producer/Consumer (Bounded-Buffer) Problem
    • Reader-Writer Locks
    • The Dining Philosophers
    • How To Implement Semaphores
    • Summary
    • References
  • Common Concurrency Problems
    • What Types Of Bugs Exist?
    • Non-Deadlock Bugs
    • Deadlock Bugs
    • Summary
    • References
  • 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
  • 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
  • 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
  • Interlude: File and Directories
    • Files and Directories
    • The File System Interface
    • Creating Files
    • Reading and Writing Files
    • Reading And Writing, But Not Sequentially
    • Writing Immediately with fsync()
    • Renaming Files
    • Getting Information About Files
    • Removing Files
    • Making Directories
    • Reading Directories
    • Deleting Directories
    • Hard Links
    • Symbolic Links
    • Making and Mounting a File System
    • Summary
    • References
    • Homework
  • 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
  • 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
  • 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
  • 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
    • 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
  • 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
  • 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
  • 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
  • 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
  • Summary Dialogue on Distribution
  • General Index
  • Asides
  • Tips
  • Cruces