Deadlocks • What is Deadlock?Hard⏱️ ~2 min
Detecting Deadlock
Key Challenge
Detecting deadlock after it occurs requires finding cycles in the wait-for graph. This is easier than prevention but requires runtime monitoring.
The Wait-For Graph
Build a graph where nodes are threads and edges represent "waits for." Thread A waits for Thread B means A has an edge to B. A cycle in this graph means deadlock. No cycle, no deadlock.
Detection Algorithm
Periodically scan all blocked threads. Build the wait-for graph. Run cycle detection (DFS). If a cycle exists, deadlock is confirmed. Choose a victim thread to kill or rollback.
Wait-For Graph With Cycle
Cycle: A → B → D → C → A = DEADLOCK
Detection vs Prevention Trade-off
Prevention: No deadlock ever occurs. May be restrictive or reduce concurrency.
Detection: Deadlock can occur, but we catch and recover. More flexible but adds overhead.
Databases often use detection. Application code usually uses prevention (lock ordering).
Practical Note: Most application-level deadlocks are prevented by design (lock ordering), not detected at runtime. Runtime detection is more common in databases and operating systems.
💡 Key Takeaways
✓Wait-for graph: nodes are threads, edges are "waits for" relationships. Cycle means deadlock.
✓Detection algorithm: periodically build graph, run cycle detection (DFS), identify victims.
✓Detection allows deadlock to happen, then recovers. Prevention stops it from ever occurring.
✓Databases use detection with transaction rollback. Applications use prevention with lock ordering.
✓Detection adds runtime overhead but allows more concurrency than strict prevention.
📌 Interview Tips
1Database deadlock detector: runs every few seconds, checks for transaction cycles, aborts youngest.
2JVM thread dump: shows blocked threads and what they wait for. Manual cycle detection.
3MySQL: innodb_lock_wait_timeout triggers after waiting too long. Not true detection, but practical.