2.6 Deadlock

1. What Is Deadlock?

A deadlock occurs when a set of participants wait indefinitely for resources held by one another.

Example:

• A holds lock 1 and waits for lock 2;
• B holds lock 2 and waits for lock 1.

Neither can progress.

2. Coffman Conditions

Four conditions are jointly necessary for the classic resource deadlock model:

1. mutual exclusion — at least one resource cannot be shared simultaneously;
2. hold and wait — a participant holds one resource while requesting another;
3. no preemption — a held resource is not forcibly taken away;
4. circular wait — a dependency cycle exists.

Breaking at least one condition prevents this form of deadlock.

3. Strategies

3.1 Prevention

Design the system so one condition cannot occur. A common engineering technique is a global lock order: all code acquires locks in the same order, removing circular wait.

3.2 Avoidance

Algorithms such as the Banker’s algorithm grant requests only when the resulting state remains safe. This is important academically but less common in ordinary application code because future resource needs are rarely known precisely.

3.3 Detection and Recovery

Allow deadlocks, detect wait-for cycles, then recover by aborting, rolling back, or preempting work. Databases commonly use this model for transactional locks.

3.4 Ignore / Time Out

Some systems rely on low probability, timeouts, watchdogs, or process restart rather than general deadlock avoidance.

4. Practical Prevention

• minimize lock scope;
• avoid calling unknown/external code while holding locks;
• use consistent lock ordering;
• avoid blocking I/O inside critical sections;
• prefer single-owner/message-passing designs when they simplify ownership;
• use timeouts only as a recovery mechanism, not as proof that deadlock is impossible.