Banker's algorithm: Difference between revisions
(cut and past from wikipedia... will need a good review (maybe even rewrite), code from ip:117.211.161.26) |
(C entry: reformatted code and output) |
||
Line 35: | Line 35: | ||
There are two <code>main()</code> functions to choose from (look for <code>#define BIG_EXAMPLE</code>), one is for task example, the other is a much heavier duty test case. |
There are two <code>main()</code> functions to choose from (look for <code>#define BIG_EXAMPLE</code>), one is for task example, the other is a much heavier duty test case. |
||
<lang c>#include <stdio.h> |
|||
<lang c>/*PROGRAM TO IMPLEMENT BANKER'S ALGORITHM |
|||
#include <stdbool.h> |
|||
* --------------------------------------------*/ |
|||
int main() { |
|||
#include <stdio.h> |
|||
int curr[5] |
int curr[5][5]; |
||
int |
int max_claim[5][5]; |
||
int |
int avl[5]; |
||
int |
int alloc[5] = {0, 0, 0, 0, 0}; |
||
int max_res[5]; |
|||
main(){ |
|||
int running[5]; |
|||
printf("\nEnter the number of resources:"); |
|||
scanf("%d",&r); |
|||
printf("\nEnter the number of processes:"); |
|||
scanf("%d",&p); |
|||
for(i=0;i<p;i++){ |
|||
running[i]=1; |
|||
count++; |
|||
} |
|||
printf("\nEnter Claim Vector:"); |
|||
for(i=0;i<r;i++) scanf("%d",&maxres[i]); |
|||
int i, j, exec, r, p; |
|||
printf("\nEnter Allocated Resource Table:"); |
|||
int count = 0; |
|||
for(i=0;i<p;i++){ |
|||
bool safe = false; |
|||
for(j=0;j<r;j++) scanf("%d",&curr[i][j]); |
|||
} |
|||
printf("\nEnter |
printf("\nEnter the number of resources: "); |
||
scanf("%d", &r); |
|||
for(i=0;i<p;i++){ |
|||
for(j=0;j<r;j++) scanf("%d",&maxclaim[i][j]); |
|||
} |
|||
printf("\ |
printf("\nEnter the number of processes: "); |
||
scanf("%d", &p); |
|||
for (i = 0; i < p; i++) { |
|||
printf("\nThe Allocated Resource Table:\n"); |
|||
running[i] = 1; |
|||
for(i=0;i<p;i++){ |
|||
count++; |
|||
} |
|||
printf("\t%d",curr[i][j]); |
|||
printf("\n"); |
|||
printf("\nEnter Claim Vector: "); |
|||
} |
|||
for (i = 0; i < r; i++) |
|||
printf("\nThe Maximum Claim Table:\n"); |
|||
scanf("%d", &max_res[i]); |
|||
for(i=0;i<p;i++){ |
|||
for(j=0;j<r;j++) printf("\t%d",maxclaim[i][j]); |
|||
printf("\nEnter Allocated Resource Table: "); |
|||
for (i = 0; i < p; i++) { |
|||
for (j = 0; j < r; j++) |
|||
scanf("%d", &curr[i][j]); |
|||
} |
|||
printf("\nEnter Maximum Claim table: "); |
|||
for (i = 0; i < p; i++) { |
|||
for (j = 0; j < r; j++) |
|||
scanf("%d", &max_claim[i][j]); |
|||
} |
|||
printf("\nThe Claim Vector is: "); |
|||
for (i = 0; i < r; i++) |
|||
printf("%d ", max_res[i]); |
|||
printf("\nThe Allocated Resource Table:\n"); |
|||
for (i = 0; i < p; i++) { |
|||
for (j = 0; j < r; j++) |
|||
printf("\t%d", curr[i][j]); |
|||
printf("\n"); |
|||
} |
|||
printf("\nThe Maximum Claim Table:\n"); |
|||
for (i = 0; i < p; i++) { |
|||
for (j = 0; j < r; j++) |
|||
printf("\t%d", max_claim[i][j]); |
|||
printf("\n"); |
|||
} |
|||
for (i = 0; i < p; i++) |
|||
for (j = 0; j < r; j++) |
|||
alloc[j] += curr[i][j]; |
|||
printf("\nAllocated resources: "); |
|||
for (i = 0; i < r; i++) |
|||
printf("%d ", alloc[i]); |
|||
for (i = 0; i < r; i++) |
|||
avl[i] = max_res[i] - alloc[i]; |
|||
printf("\nAvailable resources: "); |
|||
for (i = 0; i < r; i++) |
|||
printf("%d ", avl[i]); |
|||
printf("\n"); |
printf("\n"); |
||
} |
|||
while (count != 0) { |
|||
for(i=0;i<p;i++) |
|||
safe = false; |
|||
for(j=0;j<r;j++) alloc[j]+=curr[i][j]; |
|||
for (i = 0; i < p; i++) { |
|||
printf("\n Allocated resources:"); |
|||
if (running[i]) { |
|||
for(i=0;i<r;i++) printf("\t%d",alloc[i]); |
|||
exec = 1; |
|||
for(i=0;i<r;i++) avl[i]=maxres[i]-alloc[i]; |
|||
for (j = 0; j < r; j++) { |
|||
printf("\n Available resources:"); |
|||
if (max_claim[i][j] - curr[i][j] > avl[j]) { |
|||
for(i=0;i<r;i++) printf("\t%d",avl[i]); |
|||
exec = 0; |
|||
printf("\n"); |
|||
break; |
|||
while(count!=0){ |
|||
} |
|||
safe=0; |
|||
} |
|||
for(i=0;i<p;i++){ |
|||
if(running[i]){ |
|||
exec |
if (exec) { |
||
printf("\nProcess%d is executing.\n", i + 1); |
|||
for(j=0;j<r;j++){ |
|||
running[i] = 0; |
|||
count--; |
|||
safe = true; |
|||
for (j = 0; j < r; j++) |
|||
avl[j] += curr[i][j]; |
|||
break; |
|||
} |
|||
} |
|||
} |
|||
if (!safe) { |
|||
printf("\nThe processes are in unsafe state."); |
|||
break; |
break; |
||
} |
|||
} |
} |
||
if(exec){ |
|||
printf("\nProcess%d is executing\n",i+1); |
|||
running[i]=0; |
|||
count--; |
|||
safe=1; |
|||
for(j=0;j<r;j++) avl[j]+=curr[i][j]; |
|||
break; |
|||
} |
|||
} |
|||
} |
|||
if(!safe){ |
|||
printf("\nThe processes are in unsafe state"); |
|||
break; |
|||
} |
|||
if(safe) printf("\n The process is in safe state"); |
|||
printf("\n Available vector:"); |
|||
for(i=0;i<r;i++) printf("\t%d",avl[i]); |
|||
} |
|||
}</lang> |
|||
if (safe) |
|||
'''Output:''' |
|||
printf("\nThe process is in safe state."); |
|||
printf("\nAvailable vector: "); |
|||
Enter the number of resources:4 |
|||
for (i = 0; i < r; i++) |
|||
printf("%d ", avl[i]); |
|||
} |
|||
return 0; |
|||
}</lang> |
|||
{{out|Input and Output}} |
|||
<pre>Enter the number of resources: 4 |
|||
Enter the number of processes:5 |
Enter the number of processes: 5 |
||
Enter |
Enter Claim Vector: 8 5 9 7 |
||
Enter Allocated Resource Table: |
Enter Allocated Resource Table: 2 0 1 1 0 1 2 1 4 0 0 3 0 2 1 0 1 0 3 0 |
||
2 0 1 1 |
|||
0 1 2 1 |
|||
4 0 0 3 |
|||
0 2 1 0 |
|||
1 0 3 0 |
|||
Enter Maximum Claim table: |
Enter Maximum Claim table: 3 2 1 4 0 2 5 2 5 1 0 5 1 5 3 0 3 0 3 3 |
||
3 2 1 4 |
|||
0 2 5 2 |
|||
5 1 0 5 |
|||
1 5 3 0 |
|||
3 0 3 3 |
|||
The Claim Vector is: |
The Claim Vector is: 8 5 9 7 |
||
The Allocated Resource Table: |
The Allocated Resource Table: |
||
2 0 1 1 |
|||
2 0 1 1 |
|||
0 1 2 1 |
|||
0 1 2 1 |
|||
4 0 0 3 |
|||
4 0 0 3 |
|||
0 2 1 0 |
|||
0 2 1 0 |
|||
1 0 3 0 |
|||
1 0 3 0 |
|||
The |
The Maximum Claim Table: |
||
3 2 1 4 |
|||
3 2 1 4 |
|||
0 2 5 2 |
|||
0 2 5 2 |
|||
5 1 0 5 |
|||
5 1 0 5 |
|||
1 5 3 0 |
|||
1 5 3 0 |
|||
3 0 3 3 |
|||
3 0 3 3 |
|||
Allocated resources: 7 3 7 5 |
|||
Available resources: 1 2 2 2 |
|||
Process3 is executing |
Process3 is executing. |
||
The process is in safe state. |
|||
Available vector: 5 2 2 5 |
|||
Process1 is executing |
Process1 is executing. |
||
The process is in safe state. |
|||
Available vector: 7 2 3 6 |
|||
Process2 is executing |
Process2 is executing. |
||
The process is in safe state. |
|||
Available vector: 7 3 5 7 |
|||
Process4 is executing |
Process4 is executing. |
||
The process is in safe state. |
|||
Available vector: 7 5 6 7 |
|||
Process5 is executing |
Process5 is executing. |
||
The process is in safe state. |
|||
Available vector: 8 5 9 7</pre> |
Revision as of 15:57, 24 February 2013
This page uses content from Wikipedia. The original article was at Banker's algorithm. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |
The Banker's algorithm is a resource allocation and deadlock avoidance algorithm developed by Edsger Dijkstra that tests for safety by simulating the allocation of predetermined maximum possible amounts of all resources, and then makes a "s-state" check to test for possible deadlock conditions for all other pending activities, before deciding whether allocation should be allowed to continue.
Example input
Assuming that the system distinguishes between four types of resources, (A, B, C and D), the following is an example of how those resources could be distributed. Note that this example shows the system at an instant before a new request for resources arrives. Also, the types and number of resources are abstracted. Real systems, for example, would deal with much larger quantities of each resource.
Total resources in system: A B C D 6 5 7 6
Available system resources are: A B C D 3 1 1 2
Processes (currently allocated resources): A B C D P1 1 2 2 1 P2 1 0 3 3 P3 1 2 1 0
Processes (maximum resources): A B C D P1 3 3 2 2 P2 1 2 3 4 P3 1 3 5 0
Need= maximum resources - currently allocated resources Processes (need resources): A B C D P1 2 1 0 1 P2 0 2 0 1 P3 0 1 4 0
C
Standard binary heap-as-priority queue affair. Only that each node links back to its heap position for easier update.
There are two main()
functions to choose from (look for #define BIG_EXAMPLE
), one is for task example, the other is a much heavier duty test case.
<lang c>#include <stdio.h>
- include <stdbool.h>
int main() {
int curr[5][5]; int max_claim[5][5]; int avl[5]; int alloc[5] = {0, 0, 0, 0, 0}; int max_res[5]; int running[5];
int i, j, exec, r, p; int count = 0; bool safe = false;
printf("\nEnter the number of resources: "); scanf("%d", &r);
printf("\nEnter the number of processes: "); scanf("%d", &p); for (i = 0; i < p; i++) { running[i] = 1; count++; }
printf("\nEnter Claim Vector: "); for (i = 0; i < r; i++) scanf("%d", &max_res[i]);
printf("\nEnter Allocated Resource Table: "); for (i = 0; i < p; i++) { for (j = 0; j < r; j++) scanf("%d", &curr[i][j]); }
printf("\nEnter Maximum Claim table: "); for (i = 0; i < p; i++) { for (j = 0; j < r; j++) scanf("%d", &max_claim[i][j]); }
printf("\nThe Claim Vector is: "); for (i = 0; i < r; i++) printf("%d ", max_res[i]);
printf("\nThe Allocated Resource Table:\n"); for (i = 0; i < p; i++) { for (j = 0; j < r; j++) printf("\t%d", curr[i][j]); printf("\n"); }
printf("\nThe Maximum Claim Table:\n"); for (i = 0; i < p; i++) { for (j = 0; j < r; j++) printf("\t%d", max_claim[i][j]); printf("\n"); }
for (i = 0; i < p; i++) for (j = 0; j < r; j++) alloc[j] += curr[i][j];
printf("\nAllocated resources: "); for (i = 0; i < r; i++) printf("%d ", alloc[i]); for (i = 0; i < r; i++) avl[i] = max_res[i] - alloc[i];
printf("\nAvailable resources: "); for (i = 0; i < r; i++) printf("%d ", avl[i]); printf("\n");
while (count != 0) { safe = false; for (i = 0; i < p; i++) { if (running[i]) { exec = 1; for (j = 0; j < r; j++) { if (max_claim[i][j] - curr[i][j] > avl[j]) { exec = 0; break; } }
if (exec) { printf("\nProcess%d is executing.\n", i + 1); running[i] = 0; count--; safe = true; for (j = 0; j < r; j++) avl[j] += curr[i][j]; break; } } }
if (!safe) { printf("\nThe processes are in unsafe state."); break; }
if (safe) printf("\nThe process is in safe state.");
printf("\nAvailable vector: "); for (i = 0; i < r; i++) printf("%d ", avl[i]); }
return 0;
}</lang>
- Input and Output:
Enter the number of resources: 4 Enter the number of processes: 5 Enter Claim Vector: 8 5 9 7 Enter Allocated Resource Table: 2 0 1 1 0 1 2 1 4 0 0 3 0 2 1 0 1 0 3 0 Enter Maximum Claim table: 3 2 1 4 0 2 5 2 5 1 0 5 1 5 3 0 3 0 3 3 The Claim Vector is: 8 5 9 7 The Allocated Resource Table: 2 0 1 1 0 1 2 1 4 0 0 3 0 2 1 0 1 0 3 0 The Maximum Claim Table: 3 2 1 4 0 2 5 2 5 1 0 5 1 5 3 0 3 0 3 3 Allocated resources: 7 3 7 5 Available resources: 1 2 2 2 Process3 is executing. The process is in safe state. Available vector: 5 2 2 5 Process1 is executing. The process is in safe state. Available vector: 7 2 3 6 Process2 is executing. The process is in safe state. Available vector: 7 3 5 7 Process4 is executing. The process is in safe state. Available vector: 7 5 6 7 Process5 is executing. The process is in safe state. Available vector: 8 5 9 7