Deadlock and Prevention Techniques

Overview

A deadlock is a situation where two or more threads are blocked forever, each waiting for a resource held by the other. No thread can proceed, and the system (or subsystem) effectively halts. Unlike a crash, a deadlocked system appears alive (processes exist, memory is allocated) but produces zero throughput for the affected threads.

Formal definition: A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause.

Deadlock is one of the most frequently asked topics in Low-Level Design (LLD) interviews because it tests:

• Understanding of concurrency primitives (locks, mutexes, semaphores)
• Ability to reason about multi-threaded execution order and non-determinism
• Knowledge of classic CS theory (Coffman conditions, Banker's Algorithm)
• Practical debugging skills (identifying and resolving real deadlocks in production)
• System design trade-offs (safety vs. liveness vs. performance)
• Awareness of how deadlocks manifest differently in single-machine vs. distributed systems

Interviewers expect candidates to not only define deadlock but also explain detection, prevention, avoidance, and recovery - and apply these concepts to real problems like the Dining Philosophers or bank transfers. A strong answer demonstrates the ability to move from theory (Coffman conditions) to practice (lock ordering in code) seamlessly.

Common interview formats:

• "What is deadlock? How do you prevent it?" (theory)
• "Here's code with two locks - can it deadlock? Fix it." (debugging)
• "Design a thread-safe bank transfer system without deadlocks." (design)
• "How does MySQL detect and handle deadlocks?" (real-world systems)

---

Coffman's Four Conditions

A deadlock can occur if and only if all four of the following conditions hold simultaneously (Coffman et al., 1971):

1. Mutual Exclusion

At least one resource must be held in a non-shareable mode. Only one thread can use the resource at a time. If the resource were shareable (e.g., a read-only file), multiple threads could access it simultaneously and no blocking would occur.

Example: A write lock on a database row - only one transaction can hold it. A printer - only one job can print at a time.

When it's unavoidable: Some resources are inherently non-shareable (printers, write locks, hardware devices).

2. Hold and Wait

A thread holding at least one resource is waiting to acquire additional resources held by other threads. The thread neither releases its current resources nor proceeds without the new ones.

Example: Thread A holds Lock 1 and requests Lock 2, which is held by Thread B. Thread A will not release Lock 1 while waiting.

Why it's dangerous: The held resource is unavailable to others, creating a chain of dependencies.

3. No Preemption

Resources cannot be forcibly taken from a thread; they must be released voluntarily by the thread holding them. The system has no mechanism to revoke an allocated resource.

Example: Once a thread acquires a mutex, no other thread or the OS can revoke it - the holder must call unlock(). Compare this to CPU scheduling where the OS can preempt a running thread.

Key distinction: CPU time is preemptible; locks and memory allocations typically are not.

4. Circular Wait

A circular chain of threads exists where each thread holds a resource needed by the next thread in the chain, forming a closed loop.

Example: Thread A → waits for Lock 2 (held by B) → Thread B → waits for Lock 1 (held by A). With N threads: T1→T2→T3→...→TN→T1.

Key insight: Breaking any one of these four conditions prevents deadlock entirely.

---

ASCII Diagrams

Deadlock Scenario

┌──────────────────────────────────────────────────┐
│                DEADLOCK STATE                     │
├──────────────────────────────────────────────────┤
│                                                  │
│   Thread A                    Thread B           │
│   ┌───────┐                   ┌───────┐         │
│   │ HOLDS │──── Lock 1        │ HOLDS │── Lock 2│
│   │ WAITS │──── Lock 2        │ WAITS │── Lock 1│
│   └───────┘                   └───────┘         │
│                                                  │
│        ┌─────────┐       ┌─────────┐            │
│        │ Lock 1  │       │ Lock 2  │            │
│        └─────────┘       └─────────┘            │
│            │                   │                 │
│     held by A            held by B              │
│     wanted by B          wanted by A            │
│                                                  │
│   A ──waits──► Lock 2 ──held──► B               │
│   B ──waits──► Lock 1 ──held──► A               │
│                                                  │
│          *** CIRCULAR WAIT = DEADLOCK ***        │
└──────────────────────────────────────────────────┘

Resource Allocation Graph (with Cycle)

    Request Edge (──►)        Assignment Edge (◄──)

         ┌───────────────────────────┐
         │                           │
         ▼                           │
    ┌─────────┐    holds    ┌─────────────┐
    │ Lock 1  │◄────────────│  Thread A   │
    └─────────┘             └─────────────┘
         │                        ▲
         │ held by A              │ waits for Lock 2
         │                        │
         │                   ┌─────────┐
         │                   │ Lock 2  │
         │                   └─────────┘
         │                        ▲
         │ wanted by B            │ holds
         ▼                        │
    ┌─────────────┐         ┌─────────┐
    │  Thread B   │────────►│ Lock 2  │
    └─────────────┘ waits   └─────────┘
         │              for Lock 1
         │                        
         └────── wants ──────► Lock 1 (held by A)

    CYCLE: A → Lock2 → B → Lock1 → A  ← DEADLOCK!

---

Deadlock vs Livelock vs Starvation

Livelock Example: Two threads both detect contention, release their locks, wait, retry - and keep colliding in the same pattern forever.

Starvation Example: A ReentrantLock in unfair mode where new arrivals can jump the queue, causing a waiting thread to be perpetually bypassed.

---

Deadlock Detection

Wait-For Graph

Construct a directed graph where:

• Nodes = threads
• Edge from T1 → T2 means "T1 is waiting for a resource held by T2"

A cycle in this graph indicates deadlock.

Cycle Detection Algorithm

function detectDeadlock(waitForGraph):
    visited = {}
    recursionStack = {}

    for each thread T in graph:
        if not visited[T]:
            if dfs(T, visited, recursionStack, waitForGraph):
                return TRUE  // deadlock detected

    return FALSE

function dfs(node, visited, recursionStack, graph):
    visited[node] = true
    recursionStack[node] = true

    for each neighbor in graph[node]:
        if not visited[neighbor]:
            if dfs(neighbor, visited, recursionStack, graph):
                return TRUE
        else if recursionStack[neighbor]:
            return TRUE  // cycle found = deadlock

    recursionStack[node] = false
    return FALSE

Timeout-Based Detection

A simpler but less precise approach:

function acquireWithTimeout(lock, timeout):
    startTime = currentTime()
    while not lock.tryAcquire():
        if currentTime() - startTime > timeout:
            reportPotentialDeadlock(currentThread, lock)
            return FAILURE
        sleep(BACKOFF_INTERVAL)
    return SUCCESS

Timeouts don't prove deadlock exists but flag likely candidates for investigation.

---

Deadlock Prevention

Prevention eliminates deadlock by ensuring at least one Coffman condition can never hold.

Break Mutual Exclusion

Use shareable (read-only) resources where possible.

// Instead of exclusive lock for reads:
readWriteLock = new ReadWriteLock()

function readData():
    readWriteLock.readLock().acquire()   // multiple readers allowed
    data = sharedResource.read()
    readWriteLock.readLock().release()
    return data

function writeData(value):
    readWriteLock.writeLock().acquire()  // exclusive for writes only
    sharedResource.write(value)
    readWriteLock.writeLock().release()

Break Hold and Wait

Acquire all required locks atomically, or release all before requesting new ones.

function acquireAllOrNone(locks[]):
    sort(locks, by=lockId)  // consistent ordering
    for lock in locks:
        if not lock.tryAcquire():
            // rollback: release all previously acquired
            releaseAll(alreadyAcquired)
            return FAILURE
        alreadyAcquired.add(lock)
    return SUCCESS

Break No Preemption

Allow lock preemption via timeout - if a thread can't get a lock, it releases what it holds.

function acquireWithPreemption(lock1, lock2):
    lock1.acquire()
    if not lock2.tryAcquire(timeout=100ms):
        lock1.release()        // preempt own resource
        sleep(randomBackoff())
        return RETRY
    return SUCCESS

Break Circular Wait

Impose a global ordering on all locks. Always acquire in ascending order.

// Assign a unique ID to each lock
function acquireInOrder(lockA, lockB):
    if lockA.id < lockB.id:
        first = lockA
        second = lockB
    else:
        first = lockB
        second = lockA

    first.acquire()
    second.acquire()

This is the most commonly used prevention technique in practice.

---

Deadlock Avoidance

Avoidance allows all four Coffman conditions to exist but makes dynamic decisions to ensure the system never enters an unsafe state. Unlike prevention (which is structural), avoidance requires runtime information about future resource needs.

Banker's Algorithm (Concept)

Dijkstra's Banker's Algorithm treats the OS as a banker who must ensure it can always satisfy at least one customer's maximum demand. Before granting any resource request, the algorithm checks whether the resulting state is "safe."

Key terms:

• Available: vector of resources currently free in the system
• Max: matrix of maximum demand of each process (declared upfront)
• Allocation: matrix of resources currently held by each process
• Need: Max - Allocation (remaining demand before process can complete)

Safe State: A state where there exists at least one execution sequence (safe sequence) in which all processes can finish without deadlock. An unsafe state does not guarantee deadlock but means deadlock is possible.

Limitation: Requires processes to declare maximum resource needs in advance - often impractical in general-purpose systems but useful in embedded/real-time systems.

Pseudocode

function isSafeState(available[], max[][], allocation[][]):
    n = number of processes
    m = number of resource types
    need[][] = max[][] - allocation[][]
    work[] = copy(available)
    finish[] = [false] * n

    while true:
        found = false
        for i = 0 to n-1:
            if not finish[i] and need[i] <= work:
                // process i can finish
                work = work + allocation[i]
                finish[i] = true
                found = true

        if not found:
            break

    return all(finish)  // safe if all can finish

function requestResource(processId, request[]):
    if request > need[processId]:
        return ERROR  // exceeds declared max

    if request > available:
        return WAIT   // not enough resources

    // tentatively allocate
    available -= request
    allocation[processId] += request
    need[processId] -= request

    if isSafeState(available, max, allocation):
        return GRANTED
    else:
        // rollback
        available += request
        allocation[processId] -= request
        need[processId] += request
        return WAIT

---

Deadlock Recovery

When deadlock is detected, the system must recover. The choice of strategy depends on the cost of recovery vs. the cost of continued deadlock.

1. Process Termination

• Abort all deadlocked processes - simple but expensive; all work is lost
• Abort one at a time - terminate the lowest-cost process, recheck for deadlock, repeat if needed
• Selection criteria for victim: priority, elapsed time, resources held, resources needed to complete, number of times already chosen as victim

2. Rollback

Roll back one or more processes to a previous checkpoint (safe state) and restart them.

• Requires checkpointing infrastructure (periodic state snapshots)
• Common in database systems - transaction rollback undoes all changes via the undo log
• Cascading rollback risk: if T1 is rolled back and T2 read data written by T1, T2 must also roll back
• Cost: wasted computation, but no data corruption

3. Resource Preemption

Forcibly take resources from a deadlocked process and give them to another.

• Selecting a victim: choose the process with least cost (least work done, fewest resources held, most resources needed)
• Starvation risk: ensure the same process isn't always chosen as victim - maintain a rollback counter and factor it into victim selection
• Feasibility: only works for resources whose state can be saved and restored (e.g., memory pages, database locks). Not feasible for resources like printers mid-job.

Comparison of Recovery Strategies

---

Practical Strategies

1. Lock Ordering

Assign a global numeric ID to every lock. Always acquire locks in ascending ID order. This is simple, effective, and widely used in production systems.

Implementation tip: For objects like bank accounts, use the object's unique ID (account number, primary key) as the lock order. For arbitrary objects, use System.identityHashCode() (Java) or memory address as a tiebreaker.

2. Try-Lock with Timeout

if not lock.tryAcquire(timeout=200ms):
    release all held locks
    backoff and retry

Prevents indefinite blocking. Combine with exponential + random backoff to avoid livelock. The randomness ensures that two competing threads don't keep colliding at the same retry intervals.

Trade-off: Adds complexity and potential for spurious failures under high contention. Best suited for systems where occasional retry is acceptable.

3. Lock Hierarchy

Define layers (e.g., Layer 1: database locks, Layer 2: cache locks, Layer 3: file locks). A thread holding a Layer N lock may only request Layer N+1 or higher - never a lower layer.

Enforcement: Use runtime assertions in debug builds that verify the current thread's highest-held lock level before acquiring a new lock. Some frameworks (e.g., LLVM's lock annotations) provide compile-time checking.

4. Reducing Lock Scope

• Hold locks for the minimum duration necessary - compute outside the critical section
• Use fine-grained locks (per-row vs. per-table, per-bucket vs. per-map)
• Prefer lock-free data structures (CAS operations, atomic variables) for simple counters and flags
• Use ConcurrentHashMap over synchronized HashMap
• Split large critical sections: acquire lock, read/write shared state, release lock, then do I/O or computation

5. Avoid Nested Locks

If you must nest, always follow a documented ordering. Code reviews should flag unordered nested lock acquisition. Static analysis tools (ThreadSanitizer, FindBugs, IntelliJ inspections) can detect potential lock-order inversions.

6. Use Higher-Level Concurrency Abstractions

When possible, avoid raw locks entirely:

• Actors (Akka): each actor processes messages sequentially - no shared mutable state
• Channels (Go): communicate by passing data, not by sharing memory
• STM (Software Transactional Memory): compose atomic operations without explicit locks
• Immutable data structures: eliminate the need for synchronization entirely

---

Pseudocode Implementation

Dining Philosophers - With Deadlock

// 5 philosophers, 5 forks (locks)
forks = [Lock(0), Lock(1), Lock(2), Lock(3), Lock(4)]

function philosopher(id):
    leftFork = forks[id]
    rightFork = forks[(id + 1) % 5]

    while true:
        think()
        leftFork.acquire()     // all pick up left fork
        rightFork.acquire()    // all wait for right fork → DEADLOCK
        eat()
        rightFork.release()
        leftFork.release()

Deadlock: If all 5 philosophers pick up their left fork simultaneously, each waits for the right fork held by their neighbor.

Dining Philosophers - Fixed with Lock Ordering

function philosopher(id):
    fork1 = forks[min(id, (id + 1) % 5)]
    fork2 = forks[max(id, (id + 1) % 5)]

    while true:
        think()
        fork1.acquire()   // always lower-ID fork first
        fork2.acquire()
        eat()
        fork2.release()
        fork1.release()

Why it works: Philosopher 4 would try to acquire fork 0 before fork 4 (since min(4,0)=0). This breaks the circular wait - at least one philosopher's ordering differs, preventing the cycle.

Bank Transfer - With Deadlock

function transfer(fromAccount, toAccount, amount):
    synchronized(fromAccount):        // Thread 1: locks A
        synchronized(toAccount):      // Thread 1: waits for B
            fromAccount.balance -= amount
            toAccount.balance += amount

// Thread 1: transfer(A, B, 100)   -  locks A, waits for B
// Thread 2: transfer(B, A, 50)    -  locks B, waits for A
// DEADLOCK!

Bank Transfer - Fixed with Lock Ordering

function transfer(fromAccount, toAccount, amount):
    first = min(fromAccount.id, toAccount.id)
    second = max(fromAccount.id, toAccount.id)

    lock1 = getAccount(first).lock
    lock2 = getAccount(second).lock

    synchronized(lock1):
        synchronized(lock2):
            fromAccount.balance -= amount
            toAccount.balance += amount

Both threads now acquire locks in the same order (by account ID), eliminating circular wait.

---

Real-World Examples

Database Deadlocks

• Scenario: Transaction T1 updates Row A then Row B; Transaction T2 updates Row B then Row A. Both acquire exclusive row-level locks.
• Detection: Most RDBMS (MySQL InnoDB, PostgreSQL) maintain a wait-for graph and detect cycles automatically. InnoDB checks for deadlocks on every lock wait.
• Recovery: The database aborts one transaction (the victim - typically the one with least work done) and returns a deadlock error (e.g., MySQL error 1213). The application retries.
• Prevention in practice: Access tables and rows in a consistent order across all transactions. Keep transactions short. Use SELECT ... FOR UPDATE judiciously.

Distributed System Deadlocks

• Scenario: Service A holds a distributed lock on Resource X and makes a synchronous RPC to Service B, which holds a lock on Resource Y and makes a synchronous RPC back to Service A. Both services block waiting for the other to respond.
• Challenge: No single node has the full wait-for graph. The dependency spans network boundaries.
• Solutions:
  • Timeout-based detection: all RPCs have deadlines; if exceeded, release locks and retry
  • Distributed deadlock detectors using probe-based algorithms (Chandy-Misra-Haas)
  • Architectural prevention: avoid holding locks across RPC calls; use async messaging
  • Service call hierarchy: define that Service A can call B, but B cannot synchronously call A

Thread Pool Deadlocks

• Scenario: A thread pool of size N. All N threads submit tasks that themselves require a thread from the same pool to complete (e.g., a task that submits a subtask and blocks waiting for its result).
• Result: All threads are blocked waiting for a free thread - pool exhaustion deadlock. No actual lock is involved, but the bounded resource (threads) creates the same effect.
• Fix: Use separate pools for parent and child tasks, use async/non-blocking patterns (CompletableFuture, callbacks), or use work-stealing pools (ForkJoinPool) that can create compensation threads.

Lock Ordering Violations in Real Code

• Scenario: A logging framework acquires a log-buffer lock, then calls a user-provided callback that acquires an application lock. Meanwhile, application code holds the application lock and calls the logger.
• Fix: Never call external/user code while holding a lock. Copy data under the lock, release, then call external code.

---

Interview Follow-ups

Q1: How would you detect a deadlock in a running Java application?

A: Use jstack <pid> to get thread dumps - it reports "Found one Java-level deadlock" with the cycle. Programmatically, use ThreadMXBean.findDeadlockedThreads() which returns thread IDs involved in deadlock cycles.

Q2: Can deadlock occur with a single thread?

A: Yes - if a thread tries to acquire a non-reentrant lock it already holds, it blocks on itself. This is a self-deadlock. Reentrant locks (like Java's ReentrantLock) prevent this by allowing the same thread to re-acquire.

Q3: What's the difference between deadlock prevention and deadlock avoidance?

A: Prevention structurally eliminates one of the four Coffman conditions (static, design-time). Avoidance allows all conditions to potentially exist but dynamically refuses unsafe resource allocations at runtime (e.g., Banker's Algorithm).

Hints-Only Questions

Q4: Design a lock manager that detects deadlocks in a multi-tenant database.

• Hint 1: Maintain a per-tenant wait-for graph; run cycle detection on lock contention events.
• Hint 2: Consider the trade-off between eager detection (on every wait) vs. periodic detection (timer-based).

Q5: How would you prevent deadlocks in a microservices architecture where services call each other?

• Hint 1: Define a service call hierarchy - Service A can call B, but B cannot call A synchronously.
• Hint 2: Use async messaging (event-driven) to break synchronous call cycles.

---

Counter Questions to Ask Interviewer

1. "Are the resources shareable (read/write) or exclusively held?" - Determines if mutual exclusion can be relaxed.
2. "Is there a known upper bound on the number of resources each thread needs?" - Determines if Banker's Algorithm is feasible.
3. "Can we tolerate occasional failures and retries, or must the system be deadlock-free by design?" - Distinguishes prevention (strict) from detection+recovery (pragmatic).
4. "Is this a single-process multi-threaded system or a distributed system?" - Distributed deadlock detection is fundamentally harder.
5. "What's the expected contention level?" - High contention favors lock-free designs; low contention makes simple locking acceptable.

---

References & Whitepapers

1. Coffman, E.G., Elphick, M.J., Shoshani, A. (1971). "System Deadlocks." ACM Computing Surveys, 3(2), 67-78. - The foundational paper defining the four necessary conditions.
2. Dijkstra, E.W. (1965). "Cooperating Sequential Processes." - Introduces the Banker's Algorithm for deadlock avoidance and the Dining Philosophers problem.
3. Silberschatz, A., Galvin, P.B., Gagne, G. Operating System Concepts (10th Edition), Chapter 8: Deadlocks. - Comprehensive textbook treatment with examples and algorithms.
4. Holt, R.C. (1972). "Some Deadlock Properties of Computer Systems." ACM Computing Surveys, 4(3). - Formalizes resource allocation graphs.
5. Herlihy, M., Shavit, N. The Art of Multiprocessor Programming. - Modern treatment of lock-free algorithms and concurrent data structures.

---

Related Topics

• 01 - Introduction to Multithreading
• 02 - Locks, Mutexes, and Semaphores
• 03 - Thread Synchronization Patterns
• 04 - Producer-Consumer Problem
• 05 - Reader-Writer Problem
• 07 - Thread Pool Design
• 08 - Concurrent Data Structures