Deadlocks

A deadlock happens when two or more threads (or processes, or database transactions) are stuck forever because each holds something the next one needs. Thread 1 holds lock A and waits for lock B, while Thread 2 holds lock B and waits for lock A.

Deadlock needs all four Coffman conditions at once: mutual exclusion (a resource can be held by only one at a time), hold and wait (a thread holds one resource while waiting for another), no preemption (resources cannot be taken away by force), and circular wait (a cycle of threads each waiting for the next). Related problems are livelock, where threads keep reacting to each other and make no progress, and starvation, where one thread is always passed over.

1. 1Model it as a wait-for graph: an arrow from T1 to T2 means T1 is waiting for something T2 holds. With single-instance resources, a cycle in this graph means deadlock.
2. 2Prevention breaks one of the four conditions by design. The most practical is breaking circular wait: always acquire locks in a fixed global order (for example by account id). Other options: request all resources at once (breaks hold and wait), or allow preemption, such as try-lock with timeout and release everything on failure.
3. 3Avoidance checks each request before granting it and only grants it if the system stays in a safe state. The Banker's algorithm is the textbook example; it needs to know each process's maximum needs in advance, so it is rarely used in general-purpose systems.
4. 4Detection and recovery lets deadlocks happen, periodically finds cycles in the wait-for graph, then recovers by aborting or rolling back one victim. Databases do this.
5. 5Ignoring it (the ostrich approach) is what most general-purpose operating systems do for application locks: it is left to the programmer.

import threading

class Account:
    def __init__(self, acc_id, balance):
        self.id = acc_id
        self.balance = balance
        self.lock = threading.Lock()

def transfer(src, dst, amount):
    # Always lock the lower id first. Every thread takes locks in the
    # same global order, so a waiting cycle (circular wait) is impossible.
    first, second = (src, dst) if src.id < dst.id else (dst, src)
    with first.lock:
        with second.lock:
            if src.balance < amount:
                return False
            src.balance -= amount
            dst.balance += amount
            return True

a, b = Account(1, 100), Account(2, 100)
t1 = threading.Thread(target=transfer, args=(a, b, 30))
t2 = threading.Thread(target=transfer, args=(b, a, 50))
t1.start(); t2.start(); t1.join(); t2.join()
print(a.balance, b.balance)      # 120 80, and it never hangs

Both transfers lock account 1 before account 2, regardless of direction, so a cycle in the wait-for graph is impossible. The final balances are 120 and 80 whichever thread runs first, since both transfers have enough funds.

Cost: Detecting a cycle in the wait-for graph is O(V + E) with a depth-first search.