Banker’s Algorithm For this project, you will write a multithreaded program that
ID: 3828548 • Letter: B
Question
Banker’s Algorithm
For this project, you will write a multithreaded program that implements the banker’s algorithm discussed in Section 7.5.3. Several customers request and release resources from the bank. The banker will grant a request only if it leaves the system in a safe state. A request that leaves the system in an unsafe state
will be denied. This programming assignment combines three separate topics:
(1) multithreading, (2) preventing race conditions, and (3) deadlock avoidance.
The Banker
The banker will consider requests from n customers for m resources types. as outlined in Section 7.5.3. The banker will keep track of the resources using the
following data structures:
/* these may be any values >= 0 */
#define NUMBER OF CUSTOMERS 5
#define NUMBER OF RESOURCES 3
/* the available amount of each resource */
int available[NUMBER OF RESOURCES];
/*the maximum demand of each customer */
int maximum[NUMBER OF CUSTOMERS][NUMBER OF RESOURCES];
/* the amount currently allocated to each customer */
int allocation[NUMBER OF CUSTOMERS][NUMBER OF RESOURCES];
/* the remaining need of each customer */
int need[NUMBER OF CUSTOMERS][NUMBER OF RESOURCES];
The Customers
Create n customer threads that request and release resources from the bank. The customers will continually loop, requesting and then releasing random numbers of resources. The customers’ requests for resources will be bounded by their respective values in the need array. The banker will grant a request if it satisfies the safety algorithm outlined in Section 7.5.3.1. If a request does not leave the system in a safe state, the banker will deny it. Function prototypes for requesting and releasing resources are as follows:
int request resources(int customer num, int request[]);
int release resources(int customer num, int release[]);
These two functions should return 0 if successful (the request has been granted) and –1 if unsuccessful. Multiple threads (customers) will concurrently access shared data through these two functions. Therefore, access must be controlled through mutex locks to prevent race conditions. Both the Pthreads and Windows APIs provide mutex locks. The use of Pthreads mutex locks is covered in Section 5.9.4; mutex locks for Windows systems are described in the project entitled“Producer–Consumer Problem”at the end of Chapter 5. Implementation You should invoke your program by passing the number of resources of each type on the command line. For example, if there were three resource types, with ten instances of the first type, five of the second type, and seven of the third type, you would invoke your program follows:
./a.out 10 5 7
The available array would be initialized to these values. You may initialize the maximum array (which holds the maximum demand of each customer) using
any method you find convenient.
Write the program in c language
Explanation / Answer
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
#include <stdio.h>
int current[5][5], maximum_claim[5][5], available[5];
int allocation[5] = {0, 0, 0, 0, 0};
int maxres[5], running[5], safe = 0;
int counter = 0, i, j, exec, resources, processes, k = 1;
int main()
{
printf(" Enter number of processes: ");
scanf("%d", &processes);
for (i = 0; i < processes; i++)
{
running[i] = 1;
counter++;
}
printf(" Enter number of resources: ");
scanf("%d", &resources);
printf(" Enter Claim Vector:");
for (i = 0; i < resources; i++)
{
scanf("%d", &maxres[i]);
}
printf(" Enter Allocated Resource Table: ");
for (i = 0; i < processes; i++)
{
for(j = 0; j < resources; j++)
{
scanf("%d", ¤t[i][j]);
}
}
printf(" Enter Maximum Claim Table: ");
for (i = 0; i < processes; i++)
{
for(j = 0; j < resources; j++)
{
scanf("%d", &maximum_claim[i][j]);
}
}
printf(" The Claim Vector is: ");
for (i = 0; i < resources; i++)
{
printf(" %d", maxres[i]);
}
printf(" The Allocated Resource Table: ");
for (i = 0; i < processes; i++)
{
for (j = 0; j < resources; j++)
{
printf(" %d", current[i][j]);
}
printf(" ");
}
printf(" The Maximum Claim Table: ");
for (i = 0; i < processes; i++)
{
for (j = 0; j < resources; j++)
{
printf(" %d", maximum_claim[i][j]);
}
printf(" ");
}
for (i = 0; i < processes; i++)
{
for (j = 0; j < resources; j++)
{
allocation[j] += current[i][j];
}
}
printf(" Allocated resources:");
for (i = 0; i < resources; i++)
{
printf(" %d", allocation[i]);
}
for (i = 0; i < resources; i++)
{
available[i] = maxres[i] - allocation[i];
}
printf(" Available resources:");
for (i = 0; i < resources; i++)
{
printf(" %d", available[i]);
}
printf(" ");
while (counter != 0)
{
safe = 0;
for (i = 0; i < processes; i++)
{
if (running[i])
{
exec = 1;
for (j = 0; j < resources; j++)
{
if (maximum_claim[i][j] - current[i][j] > available[j])
{
exec = 0;
break;
}
}
if (exec)
{
printf(" Process%d is executing ", i + 1);
running[i] = 0;
counter--;
safe = 1;
for (j = 0; j < resources; j++)
{
available[j] += current[i][j];
}
break;
}
}
}
if (!safe)
{
printf(" The processes are in unsafe state. ");
break;
}
else
{
printf(" The process is in safe state");
printf(" Available vector:");
for (i = 0; i < resources; i++)
{
printf(" %d", available[i]);
}
printf(" ");
}
}
return 0;
}
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
#include <stdio.h>
int current[5][5], maximum_claim[5][5], available[5];
int allocation[5] = {0, 0, 0, 0, 0};
int maxres[5], running[5], safe = 0;
int counter = 0, i, j, exec, resources, processes, k = 1;
int main()
{
printf(" Enter number of processes: ");
scanf("%d", &processes);
for (i = 0; i < processes; i++)
{
running[i] = 1;
counter++;
}
printf(" Enter number of resources: ");
scanf("%d", &resources);
printf(" Enter Claim Vector:");
for (i = 0; i < resources; i++)
{
scanf("%d", &maxres[i]);
}
printf(" Enter Allocated Resource Table: ");
for (i = 0; i < processes; i++)
{
for(j = 0; j < resources; j++)
{
scanf("%d", ¤t[i][j]);
}
}
printf(" Enter Maximum Claim Table: ");
for (i = 0; i < processes; i++)
{
for(j = 0; j < resources; j++)
{
scanf("%d", &maximum_claim[i][j]);
}
}
printf(" The Claim Vector is: ");
for (i = 0; i < resources; i++)
{
printf(" %d", maxres[i]);
}
printf(" The Allocated Resource Table: ");
for (i = 0; i < processes; i++)
{
for (j = 0; j < resources; j++)
{
printf(" %d", current[i][j]);
}
printf(" ");
}
printf(" The Maximum Claim Table: ");
for (i = 0; i < processes; i++)
{
for (j = 0; j < resources; j++)
{
printf(" %d", maximum_claim[i][j]);
}
printf(" ");
}
for (i = 0; i < processes; i++)
{
for (j = 0; j < resources; j++)
{
allocation[j] += current[i][j];
}
}
printf(" Allocated resources:");
for (i = 0; i < resources; i++)
{
printf(" %d", allocation[i]);
}
for (i = 0; i < resources; i++)
{
available[i] = maxres[i] - allocation[i];
}
printf(" Available resources:");
for (i = 0; i < resources; i++)
{
printf(" %d", available[i]);
}
printf(" ");
while (counter != 0)
{
safe = 0;
for (i = 0; i < processes; i++)
{
if (running[i])
{
exec = 1;
for (j = 0; j < resources; j++)
{
if (maximum_claim[i][j] - current[i][j] > available[j])
{
exec = 0;
break;
}
}
if (exec)
{
printf(" Process%d is executing ", i + 1);
running[i] = 0;
counter--;
safe = 1;
for (j = 0; j < resources; j++)
{
available[j] += current[i][j];
}
break;
}
}
}
if (!safe)
{
printf(" The processes are in unsafe state. ");
break;
}
else
{
printf(" The process is in safe state");
printf(" Available vector:");
for (i = 0; i < resources; i++)
{
printf(" %d", available[i]);
}
printf(" ");
}
}
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.