{"title":"Deadlock","description":"","content":"Deadlock is one of the most dangerous concurrency bugs because it's silent. There's no exception, no error message, no crash. The system just stops making progress.\n\nIn this chapter, we will build a clear mental model of what deadlock is, why it happens, how to detect it, and most importantly, how to prevent it.\n\n---\n\n# What is Deadlock?\n\n\n> **Real-World Analogy**\n>\n> Imagine a narrow one-lane bridge where cars can enter from both ends, but there’s no space to pass or reverse once you’re on it.\n>\n> - Car A enters from the left and reaches the middle.\n> - Car B enters from the right and also reaches the middle.\n> - Now they face each other.\n>\n> Neither car can move forward because the other blocks the path. Neither can reverse because cars behind them have already entered and are blocking the exit. Everyone is stuck, and the bridge is effectively unusable until someone manually intervenes.\n>\n> That’s a deadlock: each “car” holds a position it won’t give up, while waiting for the other to move, creating a cycle where no progress is possible.\n\n\nDeadlock in multi-threading is a situation where two or more threads are blocked forever, each waiting for a resource held by another thread in the cycle.\n\n\n```mermaid\nflowchart LR\n T1[Thread 1]:::primary --> |holds| L1[Lock A]:::orange\n L1 --> |wanted by| T2[Thread 2]:::primary\n T2 --> |holds| L2[Lock B]:::orange\n L2 --> |wanted by| T1\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n```\n\n\nIn this diagram, Thread 1 holds Lock A and wants Lock B. Thread 2 holds Lock B and wants Lock A. Neither can proceed. This circular wait is the essence of deadlock.\n\n\n> **The formal definition**\n>\n> A deadlock is a state where a set of threads is blocked because each thread is holding a resource and waiting for a resource held by another thread in the set.\n\n\nKey characteristics of deadlock:\n\n- **Permanent:** Unlike a temporary block, deadlock never resolves on its own\n- **Silent:** No exceptions are thrown; threads just stop making progress\n- **Mutual:** All threads in the deadlock are both victims and perpetrators\n- **Cyclic:** There's always a cycle in the wait-for graph\n\n---\n\n# Coffman's Four Conditions\n\nIn 1971, Edward Coffman identified four conditions that must ALL hold simultaneously for deadlock to occur. Understanding these conditions is crucial because breaking any one of them prevents deadlock.\n\n\n```mermaid\nflowchart TD\n A[Mutual Exclusion]:::orange --> E[DEADLOCK]:::red\n B[Hold and Wait]:::orange --> E\n C[No Preemption]:::orange --> E\n D[Circular Wait]:::orange --> E\n\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\n### 1. Mutual Exclusion\n\nAt least one resource must be held in a non-shareable mode. Only one thread can use the resource at a time. If another thread requests it, the requesting thread must wait.\n\n**Example:** A mutex, by definition, can only be held by one thread. A database row lock in exclusive mode. A file opened for exclusive write access.\n\n**How to break it:** Use shareable resources where possible. Read-write locks allow multiple readers. Immutable data needs no locking.\n\n### 2. Hold and Wait\n\nA thread must be holding at least one resource while waiting to acquire additional resources held by other threads.\n\n**Example:** Thread holds Lock A and then tries to acquire Lock B (which is held by another thread).\n\n**How to break it:** Acquire all resources atomically before proceeding. If you can't get all locks, release everything and retry. This is the \"all-or-nothing\" approach.\n\n### 3. No Preemption\n\nResources cannot be forcibly taken away from threads. A thread holding a resource keeps it until it voluntarily releases it.\n\n**Example:** Once a thread acquires a mutex, no other thread or the OS can force it to release the mutex.\n\n**How to break it:** Use try-lock with timeout. If you can't acquire a lock within a deadline, back off and release the locks you already hold.\n\n### 4. Circular Wait\n\nA cycle exists in the wait-for graph. Thread 1 waits for Thread 2, which waits for Thread 3, which waits for Thread 1.\n\n**Example:** Thread A holds Lock 1 and wants Lock 2. Thread B holds Lock 2 and wants Lock 1.\n\n**How to break it:** Impose a total ordering on all locks. Always acquire locks in a consistent order. If every thread acquires locks in the same order, cycles cannot form.\n\n\n| Condition | Meaning | How to Break It |\n|-----------|---------|-----------------|\n| Mutual Exclusion | Resource held exclusively by one thread | Use shareable resources, read-write locks |\n| Hold and Wait | Hold one resource while waiting for another | Acquire all locks atomically or release all before retrying |\n| No Preemption | Resources can't be forcibly taken | Use try-lock with timeout, back off on failure |\n| Circular Wait | Cycle exists in wait-for graph | Impose total lock ordering, always acquire in same order |\n\n\n---\n\n# Why Deadlock Happens\n\nDeadlock doesn't happen in simple programs with one lock. It emerges from the interaction of multiple locks, often spread across different parts of a codebase.\n\n### Common Causes\n\n#### **1. Inconsistent Lock Ordering**\n\nThe most common cause. Different code paths acquire locks in different orders.\n\n\n```shell\n// Code path A\nlock(accountA);\nlock(accountB);\n\n// Code path B (different order!)\nlock(accountB);\nlock(accountA);\n```\n\n\nIf Thread 1 runs path A and Thread 2 runs path B simultaneously, deadlock can occur.\n\n#### **2. Nested Locks Across Modules**\n\nModule A calls Module B while holding a lock. Module B tries to acquire a lock that's held by someone waiting for Module A.\n\n\n```shell\nModule A:\n lock(lockA)\n call Module B\n\nModule B:\n lock(lockB) // lockB might be held by thread waiting for lockA\n```\n\n\nThis is particularly insidious because the developers of Module A and Module B might not even know about each other's locks.\n\n#### **3. Lock in Callback**\n\nYou hold a lock and call a user-provided callback. The callback tries to acquire a lock that creates a cycle.\n\n\n```shell\nlock(myLock)\ncallback.execute() // What if callback needs myLock? Or another lock that waits for myLock?\n```\n\n\n#### **4. Database Transactions**\n\nDatabase deadlocks are common. Transaction A updates rows 1, 2. Transaction B updates rows 2, 1. Classic deadlock.\n\n\n> **Why Deadlocks are Hard to Detect During Development**\n>\n> Deadlocks are timing-dependent. They only occur when threads interleave in a specific way. During development:\n>\n> - You often test with a single thread\n> - Even with multiple threads, the \"bad\" interleaving might never happen\n> - Adding debug logging changes timing and can make deadlocks disappear\n> - Deadlocks often appear first in production under load\n\n\n---\n\n# How to Detect Deadlock\n\n### Thread Dumps\n\nThe most common detection method. A thread dump shows what each thread is doing and what locks it holds or waits for.\n\n\n#### Java\n\n\n```shell\n# Get thread dump from running Java process\njstack \n\n# Or from within the JVM\nkill -3 # Prints to stdout/stderr\n```\n\n\n**Deadlock in thread dump:**\n\n\n```shell\nFound one Java-level deadlock:\n=============================\n\"Thread-1\":\n waiting to lock monitor 0x00007f9b4c003f08 (object 0x000000076ab96c10, a java.lang.Object),\n which is held by \"Thread-0\"\n\"Thread-0\":\n waiting to lock monitor 0x00007f9b4c006358 (object 0x000000076ab96c20, a java.lang.Object),\n which is held by \"Thread-1\"\n\nJava stack information for the threads listed above:\n===================================================\n\"Thread-1\":\n at DeadlockExample.methodB(DeadlockExample.java:25)\n - waiting to lock <0x000000076ab96c10> (a java.lang.Object)\n - locked <0x000000076ab96c20> (a java.lang.Object)\n at DeadlockExample.lambda$main$1(DeadlockExample.java:35)\n at java.lang.Thread.run(Thread.java:748)\n\"Thread-0\":\n at DeadlockExample.methodA(DeadlockExample.java:15)\n - waiting to lock <0x000000076ab96c20> (a java.lang.Object)\n - locked <0x000000076ab96c10> (a java.lang.Object)\n at DeadlockExample.lambda$main$0(DeadlockExample.java:33)\n at java.lang.Thread.run(Thread.java:748)\n```\n\n\nThe JVM actually detects the deadlock and tells you exactly which threads are involved and where.\n\n\n### Resource Allocation Graphs\n\nA resource allocation graph visualizes which threads hold and wait for which resources. A cycle in the graph means deadlock.\n\n\n```mermaid\nflowchart LR\n subgraph Threads\n T1[Thread 1]:::primary\n T2[Thread 2]:::primary\n end\n\n subgraph Resources\n R1[Lock A]:::orange\n R2[Lock B]:::orange\n end\n\n T1 -->|holds| R1\n R1 -.->|wanted by| T2\n T2 -->|holds| R2\n R2 -.->|wanted by| T1\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n```\n\n\nSolid arrows indicate \"holds.\" Dashed arrows indicate \"wants.\" A cycle through both types of arrows indicates deadlock.\n\n### Programmatic Detection\n\n\n#### Java\n\n\n```java\nimport java.lang.management.ManagementFactory;\nimport java.lang.management.ThreadMXBean;\n\npublic class DeadlockDetector {\n public static void detectDeadlock() {\n ThreadMXBean threadMXBean = ManagementFactory.getThreadMXBean();\n long[] deadlockedThreadIds = threadMXBean.findDeadlockedThreads();\n\n if (deadlockedThreadIds != null) {\n System.out.println(\"Deadlock detected!\");\n for (long id : deadlockedThreadIds) {\n System.out.println(\"Thread ID: \" + id);\n }\n }\n }\n}\n```\n\n\nYou can run this periodically in a monitoring thread to detect deadlocks before they're reported by users.\n\n\n---\n\n# How to Prevent Deadlock\n\n### Strategy 1: Lock Ordering (Most Common)\n\nAssign a global order to all locks. Always acquire locks in ascending order. This breaks the circular wait condition.\n\n\n```java\npublic class BankAccount {\n private final long id;\n private int balance;\n private final Object lock = new Object();\n\n public BankAccount(long id, int initialBalance) {\n this.id = id;\n this.balance = initialBalance;\n }\n\n public static void transfer(BankAccount from, BankAccount to, int amount) {\n // Always lock in order of account ID to prevent deadlock\n BankAccount first = from.id < to.id ? from : to;\n BankAccount second = from.id < to.id ? to : from;\n\n synchronized (first.lock) {\n synchronized (second.lock) {\n if (from.balance >= amount) {\n from.balance -= amount;\n to.balance += amount;\n }\n }\n }\n }\n}\n```\n\n```python\nimport threading\n\nclass BankAccount:\n def __init__(self, account_id, initial_balance):\n self.id = account_id\n self.balance = initial_balance\n self.lock = threading.Lock()\n\ndef transfer(from_account, to_account, amount):\n # Always lock in order of account ID to prevent deadlock\n first = from_account if from_account.id < to_account.id else to_account\n second = to_account if from_account.id < to_account.id else from_account\n\n with first.lock:\n with second.lock:\n if from_account.balance >= amount:\n from_account.balance -= amount\n to_account.balance += amount\n```\n\n```cpp\n#include \n#include \n\nclass BankAccount {\n long id_;\n int balance_;\n mutable std::mutex mtx_;\n\npublic:\n BankAccount(long id, int balance) : id_(id), balance_(balance) {}\n\n static void transfer(BankAccount& from, BankAccount& to, int amount) {\n // Always lock in order of account ID to prevent deadlock\n BankAccount* first = from.id_ < to.id_ ? &from : &to;\n BankAccount* second = from.id_ < to.id_ ? &to : &from;\n\n std::lock_guard lock1(first->mtx_);\n std::lock_guard lock2(second->mtx_);\n\n if (from.balance_ >= amount) {\n from.balance_ -= amount;\n to.balance_ += amount;\n }\n }\n};\n\n// C++ also provides std::lock for deadlock-free locking of multiple mutexes:\nstatic void transferWithStdLock(BankAccount& from, BankAccount& to, int amount) {\n std::unique_lock lock1(from.mtx_, std::defer_lock);\n std::unique_lock lock2(to.mtx_, std::defer_lock);\n std::lock(lock1, lock2); // Acquires both without deadlock\n\n if (from.balance_ >= amount) {\n from.balance_ -= amount;\n to.balance_ += amount;\n }\n}\n\n// C++'s std::lock uses a deadlock avoidance algorithm internally, trying different orders and backing off as needed.\n```\n\n```csharp\nusing System;\n\npublic class BankAccount\n{\n private readonly long _id;\n private int _balance;\n private readonly object _lock = new object();\n\n public long Id => _id;\n\n public BankAccount(long id, int initialBalance)\n {\n _id = id;\n _balance = initialBalance;\n }\n\n public static void Transfer(BankAccount from, BankAccount to, int amount)\n {\n // Always lock in order of account ID to prevent deadlock\n BankAccount first = from._id < to._id ? from : to;\n BankAccount second = from._id < to._id ? to : from;\n\n lock (first._lock)\n {\n lock (second._lock)\n {\n if (from._balance >= amount)\n {\n from._balance -= amount;\n to._balance += amount;\n }\n }\n }\n }\n}\n```\n\n```go\npackage main\n\nimport (\n \"sync\"\n)\n\ntype BankAccount struct {\n id int64\n balance int\n mu sync.Mutex\n}\n\nfunc NewBankAccount(id int64, initialBalance int) *BankAccount {\n return &BankAccount{id: id, balance: initialBalance}\n}\n\nfunc Transfer(from, to *BankAccount, amount int) {\n // Always lock in order of account ID to prevent deadlock\n first, second := from, to\n if from.id > to.id {\n first, second = to, from\n }\n\n first.mu.Lock()\n defer first.mu.Unlock()\n\n second.mu.Lock()\n defer second.mu.Unlock()\n\n if from.balance >= amount {\n from.balance -= amount\n to.balance += amount\n }\n}\n```\n\n\nThe key insight: no matter which two accounts are involved, locks are always acquired in the same order (lower ID first). This makes cycles impossible.\n\n### Strategy 2: Try-Lock with Timeout\n\nInstead of blocking forever, try to acquire locks with a timeout. If you can't acquire all locks, release everything and retry (possibly with backoff).\n\n\n```java\nimport java.util.concurrent.TimeUnit;\nimport java.util.concurrent.locks.Lock;\nimport java.util.concurrent.locks.ReentrantLock;\n\npublic class BankAccountWithTimeout {\n private int balance;\n private final Lock lock = new ReentrantLock();\n\n public static boolean transfer(BankAccountWithTimeout from,\n BankAccountWithTimeout to,\n int amount,\n long timeout,\n TimeUnit unit) {\n long deadline = System.nanoTime() + unit.toNanos(timeout);\n\n while (true) {\n if (from.lock.tryLock()) {\n try {\n if (to.lock.tryLock()) {\n try {\n if (from.balance >= amount) {\n from.balance -= amount;\n to.balance += amount;\n return true;\n }\n return false; // Insufficient funds\n } finally {\n to.lock.unlock();\n }\n }\n } finally {\n from.lock.unlock();\n }\n }\n\n // Couldn't get both locks, check timeout\n if (System.nanoTime() >= deadline) {\n return false; // Timeout\n }\n\n // Back off before retrying\n try {\n Thread.sleep(1);\n } catch (InterruptedException e) {\n Thread.currentThread().interrupt();\n return false;\n }\n }\n }\n}\n```\n\n```python\nimport threading\nimport time\n\nclass BankAccountWithTimeout:\n def __init__(self, initial_balance):\n self.balance = initial_balance\n self.lock = threading.Lock()\n\ndef transfer_with_timeout(from_account, to_account, amount, timeout_seconds):\n deadline = time.time() + timeout_seconds\n\n while True:\n if from_account.lock.acquire(blocking=False):\n try:\n if to_account.lock.acquire(blocking=False):\n try:\n if from_account.balance >= amount:\n from_account.balance -= amount\n to_account.balance += amount\n return True\n return False # Insufficient funds\n finally:\n to_account.lock.release()\n finally:\n from_account.lock.release()\n\n # Couldn't get both locks, check timeout\n if time.time() >= deadline:\n return False # Timeout\n\n # Back off before retrying\n time.sleep(0.001)\n```\n\n```cpp\n#include \n#include \n#include \n\nclass BankAccountWithTimeout {\n int balance_;\n std::timed_mutex mtx_;\n\npublic:\n BankAccountWithTimeout(int balance) : balance_(balance) {}\n\n static bool transfer(BankAccountWithTimeout& from,\n BankAccountWithTimeout& to,\n int amount,\n std::chrono::milliseconds timeout) {\n auto deadline = std::chrono::steady_clock::now() + timeout;\n\n while (true) {\n if (from.mtx_.try_lock()) {\n std::unique_lock lock1(from.mtx_, std::adopt_lock);\n\n if (to.mtx_.try_lock()) {\n std::unique_lock lock2(to.mtx_, std::adopt_lock);\n\n if (from.balance_ >= amount) {\n from.balance_ -= amount;\n to.balance_ += amount;\n return true;\n }\n return false; // Insufficient funds\n }\n }\n\n // Couldn't get both locks, check timeout\n if (std::chrono::steady_clock::now() >= deadline) {\n return false; // Timeout\n }\n\n // Back off before retrying\n std::this_thread::sleep_for(std::chrono::milliseconds(1));\n }\n }\n};\n```\n\n```csharp\nusing System;\nusing System.Threading;\n\npublic class BankAccountWithTimeout\n{\n private int _balance;\n private readonly object _lock = new object();\n\n public BankAccountWithTimeout(int balance)\n {\n _balance = balance;\n }\n\n public static bool Transfer(BankAccountWithTimeout from,\n BankAccountWithTimeout to,\n int amount,\n TimeSpan timeout)\n {\n var deadline = DateTime.UtcNow + timeout;\n\n while (true)\n {\n bool gotFromLock = false;\n bool gotToLock = false;\n\n try\n {\n // Try to acquire first lock with timeout\n gotFromLock = Monitor.TryEnter(from._lock, TimeSpan.FromMilliseconds(10));\n if (gotFromLock)\n {\n // Try to acquire second lock\n gotToLock = Monitor.TryEnter(to._lock, TimeSpan.FromMilliseconds(10));\n if (gotToLock)\n {\n if (from._balance >= amount)\n {\n from._balance -= amount;\n to._balance += amount;\n return true;\n }\n return false; // Insufficient funds\n }\n }\n }\n finally\n {\n if (gotToLock) Monitor.Exit(to._lock);\n if (gotFromLock) Monitor.Exit(from._lock);\n }\n\n // Couldn't get both locks, check timeout\n if (DateTime.UtcNow >= deadline)\n {\n return false; // Timeout\n }\n\n // Back off before retrying\n Thread.Sleep(1);\n }\n }\n}\n```\n\n```go\npackage main\n\nimport (\n \"context\"\n \"sync\"\n \"time\"\n)\n\ntype BankAccountWithTimeout struct {\n balance int\n mu sync.Mutex\n}\n\nfunc NewBankAccountWithTimeout(balance int) *BankAccountWithTimeout {\n return &BankAccountWithTimeout{balance: balance}\n}\n\nfunc TransferWithTimeout(ctx context.Context, from, to *BankAccountWithTimeout, amount int) bool {\n deadline, ok := ctx.Deadline()\n if !ok {\n deadline = time.Now().Add(5 * time.Second) // Default timeout\n }\n\n for {\n // Try to acquire first lock\n if from.mu.TryLock() {\n // Try to acquire second lock\n if to.mu.TryLock() {\n // Got both locks\n defer to.mu.Unlock()\n defer from.mu.Unlock()\n\n if from.balance >= amount {\n from.balance -= amount\n to.balance += amount\n return true\n }\n return false // Insufficient funds\n }\n // Couldn't get second lock, release first\n from.mu.Unlock()\n }\n\n // Check timeout\n if time.Now().After(deadline) {\n return false // Timeout\n }\n\n // Check context cancellation\n select {\n case <-ctx.Done():\n return false\n default:\n }\n\n // Back off before retrying\n time.Sleep(time.Millisecond)\n }\n}\n\n// Usage:\n// ctx, cancel := context.WithTimeout(context.Background(), 5*time.Second)\n// defer cancel()\n// success := TransferWithTimeout(ctx, accountA, accountB, 100)\n```\n\n\nThis approach breaks the \"no preemption\" condition. If we can't get all locks, we release what we have.\n\n### Strategy 3: All-or-Nothing Acquisition\n\nAcquire all required locks at once, or none at all. This breaks the \"hold and wait\" condition.\n\n\n```java\n// Java doesn't have built-in all-or-nothing locking,\n// but you can implement it with tryLock:\n\npublic class AllOrNothingLock {\n public static boolean acquireAll(Lock... locks) {\n int acquired = 0;\n try {\n for (Lock lock : locks) {\n if (!lock.tryLock()) {\n // Failed to acquire, release all and return false\n for (int i = 0; i < acquired; i++) {\n locks[i].unlock();\n }\n return false;\n }\n acquired++;\n }\n return true;\n } catch (Exception e) {\n // Release any acquired locks on exception\n for (int i = 0; i < acquired; i++) {\n locks[i].unlock();\n }\n throw e;\n }\n }\n}\n```\n\n```cpp\n#include \n\nclass MultiLockResource {\n std::mutex mtx1_, mtx2_, mtx3_;\n\npublic:\n void operationNeedingAllLocks() {\n // std::lock acquires all or none, with deadlock avoidance\n std::scoped_lock lock(mtx1_, mtx2_, mtx3_);\n\n // Critical section with all three locks held\n doWork();\n }\n};\n```\n\n```csharp\nusing System;\nusing System.Collections.Generic;\nusing System.Threading;\n\npublic class AllOrNothingLock\n{\n public static bool AcquireAll(params object[] locks)\n {\n var acquired = new List

Deadlock

Get Premium