Four deadlock conditions; prevention, recovery

Four essential conditions

1. Mutual exclusion: a resource can be held by only one process at a time (e.g. printer).
2. Hold and wait: a process holds at least one resource and waits for others.
3. No preemption: a resource can be released only voluntarily by the process holding it.
4. Circular wait: processes form a circle, each waiting for a resource held by the next.

Preventing deadlock

The OS must make sure at least one condition never holds.

• Mutual exclusion: spool shared devices (e.g. printer spooler) so no process holds the device directly.
• Hold and wait: a process must request all resources at the start, or release all held resources before requesting more.
• No preemption: if a request cannot be granted, the process releases everything it holds and retries later; or the OS preempts resources of waiting processes.
• Circular wait: give each resource type a number and let processes request only in increasing order; no cycle can form.

Recovery from deadlock

After detection, the system recovers by:

1. Process termination: abort all deadlocked processes, or abort one at a time until the deadlock disappears. The victim is chosen by priority, running time, resources used, resources needed.
2. Resource preemption: take a resource from one process and give it to another; roll the victim back to a safe state (checkpoint) and restart it. To avoid starvation, count rollbacks per process.
3. Recovery by rollback: processes periodically checkpoint their state; on deadlock, a process holding a needed resource is restarted from an earlier checkpoint, releasing it.