Repository navigation
Expand file tree
/
Copy pathdeadlock.cpp
More file actions
149 lines (129 loc) · 4.64 KB
/
Copy pathdeadlock.cpp
File metadata and controls
149 lines (129 loc) · 4.64 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
/*
* deadlock.cpp
* ------------
* Detects deadlock using a simplified Resource Allocation Graph (RAG).
*
* HOW IT WORKS:
* - Each process and resource is a node in the graph.
* - A "request edge" goes from a Process → Resource (process waiting for resource).
* - An "assignment edge" goes from Resource → Process (resource held by process).
* - If we find a CYCLE in this graph, a DEADLOCK exists.
*
* This file builds the RAG and then uses DFS to detect any cycle.
*
* INPUTS (via stdin):
* Line 1: n (processes), m (resources)
* Next n lines: Allocation matrix (which resources each process holds)
* Next n lines: Request matrix (which resources each process is waiting for)
*
* OUTPUT:
* Deadlock status and list of deadlocked processes (if any)
*/
#include <iostream>
#include <vector>
#include <string>
using namespace std;
/*
* Node numbering scheme:
* Processes: nodes 0 to n-1
* Resources: nodes n to n+m-1
*
* This lets us put both in one graph for the RAG.
*/
int totalNodes;
vector<vector<int>> adj;
// DFS to detect cycle
bool dfs(int node, vector<bool>& visited, vector<bool>& recStack) {
visited[node] = true;
recStack[node] = true;
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
if (dfs(neighbor, visited, recStack))
return true;
} else if (recStack[neighbor]) {
return true; // cycle found
}
}
recStack[node] = false;
return false;
}
int main() {
int n, m;
cin >> n >> m;
// Allocation[i][j] = 1 means process i holds resource j
vector<vector<int>> allocation(n, vector<int>(m));
// Request[i][j] = 1 means process i is waiting for resource j
vector<vector<int>> request(n, vector<int>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> allocation[i][j];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> request[i][j];
// Total nodes = n processes + m resources
totalNodes = n + m;
adj.resize(totalNodes);
cout << "STEP: Building Resource Allocation Graph (RAG)..." << endl;
cout << " Processes: P0 to P" << n-1 << " (nodes 0 to " << n-1 << ")" << endl;
cout << " Resources: R0 to R" << m-1 << " (nodes " << n << " to " << n+m-1 << ")" << endl << endl;
// Build assignment edges: Resource j -> Process i (resource held by process)
cout << "STEP: Adding Assignment Edges (Resource -> Process):" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (allocation[i][j] == 1) {
int resourceNode = n + j; // resource j's node index
adj[resourceNode].push_back(i); // R_j -> P_i
cout << " R" << j << " -> P" << i << endl;
}
}
}
cout << endl;
// Build request edges: Process i -> Resource j (process waiting for resource)
cout << "STEP: Adding Request Edges (Process -> Resource):" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (request[i][j] == 1) {
int resourceNode = n + j; // resource j's node index
adj[i].push_back(resourceNode); // P_i -> R_j
cout << " P" << i << " -> R" << j << endl;
}
}
}
cout << endl;
// Run cycle detection on the RAG
cout << "STEP: Running DFS to detect cycle in RAG..." << endl;
vector<bool> visited(totalNodes, false);
vector<bool> recStack(totalNodes, false);
vector<int> deadlockedProcesses;
bool deadlockFound = false;
for (int i = 0; i < totalNodes; i++) {
if (!visited[i]) {
if (dfs(i, visited, recStack)) {
deadlockFound = true;
}
}
}
// Identify which processes are deadlocked
// (those that are waiting AND their requests cannot be satisfied)
if (deadlockFound) {
cout << endl << "RESULT: DEADLOCK_DETECTED" << endl;
cout << "A cycle was found in the Resource Allocation Graph." << endl;
// Find processes that are waiting for at least one resource
cout << "Processes involved in deadlock: ";
for (int i = 0; i < n; i++) {
bool waiting = false;
for (int j = 0; j < m; j++) {
if (request[i][j] == 1) { waiting = true; break; }
}
if (waiting) {
cout << "P" << i << " ";
deadlockedProcesses.push_back(i);
}
}
cout << endl;
} else {
cout << endl << "RESULT: NO_DEADLOCK" << endl;
cout << "No cycle in RAG — system is safe from deadlock." << endl;
}
return 0;
}