Practical- 12
Title: Implementation of Bankers algorithm for the purpose of deadlock avoidance.
—----------------------------------------------------------------------------------------------------------------------------
The Banker's Algorithm is used in operating systems to ensure safe allocation of resources and avoid deadlocks. It works by checking whether resource allocation will result in a safe state before actually granting the request. If the system is in a safe state after the allocation, the request is granted; otherwise, it is denied until it is safe to proceed.
Banker's Algorithm
Initialization:
Define Constants:
NUM_PROCESSES: Number of processes.
NUM_RESOURCES: Number of resource types.
Initialize Data Structures:
Available[]: Vector of available resources.
Maximum[][]: Matrix of maximum resource needs for each process.
Allocation[][]: Matrix of currently allocated resources for each process.
Need[][]: Matrix of remaining resource needs for each process, computed as Need[i][j] = Maximum[i][j] - Allocation[i][j].
Resource Request Algorithm:
Request by Process P for resources Request[]:
Check Request Validity:
Ensure Request[i] <= Need[P][i] for all resources i (request does not exceed maximum claim).
Ensure Request[i] <= Available[i] for all resources i (request does not exceed available resources).
Pretend Allocation:
Temporarily allocate resources:
Available[i] -= Request[i] for all i
Allocation[P][i] += Request[i] for all i
Need[P][i] -= Request[i] for all i
Check Safety:
Initialize:
Work[] = Available[] (Work vector starts with available resources).
Finish[] (Boolean vector to keep track of process completion status, initially all false).
Find Safe Sequence:
While there are unfinished processes:
Find a process i such that Finish[i] == false and Need[i][j] <= Work[j] for all j (process can complete with available resources).
If such a process is found:
Simulate the process completion:
Work[j] += Allocation[i][j] for all j (add resources back to Work vector).
Set Finish[i] = true.
If no such process is found, the system is not in a safe state.
Rollback if Unsafe:
If the system is not in a safe state:
Rollback the temporary allocation:
Available[i] += Request[i] for all i
Allocation[P][i] -= Request[i] for all i
Need[P][i] += Request[i] for all i
Deny the request until it can be safely granted.
Grant Request:
If the system is in a safe state after the allocation, grant the request.
Release Resources Algorithm:
Release Resources by Process P:
Return Allocated Resources:
Available[i] += Allocation[P][i] for all i
Need[P][i] += Allocation[P][i] for all i
Allocation[P][i] = 0 for all i (reset allocation).
Code :
#include <stdio.h>
#include <stdbool.h>
#define NUM_PROCESSES 5
#define NUM_RESOURCES 3
// Function prototypes
void initialize();
bool request_resources(int process_id, int request[]);
void release_resources(int process_id);
bool is_safe_state();
void print_matrices();
// Global variables
int available[NUM_RESOURCES];
int maximum[NUM_PROCESSES][NUM_RESOURCES];
int allocation[NUM_PROCESSES][NUM_RESOURCES];
int need[NUM_PROCESSES][NUM_RESOURCES];
int main() {
// Initialize data
initialize();
// Example of requesting resources
int request1[NUM_RESOURCES] = {1, 0, 2}; // Request by process 1
if (request_resources(1, request1)) {
printf("Request granted.\n");
} else {
printf("Request denied.\n");
}
// Print current state
print_matrices();
// Release resources by process 1
release_resources(1);
// Print current state
print_matrices();
return 0;
}
void initialize() {
// Initialize the available resources
available[0] = 10;
available[1] = 5;
available[2] = 7;
// Initialize the maximum demand of each process
maximum[0][0] = 7; maximum[0][1] = 5; maximum[0][2] = 3;
maximum[1][0] = 3; maximum[1][1] = 2; maximum[1][2] = 2;
maximum[2][0] = 9; maximum[2][1] = 0; maximum[2][2] = 2;
maximum[3][0] = 2; maximum[3][1] = 2; maximum[3][2] = 2;
maximum[4][0] = 4; maximum[4][1] = 3; maximum[4][2] = 3;
// Initialize the allocation of resources to each process
allocation[0][0] = 0; allocation[0][1] = 1; allocation[0][2] = 0;
allocation[1][0] = 2; allocation[1][1] = 0; allocation[1][2] = 0;
allocation[2][0] = 3; allocation[2][1] = 0; allocation[2][2] = 2;
allocation[3][0] = 2; allocation[3][1] = 1; allocation[3][2] = 1;
allocation[4][0] = 0; allocation[4][1] = 0; allocation[4][2] = 2;
// Calculate the need matrix
for (int i = 0; i < NUM_PROCESSES; i++) {
for (int j = 0; j < NUM_RESOURCES; j++) {
need[i][j] = maximum[i][j] - allocation[i][j];
}
}
}
bool request_resources(int process_id, int request[]) {
// Check if request is less than need
for (int i = 0; i < NUM_RESOURCES; i++) {
if (request[i] > need[process_id][i]) {
printf("Error: Process has exceeded its maximum claim.\n");
return false;
}
}
// Check if request is less than available
for (int i = 0; i < NUM_RESOURCES; i++) {
if (request[i] > available[i]) {
printf("Resources not available.\n");
return false;
}
}
// Pretend to allocate requested resources
for (int i = 0; i < NUM_RESOURCES; i++) {
available[i] -= request[i];
allocation[process_id][i] += request[i];
need[process_id][i] -= request[i];
}
// Check system state
if (is_safe_state()) {
return true;
} else {
// Rollback allocation
for (int i = 0; i < NUM_RESOURCES; i++) {
available[i] += request[i];
allocation[process_id][i] -= request[i];
need[process_id][i] += request[i];
}
return false;
}
}
void release_resources(int process_id) {
for (int i = 0; i < NUM_RESOURCES; i++) {
available[i] += allocation[process_id][i];
need[process_id][i] += allocation[process_id][i];
allocation[process_id][i] = 0;
}
}
bool is_safe_state() {
int work[NUM_RESOURCES];
bool finish[NUM_PROCESSES] = { false };
// Initialize work with available resources
for (int i = 0; i < NUM_RESOURCES; i++) {
work[i] = available[i];
}
// Find a safe sequence
while (true) {
bool progress = false;
for (int i = 0; i < NUM_PROCESSES; i++) {
if (!finish[i]) {
// Check if process can be satisfied with work + allocation
bool can_satisfy = true;
for (int j = 0; j < NUM_RESOURCES; j++) {
if (need[i][j] > work[j]) {
can_satisfy = false;
break;
}
}
if (can_satisfy) {
// Simulate the process finishing
for (int j = 0; j < NUM_RESOURCES; j++) {
work[j] += allocation[i][j];
}
finish[i] = true;
progress = true;
}
}
}
if (!progress) {
break;
}
}
// Check if all processes are finished
for (int i = 0; i < NUM_PROCESSES; i++) {
if (!finish[i]) {
return false;
}
}
return true;
}
void print_matrices() {
printf("\nAvailable Resources:\n");
for (int i = 0; i < NUM_RESOURCES; i++) {
printf("%d ", available[i]);
}
printf("\n");
printf("Maximum Demand Matrix:\n");
for (int i = 0; i < NUM_PROCESSES; i++) {
for (int j = 0; j < NUM_RESOURCES; j++) {
printf("%d ", maximum[i][j]);
}
printf("\n");
}
printf("Allocation Matrix:\n");
for (int i = 0; i < NUM_PROCESSES; i++) {
for (int j = 0; j < NUM_RESOURCES; j++) {
printf("%d ", allocation[i][j]);
}
printf("\n");
}
printf("Need Matrix:\n");
for (int i = 0; i < NUM_PROCESSES; i++) {
for (int j = 0; j < NUM_RESOURCES; j++) {
printf("%d ", need[i][j]);
}
printf("\n");
}
}
No comments:
Post a Comment