Welcome to Operating Systems#
This site contains lecture notes, examples, and supporting materials for Operating Systems.
- About the Book
- Introduction
- Systems and Discrete Math Recap
- Boolean Logic
- Logical Equivalence
- De Morgan’s Laws
- Short-Circuit Evaluation
- Bitwise Operations
- XOR and Parity
- Number Systems and Data Representation
- Signed and Unsigned Values
- Modular Arithmetic
- Sets
- Power Sets
- Relations and Partial Orders
- Graphs
- Trees
- Counting and Interleavings
- Basic Complexity Thinking
- Computer Hardware Overview
- Memory Hierarchy
- Machine-Level Data
- Instruction Execution and Assembly
- Bitwise Assembly
- C as a Systems Language
- User Mode, Kernel Mode, and System Calls
- Files, Processes, and Interfaces
- What to Review Before Continuing
- Introduction to Processes
- Process Memory Layout
- Process Memory Layout
- Multithreaded Memory Layout
- Preliminaries
- Examine Process Layout Example
- Loading Programs
- Simple Executable Example
- Loading shared libraries (.so)
- Shared Library Example
- more about GCC pic option
- Loading static libraries
- Position Independent Code Example
- main.c
- main.nopic.s - non-position independent code (gcc -fno-pic)
- main.nopic.s - position independent code (gcc -fpic, default option)
- What’s the difference?
- Shared Libraries - Evaluation
- Static Libraries - Evaluation
- Libraries vs. Statically-Linked Programs
- Process Protection
- Process Creation with fork()
- fork() example
- fork() and exec() example
- Process Creation with clone()
- Windows CreateProcess() and CreateThread()
- Emulating fork() on Windows
- System Call Boundary Example
- Command-Line Option Example
- Process Termination
- wait() and waitpid() examples
- SIGCHLD examples
- Process-Oriented C Case Studies
- Files and I/O
- Common attributes of all (UNIX) files
- Types of Files in Unix
- Regular Files
- Folders
- Symbolic Links
- Block Device Files
- Character Device Files
- Named Pipes/FIFOs
- Unix Domain Sockets
- Filesystem System Calls
- Filesystem System Calls
- More Filesystem System Calls
- Opening Files with open()
- Closing files with close()
- Writing to a File
- Writing Example
- Reading from a File
- Reading Example
- Complete File I/O Example
- Seeking within a File
- Standard File Descriptors
- Duplicating File Descriptors
- Redirecting File Descriptors
- Reading Folders
- Directory Traversal in C
- Directory Traversal in C++
- Text Input
- Bounded Line Input Example
- Tokenizing Input with strtok()
- Dynamic String Buffer
- String Buffer Input Example
- Regular Expression Example
- Character List Case Study
- Word Counting with Hash Tables
- Word Counting with Trees
- Looking Ahead: I/O Performance
- Simple I/O Performance Experiment
- Reading/Writing Performance
- Vectored I/O Example
- Process/Thread Scheduling
- Kernel Mode vs. User Mode
- Interrupts
- Hardware Interrupts - PC Architecture
- Hardware Interrupts - Sources
- Software Interrupts
- Goals of a Process Scheduler
- Types of Scheduling Strategies
- OS Support
- Types of Processes to Schedule
- Preemptive Scheduling Key Terms
- Process states
- Choosing a Quantum
- Context Switches
- Context switching - How it works
- Degrees of Preemption
- Round - Robin Process Scheduling
- Scheduling with Multiple Queues
- Real-time Schedulers
- Example Real World RTS Problem
- Solution to Example Real World RTS Problem
- Types of Real-Time Scheduler Implementations
- Additional Concerns in Advanced Scheduler Implementations
- Process Priority and Scheduling in Linux
- Linux Real Time Scheduler
- Linux Preemptive Scheduler
- Nice Values
- Process Scheduling in Windows
- User-Mode Schedulers
- User-Mode Threads: Why?
- User-Mode Threads: Why Not?
- GNU - Pth - User Mode Pthreads
- PThreads - Kernel Threads
- Basic pthread creation
- Joinable pthreads
- Condition variable preview
- Condition variable with explicit shared data
- C# Thread Scheduling Case Study
- Mutual Exclusion
- Critical Sections
- Identifying the Critical Section
- Execution Orders and Atomicity
- Interleavings
- Characteristics of a Good Locking Solution
- Achieving Atomicity and Serializability
- Types of Pessimistic Locks
- Types of Optimistic Locks
- Software Transactional Memory Example
- Disabling Interrupts
- Strict Alternation
- Spin Locks
- Spin Lock Implementation
- Spin Lock Example
- Mutexes
- Mutex Example
- Semaphores
- Semaphore Implementation
- Semaphore Example
- Producer-Consumer with Semaphores
- Bounded Buffer Example
- Reader-Writer Locks
- POSIX Semaphores
- Windows Semaphores
- Monitors and Condition Variables
- Monitor Example
- Pthreads Condition Variables
- Windows Condition Variables
- C# Bounded Buffer
- C# Monitor Pipeline
- C# Threaded Enumeration
- Concise Pipeline with ThreadedList
- Dining Philosophers
- Deadlock
- Dining Philosophers Problem
- Dining Philosophers Deadlock Scenario
- Dining Philosophers Lock Graph
- Avoiding Deadlock with Try-and-Release
- Avoiding Deadlock with Lock Ordering
- Dijkstra’s Solution and the Banker’s Algorithm
- Deadlock Avoidance Implementation
- Deadlock Prevention Implementation
- Dining Philosophers Example
- Example of Deadlock in Nested Calls
- Multi-Lock Solutions in Windows
- Multi-Lock Solutions in Linux and Minix
- Deadlock with Correct Lock Ordering
- Starvation
- Starvation Example
- Reducing Starvation
- Guidelines to Avoid Starvation
- Livelock
- Lock Fairness
- Fairness Tradeoffs
- IPC Topics
- IPC Performance Hierarchy
- Pipes
- Pipe Descriptors
- Pipe Example
- Fork and Pipe Example
- Pipes and Context Switches
- Named Pipes and FIFOs
- Regular and Named Pipe Usage
- Named Pipe Uses
- Named Pipe Atomicity
- Signals
- Important Signals
- Handling Signals
- Sending Signals
- Interrupted System Calls
- Reentrant Signal Handlers
- Sleep with Alarm
- Better Sleep with Longjmp
- Signal Timing Problem
- Using Alarm for Time Limits
- Memory Mapped Files
- Virtual Addressing in Mapped Files
- Absolute Memory Addressing
- Relative Memory Addressing
- Using mmap
- Memory Mapped Example
- Memory Mapped Atomicity
- Shared Memory Locking
- Memory Mapped Queue Example
- Memory Mapped Queue Programs
- Submodule Memory Mapped Lock Example
- Memory Mapped I/O Performance
- Files as IPC
- Exposing Current State
- Spool Folders
- Cron Spool Folders
- CUPS Spool Folders
- Lock Files
- Doors
- Door Server
- Door Client
- Domain Sockets
- Domain Socket Example
- Submodule Domain Socket Example
- TCP/IP
- Virtual Memory
- What is Virtual Memory?
- Memory Management Units
- Pages and Page Tables
- Page Table Size
- Page Table Entries
- Multi-Level Page Tables
- Two-Level Page Table
- MMU Address Translation Algorithm
- Page Faults
- Page Faults in UNIX
- Page Faults in Windows
- Page Replacement and Swapping
- When the Swapper Runs
- Physical Page Contenders
- Swapper Algorithms
- Page Classification
- Not Recently Used
- FIFO Replacement
- Second-Chance FIFO
- Clock Replacement
- Least Recently Used
- Not Frequently Used
- Aging
- Belady’s Anomaly
- Belady’s Anomaly Diagram
- Modeling Page Replacement
- Modeling LRU
- Distance Strings
- Distance String Example
- Design Considerations for Paging Systems
- Working Sets
- Taking Advantage of Locality
- Costs of Paging Page Classes
- Reducing Paging Cost
- Local and Global Paging
- Page Locking
- Copy on Write
- Backing Store
- Hibernation
- Hot Memory
- Hot Memory Example
- Summary: Page Fault Handling
- Linux Kernel Module Case Study
- Linux /proc Module Case Study
- Linux Character Device Case Study
- Linux System Call Case Study
- Minix Startup Case Study
- Minix Time Driver Case Study
- Userland Memory Management
- Why Userland Memory Management?
- Userland Memory as Runtime Policy
- Heap Management
- The Memory Manager
- Characteristics of Allocation
- Over-Allocation and Buckets
- Characteristics of a Good Memory Manager
- Memory Hierarchy Refresher
- Program Locality
- Fragmentation
- Reducing Heap Fragmentation
- First Fit and Best Fit
- Best-Fit Buckets
- Managing Free Space
- Bugs and Explicit Allocators
- Debugging malloc and free
- Expanding the Heap
- Simple malloc Case Study
- Manual Deallocation Problems
- Avoiding Manual Deallocation Problems
- Garbage Collection
- Requirements for Garbage Collectors
- Goals for a Garbage Collector
- Disadvantages of Garbage Collection
- Reachability
- Reference Counting
- Reference Counting Tradeoffs
- Mark-and-Sweep Garbage Collection
- Mark-and-Compact Garbage Collection
- Garbage Collection Costs
- Incremental Garbage Collection
- Why Incremental Collection Works
- Generational Garbage Collection
- Buyer Beware
- Recommended Reading
- Storage and Devices
- Storage Devices
- IDE and ATA
- ATAPI
- SATA
- Hard Disk Geometry
- Logical Block Addressing
- Storage and Failure
- Maximizing Availability with RAID
- RAID Implementation
- RAID 0
- RAID 1
- RAID 5
- RAID 5 Parity Write
- RAID 5 Parity Read
- RAID 5 Recovery Example
- Disk Partitioning
- Disk Arms and Heads
- Good Disk Scheduling
- Disk Scheduling Algorithms
- FIFO Disk Scheduling
- Shortest Seek First
- Elevator Algorithm
- Elevator Tradeoffs
- FSCAN
- Implementing Files and Folders
- Filesystem Layout
- Linked-List Allocation
- Linked-List Tradeoffs
- File Allocation Tables
- FAT Tradeoffs
- inodes
- Minix inode
- inode Strategy
- Block Caches
- Minix Block Cache
- Block Cache Tradeoffs
- Folders and Path Traversal
- Path Traversal
- Virtual Filesystems
- VFS Adaptation
- Filesystem Stacking
- User-Mode Filesystems
- User-Mode Filesystem Tradeoffs
- Pass-Through FUSE Filesystem
- FUSE Name Operations
- FUSE File I/O Operations
- FUSE Directory Operations
- FUSE
- Contributors
- Code of Conduct
- Book Index