Deadlock

In a computer system, Deadlock is a state where two or more processes are unable to move forward; this is known as a deadlock. Each process waits for a resource held by another process in the group. This results in a situation where none of the processes can continue, and the system becomes stuck, unable to progress.

Understanding Deadlock is essential in computer science as it can cause significant problems for software and hardware systems. Deadlock can lead to lost productivity, system crashes, and data loss. Therefore, it is crucial to understand the conditions that can cause Deadlock and how to prevent or recover from it.

Definition of Deadlock

Deadlock is a state where each process in a group waits for a resource held by another process. None of the processes can proceed until the resource they need become available, which may never happen.

Characteristics of Deadlock

The Deadlock has the following characteristics:

• Mutual exclusion:  Each resource can only be held by one process at a time.
•  Hold and wait: A process holding a resource can request other resources.
•  No preemption: Resources cannot be taken away from a process until the process releases them voluntarily.
•  Circular wait:  A set of processes waits for each other in a circular chain.

Conditions of Deadlock

1. Mutual Exclusion – Only one process can access a resource at a time. If a process has already acquired a resource, then this process can only access it once the first process releases it. Imagine a situation where several processes attempt to use a printer. In the absence of mutual exclusion, it is feasible for two or more processes to use the printer simultaneously, resulting in conflicts and mistakes. Nevertheless, mutual exclusion guarantees that only one process can use the printer at a time, ensuring that the printer runs smoothly and effectively.
2.  Hold and Wait – A process is holding a resource and waiting for another resource that is currently held by another process. Neither process can proceed as long as both processes continue to hold their respective resources. Imagine a situation where two processes, A and B, need two resources, X and Y, respectively, to finish their tasks. Process A obtains resource X and retains it while waiting for resource Y, which currently possesses process B. Likewise, process B holds resource Y while waiting for resource X, which is in the possession of process A. This leads to a deadlock, where neither process can move forward until one of them releases its resource.
3.  No Preemption – A resource cannot be forcibly taken away from a process that is currently holding it. The resource can only be released voluntarily by the process holding it. Consider a scenario where two processes, A and B, compete for a printer resource. If process A currently uses the printer, process B cannot interrupt and take over the printer until process A has finished and released the resource. This ensures that processes are given fair access to resources and prevents conflicts from arising.
4.  Circular Wait – A set of processes waits for each other in a circular chain. Each process is waiting for a resource held by the next process in the chain, and the last process waits for a resource held by the first process in the chain. Consider a scenario where two processes, A and B, are trying to access two resources, X and Y. Process A has resource X and is waiting for resource Y, while process B has resource Y and is waiting for resource X. This creates a circular wait, where neither process can proceed until the other releases the resource it needs.

Deadlock Prevention

 The deadlock occurrence depends on the fulfilment of four necessary conditions. We must ensure that at least one of these conditions cannot hold to prevent a deadlock. To elaborate on this approach, let us examine the four necessary conditions separately.

Mutual-Exclusion:

 For non-sharable resources, mutual exclusion is a necessary condition. For instance, several processes cannot share a printer simultaneously. On the other hand, shareable resources don’t need mutually exclusive access, thus they can’t get stuck in a deadlock. Read-only files exemplify a shareable resource. Several processes can open a read-only file simultaneously and be granted simultaneous access. A process can hold a sharable resource for some time. However, denying the mutual exclusion condition cannot prevent deadlocks because some resources are intrinsically non-sharable.

Hold and Wait: 

To make sure that the hold-and-wait condition never occurs in the system, we must ensure that a process does not hold any other resources whenever it requests a resource.

 One protocol allows for all processes to request and get their full set of resources before starting their executions.

 Another protocol enables a process to ask for resources only when it has none. A process may request some resources, use them, release all the resources it currently holds, and then request additional resources. Both these protocols have two main disadvantages. First, resource utilization may be low because resources may be allocated but unused for an extended period. Second, starvation is possible.

No Preemption:

 The third necessary condition for deadlocks is the absence of preemption of resources that have already been allocated. We can use the following protocol to ensure this condition does not hold. First protocol: If a process holds some resources and requests another resource that cannot be immediately allocated, we preempt all resources currently held by the process. Second protocol: If a process requests some resources, we check whether they are available. If they are, we allocate them. If not, we check whether they are allocated to another process waiting for additional resources. If yes, we allocate the requested resources to the asking process instead of waiting for them to be needed. If the resources are neither accessible nor held by a waiting process, the requesting process must wait.

Circular Wait: 

The fourth condition that can lead to deadlocks is the circular-wait condition. However, there is a way to prevent this condition from occurring. We can ensure that deadlocks never happen by imposing a specific ordering on all resource types and requiring each process to request resources in increasing order of enumeration.

We first assign a unique integer number to each resource type to implement this solution. This allows us to compare two resources and determine which one precedes the other in our ordering. We can define a function F: R → N, where R is the set of resource types and N is the set of natural numbers.

For instance, if we have tape drives, disk drives, and printers in our resource set, we can define F as follows:

F(tape drive) = 1

F(disk drive) = 5

F(printer) = 12

To avoid deadlocks, we can use the technique described below: Each process can only ask for resources in increasing order of enumeration. This means that any number of instances of a resource type a process may request Ri at first. The process can thus only make requests for instances of resource type Rj if F(Rj) > F(Ri). If multiple instances of the same resource type are required, only one request needs to be made.

By following this protocol, we can ensure that deadlocks never occur due to the circular-wait condition. This approach is a simple yet effective way to manage resources and prevent system failures.

Deadlock Avoidance

There are several techniques for avoidance, including the Resource Allocation Graph and the Banker’s Algorithm.

Resource Allocation Graph

The Resource Allocation Graph is a directed graph representing the current resource allocation and requests. A node represents each process, and a resource-type node represents each resource. The edges represent the requests and the allocation of resources. If there is a cycle in the graph, then a Deadlock is possible. In this case, the system must prevent the request that caused the cycle from being granted. Let’s consider an example to understand this technique better.

Suppose we have three processes: P1, P2, and P3, and three resource types: R1, R2, and R3. The current allocation of resources is as follows:

ProcessR1R2R3

P1 1 0 1

P2 1 1 0

P3 0 1 1

Now let’s say process P1 requests resource R2. The system will add an edge from P1 to R2, representing the request. If granting this request leads to a cycle in the graph, then Deadlock is possible, and the request must be denied.

Banker’s Algorithm:

The Banker’s Algorithm is another technique for avoidance. In this technique, the system keeps track of each process’s maximum resources and current resources. The system then checks if granting a request will result in a safe state. A safe state is one where at least one sequence of allocating resources to processes that do not result in Deadlock. The request is granted if the requested resources can be given without entering an unsafe state; otherwise, it is denied.

Let’s consider an example to understand this technique better. Suppose we have three processes: P1, P2, and P3, and three resource types: R1, R2, and R3. The maximum resources each process can use, and the resources currently in use are as follows:

ProcessR1R2R3Available

P1 3 1 2 2

P2 2 1 1 1

P3 2 2 2 2

Total 7 4 5 5

Now let’s say process P1 requests one unit of resource R2. The system checks if granting this request will result in a safe state. To do this, the system checks if there is a sequence of allocating resources to processes that do not result in Deadlock. In this case, the arrangement would be:

1. Allocate one unit of R2 to P1.
2.  Allocate one unit of R1 to P2.
3.  Allocate one unit of R3 to P3.
4.  Allocate one unit of R2 to P2.
5.  Allocate one unit of R2 to P1.

This allocation sequence does not result in Deadlock, so the request is granted.

In conclusion, avoidance is a technique that can be used to prevent Deadlock from occurring in computer systems.