forked from HarshCasper/NeoAlgo
-
Notifications
You must be signed in to change notification settings - Fork 0
/
bankers.c
157 lines (131 loc) · 4.44 KB
/
bankers.c
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
150
151
152
153
154
155
156
157
/* Some information about Banker's algorithm :-
* The Banker’s algorithm is a resource allocation and deadlock avoidance algorithm developed by Edsger Dijkstra.
* The time complexity of the Banker's algorithm as a function of the number n of processes and m of resources is o(n*n*m).
*
Let Pbe number of process and R be number of resources.
* BOOLEAN function SAFESTATE is -- Determines if current state is safe
{ UNSAFE : boolean;
AVAILABLE : array[1..R] of INTEGER
FINISH : array[1..P] of boolean = [false, ..,false];
I : integer;
repeat
UNSAFE = TRUE;
for I = 1 to P do
if ((not FINISH[i]) and
NEEDi <= WORK) then {
WORK = WORK + ALLOCATION_i;
FINISH[i] = true;
UNSAFE = false;
}
until NOCHANGE;
return (FINISH == (true, .., true));
}
*/
#include <stdio.h>
// Calculating the remaining need of the resources for each process.
void CalculateRemainingNeed(int process, int resource, int need[process][resource], int allocated[process][resource], int max[process][resource]){
int i,j;
for(i = 0; i < process; ++i){
for(j = 0; j < resource; ++j){
need[i][j] = max[i][j] - allocated[i][j];
}
}
}
// Checking whether all the processrocess can be executed.
int CheckDeadlock(int process, int resource, int need[process][resource], int avail[], int allocated[process][resource], int finish[], int seq[]){
int count = 0, i, j, k, unsafe = 1;
while (count != process){
unsafe = 1;
for(i = 0; i < process; ++i){
// Checking whether particular process is executed or not.
if (finish[i] == 0){
for(j = 0; j < resource; ++j){
// Checking whether the need of any process is greater than availability.
if (need[i][j] > avail[j]){
break;
}
}
// If all the resources are available for any process.
if (j == resource){
for (k = 0; k < resource; ++k)
avail[k] = avail[k] + allocated[i][k];
finish[i] = 1;
seq[count] = i+1;
count++;
unsafe = 0;
}
}
}
if (unsafe == 1)
return unsafe;
}
}
void DisplaySafeSequence(int seq[], int process){
int i;
printf("The safe sequence is:\n");
for(i = 0; i < process - 1; ++i)
printf("P%d->", seq[i]);
printf("P%d\n", seq[process-1]);
}
int main() {
int process, resource, i, j;
printf("Enter number of process\n");
scanf("%d", &process);
printf("Enter the number of resources\n");
scanf("%d", &resource);
int allocated[process][resource], max[process][resource], avail[resource], need[process][resource], finish[process], seq[process];
printf("Enter the available resources\n");
for(i = 0; i < resource; ++i){
scanf("%d", &avail[i]);
}
printf("Enter the allocated resources to each process\n");
for(i = 0; i < process; ++i){
for(int j = 0; j < resource; ++j){
scanf("%d", &allocated[i][j]);
}
}
printf("Enter the maximum demand of resources by each process\n");
for(i = 0; i < process; ++i){
for(j = 0; j < resource; ++j){
scanf("%d", &max[i][j]);
}
}
/*
Finish matrix is used to keep track of the executed process.
Initializing with value '0' which means no process is executed yet.
*/
for(i = 0; i < process; ++i){
finish[i] = 0;
}
CalculateRemainingNeed(process, resource, need, allocated, max);
int unsafe = CheckDeadlock(process, resource, need, avail, allocated, finish, seq);
// Checking if there is any process which will not able to execute.
if (unsafe == 1)
printf("The sequence is unsafe. Deadlock will occur.\n");
else
DisplaySafeSequence(seq, process);
return 0;
}
/*
OUTPUT
Enter number of process
5
Enter the number of resources
3
Enter the available resources
2 1 0
Enter the allocated resources to each process
1 1 2
2 1 2
4 0 1
0 2 0
1 1 2
Enter the maximum demand of resources by each process
4 3 3
3 2 2
9 0 2
7 5 3
1 1 2
The safe sequence is:
P2->P5->P1->P3->P4
*/