Deadlock Conditions & Prevention

In a multiprogramming environment, several processes may compete for a finite number of resources. A process requests resources; if the resources are not available at that time, the process enters a waiting state. Sometimes, a waiting process is never again able to change state because the resources it has requested are held by other waiting processes. This situation is called a deadlock.

1. System Model

A system consists of a finite number of resources to be distributed among a number of competing processes. The resources are partitioned into several types (e.g., CPU cycles, memory space, files, I/O devices).

Under the normal mode of operation, a process may utilize a resource in only the following sequence:

1. Request: The process requests the resource.
2. Use: The process operates on the resource.
3. Release: The process releases the resource.

2. Necessary Conditions for Deadlock

A deadlock situation can arise if and only if the following four conditions (often called the Coffman conditions) hold simultaneously in a system:

1. Mutual Exclusion: At least one resource must be held in a non-sharable mode; that is, only one process at a time can use the resource.
2. Hold and Wait: A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes.
3. No Preemption: Resources cannot be preempted; that is, a resource can be released only voluntarily by the process holding it, after that process has completed its task.
4. Circular Wait: A set of waiting processes must exist such that $P_0$ is waiting for a resource held by $P_1$, $P_1$ is waiting for a resource held by $P_2$, ..., and $P_n$ is waiting for a resource held by $P_0$.

3. Deadlock Prevention

Deadlock Prevention provides a set of strict rules to ensure that at least one of the four necessary conditions cannot hold. By preventing just one condition, deadlocks become mathematically impossible.

1. Breaking Mutual Exclusion

We can prevent deadlocks by making all resources sharable.

• Problem: While read-only files are sharable, physical resources like a printer are fundamentally non-sharable. We cannot break this condition for all resources.

2. Breaking Hold and Wait

We must guarantee that whenever a process requests a resource, it does not hold any other resources.

• Solution: Require a process to request and be allocated all its resources before it begins execution.
• Problem: Resource utilization may be very low, since many of the resources may be allocated but unused for a long period. Starvation is also possible.

3. Breaking No Preemption

If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are preempted (taken away).

• Problem: This works for resources whose state can be easily saved and restored (like CPU registers), but it cannot be applied to resources like printers or tape drives.

4. Breaking Circular Wait

This is the most practical prevention method. We impose a total ordering of all resource types and require that each process requests resources in an increasing order of enumeration.

• Solution: Number all resources (Tape Drive = 1, Disk Drive = 2, Printer = 3). A process must always request resource 1 before resource 2. A circular wait is mathematically impossible under this strict ordering constraint.