What is a Deadlock Detection Algorithm in an Operating System?

Deadlock is a situation everyone wants to avoid!

Whether it is your real-life or computer systems, no one wants to get stuck in a deadlock. Deadlock is simply a situation where you can not do anything further and at the same time, you will not be able to undo your actions. 

When it comes to operating systems, a deadlock occurs when two systems are using the same resources and interrupting each other’s workflow. For example, if one process is using a printer and the other process is using a scanner. Now, if the third process requires both printer and scanner, it will not be executed until the other two are done. So, the third process will be in a deadlock state.

If a system fails to implement a deadlock prevention or avoidance algorithm, there is a high chance that the system will encounter a deadlock. 

In this case, either an algorithm is implemented to check if the system has encountered a deadlock or not using a deadlock detection algorithm or you can simply implement an algorithm to recover from the deadlock.

Well, here, we are considering the first case and will discuss in detail the deadlock detection algorithm.

An Introduction To Deadlock Detection Algorithm

To detect and avoid deadlock in an operating system, Banker’s algorithm is used. This algorithm allocates all the resources to every system safely and ensures that there is no condition of deadlock.

The S-state in the algorithm checks all the possible tests before allocating any resource to the running process. It simplifies the process in which the operating system shares its resources between the processes running on the system.

Are you wondering why the algorithm is called Banker’s algorithm and simply not a deadlock avoidance algorithm?

The name has been given because the process has similarities with how bank grants loan to people. Before sanctioning the loan to anyone, the system analyses the background and available resources to decide if the loan should be sanctioned or not. This streamlines the whole process of the bank and allows the bank to allocate its resources wisely.

Banker’s algorithm works in the same way and hence the name.

How Does Deadlock Detection Algorithm Work?

Let’s understand the working of the deadlock detection algorithm with a real-life example:

Let’s suppose that there are “n” number of account holders in a bank and the total amount of money present in the bank is “T”. Now, if any account holder has applied for a loan from the bank. 

What is the first thing that the bank will do?

The bank will simply subtract the loan amount from the total amount available with the bank. Now, the bank will calculate the loan difference. A bank will only approve the loan if the cash difference between the amounts is larger than the total amount.

Why the bank goes through so many calculations when there are funds available?

The idea is simple. The bank will have to provide resources to its other users also. These calculations are done so that if any other account holder also applies for any loan amount or simply withdraws some money from the bank, the bank must be able to provide the required amount to the user.

This makes it easy for the bank to operate and merge all the data together and make efficient decisions.

The same thing is followed in the operating system. Whenever a process is generated, the operating system should have all the necessary information related to it including the resources required and upcoming processes. 

On the basis of this data, the OS will decide which process should be executed first and which one should be kept on the waiting list. This helps the operating system to avoid deadlock in the system.

Therefore, the banker’s algorithm is called the deadlock detection algorithm and the deadlock avoidance algorithm. 

If you are wondering whether these are two different types of algorithms, always keep in mind that the banker’s algorithm is used as both a detection and avoidance algorithm.

However, while writing the code, there is a complete format that you have to follow. Here are all the steps that you have to follow while writing code for the banker’s algorithm.

• To begin with, consider two vectors, Finish and work of length n and m respectively.

• Now, initialize work as available. Run the for loop i=0, 1, 2,... n-1. In case Requesti= 0, finish[i]= True. otherwise, finish[i]= false.

• You will now have to find an “i” in a way, request<=work and Finish== false. In case there is no such “i” present, proceed to step 4.

• If work = work + allocate, and finish = TRUE, hover to step 2.

• However, in case finish== false of any “i” it means that there is a deadlock. 

Advantages Of Deadlock Detection Algorithm

There are multiple characteristics of the banker’s algorithm because of which the algorithm is preferred for detecting deadlock in the system. Here is a list of all the advantages of using the banker’s algorithm.

• There are multiple resources available to meet the requirements of all the processes.

• All the processes must provide the desired information like the required number of resources, upcoming requests for resources, and the time for which each resource is required.

• The algorithm enables the operating system to manage and control all the resources and processes efficiently.

• There is also a max resource attribute available in this algorithm that indicates how many maximum resources can be acquired by a particular process.

Disadvantages Of Deadlock Detection Algorithm

Though the banker’s algorithm is an efficient way to handle all the processes and resources of a system, it also possesses some limitations on it. Here are some reasons why a banker’s algorithm may not be preferred.

• A fixed number of processes are required in the algorithm. So, if you wish to add a process, you will have to do it after all the processes are done.

• Every process should have all the information in advance.

• All the resources are allocated for a limited time only.

Conclusion

Deadlock detection is very important to avoid the deadlock state and use all the resources properly and efficiently. Only the banker’s algorithm is used as a deadlock detection algorithm as well as a deadlock avoidance algorithm.

So, if you are confused between the two, remember that both of them are the same!