Deadlocks and Synchronization

Learning Objectives

By the end of this page, you should be able to:

• Explain what a race condition is and why the critical-section problem requires mutual exclusion, progress, and bounded waiting.
• Differentiate mutex locks, counting/binary semaphores, and monitors, and know when each is the right tool.
• State the four necessary conditions for deadlock (Coffman conditions) and explain why all four must hold simultaneously.
• Apply the Banker's Algorithm to determine whether a resource allocation state is safe.
• Compare deadlock prevention, avoidance, detection, and recovery as four distinct strategies.
• Trace a resource-allocation graph to identify a cycle and decide whether it implies deadlock.

Quick Answer

Synchronization is how an OS coordinates concurrent processes/threads so they share data and resources safely, using tools like mutexes, semaphores, and monitors to prevent race conditions. Deadlock is the failure mode where synchronization goes wrong in a specific way: two or more processes each hold a resource the other needs and neither will yield, so all of them freeze forever. Deadlock requires four conditions simultaneously — mutual exclusion, hold-and-wait, no preemption, and circular wait — and breaking any single one prevents it. This matters because deadlock isn't a crash with an error message; it's silent, and a database, an OS kernel, or a multithreaded app can hang indefinitely until an operator notices and kills a process, so every system that shares resources needs a deliberate strategy: prevent, avoid, detect, or simply ignore and reboot.

Race Conditions and the Critical-Section Problem

A race condition occurs when two or more threads/processes access shared data concurrently and the final result depends on the unpredictable timing of their execution. The classic example is two threads incrementing a shared counter: count++ is not atomic — it compiles to a load, an increment, and a store. If both threads load the same value before either stores, one increment is silently lost.

The critical section is the part of a program that accesses shared data and must not be executed by more than one thread at a time. A correct solution to the critical-section problem must satisfy three requirements:

1. Mutual Exclusion — only one process may be in its critical section at a time.
2. Progress — if no process is in its critical section, one of the processes wanting to enter must eventually be allowed to, and that decision can't be postponed indefinitely.
3. Bounded Waiting — there is a limit on how many times other processes can enter their critical sections before a waiting process gets its turn.

Synchronization Primitives

Mutex Locks

A mutex (mutual exclusion lock) is the simplest primitive: a binary flag with acquire()/lock() and release()/unlock() operations. Only the thread that locked it may unlock it. It guarantees mutual exclusion but nothing more — if you forget to unlock, everyone else waits forever.

std::mutex mtx;
void safeIncrement(int& counter) {
    std::lock_guard<std::mutex> guard(mtx); // acquired here
    counter++;
    // released automatically when guard goes out of scope
}

Real-world example: A bank account object shared by multiple transaction threads wraps its balance updates in a mutex so that a withdrawal and a deposit can never interleave mid-update.

Why it matters: Without a mutex, concurrent updates to shared state produce lost updates or corrupted data structures — bugs that appear rarely and are notoriously hard to reproduce.

Common misunderstanding: Students often think locking "pauses" the other thread's entire execution. It doesn't — the other thread keeps running until it tries to acquire the same lock, at which point it blocks.

Semaphores

A semaphore is an integer counter manipulated only through two atomic operations: wait()/P() (decrement; block if the result would be negative) and signal()/V() (increment; wake a waiter if any). A binary semaphore (0 or 1) behaves like a mutex. A counting semaphore can guard a pool of N identical resources — e.g., N database connections — by initializing the counter to N.

std::counting_semaphore<5> pool(5); // 5 available connections
void useConnection() {
    pool.acquire();   // P(): blocks if all 5 are in use
    // ... use one connection ...
    pool.release();   // V(): returns it to the pool
}

Real-world example: A web server limits itself to 5 concurrent database connections using a counting semaphore initialized to 5, so the 6th request naturally blocks until one is freed.

Why it matters: Semaphores generalize mutual exclusion to resource counting, which a plain mutex cannot express.

Common misunderstanding: Unlike a mutex, a semaphore has no concept of "ownership" — any thread can call signal(), even one that never called wait(). This flexibility is powerful (useful for producer-consumer signaling) but also a common source of bugs, since there's no compiler-enforced discipline preventing a mismatched or duplicate signal().

Monitors

A monitor is a higher-level construct that bundles shared data, the procedures that operate on it, and an implicit lock into one language-level unit, so that only one thread executes inside the monitor at a time. Threads that need to wait for a condition (e.g., "buffer is not full") use condition variables with wait()/signal() (or notify()), which release the monitor's lock while waiting and reacquire it on wake.

public class Buffer {
    private final Object lock = new Object();
    private boolean full = false;
    public void put() throws InterruptedException {
        synchronized (lock) {
            while (full) lock.wait();      // release lock, sleep
            full = true;
            lock.notifyAll();
        }
    }
}

Real-world example: Java's synchronized blocks and wait()/notifyAll(), and the bounded-buffer producer-consumer pattern used inside message queues, are textbook monitors.

Why it matters: Monitors reduce the chance of programmer error compared to raw semaphores because the lock is acquired/released automatically by the language runtime — you can't forget to release it.

Common misunderstanding: Students assume notify()/signal() immediately hands the CPU to the waiting thread. In practice, the signaled thread only becomes runnable again — it must still reacquire the monitor lock and re-check its condition (hence while (full) not if (full)), because another thread might grab the lock first and change the state again ("spurious wakeup" or a beaten-to-the-punch waiter).

Deadlock: The Four Necessary Conditions

A deadlock is a state where a set of processes are each waiting for an event (typically resource release) that only another process in the same set can cause — so none of them can ever proceed. Deadlock can occur if and only if all four of the following (the Coffman conditions) hold at once:

1. Mutual Exclusion — at least one resource must be held in a non-shareable mode (only one process can use it at a time).
2. Hold and Wait — a process holding at least one resource is waiting to acquire additional resources currently held by other processes.
3. No Preemption — resources cannot be forcibly taken away; a process must release them voluntarily.
4. Circular Wait — there exists a set of processes {P0, P1, ..., Pn} where P0 waits for a resource held by P1, P1 waits for P2, ..., and Pn waits for a resource held by P0.

Example: Process A holds a printer and requests a scanner; Process B holds the scanner and requests the printer. All four conditions hold — printer/scanner are non-shareable (mutual exclusion), each process holds one resource while waiting for another (hold and wait), neither resource can be yanked away (no preemption), and A→B→A forms a cycle (circular wait). Neither process can ever finish.

Why it matters: Because all four conditions are necessary (not just sufficient in combination), breaking any single one is enough to make deadlock impossible — this is the entire basis for deadlock prevention strategies.

Common misunderstanding: Students often think a cycle in a resource-allocation graph always means deadlock. That's only guaranteed when each resource type has exactly one instance. If a resource type has multiple instances, a cycle is necessary but not sufficient — the processes involved might still be able to proceed if enough instances free up along the cycle.

Handling Deadlock: Four Strategies

Prevention

Prevention works by ensuring at least one Coffman condition can never hold, structurally.

• Break mutual exclusion: make resources shareable (not always possible, e.g., a printer).
• Break hold-and-wait: require a process to request all resources it will ever need upfront, or release everything before requesting more.
• Break no-preemption: allow the OS to forcibly take a resource from a process (used in some database transaction managers via rollback).
• Break circular wait: impose a total ordering on resource types and require processes to request resources in increasing order.

This guarantees no deadlock but can cause low resource utilization and reduced concurrency — requesting everything upfront wastes resources a process might not need for a while.

Avoidance: The Banker's Algorithm

Avoidance doesn't eliminate the Coffman conditions; instead, it makes the OS refuse any resource request that would move the system into an unsafe state — one where no ordering of remaining process completions is guaranteed. This requires processes to declare their maximum future resource needs in advance.

The Banker's Algorithm checks, before granting a request, whether a safe sequence still exists — an ordering of all processes such that each one's remaining need can be satisfied using currently available resources plus what's released by processes finishing before it.

Worked example: Suppose there are 3 resource types with 10 total instances of type A. Two processes have declared max needs: P1 max = 7, currently allocated = 3 (need = 4); P2 max = 9, currently allocated = 5 (need = 4). Available = 10 − 3 − 5 = 2.

• Can P1 finish with 2 available? No (needs 4).
• Can P2 finish with 2 available? No (needs 4).

Neither can finish yet, so the system is already tight, but not necessarily unsafe — if either process only needed ≤ 2 more, a safe sequence would exist. If, in this example, neither process's remaining need is ≤ available and neither will release partial resources before finishing, the state is unsafe, and the Banker's Algorithm would have refused whatever earlier allocation created this state.

Why it matters: Avoidance permits more concurrency than blanket prevention because it only blocks requests that would actually create risk, not every request that merely holds one resource while asking for another.

Common misunderstanding: An "unsafe state" is not the same as a deadlock. Unsafe only means some future request pattern could lead to deadlock — the system might still get lucky and finish fine. The Banker's Algorithm is conservative: it refuses to gamble on luck.

Detection and Recovery

Detection lets deadlocks happen and periodically checks for them, typically by maintaining a wait-for graph (an edge from Pi to Pj means Pi is waiting for a resource held by Pj) and running a cycle-detection algorithm. If a cycle is found (with single-instance resources) or an availability-based reduction algorithm can't reduce the graph fully (multi-instance resources), deadlock is confirmed.

Recovery options once detected:

• Process termination — kill one process in the cycle (or all of them) to free its resources.
• Resource preemption — forcibly take a resource from one process and give it to another, rolling the victim back to a safe checkpoint.

Real-world example: Relational database engines (PostgreSQL, MySQL/InnoDB) run periodic deadlock detection on lock waits between transactions; when found, the database automatically aborts one transaction (the "victim," often the one with the least rollback work) and returns a deadlock error to that client.

Why it matters: Detection + recovery is often cheaper in practice than prevention or avoidance because deadlocks are rare in well-designed systems, so paying a small periodic detection cost beats permanently restricting concurrency.

Key Terms

Term	Definition	Context/Related
Race Condition	Outcome depends on the unpredictable timing/interleaving of concurrent operations on shared data	Root cause synchronization primitives exist to prevent
Critical Section	Code segment that accesses shared data and must run under mutual exclusion	Must satisfy mutual exclusion, progress, bounded waiting
Mutex	Binary lock allowing only its owner to unlock it; simplest synchronization primitive	Guarantees mutual exclusion only
Semaphore	Integer counter with atomic wait()/signal() operations; can guard N instances of a resource	Binary semaphore ≈ mutex; counting semaphore manages a pool
Monitor	Language-level construct bundling shared data, procedures, and an implicit lock	Uses condition variables (wait/notify) for conditional blocking
Deadlock	A set of processes each waiting on an event only another process in the set can trigger	Requires all four Coffman conditions simultaneously
Coffman Conditions	Mutual exclusion, hold-and-wait, no preemption, circular wait	All four necessary; breaking any one prevents deadlock
Safe State	A state from which some sequence lets every process finish given max future demands	Distinct from deadlock — a superset of "not yet deadlocked"
Banker's Algorithm	Avoidance algorithm that only grants requests that keep the system in a safe state	Requires processes to declare maximum resource needs upfront
Wait-For Graph	Graph with an edge Pi→Pj if Pi waits for a resource held by Pj	Used for deadlock detection; a cycle signals deadlock (single-instance case)
Livelock	Processes keep changing state in response to each other but make no progress	Unlike deadlock, processes aren't blocked, just unproductive

Common Mistakes

1. Misconception: "A cycle in the resource-allocation graph always means the system is deadlocked." Why it's wrong: This is only true when every resource type involved has a single instance. With multiple instances of a resource type, a cycle is necessary but not sufficient for deadlock — the processes in the cycle might still be resolvable if freed instances elsewhere allow one to finish and release what the next one needs. Correct explanation: For single-instance resource types, cycle = deadlock. For multi-instance types, you must check whether the graph can be fully "reduced" (every process eventually satisfiable) — only an irreducible cycle confirms deadlock.

2. Misconception: "Semaphores and mutexes are basically the same thing, just different names." Why it's wrong: A mutex has ownership semantics (only the locking thread can unlock it) and represents "is this single resource free or not," while a semaphore is a counter with no ownership and can represent N interchangeable resource instances, and any thread can call signal() regardless of who called wait(). Correct explanation: Use a mutex to protect a single critical section. Use a semaphore when you need to track availability of a countable resource pool or to signal between threads (e.g., producer-consumer) rather than just exclude.

3. Misconception: "Preventing deadlock is always the right strategy since it eliminates the problem entirely." Why it's wrong: Prevention techniques (requesting all resources upfront, imposing strict resource ordering) reduce concurrency and resource utilization, sometimes severely, and aren't always feasible if a process doesn't know its future needs in advance. Correct explanation: The right strategy depends on context: prevention for safety-critical systems where a hang is unacceptable and overhead is tolerable; avoidance (Banker's Algorithm) when maximum needs are knowable in advance; detection and recovery when deadlocks are rare and an occasional rollback/restart is cheaper than restricting every request; and some systems (most general-purpose OS kernels for user processes) simply ignore the problem (the "ostrich algorithm") because deadlocks are infrequent enough that a reboot is cheaper than constant overhead.

Comparison and Connections

Strategy	How It Works	Concurrency Cost	When Used
Prevention	Structurally negate one Coffman condition	High (often forces upfront resource requests)	Safety-critical or simple systems
Avoidance (Banker's)	Refuse requests that lead to an unsafe state	Moderate (needs max-need info in advance)	Systems where resource needs are declarable
Detection & Recovery	Let deadlock happen, detect via graph, then kill/preempt	Low (only pays cost when needed)	Databases, systems where deadlock is rare
Ignorance ("ostrich algorithm")	Do nothing; rely on rarity and manual recovery (reboot)	None	Most general-purpose OS kernels (e.g., UNIX)

Primitive	Ownership?	Can Count Resources?	Typical Use
Mutex	Yes (only locker unlocks)	No (binary only)	Protecting a single critical section
Semaphore	No	Yes (counting)	Managing a resource pool, signaling between threads
Monitor	Yes (implicit, language-managed)	Via condition variables	High-level structured synchronization

Practice Questions

Recall

1. Name the four Coffman conditions required for deadlock. Answer guidance: Mutual exclusion, hold and wait, no preemption, circular wait.

2. What are the three requirements a solution to the critical-section problem must satisfy? Answer guidance: Mutual exclusion, progress, bounded waiting.

Understanding

3. Why does breaking just one Coffman condition prevent deadlock, even though the other three might still hold? Answer guidance: Because deadlock is only possible when all four conditions hold simultaneously — they're a conjunction, not independent risks — so if even one is structurally impossible, the specific circular-wait freeze pattern can never form, regardless of the other three.

4. Why does a monitor's condition-variable wait use while (condition) instead of if (condition)? Answer guidance: After being woken, the thread must reacquire the monitor lock, and by the time it does, another thread might have already changed the state again (or the wakeup was spurious), so re-checking the condition in a loop avoids acting on stale assumptions.

Application

5. Two threads share a bank account with methods deposit() and withdraw(), neither currently synchronized. Identify the race condition and describe the minimal fix. Answer guidance: Both methods read-modify-write the balance non-atomically; concurrent calls can interleave so one update is lost (classic lost-update). Fix: wrap the balance read-modify-write in a mutex (or make the whole method synchronized) so only one thread updates the balance at a time.

6. A system has 12 instances of one resource type. Three processes have max needs of 10, 4, and 9, and currently hold 5, 2, and 2 respectively. Is this state safe? Show the safe sequence if one exists. Answer guidance: Available = 12 − 5 − 2 − 2 = 3. Needs: P1 needs 5, P2 needs 2, P3 needs 7. P2 can finish with available=3 (needs 2) → releases its 2, available becomes 3+2=5. P1 can then finish (needs 5) → releases 5, available becomes 10. P3 can then finish (needs 7 ≤ 10). Safe sequence: P2, P1, P3.

Analysis

7. A resource-allocation graph shows P1 → R1 → P2 → R2 → P1, where R1 and R2 each have exactly one instance. Is the system deadlocked? What if R1 has two instances instead? Answer guidance: With single-instance resources, this cycle means deadlock — P1 waits for R1 (held by P2), P2 waits for R2 (held by P1), and neither can proceed. If R1 has two instances, the cycle is necessary but not sufficient: if the second instance of R1 is available or held by a process outside the cycle that can finish and release it, P1 could still obtain R1 and the deadlock resolves — so you'd need to check whether the graph reduces fully before concluding deadlock.

8. Compare deadlock avoidance (Banker's Algorithm) with deadlock detection-and-recovery in terms of the information each requires and the risk each accepts. Answer guidance: Avoidance requires processes to declare their maximum resource needs in advance and pays an ongoing cost (safety check) on every request, in exchange for guaranteeing deadlock never happens. Detection-and-recovery requires no advance declaration and imposes no cost on normal requests, but accepts the risk that deadlock can actually occur and must be cleaned up afterward (killing/rolling back a process) — a tradeoff of upfront restriction vs. occasional recovery cost.

FAQ

Q: Is livelock worse than deadlock? A: Neither is strictly "worse," but livelock is often more confusing to debug because the processes involved are actively running (consuming CPU) and changing state — they just never make forward progress, like two people repeatedly stepping aside for each other in a hallway and blocking each other again each time. Deadlock at least freezes visibly; livelock can masquerade as normal activity while wasting resources.

Q: Why can't operating systems just always use the Banker's Algorithm to avoid every deadlock? A: It requires every process to declare its maximum possible resource usage in advance, which is often unknown or impractical for general-purpose applications (a user program rarely knows upfront exactly how much memory or how many file handles it'll eventually need). It's practical in controlled environments (e.g., embedded/real-time systems with known task sets) but not for a general-purpose OS running arbitrary user programs.

Q: What's the difference between a deadlock and just a really slow process? A: A slow process is still making progress, just at low speed — it will eventually finish or unblock on its own. A deadlocked process will never proceed no matter how long you wait, because the thing it's waiting for cannot happen without it also taking an action it's blocked from taking. Timeouts are a heuristic way to distinguish the two: if a wait exceeds a threshold, the system often assumes deadlock even without formal cycle detection.

Q: Do modern programming languages solve deadlock automatically? A: No — mutexes, semaphores, and monitors in languages like Java, C++, and Python are tools that can prevent deadlock if used correctly (e.g., consistent lock ordering), but the language runtime doesn't stop you from acquiring locks in an order that creates a circular wait. Some tools (static analyzers, runtime deadlock detectors like Java's ThreadMXBean) help catch this, but it isn't automatic.

Q: Why do database transactions sometimes fail with a "deadlock detected" error instead of just hanging? A: Databases run continuous or periodic detection (wait-for graph analysis on row/table locks) precisely so they don't hang indefinitely; when a cycle is found, the database picks a victim transaction, aborts it, releases its locks, and returns an error the application is expected to retry — this is detection-and-recovery in action, chosen because true deadlocks between transactions are relatively rare.

Quick Revision

• Race condition: outcome depends on timing of concurrent access to shared data; critical section must satisfy mutual exclusion, progress, bounded waiting.
• Mutex: binary, ownership-based lock for one critical section at a time.
• Semaphore: integer counter with atomic wait()/signal(); binary ≈ mutex, counting manages a resource pool; no ownership.
• Monitor: language-level construct bundling data + procedures + implicit lock, plus condition variables for conditional waiting.
• Deadlock requires all four Coffman conditions at once: mutual exclusion, hold-and-wait, no preemption, circular wait.
• Breaking any single Coffman condition prevents deadlock — basis of prevention strategies.
• Single-instance resource cycle in a resource-allocation graph = deadlock; multi-instance cycle is necessary but not sufficient.
• Banker's Algorithm (avoidance): only grants a request if the resulting state is still safe (a completion sequence exists).
• Unsafe state ≠ deadlock — unsafe just means deadlock could occur depending on future requests.
• Detection uses a wait-for graph; recovery options are process termination or resource preemption/rollback.
• Ostrich algorithm: many general-purpose OS kernels simply ignore deadlock risk because it's rare enough that manual recovery (reboot/kill) is cheaper than prevention overhead.
• Livelock: processes stay active and keep changing state but never make progress — distinct from deadlock's frozen state.

Related Topics

Prerequisites: Process Management and Scheduling, Introduction to Operating Systems

Related Topics: Threads and Concurrency, Inter-Process Communication, Memory Management

Next Topics: Virtualization