/* Demonstration implementation of the "Banker's Algorithm"
as described A. S. Tanenbaum, "Modern Operating Systems",
2nd ed., Prentice Hall, Upper Saddle River, NJ, 2001.
Herbert J. Bernstein, yaya@dowling.edu, 3 April 2002
The original design of the Banker's Algorith is due to
Dijkstra (1965)
The purpose of this code is to demonstrate a common
"systems" programming style using a mixture of C and C++.
The code is intentionally non-modular, something simply
"dashed off" while transcribing an idea from a book
directly into code. Final code would be extensively
reqorked and modularized.
*/
/* We will need some standard C library routines, such as malloc
*/
#include <stdlib.h>
/* We will take advantage of the C++ iostream library
*/
#include <iostream>
/* We will pick up two useful parameters from the command
line. In order to do this we need to declare the argument
count (argc) and the array of strings (argv). Note that
we have declared an array of strings (which in C is actually
an array or arrays of chars) with pointer syntax, rather
than with array syntax.
*/
int main (int argc, char ** argv) {
/* Now we need to declare essential variables.
We will use two 1-dimensional arrays and two 2-dimensional
arrays, but we declare them as pointers, and use malloc
call later to make them into arrays with actual storage
*/
int num_resources; /* The number of resources */
int num_customers; /* The number of customers (processes) */
int ii, jj; /* A couple of scratch variables for loops */
int * existing_resources; /* An array of the total resources existing */
int * available_resources; /* An array of currently available resources */
int ** current_allocation; /* A 2-dimensional array with one row per
customer, one column per resource, giving
the current allocations of resources to
customers */
int ** requested_resources; /* A similar 2-dimensional array giving the
additional resource requests that each
customer might make *.
/* We extract the number of customers and the number of resources from the
command line.
*/
cout << "Bankers Algorithm" <<endl;
if (argc > 2 ) {
num_customers = atoi(argv[1]);
num_resources = atoi(argv[2]);
cout << "Customers: "<<num_customers
<<" Resources: " << num_resources << endl;
} else {
cerr << "Please specify the number of customers and resources" <<endl;
exit(1);
}
/* Now we provide some storage for our arrays. Note that each call
to malloc return NULL, indicating failure, and that we need to
cast the pointer mallow returns to the correct type.
*/
/* For the first two array, we just need to allocate space for the
elements themselves. Note, however, that for the last two arrays,
we first need to allocate a dope vector and then to allocate
storage for each row of data. This is very different from the
handling of multiply dimensioned arrays in a language such as,
say, Fortran, which would allocate all the data area as one large
contiguous block. */
/* Notice the use of the NULL return case as equivalent to false */
if (! (existing_resources = (int *)malloc(sizeof(int)*num_resources))) {
cerr << "Failed to allocate existing_resources "<< endl; exit(1);
}
if (! (available_resources = (int *)malloc(sizeof(int)*num_resources))) {
cerr << "Failed to allocate available_resources "<< endl; exit(1);
}
if (! (current_allocation = (int **)malloc(sizeof(int *)*num_customers))) {
cerr << "Failed to allocate the current_allocation dope vector"<< endl;
exit(1);
}
if (! (requested_resources = (int **)malloc(sizeof(int *)*num_customers))) {
cerr << "Failed to allocate the requested_resources dope vector"<< endl;
exit(1);
}
for (ii = 0; ii < num_customers; ii++) {
if (! (current_allocation[ii] = (int *)malloc(sizeof(int)*num_resources))) {
cerr << "Failed to allocate the current_allocation dope vector entry "<< ii << endl;
}
if (! (requested_resources[ii] = (int *)malloc(sizeof(int)*num_resources))) {
cerr << "Failed to allocate the requested_resources dope vector entry "<< ii << endl;
}
}
/* Having allocated storage, we now ask to the data,
element by element */
/* First we load up the array of existing resources */
for (ii = 0; ii < num_resources; ii++) {
cout << "How many of resource " << ii << " exist? ";
cin >> existing_resources[ii];
available_resources[ii] = existing_resources[ii];
}
/* Now for each customer and resource, we inquire
as to how many resource units are allocated,
and what is the maximum number that will be
needed. We subtract the current use from the
maximum to discover how many more will be needed.
*/
for (ii = 0; ii < num_customers; ii++) {
cout << "Tell me about the resources for customer " << ii << endl;
for (jj = 0; jj < num_resources; jj++) {
cout << " How many of resource " << jj
<< " are currently allocated to customer "
<< ii << "? ";
cin >> current_allocation[ii][jj];
available_resources[jj] -= current_allocation[ii][jj];
if (available_resources[jj] < 0 ) {
cerr << "Overallocation of resources" << endl;
exit(1);
}
cout << " How many maximum of resource " << jj
<< " would customer " << ii
<< " like to have? ";
cin >> requested_resources[ii][jj];
requested_resources[ii][jj] -= current_allocation[ii][jj];
}
}
/* All that is left to do is to cycle through, seeing
if there is some way to get enough resources to satisfy
some customer. If those resources exist, then we are
certain that that customer can be run to completion,
so, instead of allocating resources to the customer,
we return the resources that customer currently holds
to the pool, mark the customer as satisfied and look
for another customer to satisfy.
If we run out of customers before we run out of
resources, the original allocation was "safe".
*/
{ int done = 0;
int failed;
int trials;
int freed;
while (!done) {
trials = 0;
freed = 0;
for (ii=0; ii < num_customers; ii++) {
if (requested_resources[ii]) {
trials++;
failed = 0;
for (jj = 0; jj < num_resources; jj++) {
if (requested_resources[ii][jj] > available_resources[jj] ) {
failed = 1;
cout << "Failed to satisfy customer " << ii << endl;
break;
}
}
if ( !failed ) {
freed++;
for (jj = 0; jj < num_resources; jj++) {
available_resources[jj] += current_allocation[ii][jj];
}
free(requested_resources[ii]);
requested_resources[ii] = NULL;
cout << "Satisfying customer " << ii << endl;
}
}
}
if (trials == 0) {
cout << "The state is safe!!!" << endl;
exit(0);
}
if (freed == 0) {
cerr << "unsafe!!!" <<endl;
exit(1);
}
}
}
}