Free lesson · Operating Systems

DEADLOCKS

Easy12 min readoperating-systemsosconcurrency

The Problems That Defined the Field

Every synchronization primitive you have learned in this module - mutexes, semaphores, condition variables, monitors - was designed to solve a specific class of coordination problems. Before these primitives existed, computer scientists formulated a set of canonical problems that capture the essential challenges of concurrent programming. These problems are studied because they are not contrived puzzles - they are precise abstractions of real coordination challenges that appear in operating systems, databases, web servers, and distributed systems every day.

This topic introduces the five classic synchronization problems. For each one, you will understand the problem statement, why it matters, which primitives solve it, and where it appears in real systems. The detailed implementations - with code, performance analysis, and variant trade-offs - are covered in depth in the Concurrency Interview Mastery course. This topic gives you the conceptual map so you can reason about these problems in interviews without needing to memorize every implementation detail.

Tip: The Concurrency Interview Mastery course (led by Nikhil Joshi) covers each of these problems across multiple lessons with full Java and Python implementations, starvation analysis, fairness proofs, and interview-specific variations. If you are preparing for a concurrency-heavy interview (Google, Amazon, or any systems role), that course is the natural next step after this module.

Problem 1: Producer-Consumer (Bounded Buffer)

The Problem

One or more producer threads generate data items and place them into a shared buffer. One or more consumer threads take items from the buffer and process them. The buffer has a fixed capacity. Producers must wait when the buffer is full. Consumers must wait when the buffer is empty.

Why It Matters

The producer-consumer pattern is everywhere in systems programming. Any time data flows from one stage of a pipeline to the next, you have a producer and a consumer with a buffer between them.

Operating systems: The keyboard driver is a producer that puts keystrokes into a buffer. The terminal application is a consumer that reads them. The pipe between two Unix commands (ls | grep foo) is a bounded buffer connecting a producer process to a consumer process.

Web servers: The main thread accepts incoming HTTP connections (producer) and places them into a task queue. Worker threads from a thread pool (consumers) take connections from the queue and handle them. Nginx, Apache, and every async web framework use this pattern.

Data pipelines: Apache Kafka is fundamentally a distributed producer-consumer system. Producers write events to topic partitions (bounded by disk). Consumers read events from partitions. The entire real-time data processing ecosystem is built on this abstraction.

Logging frameworks: Application threads (producers) generate log entries and place them into an in-memory buffer. A dedicated I/O thread (consumer) writes the buffer to disk or a logging service. This decouples the application's hot path from slow disk I/O.

The Synchronization Challenge

Three constraints must hold simultaneously:

Mutual exclusion on the buffer. Multiple producers or consumers must not corrupt the buffer by accessing it concurrently.
Block producers when full. A producer that tries to add to a full buffer must wait until a consumer removes an item.
Block consumers when empty. A consumer that tries to remove from an empty buffer must wait until a producer adds an item.

Solution Approaches

You have already seen solutions in Topics 4 and 5:

Semaphore solution (Topic 4): Two counting semaphores (empty initialized to N, full initialized to 0) enforce the capacity constraints. A mutex protects the buffer itself. This is the classic textbook solution.

Condition variable solution (Topic 5): A mutex protects the buffer. Two condition variables (not_full and not_empty) handle the blocking. Producers wait on not_full and signal not_empty. Consumers wait on not_empty and signal not_full.

Monitor solution (Topic 6): The buffer, the mutex, and the condition variables are packaged into a single monitor. Java's BlockingQueue interface is exactly this - a monitor-style bounded buffer.

Problem 2: Readers-Writers

The Problem

Multiple threads share a data structure. Some threads only read the data (readers). Some threads modify the data (writers). Multiple readers can read simultaneously without conflict. But a writer must have exclusive access - no other readers or writers can access the data while a writer is modifying it.

Why It Matters

The readers-writers pattern appears whenever data is read far more often than it is written - which is most data in most systems.

Database systems: Read queries (SELECT) can execute concurrently. Write queries (INSERT, UPDATE, DELETE) require exclusive access to avoid corrupted indexes. Database locking systems are implementations of the readers-writers solution.

Configuration management: Application threads read configuration values thousands of times per second. Configuration updates happen rarely (a deploy, a settings change). A read-write lock allows concurrent reads with exclusive updates.

Caching layers: Cache reads happen on every request. Cache invalidation or refresh happens infrequently. Concurrent reads with exclusive writes is the readers-writers pattern.

File systems: Multiple processes can read a file simultaneously. A process writing to the file needs exclusive access. The flock() system call in Unix supports shared (read) and exclusive (write) locks.

The Three Variants

The readers-writers problem has three variants that differ in fairness:

First readers-writers problem (readers-preferred): Readers have priority. As long as any reader is reading, new readers can start immediately - even if a writer is waiting. This maximizes read throughput but can starve writers if readers arrive continuously.

Second readers-writers problem (writers-preferred): Writers have priority. Once a writer is waiting, no new readers are allowed to start - existing readers finish, then the writer gets access. This prevents writer starvation but can delay readers.

Third readers-writers problem (fair / FIFO): Requests are served in arrival order. If a writer is waiting and a new reader arrives, the reader waits behind the writer. Neither readers nor writers can be starved. This is the most fair but typically has the lowest throughput.

graph TD
    subgraph READERS_PREF["Readers-Preferred"]
        RP_R1["Reader 1: reading"] 
        RP_R2["Reader 2: reading"]
        RP_W["Writer: WAITING<br/>(starved if readers keep arriving)"]
        RP_R3["Reader 3: starts immediately<br/>(jumps ahead of writer)"]
    end
    
    subgraph WRITERS_PREF["Writers-Preferred"]
        WP_R1["Reader 1: reading (will finish)"]
        WP_W["Writer: WAITING<br/>(gets next turn)"]
        WP_R2["Reader 2: BLOCKED<br/>(must wait for writer)"]
    end
    
    subgraph FAIR["Fair / FIFO"]
        F_R1["Reader 1: reading"]
        F_W["Writer: WAITING (next in queue)"]
        F_R2["Reader 2: WAITING (behind writer)"]
    end

This diagram shows the three variants of the readers-writers problem. In the readers-preferred variant, Reader 1 and Reader 2 are reading, a Writer is waiting, and Reader 3 starts immediately, jumping ahead of the waiting writer - which can starve the writer. In the writers-preferred variant, Reader 1 is finishing, the Writer will get the next turn, and Reader 2 is blocked behind the writer. In the fair or FIFO variant, Reader 1 is reading, the Writer is next in the queue, and Reader 2 is waiting behind the writer - neither readers nor writers can be starved.

Solution Approach

The readers-writers problem is typically solved with a read-write lock (RWLock), which you saw in Topic 3. The RWLock maintains a reader count and uses a mutex and condition variables (or semaphores) to coordinate access. The choice of variant (readers-preferred, writers-preferred, fair) is a parameter of the RWLock implementation.

Problem 3: Dining Philosophers

The Problem

Five philosophers sit around a circular table. Between each pair of adjacent philosophers is a single fork (five forks total). Each philosopher alternates between thinking and eating. To eat, a philosopher needs both the fork on their left and the fork on their right. After eating, they put both forks down and resume thinking.

The challenge: design a protocol that prevents deadlock (all philosophers stuck waiting for forks), prevents starvation (some philosopher never gets to eat), and allows maximum concurrency (as many philosophers eating simultaneously as possible).

Why It Matters

The Dining Philosophers problem is an abstraction of resource allocation with circular dependencies - the exact situation that causes deadlock in real systems.

Database deadlocks. Transaction A locks row 1 and needs row 2. Transaction B locks row 2 and needs row 1. This is two philosophers each holding one fork and waiting for the other.

Multi-lock acquisition. Any code that acquires multiple locks is vulnerable to the same circular dependency. The bank transfer example from Topic 3 (lock account A then account B vs lock account B then account A) is a two-philosopher version.

Resource allocation in operating systems. Processes that need multiple resources (memory, disk, network) can deadlock if each process holds some resources and waits for others held by other processes.

Why the Naive Solution Deadlocks

The obvious approach is: each philosopher picks up the left fork, then the right fork.

# DEADLOCKS
def philosopher(id):
    while True:
        think()
        pick_up(left_fork[id])       # All 5 do this simultaneously
        pick_up(right_fork[id])      # All 5 are now waiting - DEADLOCK
        eat()
        put_down(right_fork[id])
        put_down(left_fork[id])

If all five philosophers pick up their left fork at the same time, each one is holding one fork and waiting for the other - which is held by their neighbor. Nobody can proceed. This is the circular wait condition from the Coffman conditions (Topic 3).

Solution Approaches

Several solutions exist, each breaking a different Coffman condition:

Resource ordering (break circular wait). Number the forks 0 through 4. Each philosopher always picks up the lower-numbered fork first. Philosopher 4 picks up fork 0 (lower) before fork 4 (higher) - this breaks the cycle because nobody waits for a lower-numbered fork while holding a higher-numbered one.

Limiting diners (break hold-and-wait). Allow at most 4 philosophers to sit at a 5-fork table. Use a semaphore initialized to 4. Since there are 5 forks and at most 4 philosophers, at least one philosopher can always get both forks. No deadlock.

Monitor solution (atomic acquisition). Use a monitor that allows a philosopher to pick up both forks atomically - they either get both or neither. This eliminates the "holding one fork while waiting for the other" state entirely. Each philosopher checks if both forks are available; if not, they wait on their personal condition variable. When a neighbor puts down forks, they signal their neighbors' condition variables.

Problem 4: Sleeping Barber

The Problem

A barbershop has one barber, one barber chair, and N waiting chairs. If there are no customers, the barber sleeps in the barber chair. When a customer arrives, they wake the barber if the barber is sleeping, or sit in a waiting chair if the barber is busy. If all waiting chairs are full, the customer leaves.

Why It Matters

The sleeping barber is an abstraction of server thread pools with bounded queues - the exact architecture used by web servers, database connection handlers, and message processing systems.

Thread pool with bounded task queue. The barber is a worker thread. Customers are incoming tasks. Waiting chairs are the task queue. The barber sleeps when the queue is empty (thread waits on a condition variable). A new task wakes the worker. If the queue is full, the task is rejected (customer leaves).

Nginx/Apache worker model. The main listener socket accepts connections (customers arriving). Worker threads (barbers) process requests. The accept queue has a bounded size (waiting chairs). Connections that arrive when the queue is full are refused.

Solution Approach

The sleeping barber is typically solved with three semaphores and a mutex:

A customers semaphore (counting, initialized to 0) tracks waiting customers. The barber waits on this semaphore to sleep when there are no customers.
A barber semaphore (binary, initialized to 0) signals that the barber is ready for the next customer.
A mutex protects the shared waiting-room counter.

Problem 5: Cigarette Smokers

The Problem

Three smokers sit around a table. Each smoker needs three ingredients to make a cigarette: tobacco, paper, and matches. Each smoker has an infinite supply of one ingredient: smoker A has tobacco, smoker B has paper, smoker C has matches. An agent places two random ingredients on the table. The smoker who has the third ingredient picks up the two ingredients, makes a cigarette, and smokes. The agent then places two new ingredients.

Why It Matters

The cigarette smokers problem demonstrates the difficulty of resource matching - coordinating access to resources where each consumer needs a specific combination. It is relevant to:

Task scheduling with resource constraints. A task requires CPU and memory and disk. Different tasks need different combinations. The scheduler must match available resources to waiting tasks.

Supply chain coordination. A manufacturing step needs parts A, B, and C from different suppliers. The coordination of which parts are available and which step can proceed is a matching problem.

Why It Is Hard

The difficulty is that the smokers cannot simply test which ingredients are on the table - the problem specification requires that they use only semaphores (no conditional logic on the ingredients). This makes the problem artificially constrained, and Patil (1971) proved that it has no solution using only semaphores without helper threads. The solution requires pusher threads - intermediary threads that observe which ingredient the agent placed and signal the appropriate smoker.

This is why the cigarette smokers problem is primarily an academic exercise - it demonstrates the expressive limits of semaphores. In practice, you would solve this with condition variables (which allow arbitrary boolean conditions) or message passing.

How These Problems Map to Interview Questions

Interviewers rarely ask you to solve these problems by name. Instead, they present a scenario that maps to one of these patterns, and they expect you to recognize the underlying problem:

Interview Scenario	Underlying Classic Problem
"Design a thread-safe bounded queue"	Producer-Consumer
"Design a cache that supports concurrent reads"	Readers-Writers
"Multiple processes need multiple locks"	Dining Philosophers (deadlock)
"Design a worker thread pool with a task queue"	Sleeping Barber
"How do you handle database deadlocks?"	Dining Philosophers
"Design a rate limiter for an API"	Producer-Consumer (variant)
"How does `ReadWriteLock` work in Java?"	Readers-Writers

The value of knowing the classic problems is pattern recognition. When an interviewer describes a custom scenario, you can say: "This is structurally the readers-writers problem - I would approach it with a read-write lock and choose the writers-preferred variant to prevent starvation." That statement immediately establishes credibility.

Interview: "Walk me through the classic synchronization problems and where you would see each one in practice."

"The five classic problems are:

Producer-Consumer - data flows through a bounded buffer between producers and consumers. Solved with semaphores or condition variables. Real-world: Kafka, thread pool task queues, logging pipelines, Unix pipes.

Readers-Writers - many readers can access data concurrently, but writers need exclusive access. Solved with read-write locks. Real-world: database read/write locking, configuration stores, caches.

Dining Philosophers - multiple threads each need multiple resources, creating deadlock risk from circular dependencies. Solved by resource ordering, limiting concurrency, or atomic resource acquisition. Real-world: database deadlocks, multi-lock acquisition patterns.

Sleeping Barber - a server thread sleeps when there is no work and wakes when work arrives, with a bounded queue for excess work. Solved with semaphores and condition variables. Real-world: web server thread pools, connection handlers.

Cigarette Smokers - resource matching under constrained signaling. Primarily academic - demonstrates the limits of semaphore-only solutions. In practice, condition variables or message passing handle this naturally."

The Bridge to Concurrency Interview Mastery

This module gives you the operating system foundation: what synchronization primitives are, how they work at the OS level, and what problems they solve. The Concurrency Interview Mastery course builds on this foundation with implementation-level depth:

What this module covers: How mutexes, semaphores, condition variables, and monitors work at the OS level. The conceptual framework for the classic problems. The vocabulary and reasoning patterns you need for interview conversations.

What the Concurrency course covers: Full Java and Python implementations of every classic problem with multiple variants. Lock-free data structures using CAS. Java's java.util.concurrent library in depth. Thread pool design patterns. Concurrent collection internals (ConcurrentHashMap, CopyOnWriteArrayList). Deadlock detection and avoidance algorithms. Memory model and happens-before relationships. Performance analysis of different synchronization strategies.

If your interview involves concurrency-heavy systems (distributed systems, database internals, real-time processing), the Concurrency course is essential. If your interview is general software engineering with standard OS-knowledge questions, this module provides sufficient depth.

graph LR
    subgraph THIS["This Module: Process Synchronization"]
        M1["Critical Sections"]
        M2["Race Conditions"]
        M3["Mutexes"]
        M4["Semaphores"]
        M5["Condition Variables"]
        M6["Monitors"]
        M7["Classic Problems<br/>(conceptual)"]
    end
    
    subgraph CONC["Concurrency Interview Mastery"]
        C1["Producer-Consumer<br/>(4 variants, full code)"]
        C2["Readers-Writers<br/>(3 variants, fairness proofs)"]
        C3["Dining Philosophers<br/>(5 solutions compared)"]
        C4["Lock-Free Data Structures"]
        C5["java.util.concurrent deep dive"]
        C6["Memory Models"]
    end
    
    M7 -->|"foundation"| C1
    M7 -->|"foundation"| C2
    M7 -->|"foundation"| C3
    M3 -->|"prerequisite"| C4
    M5 -->|"prerequisite"| C5
    M6 -->|"prerequisite"| C6

This diagram shows the relationship between the current module on Process Synchronization and the Concurrency Interview Mastery course. The current module covers critical sections, race conditions, mutexes, semaphores, condition variables, monitors, and the classic problems at a conceptual level. These topics serve as the foundation and prerequisites for the Concurrency course, which covers the producer-consumer problem in four variants with full code, the readers-writers problem in three variants with fairness proofs, the dining philosophers with five solutions compared, lock-free data structures, a deep dive into Java's concurrent utilities library, and memory models.

Exercise: Starter: For each of the following real-world scenarios, identify which classic synchronization problem it maps to: (a) A print server that accepts print jobs from multiple computers and processes them one at a time. (b) A DNS cache that is read by thousands of request-handling threads and updated once every 30 seconds. (c) Two database transactions that each lock one row and then try to lock the row the other one holds.

Intermediate: Implement the Dining Philosophers problem in Python using a monitor-style approach. Create a Table class with pickup_forks(philosopher_id) and putdown_forks(philosopher_id) methods. Use a single threading.Condition to coordinate. Prevent deadlock by requiring that both forks are available before a philosopher picks up either one. Run with 5 philosophers each eating 10 meals and verify no deadlock occurs.

Advanced: Implement the Sleeping Barber problem in Python with 1 barber, 5 waiting chairs, and 20 customers arriving at random intervals. Use semaphores for customer/barber coordination and a mutex for the waiting-room counter. Track and print: how many customers were served, how many left because the waiting room was full, and the average wait time for served customers.

Back to Operating Systems