What is Deadlock in Operating System : Conditions & Detection Algorithm

The main objective of an operating system is to provide proper communication between hardware and software resources and also give common services to programs. When an operating system process wants to access any resource, it firstly sends a request to the particular resource which it wants to access, then it utilizes the resource and finally releases the resource after using. For suppose many processes are trying to access one resource at the same time, it becomes difficult to provide one resource to all the processes at a time in such a situation the concept named deadlock arises. Hence this article describes how deadlock occurs and how to overcome this deadlock situation.

What is the Deadlock in Operating System?

Definition: Dead-Lock is a situation where two or more processors are waiting for some event to happen, but such events that don’t happen is a deadlock condition, and the processors are said to be in a deadlock state. For instance, let us assume a real-time scenario, where there are two cars A & B, driven by two individual drivers on a one-way road. Now the situation arises where Car A driver says he moving towards north is a correct direction, while Car B driver says he moving toward south direction is correct. But neither of one moves back to allow another car to move forward, this condition is called a deadlock condition.

For better understanding let us consider another example where there two resources R1, R2, and two processes P1 and P2, where R1 is assigned to P1 and R2 is assigned to P2. Now if P1 wants to access R2, as we already know R2 is held by P2, and now P2 wants to access R1, which is P1 executes only when it gets accessed to R2, also P2 executes only when it gets accessed to R1 this situation is a deadlock state.

Dead-Lock Conditions

The following are the four important deadlock conditions to occur if all the conditions occur simultaneously there are certain chances for the deadlock to occur.

Mutual Exclusion

It means whatever resource we are using it must be used in a mutually exclusive way. Where only one processes use one resource at a time only. For example, the printing process is going on and all sudden another process tries to interrupt the printing process. So here in mutual exclusion situation, only after the printing task is completed then only the next task is processed. Mutual exclusion can be eliminated by sharing resources simultaneously, which is not possible practically.

 No Pre-emption

According to pre-emptive based algorithms, if there is a priority task trying to interrupt the current task. The pre-emptive algorithm it holds the current task and firstly executes priority task and get backs to its first task.  A situation explained as per the above example where a process holds the resource as long as it gets executed, that is P1 can release R1 only after executing, similarly P2 release R2 only after execution. If there is no pre-emption the deadlock may occur.

Hold and Wait

A process is holding some resources and is waiting for additional resources but those resources are acquired by some other process. From the above example, P1 is holding R1 and waiting for R2, where R2 is acquired by P2, and P2 is holding R2 and waiting for R1, where R1 is acquired by P1 is a hold and wait situation deadlock may occur in the system.

 Circular Wait

A set of processes are said to be in deadlock if one process is waiting for a resource that is allocated to another process and that process is waiting for a resource, it is similar to the above-explained example where it is in loop form. Where P1 is waiting for R2 and R2 is allocated for P2 and P2 is waiting for R1 and R1 allocated for P1 which is a circular wait form if this condition satisfies deadlock occurs.

Dead-Lock Detection Algorithm

The cases where we allocate resources to processes, and operating system rechecks if a deadlock has occurred in the system or no using 2 main deadlock detection algorithms, they are

• Single instance
• Multiple instances of resource type

 Single Instance

A single instance is a situation where a system is having single instances of all the resources. It is also known as wait for graph algorithm or resource allocation graph. The resource allocation graph is consisting of a set of processes and set of resources which are represented as two different vertices. The resources in the resource allocation graph are modified and are represented as wait for graph form. Where wait for graph form has only processes which are represented as vertices as shown below wherein,

• Resource allocation graph: Processes P1, P2, P3 and resources R1, R2, R3 are represented in the resource-allocation graph.
• Wait for Graph: Only Processes P1, P2, P3 are mentioned in wait for the graph.
• If there is a cycle condition, that if there is a continuous flow of a process in one direction it means cycle condition exits and wait for the graph is in a deadlock condition.

Example 1: The below example shows there is no deadlock state because there is no continuous flow observed in wait for the graph.

Example 2: Deadlock condition has occurred because there is a continuous flow of cycle from P1 to P4.

If deadlock occurs very frequently in the system then the detection algorithm is used frequently. If there is more usage of the detection algorithm then there will be more overhead and more computation time. Hence to overcome this, we invoke the algorithm after, giving an equal amount of time, this is how the weight for the graph is used to detect deadlock.

Multiple Instances of Resource Type

Multiple instances of the resource type is a situation where a system is having multiple instances of all resources, it is also known as Bankers algorithm. According to the Bankers algorithm, as soon as the process gets all its required resources, then it releases its resources.

Let us consider the following example, assume there are 3 processes P0, P1, P2, and resource type A, B, C where A can be CPU, B can be printer and C can be the keyboard. The digits “0” in the column represent the availability of resources.

Case (i): Suppose if we take the condition request is “000” condition which is present in P0 and P2, we should check which request is fulfilled, the processes P0 release the processes after getting allocated, then next P2 processes releases after getting allocated. Like this, in a sequence, one by one process releases P0, P2, P3, P1, P4 in a sequence. Finally, we get available resources as P7, P2, P6. The available sequence is a condition where there is no deadlock.

Case(ii): Suppose if P2 is 001 instead of 000, now apply the banker’s algorithm to check for deadlock condition, where the only P0 gets executed among all 5 processes. Hence P1, P2, P3, P4 are in deadlock state except for P0.

Applications of Deadlock

The applications of deadlock can be explained with a real-time example of examination online results, where several students try to access their university website on time of release. One can observe that at times the web page does not load at a time to multiple users, this is a deadlock condition. This can be overcome using any one of the algorithms.

Advantages

The advantages of deadlock are

• No pre-emption is observed in deadlock avoidance
• No delay in the process

Disadvantages

The disadvantage of deadlock is

• The resource to be used must be known in advance
• Blockage of the process for a long time
• Pre-emption losses are inherited.

This article overviews about how deadlock occurs when there are two or more processes and the three conditions which is the cause for a deadlock to occur, and the two types of algorithms namely resource sharing algorithm which detects there exists a deadlock condition and bankers’ algorithm which is deadlock avoidance algorithm. Here is the question “What happens if the deadlock is ignored?”.