COSC240 • Operating Systems

Week 6: Synchronization & Deadlock

Now that our operating system supports true multiprocessing and preemptive scheduling, we confront the structural pathologies of concurrent execution. Expanding beyond race conditions on shared memory, we examine the systemic failure states that emerge when threads compete for scarce system resources: Deadlock, Livelock, and Starvation.

📚 What You Will Learn
  • Differentiating Deadlock (permanent blockage), Livelock (active state oscillation), and Starvation (scheduling unfairness).
  • The Four Coffman Conditions governing necessary and sufficient deadlock states.
  • Resource Allocation Graphs (RAGs), wait-for graph reduction, and cycle detection algorithms.
  • The four canonical handling strategies: The Ostrich Algorithm, Deadlock Prevention, Detection/Recovery, and Dijkstra's Banker's Algorithm.
  • Classic synchronization problems: Dining Philosophers, Readers-Writers starvation, and modern kernel defenses (Linux lockdep).
✅ What You Should Do
  • Review the Week 6 concurrency lecture recordings and guided notes.
  • Engage with the interactive directed narrative steppers embedded in each module.
  • Complete Theory Tutorial 06 (Resource Allocation Graphs & Coffman Analysis).
  • Complete Practical Tutorial 06 (Deadlock Detection & POSIX Lock Ordering in C).
  • Prepare for Quiz 3 (covering Week 5 I/O / Disks and Week 6 Synchronization / Deadlock).
📂 Course Modules & Deep-Dive Texts
Module 01

Concurrency Hazards: Livelock, Starvation & PIP

Contrast CPU-burning livelock with blocking deadlocks, study scheduling starvation, and analyze Priority Inheritance Protocols (PIP) using the Mars Pathfinder anomaly.

Livelock Starvation Priority Inversion PIP Protocol
Launch Module 01 →
Module 02

Deadlock Characterization & Coffman Conditions

Dissect the four necessary and sufficient Coffman conditions: Mutual Exclusion, Hold and Wait, No Preemption, and Circular Wait. Construct Resource Allocation Graphs (RAGs) and execute graph cycle detection.

Coffman Conditions RAG Matrices Wait-For Graphs Cycle Detection
Launch Module 02 →
Module 03

Deadlock Handling Strategies & The Banker's Algorithm

Evaluate the Ostrich policy, static prevention via global lock hierarchy, runtime detection with victim preemption, and Dijkstra's Banker's Algorithm for multi-unit resource allocation.

Banker's Algorithm Safe Sequence Deadlock Prevention Victim Selection
Launch Module 03 →
Module 04

Classic Synchronization Problems & Real-World Defenses

Analyze the Dining Philosophers, Readers-Writers starvation, and Sleeping Barber challenges. Investigate production OS deadlock defenses, including Linux lockdep validation and Windows Driver Verifier.

Dining Philosophers Readers-Writers Linux lockdep Static Analysis
Launch Module 04 →
🔮 Interactive Visualizers & Simulation Laboratories

Deadlock Detector

Interactive graph cycle detection sandbox for Resource Allocation Graphs.

Open Detector →

Dining Philosophers

Simulate concurrent resource contention, deadlocks, and asymmetric fork solutions.

Open Simulation →

Database Deadlock

Trace lock contention, two-phase locking (2PL), and transaction abort/rollback.

Open Database 2PL →

IPC Deadlock

Explore synchronous rendezvous message queues and circular wait deadlocks.

Open IPC Lab →