Deadlock: Definition and necessary conditions

A deadlock occurs when two or more concurrent processes or transactions are permanently blocked, each waiting for a resource that the other process holds. This creates a circular dependency where no process can proceed, leading to system stagnation.

Necessary Conditions

For a deadlock to occur, all four of the following conditions must simultaneously be met (often referred to as the Coffman conditions):

Mutual Exclusion: Resources involved must be non-shareable, meaning only one process can use a resource at a time. For example, a write lock on a database row or a file handle.

Hold-and-Wait: A process must be holding at least one resource and simultaneously waiting to acquire additional resources that are currently held by other processes.

No Preemption: Resources cannot be forcibly taken away from a process; they must be voluntarily released by the process holding them upon completion.

Circular Wait: A set of processes {P0, P1, ..., Pn} must exist such that P0 is waiting for a resource held by P1, P1 is waiting for a resource held by P2, and so on, with Pn waiting for a resource held by P0.

Prevention, Detection, and Resolution

Prevention involves designing systems to break one or more of these conditions. A common and effective strategy is to break the circular wait condition by enforcing a strict global ordering for resource acquisition. For example, always acquire locks on tables A then B, never B then A. In distributed data systems like Spark, careful management of shared state or external resources (e.g., Delta Lake transaction logs, Kafka offsets) is crucial to avoid such contention.

Detection and Resolution are often handled by database management systems. They can build a "wait-for graph" to detect cycles (deadlocks). Upon detection, the system typically resolves the deadlock by preempting one of the involved transactions (e.g., rolling back the "victim" transaction) and allowing others to proceed. This often results in an error for the rolled-back transaction, requiring application-level retry logic.

Best practices include designing transactions to be short-lived and acquire resources quickly, and implementing timeouts for resource acquisition to prevent indefinite waits.

-- Transaction 1
START TRANSACTION;
UPDATE accounts SET balance = balance - 10 WHERE id = 1; -- Locks account 1
-- (Concurrent) Waits for lock on account 2
UPDATE accounts SET balance = balance + 10 WHERE id = 2;
COMMIT;
-- Transaction 2 (concurrently)
START TRANSACTION;
UPDATE accounts SET balance = balance - 10 WHERE id = 2; -- Locks account 2
-- (Concurrent) Waits for lock on account 1
UPDATE accounts SET balance = balance + 10 WHERE id = 1;
COMMIT;

This SQL example illustrates a circular wait: Transaction 1 locks id=1 and waits for id=2; Transaction 2 locks id=2 and waits for id=1.

In the interview, also mention how deadlocks become significantly more complex in distributed systems where resources span multiple nodes or services, often requiring distributed lock managers or sophisticated coordination protocols.