Interview Prep Zoneby CuriouserLabs

Question 3 of 5 · senior level

Deadlock: the four conditions, and the real-world strategies — prevention, avoidance, detection, or shrug?

🎤 Say this first

Deadlock requires all four Coffman conditions simultaneously: mutual exclusion, hold-and-wait, no preemption, circular wait — break any one and it's impossible. In practice: general-purpose OSes mostly ignore it (the 'ostrich algorithm' — Linux won't save your app), databases detect it (waits-for cycle detection, kill a victim, which is why you see DeadlockLoserException and must retry), and applications prevent it — overwhelmingly by breaking circular wait with a global lock ordering, or breaking hold-and-wait with tryLock+timeout+backoff. Banker's algorithm (avoidance) is exam material; nobody runs it.

The full picture

🎬 Deadlock: circular wait and the lock-ordering fix

1 / 5
Process P1wants DB, then FILEProcess P2wants FILE, then DB🔒 DB lockfree🔒 FILE lockfreeSame pattern at every scale: JVM monitors, DB row locks, microservices calling each other.

Two processes, two locks. P1 needs both the DB lock and the file lock to do its job; so does P2 — but they acquire them in OPPOSITE orders.

Two locks, opposite orders, circular wait — then the ordering fix.
Break thisHowWhere you've seen it
Circular waitglobal lock order (e.g., by account id)the transfer(a,b) idiom; kernel lock ordering docs
Hold-and-waitacquire all up front, or tryLock + release + retryReentrantLock.tryLock with jittered backoff
No preemptionvictimize someone (rollback)DB deadlock detectors killing a transaction
Mutual exclusiondon't lock: immutable / lock-free / single-writerCAS counters, event-loop designs, actor models
  • Detection mechanics: build the waits-for graph, find a cycle, pick a victim (least work lost); that's InnoDB/Postgres behavior — application consequence: deadlock errors are retryable by design, so your data layer needs a retry policy for them.
  • Livelock is deadlock's embarrassed cousin: everyone retries politely and in sync forever (two people side-stepping in a hallway). Fix: randomized backoff — jitter is a correctness tool, not just a networking nicety.
  • Distributed deadlock: same theory, no shared memory to inspect — hence lock managers with timeouts (a lease is 'preemption by clock'), and why every distributed lock has a TTL.

🔄 Likely follow-up questions

  • Why don't general-purpose OSes do deadlock detection for user processes?
  • Design the lock-ordering rule for transfer(from, to) — and what about lock(a) where a==b?
  • How do lease-based distributed locks map onto 'preemption'?