Deadlock

Updated September 30, 20262 min read

In short

A deadlock is a situation where two or more threads or processes wait forever for each other to release resources, so none of them can make progress.

What is a deadlock?

A deadlock happens when a group of threads or processes each hold a resource and wait for a resource held by another member of the group. Because every participant is waiting on someone else, nobody can continue, and the program freezes without crashing or reporting an error.

A deadlock can only occur when four conditions, known as the Coffman conditions, are true at the same time: mutual exclusion (a resource can be held by only one party), hold and wait (a party holds one resource while waiting for another), no preemption (resources cannot be forcibly taken away), and circular wait (a cycle of parties each waiting on the next). Breaking any one of them prevents deadlock. The most common practical fix is to make every thread acquire locks in the same global order, which removes the circular wait.

Picture two cars meeting in the middle of a narrow one-lane bridge from opposite ends. Each driver waits for the other to back up, and neither moves. Deadlocks show up in multithreaded programs that use locks, in databases when two transactions lock the same rows in opposite order, and in operating systems that manage shared devices.

Deadlock is often confused with livelock and starvation. In a deadlock the parties are stuck doing nothing, while in a livelock they keep actively reacting to each other without making real progress. Starvation means one party waits indefinitely because others keep getting the resource first, even though the system as a whole is still moving.

At a glance

Each thread holds what the other needs, so neither can continue. Taking locks in the same order breaks the cycle.

Key takeaways

A deadlock is a cycle of parties, each waiting for a resource another one holds.
It requires mutual exclusion, hold and wait, no preemption, and circular wait.
Acquiring locks in a consistent order is the most common way to prevent it.
Timeouts and deadlock detection let systems such as databases recover by aborting one party.
Deadlock differs from livelock, where parties stay busy without making progress.

Example

Two threads that can deadlock in Pythonpython

import threading

lock_a = threading.Lock()
lock_b = threading.Lock()

def task_1():
    with lock_a:      # Holds A...
        with lock_b:  # ...then waits for B
            print("task 1 done")

def task_2():
    with lock_b:      # Holds B...
        with lock_a:  # ...then waits for A: possible deadlock!
            print("task 2 done")
# Fix: make both tasks acquire lock_a before lock_b.

Readers ask

How do databases handle deadlocks?

Most relational databases detect deadlocks automatically by looking for cycles among waiting transactions. They then abort one of the transactions and return an error, so the application can retry it.

How can I prevent deadlocks in my code?

Acquire multiple locks in the same fixed order everywhere, hold locks for as short a time as possible, and use timeouts when acquiring them. Higher-level tools such as queues or immutable data can also reduce the need for locks.

What is the difference between a deadlock and a race condition?

In a deadlock, threads block forever waiting for each other, so the program stops making progress. In a race condition, threads access shared data without proper coordination, so the program keeps running but may produce wrong results.