Avoidance, detection, prevention techniques

Deadlock avoidance

The OS has advance information on the maximum resources each process may request. It grants a request only if the resulting state is safe, i.e. there is some order in which all processes can complete. The Banker's algorithm (Dijkstra) is the standard method. Unsafe states are not necessarily deadlocked, but are avoided.

Deadlock detection

The system does not prevent or avoid deadlock; it lets it occur, then detects it by examining a resource allocation graph (cycle means deadlock) or by the matrix detection algorithm, and recovers by terminating processes or preempting resources.

Deadlock prevention techniques

Prevention ensures that at least one of the four necessary conditions can never hold.

1. Attacking mutual exclusion: make resources sharable where possible (e.g. spooling a printer so only the spooler daemon uses it). Not all resources can be shared.
2. Attacking hold and wait: require a process to request all its resources before starting (or to release all it holds before asking for more). Drawbacks: low resource utilisation, starvation, and the need to know all requirements in advance.
3. Attacking no preemption: if a process holding resources requests another one that is unavailable, all its held resources are preempted (released implicitly) and it restarts later when all can be had. Works for state-saveable resources (CPU registers, memory), not for printers.
4. Attacking circular wait: number all resource types and require processes to request resources only in increasing numerical order (or hold only one at a time). A cycle can then never form. Drawback: finding a natural ordering that suits all processes is hard.