Deadlock conditions, detection, action

Necessary conditions

1. Mutual exclusion: a resource can be used by only one process at a time.
2. Hold and wait: a process holds resources while requesting more.
3. No preemption: resources cannot be taken away forcibly.
4. Circular wait: a cycle of processes exists, each waiting for a resource held by the next.

Deadlock detection

The system allows deadlock to happen and periodically runs an algorithm to find it.

1. Resource allocation graph (single instance per resource) Nodes are processes and resources; a request edge is P → R and an assignment edge is R → P. A cycle in the graph means deadlock. (A wait-for graph is also used: P → Q if P waits for a resource held by Q.)

  P1 --> R1 --> P2 --> R2 --> P1   (cycle = deadlock)

2. Matrix algorithm (multiple instances) Uses Available, Allocation and Request.

1. Work = Available; Finish[i] = false if Allocation[i] ≠ 0, otherwise true.
2. Find i with Finish[i] = false and Request[i] ≤ Work.
3. Work = Work + Allocation[i]; Finish[i] = true; repeat.
4. Processes with Finish = false are deadlocked.

Detection is run at fixed time intervals or when CPU utilisation falls below a threshold, since running it on every request is costly.

Action after detection (recovery)

1. Process termination

• Abort all deadlocked processes (simple but costly), or
• Abort one process at a time until the cycle is broken. The victim is chosen by priority, time already computed, resources held, resources still needed, and whether it is interactive.

2. Resource preemption

• Select a victim and take its resources away to give to another process (minimising cost).
• Roll the victim back to a safe state (checkpoint) and restart it.
• Prevent starvation by limiting the number of times the same process is chosen as a victim.

3. Manual recovery: the operator is informed and kills processes by hand; e.g. in UNIX, which largely ignores deadlock (the ostrich approach), the system administrator kills the stuck processes.