What is Deadlock?

A set of processes is deadlocked if every process in the set is waiting for an event that only another process in the set can cause.

The cycle in the resource-allocation graph proves deadlock when each resource has a single instance.

System Model

• Resource types R1, R2, ..., Rm (CPU, memory, devices, files).
• Each type has Wᵢ instances.
• A process uses a resource in three steps: request → use → release.

The Four Coffman Conditions

All four must hold simultaneously for deadlock to be possible:

1. Mutual Exclusion — at least one resource type is non-shareable.
2. Hold and Wait — a process holds resources while waiting for more.
3. No Preemption — resources cannot be forcibly taken; the holder must release.
4. Circular Wait — there is a cycle P0 → P1 → ... → Pn → P0 in the wait graph.

Resource-Allocation Graph (RAG)

• Vertices: processes (circles), resource types (squares with dots for instances).
• Request edge: P → R.
• Assignment edge: R → P.
• Cycle + single instances → deadlock.
• Cycle + multiple instances → possible deadlock (need further analysis).

Methods for Handling Deadlocks

1. Ignore — let it happen, reboot when noticed (Ostrich algorithm; common in PC OSes).
2. Prevention — design protocols that violate one Coffman condition.
3. Avoidance — give each request only if the system stays in a "safe state" (Banker's algorithm).
4. Detection & Recovery — let deadlock occur, detect cycles, and recover.

Worked Example — Two-resource Deadlock

• R1 = printer, R2 = tape drive (one instance each).
• P1 holds printer, requests tape.
• P2 holds tape, requests printer.

Both wait forever — classic deadlock. Resolution requires preemption (kill one) or rollback.

Comparison Table

Summary

• Deadlock = circular wait under non-preemptable, non-shareable resource holds.
• Coffman's four conditions are necessary; breaking any one breaks deadlock.
• The four management strategies trade off complexity, performance, and risk.