Deadlock
A computer system has a finite set of resources, which may be hardware such as memory, CPU, or printer or pieces of information such as shared variables, files, etc. It also has a limited set of processes that want to use these available resources. So any process in a system that wants to use any of these resources makes a request for the resource. The usual sequence of steps that occur when a resource is used by a process is as follows:
1. Request the resource
2. Use the resource
3. Release the resource.
Numerous processes run at the same time. In a multiprogramming system, they compete for available resources. In this type of situation, a deadlock may arise. Deadlock is a type of synchronization problem that occurs when several processes compete for available shared resources, such as files, I/O devices, or locks. It has major impacts on the system, including data loss, system crashes, decreased productivity, etc. Here, we will discuss the concept of deadlocks in operating systems, their causes, and methods for handling them.
"A deadlock is a situation that occurs when two or more than two processes are blocked for indefinite time period, each process waiting for the other process to release a hold resource.” For example, a system has two processes, A and B, and two resources, one is the output device printer, and the other is the input device tape drive. Process A requests a tape drive, system accept the request, so Process A acquires it. Similarly, process B requests a printer. At that time, the printer was free, so the system granted it to Process B. Now process A requires a printer along with a tape drive, so it requests a printer too. The request is denied by the system because B is using the printer. At the same time, process B also requests a tape drive, but the request is denied by the system because process A using it. So a situation arises where both processes are waiting for each other to release the resource. They are blocked; that is, they remain in this situation forever. This is a deadlock situation. A resource allocation graph shows the processes that now have resources and those that are waiting for specific types of resource.
Fig1: Resource allocation graph
Causes of Deadlock
A deadlock occurs in a system when all four conditions or prerequisites are met at the same time. If one of them is avoided, the deadlock is broken. The conditions are discussed below:
1.Mutual exclusion
It is necessary to hold at least one resource in a non-shareable mode. It indicates that the resource may only be used by one process at a time. If multiple processes make a request for any resource, and suppose that the requested resource is not available then the request must be put on hold until the resource release. In other words, if a process P1 is utilising a resource R at a certain moment, then that same resource R cannot be held or used by another process P2 at that same moment. Although P2 just requests it, it is impossible for process P2 to use resource R concurrently with process P1.
2.Hold and wait.
Hold and wait is a condition in which a process has to have at least one resource in its possession while at the same time waiting to obtain other resources that another process is holding. For instance, a process P1 may simultaneously have two resources, R1 and R2, and make a request for some resource R3, which process P2 is presently holding.
3.No Preemption
One cannot preempt resources. The process that is holding the resource must choose to release it after the process has finished its job. One process cannot forcibly remove a resource from another process. For instance, when a process P1 employs a resource R, that resource cannot be taken by force by another process P2. Process P2 has the ability to request resource R and wait for process P1 to release the resource.
4.Circular wait
There is a collection of waiting processes in which p0 is waiting for resources held by p1, p1 is waiting for resources held by p2,... pn-1 is waiting for resources held by pn, and pn is waiting for resources held by p0. A situation arises where no process is releasing its own resource; instead, all processes are waiting for each other to release the resource. Everyone is trying to get the resource, but no one can acquire it. This situation is termed a circular wait.
Fig3: Processes in Circular wait
METHODS FOR RESOLVING THE PROBLEM OF DEADLOCKS
There are several methods with the help of which deadlock problems can be handled. These methods include the following:
Deadlock prevention,
Deadlock avoidance,
Deadlock detection and recovery
1.Deadlock Prevention
Prevention of deadlocks occurs by ensuring that, among the four deadlock conditions, at least one is not satisfied. If we successfully eliminate one of the four conditions, the deadlock will not occur. Many strategies were applied to violate the necessary deadlock condition.
Mutual exclusion can easily be resolved for shareable resources, for example, read-only files. Several processes can read the file simultaneously without interfering with other processes. But there are some resources that are intrinsically nonshareable, for example, printers, so in this case, we can’t get rid of mutual exclusion because printers are not used by multiple processes simultaneously.
Deadlock can also be avoided by eliminating the hold and wait conditions. The hold and wait condition can be denied in two different ways. One approach is to process requests for all the resources at once when they are needed. If all the requested resources are available, then these resources are granted to the process . However, the system will not grant any resources if any of the requested resources are not available. The other approach is that the process acquires or requests a new resource only when it releases all the resources it has.
No preemption condition can also be denied for deadlock prevention. In order to avoid a preemption condition, the system should take away resources from processes when they are waiting for other resources. for example, a process that holds a tape drive and requests a printer that is not available at that time. Then the system also takes away the tape drive from the process. Now the process is in a state of waiting for both the tape drive and the printer.
Deadlock can also be prevented by making a circular wait impossible. A number is assigned to each resource, and the process can make requests for resources in increasing order. For example, for a disc drive, number 1 is given, and number 3 is given to the printer. A process wants to read a disc drive and then print the result, so it will first allocate a disc drive and then print.
2.Deadlock avoidance
Deadlock avoidance is a technique in which resources are allocated to a process in such an order as to prevent deadlock occurrence. This technique ensures that after resource allocation, the system will be in a safe state. “A state is said to be safe if the system may allocate the required resources to each process without forcing deadlock.”.
There are different algorithms used that determine whether the system is in a safe state or not after resource allocation. One popular algorithm is the “recourse allocation graph algorithm,” and the other is the banker algorithm.
The resource allocation graph algorithm uses a graph to describe different deadlocks. Two different types of nodes present in a graph. One node is used for resource representation, and the other node is used for process representation. The resource node is rectangular in shape, while the process node is circular in shape. Edges are used for node connection. There are three types of edges. One edge represents resource allocation, which goes from resources to processes. One represents resource requests, which go from process node to resource node, and the third is the claim edge, represented by a dashed line, which represents that a process may request a resource in the future. The dashed line is counted into solid lines when the resource is requested by a process and the system allocates it to that process. But before the allocation system, ensure that the resource allocation does not form a cycle .
Resource allocation graph with claim edge
In order to understand the algorithm clearly. Consider the above-given figure. According to the graph given in the figure, Resource 1 is allocated to Process 1, while Process 2 makes a request for Resource 1. Thus, Process 2 is in a waiting state as Resource 1 is not free. At the same time, Process 2 makes requests for Resource 2 too, which is required by P1 in the future, so if we allocate Process 2 a Resource 2, then a cycle will be created. Process 1 is waiting for Process 2 to release Resource 2. In the same way, Process 2 is also waiting for Resource 1, which is in the possession of Process 1. In order to avoid such a situation, Resource 2 should not be allocated to Process 2.
The above algorithm is not applied in cases where there are multiple instances of each resource type. In such a case, the banker algorithm can be used. The OS's bankers algorithm is used to safely distribute resources across all of the processes running on the system in order to avoid deadlocks. Every process in the system has to notify the operating system of all significant information, including impending processes, resource demands, delays, etc. The system then makes a decision based on the available details about whether to allocate resources to a process and run it or deny the request. The banker algorithm integrates the safety algorithm and the resource request algorithm. The safety algorithm finds out if the system is in a safe condition, while the resource request algorithm finds out how the system responds to a resource request from a process.
3.Deadlock Detection and Recovery
If the system does not have any of the preventive or avoidance methods, there is a chance that deadlock may occur. So there should be mechanisms to detect and recover.For deadlock detection, a system uses a variant of the resource allocation graph called the wait for graph. In this graph, processes are not waiting for resources, but instead they are waiting for other processes that hold these resources. A cycle in the graph shows the occurrence of deadlock. In order to detect deadlock, the deadlock detection algorithm runs from time to time during the system's execution lifetime. Deadlock recovery requires the killing of one or more processes that involve a deadlock. We can also recover from deadlock by using resource pre-emption methods.
You must be logged in to post a comment.