Steps of Algorithm
Step 1
- Let Work(vector) length = m
- Finish(vector) length = n
-
Initialise Work= Available.
- if Allocationi = 0 ∀ i ∈[0,N-1], then Finish[i] = true;
otherwise, Finish[i]= false.
Step 2
-
Find an index i such that both
- Finish[i] == false
- Work >= Requesti
If there exists no i, go to step 4.
Step 3
- Work += Allocationi
- Finish[i] = true
Go to Step 2.
Step 4
- 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++
#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
********** Deadlock Detection Algorithm ************
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
system is in Deadlock and the Deadlock process are
P0 P1 P2
Complexity Analysis
Time Complexity: The time complexity is O(n*r*r)
Space Complexity: The space complexity isO(n*r)
Must Read Evolution of Operating System and Open Source Operating System.
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.
Advantages of Deadlock Detection Algorithms in Operating System
The advantages of deadlock detection algorithms in operating system are:
-
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.
Disadvantages of Deadlock Detection Algorithms in Operating System
The disadvantages of deadlock detection algorithms in operating system are:
-
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.
Frequently Asked Questions
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!
Good luck with your preparation!
306+ registered