Banker's algorithm

Banker's algorithm

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

For the Banker's algorithm to work, we need 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]
Implementation :Let ‘n’ be the number of processes in the system and ‘m’ be the number of resources types.
Available : 

• It is a 1-d array of size ‘m’ indicating the number of available resources of each type.
• Available[ j ] = k means there are ‘k’ instances of resource type R_j
  

Max :

• It is a 2-d array of size ‘n*m’ that defines the maximum demand of each process in a system.
• Max[ i, j ] = k means process P_i may request at most ‘k’ instances of resource type R_j.
  

Allocation :

• It is a 2-d array of size ‘n*m’ that defines the number of resources of each type currently allocated to each process.
• Allocation[ i, j ] = k means process P_i is currently allocated ‘k’ instances of resource type R_j
  

Need :

•  It is a 2-d array of size ‘n*m’ that indicates the remaining resource need of each process.
• Need [ i,  j ] = k means process P_i currently need ‘k’ instances of resource type R_j
  for its execution.
  
• Need [ i,  j ] = Max [ i,  j ] – Allocation [ i,  j ]
  

Note:

Allocation_i specifies the resources currently allocated to process P_i a
Need_i specifies the additional resources that process P_i may still request to complete its task.
Banker’s algorithm consist of Safety algorithm and Resource request algorithm


Safety Algorithm
The algorithm for finding out whether or not a system is in a safe state can be described as follows:

1) Let Work and Finish be vectors of length ‘m’ and ‘n’ respectively.
Initialize: Work = Available
Finish[i] = false; for i=1, 2, 3, 4….n

2) Find an i such that both
a) Finish[i] = false
b) Need_i <= Work
if no such i exists goto step (4)

3) Work = Work + Allocation[i]
Finish[i] = true
goto step (2)

4) if Finish [i] = true for all i
then the system is in a safe state

Resource-Request Algorithm
Let Request_i be the request array for process P_i. Request_i [j] = k means process P_i wants k instances of resource type R_j. When a request for resources is made by process P_i, the following actions are taken

1) If Request_i <= Need_i
Goto step (2) ; otherwise, raise an error condition, since the process has exceeded its maximum claim.

2) If Request_i <= Available
Goto step (3); otherwise, P_i must wait, since the resources are not available.

3) Have the system pretend to have allocated the requested resources to process Pi by modifying the state as
follows:
Available = Available – Requesti
Allocation_i = Allocation_i + Request_i
Need_i = Need_i– Request_i

Program on Bankers algorithm
#include <stdio.h>
#include <stdlib.h>
void main()
{
    int Max[10][10], need[10][10], alloc[10][10];
    int avail[10], completed[10], safeSequence[10];
    int p, r, i, j, process, count=0;
    printf("\nEnter the no of processes : ");
    scanf("%d", &p);
    for(i = 0; i< p; i++)
    completed[i] = 0;
    printf("\nEnter the no of resources : ");
    scanf("%d", &r);
    printf("\nEnter the Max Matrix for each process : ");
    for(i = 0; i < p; i++)
    {
    printf("\nFor process %d : ", i + 1);
    for(j = 0; j < r; j++)
        scanf("%d", &Max[i][j]);
    }
    printf("\nEnter the allocation for each process : ");
    for(i = 0; i < p; i++)
    {
    printf("\nFor process %d : ",i + 1);
    for(j = 0; j < r; j++)
        scanf("%d", &alloc[i][j]);
    }
    printf("\nEnter the Available Resources : ");
    for(i = 0; i < r; i++)
    scanf("%d", &avail[i]);
    for(i = 0; i < p; i++)
    {
      for(j = 0; j < r; j++)
       {
        need[i][j] = Max[i][j] - alloc[i][j];
       }
    }
    do
    {
        printf("\n Max matrix:\tAllocation matrix:\n");
        for(i = 0; i < p; i++)
        {
        for( j = 0; j < r; j++)
            printf("%d ", Max[i][j]);
        printf("\t\t");
        for( j = 0; j < r; j++)
            printf("%d ", alloc[i][j]);
        printf("\n");
        }
        process = -1;
        for(i = 0; i < p; i++)
        {
        if(completed[i] == 0)//if not completed
        {
            process = i ;
            for(j = 0; j < r; j++)
            {
            if(avail[j] < need[i][j])
            {
                process = -1;
                break;
            }
            }
        }
        if(process != -1)
            break;
        }

       if(process != -1)
         {
              printf("\nProcess %d runs to completion!", process + 1);
        safeSequence[count] = process + 1;
        count++;
        for(j = 0; j < r; j++)
        {
            avail[j] += alloc[process][j];
            alloc[process][j] = 0;
            Max[process][j] = 0;
            completed[process] = 1;
        }
        }
    }while(count != p && process != -1);

    if(count == p)
    {
        printf("\nThe system is in a safe state!!\n");
        printf("Safe Sequence : < ");
        for( i = 0; i < p; i++)
        printf("%d ", safeSequence[i]);
        printf(">\n");
    }
    else
        printf("\nThe system is in an unsafe state!!");
}


Single Resource Output:

Multiple Resource Output: