What is Banker’s algorithm
Banker’s algorithm is an algorithm to avoid deadlock and to allocate resources to the processes safely. Banker’s algorithm helps the operating system to successfully share the resources among all the processes.
Let’s discuss with an example;
Examples of bankers algorithm
Example 1
Example 2
| Process | Total instances of Resource A | Total instances of Resource B | Total instances of Resource C |
| P0 | 0 | 1 | 0 |
| P1 | 2 | 0 | 0 |
| P2 | 3 | 0 | 2 |
| P3 | 2 | 1 | 1 |
| P4 | 0 | 0 | 2 |
Table: Showing resources already processes occupies
Note: PCB manage the memory by keeping a record of the allocated resources and free resources.
Explanation of the table
Process P0 already has 0 resource instances of A, 1 resource instance of B, and similarly 0 resource instance of C.
Process P1 already has 2 resource instances of A, 0 resource instance of B, and similarly 0 resource instance of C.
Process P2 already have 3 resource instances of A, 0 resource instance of B, and similarly 2 resource instance of C.
Process P3 already has 2 resource instances of A, 1 resource instance of B, and similarly 1 resource instance of C.
Process P4 already have 0 resource instances of A, 0 resource instance of B, and similarly 2 resource instance of C.
| Process | Total instances of Resource A | Total instances of Resource B | Total instances of Resource C |
| P0 | 7 | 5 | 3 |
| P1 | 3 | 2 | 2 |
| P2 | 9 | 0 | 2 |
| P3 | 2 | 2 | 2 |
| P4 | 4 | 3 | 3 |
Table: Showing maximum resources required for complete execution.
Explanation of the table
Process P0 requires a maximum of 7 resource instances of A, 51 resource instances of B, and similarly 3 resource instances of C for the successful execution.
Process P1 requires a maximum of 3 resource instances of A, 2 resource instance of B, and similarly 2 resource instances of C for the successful execution.
Process P2 requires a maximum of 9 resource instances of A, 0 resource instance of B, and similarly 2 resource instances of C for the successful execution.
Process P3 requires a maximum of 2 resource instances of A, 2 resource instance of B, and similarly 2 resource instances of C for the successful execution.
Process P4 requires a maximum of 4 resource instances of A, 3 resource instance of B, and similarly 3 resource instances of C for the successful execution.
| Process | Total instances of Resource A | Total instances of Resource B | Total instances of Resource C |
| P0 | 7 | 4 | 3 |
| P1 | 1 | 2 | 2 |
| P2 | 6 | 0 | 0 |
| P3 | 0 | 1 | 1 |
| P4 | 4 | 3 | 1 |
Table: Showing needed resources to each process for execution.
We can get the needed resources with the help of the following formula;
Needed resources = maximum resources – allocated resources
| Process | Total instances of Resource A | Total instances of Resource B | Total instances of Resource C |
| P0 | 3 | 3 | 2 |
| P1 | 5 | 3 | 2 |
| P2 | 5 | 3 | 2 |
| P3 | 7 | 4 | 3 |
| P4 | 7 | 4 | 5 |
| P0 | 7 | 5 | 5 |
| P2 | 10 | 5 | 7 |
Table: Showing available free resources for each process.
Now compare available free resources of each process with its needed resources. The needed matrix should less than/equal as compared to the available matrix for process execution.
First iteration:
P0=finish[p0]=False can’t execute because if we assign free resources
to P0, and we add the free resources of P0 with
needed resources of P0, it still does not fulfill the
the requirement of maximum resources needed to P0 for
it’s execution.
P1=FINISH[P1]=TRUE can execute
P2=FINISH[P2]=False can’t execute
P3=FINSH[P3]=TRUE can execute
P4=FINISH[P4]=TRUE can execute
2nd iteration:
P0=FINISH[P0]=TRUE can execute
P2=FINISH[P2]=TRUE can execute
Example 3
Allocated Resources
| A | B | C | |
| P1 | 2 | 0 | 1 |
| P2 | 5 | 2 | 6 |
| P3 | 3 | 1 | 5 |
| P4 | 4 | 0 | 9 |
Maximum Resources
| A | B | C | |
| P1 | 3 | 5 | 4 |
| P2 | 9 | 2 | 8 |
| P3 | 5 | 7 | 5 |
| P4 | 8 | 6 | 10 |
Needed Resources
| A | B | C | |
| P1 | 1 | 5 | 3 |
| P2 | 4 | 0 | 2 |
| P3 | 2 | 6 | 0 |
| P4 | 4 | 6 | 1 |
Free Resources
| A | B | C |
| 3 | 7 | 2 |
P1= fails ( as the number of needed resources are greater than the free resources)
P2=fails ( as the number of needed resources are greater than the free resources)
P3= works and executes
After the execution of P3, it releases its allocated resources as well so that the number of free resources increased.
Free Resources
| A | B | C |
| 6 | 8 | 7 |
P4= works and executes
After the execution of P4, it releases its allocated resources to increased the number of free resources.
Free ResourceP1
| A | B | C |
| 10 | 8 | 16 |
P1= works and executes
After the execution of P1, it releases its allocated resources to increased the number of free resources.
Free Resources
| A | B | C |
| 12 | 8 | 17 |
P2= works and executes
After the execution of P2, it releases its allocated resources to increased the number of free resources.
Free Resources
| A | B | C |
| 15 | 10 | 23 |
These are the free resources when all the processes execute successfully.
Click Below to Download Implementation file
Bankers algorithm implementation Operating Systems (OS)
Advantages of Banker’s algorithm
Banker’s algorithm Avoids deadlock and it is less restrictive than deadlock prevention.
Disadvantages of Banker’s algorithm
It only works with a fixed number of resources and processes.
Banker Algorithm code in C
Here, i am sharing with you the banker algorithm code in 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 |
#include <iostream> #include <stdio.h> int Resources_Available[5]; int Resources_Required[5][5]; int Resources_Already_Having[5][5]; int allocation[5] = {0, 0, 0, 0, 0}; int maxres[5], running[5], safe = 0; int counter = 0, i, j, Exection, resources, processes, k = 1; int main() { printf("\nEnter number of processes: "); scanf("%d", &processes); for (i = 0; i < processes; i++) { running[i] = 1; counter++; } printf("\nEnter number of resources: "); scanf("%d", &resources); printf("\nEnter Claim Resources:"); for (i = 0; i < resources; i++) { scanf("%d", &maxres[i]); } printf("\nEnter Allocated Resource Table:\n"); for (i = 0; i < processes; i++) { for(j = 0; j < resources; j++) { scanf("%d", &Resources_Already_Having[i][j]); } } printf("\nEnter Maximum Claim Table:\n"); for (i = 0; i < processes; i++) { for(j = 0; j < resources; j++) { scanf("%d", &Resources_Required[i][j]); } } printf("\nThe Claim Resources is: "); for (i = 0; i < resources; i++) { printf("\t%d", maxres[i]); } printf("\nThe Allocated Resource Table:\n"); for (i = 0; i < processes; i++) { for (j = 0; j < resources; j++) { printf("\t%d", Resources_Already_Having[i][j]); } printf("\n"); } printf("\nThe Maximum Claim Table:\n"); for (i = 0; i < processes; i++) { for (j = 0; j < resources; j++) { printf("\t%d", Resources_Required[i][j]); } printf("\n"); } for (i = 0; i < processes; i++) { for (j = 0; j < resources; j++) { allocation[j] += Resources_Already_Having[i][j]; } } printf("\nAllocated resources:"); for (i = 0; i < resources; i++) { printf("\t%d", allocation[i]); } for (i = 0; i < resources; i++) { Resources_Available[i] = maxres[i] - allocation[i]; } printf("\nAvailable resources:"); for (i = 0; i < resources; i++) { printf("\t%d", Resources_Available[i]); } printf("\n"); while (counter != 0) { safe = 0; for (i = 0; i < processes; i++) { if (running[i]) { Exection = 1; for (j = 0; j < resources; j++) { if (Resources_Required[i][j] - Resources_Already_Having[i][j] > Resources_Available[j]) { Exection = 0; break; } } if (Exection) { printf("\nProcess%d is Execting\n", i + 1); running[i] = 0; counter--; safe = 1; for (j = 0; j < resources; j++) { Resources_Available[j] += Resources_Already_Having[i][j]; } break; } } } if (!safe) { printf("\nThe processes are in unsafe state.\n"); break; } else { printf("\nThe process is in safe state"); printf("\nAvailable Resources:"); for (i = 0; i < resources; i++) { printf("\t%d", Resources_Available[i]); } printf("\n"); } } return 0; } |
Output
Frequently Asked Questions (FAQ)
Who developed the banker’s algorithm?
Edsger Dijkstra developed the banker’s algorithm.
Excercise
Answer the following questions using the bankers algorithm.
- System is in safe state or not?
- How you will apply bankers algorithm on the given data.
| Allocation | Max | Available | |
| A B C D | A B C D | A B C D | |
| P1 | 4111 | 4414 | 7741 |
| P1 | 7141 | 5454 | |
| P4 | 4117 | 4716 | |
| P7 | 1714 | 1444 | |
| P4 | 1474 | 7665 |
