Deadlock and how to avoid it

01The intuition

The problem it solves

A bank moves money between accounts. Each account has its own lock so unrelated transfers run in parallel. A transfer locks the source, then the destination.

import threading

class Account:
    def __init__(self, balance: int) -> None:
        self.balance = balance
        self.lock = threading.Lock()

def transfer(src: Account, dst: Account, amount: int) -> None:
    with src.lock:
        with dst.lock:              # A→B holds A, waits for B
            src.balance -= amount   # B→A holds B, waits for A: forever
            dst.balance += amount

Thread one transfers from A to B and holds A. Thread two transfers from B to A at the same moment and holds B. Each now waits for the other's lock and neither can ever proceed. Nothing crashes, nothing logs; the two threads simply stop, and everything behind them queues up. That is a deadlock, and two locks taken in opposite orders are all it takes.

Build it one piece at a time

Step one: name the four conditions a deadlock needs, because breaking any one of them prevents it. Resources are exclusive; a thread holds one while waiting for another; locks cannot be taken away; and the waiting forms a cycle. The transfer satisfies all four. Every fix below breaks exactly one.

Step two: break the cycle with a global order. Give every lock a rank (here, the account id) and always acquire lower rank first. Both transfers then take A before B, so the second one waits politely instead of holding B.

class Account:
    _next_id = 0

    def __init__(self, balance: int) -> None:
        self.id = Account._next_id; Account._next_id += 1
        self.balance = balance
        self.lock = threading.Lock()

def transfer(src: Account, dst: Account, amount: int) -> None:
    first, second = sorted((src, dst), key=lambda a: a.id)
    with first.lock:
        with second.lock:
            if src.balance < amount:
                raise ValueError("insufficient funds")
            src.balance -= amount
            dst.balance += amount

Step three: when an order cannot be fixed in advance, break "hold and wait" with timeouts. Try to acquire the second lock for a bounded time; on failure release the first, back off a little, and retry. The transfer may be delayed but can never hang.

import random, time

def transfer_with_timeout(src: Account, dst: Account, amount: int, tries: int = 10) -> bool:
    for _ in range(tries):
        if not src.lock.acquire(timeout=0.05):
            continue
        try:
            if dst.lock.acquire(timeout=0.05):
                try:
                    src.balance -= amount
                    dst.balance += amount
                    return True
                finally:
                    dst.lock.release()
        finally:
            src.lock.release()
        time.sleep(random.uniform(0.001, 0.01))   # back off, then retry
    return False

Step four, the quiet one: avoid holding two locks at all. A transfer can be a single lock on a ledger object, or an append to a queue processed by one thread. Fewer locks is the most reliable deadlock fix there is.

Two transfers under the ordered version, with A.id = 0 and B.id = 1:

Why it works

A fixed acquisition order makes a cycle impossible: for a cycle to exist, some thread must hold a higher-ranked lock while waiting for a lower one, which the rule forbids. Timeouts work for a different reason: a thread never waits forever, so a cycle dissolves after at most one timeout, at the cost of retries. The invariant to state in an interview is the rule, "locks are always acquired in increasing id order", and where in the code it is enforced.

Where it breaks: a lock acquired inside a callback or a method you did not write can violate the order without you seeing it; nested calls that take the same lock twice deadlock on a plain Lock. Timeouts can also produce livelock, two threads retrying in step forever, which is why the backoff is randomised.

a deadlock needs all four: exclusive resources, hold-and-wait, no preemption, a waiting cycle. Ordering removes the cycle; timeouts remove hold-and-wait

The trade-off you must say out loud

Lock ordering is free at runtime but is a convention every future developer must keep; timeouts are self-healing but turn a clean API into one that can fail and retry; one coarse lock removes the problem and the parallelism together. Say which you chose and what it costs. The follow-up that usually comes next is detection: how you would notice a deadlock in production, and the answer is lock wait-time metrics and a watchdog that dumps thread stacks.

Where it shows up in the 100 Google problems

• Multi-threaded parking lot: moving a car between spots or floors touches two locks; order them by spot id.
• Thread-safe LFU cache: a get that moves a key between frequency buckets would take two bucket locks; one lock per cache or careful ordering avoids the trap.
• Digital wallet: the transfer above is its core operation.
• Inventory management: reserving several items for one order is the many-locks version; sort the item ids first.

02Used in these problems

• Design a thread-safe LFU cache
• Design a multi-threaded parking lot