Banker's Algorithm

banker.c

#include <stdio.h>
#include <stdlib.h>

#define TYPES_OF_RESOURCES 3
#define NUM_OF_THREADS 5
#define DEBUG 2

void populate_need();
int is_system_in_safe_state();
void traverse_array(int length, int* first, char* name);
void populate_resources_available();
int has_finished(int* first);
int next_thread(int current_thread);

// Number of existent resources of each type
int resources_existent[TYPES_OF_RESOURCES] = { 10, 5, 7 };

// Number of available resources of each type
int resources_available[TYPES_OF_RESOURCES] = { 0, 0, 0 };

// Max demand of each thread for each resource
// Each line illustrates a thread
// Each column illustrates a type of resource
int max[NUM_OF_THREADS][TYPES_OF_RESOURCES] = {
    { 7, 5, 3 },
    { 3, 2, 2 },
    { 9, 0, 2 },
    { 2, 2, 2 },
    { 4, 3, 3 }
};

// Number of each type of resource currently allocated to each thread
/*
int allocated[NUM_OF_THREADS][TYPES_OF_RESOURCES] = {
    { 0, 0, 0 },
    { 0, 0, 0 },
    { 0, 0, 0 },
    { 0, 0, 0 },
    { 0, 0, 0 }
};
*/

int allocated[NUM_OF_THREADS][TYPES_OF_RESOURCES] = {
    { 0, 1, 0 },
    { 2, 0, 0 },
    { 3, 0, 2 },
    { 2, 1, 1 },
    { 0, 0, 2 }
};

int need[NUM_OF_THREADS][TYPES_OF_RESOURCES] = {
    { 0, 0, 0 },
    { 0, 0, 0 },
    { 0, 0, 0 },
    { 0, 0, 0 },
    { 0, 0, 0 }
};

int main() {
    populate_resources_available();
    populate_need();
    is_system_in_safe_state();
    return 0;
}

void populate_resources_available()
{
    for (int resource_num = 0; resource_num < TYPES_OF_RESOURCES; ++resource_num) {
        int occupied = 0;
        for (int thread_num = 0; thread_num < NUM_OF_THREADS; ++thread_num) {
            occupied += allocated[thread_num][resource_num];
        }
        if (DEBUG > 1) printf("Resource number %d has %d and %d are occupied...\n", resource_num, resources_existent[resource_num], occupied);
        resources_available[resource_num] = resources_existent[resource_num] - occupied;
    }
    if (DEBUG) traverse_array(TYPES_OF_RESOURCES, &resources_available[0], "Resources available");
}

void populate_need()
{
    for (int thread_num = 0; thread_num < NUM_OF_THREADS; ++thread_num) {
        for (int resource_num = 0; resource_num < TYPES_OF_RESOURCES; ++resource_num) {
            need[thread_num][resource_num] = max[thread_num][resource_num] - allocated[thread_num][resource_num];
        }
    }
}

// Returns 1 if it is in safe state, 0 otherwise
int is_system_in_safe_state()
{
    int work[TYPES_OF_RESOURCES];
    int finish[NUM_OF_THREADS];
    for (int resource_num = 0; resource_num < TYPES_OF_RESOURCES; ++resource_num) {
        work[resource_num] = resources_available[resource_num];
    }
    for (int thread_num = 0; thread_num < NUM_OF_THREADS; ++thread_num) {
        finish[thread_num] = 0;
    }
    int thread_num = 0;
    int is_safe = 0;
    while (!has_finished(&finish[0])) {
        if (finish[thread_num]) {
            thread_num = next_thread(thread_num);
            continue;
        }
        int passed = 1;
        if (DEBUG > 1) {
            printf("Current thread T%d = ",thread_num);
            traverse_array(TYPES_OF_RESOURCES, &need[thread_num][0], "");
        }
        for (int resource_num = 0; resource_num < TYPES_OF_RESOURCES; ++resource_num) {
            if (need[thread_num][resource_num] > work[resource_num]) {
                passed = 0;
                break;
            }
        }
        if (!passed) {
            thread_num = next_thread(thread_num); 
            continue; 
        }
        if (DEBUG) printf("Thread T%d has passed...\n", thread_num);
        finish[thread_num] = 1;
        for (int resource_num = 0; resource_num < TYPES_OF_RESOURCES; ++resource_num) {
            work[resource_num] += allocated[thread_num][resource_num];
        }
        if (DEBUG) traverse_array(TYPES_OF_RESOURCES, &work[0], "Resources available");
        thread_num = next_thread(thread_num);
    }
    return is_safe;
}

void traverse_array(int length, int* first, char* name)
{
    printf("Array: %s = ", name);
    for (int i = 0; i < length; ++i) {
        printf("%d ", *(first+i));
    }
    printf("\n");
}

int has_finished(int* first)
{
    int finished = 1;
    for (int thread_num = 0; thread_num < NUM_OF_THREADS; ++thread_num) {
        if (!*(first + thread_num)) {
            finished = 0;
            break;
        }
    }
    printf("Has finished ? %s...\n", finished ? "true" : "false");
    printf("-------------------------\n");
    return finished;
}

int next_thread(int current_thread)
{
    return current_thread == NUM_OF_THREADS - 1 ? 0 : current_thread + 1;
}