Introduction to Operating Systems

• C Programming Coding Conventions
• Course Overview
  • The Toy Shop Analogy
• What is an Operating System?
  • OS Elements
    • Memory Management Example
  • OS Protection Boundary
    • System Calls
    • Cost of User/Kernel Transitions
  • OS Services
    • OS Components
  • OS Architectures
    • Monolithic OS
    • Modular OS
    • Microkernel
    • Linux and Mac OS X
• Process and Process Management
  • What is a Process?
  • Process Address Space
    • Virtual Addresses and Page Tables
  • Process Execution State
  • Process Control Block (PCB)
  • Context Switching
  • Process Life Cycle
    • States
    • Process Creation
  • CPU Scheduling
    • Timeslice and Efficiency
    • I/O and Scheduling
  • Inter-Process Communication (IPC)
    • Message Passing
    • Shared Memory
• Threads and Concurrency
  • Threads vs Processes
  • Benefits of Multithreading
  • Basic Thread Mechanisms
    • Thread Creation (Birrell’s Model)
  • Mutexes
    • Mutex Example
  • Condition Variables
  • Readers-Writer Problem
    • Critical Section Structure
  • Common Pitfalls
    • Spurious Wakeups
  • Deadlocks
  • Kernel vs User-Level Threads
    • Multithreading Models
    • Scope of Multithreading
  • Multithreading Patterns
    • Boss-Workers
    • Pipeline
    • Layered
• PThreads
  • Overview
  • Thread Creation
    • Thread Attributes
    • Detachable Threads
  • Compiling PThreads
  • Thread Creation Examples
  • PThread Mutexes
  • PThread Condition Variables
  • Producer-Consumer Example
• Thread Design Considerations
  • Kernel vs User-Level Threads
  • Thread Data Structures
    • Single CPU, Single-Threaded Process
    • Many-to-One Model
    • Splitting the PCB
    • Scaling to Multiple Processes and CPUs
    • Hard and Light Process State
    • Benefits of Multiple Data Structures
  • SunOS/Solaris Threading Model
    • User-Level Thread Structures (Stein & Shah)
    • Kernel-Level Data Structures
  • Thread Management Interactions
    • set_concurrency System Call
    • Visibility and Scheduling Problems
    • Multi-CPU Issues
    • Adaptive Mutexes
    • Thread Destruction and Reuse
  • Interrupts and Signals
    • Interrupts
    • Signals
    • Why Disable Interrupts/Signals
    • Signal Types
  • Interrupts as Threads (SunOS/Solaris)
  • Threads and Signal Handling (Solaris)
  • Linux Threading Model
    • Linux Kernel Quiz
• Thread Performance Considerations
  • Choosing a Threading Model
  • Performance Metrics
  • Multi-Process vs Multi-Threaded
    • Web Server Processing Steps
    • Multi-Process Model
    • Multi-Threaded Model
  • Event-Driven Model
    • Architecture
    • Achieving Concurrency
    • Why It Works
    • Implementation
    • Helper Threads/Processes (AMPED Model)
  • The Flash Web Server
    • Application-Level Optimizations
    • Apache Web Server
  • Experimental Methodology
    • Comparison Points
    • Workloads
    • Metrics
  • Results
    • Best Case (Synthetic — Single File)
    • Owlnet Trace (Small, Mostly Cached)
    • CS Trace (Large, I/O-Bound)
    • Impact of Optimizations
    • Summary of Flash Results
  • Designing Experiments
    • Principles
    • Experimental Design Guidelines
• CPU Scheduling
  • Scheduling Overview
  • Run-to-Completion Scheduling
    • First-Come First-Serve (FCFS)
    • Shortest Job First (SJF)
  • Preemptive Scheduling
    • SJF with Preemption
    • Priority Scheduling
    • Priority Inversion
    • Round Robin Scheduling
  • Timesharing and Timeslices
    • Timeslice Length
  • Runqueue Data Structures
    • Multi-Level Feedback Queue (MLFQ)
  • Linux O(1) Scheduler
  • Linux CFS (Completely Fair Scheduler)
  • Scheduling on Multiprocessors
    • Cache Affinity
    • NUMA-Aware Scheduling
  • Hyperthreading (SMT)
    • Hardware Counters and CPI
• Memory Management
  • Goals
  • Hardware Support
  • Page Tables
    • Page Table Entries
    • Page Table Size
    • Multi-Level Page Tables
    • TLB (Translation Lookaside Buffer)
    • Inverted Page Tables
    • Segmentation
  • Page Size
  • Memory Allocation
    • External Fragmentation
    • Linux Kernel Allocators
  • Demand Paging
    • Page Replacement
  • Copy-on-Write (COW)
  • Checkpointing
• Inter-Process Communication
  • IPC Overview
  • Message-Based IPC
    • Forms of Message Passing
  • Shared Memory IPC
    • Performance Comparison
  • System V Shared Memory API
  • POSIX Shared Memory API
  • Synchronization with Shared Memory
    • PThreads Synchronization for IPC
    • Other Synchronization for IPC
  • IPC Command Line Tools
  • Shared Memory Design Considerations
• Synchronization Constructs
  • Why More Synchronization?
  • Spinlocks
  • Semaphores
    • POSIX Semaphore API
  • Reader/Writer Locks
  • Monitors
    • Other Constructs
  • Hardware Atomic Instructions
    • Shared Memory Multiprocessors
    • Cache Coherence
    • Atomics and Cache Coherence
  • Spinlock Performance Metrics
    • Test-and-Set Spinlock
    • Test-and-Test-and-Set Spinlock (Spin on Read)
    • Delay-Based Spinlocks
  • Anderson’s Queueing Lock
    • Performance Comparison (Anderson’s Paper)
• I/O Management
  • I/O Devices
    • Device Features
    • CPU-Device Interconnect
  • Device Drivers
    • Types of Devices
  • CPU-Device Interactions
    • Memory-Mapped I/O
    • I/O Port Model
    • Interrupt vs. Polling
  • Programmed I/O (PIO)
  • Direct Memory Access (DMA)
  • Typical Device Access Flow
    • OS Bypass
    • Synchronous vs. Asynchronous I/O
  • Block Device Stack
  • Virtual File System (VFS)
    • VFS Key Abstractions
  • ext2 File System
    • Inodes and Indirect Pointers
  • Disk Access Optimizations
• Virtualization
  • What is Virtualization
  • Defining Virtualization
  • Benefits of Virtualization
  • Virtualization Models
    • Bare-Metal (Type 1)
    • Hosted (Type 2)
  • Hardware Protection Levels
  • Processor Virtualization
    • Trap-and-Emulate
    • x86 Challenges (Pre-2005)
    • Binary Translation
    • Paravirtualization
  • Memory Virtualization
    • Full Virtualization
    • Paravirtualized
  • Device Virtualization
    • Passthrough Model
    • Hypervisor Direct Model
    • Split Device Driver Model
  • Hardware Virtualization Support
• Remote Procedure Calls (RPC)
  • Why RPC
  • RPC Requirements
  • Structure of RPC
  • Steps in RPC
  • Interface Definition Language (IDL)
  • Marshalling and Unmarshalling
  • Binding and Registry
  • Handling Pointers
  • Partial Failures
  • SunRPC
    • Overview
    • XDR Interface Definition
    • Compiling XDR
    • Registry
    • Binding
  • XDR Data Types and Encoding
    • Data Types
    • Encoding Rules
    • XDR Routines
  • Java RMI
• Distributed File Systems
  • Distributed File Systems
    • DFS Models
  • Remote File Service Models
    • Upload/Download Model
    • True Remote File Access
    • Practical Compromise
  • Stateless vs Stateful Servers
  • Caching in a DFS
  • File Sharing Semantics
    • UNIX Semantics
    • Session Semantics
    • Periodic Updates
    • Other Semantics
    • Per-File Server State (Session + Server-Driven)
    • File vs Directory Service
  • Replication and Partitioning
    • Replication
    • Partitioning
  • Network File System (NFS)
    • Architecture
    • NFS Versions
  • Sprite Distributed File System
    • Access Pattern Observations
    • Design Decisions
    • File Access State
• Distributed Shared Memory
  • Distributed Shared Memory Overview
    • Peer Distributed Applications
    • Why DSM Matters
  • Hardware vs Software DSM
  • DSM Design: Sharing Granularity
    • False Sharing
  • DSM Design: Access Algorithm
  • DSM Design: Migration vs Replication
  • DSM Design: Consistency Management
  • DSM Architecture
    • Indexing Distributed State
    • Implementing DSM
  • Consistency Models
    • Strict Consistency
    • Sequential Consistency
    • Causal Consistency
    • Weak Consistency
• Datacenter Technologies
  • Internet Services
    • Multi-Tier Architecture
  • Internet Service Architectures
    • Scale-Out
    • Functionally Homogeneous
    • Functionally Heterogeneous
    • Scale-Out Limitations
  • Cloud Computing
    • The Animoto Example
    • Requirements
    • What Cloud Computing Provides
    • Why It Works
    • Cloud Computing Vision
  • Cloud Deployment Models
  • Cloud Service Models
  • Cloud Technology Requirements
  • Cloud Enabling Technologies
  • Cloud as a Big Data Engine
    • Example Big Data Stacks
• Threads Birrell
  • Introduction
  • Why Use Concurrency?
  • Design of a Thread Facility
    • Thread Creation
    • Mutual Exclusion
    • Condition Variables
    • Alerts
    • Deadlocks
    • Complexity
• Beyond MultiProcessing
  • Introduction
  • Overview of the Kernel Architecture
  • Data structures
  • Kernel Thread Scheduling
  • System Threads
  • Synchronization Architecture
  • Mutual Exclusion Lock Implementation
  • Turnstiles vs Queues in Synchronization Objects
  • Interrupts as Threads
  • Implementing Interrupts as Threads
  • Interrupt Thread Cost
• Implementing Lightweight Threads
• Network Programming
  • 3.4. IP Addresses, Part Deux
  • getaddrinfo()—Prepare to launch!
  • socket()—Get the File Descriptor!
  • bind()—What port am I on?
  • 5.4. connect()