How Do You Prevent, Detect, and Recover from Deadlocks?

Prompt and Applicable Context

A transfer service occasionally freezes: thread A holds the lock for account 42 and waits for account 84, while thread B holds account 84 and waits for account 42. Neither thread releases its first lock. Is this deadlock? Explain the four necessary conditions and design prevention, detection, recovery, and validation.

This is a general software-engineering and operating-systems question for backend, systems, infrastructure, SRE, and other roles that write concurrent code. Current English and Chinese 2026 interview material still asks separately about the definition, four necessary conditions, and handling strategies. This article makes no company attribution and claims no unsupported interview frequency.

Accounts 42 and 84 are fictional identifiers. The task goes beyond reciting four names. A strong answer distinguishes a long wait from an irreducible wait cycle, then connects the theory to a lock protocol, runtime evidence, failure recovery, and testing. The primary scope is single-instance mutexes and database row locks. Distributed leases, network partitions, and consensus are outside the first answer.

What the Interviewer Evaluates

The first signal is whether diagnosis uses wait relationships. Low CPU, timed-out requests, or two blocked threads show a lack of progress but do not independently prove deadlock. A strong answer builds a wait-for graph whose nodes are threads or transactions and whose edges mean “waits for a resource owned by,” then looks for a cycle.

The second signal is accurate use of the four necessary conditions: mutual exclusion, hold and wait, no preemption, and circular wait. They explain why deadlock is possible. Listing them without mapping each one to the transfer path is still a memorized response.

The third signal is a prevention strategy with a provable global invariant. The practical choice is often a stable total order for every lock, enforced across every entry point. Swapping two lines in one function is insufficient. Batch jobs, refunds, repair tools, and future paths can recreate the cycle if any acquire in reverse order.

Finally, the interviewer evaluates recovery boundaries. A database can detect a cycle and roll back a transaction. An in-process mutex usually cannot be safely stolen and execution resumed because the interrupted code may have changed only half of an invariant. A strong answer separates prevention, avoidance, detection, and recovery, states the cost of timeouts, and reproduces the interleaving rather than hoping a stress test encounters it.

Questions to Clarify Before Answering

Are all resources single-instance mutexes? A cycle in a wait-for graph over single-instance resources proves that group cannot progress. If a resource type has multiple instances, a cycle in the resource-allocation graph indicates possibility; available instances and remaining needs still matter.
Are the locks reentrant? Reacquiring a non-reentrant lock in the same thread can self-deadlock. When source and destination are the same account, deduplicate before locking instead of assuming sorting handles the duplicate.
Are both account changes in one rollback-capable transaction? A transaction boundary can abandon a victim and retry. A flow that already sent an external payment or email needs an idempotency key or post-commit outbox, not blind replay.
Can every acquisition path share one ordering rule? If so, prefer global ordering. If a third-party component or cross-service resource cannot join that protocol, reduce simultaneous ownership, redesign ownership, or put detection and rollback around a safe boundary.
How long may a request wait, and what does timeout mean? A lock timeout bounds tail latency but can terminate a legitimate slow request. Callers need to know whether the operation is retryable, final, or outcome-unknown.
Which diagnostic facilities does the runtime expose? JVM thread management, database wait views, and kernel lock validators cover different lock classes. No report from one tool does not clear asynchronous waits, virtual threads, or external resources.
Does the critical section call a network, disk, or user-controlled operation? Unbounded dependencies extend ownership and amplify blocking. Move them outside unless the consistency protocol explicitly requires the wait and handles its failure.

30-Second Answer Framework

“This is deadlock: A waits for B to release 84, while B waits for A to release 42, so the wait-for graph contains A → B → A. The case has mutual exclusion, hold and wait, no preemption, and circular wait. I would deduplicate account IDs and acquire all account locks in one stable ascending order, releasing in reverse, which breaks circular wait by protocol. In production I would confirm the cycle from thread or database wait data. A database victim rolls back and retries with a bound; for an in-process deadlock I preserve diagnostics and recover only at a safe state boundary. A barrier test makes the old interleaving deterministic and verifies that the ordered version preserves the balance invariant.”

A complete answer should add why ordering rules out a cycle, why timeout is not a proof, which waits a detector covers, and whether recovery can duplicate an external side effect.

Step-by-Step Deep Answer

Step 1: Prove a wait cycle instead of diagnosing from symptoms

Represent the runtime state as a wait-for graph. Thread A holds lock 42 and requests 84, which B owns, so add A → B. Thread B holds 84 and requests 42, which A owns, so add B → A. Each thread releases its first lock only after acquiring the second. No node in the cycle can finish first, so the group cannot make progress on its own.

Production diagnosis needs owners, waiters, and stacks from approximately the same moment. One thread snapshot may catch harmless contention. Repeated snapshots with the same stacks and edges provide stronger evidence. A long but ordinary wait has no return edge: A may wait for B while B runs and eventually releases its resource. Calling every slow lock a deadlock misdiagnoses capacity or dependency latency as a lock-protocol bug.

The graph conclusion has a model boundary. When each mutex has one owner, a wait cycle is sufficient for deadlock among those threads. When a resource category has multiple instances, a cycle in the resource-allocation graph shows risk rather than proof; an outside instance may be released and let a participant continue. The analysis then needs available, allocated, and maximum remaining demand.

Step 2: Map the four necessary conditions to the code

The four conditions are concrete in this transfer:

Mutual exclusion: one thread at a time owns an account's write lock.
Hold and wait: A holds 42 while requesting 84; B holds 84 while requesting 42.
No preemption: the runtime does not safely take an account lock from its owner; the owner releases it.
Circular wait: A waits for B and B waits for A.

Every condition exists when this deadlock occurs, and breaking any one prevents this class. Do not treat “the system uses mutexes” or “the code nests locks” as proof of an active deadlock. Necessary conditions describe what permits deadlock; the runtime state still needs an irreducible cycle.

Mutual exclusion may protect the balance invariant, so removing it and racing on shared state is not a fix. Safe preemption is also difficult for an ordinary in-memory critical section. Engineering systems more often remove circular wait or, at rollback-capable boundaries, detect and abandon one transaction.

Step 3: Eliminate circular wait with a global lock order

Define a total order for every lock that may be held together, such as resource-type rank followed by resource ID. When only account locks are involved, sort by account ID. Deduplicate first to handle a transfer whose source and destination match. Acquire in order, perform only validation and state mutation in the critical section, and release in reverse.

Language-neutral pseudocode:

transfer(fromid, toid, amount): ids = unique(sortascending([fromid, to_id])) acquired = [] try: for id in ids: acquired.append(lock_account(id)) validateandapplytransfer(fromid, to_id, amount) finally: for lock in reverse(acquired): unlock(lock)

The correctness argument is short. If a thread holding a lower-ranked lock may wait only for a higher-ranked lock, a wait cycle would require ranks to increase strictly:

r1 < r2 < … < rn < r1

A strict order cannot return to its starting point, so circular wait is impossible. The proof depends on every path obeying the same order. Acquiring by request order, list iteration order, or database return order on one side path invalidates the invariant.

Reverse release makes nested ownership easy to reason about but is not what prevents the cycle. The more important rule is to avoid remote calls, user input, and unbounded I/O while holding locks. A long critical section may not deadlock, but it magnifies contention, timeout, and recovery cost.

Step 4: Know when another strategy fits

Requesting every resource before doing work breaks hold and wait, but callers must know the complete set in advance. A large set also lengthens ownership and reduces concurrency. It fits a small, known lock set and fits poorly when traversal discovers resources incrementally.

Deadlock avoidance asks whether granting a request preserves a safe state. Banker's algorithm requires maximum demands in advance and tracks available, maximum, allocated, and remaining resources. A dynamic web request rarely knows every object it will later touch, so the algorithm is useful for explaining safe states but is usually not copied into application code. A safe state guarantees a completion sequence. An unsafe state may lead to deadlock but is not already deadlocked.

Reducing shared mutable state, assigning one owner, or using mature concurrent containers can remove hand-written lock paths. It does not justify “messages cannot deadlock.” Two bounded queues can wait for each other's capacity, and tasks in one executor can wait cyclically for results. The alternative still needs a wait graph.

Try-lock and timeout are lossy escape mechanisms, not proof of an acyclic protocol. If the timeout path rolls back partial state and releases every held lock, it breaks hold and wait after the threshold and dissolves this cycle. Requests still stall before the threshold, and a short threshold aborts legitimate work. Both sides can time out and retry together, producing livelock. Use a maximum attempt count, randomized backoff, idempotent semantics, and a terminal error.

Step 5: State what each detector actually covers

The JVM ThreadMXBean can find cycles among platform threads waiting for object monitors or ownable synchronizers and return their IDs. The Java SE 25 documentation states that cycles containing virtual threads are not found by this method and that the operation is for troubleshooting, not synchronization control. A null result clears only the detector's coverage.

The Linux kernel's lockdep records observed acquisition dependencies between lock classes. If execution exposes L1 → L2 and L2 → L1, it can report a potential inversion even when this run has not happened to freeze. This demonstrates how development and test environments can validate an ordering protocol; application code cannot assume every runtime offers the same validator.

PostgreSQL automatically detects transaction deadlocks and aborts one participating transaction so the others can continue. Its documentation says the victim is difficult to predict, so business logic must not depend on “the newer request always loses.” PostgreSQL also recommends consistent acquisition order across applications and retrying transactions that abort when full prevention is infeasible.

Production signals should include lock-wait duration, lock-held duration, deadlock count, rolled-back transactions, retry attempts, and terminal failures. A diagnostic record should correlate waiter, owner, lock class, and stack without logging full account data, query parameters, or sensitive payloads.

Step 6: Recover at the resource's consistency boundary

After a database chooses a victim, roll back the entire transaction, reread state, and execute again. Do not resume from “after the first lock.” Bound retries and add randomized delay. If duplicate requests can arrive, use a business idempotency key. Trigger email, messaging, or external payment after commit through an idempotent outbox-like path because a database rollback cannot undo an emitted side effect.

When in-process threads are stuck on mutexes, forcibly terminating one can leave an in-memory invariant half-updated. A common recovery path captures thread dumps and key metrics, then lets supervision restart a process or instance whose state can be safely reconstructed. If the process owns unique, unrecoverable state, restart is not safe either; persistence and recovery need redesign.

Victim selection may consider work already performed, rollback cost, priority, and retry history, but correctness comes first. Recovery restores progress and does not remove the cause. Without fixing lock order, the same traffic can deadlock again.

Step 7: Validate the fix with a deterministic interleaving

Do not rely only on a high-concurrency test to get lucky. Add a test barrier to the old implementation. A reaches the barrier after locking 42, and B reaches it after locking 84. Release both to request their second lock. A watchdog should capture both wait edges within the test deadline, proving A → B → A rather than merely detecting a slow test machine.

Run the same reversed inputs against the fix. A and B both try lower ID 42 first. One waits without owning 84; the winner acquires 84, completes, and releases, after which the other proceeds. Verify that both requests receive a contract-valid result, total balance stays unchanged, and no transfer executes twice.

Also cover:

identical source and destination IDs, proving deduplication avoids a second acquisition of a non-reentrant lock;
three or more accounts and multiple resource types, proving the order key is identical across paths;
insufficient balance, exceptions, cancellation, and partial acquisition failure, proving finally releases every acquired lock;
batch, refund, and repair paths concurrent with online transfers, finding bypass inversions;
database detection and victim rollback, validating full retry, idempotent side effects, and the retry bound;
a randomized high-contention soak that continuously checks balances, lock waits, deadlocks, and starvation.

The deterministic test closes the known counterexample. The soak searches for unmodeled paths. Both are needed before claiming the protocol is validated.

High-Quality Sample Answer

“I would first prove this is more than a slow wait. A owns 42 and waits for B's 84, so A → B. B owns 84 and waits for A's 42, so B → A. Each single-instance mutex is released only after its owner gets the second one, making this cycle a deadlock.

All four necessary conditions are present: account write locks are mutually exclusive; both threads hold one while waiting for another; the locks cannot be safely preempted; and the waits form a cycle. I would not remove mutual exclusion because it protects balances. I would break circular wait by defining one total order for account locks, deduplicating IDs, acquiring in ascending order, and releasing in reverse. If every path waits only from a lower rank to a higher rank, a cycle would require ranks to increase and then return to a lower starting point, which is impossible.

The rule must cover online transfers, refunds, batch work, and repair tools. Critical sections contain only validation and state mutation, not remote calls. A timeout can dissolve this wait after complete release, but it does not prove the lock protocol is acyclic. Simultaneous timeout and retry can become livelock, so any timeout path needs bounded attempts, randomized backoff, and an idempotency key.

In production I would construct the waiter-to-owner graph from thread dumps or database wait data, while respecting each detector's coverage. If PostgreSQL detects a transaction deadlock, it aborts one transaction. I would roll back and retry the whole transaction with a bound, without assuming which request becomes the victim, and publish external messages only through an idempotent post-commit path.

For verification, a barrier lets A lock 42 and B lock 84 before both request the second lock, reliably reproducing the old implementation. The ordered version receives the same reversed inputs and should show only acyclic waiting before completion. I would also test identical accounts, three-account operations, exception cleanup, bypass jobs, and database rollback while checking total balance, duplicate side effects, deadlock count, and terminal failures.”

This answer connects the definition, proof, engineering choice, recovery, and validation. If the interviewer asks only for the four conditions, stop after the second paragraph. Expand into tooling and retry boundaries when production handling becomes the follow-up.

Common Mistakes

Declaring deadlock whenever a thread blocks → A long holder may still be progressing → Draw waiter-to-owner edges and confirm a cycle under the correct resource-instance model.
Reciting only four conditions → The answer neither maps the code nor selects a remedy → Map each condition to the scenario and say which one the design breaks.
Sorting independently inside each function → Modules may disagree on the key or resource-type rank → Define a repository-wide lock hierarchy and inspect every entry point.
Ignoring duplicate resource IDs → One thread may acquire the same non-reentrant lock twice → Deduplicate before sorting and define same-account transfer semantics.
Treating a timeout as an acyclic design → The inverse order remains, and timeout can abort legitimate waits → Release every held lock and add bounded backoff, idempotency, and terminal failure.
Resuming midway after cycle detection → Partial state can be stale and side effects can repeat → Roll back and rerun the complete transaction with an idempotent post-commit path.
Assuming every resource graph cycle proves deadlock → An outside instance can release a multi-instance resource → Separate single-instance wait-for graphs from multi-instance allocation analysis.
Forcibly killing the lock owner → In-memory invariants may be half-updated → Capture evidence and restart only at a state-reconstructible boundary.
Running only randomized stress → Failure to reproduce says nothing about an inverse order → Fix the interleaving with barriers, then add a soak for unknown paths.

Follow-Up Questions and Responses

Follow-up 1: Does ordering still work when a transfer locks three accounts?

Yes, if the complete, deduplicated lock set is known before acquisition and sorted by the same stable key. If execution discovers accounts dynamically, read a candidate set without locks, acquire it together, and revalidate versions. If the set cannot be known, split the transaction or use detection around a rollback-capable boundary instead of acquiring incrementally by local order.

Follow-up 2: How do you order different resource types?

Create a composite rank, such as customer before account before ledger shard, then stable ID within each type. A shared lock protocol owns the rule, and review plus tests validate cross-type edges. If one operation must enter in reverse, redesign the call direction or release the lower-level resource before crossing the boundary rather than adding a one-off exception.

Follow-up 3: Has tryLock with a 100-millisecond timeout solved deadlock?

It bounds this attempt's wait to the configured window but does not prove an acyclic protocol. One hundred milliseconds may also be below a legitimate critical section's tail and create false failure. Define release of acquired locks, rollback of partial state, bounded randomized backoff, idempotency, and a terminal error; otherwise deadlock can become retry livelock.

Follow-up 4: Why is upgrading a read lock to a write lock dangerous?

If two threads both own shared read locks and both wait to upgrade to exclusive write, each read lock blocks the other's upgrade and forms a cycle. Prefer an explicit upgrade protocol supplied by the library. Without one, release the read lock, compete for the write lock, and revalidate the condition because state may change during the gap.

Follow-up 5: If PostgreSQL detects deadlocks automatically, what remains for the application?

Use consistent multi-object order to reduce their occurrence and treat a deadlock error as failure of the whole transaction. Reread and retry with a bound, make the request idempotent, and record retries plus terminal failures. Do not assume a particular transaction always loses or repeat an irreversible external action after rollback.

Follow-up 6: How do deadlock, livelock, and starvation differ?

Deadlocked participants cannot progress because of a wait cycle. Livelocked participants execute and change state but repeatedly yield or retry without completing. Starvation means one participant is denied a resource for an unbounded time while others may finish. Their evidence differs: a wait cycle, continued state changes without completion, and sustained unfair waiting.