Banker's Algorithm - OS Lab
Question 1
Write a C program to implement the Banker's algorithm and display the safe state sequence.
Aim
To write a C program to implement the Banker's Algorithm and display the Safe State
Sequence.
Algorithm
1. Input the number of processes and resources.
2. Input Allocation, Max, and Available matrices.
3. Calculate the Need matrix using Need[i][j] = Max[i][j] - Allocation[i][j].
4. Initialize Work = Available and Finish[i] = false for all i.
5. Find an i such that Finish[i] == false and Need[i] <= Work.
6. If such i is found:
a. Work = Work + Allocation[i]
b. Finish[i] = true
c. Add i to Safe Sequence
7. Repeat step 5 until all processes are finished or no such process is found.
8. If all processes are finished, the system is in a safe state and Safe Sequence is printed.
Otherwise, it is in an unsafe state.
C Code
#include <stdio.h>
int main() {
int n, m, i, j, k;
printf("Enter number of processes: ");
scanf("%d", &n);
printf("Enter number of resources: ");
scanf("%d", &m);
int alloc[n][m], max[n][m], avail[m];
printf("Enter Allocation Matrix:
");
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d", &alloc[i][j]);
printf("Enter Max Matrix:
");
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d", &max[i][j]);
printf("Enter Available Resources:
");
for(i=0;i<m;i++)
scanf("%d", &avail[i]);
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;
for(y=0;y<m;y++)
avail[y] += alloc[i][y];
f[i]=1;
}
}
}
}
int flag=1;
for(i=0;i<n;i++) {
if(f[i]==0) {
flag=0;
printf("System is not in a safe state\n");
break;
}
}
if(flag==1) {
printf("System is in a safe state\nSafe sequence is: ");
for(i=0;i<n-1;i++)
printf("P%d -> ", ans[i]);
printf("P%d\n", ans[n-1]);
}
return 0;
}
Output
Displays whether the system is in a safe state and prints the Safe Sequence of processes.
Result
Thus, the Banker's Algorithm was successfully implemented and the safe sequence was
displayed.
Sample Input/Output for Question 1
Sample Input:
Number of Processes: 3
Number of Resources: 3
Allocation Matrix:
P0: 0 1 0
P1: 2 0 0
P2: 3 0 2
Max Matrix:
P0: 7 5 3
P1: 3 2 2
P2: 9 0 2
Available Resources: 3 3 2
Sample Output:
Safe Sequence: P1 -> P0 -> P2
System is in a SAFE STATE.
Question 2
Write a C program to implement the Banker's algorithm and identify the deadlocked states.
Aim
To write a C program to implement the Banker's Algorithm and identify deadlocked states.
Algorithm
1. Input the number of processes and resources.
2. Input Allocation, Max, and Available matrices.
3. Calculate the Need matrix.
4. Initialize Work = Available and Finish[i] = false.
5. Try to find a process whose Need <= Work.
6. If found, mark Finish[i] = true and add Allocation[i] to Work.
7. If no such process is found and there are unfinished processes, they are deadlocked.
C Code
#include <stdio.h>
int main() {
int n, m, i, j, k;
printf("Enter number of processes: ");
scanf("%d", &n);
printf("Enter number of resources: ");
scanf("%d", &m);
int alloc[n][m], max[n][m], avail[m];
printf("Enter Allocation Matrix:
");
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d", &alloc[i][j]);
printf("Enter Max Matrix:
");
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d", &max[i][j]);
printf("Enter Available Resources:
");
for(i=0;i<m;i++)
scanf("%d", &avail[i]);
int f[n], ind=0;
for(i=0;i<n;i++) f[i]=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 count=0;
while(count<n) {
int found=0;
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) {
for(j=0;j<m;j++)
avail[j]+=alloc[i][j];
f[i]=1;
found=1;
count++;
}
}
}
if(found==0) break;
}
int deadlock=0;
for(i=0;i<n;i++) {
if(f[i]==0) {
deadlock=1;
printf("Process P%d is in Deadlock\n", i);
}
}
if(deadlock==0)
printf("No Deadlock detected\n");
return 0;
}
Output
Displays processes that are deadlocked if any. If no deadlock exists, prints 'No Deadlock
detected'.
Result
Thus, the Banker's Algorithm was successfully implemented and deadlocked states were
identified.
Sample Input/Output for Question 2
Sample Input:
Number of Processes: 3
Number of Resources: 3
Allocation Matrix:
P0: 0 2 0
P1: 3 0 3
P2: 2 1 1
Max Matrix:
P0: 1 3 2
P1: 3 2 3
P2: 3 3 3
Available Resources: 0 0 1
Sample Output:
No Safe Sequence Found!
System is in a DEADLOCKED STATE.
