deadlock

**Deadlock** — a situation where two or more threads are permanently blocked, each waiting for a resource held by another, creating a circular dependency. **Four Necessary Conditions (Coffman)** 1. **Mutual Exclusion**: Resources can only be held by one thread 2. **Hold and Wait**: Thread holds one resource while waiting for another 3. **No Preemption**: Resources can't be forcibly taken 4. **Circular Wait**: Thread A waits for B, B waits for A (or longer chain) **Classic Example** ``` Thread 1: lock(A) → waiting for lock(B) Thread 2: lock(B) → waiting for lock(A) → Both threads blocked forever ``` **Prevention Strategies** - **Lock Ordering**: Always acquire locks in the same global order (breaks circular wait) - **Try-Lock with Timeout**: Attempt to lock, give up if timeout expires - **Lock-Free Algorithms**: Use atomic operations instead of locks - **Resource Hierarchy**: Number all resources, only request in ascending order **Livelock vs Deadlock** - Deadlock: Threads are stuck (not executing) - Livelock: Threads keep running but make no progress (repeatedly yielding to each other) **Deadlock** detection is available at runtime (cycle detection in resource wait graphs), but prevention through disciplined design is strongly preferred.