Deadlock (Cyclic Acquisition)

When two programs freeze forever because they each have what the other one wants.

The idea

Imagine transferring money from Alice's bank account to Bob's. To prevent race conditions, Thread 1 locks Alice's account, then tries to lock Bob's account. At the exact same moment, Bob is transferring money to Alice! Thread 2 locks Bob's account, then tries to lock Alice's account. Thread 1 is waiting for Bob's account. Thread 2 is waiting for Alice's account. Neither thread will ever release their first lock until they get the second. They are completely frozen. This is a Deadlock caused by a cyclic dependency.

Step 1: Thread 1 wants to move money from A to B. Thread 2 wants to move money from B to A.

How it works (The Four Coffman Conditions)

For a deadlock to occur, four things must be true simultaneously (The Coffman Conditions):

  1. Mutual Exclusion: Only one thread can hold a lock at a time.
  2. Hold and Wait: A thread holding a lock can wait for another lock.
  3. No Preemption: A lock cannot be forcibly taken away; it must be willingly released.
  4. Circular Wait: Thread 1 waits on Thread 2, which waits on Thread 1.
// BAD: Classic Deadlock scenario
function transferMoney(fromAccount, toAccount) {
    // Thread 1 locks A. Thread 2 locks B.
    lock(fromAccount); 
    
    // Thread 1 waits for B forever. Thread 2 waits for A forever.
    lock(toAccount);   
    
    fromAccount.balance -= 100;
    toAccount.balance += 100;
    
    unlock(toAccount);
    unlock(fromAccount);
}

Cost

When a deadlock occurs, the involved threads are permanently blocked. If those threads are part of a web server's worker pool, they will never handle another request again. If enough deadlocks happen over time, your server will slowly run out of available threads and become completely unresponsive, requiring a hard reboot.

Watch out for