1.
Introduction
1.1.
When Does a Deadlock Detection Algorithm Occur?
2.
2.1.
Available
2.2.
Allocation
2.3.
Request
3.
Steps of Algorithm
3.1.
Step 1
3.2.
Step 2
3.3.
Step 3
3.4.
Step 4
4.
C++ Program to Implement Deadlock Detection
4.1.
C++
4.2.
Complexity Analysis
5.
Several algorithms for detecting deadlocks in an operating systems
5.1.
Wait-For Graph
5.2.
Banker’s Algorithm
5.3.
Detection by System Modeling
5.4.
Resource Allocation Graph
5.5.
Timestamping
6.
7.
8.
8.1.
What is a Deadlock Detection Algorithm?
8.2.
8.3.
Which algorithm is used for deadlock detection?
8.4.
8.5.
What is the algorithm to prevent deadlock?
9.
Conclusion
Last Updated: Mar 27, 2024
Easy

# Deadlock Detection Algorithm in Operating System

0 upvote

## Introduction

In an operating system, a deadlock occurs when a process or thread enters a waiting state because a requested system resource is being held by another waiting process, which is, in turn, waiting for another waiting process.

A deadlock situation may occur if a system does not employ either a deadlock prevention or avoidance algorithm. In this case-

• Use an algorithm to examine the system's state and determine whether or not a deadlock has occurred.
• Apply an algorithm to get out of the deadlock.

### When Does a Deadlock Detection Algorithm Occur?

Four conditions need to be occurred simultaneously for a deadlock to occur.

• Mutual exclusion
• Hold and wait
• No preemption
• Circular wait

For more details regarding the conditions of a deadlock, you must visit the Guided Path on Coding Ninjas Studio.

We shall now proceed with the Deadlock Avoidance Algorithm to avoid the deadlock situation.

The algorithm makes use of numerous data structures that change over time:

### Available

A vector of length m represents the number of accessible resources of each category.

### Allocation

An n*m matrix indicates the number of resources of each kind currently assigned to a process. The column represents the resource, while the rows represent the process.

### Request

A n*m matrix represents each process's current request. Process Pi is requesting k additional instances of resource type Rj if request[i][j] = k.

The Banker's Algorithm is a deadlock avoidance and resource allocation algorithm.

It determines if allocating a resource will cause a deadlock or whether allocating a resource to a process is safe, and if not, the resource is not assigned to that process.

Determining a safe sequence (even if it is only one) ensures that the system does not enter a state of deadlock.

The Deadlock Detection Algorithm/Safety Algorithm is included in the Bankers' algorithm.

The following is the algorithm for determining if a system is in a safe state:

## Steps of Algorithm

### Step 1

1. Let Work(vector) length = m
2. Finish(vector) length = n
3. Initialise Work= Available.
1. if Allocationi = 0 ∀ i ∈[0,N-1], then Finish[i] = true;

otherwise, Finish[i]= false.

### Step 2

1. Find an index i such that both
1. Finish[i] == false
2. Work >= Requesti

If there exists no i, go to step 4.

### Step 3

1. Work += Allocationi
2. Finish[i] = true

Go to Step 2.

### Step 4

1. For some i in [0,N), if Finish[i]==false, then the system is considered in a deadlock state. Moreover, if Finish[i]==false the process Pi is deadlocked.

## C++ Program to Implement Deadlock Detection

• C++

### C++

``#include <bits/stdc++.h>using namespace std;int arrmax[100][100];int alloc[100][100];int need[100][100];int avail[100];int n, r;void input(){    int i, j;    cout << "Enter the no of Processes\t";    cin >> n;    cout << "Enter the no of resource instances\t";    cin >> r;    cout << "Enter the Max Matrix\n";    for (i = 0; i < n; i++)    {        for (j = 0; j < r; j++)        {            cin >> arrmax[i][j];        }    }    cout << "Enter the Allocation Matrix\n";    for (i = 0; i < n; i++)    {        for (j = 0; j < r; j++)        {            cin >> alloc[i][j];        }    }    cout << "Enter the available Resources\n";    for (j = 0; j < r; j++)    {        cin >> avail[j];    }}void show(){    int i, j;    cout << "Process\t Allocation\t Max\t Available\t";    for (i = 0; i < n; i++)    {        cout << "\nP" << i + 1 << "\t ";        for (j = 0; j < r; j++)        {            cout << alloc[i][j] << " ";        }        cout << "\t\t";        for (j = 0; j < r; j++)        {            cout << arrmax[i][j] << " ";        }        cout << "\t ";        if (i == 0)        {            for (j = 0; j < r; j++)                cout << avail[j] << " ";        }    }}void cal(){    int finish[100], temp, need[100][100], flag = 1, k, c1 = 0;    int dead[100];    int safe[100];    int i, j;    for (i = 0; i < n; i++)    {        finish[i] = 0;    }    //find need matrix    for (i = 0; i < n; i++)    {        for (j = 0; j < r; j++)        {            need[i][j] = arrmax[i][j] - alloc[i][j];        }    }    while (flag)    {        flag = 0;        for (i = 0; i < n; i++)        {            int c = 0;            for (j = 0; j < r; j++)            {                if ((finish[i] == 0) && (need[i][j] <= avail[j]))                {                    c++;                    if (c == r)                    {                        for (k = 0; k < r; k++)                        {                            avail[k] += alloc[i][j];                            finish[i] = 1;                            flag = 1;                        }                        //cout<<"\nP%d",i;                        if (finish[i] == 1)                        {                            i = n;                        }                    }                }            }        }    }    j = 0;    flag = 0;    for (i = 0; i < n; i++)    {        if (finish[i] == 0)        {            dead[j] = i;            j++;            flag = 1;        }    }    if (flag == 1)    {        cout << "\n\nSystem is in Deadlock and the Deadlock process are\n";        for (i = 0; i < n; i++)        {            cout << "P" << dead[i] << "\t";        }    }    else    {        cout << "\nNo Deadlock Occur";    }}int main(){    int i, j;    cout << "********** Deadlock Detection Algorithm ************\n";    input();    show();    cal();    return 0;}``

OUTPUT

``````
Enter the no of Processes       3
Enter the no of resource instances      3
Enter the Max Matrix
3 6 8
4 3 3
3 4 4
Enter the Allocation Matrix
3 3 3
2 0 3
1 2 4
Enter the available Resources
1 2 0
Process  Allocation      Max     Available
P1           3 3 3        3 6 8     1 2 0
P2           2 0 3        4 3 3
P3           1 2 4        3 4 4

P0      P1      P2``````

### Complexity Analysis

Time Complexity: The time complexity is O(n*r*r)

Space Complexity: The space complexity isO(n*r)

## Several algorithms for detecting deadlocks in an operating systems

### Wait-For Graph

The Wait-For Graph is a deadlock detection algorithm used in operating systems. It represents processes and resources as nodes in a directed graph, where edges denote processes waiting for resources. By analyzing the graph for cycles, the algorithm can identify potential deadlocks. However, it may produce false positives as it doesn't consider resource preemption, and cycles may not always lead to deadlocks.

### Banker’s Algorithm

Banker's Algorithm is a deadlock detection and avoidance method. It ensures a safe state by checking resource requests before allocation. Processes declare their maximum needs, and the algorithm simulates resource allocation to determine if the system remains in a safe state. However, it assumes accurate declaration of maximum needs by processes and may be restrictive in certain scenarios.

### Detection by System Modeling

Detection by System Modeling involves modeling the system state, resources, and processes. It analyzes the system's behavior to identify potential deadlocks. This method utilizes system state models to detect conditions leading to deadlocks. While effective, it demands precise modeling of system interactions, which may be challenging in complex systems.

### Resource Allocation Graph

The Resource Allocation Graph is a deadlock detection technique representing processes and resources as nodes in a graph. Edges indicate resource requests, and detecting cycles in the graph implies potential deadlocks. However, it may not handle resource preemption well, and false positives are possible. The graph is dynamic and changes as processes request and release resources.

### Timestamping

Timestamping is a deadlock detection approach that assigns unique timestamps to resource requests and releases. Processes use these timestamps to order their requests and releases. If a process cannot acquire resources due to conflicts, a deadlock is detected. However, this method relies on accurate clock synchronization, and managing timestamps adds complexity to the system.

• Dynamic Handling: Deadlock detection algorithms operate dynamically during runtime, identifying and resolving deadlocks as they occur, ensuring adaptability to changing system conditions.
• No A Priori Information: These algorithms don't require a priori information about the processes and resources, making them suitable for systems with dynamic and unpredictable resource usage patterns.
• No Restriction on Resource Allocation: Unlike deadlock prevention methods that impose restrictions on resource allocation, detection algorithms allow flexible resource allocation, optimizing system performance.
• Suitable for Complex Systems: Deadlock detection is suitable for complex systems where accurately predicting potential deadlocks in advance is challenging. It accommodates diverse resource allocation scenarios.
• No Starvation: Deadlock detection ensures that processes are not starved of resources indefinitely. Once a deadlock is detected, appropriate measures can be taken to break the deadlock and release resources.

• Resource Overhead: Deadlock detection introduces additional computational overhead, requiring periodic checks and analysis of the system state, which may impact overall system performance.
• Reactive Nature: These algorithms are reactive, addressing deadlocks after they occur. This reactive nature may lead to delays in deadlock resolution, affecting the responsiveness of the system.
• False Positives: Deadlock detection algorithms may produce false positives, identifying situations as deadlocks that are not actual deadlocks. This can result in unnecessary interventions and resource reallocations.
• Complexity: Implementing deadlock detection algorithms can be complex, especially in large-scale systems. The need for accurate modeling and frequent system checks adds to the overall complexity of the system.
• Limited Prevention: While detection resolves deadlocks after they occur, it doesn't prevent them. It may lead to situations where processes are briefly blocked, impacting the system's ability to maintain continuous operation.

### What is a Deadlock Detection Algorithm?

A deadlock detection algorithm checks the allocation of resources to various processes and determines whether or not the system is in a deadlock. If it is in a deadlock, a separate algorithm can help eliminate the deadlock and save the system.

### What is deadlock detection mechanism?

Deadlock detection is a system mechanism that periodically scans a resource allocation graph for cycles, indicating potential deadlocks. Once detected, the system identifies the involved processes and resources, then takes corrective actions such as preempting resources or terminating processes to resolve the deadlock.

### Which algorithm is used for deadlock detection?

Banker's algorithm is generally used to detect deadlocks in the system. It is a resource allocation and deadlock avoidance algorithm that simulates the resource allocation and determines whether or not the system will be in a safe state after this allocation. If not, it will lead to a deadlock.

### How could deadlocks be detected?

The easiest way to detect deadlock is to check the resource allocation graph. The operating system usually checks the resource allocation graph. If it finds a cycle in the graph, we can conclude that a deadlock has occurred in the system.

### What is the algorithm to prevent deadlock?

Deadlock prevention involves eliminating at least one of the necessary conditions for deadlocks, such as mutual exclusion, hold and wait, no preemption, or circular wait. Strategies include optimistic resource allocation, Banker's Algorithm, lock usage, timeouts, and preemptive scheduling.

## Conclusion

• Cheers if you reached here! In this blog, we learned about the Deadlock Detection Algorithm.
• We have covered the basic idea of a deadlock.
• We have also seen when it occurs.
• Further, we saw the Deadlock Avoidance Algorithm(Banker’s Algorithm).
• We have also seen the Algorithm to determine whether or not a system is in a safe state(Deadlock Detection Algorithm).

So its time for you now to refer to other articles based on a similar topic, i.e., deadlock in operating system-

On the other hand, learning never ceases, and there is always more to learn. So, keep learning and keep growing, ninjas!

With this fantastic course, test series, and problems available on Coding Ninjas Studio, you can make learning enjoyable and stress-free. Are you planning to ace the interviews of reputed product-based companies like Amazon, Microsoft, Google, and more? Attempt our mock test series and participate in the contests hosted on Coding Ninjas Studio now!