Deadlocks

What is a Deadlock?

A set of processes is in deadlock if each process is waiting for a resource that another process in the set holds. None can progress.

Coffman's Necessary Conditions

Deadlock requires all four conditions simultaneously:

1. Mutual exclusion — at least one resource is non-sharable.
2. Hold and wait — a process holds at least one resource while requesting more.
3. No preemption — resources are released only voluntarily.
4. Circular wait — a cycle of processes each waiting for a resource held by the next.

Breaking any one prevents deadlock.

Resource Allocation Graph (RAG)

Nodes are processes (circles) and resources (rectangles). A request edge P_i → R_j means P_i requests R_j; an assignment edge R_j → P_i means R_j is held by P_i. With single-instance resources, a cycle in the RAG is both necessary and sufficient for deadlock.

Handling Deadlocks

• Prevention — structurally ensure one of Coffman's conditions cannot hold.
• Avoidance — allocate resources only if the system stays in a safe state.
• Detection and recovery — let them happen, then detect and recover.
• Ignorance — ostrich algorithm; used by most desktop OSes.

Deadlock Prevention

• Break mutual exclusion — spool printers; not all resources can be made sharable.
• Break hold-and-wait — require a process to request all resources upfront.
• Allow preemption — forcibly take resources back (possible for CPU and memory; hard for I/O).
• Break circular wait — impose a total order on resources; processes must request in increasing order.

Deadlock Avoidance — Banker's Algorithm

The banker's algorithm requires each process to declare its maximum need. Before granting a request, the OS checks that there is a safe sequence: an order in which every process can complete with the remaining resources plus whatever it will release.

Data structures:

• Available[m] — free resources.
• Max[n][m] — maximum claim per process.
• Allocation[n][m] — currently held.
• Need[n][m] = Max - Allocation.

Safety algorithm: repeatedly find a process whose Need ≤ Available and "run" it, freeing its resources. If all finish, the state is safe.

Deadlock Detection

If prevention and avoidance are not used, periodically check for deadlock. For single-instance resources, run cycle detection on the RAG. For multi-instance, use an algorithm similar to the banker's safety check on the current state.

Recovery

• Process termination — abort all deadlocked processes, or one at a time (by priority, age, resources held) until the deadlock breaks.
• Resource preemption — select a victim, roll it back to a safe checkpoint, and reassign the resource. Starvation must be avoided.

Worked Example

Three processes, three resources A(10), B(5), C(7). Allocation and Max tables given, Available = (3, 3, 2). Apply safety algorithm to find a safe sequence. If one exists, the state is safe; otherwise, deadlock can occur.

Deadlock vs Starvation

A deadlocked process is blocked by a cycle; a starved process is continually skipped by the scheduler. Aging can prevent starvation; careful design and the techniques above prevent deadlock.

Summary

Deadlock is the nightmare of concurrent systems. Understand the four Coffman conditions and choose a handling strategy — prevention, avoidance, or detect-and-recover — that matches the criticality and resource patterns of your system.

Important Questions

1. Define deadlock and state the four Coffman conditions.
2. Draw a resource allocation graph with and without deadlock.
3. Compare deadlock prevention, avoidance, and detection.
4. Explain the banker's algorithm with data structures.
5. Given Max, Allocation, Available, find a safe sequence.
6. List techniques to break circular wait.
7. Describe recovery by process termination and by preemption.
8. Differentiate deadlock and starvation.