Deadlock

What is a Deadlock?

A Deadlock is a state in which two or more processes are indefinitely blocked, each waiting for a resource currently held by another process in the set, resulting in a cyclical dependency where none can proceed.

To use an analogy: Two people meet face-to-face in a very narrow hallway. Both refuse to step aside and insist the other yield first. The result is total gridlock.

Process A:                         Process B:
  Holds Resource 1                   Holds Resource 2
  Requests Resource 2 → Waits        Requests Resource 1 → Waits
       │                                  │
       └──── Infinite Mutual Blocking ────┘

The Four Necessary Conditions

A deadlock can only occur if all four of the following conditions (defined by Coffman) are met simultaneously:

Breaking ANY ONE of these four conditions guarantees that deadlock cannot occur.

Deadlock Handling Strategies

1. Deadlock Prevention

Design the system protocols to structurally destroy at least one of the four necessary conditions:

Resource Ordering is the most widely adopted prevention strategy in practical software engineering:

Resource IDs: Lock_1=1, Lock_2=2, Lock_3=3

Rule: Locks must be acquired in ascending numerical order.

Process A: acquire(Lock_1) → acquire(Lock_2) ✅
Process B: acquire(Lock_1) → acquire(Lock_2) ✅  ← Circular wait is impossible

Anti-pattern:
Process A: acquire(Lock_1) → acquire(Lock_2)
Process B: acquire(Lock_2) → acquire(Lock_1) ❌  ← Violates strict ordering

2. Deadlock Avoidance

Allow the first three conditions to exist, but dynamically analyze every resource request. If granting the request could potentially lead to a deadlock, the request is delayed.

The Banker's Algorithm

Modeled after a bank's lending policy: Before approving a loan (allocating a resource), the bank (OS) checks if the remaining capital (available resources) is sufficient to fully satisfy the maximum needs of at least one customer (process). If so, the system remains in a Safe State.

Example: 3 Resource Types (A=10, B=5, C=7), 5 Processes

        Allocated      Max Required    Still Needed
        A  B  C        A  B  C         A  B  C
P0      0  1  0        7  5  3         7  4  3
P1      2  0  0        3  2  2         1  2  2
P2      3  0  2        9  0  2         6  0  0
P3      2  1  1        2  2  2         0  1  1
P4      0  0  2        4  3  3         4  3  1

Currently Available: A=3, B=3, C=2

Safe Sequence Check:
1. P1 needs (1,2,2) ≤ Available (3,3,2) → Execute P1 → Available becomes (5,3,2)
2. P3 needs (0,1,1) ≤ Available (5,3,2) → Execute P3 → Available becomes (7,4,3)
3. P4 needs (4,3,1) ≤ Available (7,4,3) → Execute P4 → ...
4. ...

A Safe Sequence exists <P1, P3, P4, P2, P0> → The system is in a Safe State ✅

3. Deadlock Detection & Recovery

Neither prevent nor avoid. Allow deadlocks to occur, periodically detect them, and forcefully recover the system.

Detection: Periodically build a Resource Allocation Graph (RAG) and run cycle-detection algorithms (like Tarjan's or DFS).

Recovery Mechanics:

• Process Termination: Abort one or more deadlocked processes until the cycle is broken.
• Resource Preemption: Forcibly seize a resource from a process and give it to another.
• Rollback: Snapshot processes at safe checkpoints. If a deadlock occurs, roll back the involved processes to their last checkpoint and try again.

4. The Ostrich Algorithm (Ignore)

If deadlocks are statistically rare, and the computational cost of continuous prevention/avoidance is higher than simply rebooting the system when it crashes, the optimal engineering choice is to do nothing. Most general-purpose operating systems (including Linux and Windows) employ the Ostrich Algorithm for user-space deadlocks—if a user application deadlocks, the user is expected to forcefully terminate and restart it.

System Design Audit & Observability

In distributed systems and backend engineering, deadlocks manifest as silent application freezes where CPU utilization drops to 0%, but requests time out indefinitely.

1. Database Transaction Deadlocks

Relational databases (like MySQL/InnoDB) inherently detect and break deadlocks by sacrificing one transaction, but application code must be built to handle this.

• Audit Protocol: If you encounter Deadlock found when trying to get lock; try restarting transaction, your application is likely acquiring row locks in unpredictable orders. Refactor your ORM queries to always sort the target IDs (ORDER BY id ASC) before executing bulk UPDATE or SELECT ... FOR UPDATE operations. This strictly enforces the "Resource Ordering" prevention strategy.

2. Thread-Level Deadlock Detection

A JVM or Node process locking up entirely is almost always a thread-level deadlock (e.g., synchronized blocks or Mutexes held in circular dependencies).

• Audit Command: For Java, execute jstack <PID>. The JVM will explicitly parse the thread dump and print Found one Java-level deadlock: along with the exact class names and line numbers of the offending locks. For Go, triggering a SIGQUIT (kill -3 <PID>) will dump all goroutine stacks, allowing you to trace the lock graph manually.

3. Lock Timeouts over Indefinite Blocking

Relying purely on structural prevention is fragile as codebases scale.

• Audit Protocol: Never use blocking lock acquisitions (lock.acquire()) in distributed systems. Always use bounded acquisitions (lock.try_acquire(timeout=5s)). If the lock cannot be acquired within the timeout, abort the operation, log an error, and return a 503 Service Unavailable. This transforms a catastrophic permanent deadlock into a recoverable transient failure.