Back
+30 XP
Concept

Detect Deadlocks in Multi-Lock Acquisition

Acquiring multiple mutexes in inconsistent orders produces catastrophic deadlocks when concurrent threads wait circularly on each other. Enforcing a strict global lock acquisition hierarchy (such as ordering locks by id) completely eliminates circular wait conditions.

python
import threading

def safe_multi_acquire(*locks):
    # Strict global ordering by memory address
    for lk in sorted(locks, key=id):
        lk.acquire()

# Detect Deadlocks in Multi-Lock Acquisition Consider two bank accounts transferring funds between each other: - Thread 1: `transfer(Account A, Account B)` locks Account A, then attempts to lock Account B. - Thread 2: `transfer(Account B, Account A)` locks Account B, then attempts to lock Account A. If both run simultaneously, Thread 1 holds Lock A and waits for Lock B, while Thread 2 holds Lock B and waits for Lock A. Neither will ever yield. Both threads freeze forever. 💀🔒 The classic computer science solution to Coffman’s circular wait condition is **Total Lock Ordering**. If every thread in the universe is forced to acquire locks in a consistent, deterministic order (e.g. sorted by `id(lock)` or unique key), circular waiting is mathematically impossible. ```python import threading def acquire_in_order(lock1, lock2): first, second = sorted([lock1, lock2], key=id) first.acquire() second.acquire() ``` ## Pop Quiz Why does sorting locks by a deterministic key (like `id(lock)`) mathematically guarantee deadlock prevention? - [ ] It enforces a total ordering on lock acquisition, making circular dependency cycles impossible. - [ ] It forces the Python GIL to merge multiple locks into a single atomic hardware instruction. - [ ] It converts mutual exclusion locks into non-blocking reader-writer semaphores. - [ ] It bypasses thread context switching by locking the operating system scheduler. ## Real-World Challenge Implement `OrderedLockManager` providing `@contextmanager acquire(*locks)`. It must sort the provided locks by `id()`, acquire them sequentially, and release them in reverse order in a `finally` block. Verify that concurrent threads acquiring locks in opposing orders complete without deadlocking. <details> <summary>Solution</summary> ```python import threading from contextlib import contextmanager class OrderedLockManager: @staticmethod @contextmanager def acquire(*locks): # Sort locks by their unique memory identity to establish total ordering ordered = sorted(locks, key=id) acquired = [] try: for lk in ordered: lk.acquire() acquired.append(lk) yield finally: for lk in reversed(acquired): lk.release() # Verification lock_alpha = threading.Lock() lock_beta = threading.Lock() audit_events = [] def worker_forward(): with OrderedLockManager.acquire(lock_alpha, lock_beta): audit_events.append("forward_done") def worker_reverse(): with OrderedLockManager.acquire(lock_beta, lock_alpha): audit_events.append("reverse_done") t1 = threading.Thread(target=worker_forward) t2 = threading.Thread(target=worker_reverse) t1.start() t2.start() t1.join(timeout=1.0) t2.join(timeout=1.0) assert not t1.is_alive(), "Thread 1 deadlocked!" assert not t2.is_alive(), "Thread 2 deadlocked!" assert len(audit_events) == 2 ``` </details>