Deadlock conditions; recovery methods

Deadlock

A set of processes is deadlocked if each process is waiting for an event (release of a resource) that can be caused only by another process in the set.

Conditions for resource deadlock (Coffman)

1. Mutual exclusion: each resource is either assigned to exactly one process or is available.
2. Hold and wait: processes holding earlier-granted resources may request new ones.
3. No preemption: resources previously granted cannot be forcibly taken away.
4. Circular wait: a circular chain of two or more processes exists, each waiting for a resource held by the next one.

Recovery from deadlock

1. Recovery through preemption: temporarily take a resource away from its owner and give it to another process. This often needs manual intervention and depends on the resource (e.g. suspending a process and giving its printer to another is difficult, but taking memory by swapping is possible).
2. Recovery through rollback: processes are checkpointed regularly (state and resources saved in files). On deadlock, a process that owns a needed resource is rolled back to a checkpoint before it acquired it, and the resource is given to a waiting process.
3. Recovery through killing processes: the simplest. Kill one process in the cycle, or all of them. The victim should be one that can be rerun without bad effects (e.g. a compile, not a database update). The process is chosen using priority, run time, and resources held.

After recovery, care is needed to avoid starvation, so the same victim is not chosen repeatedly.