Deadlock conditions; detection with example

Deadlock

Deadlock is a state in which a set of processes are all blocked, each waiting for a resource that is held by another process of the set.

Essential conditions

1. Mutual exclusion: resources are non-sharable.
2. Hold and wait: a process holds a resource while waiting for another.
3. No preemption: resources are released only voluntarily.
4. Circular wait: a circular chain of waiting processes exists.

Detecting deadlock

Resource allocation graph (RAG). Draw processes as circles and resources as boxes; an edge R → P means R is allocated to P, and P → R means P is requesting R. If every resource has a single instance, a cycle in the RAG means deadlock.

Matrix method (multiple instances). Keep Available (A), Allocation (C) and Request (R). Set Work = A, mark processes with zero allocation as finished, then repeatedly select a process whose Request ≤ Work, add its Allocation to Work and mark it finished. Processes still unmarked at the end are deadlocked.

Example

Take two processes and two resource types A and B with one instance each.

 P1 holds A, requests B
 P2 holds B, requests A

 A --> P1 --> B --> P2 --> A   (cycle)

Allocation: P1 = (1,0), P2 = (0,1); Request: P1 = (0,1), P2 = (1,0); Available = (0,0).

Work = (0,0). P1's request (0,1) is not ≤ (0,0), and P2's request (1,0) is not ≤ (0,0). No process can be marked, so both P1 and P2 remain unmarked and the system is deadlocked. The cycle A → P1 → B → P2 → A in the RAG shows the same thing.