C Program to Implement Bankers Algorithm [System Programming]

This is the C Programming Implementation of bankers algorithm

The Banker’s algorithm is a resource allocation and deadlock avoidance algorithm developed by Edsger Dijkstra that tests for safety by simulating the allocation of predetermined maximum possible amounts of all resources, and then makes an “s-state” check to test for possible deadlock conditions for all other pending activities, before deciding whether allocation should be allowed to continue.

The algorithm was developed in the design process for the THE operating system and originally described (in Dutch) in EWD108. When a new process enters a system, it must declare the maximum number of instances of each resource type that it may ever claim; clearly, that number may not exceed the total number of resources in the system. Also, when a process gets all its requested resources it must return them in a finite amount of time.

Resources

For the Banker’s algorithm to work, it needs to know three things:

How much of each resource each process could possibly request[MAX]
How much of each resource each process is currently holding[ALLOCATED]
How much of each resource the system currently has available[AVAILABLE]

Resources may be allocated to a process only if it satisfies the following conditions:

request ≤ max, else set error condition as process has crossed maximum claim made by it.
request ≤ available, else process waits until resources are available.

Some of the resources that are tracked in real systems are memory, semaphores and interface access.

The Banker’s Algorithm derives its name from the fact that this algorithm could be used in a banking system to ensure that the bank does not run out of resources, because the bank would never allocate its money in such a way that it can no longer satisfy the needs of all its customers. By using the Banker’s algorithm, the bank ensures that when customers request money the bank never leaves a safe state. If the customer’s request does not cause the bank to leave a safe state, the cash will be allocated, otherwise the customer must wait until some other customer deposits enough.

Basic data structures to be maintained to implement the Banker’s Algorithm:

Let n be the number of processes in the system and m be the number of resource types. Then we need the following data structures:

Available: A vector of length m indicates the number of available resources of each type. If Available[j] = k, there are k instances of resource type Rj available.
Max: An n×m matrix defines the maximum demand of each process. If Max[i,j] = k, then Pi may request at most k instances of resource type Rj.
Allocation: An n×m matrix defines the number of resources of each type currently allocated to each process. If Allocation[i,j] = k, then process Pi is currently allocated k instances of resource type Rj.
Need: An n×m matrix indicates the remaining resource need of each process. If Need[i,j] = k, then Pi may need k more instances of resource type Rj to complete the task.

Note: Need[i,j] = Max[i,j] – Allocation[i,j].

Safe and Unsafe States

A state (as in the above example) is considered safe if it is possible for all processes to finish executing (terminate). Since the system cannot know when a process will terminate, or how many resources it will have requested by then, the system assumes that all processes will eventually attempt to acquire their stated maximum resources and terminate soon afterward. This is a reasonable assumption in most cases since the system is not particularly concerned with how long each process runs (at least not from a deadlock avoidance perspective). Also, if a process terminates without acquiring its maximum resources, it only makes it easier on the system. A safe state is considered to be the decision maker if it is going to process ready queue. Safe State ensures the Security.

Given that assumption, the algorithm determines if a state is safe by trying to find a hypothetical set of requests by the processes that would allow each to acquire its maximum resources and then terminate (returning its resources to the system). Any state where no such set exists is an unsafe state.

#include <stdio.h>
int curr[5][5], maxclaim[5][5], avl[5];
int alloc[5] = {0, 0, 0, 0, 0};
int maxres[5], running[5], safe=0;
int count = 0, i, j, exec, r, p, k = 1;
 
int main()
{
    printf("nEnter the number of processes: ");
    scanf("%d", &p);
 
    for (i = 0; i < p; i++) {
        running[i] = 1;
        count++;
    }
 
    printf("nEnter the number of resources: ");
    scanf("%d", &r);
 
    for (i = 0; i < r; i++) { 
        printf("nEnter the resource for instance %d: ", k++);
        scanf("%d", &maxres[i]);
    }
 
    printf("nEnter maximum resource table:n");
    for (i = 0; i < p; i++) {
        for(j = 0; j < r; j++) {
            scanf("%d", &maxclaim[i][j]);
        }
    }
 
    printf("nEnter allocated resource table:n");
    for (i = 0; i < p; i++) {
        for(j = 0; j < r; j++) {
            scanf("%d", &curr[i][j]);
        }
    }
 
    printf("nThe resource of instances: ");
    for (i = 0; i < r; i++) {
        printf("t%d", maxres[i]);
    }
 
    printf("nThe allocated resource table:n");
    for (i = 0; i < p; i++) {
        for (j = 0; j < r; j++) {
            printf("t%d", curr[i][j]);
        }
 
        printf("n");
    }
 
    printf("nThe maximum resource table:n");
    for (i = 0; i < p; i++) {
        for (j = 0; j < r; j++) {
            printf("t%d", maxclaim[i][j]);
        }
 
        printf("n");
    }
 
    for (i = 0; i < p; i++) {
        for (j = 0; j < r; j++) {
            alloc[j] += curr[i][j];
        }
    }
 
    printf("nAllocated resources:");
    for (i = 0; i < r; i++) {
        printf("t%d", alloc[i]);
    }
 
    for (i = 0; i < r; i++) {
        avl[i] = maxres[i] - alloc[i];
    }
 
    printf("nAvailable resources:");
    for (i = 0; i < r; i++) {
        printf("t%d", avl[i]);
    }
    printf("n");
 
    //Main procedure goes below to check for unsafe state.
    while (count != 0) {
        safe = 0;
        for (i = 0; i < p; i++) {
            if (running[i]) {
                exec = 1;
                for (j = 0; j < r; j++) {
                    if (maxclaim[i][j] - curr[i][j] > avl[j]) {
                        exec = 0;
                        break;
                    }
                }
                if (exec) {
                    printf("nProcess%d is executingn", i + 1);
                    running[i] = 0;
                    count--;
                    safe = 1;
 
                    for (j = 0; j < r; j++) {
                        avl[j] += curr[i][j];
                    }
 
                    break;
                }
            }
        }
        if (!safe) {
            printf("nThe processes are in unsafe state.n");
            break;
        } else {
            printf("nThe process is in safe state");
            printf("nSafe sequence is:");
 
            for (i = 0; i < r; i++) {
                printf("t%d", avl[i]);
            }
 
            printf("n");
        }
    }
}

OUTPUT:
Enter the number of resources:4

Enter the number of processes:5

Enter Claim Vector:8 5 9 7

Enter Allocated Resource Table:
2 0 1 1
0 1 2 1
4 0 0 3
0 2 1 0
1 0 3 0

Enter Maximum Claim table:
3 2 1 4
0 2 5 2
5 1 0 5
1 5 3 0
3 0 3 3

The Claim Vector is: 8 5 9 7
The Allocated Resource Table:
2 0 1 1
0 1 2 1
4 0 0 3
0 2 1 0
1 0 3 0

The Maximum Claim Table:
3 2 1 4
0 2 5 2
5 1 0 5
1 5 3 0
3 0 3 3

Allocated resources: 7 3 7 5
Available resources: 1 2 2 2

Process3 is executing

The process is in safe state
Available vector: 5 2 2 5
Process1 is executing

The process is in safe state
Available vector: 7 2 3 6
Process2 is executing

The process is in safe state
Available vector: 7 3 5 7
Process4 is executing

The process is in safe state
Available vector: 7 5 6 7
Process5 is executing

The process is in safe state
Available vector: 8 5 9 7

Courtesy: http://www.wikipedia.com