Deadlock is a situation in a distributed or multi-process system where a set of processes are permanently blocked, each waiting for a resource that another process in the set holds. Detecting which processes are causing a deadlock is a critical operating system responsibility.
This C program implements a deadlock detection algorithm using a resource allocation graph. It uses a claim matrix (maximum resource needs), an allocation matrix (currently held resources), and availability vectors to identify processes that are involved in a deadlock.
C Program: Deadlock Detection via Resource Allocation
#include <stdio.h>
int main() {
int found, flag, resourceIdx;
// p[i][j] = allocation matrix: resources of type j held by process i
// c[i][j] = claim matrix: maximum resources of type j that process i can request
int alloc[5][10], claim[5][10];
int totalProcesses; // number of processes
int safeSeq[10]; // safe sequence (non-deadlocked processes)
int safeCount = 1; // count of processes in safe sequence
int resourceVector[10]; // total number of each resource type
int availVector[10]; // currently available resources
int tempAvail[10]; // working copy of available vector
int resourceTypes = 5; // number of resource types
int sum = 0;
printf("Enter total number of processes:\n");
scanf("%d", &totalProcesses);
// Read claim matrix (maximum resource needs per process)
printf("Enter claim matrix:\n");
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= resourceTypes; j++)
scanf("%d", &claim[i][j]);
// Read allocation matrix (resources currently held per process)
printf("Enter allocation matrix:\n");
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= resourceTypes; j++)
scanf("%d", &alloc[i][j]);
// Read the total resource vector
printf("Enter resource vector:\n");
for (int i = 1; i <= resourceTypes; i++)
scanf("%d", &resourceVector[i]);
// Read the availability vector and initialise working copy
printf("Enter availability vector:\n");
for (int i = 1; i <= resourceTypes; i++) {
scanf("%d", &availVector[i]);
tempAvail[i] = availVector[i];
}
// Step 1: Identify processes with zero allocation (they are not holding any resources)
for (int i = 1; i <= 4; i++) {
sum = 0;
for (int j = 1; j <= resourceTypes; j++)
sum += alloc[i][j];
if (sum == 0) {
// This process is not holding any resources — add to safe sequence
safeSeq[safeCount] = i;
safeCount++;
}
}
// Step 2: Try to find more processes that can complete given current availability
for (int i = 1; i <= 4; i++) {
for (int l = 1; l < safeCount; l++) {
if (i != safeSeq[l]) {
flag = 1;
// Check if all claims of process i can be satisfied with tempAvail
for (int j = 1; j <= resourceTypes; j++) {
if (claim[i][j] > tempAvail[j]) {
flag = 0;
break;
}
}
}
}
if (flag == 1) {
// Process i can complete — add to safe sequence and release its resources
safeSeq[safeCount] = i;
safeCount++;
for (int j = 1; j <= resourceTypes; j++)
tempAvail[j] += alloc[i][j];
}
}
// Step 3: Processes NOT in the safe sequence are deadlocked
printf("Deadlock-causing processes are: ");
for (int j = 1; j <= totalProcesses; j++) {
found = 0;
for (int i = 1; i < safeCount; i++) {
if (j == safeSeq[i])
found = 1;
}
if (found == 0)
printf("%dt", j); // print deadlocked process number
}
return 0;
}
How the Code Works
- Input: The program reads the number of processes, a claim matrix (maximum resource needs), an allocation matrix (resources currently held), the total resource vector, and the current availability vector.
- Zero-Allocation Pass: Processes holding no resources (all-zero rows in the allocation matrix) are immediately added to the safe sequence, since they cannot be causing a deadlock.
- Resource-Release Simulation: The algorithm iterates over the remaining processes. If a process’s entire claim can be satisfied from the currently available pool (
tempAvail), it is deemed safe. It is added to the safe sequence and its allocated resources are returned totempAvail. - Deadlock Identification: Any process not found in the safe sequence at the end is part of the deadlock — it is waiting for resources that can never be released.
Sample Input / Output
Enter total number of processes:
4
Enter claim matrix:
0
1
0
0
1
0
0
1
0
1
0
0
0
0
1
1
0
1
0
1
Enter allocation matrix:
1
0
1
1
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
Enter resource vector:
2
1
1
2
1
Enter availability vector:
0
0
0
0
1
Deadlock-causing processes are: 1 2Output Explanation
- Process 4 has a zero allocation row, so it is immediately safe.
- With the minimal availability (only 1 unit of resource type 5), no other process can have its full claim satisfied.
- Processes 1 and 2 are holding resources but cannot proceed — they are deadlocked.
- Process 3 also cannot proceed in this scenario, but its exact membership in the deadlock set depends on the iterative check order.
See Also
- Demonstrating Bully Algorithm in Java — leader election in distributed computing
Conclusion
Deadlock detection is a fundamental challenge in operating systems and distributed computing. This program demonstrates the core idea: simulate resource release for processes that can complete, build a safe sequence, and flag any process left outside that sequence as a deadlock participant. Mastering this algorithm builds a strong foundation for understanding Banker’s Algorithm and other resource management strategies.
Please see my answer to this question . Bottom line whenever two threads need to acquire two different resources, and do so in different orders then you can get deadlocks.