I've been working on a bankers algorithm implementation in C and it seems to work fine except the allocation matrix isn't adding values correctly. In the request resources function, I use a mutex lock at the beginning and unlock right before returning a value to indicate pass or failure. In the function itself, the allocation matrix updates with what's been requested and given but when another thread comes in and does it's request, the allocation resets and starts adding again. I'm not sure why this is since allocation is global like the other structures being modified in the function and they are updating values properly.
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<pthread.h>
#include<semaphore.h>
/* these may be any values >= 0 */
#define NUMBER_OF_CUSTOMERS 5
#define NUMBER_OF_RESOURCES 3
/* the available amount of each resource */
int available[NUMBER_OF_RESOURCES];
/*the maximum demand of each customer */
int maximum[NUMBER_OF_CUSTOMERS][NUMBER_OF_RESOURCES];
/* the amount currently allocated to each customer */
int allocation[NUMBER_OF_CUSTOMERS][NUMBER_OF_RESOURCES];
/* the remaining need of each customer */
int need[NUMBER_OF_CUSTOMERS][NUMBER_OF_RESOURCES];
pthread_mutex_t mutex =
PTHREAD_MUTEX_INITIALIZER;
struct threadParams {
int req[3];
int threadNum;
};
int safe_state(int customer_num){
int work[NUMBER_OF_RESOURCES];
int done =0;
for(int w = 0; w < NUMBER_OF_CUSTOMERS; w++){
work[w] = available[w];
}
int finish[NUMBER_OF_CUSTOMERS];
for(int i = 0; i < NUMBER_OF_CUSTOMERS; i++){
finish[i] = 0;
//setting finish to false
}
for(int k = 0; k < NUMBER_OF_CUSTOMERS; k++){
for(int j = 0; j< NUMBER_OF_RESOURCES; j++){
if(finish[k] == 0 && need[customer_num][k] <= work[j]){
work[j] += allocation[customer_num][j];
finish[k] = 1;
//printf("%d\n", finish[k]);
}
}
}
for(int x = 0; x < NUMBER_OF_CUSTOMERS; x++){
if(finish[x] == 1){
done = 1;
}
else{
done = -1;
}
}
if(done == 1){
printf("\n Granted\n");
return done;
}
printf("\nDenied\n");
return done;
}
void* request_resources(void *arg){
pthread_mutex_lock(&mutex);
struct threadParams *params = arg;
int customer_num = params->threadNum;
printf("\nCustomer %d is in critical\n", customer_num+1);
int request[3];
request[0] = params->req[0];
request[1] = params->req[1];
request[2] = params->req[2];
int pass;
for(int i = 0; i < NUMBER_OF_RESOURCES; i++){
if(request[i] <= need[customer_num][i] && request[i] <= available[i]){
//printf("\nreq: %d, need: %d, avail: %d, alloc: %d\n\t", request[i], need[customer_num][i], available[i],allocation[customer_num][i]);
int state = safe_state(customer_num);
if(state == 1){
available[i] -= request[i];
allocation[customer_num][i] += request[i];
//printf("%d + %d\n", allocation[customer_num][i], request[i]);
need[customer_num][i] -= request[i];
pass = 1;
}
else if(state == -1){
printf("\nThe request from customer %d results in unsafe state\n", customer_num+1);
printf("\nreq: %d, need: %d, avail: %d, alloc: %d\n\t", request[i], need[customer_num][i], available[i],allocation[customer_num][i]);
pass = -1;
break;
}
}
else{
printf("\nreq: %d, need: %d, avail: %d\n", request[i], need[customer_num][i], available[i]);
printf("\nNot enough resources for customer %d's request or the customer doesn't need this resource.\n", customer_num);
pass = -1;
break;
}
printf("\nResource: %d req: %d, need: %d, avail: %d, alloc: %d\n\t",i+1, request[i], need[customer_num][i], available[i],allocation[customer_num][i]);
}
//printf("I'm a thread\n");
pthread_mutex_unlock(&mutex);
printf("\n Customer %d has left critical\n", customer_num+1);
return pass;
}
int release_resources(int customer_num, int release[]){
}
int main(int argc, char *argv[]){
pthread_t threads [NUMBER_OF_CUSTOMERS];
int result;
unsigned index = 0;
// for(int ii = 0; ii < NUMBER_OF_CUSTOMERS; ii++){
// for(int jj = 0; jj < NUMBER_OF_RESOURCES; jj++){
// allocation[ii][jj] += 0;
// }
// }
for(index = 0; index < NUMBER_OF_RESOURCES; index++){
available[index] = strtol(argv[index+1], NULL,10);
}
for(int i = 0; i < NUMBER_OF_CUSTOMERS; i++){
for(int j = 0; j < NUMBER_OF_RESOURCES; j++){
maximum[i][j] = strtol(argv[j+1], NULL, 10)-4;
need[i][j] = 2; //strtol(argv[j+1], NULL, 10) - 6;
//printf("%d\t", maximum[i][j]);
}
}
for(index = 0; index < NUMBER_OF_CUSTOMERS; index++){
printf("\nCreating customer %d\n", index+1);
struct threadParams params;
params.req[0] = 2;
params.req[1] = 2;
params.req[2] = 2;
params.threadNum = index;
result = pthread_create(&threads[index],NULL,request_resources,¶ms);
}
for(index = 0; index < NUMBER_OF_CUSTOMERS; ++index){
pthread_join(threads[index], NULL);
}
printf("\nDone");
}
Finally, I found some time to handle this seriously:
I still have problems to understand your implementation in general. (I spent some hours to first understand Edsger Dijkstras Banker's algorithm itself before I came back.)
Thus, I do not understand why you distinguish
need[]andthreadParams.req[]. When I got it right this should actually be the same (i.e. one of them should not be there).However, I want to show you what I got so far (which might be a help). After I studied and compared multiple samples I finally made a modified version of Banker's Algorithm on rosettacode.org:
(Debugged in VS2013 but) compiled and tested with gcc in cygwin on Windows 10 (64 bit):
This looks quite good (for me).
Now, I made a derived sample introducing multi-threading.
A note about this:
The Wikipedia article Banker's algorithm states that the algorithm is intended for OS resource management like e.g. memory, semaphores and interface access. Sounds for me like, these algorithm is intended to manage things like muteces. Thus, a mutex should/can not be used for it and multi-threading makes not so much sense.
However, let forget about my concern and say this is for educational/understanding purpose:
(Again debugged in VS2013 but) compiled and tested with gcc in cygwin on Windows 10 (64 bit):
Although, this looks quite good also, I'm not sure about whether the dead-lock detection is 100 % correct. Because multi-threading introduces non-deterministics, this is hard to test. I tried to "debug it by head" but ended up with headache...
Note about implementation:
I used the thin-layer for multi-threading, again. Thus, these samples can be compiled in C++ (
std::thread, VS2013/g++) as well as in C (pthread, gcc).