Handling Deadlock

Dealing with Deadlock

Prevention
- Build systems where deadlock couldn’t possibly occur.
Avoidance
- Make decisions dynamically as to which resource requests can be granted.
Detection and Recovery
- Allow deadlock to occur, then cure it.
Ignore the Problem

There are several techniques to prevent deadlock:

Force processes to claim all resources in one operation.
- Problem of under-utilisation.
- Process might hog a resource it no longer needs.
Require processes to claim resources in pre-defined order.
- Resource $A$ always before resource $B$.
- Avoids processes waiting for each other.
Grant request only if all allocated resources released first.
- Release resource $A$ before allowing claim for resource $B$.
- Avoids processes hogging resources needlessly.

Requires information about which resources a process plans to use.

When a request is made, system analyses allocation graphs to see if it could lead to deadlock:

If so, process is forced to wait.
Can lead to reduces throughput and process starvation.
- Might not actually need to wait.

This is done by analysis of cycles.

Requires analysis of a wait-for graph:

This is similar to the directed graph seen earlier.
- Costly to do for every request.
- May be better to do at regular intervals, or when CPU usage deteriorates too much.
Recovery could involve process termination.
- All involved:
  - May mean huge loss of computation.
- One at a time:
  - Expensive; requires re-run of detection algorithm after each termination.
Recovery could involve pre-emption, with its own problems:
- Choice of victim.
- Rollback
- Starvation

This is the common approach for Windows, Unix, Java and others.

Why is this useful to implement:

Cheap to implement.
Saves a lot of processing time.
Risk of deadlock is small in most well-written systems.

This relies on programs to incorporate deadlock avoidance themselves.
Modern processors are faster.
Puts burden onto the end user.