Deadlocks | Computer Science - Wyatt's Notes

flowchart TD
    A[4_Deadlocks] --> B[Key Concepts]
    A --> C[Core Principles]
    A --> D[Practical Applications]
    B --> E[Fundamental definitions]
    C --> F[Design patterns]
    D --> G[Real-world usage]

Deadlock is a circular wait — two or more processes are each holding a resource the other needs, and neither will release what they have. Think of a traffic jam at a four-way intersection where each car refuses to back up. The critical insight is that deadlock is not about a single resource being busy; it’s about a cycle of dependencies.

Why the four conditions matter: All four Coffman conditions (mutual exclusion, hold-and-wait, no preemption, circular wait) must hold simultaneously for deadlock to occur. Breaking any one condition prevents deadlock. Resource ordering (preventing circular wait) and allowing preemption are the most practical strategies.

Recovery intuition: When deadlock occurs, you must either kill processes (lose work) or preempt resources (roll back to a checkpoint). Both are expensive. Prevention (breaking conditions before deadlock can form) is almost always better than recovery.

A deadlock is a situation where a set of processes are all blocked, each waiting for a resource Held by another process in the set.

Coffman conditions (all four must hold simultaneously):

1. Mutual exclusion: At least one resource is non-sharable.
2. Hold and wait: A process holds at least one resource and is waiting for others.
3. No preemption: Resources cannot be forcibly taken.
4. Circular wait: A circular chain of processes exists, each waiting for a resource held by the next.

Eliminate one of the four Coffman conditions:

The Banker’s algorithm avoids deadlock by checking whether granting a request leads to a safe State.

Definitions:

• Available: Vector $A = (A_1, \ldots, A_m)$ of available instances of each resource type.
• Maximum: Matrix $\mathrm{Max}$ where $\mathrm{Max}[i][j]$ is the maximum demand of process $i$ for resource $j$.
• Allocation: Matrix $\mathrm{Alloc}$ where $\mathrm{Alloc}[i][j]$ is the current allocation.
• Need: $\mathrm{Need}[i][j] = \mathrm{Max}[i][j] - \mathrm{Alloc}[i][j]$.

Safety algorithm:

1. Work = Available; Finish[i] = false for all i
2. Find i such that Finish[i] == false AND Need[i] <= Work
3. If no such i exists, go to step 5
4. Work = Work + Alloc[i]; Finish[i] = true; go to step 2
5. If Finish[i] == true for all i, system is SAFE

Resource request algorithm. When process $i$ requests resources:

1. If Request[i] > Need[i], error (exceeded maximum claim)
2. If Request[i] > Available, process must wait
3. Pretend to allocate:
   Available = Available - Request[i]
   Alloc[i]  = Alloc[i] + Request[i]
   Need[i]   = Need[i] - Request[i]
4. Run safety algorithm.
   If safe, grant the request.
   If unsafe, roll back and make the process wait.

Example. Five processes, three resource types, $A = (3, 3, 2)$:

Safety check: $P_1$ has $\mathrm{Need} = (1,2,2) \leq (3,3,2) = A$. Execute $P_1$Release $(2,0,0)$New $A = (5,3,2)$. Then $P_3$: $\mathrm{Need} = (0,1,1) \leq (5,3,2)$. Continuing, All processes can complete: system is safe.

Theorem 4.1. The Banker’s algorithm is correct: if it declares a state safe, there exists a Sequence of process completions that avoids deadlock.

Proof. The safety algorithm constructs an explicit sequence. Each process in the sequence can run To completion with the currently available resources plus those released by previously completed Processes. If no such sequence exists, there is a set of processes whose combined needs exceed Available resources. $\blacksquare$

Allow deadlocks to occur, then detect and recover.

Detection algorithm:

1. Work = Available
   Finish[i] = false if Alloc[i] != 0; true otherwise
2. Find i such that Finish[i] == false AND Request[i] <= Work
3. If found: Work = Work + Alloc[i]; Finish[i] = true; go to step 2
4. If not found: processes with Finish[i] == false are deadlocked

Recovery strategies:

1. Process termination: Kill deadlocked processes one at a time until the cycle is broken.
2. Resource preemption: Forcibly reclaim resources; must handle rollback of the affected process.
3. Checkpoint and rollback: Periodically save process state; restore on deadlock.

Most modern OSes (Linux, Windows) use the ostrich algorithm: ignore deadlocks and rely on process Termination or reboot. Rationale: deadlocks are rare, detection is expensive, and prevention is Overly restrictive.

Confusing deadlock with livelock: Deadlock is when processes wait indefinitely for each other. Livelock is when processes change state but make no progress (e.g., both backing up and retrying). They’re different concurrency problems.

Assuming all four Coffman conditions must be present for deadlock: All four must hold simultaneously. If even one is broken, deadlock cannot occur. Focus on breaking one condition.

Forgetting that deadlock prevention can reduce concurrency: Strategies like resource ordering or requiring all resources upfront limit how processes can request resources. There’s always a trade-off.

• Synchronisation: Mutexes, semaphores, and condition variables.

• Process Management: Process scheduling and lifecycle.

• I/O Systems: I/O resource allocation and deadlock.

• Discrete Mathematics

• Algorithm Implementation