Created
October 2, 2019 00:37
-
-
Save victoroliveirab/ba16a8638be02c3a55f46495a5cd836a to your computer and use it in GitHub Desktop.
Banker's Algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment