What is a Deadlock - Deadlocks And Prevention | OneNoughtOne

0/246

System Design (LLD)Concurrency Fundamentals

Deadlocks and Prevention

LevelAdvanced

Duration90 mins

TopicConcurrency Fundamentals

1 / 4

What is a Deadlock

The Dining Philosophers' Dilemma

In 1965, Edsger Dijkstra introduced one of computer science's most enduring thought experiments: five philosophers sit around a circular table, each with a plate of spaghetti. Between each pair of adjacent philosophers lies a single fork. To eat, a philosopher needs both the fork to their left and the fork to their right. They think, get hungry, pick up forks, eat, put down forks, and resume thinking.

The problem? If every philosopher simultaneously picks up their left fork and waits for their right fork, no one can eat. Each holds a resource (left fork) while waiting for another resource (right fork) held by their neighbor. They're stuck forever—a deadlock.

What You Will Learn

By the end of this page, you will understand exactly what a deadlock is, why it occurs, and how to recognize deadlock scenarios in real software systems. You'll develop the intuition to spot potential deadlocks during code review and system design—before they manifest in production.

Deadlocks aren't merely academic curiosities. They're production nightmares that have caused system outages, database corruption, and millions of dollars in losses. Understanding deadlocks at a deep level is essential for any engineer building concurrent or distributed systems.

Formal Definition of Deadlock

A deadlock is a situation in which two or more competing processes or threads are each waiting for the other to release a resource, resulting in a permanent state where no process can proceed. More formally:

A set of processes is deadlocked when every process in the set is waiting for an event that can only be caused by another process in the set.

This definition captures the essence: circular waiting with no external intervention possible. Unlike a temporary delay (where a resource will eventually become available), a deadlock is permanent. The system will remain frozen indefinitely without external action.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// Two resources that require exclusive access
const resourceA = new Mutex();
const resourceB = new Mutex();
 
// Thread 1: Acquires A, then tries to acquire B
async function thread1() {
    await resourceA.acquire();
    console.log("Thread 1: Acquired resource A");
    
    // Some processing...
    await sleep(100);
    
    // Now waiting for B, which Thread 2 holds
    await resourceB.acquire();  // BLOCKED FOREVER
    console.log("Thread 1: Acquired resource B");
    
    resourceB.release();
    resourceA.release();
}
 
// Thread 2: Acquires B, then tries to acquire A
async function thread2() {
    await resourceB.acquire();
    console.log("Thread 2: Acquired resource B");
    
    // Some processing...
    await sleep(100);
    
    // Now waiting for A, which Thread 1 holds
    await resourceA.acquire();  // BLOCKED FOREVER
    console.log("Thread 2: Acquired resource A");
    
    resourceA.release();
    resourceB.release();
}
 
// Execute concurrently - DEADLOCK!
Promise.all([thread1(), thread2()]);

In the example above:

Thread 1 acquires resourceA and waits for resourceB
Thread 2 acquires resourceB and waits for resourceA
Neither can proceed because each holds what the other needs

The critical insight is that this isn't a bug in either thread's logic—each thread's code is perfectly reasonable in isolation. The deadlock emerges from the interaction between threads and the order in which they acquire resources.

Deadlock vs. Related Concepts

Deadlock is often confused with related but distinct concurrency problems. Understanding these distinctions is crucial for accurate diagnosis and appropriate solutions:

Deadlock vs. Related Concurrency Problems
Problem	Definition	Key Characteristic	Resolution
Deadlock	Circular wait where no thread can proceed	Permanent; requires external intervention	Break one of the four necessary conditions
Livelock	Threads actively respond to each other but make no progress	Threads are running but accomplishing nothing	Add randomization or backoff strategies
Starvation	A thread never gets the resources it needs	Other threads keep 'cutting in line'	Use fair scheduling or priority aging
Priority Inversion	High-priority thread blocked by low-priority thread	Medium-priority threads run while high-priority waits	Priority inheritance or priority ceiling protocols

The Hallway Analogy

Deadlock: Two people in a narrow hallway, each refusing to step aside, standing forever.

Livelock: Two polite people in a hallway, each stepping aside to let the other pass, but stepping the same direction repeatedly—left, then right, then left—making no progress.

Starvation: A person in the hallway keeps getting pushed aside by more aggressive passersby, never reaching their destination.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// Livelock: Both threads actively respond but make no progress
class Spoon {
    private owner: Diner | null = null;
    
    setOwner(diner: Diner) { this.owner = diner; }
    getOwner() { return this.owner; }
}
 
class Diner {
    private name: string;
    private isHungry: boolean = true;
    
    constructor(name: string) { this.name = name; }
    
    eatWith(spoon: Spoon, partner: Diner) {
        while (this.isHungry) {
            // If partner is hungry, politely give them the spoon
            if (spoon.getOwner() !== this) {
                continue; // Wait for spoon
            }
            
            if (partner.isHungry) {
                console.log(`${this.name}: I'll let ${partner.name} eat first`);
                spoon.setOwner(partner);
                continue; // Keep looping!
            }
            
            // Actually eat (never reached if both keep yielding)
            this.isHungry = false;
            console.log(`${this.name}: Eating!`);
            spoon.setOwner(partner);
        }
    }
}
 
// Both diners keep yielding to each other forever!
const husband = new Diner("Husband");
const wife = new Diner("Wife");
const spoon = new Spoon();
spoon.setOwner(husband);
 
// LIVELOCK: Both threads run but neither eats

The key distinction:

Deadlock: Threads are blocked waiting for resources
Livelock: Threads are actively running but making no progress
Starvation: At least one thread makes progress; others are indefinitely delayed

In production systems, livelocks can be harder to diagnose than deadlocks because CPU utilization remains high—the symptom looks like a performance issue rather than a fundamental locking problem.

Resources and Resource Types

To understand deadlocks deeply, we must first understand resources—the objects that threads compete for. Resources in concurrent systems come in two fundamental categories:

Preemptable Resources

•Can be taken away from the owning process without ill effects
•Process can be restored later with no corruption
•Examples: CPU time slices, memory pages (can be swapped)
•Handling: Operating system can preempt and reallocate
•Deadlock risk: Low—OS can break the deadlock by preemption

Non-Preemptable Resources

•Cannot be taken away without disrupting the process
•Forced removal causes corruption or inconsistency
•Examples: Locks, file handles, database transactions, printer mid-job
•Handling: Must wait for voluntary release
•Deadlock risk: High—these cause most real-world deadlocks

Deadlocks primarily involve non-preemptable resources because the system cannot forcibly take them away to break cycles. When a thread holds a mutex and is waiting for another mutex, the operating system cannot simply 'steal' the first mutex—doing so would violate the mutual exclusion guarantee and potentially corrupt shared data.

Resources can also be classified by cardinality:

Resource Cardinality

•Single-instance resources: Only one unit exists (e.g., a specific file, a singleton lock). Deadlock detection is simpler because the resource graph becomes a directed graph.
•Multi-instance resources: Multiple identical units exist (e.g., a pool of database connections, a semaphore with count > 1). Deadlock detection requires more sophisticated algorithms.

Resource Modeling

When analyzing systems for potential deadlocks, you must identify all resources that require exclusive access. These include: mutexes, read-write locks, database row/table locks, file locks, semaphores, connection pools, and any custom synchronization primitives. The resource model is the foundation for deadlock analysis.

Resource Allocation Graphs

The Resource Allocation Graph (RAG) is a powerful visual and mathematical tool for understanding and detecting deadlocks. It's a directed graph with two types of nodes:

Process nodes (circles): Represent threads, processes, or transactions
Resource nodes (squares): Represent resources with dots inside indicating instances

And two types of edges:

Request edge (P → R): Process P is waiting for resource R
Assignment edge (R → P): Resource R is currently held by process P

    ┌─────┐          ┌─────┐
    │ P1  │          │ P2  │
    └──┬──┘          └──┬──┘
       │                │
       │ holds          │ holds
       ▼                ▼
    ┌─────┐          ┌─────┐
    │ R1  │◄─────────│ R2  │
    │ [●] │  waits   │ [●] │
    └─────┘          └─────┘
 
P1 holds R1
P2 holds R2  
P2 waits for R1
 
No cycle → No deadlock
(P1 can finish, release R1, then P2 can acquire R1)

    ┌─────┐          ┌─────┐
    │ P1  │◄─────────│ P2  │
    └──┬──┘  waits   └──┬──┘
       │                │
       │ holds          │ holds
       ▼                ▼
    ┌─────┐          ┌─────┐
    │ R1  │─────────►│ R2  │
    │ [●] │  waits   │ [●] │
    └─────┘          └─────┘
 
P1 holds R1, waits for R2
P2 holds R2, waits for R1
 
Cycle exists: P1 → R2 → P2 → R1 → P1
DEADLOCK!

Key insight: For single-instance resources, a cycle in the RAG is both necessary and sufficient for deadlock. If there's a cycle, there's a deadlock; if there's no cycle, there's no deadlock.

For multi-instance resources, a cycle is necessary but not sufficient. Consider a resource with two instances and three processes—a cycle might exist, but if one process completes and releases its instance, the cycle can be broken.

    ┌─────┐     ┌─────┐     ┌─────┐
    │ P1  │     │ P2  │     │ P3  │
    └──┬──┘     └──┬──┘     └──┬──┘
       │           │           │
       │ holds     │ holds     │ waits
       ▼           ▼           ▼
    ┌───────────────────────────────┐
    │           R1 [●][●]           │
    │        (2 instances)          │
    └───────────────────────────────┘
 
P1 holds one instance of R1
P2 holds one instance of R1
P3 waits for R1
 
P3 → R1 → P1 or P3 → R1 → P2 (edges exist)
 
But NO DEADLOCK: When P1 or P2 finishes, P3 can proceed.

Cycle Detection is Not Enough

For multi-instance resources, you need more sophisticated algorithms like the Banker's algorithm to determine if a given state is safe or if deadlock has occurred. Simple cycle detection only works for single-instance resources.

Real-World Deadlock Examples

Deadlocks manifest in many forms across different system layers. Understanding these patterns helps you recognize potential deadlocks in code review and system design:

Database Transaction Deadlocks

•Scenario: Transaction T1 updates row A, then row B. Transaction T2 updates row B, then row A. Both run concurrently.
•Result: T1 holds lock on A, waits for B. T2 holds lock on B, waits for A. Deadlock.
•Real impact: Database engines detect this and abort one transaction, but your application must handle retries.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
-- Transaction 1 (Session A)
BEGIN TRANSACTION;
UPDATE accounts SET balance = balance - 100 WHERE id = 1;  -- Lock on row 1
-- Time delay...
UPDATE accounts SET balance = balance + 100 WHERE id = 2;  -- Waiting for row 2
COMMIT;
 
-- Transaction 2 (Session B) - Running concurrently
BEGIN TRANSACTION;
UPDATE accounts SET balance = balance - 50 WHERE id = 2;   -- Lock on row 2
-- Time delay...
UPDATE accounts SET balance = balance + 50 WHERE id = 1;   -- Waiting for row 1
COMMIT;
 
-- DEADLOCK: Session A holds row 1, waits for row 2
--           Session B holds row 2, waits for row 1
-- Database will detect and abort one transaction with error 1205 (SQL Server)

Distributed System Deadlocks

•Scenario: Service A holds lock on resource X, calls Service B. Service B holds lock on resource Y, calls Service A.
•Complexity: Locks span process boundaries; no single component sees the full picture.
•Detection: Requires distributed deadlock detection or timeouts.
•Real example: Microservices with synchronous calls that acquire locks, then call other services.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class BankAccount {
    private lock = new Mutex();
    private balance: number;
    
    async transfer(to: BankAccount, amount: number) {
        await this.lock.acquire();  // Lock source account
        try {
            if (this.balance >= amount) {
                await to.lock.acquire();  // Lock destination - DANGER!
                try {
                    this.balance -= amount;
                    to.balance += amount;
                } finally {
                    to.lock.release();
                }
            }
        } finally {
            this.lock.release();
        }
    }
}
 
const accountA = new BankAccount(1000);
const accountB = new BankAccount(1000);
 
// Concurrent transfers in opposite directions - DEADLOCK!
Promise.all([
    accountA.transfer(accountB, 100),  // Locks A, waits for B
    accountB.transfer(accountA, 50),   // Locks B, waits for A
]);

Operating System Level Deadlocks

•Process resources: Print jobs, tape drives, memory allocation
•I/O resources: File handles, network ports, device access
•System calls: Fork without sufficient memory, pipe buffer full with reader blocked
•Historical example: Early UNIX would deadlock if fork() was called when memory was fragmented

Production Disaster

In 2007, a deadlock in a hospital's medication system caused by concurrent prescription updates left nurses unable to access critical patient medication orders for over 30 minutes. The deadlock wasn't detected until the timeout threshold expired, by which time significant manual intervention was required. This illustrates why deadlock prevention and quick detection are critical in safety-critical systems.

How Deadlocks Are Detected

Before we dive into prevention (covered in subsequent pages), it's valuable to understand how systems detect deadlocks. Detection approaches vary by the level of the system:

Deadlock Detection Mechanisms by System Level
System Level	Detection Method	Typical Action
Database Engines	Wait-for graphs constructed from lock tables; cycle detection runs periodically or on demand	Abort youngest/cheapest transaction; return deadlock error code
Operating Systems	Resource allocation graph analysis; usually only for specific resource types	Kill one process or preempt resources if possible
Application Layer	Timeouts on lock acquisition; watchdog threads monitoring thread states	Log error, trigger alert, attempt recovery or restart
Distributed Systems	Distributed wait-for graph construction; probe-based algorithms; global snapshots	Abort one transaction; timeouts; coordinator-based resolution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class MutexWithTimeout {
    private locked = false;
    private waitQueue: Array<{
        resolve: () => void;
        reject: (err: Error) => void;
    }> = [];
    
    async acquire(timeoutMs: number = 30000): Promise<void> {
        if (!this.locked) {
            this.locked = true;
            return;
        }
        
        return new Promise((resolve, reject) => {
            const waiter = { resolve, reject };
            this.waitQueue.push(waiter);
            
            // Timeout acts as deadlock detection
            const timeoutId = setTimeout(() => {
                const index = this.waitQueue.indexOf(waiter);
                if (index !== -1) {
                    this.waitQueue.splice(index, 1);
                    reject(new Error(
                        'Potential deadlock: Lock acquisition timeout'
                    ));
                }
            }, timeoutMs);
            
            // Modify resolve to clear timeout
            const originalResolve = waiter.resolve;
            waiter.resolve = () => {
                clearTimeout(timeoutId);
                originalResolve();
            };
        });
    }
    
    release(): void {
        if (this.waitQueue.length > 0) {
            const next = this.waitQueue.shift()!;
            next.resolve();
        } else {
            this.locked = false;
        }
    }
}

Timeout-based detection is pragmatic but imprecise:

Advantages:

Simple to implement
Works across system boundaries
Catches other issues (slow operations, network partitions)

Disadvantages:

False positives: A slow operation isn't necessarily a deadlock
Delayed detection: Must wait for timeout before acting
Tuning difficulty: Too short triggers false alarms; too long delays recovery

Production Strategy

Most production systems use a combination: short timeouts (5-30 seconds) for quick detection, combined with logging and metrics to distinguish true deadlocks from performance issues. When timeouts fire repeatedly for the same lock patterns, that's strong evidence of an actual deadlock that needs code-level fixes.

The Cost of Deadlocks

Understanding the business and operational impact of deadlocks reinforces why mastering this topic is essential:

Direct Costs

•System unavailability: Users can't complete transactions, leading to lost revenue
•Transaction rollbacks: Work is wasted; must be retried, consuming additional resources
•Resource waste: Threads blocked in deadlock consume memory, connection pool slots, and other resources
•Cascading failures: A deadlocked component can cause upstream timeouts and failures
•Emergency response: On-call engineers investigating at 3 AM

Indirect Costs

•Debugging complexity: Deadlocks are notoriously hard to reproduce in development
•Trust erosion: Users and stakeholders lose confidence in system reliability
•Technical debt: Quick fixes (liberal timeouts, reduced concurrency) accumulate
•Opportunity cost: Time spent chasing deadlocks isn't spent building features

The insidious nature of deadlocks:

Unlike a crash (which is obvious and immediately investigated), a deadlock can be subtle. A system might deadlock under specific conditions that occur rarely—perhaps only under peak load, or with specific data patterns. The system appears to work 99% of the time, making the deadlock hard to prioritize and even harder to reproduce for debugging.

This is why prevention is far more valuable than detection. The next pages will explore the four necessary conditions for deadlock and strategies to eliminate them proactively.

The Heisenbug Problem

Deadlocks are often 'Heisenbugs'—they disappear when you try to observe them. Adding logging can change timing enough to prevent the deadlock. Attaching a debugger pauses threads and changes the race. This is why theoretical understanding (the four conditions, prevention strategies) is more reliable than trial-and-error debugging.

Summary: Understanding Deadlocks

We've established a comprehensive foundation for understanding deadlocks. Let's consolidate the key concepts:

Key Takeaways

•A deadlock is a permanent state where each process in a set is waiting for a resource held by another process in the set. No process can proceed without external intervention.
•Deadlock differs from livelock and starvation: Deadlocked threads are blocked (not running); livelocked threads are running but making no progress; starved threads are waiting while others proceed.
•Non-preemptable resources cause most deadlocks because the system cannot forcibly reclaim them without causing data corruption.
•Resource Allocation Graphs provide visual analysis: For single-instance resources, a cycle means deadlock. For multi-instance resources, cycles are necessary but not sufficient.
•Deadlocks occur across system layers: Database transactions, application-level locks, distributed services, and operating system resources all can deadlock.
•Detection is typically timeout-based at the application level, with more sophisticated graph analysis in databases and operating systems.
•Prevention is far more valuable than detection because deadlocks are hard to reproduce and debug after the fact.

What's next:

Now that we understand what deadlocks are and how to recognize them, the next page will dive deep into the four necessary conditions for deadlock (Coffman conditions). Understanding these conditions is the key to prevention—if we can eliminate any one of them, deadlock becomes impossible.

Page Complete

You now understand what deadlocks are, how they differ from related problems, and why they matter. The Dining Philosophers aren't just a clever puzzle—they represent a fundamental challenge in concurrent systems that you'll encounter throughout your career. Next, we'll examine the precise conditions that make deadlocks possible.