Deadlock: the standstill

The bug that does not crash, it just stops

Lesson 5-3 fixed races with locks and mentioned the price in passing: deadlock. It deserves its own lesson because it is a bug class that produces no error message, no exception, and no crash. The program simply stops making progress forever.

In production that looks like a service which suddenly answers nothing until someone restarts it. Databases, web servers, and desktop apps all suffer real outages from exactly this.

The recipe requires two locks and two threads:

1. Thread 1 acquires lock A, then tries to acquire lock B.
2. Thread 2 acquires lock B, then tries to acquire lock A.
3. If the timing interleaves, so that each grabs its first lock before the other grabs its second, thread 1 waits for B held by 2 while thread 2 waits for A held by 1.

Neither can proceed until the other releases, and neither will ever release, because each is stuck waiting. This closed loop of "you first" is called a circular wait, and it is the defining ingredient of every deadlock.

The demo below forces the interleaving with sleeps and uses acquire(timeout=...) so the standstill is observable without hanging the program. After 1 second of waiting, each acquire gives up and reports False.

A deadlock made visible instead of eternal

Each worker grabs one lock, sleeps so the other worker grabs the other lock, then tries for the second with a one-second timeout.

import threading
import time

lock_a = threading.Lock()
lock_b = threading.Lock()
results = {}

def worker1():
    with lock_a:
        time.sleep(0.2)
        got = lock_b.acquire(timeout=1)
        results["worker1 got lock_b"] = got
        if got:
            lock_b.release()

def worker2():
    with lock_b:
        time.sleep(0.2)
        got = lock_a.acquire(timeout=1)
        results["worker2 got lock_a"] = got
        if got:
            lock_a.release()

t1 = threading.Thread(target=worker1)
t2 = threading.Thread(target=worker2)
t1.start()
t2.start()
t1.join()
t2.join()

for key in sorted(results):
    print(key + ":", results[key])
print("each thread held one lock and waited for the other: deadlock")

Output

worker1 got lock_b: False
worker2 got lock_a: False
each thread held one lock and waited for the other: deadlock

The sleep(0.2) guarantees the bad interleaving, because both first locks are taken before either second acquire starts. Without it, one worker would usually finish before the other began.

Without the timeouts both acquires would wait forever and the program would hang, and that hang is the deadlock. The timeout exists only so the failure can be observed safely.

Fixing it with one agreed lock order

Both workers now take lock_a first and lock_b second.

import threading
import time

lock_a = threading.Lock()
lock_b = threading.Lock()
results = {}

def worker1():
    with lock_a:
        time.sleep(0.2)
        got = lock_b.acquire(timeout=2)
        results["worker1 finished"] = got
        if got:
            lock_b.release()

def worker2():
    with lock_a:
        time.sleep(0.2)
        got = lock_b.acquire(timeout=2)
        results["worker2 finished"] = got
        if got:
            lock_b.release()

t1 = threading.Thread(target=worker1)
t2 = threading.Thread(target=worker2)
t1.start()
t2.start()
t1.join()
t2.join()

for key in sorted(results):
    print(key + ":", results[key])

Output

worker1 finished: True
worker2 finished: True

Only worker2 changed. It takes lock_a first and then acquires lock_b, which is the same order worker1 already used.

After the change, whichever worker gets lock_a first simply finishes, releases, and the other takes its turn. That is a queue rather than a circle, and the wait is bounded by how long the critical section takes rather than being unbounded.

The working defenses

Ranked by how often real teams use them.

1. One agreed lock order. If every thread that needs multiple locks acquires them in the same fixed order, whether alphabetical, by ID, or anything else consistent, a circular wait cannot form. This is the fix from the previous block and the standard answer in interviews and code review.
2. Hold one lock at a time. No second lock, no circle. This is often achievable by shrinking the critical section or copying data out before taking the next lock.
3. Timeouts plus retry. Acquire with a timeout, and on failure release everything, wait a moment, and try again. It is messier, but it turns an eternal hang into a recoverable slowdown.

Databases take a fourth path and detect the cycle. PostgreSQL and MySQL watch who waits for whom, and on finding a loop they kill one transaction with a deadlock detected error so the others can proceed.

Seeing deadlock detected in a backend log now has a precise meaning: two transactions locked rows in opposite orders.

The defense that makes it impossible, not unlikely

With thread 1 holding the accounts lock and waiting for the audit-log lock, and thread 2 the reverse, the fix that eliminates the scenario is requiring every thread to acquire accounts before audit-log, always, in that order.

With a global lock order, no thread can ever hold audit-log while waiting for accounts, because it would have needed accounts first. The circular wait is structurally impossible rather than merely improbable.

The distinction matters because timing-based mitigations look successful in testing. A race that now happens one time in a million is still a race, and production traffic finds it.

Naming the closed loop of waiting

Two threads each holding a lock the other needs, in a closed loop of waiting nobody can exit, are in a deadlock.

Each thread waits for a lock the other holds, and because both are waiting, neither ever releases. That is a circular wait, and the name is literal: the threads are locked, dead, in place.

Databases report the detected case with a famous two-word error, deadlock detected, which is worth recognizing on sight because it points straight at two transactions that locked rows in opposite orders.