Deadlock

Ana transfers 30 from account 1 to account 2. At the same moment, Raj transfers 20 from account 2 to account 1. Each transfer locks the source account, then the destination. That is exactly what the locks page taught. Ana’s thread holds account 1 and waits for account 2. Raj’s thread holds account 2 and waits for account 1. Neither will ever let go.

That is a deadlock: a set of threads where each one waits for something another one holds. So none of them can move. There’s no exception, no error log, and no CPU use. The two requests just never return. Every later request that touches either account joins the queue behind them. In production, it looks like a service that slowly stops answering, until someone restarts it.

What makes this hard

• Deadlock needs four conditions at once: mutual exclusion, hold and wait, no preemption and circular wait. Break any one and deadlock is impossible.
• The practical fix is almost always breaking circular wait: take locks in one global order.
• Where no order exists, break hold and wait instead. Use tryLock with a timeout. If it fails, release everything, back off for a random time, and retry.
• Deadlock isn’t only about locks. Threads that wait on each other through queues, thread pools, condition variables or await can wait in a circle just as well.

Make it happen

You are the scheduler. Play A, B, A, B. Ana takes account 1, Raj takes account 2, and then each asks for the other’s. The board draws the wait-for graph: a thread waiting for a lock points at the thread that holds it. When the arrows close into a circle, nobody can ever move again.

Source firstLower id firsttryLock and back off

A · AnaStep A

1. lock(acct1)
2. lock(acct2)
3. balance1 -= 30; balance2 += 30
4. unlock(acct2)
5. unlock(acct1)

ready

B · RajStep B

1. lock(acct2)
2. lock(acct1)
3. balance2 -= 20; balance1 += 20
4. unlock(acct1)
5. unlock(acct2)

ready

Play A, B, A, BRun 1,000 schedulesReset

Ana (A) sends 30 from account 1 to account 2 while Raj (B) sends 20 back. Each transfer locks both accounts. Try A, B, A, B.

Now switch to Lower id first, and play the same order. Both transfers want account 1 first. So whoever gets it can always get account 2 too. The other thread waits, but only in a line, never in a circle.

Then try tryLock and back off. The second lock attempt fails instead of waiting. The thread releases what it holds, and the cycle never closes.

Here is the same deadlock in real code. A barrier holds each thread between its first and second lock, until both have their first. So it deadlocks on every run:

JMain.javaPyaccount.pyC#Program.csGoaccount.goTSaccount.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.lang.management.ManagementFactory;
import java.util.concurrent.CyclicBarrier;

// Ana sends 30 from account 1 to 2 while Raj sends 20 from 2 to 1. Each locks the source first.
public class Main {
    public static void main(String[] args) throws Exception {
        Account one = new Account(1, 100);
        Account two = new Account(2, 100);
        // Holds each thread between its first and second lock until both have their first, so
        // the deadlock happens on every run instead of once in a while.
        CyclicBarrier bothHoldOne = new CyclicBarrier(2);
        Thread ana = new Thread(() -> Account.transfer(one, two, 30, bothHoldOne), "ana");
        Thread raj = new Thread(() -> Account.transfer(two, one, 20, bothHoldOne), "raj");
        ana.setDaemon(true); // let the JVM exit even though these threads will never finish
        raj.setDaemon(true);
        ana.start();
        raj.start();
        ana.join(1000);
        // The JVM tracks who owns each monitor and who waits for it, so it can find the cycle.
        // This is what `jstack` prints as "Found one Java-level deadlock".
        long[] stuck = ManagementFactory.getThreadMXBean().findDeadlockedThreads();
        if (stuck == null || stuck.length != 2) throw new AssertionError("expected a deadlock");
        System.out.println("deadlocked: " + stuck.length + " threads, each waiting for the other's lock");
    }
}

class Account {
    final int id;
    private int balance; // guarded by this account's monitor

    Account(int id, int balance) {
        this.id = id;
        this.balance = balance;
    }

    // Locks the source, then the destination. Two transfers in opposite directions each take
    // one lock and wait forever for the other: a cycle.
    static void transfer(Account from, Account to, int amount, CyclicBarrier gap) {
        synchronized (from) {
            try { gap.await(); } catch (Exception e) { throw new RuntimeException(e); }
            synchronized (to) {
                from.balance -= amount;
                to.balance += amount;
            }
        }
    }
}

Each runtime tells you something different about it:

• Java: the JVM knows who owns each monitor and ReentrantLock, and who waits for it. So ThreadMXBean.findDeadlockedThreads() finds the cycle. jstack <pid> prints “Found one Java-level deadlock” with both stacks. That’s the first command to run on a hung Java service.
• Go: the runtime panics with “all goroutines are asleep - deadlock!” only when every goroutine is blocked. In a server, the HTTP listener is still running, so two stuck goroutines go unreported. A goroutine dump (kill -QUIT, or /debug/pprof/goroutine?debug=2) shows them in Mutex.Lock.
• Python and C#: no built-in detector. py-spy dump --pid or dotnet-dump shows every thread’s stack. The stuck ones are sitting in acquire() or Monitor.Enter.
• TypeScript: deadlock without threads. Two async tasks each hold an async lock, and await the other’s. Node doesn’t notice anything. Two promises simply never settle, and the requests that awaited them time out.

The four conditions

In 1971 Coffman, Elphick and Shoshani showed that deadlock requires all four of these at once:

Condition	Means	In the transfer
Mutual exclusion	A resource can be held by only one thread at a time	Each account lock has one owner
Hold and wait	A thread holds one resource while waiting for another	Holds the source while waiting for the destination
No preemption	Nobody can take a resource away from its holder	lock() waits forever; nothing forces an unlock
Circular wait	A cycle: T1 waits for T2, which waits for … T1	Ana waits for Raj, Raj waits for Ana

That table is also the menu of fixes. Every deadlock prevention technique removes one row.

Each fix breaks one condition

Scroll or pinch to zoom, drag to pan

• Color key
• One of the four conditions
• A fix that breaks it

Interviewer

What are the conditions for deadlock, and which one would you break here?

What they are testing

Whether you can name all four, and then pick one with a reason, not just recite a list. For transfers, the strong answer is circular wait, broken by ordering by account id. It’s cheap, needs no retries, and is easy to check in review. The red flag is listing the four and stopping. So is “add a timeout”, with no word on what happens after it fires.

Fix 1: one global lock order

If every thread takes locks in the same order, a cycle can’t form. For a cycle, some thread would have to hold a later lock while waiting for an earlier one. The order forbids exactly that. Ordering by account id turns every transfer into “lock the lower id, then the higher id”, whichever way the money moves.

Three philosophers sit at a round table, with a fork between each pair. Each needs both neighboring forks to eat. Say each picks up the left fork first. Play A, B, C: everyone holds one fork and waits for the next one, all the way round. With Lower-numbered fork first, philosopher 2 reaches for fork 0 before fork 2. That breaks the circle: one philosopher always gets both forks.

Left fork firstLower-numbered fork first

A · Philosopher 0Step A

1. lock(fork0)
2. lock(fork1)
3. eat()
4. unlock(fork1)
5. unlock(fork0)

ready

B · Philosopher 1Step B

1. lock(fork1)
2. lock(fork2)
3. eat()
4. unlock(fork2)
5. unlock(fork1)

ready

C · Philosopher 2Step C

1. lock(fork2)
2. lock(fork0)
3. eat()
4. unlock(fork0)
5. unlock(fork2)

ready

Play A, B, C, A, B, CRun 1,000 schedulesReset

Three philosophers share three forks; each needs the fork on both sides to eat. Try A, B, C: everyone picks up a first fork.

Here are the fixed transfers in code, run 20,000 times in each direction at once:

JBank.javaPyaccount.pyC#Bank.csGoaccount.goTSaccount.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.ReentrantLock;

// The same opposite-direction transfers, 20,000 each way, with two fixes that can't deadlock.
public class Main {
    public static void main(String[] args) throws InterruptedException {
        run("lock ordering", Bank::transfer);
        run("tryLock with back-off", Bank::transferOrBackOff);
    }

    interface Transfer { void move(Account from, Account to, int amount) throws InterruptedException; }

    static void run(String name, Transfer t) throws InterruptedException {
        Account one = new Account(1, 1_000), two = new Account(2, 1_000);
        Thread ana = new Thread(() -> repeat(() -> t.move(one, two, 3)));
        Thread raj = new Thread(() -> repeat(() -> t.move(two, one, 2)));
        ana.start(); raj.start();
        ana.join(10_000); raj.join(10_000);
        if (ana.isAlive() || raj.isAlive()) throw new AssertionError(name + ": stuck");
        int total = one.balance() + two.balance();
        if (total != 2_000) throw new AssertionError(name + ": money created or lost: " + total);
        System.out.println(name + ": done, total = " + total); // total = 2000
    }

    interface Step { void run() throws InterruptedException; }

    static void repeat(Step s) {
        try { for (int i = 0; i < 20_000; i++) s.run(); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
    }
}

class Account {
    final int id; // unique and never changes, so every thread agrees on the order
    final ReentrantLock lock = new ReentrantLock();
    private int balance; // guarded by lock

    Account(int id, int balance) { this.id = id; this.balance = balance; }

    void add(int delta) { balance += delta; } // caller holds lock
    int balance() { lock.lock(); try { return balance; } finally { lock.unlock(); } }
}

class Bank {
    // Fix 1: every thread takes the two locks in the same global order (lower id first),
    // whatever the direction of the transfer. A cycle needs someone to hold a higher lock while
    // waiting for a lower one, and nobody ever does.
    static void transfer(Account from, Account to, int amount) {
        Account first = from.id < to.id ? from : to;
        Account second = first == from ? to : from;
        first.lock.lock();
        try {
            second.lock.lock();
            try {
                from.add(-amount);
                to.add(amount);
            } finally {
                second.lock.unlock();
            }
        } finally {
            first.lock.unlock();
        }
    }

    // Fix 2: never wait forever while holding a lock. If the second lock isn't free within a
    // few milliseconds, give up the first, pause for a random moment, and try again. Random, so
    // the two threads don't retry in lockstep forever (livelock).
    static void transferOrBackOff(Account from, Account to, int amount) throws InterruptedException {
        while (true) {
            from.lock.lock();
            try {
                if (to.lock.tryLock(1, TimeUnit.MILLISECONDS)) {
                    try {
                        from.add(-amount);
                        to.add(amount);
                        return;
                    } finally {
                        to.lock.unlock();
                    }
                }
            } finally {
                from.lock.unlock();
            }
            Thread.sleep(0, ThreadLocalRandom.current().nextInt(1, 50_000)); // back off up to 50 µs
        }
    }
}

Ordering needs a key that every thread agrees on, and that never changes: a database id, an account number, a file path. Objects without one need a stable key. Java’s System.identityHashCode works, with a tie-breaker lock for the rare equal hashes. (This is the approach in Java Concurrency in Practice.)

In a larger codebase, document the order. This is called a “lock hierarchy”, for example: always the order lock before its line items, never the reverse. Check it in code review, because one function that takes them backwards brings the deadlock back.

TradeoffLock ordering

We gain

No retries, no timeouts, no wasted work. The code stays simple, and anyone can check the rule by reading it.

We give up

You must know every lock you need before taking the first one. Some code finds the next lock only after reading data under the first, like following a pointer or loading a row. It can’t always respect a fixed order. And one violation anywhere, even in a library callback, brings the risk back.

Fix 2: tryLock, timeouts and back-off

When you can’t fix an order, don’t wait forever while holding something. Take the first lock, then try the second with a short timeout. If that fails, release the first, pause, and start over. This breaks hold-and-wait: no thread ever sits holding one lock while blocked on another.

The pause must be random. Say both threads back off for the same time. They retry at the same moment, collide again, and back off again, forever. That’s livelock. Both threads are busy, the CPU is at 100%, and nothing moves forward. Picture two people in a corridor who both step aside the same way, again and again. Random back-off makes the threads fall out of step. (It’s exponential with jitter, the same idea as network retries.)

Timeouts are also how most production systems handle a deadlock they didn’t prevent. A request with a deadline gives up, releases what it holds, and returns an error the client can retry.

TradeofftryLock with back-off vs lock ordering

We gain

It works when the set or order of locks isn’t known up front. And it turns a permanent hang into a delay and a retry.

We give up

Wasted work on every collision. A risk of livelock without randomness. And harder reasoning: every operation must be safe to abandon and retry halfway. Under heavy contention, throughput can collapse as threads keep backing off.

Fix 3: take everything at once, or nothing at all

Two other ways to remove a condition:

• Hold and wait, removed differently: take every lock the operation needs in one step. Or use one coarser lock for the whole operation. A bank with one lock around all transfers can’t deadlock on accounts. But it also can’t run two transfers at once. At scale that’s usually the wrong trade. In an interview, it’s a perfectly good first version.
• Mutual exclusion, removed: don’t share a lock at all. Give each account to one owner thread (or actor, or partition), and send it messages. The owner applies them one at a time. Use an atomic for a single value. A transfer between two owners then becomes two messages and a saga-style protocol. This is how actor systems and partitioned databases avoid locks across entities.

Detection and recovery

Some systems let deadlocks happen, and clean up after. Databases are the main example, because they can’t know in advance which rows a transaction will lock.

• PostgreSQL waits deadlock_timeout (1 second by default) on a lock. Then it builds the wait-for graph. If it finds a cycle, it aborts one transaction with “deadlock detected”. The application is expected to retry it.
• MySQL InnoDB checks for cycles right away, on every lock wait. It rolls back the transaction that is cheapest to undo.

So database code that updates several rows should do two things. Lock the rows in a consistent order (ORDER BY id ... FOR UPDATE). And retry on a deadlock error. Ordering makes deadlocks rare, and the retry handles the ones that remain.

Go deeperAvoidance: the banker's algorithm2 min

The fourth classic strategy is avoidance. Before granting a resource, check whether granting it could lead to a state where deadlock is possible. If so, make the thread wait. Dijkstra’s banker’s algorithm does this, when each thread declares its maximum need up front. It’s taught in operating systems courses, and almost never used in application code. Threads rarely know their maximum needs, and the check runs on every request. If an interviewer asks, name it. Explain the safe-state idea in a sentence, and say why ordering or timeouts are used instead.

Deadlocks without two locks

Deadlock is any circular wait, and the resources don’t have to be mutexes:

• Self-deadlock: a thread takes a non-reentrant lock it already holds. Go’s sync.Mutex and Python’s Lock aren’t reentrant. So a locked method that calls another locked method on the same object hangs right away.
• Thread pool starvation: a task on a pool submits a subtask to the same pool, and blocks waiting for it. Every pool thread is doing the same. So the subtasks sit in the queue with no thread to run them. The thread pools page steps through it.
• Everyone asleep: with condition variables, a wakeup sent to the wrong thread can leave every thread waiting for a signal nobody will send. The producer-consumer page shows it with four threads.
• Sync over async: in C#, say you call .Result or .Wait() on a task from a thread the task needs to resume on (the UI thread, or old ASP.NET’s request context). That blocks the thread forever. Use await all the way up.
• Calling out while holding a lock: you invoke a listener or callback under your lock. It takes another lock, which some other thread holds while calling you. Neither of you wrote a cycle, but together you did. Release your lock before calling code you don’t own.

Common mistake

Starvation and deadlock are the same thing

In deadlock, a set of threads can never proceed, whatever the scheduler does. In starvation, a thread could proceed, but keeps losing. An unfair lock always goes to newer arrivals. Readers keep a read-write lock busy, so a writer never gets in. A low-priority thread never gets the CPU. Starvation is fixed with fairness: FIFO locks, writer preference, aging priorities. Fairness doesn’t affect deadlock at all.

Say this out loud

Two transfers in opposite directions can each hold one account and wait for the other. That’s a circular wait. I’ll break it by always locking the lower account id first. Then locks are taken in one global order, and a cycle can’t form. If I couldn’t know the order up front, I’d use tryLock with a timeout and random back-off.

Mid-level covers

Spots the opposite-order locking, names the four conditions, and fixes it with a global lock order. Knows what livelock is.

Senior adds

Also chooses between ordering, timeouts and restructuring, with reasons. Knows how databases detect deadlocks, and why application code still retries. Recognizes deadlocks without locks: pool starvation, sync over async, callbacks under a lock. Knows how to diagnose one from a thread dump.

Each language, honestly

Language	Detect a deadlock	Timeouts and tryLock
Java	jstack, ThreadMXBean.findDeadlockedThreads(); finds monitor and lock cycles	tryLock(), tryLock(timeout); synchronized can’t time out
Python	No detector; py-spy dump, faulthandler	lock.acquire(timeout=...)
C#	No detector; dotnet-dump, Visual Studio’s Parallel Stacks	Monitor.TryEnter(obj, timeout), SemaphoreSlim.WaitAsync(timeout)
Go	Panics only if every goroutine is blocked; goroutine dumps otherwise	Mutex.TryLock() (since 1.18, discouraged); prefer select with a timeout on channels
TypeScript	Nothing; stuck promises just never settle	Race the wait against a timer; an AbortSignal to cancel

Interview questions

Interviewer asksHow would you prevent deadlock when transferring money between two accounts?

Lock both accounts in a consistent global order, for example by account id. Always lock the lower id first, whatever the direction. Two transfers between the same accounts then queue on the same first lock, instead of each holding one. If there were no ids, I’d use any stable unique key. Or I’d use tryLock with a timeout and random back-off. In a database, SELECT ... ORDER BY id FOR UPDATE does the same, plus a retry on the deadlock error.

Interviewer asksWhat is livelock? Give an example.

Threads that keep changing state in response to each other, without making progress. They aren’t blocked, so CPU usage is high. That’s how it differs from deadlock. For example, two transfers use tryLock. Both fail, both release, both wait the same time, and both retry at the same moment. They will repeat that forever. Random back-off breaks the symmetry.

Interviewer asksYour service stops responding but CPU is near zero. How do you find out whether it's a deadlock?

Take a thread dump. Use jstack for Java (it reports Java-level deadlocks directly), a goroutine dump with SIGQUIT or pprof for Go, py-spy dump for Python, and dotnet-dump for .NET. Look for threads blocked on taking a lock, and find who holds it. A cycle confirms deadlock. Take two or three dumps a few seconds apart. If they show the same threads stuck in the same places, it isn’t ordinary slowness. Also check for pool starvation: every worker blocked, waiting on work queued to the same pool.

Interviewer asksDoes making every lock reentrant prevent deadlock?

No. Reentrancy only stops a thread from deadlocking on a lock it already holds. Say two threads each hold a different reentrant lock, and wait for the other’s. They still deadlock. The cycle is between threads, and reentrancy doesn’t touch it.

Interviewer asksThe dining philosophers: how do you make sure everyone can eat?

Number the forks, and have every philosopher pick up the lower-numbered fork first. One philosopher then reaches across in the other direction, and the cycle is broken. There are two alternatives. A semaphore can let at most N-1 philosophers try at once, so someone always gets two forks. Or use tryLock on the second fork, with release and random back-off. To also avoid starvation, a waiter or a fair queue decides who eats next.

Recap

Idea	Remember
Deadlock	A set of threads each waiting for something another holds; nobody can ever move
Four conditions	Mutual exclusion, hold and wait, no preemption, circular wait; break any one
Lock ordering	One global order breaks circular wait; the default fix
tryLock and back-off	Breaks hold and wait; back-off must be random to avoid livelock
Detection	Databases find cycles and abort a victim; applications retry
Livelock	Busy but no progress; caused by symmetric retries
Starvation	Could progress but keeps losing; fixed by fairness, not by ordering
Beyond locks	Pool starvation, sync over async, condition variables, callbacks under a lock

Further reading

• E. G. Coffman, M. Elphick, A. Shoshani, “System Deadlocks”, ACM Computing Surveys, 1971.
• Brian Goetz et al., Java Concurrency in Practice, chapter 10 (avoiding liveness hazards).
• PostgreSQL: deadlock_timeout and lock monitoring.
• Next: Producer-consumer, which puts every tool so far to work in one structure.