Deadlocks and Prevention
Prompt
Two threads grab two locks in opposite order and hang forever. Walk me through the precise conditions that have to all hold for that to be a deadlock — and then how you'd design the code so it can't happen.
How this round runs
This is a conversation that escalates — I'll keep asking "and what happens when…" until I find the edge of what you know. I want the four conditions and which one you're actually attacking with each fix — and the distinction between preventing and avoiding deadlock, which is where I'll push.
Model answer
I'll name the conditions, then map each fix to the condition it breaks, because "use locks carefully" isn't an answer — knowing which condition you defeat is. A deadlock needs all four Coffman conditions simultaneously: mutual exclusion (a resource can't be shared), hold-and-wait (a thread holds one resource while requesting another), no preemption (you can't forcibly take a resource back), and circular wait (a cycle in the wait-for graph — A waits on B's lock, B waits on A's). All four together is the deadlock; break any one and it can't form. The classic example — thread 1 takes A then wants B, thread 2 takes B then wants A — is purely the circular-wait condition.
So fixes are "which condition am I killing." A global lock ordering — every thread always acquires locks in the same total order — destroys circular wait, because you can't form a cycle if everyone climbs the ordering the same direction; that's my default, it's static and cheap. Try-lock with backoff attacks hold-and-wait/no-preemption: if you can't get the second lock, release the first and retry — but that risks livelock, threads endlessly grabbing and releasing in lockstep, so you need randomized backoff. Reducing to a single coarse lock removes the possibility of a cycle entirely at a concurrency cost.
The distinction I'd draw, and the honest edge — prevention vs. avoidance. Prevention designs the system so a Coffman condition can never hold (lock ordering is prevention: structural, no runtime check). Avoidance lets the conditions be possible but inspects each request at runtime and refuses any that could lead to an unsafe state — the textbook algorithm is Banker's, which needs every process to declare its maximum resource claim up front. That's where I'm honest: Banker's is real but rarely used in practice because the "declare your maximum claim" requirement almost never holds for general software, so working systems lean on prevention (lock ordering) or detection-and-recovery. The exact safe-state check in Banker's I'd re-derive rather than quote from memory.
- Named all four Coffman conditions and stressed that breaking ANY one suffices
- Mapped each fix to the specific condition it defeats, not a vague 'be careful with locks'
- Picked lock ordering as the default with a reason (kills circular wait, static, cheap)
- Flagged the livelock risk of try-lock/backoff and the need for randomized backoff
- Drew prevention vs. avoidance crisply and was honest that Banker's avoidance is rarely practical
- Which Coffman condition does a global lock ordering actually break, and why does that suffice? → circular wait; a cycle can't form if everyone acquires in the same total order
- What's the difference between deadlock prevention and avoidance? → prevention makes a condition impossible by design; avoidance permits them but refuses requests that could reach an unsafe state (Banker's)
- And what happens when your try-lock-and-retry threads keep releasing in lockstep? → livelock — busy but no progress; needs randomized backoff