Concurrency & Multi-threading
Deadlocks & Livelocks
Analyzing Coffman conditions and avoiding execution traps
Overview
Deadlocks and Livelocks are concurrency failure modes where threads get stuck indefinitely: - Deadlock: Two or more threads are blocked forever, each waiting for a lock held by the other. - Livelock: Threads continuously change their states in response to each other, but make no actual progress.
Key Concepts
- Four Coffman Conditions for Deadlock: 1. Mutual Exclusion, 2. Hold and Wait, 3. No Preemption, 4. Circular Wait.
- Circular Wait: Thread 1 holds lock A, wants lock B; Thread 2 holds lock B, wants lock A.
- Livelock: Similar to two polite people meeting in a hallway, both repeatedly stepping to the side in unison to let each other pass, blocking each other indefinitely.
- Deadlock Prevention: Enforce global lock ordering, acquire locks with timeouts (tryLock), or release held locks if another lock cannot be acquired.
Code Example
If Thread 1 calls method1 and Thread 2 calls method2 concurrently, they lock A and B respectively, and will block forever waiting for the other lock.
Interview Tips
- List the Coffman conditions from memory and explain how breaking circular wait (locking order) is the most common way to prevent deadlock.
- Discuss toolings: using thread dumps (jstack), visual tools, or static code analysis to detect deadlocks.
Related Topics
- Introduction to ConcurrencyUnderstand the fundamentals of concurrency, why it is essential for modern high-performance LLD, and how the operating system schedules interleaved execution.
- Concurrency vs ParallelismDifferentiate between logical task structures and physical hardware execution, understanding cache coherence, false sharing, and hardware limits.
- Processes vs ThreadsMaster the operating system level differences between processes and threads, comparing virtual memory layouts, context switching costs, and communication boundaries.