Operating Systems - Three Easy Pieces (Deprecated)

1 A Dialogue on the Book
2 Introduction to Operating Systems
	2.1 Virtualizing The CPU
	2.2 Virtualizing Memory
	2.3 Concurrency
	2.4 Persistence
	2.5 Design Goals
	2.6 Some History
	2.7 Summary
3 A Dialogue on Virtualization
4 The Abstraction: The Process
	4.1 The Abstraction: A Process
	4.2 Process API
	4.3 Process Creation: A Little More Detail
	4.4 Process States
	4.5 Data Structures
	4.6 Summary
	Homework (Simulation)
5 Interlude: Process API
	5.1 The fork() System Call
	5.2 The wait() System Call
	5.3 Finally, The exec() System Call
	5.4 Why? Motivating The API
	5.5 Process Control And Users
	5.6 Useful Tools
	5.7 Summary
6 Mechanism: Limited Direct Execution
	6.1 Basic Technique: Limited Direct Execution
	6.2 Problem #1: Restricted Operations
	6.3 Problem #2: Switching Between Processes
	6.4 Worried About Concurrency?
	6.5 Summary
7 Scheduling: Introduction
	7.1 Workload Assumptions
	7.2 Scheduling Metrics
	7.3 First In, First Out (FIFO)
	7.4 Shortest Job First (SJF)
	7.5 Shortest Time-to-Completion First (STCF)
	7.6 A New Metric: Response Time
	7.7 Round Robin
	7.8 Incorporating I/O
	7.9 No More Oracle
	7.10 Summary
8 Scheduling: The Multi-Level Feedback Queue
	8.1 MLFQ: Basic Rules
	8.2 Attempt #1: How To Change Priority
	8.3 Attempt #2: The Priority Boost
	8.4 Attempt #3: Better Accounting
	8.5 Tuning MLFQ And Other Issues
	8.6 MLFQ: Summary
9 Scheduling: Proportional Share
	9.1 Basic Concept: Tickets Represent Your Share
	9.2 Ticket Mechanisms
	9.3 Implementation
	9.4 An Example
	9.5 How To Assign Tickets?
	9.6 Stride Scheduling
	9.7 The Linux Completely Fair Scheduler (CFS)
	9.8 Summary
10 Multiprocessor Scheduling (Advanced)
	10.1 Background: Multiprocessor Architecture
	10.2 Don’t Forget synchronization
	10.3 One Final issue: cache Affinity
	10.4 Single-Queue Scheduling
	10.5 Multi-Queue scheduling
	10.6 Linux Multiprocessor schedulers
	10.7 summary
11 Summary Dialogue on CPU Virtualization
12 A Dialogue on Memory Virtualization
13 The Abstraction: Address Spaces
	13.1 Early Systems
	13.2 Multiprogramming and Time Sharing
	13.3 The Address Space
	13.4 Goals
	13.5 Summary
14 Interlude: Memory API
	14.1 Types of Memory
	14.2 The malloc() Call
	14.3 The free() Call
	14.4 Common Errors
	14.5 Underlying OS Support
	14.6 Other Calls
	14.7 Summary
15 Mechanism: Address Translation
	15.1 Assumptions
	15.2 An Example
	15.3 Dynamic (Hardware-based) Relocation
	15.4 Hardware Support: A Summary
	15.5 Operating System Issues
	15.6 Summary
16 Segmentation
	16.1 Segmentation: Generalized Base/Bounds
	16.2 Which Segment Are We Referring To?
	16.3 What About The Stack?
	16.4 Support for Sharing
	16.5 Fine-grained vs.Coarse-grained Segmentation
	16.6 OS Support
	16.7 Summary
17 Free-Space Management
	17.1 Assumptions
	17.2 Low-level Mechanisms
	17.3 Basic Strategies
	17.4 Other Approaches
	17.5 Summary
18 Paging: Introduction
	18.1 A Simple Example And Overview
	18.2 Where Are Page Tables Stored?
	18.3 What’s Actually In The Page Table?
	18.4 Paging: Also Too Slow
	18.6 Summary
19 Paging: Faster Translations (TLBs)
	19.1 TLB Basic Algorithm
	19.2 Example: Accessing An Array
	19.3 Who Handles The TLB Miss?
	19.4 TLB Contents: What’s in There?
	19.5 TLB issue: Context switches
	19.6 issue: Replacement Policy
	19.7 A Real TLB Entry
	19.8 summary
20 Paging: Smaller Tables
	20.1 Simple Solution: Bigger Pages
	20.2 Hybrid Approach: Paging and Segments
	20.3 Multi-level Page Tables
	20.4 Inverted Page Tables
	20.5 Swapping the Page Tables to Disk
	20.6 Summary
21 Beyond Physical Memory: Mechanisms
	21.1 Swap Space
	21.2 The Present Bit
	21.3 The Page Fault
	21.4 What If Memory Is Full?
	21.5 Page Fault Control Flow
	21.6 When Replacements Really Occur
	21.7 Summary
22 Beyond Physical Memory: Policies
	22.1 Cache Management
	22.2 The Optimal Replacement Policy
	22.3 A Simple Policy: FIFO
	22.4 Another Simple Policy: Random
	22.5 Using History: LRU
	22.6 Workload Examples
	22.7 Implementing Historical Algorithms
	22.8 Approximating LRU
	22.9 Considering Dirty Pages
	22.10 Other VM Policies
	22.11 Thrashing
	22.12 Summary
23 Complete Virtual Memory Systems
	23.1 VAX/VMS Virtual Memory
	23.2 The Linux Virtual Memory System
	23.3 Summary
24 Summary Dialogue on Memory Virtualization
25 A Dialogue on Concurrency
26 Concurrency: An Introduction
	26.1 Why Use Threads?
	26.2 An Example: Thread Creation
	26.3 Why It Gets Worse: Shared Data
	26.4 The Heart Of The Problem: Uncontrolled Scheduling
	26.5 The Wish For Atomicity
	26.6 One More Problem: Waiting For Another
	26.7 Summary: Why in OS Class?
	Homework (Simulation)
27 Interlude: Thread API
	27.1 Thread Creation
	27.2 Thread Completion
	27.3 Locks
	27.4 Condition Variables
	27.5 Compiling and Running
	27.6 Summary
28 Locks
	28.1 Locks: The Basic Idea
	28.2 Pthread Locks
	28.3 Building A Lock
	28.4 Evaluating Locks
	28.5 Controlling Interrupts
	28.6 A Failed Attempt: Just Using Loads/Stores
	28.7 Building Working Spin Locks with Test-And-Set
	28.8 Evaluating Spin Locks
	28.9 Compare-And-Swap
	28.10 Load-Linked and Store-Conditional
	28.11 Fetch-And-Add
	28.12 Too Much Spinning: What Now?
	28.13 A Simple Approach: Just Yield, Baby
	28.14 Using Queues: Sleeping Instead Of Spinning
	28.15 Different OS, Different Support
	28.16 Two-Phase Locks
	28.17 Summary
29 Lock-based Concurrent Data Structures
	29.1 Concurrent Counters
	29.2 Concurrent Linked Lists
	29.3 Concurrent Queues
	Concurrent Hash Table
	Summary
30 Condition Variables
	30.1 Definition and Routines
	30.3 Covering Conditions
	30.4 Summary
31 Semaphores
	31.1 Semaphores: A Definition
	31.2 Binary Semaphores (Locks)
	31.3 Semaphores For Ordering
	31.4 The Producer/Consumer (Bounded Buffer) Problem
	31.5 Reader-Writer Locks
	31.6 The Dining Philosophers
	31.7 Thread Throttling
	31.8 How To Implement Semaphores
32 Common Concurrency Problems
	32.1 What Types Of Bugs Exist?
	32.2 Non-Deadlock Bugs
	32.3 Deadlock Bugs
	32.4 Summary
33 Event-based Concurrency (Advanced)
	33.1 The Basic Idea: An Event Loop
	33.2 An Important API: select() (or poll())
	33.3 Using select()
	33.4 Why Simpler? No Locks Needed
	33.5 A Problem: Blocking System calls
	33.6 A Solution: Asynchronous I/O
	33.7 Another Problem: State Management
	33.8 What Is Still Difficult With Events
	33.9 Summary
34 Summary Dialogue on Concurrency
35 A Dialogue on Persistence
36 I/O Devices
	36.1 System Architecture
	36.2 A Canonical Device
	36.3 The Canonical Protocol
	36.4 Lowering CPU Overhead With Interrupts
	36.5 More Efficient Data Movement With DMA
	36.6 Methods Of Device Interaction
	36.7 Fitting Into The OS: The Device Driver
	36.8 Case Study: A Simple IDE Disk Driver
	36.9 Historical Notes
	36.10 Summary
37 Hard Disk Drives
	37.1 The Interface
	37.2 Basic Geometry
	37.3 A Simple Disk Drive
	37.4 I/O Time: Doing The Math
	37.5 Disk Scheduling
	37.6 Summary
38 Redundant Arrays of Inexpensive Disks (RAIDs)
	38.1 Interface And RAID Internals
	38.2 Fault Model
	38.3 How To Evaluate A RAID
	38.4 RAID Level 0: striping
	38.5 RAID Level 1: Mirroring
	38.6 RAID Level 4: saving space With Parity
	38.7 RAID Level 5: Rotating Parity
	38.8 RAID Comparison: A summary
	38.9 Other Interesting RAID Issues
	38.10 summary
39 Interlude: Files and Directories
	39.1 Files And Directories
	39.2 The File System Interface
	39.3 Creating Files
	39.4 Reading And Writing Files
	39.5 Reading And Writing, But Not Sequentially
	39.6 Shared File Table Entries: fork() And dup()
	39.7 Writing Immediately With fsync()
	39.8 Renaming Files
	39.9 Getting Information About Files
	39.10 Removing Files
	39.11 Making Directories
	39.12 Reading Directories
	39.13 Deleting Directories
	39.14 Hard Links
	39.15 Symbolic Links
	39.16 Permission Bits And Access Control Lists
	39.17 Making And Mounting A File System
	39.18 Summary
40 File System Implementation
	40.1 The Way To Think
	40.2 Overall Organization
	40.3 File Organization: The Inode
	40.4 Directory Organization
	40.5 Free Space Management
	40.6 Access Paths: Reading and Writing
	40.7 Caching and Buffering
	40.8 Summary
41 Locality and The Fast File System
	41.1 The Problem: Poor Performance
	41.2 FFS: Disk Awareness Is The Solution
	41.3 Organizing Structure: The Cylinder Group
	41.4 Policies: How To Allocate Files and Directories
	41.5 Measuring File Locality
	41.6 The Large-File Exception
	41.7 A Few Other Things About FFS
	41.8 Summary
42 Crash Consistency: FSCK and Journaling
	42.1 A Detailed Example
	42.2 Solution #1: The File System Checker
	42.3 Solution #2: Journaling (or Write-Ahead Logging)
	42.4 Solution #3: Other Approaches
	42.5 Summary
43 Log-structured File Systems
	43.1 Writing To Disk Sequentially
	43.2 Writing Sequentially And Effectively
	43.3 How Much To Buffer?
	43.4 Problem: Finding Inodes
	43.5 Solution Through Indirection: The Inode Map
	43.6 Completing The Solution: The Checkpoint Region
	43.7 Reading A File From Disk: A Recap
	43.8 What About Directories?
	43.9 A New Problem: Garbage Collection
	43.10 Determining Block Liveness
	43.11 A Policy Question: Which Blocks To Clean, And When?
	43.12 Crash Recovery And The Log
	43.13 Summary
44 Flash-based SSDs
	44.1 Storing a Single Bit
	44.2 From Bits to Banks/Planes
	44.3 Basic Flash Operations
	44.4 Flash Performance And Reliability
	44.5 From Raw Flash to Flash-Based SSDs
	44.6 FTL Organization: A Bad Approach
	44.7 A Log-Structured FTL
	44.8 Garbage Collection
	44.9 Mapping Table Size
	44.10 Wear Leveling
	44.11 SSD Performance And Cost
	44.12 Summary
45 Data Integrity and Protection
	45.1 Disk Failure Modes
	45.2 Handling Latent Sector Errors
	45.3 Detecting Corruption: The Checksum
	45.4 Using Checksums
	45.5 A New Problem: Misdirected Writes
	45.6 One Last Problem: Lost Writes
	45.7 Scrubbing
	45.8 Overheads Of Checksumming
	45.9 Summary
46 Summary Dialogue on Persistence
47 A Dialogue on Distribution
48 Distributed Systems
	48.1 Communication Basics
	48.2 Unreliable Communication Layers
	48.3 Reliable Communication Layers
	48.4 Communication Abstractions
	48.5 Remote Procedure Call (RPC)
	48.6 Summary
49 Sun’s Network File System (NFS)
	49.1 A Basic Distributed File System
	49.2 On To NFS
	49.3 Focus: Simple And Fast Server Crash Recovery
	49.4 Key To Fast Crash Recovery: Statelessness
	49.5 The NFSv2 Protocol
	49.6 From Protocol To Distributed File System
	49.7 Handling Server Failure With Idempotent Operations
	49.8 Improving Performance: Client-side Caching
	49.9 The Cache Consistency Problem
	49.10 Assessing NFS Cache Consistency
	49.11 Implications On Server-Side Write Buffering
	49.12 Summary
50 The Andrew File System (AFS)
	50.1 AFS Version 1
	50.2 Problems with Version 1
	50.3 Improving the Protocol
	50.4 AFS Version 2
	50.5 Cache Consistency
	50.6 Crash Recovery
	50.7 Scale And Performance Of AFSv2
	50.8 AFS: Other Improvements
	50.9 Summary
51 Summary Dialogue on Distribution
52 A Dialogue on Security
53 Introduction to Operating System Security
	53.1 Introduction
	53.2 What Are We Protecting?
	53.3 Security Goals and Policies
	53.4 Designing Secure Systems
	53.5 The Basics of OS Security
	53.6 Summary
54 Authentication
	54.1 Introduction
	54.2 Attaching Identities To Processes
	54.3 How To Authenticate Users?
	54.4 Authentication By What You Know
	54.5 Authentication by What You Have
	54.6 Authentication by What You Are
	54.7 Authenticating Non-Humans
	54.8 Summary
55 Access Control
	55.1 Introduction
	55.2 Important Aspects Of The Access Control Problem
	55.3 Using ACLs For Access Control
	55.4 Using Capabilities For Access Control
	55.5 Mandatory And Discretionary Access Control
	55.6 Practicalities Of Access Control Mechanisms
	55.7 Summary
56 Protecting Information With Cryptography
	56.1 Introduction
	56.2 Cryptography
	56.3 Public Key Cryptography
	56.4 Cryptographic Hashes
	56.5 Cracking Cryptography
	56.6 Cryptography And Operating Systems
	56.7 At-Rest Data Encryption
	56.8 Cryptographic Capabilities
	56.9 Summary
57 Distributed System Security
	57.1 Introduction
	57.2 The Role of Authentication
	57.3 Public Key Authentication For Distributed Systems
	57.4 Password Authentication For Distributed Systems
	57.5 SSL/TLS
	57.6 Other Authentication Approaches
	57.7 Some Higher Level Tools
	57.8 Summary
A Dialogue on Virtual Machine Monitors
B Virtual Machine Monitors
	B.1 Introduction
	B.2 Motivation: Why VMMs?
	B.3 Virtualizing the CPU
	B.4 Virtualizing Memory
	B.5 The Information Gap
	B.6 Summary
C Dialogue on Monitors
D Monitors (Deprecated)
	D.1 Why Bother with Monitors?
	D.2 Do We Get More Than Automatic Locking?
	D.3 Where Theory Meets Practice
	D.4 Oh Oh, A Race
	D.5 Peeking Under The Hood A Bit
	D.6 Other Uses Of Monitors
	D.7 Using Monitors To Implement Semaphores
	D.8 Monitors in the Real World
	D.9 Summary
E A Dialogue on Labs
F Laboratory: Tutorial
	F.1 A Simple C Program
	F.2 Compilation and Execution
	F.3 Useful Flags
	F.4 Linking with Libraries
	F.5 Separate Compilation
	F.6 Makefiles
	F.7 Debugging
	F.8 Documentation
	F.9 Suggested Readings
G Laboratory: Systems Projects
	G.1 Intro Project
H Laboratory: xv6 Projects
	H.1 Intro Project
	H.2 Processes and Scheduling
	H.3 Intro to Virtual Memory
	H.4 Copy-on-write Mappings
	H.5 Memory mappings
	H.6 Kernel Threads
	H.7 Advanced Kernel Threads
	H.8 Extent-based File System
	H.9 Fast File System
	H.10 Journaling File System
	H.11 File System Checker