Deadlocks

In operating systems, a deadlock is a situation where two or more processes are unable to proceed because each is waiting for the other to release a resource. Imagine two cars approaching an intersection from different directions, and neither is willing to back up. This is a deadlock. In computing, it's a common problem that can halt system operations if not managed properly.

A deadlock can be formally defined as a set of processes, each of which is waiting for an event that can only be caused by another process in the set. These events are typically the release of a resource that is currently held by another process in the set.

Deadlock Characterization

For a deadlock to occur, four necessary conditions, known as the Coffman conditions, must hold simultaneously. If any one of these conditions is not met, a deadlock cannot occur. Understanding these conditions is crucial for designing systems that prevent or handle deadlocks effectively.

1. Mutual Exclusion

At least one resource must be held in a non-sharable mode. This means that only one process can use the resource at any given time. If another process requests access to this resource, it must wait until the resource has been released. For example, a printer is a classic example of a non-sharable resource; only one process can print at a time.

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. A process might request resources incrementally, holding onto the ones it already has while waiting for new ones. This can lead to a chain of dependencies.

3. No Preemption

Resources cannot be preempted; that is, a resource can only be released voluntarily by the process holding it after that process has completed its task. If a process is holding resources and requests more, it cannot be forced to release the resources it currently holds. The system cannot take away a resource from a process.

4. Circular Wait

A set of waiting processes {P0, P1, ..., Pn} must exist such that P0 is waiting for a resource held by P1, P1 is waiting for a resource held by P2, ..., Pn-1 is waiting for a resource held by Pn, and Pn is waiting for a resource held by P0. This creates a cycle of dependencies.

Deadlock Prevention

Deadlock prevention strategies aim to ensure that at least one of the four necessary conditions for deadlock cannot hold. By violating one of these conditions, we can guarantee that deadlocks will not occur.

1. Preventing Mutual Exclusion

This condition is often difficult to eliminate because many resources are inherently non-sharable. However, for resources that can be shared, like read-only files, mutual exclusion is not required, and thus, deadlocks related to these resources can be avoided. For strictly non-sharable resources, this condition must hold.

2. Preventing Hold and Wait

One approach is to require all processes to request and be allocated all their required resources before they begin execution. Alternatively, a process can only request resources when it holds no other resources.

Method 1: All Resources Allocated at Once A process must request all of its resources at the time it starts execution. If all resources are available, they are allocated to the process. Otherwise, the process must wait for all requested resources to become available. Drawback: This can lead to low resource utilization and potential starvation if a process requests a rare resource that is often unavailable.

Method 2: Request Resources Only When None Held A process that holds resources may not request any additional resources. If it needs more resources, it must first release all currently held resources. Drawback: This can also lead to low resource utilization and may increase the probability of starvation, as a process might have to repeatedly release resources it needs.

3. Preventing No Preemption

If a process holding some resources requests another resource that cannot be immediately allocated to it, the process will be preempted. All resources it is currently holding are released. The preempted resources are added to the list of resources for which the process is waiting. The process will be restarted only when it is able to regain its original resources, as well as any new ones it requested.

This method is often complex to implement and can be inefficient, especially if preemption of a resource leads to a loss of significant work done by the process.

4. Preventing Circular Wait

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

For example, if resource types are numbered 1, 2, ..., n, then a process can request any number of instances of resource type R_i, but it can only request instances of resource type R_j if j > i. This means a process holding resource R_i can only request resources R_j where j is greater than i. If a process P_k holds R_i and requests R_j (where j > i), and another process P_m holds R_j and requests R_k (where k < j), then P_m must be requesting a resource with a lower index than R_j. If P_m also holds R_k (k < j), it cannot be holding R_i (i < j) because it would violate the ordering rule. This prevents the circular dependency.

Deadlock Avoidance

Deadlock avoidance is a more sophisticated approach than prevention. Instead of trying to eliminate the conditions for deadlock, avoidance algorithms dynamically analyze the resource allocation state of the system to ensure that a sequence of resource allocations can be made that does not lead to a deadlock. The system makes a decision on whether to grant a resource request based on whether it might lead to a deadlock in the future.

The most well-known deadlock avoidance algorithm is the Banker's Algorithm. This algorithm requires that each process declare the maximum number of resources of each type that it might request.

The Banker's Algorithm

The Banker's Algorithm operates by maintaining state information about resource allocation. This state includes:

• The number of available resources of each type.
• The maximum demand of each process.
• The current allocation of resources to each process.
• The remaining needs of each process.

The algorithm checks if granting a resource request leads to a "safe state." A state is safe if there exists a sequence of all processes in the system such that for each process P_i, the resources that P_i can still request can be satisfied by the currently available resources plus the resources held by all processes P_j, where j comes after i in the sequence. If a process can complete, it releases its resources, making them available for subsequent processes.

Algorithm Steps: When a process P_i makes a request for resources:

1. If the request is greater than the remaining need of P_i, it's an error (process has exceeded its maximum claim).
2. If the request is greater than the available resources, P_i must wait.
3. If the request is less than or equal to available resources, the system tentatively allocates the resources to P_i. It then updates the available resources and the remaining need of P_i.
4. The system then checks if the resulting state is safe. It does this by finding a sequence of processes that can complete.
5. If the state is safe, the request is granted, and the resources are allocated.
6. If the state is unsafe, the request is denied, and P_i must wait. The system state is restored to what it was before the tentative allocation.

Drawbacks of Banker's Algorithm:

• Requires processes to declare their maximum resource needs in advance, which is often impractical.
• Can be computationally expensive, as it requires recalculating the safe state after every resource allocation.
• Can lead to lower resource utilization because resources might be held longer than necessary to maintain a safe state.

Deadlock Detection

Deadlock detection algorithms are used when the system does not employ prevention or avoidance strategies. These algorithms periodically check the system's state to identify if a deadlock has occurred. If a deadlock is detected, the system must then take action to recover from it.

Detection algorithms typically use a resource-allocation graph or a variation of it. A resource-allocation graph is a directed graph where nodes represent processes and resource types. Edges represent resource requests and allocations.

Resource-Allocation Graph

• A set of processes P = {P0, P1, ..., Pn}.
• A set of resource types R = {R1, R2, ..., Rm}.
• A directed edge from P_i to R_j (P_i → R_j) means P_i is requesting an instance of R_j.
• A directed edge from R_j to P_i (R_j → P_i) means an instance of R_j is allocated to P_i.

Cycle Detection:

• If the graph contains no cycles, then there is no deadlock.
• If the graph contains a cycle, a deadlock exists.
• If each resource type has only one instance, the detection of a cycle is a necessary and sufficient condition for deadlock.
• If resource types have multiple instances, a cycle is a necessary but not sufficient condition for deadlock. A more complex algorithm is needed to check for deadlocks when multiple instances of resources exist.

Wait-For Graph

When each resource type has only one instance, the resource-allocation graph can be simplified into a wait-for graph. In a wait-for graph, nodes represent processes, and a directed edge from P_i to P_j means P_i is waiting for a resource currently held by P_j.

A deadlock exists if and only if the wait-for graph contains a cycle.

Algorithm for Detecting Deadlocks (with multiple instances of resources)

This algorithm is a variation of the Banker's Algorithm's safety check. It uses vectors and matrices to represent the system state. Let:

• `Available[m]` be a vector of length m indicating the number of available instances of each resource type.
• `Allocation[n, m]` be a matrix indicating the number of instances of each resource type currently allocated to each process.
• `Request[n, m]` be a matrix indicating the current request of each process.

The algorithm proceeds as follows:

1. Initialize `Work[m]` = `Available` and `Finish[n]` = {false} for all processes P_i.
2. Find an index i such that `Finish[i]` is false and `Request[i]` ≤ `Work`.
3. If no such i exists, go to step 4.
4. If such an i exists, set `Work` = `Work` + `Allocation[i]` and `Finish[i]` = true. Go to step 2.
5. If `Finish[i]` is false for some i (0 ≤ i < n), then the system is in a deadlock state. The processes P_i for which `Finish[i]` is false are the deadlocked processes.

Deadlock Recovery

Once a deadlock is detected, the system must take steps to recover. Recovery involves breaking the deadlock by aborting one or more processes or preempting resources from one or more processes.

1. Process Termination

There are two ways to abort processes to break a deadlock:

• Abort one process at a time: Repeatedly abort a process until the deadlock is eliminated. Choose the process to abort based on factors like:
  • Priority of the process.
  • How long the process has computed.
  • How many more resources the process needs to complete.
  • The number of processes already involved in the deadlock.
  • Whether the process is computing or interacting.
• Abort all processes involved in the deadlock: This is simpler to implement but can be very expensive if these processes have done significant work.

2. Resource Preemption

To break the deadlock, we need to preempt resources from one or more processes.

• Select a victim: Choose a process from which to preempt resources. The selection criteria can be similar to those used for process termination (e.g., cost of preemption, amount of resources held).
• Rollback: A more complex recovery method is to roll back processes to a previous checkpoint. This requires the system to periodically save the state of processes. The goal is to restart processes from a state where the deadlock did not occur. This avoids loss of computation but requires careful management of checkpoints.
• Starvation: A potential issue with resource preemption is starvation. If we always choose the same process as the victim, it may never complete its execution. To avoid starvation, we must ensure that each victim process is chosen only once.