Lab Session # 8 Banker’s Algorithm in Operating System

Following Data structures are used to implement the Banker’s Algorithm:
Let ‘n’ be the number of processes in the system and ‘m’ be the number of resources
types.
Available :
 It is a 1-d array of size ‘m’ indicating the number of available resources of each
type.
 Available[ j ] = k means there are ‘k’ instances of resource type Rj
Max :
 It is a 2-d array of size ‘n*m’ that defines the maximum demand of each process in a
system.
 Max[ i, j ] = k means process Pi may request at most ‘k’ instances of resource type
Rj.
Allocation :
 It is a 2-d array of size ‘n*m’ that defines the number of resources of each type
currently
allocated to each process.
 Allocation[ i, j ] = k means process Pi is currently allocated ‘k’ instances of resource
type Rj
Need :
 It is a 2-d array of size ‘n*m’ that indicates the remaining resource need of each
process.
 Need [ i, j ] = k means process Pi currently need ‘k’ instances of resource type Rj
for its execution.
 Need [ i, j ] = Max [ i, j ] – Allocation [ i, j ]
Allocationi specifies the resources currently allocated to process Pi and Needi specifies
the additional
resources that process Pi may still request to complete its task.
Banker’s algorithm consists of Safety algorithm and Resource request algorithm
Code for Banker’s Algorithm
// Banker's Algorithm
#include <iostream>
using namespace std;
31
int main()
{
// P0, P1, P2, P3, P4 are the Process names here
int n, m, i, j, k;
n = 5; // Number of processes
m = 3; // Number of resources
int alloc[5][3] = { { 0, 1, 0 }, // P0 // Allocation
Matrix
{ 2, 0, 0 }, // P1
{ 3, 0, 2 }, // P2
{ 2, 1, 1 }, // P3
{ 0, 0, 2 } }; // P4
int max[5][3] = { { 7, 5, 3 }, // P0 // MAX Matrix
{ 3, 2, 2 }, // P1
{ 9, 0, 2 }, // P2
{ 2, 2, 2 }, // P3
{ 4, 3, 3 } }; // P4
int avail[3] = { 3, 3, 2 }; // Available Resources
int f[n], ans[n], ind = 0;
for (k = 0; k < n; k++) {
f[k] = 0;
}
int need[n][m];
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++)
need[i][j] = max[i][j] - alloc[i][j];
}
int y = 0;
for (k = 0; k < 5; k++) {
for (i = 0; i < n; i++) {
if (f[i] == 0) {
int flag = 0;
for (j = 0; j < m; j++) {
if (need[i][j] > avail[j]){
flag = 1;
break;
}
}
if (flag == 0) {
ans[ind++] = i;
32
for (y = 0; y < m; y++)
avail[y] += alloc[i][y];
f[i] = 1;
}
}
}
}
cout << "Following is the SAFE Sequence" << endl;
for (i = 0; i < n - 1; i++)
cout << " P" << ans[i] << " ->";
cout << " P" << ans[n - 1] <<endl;
return (0);
}
Exercise
i)Implement the deadlock detection algorithm for n no of processes after reading
maximum, allocated resources and remaining needs.