Banker Algorithm

                              Banker Algorithm

The resource-allocation graph algorithm is suitable to a resource allocation system with single instances of each resource type. It is not suitable for multiple instance of each resource type. Banker’s algorithm is suitable to a resource allocation system with multiple instances of each resource type. The banker’s algorithm makes decisions on granting a resource based on whether or not granting the request will put the system into an unsafe state. Several data structures must be maintained to implement the banker’s algorithm. Let n be the number processes in the system and m be the number of resource types. We need the following data structures:
(1) Available (2) Max (3) Allocation (4) Need
1) 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 R available.
2)    Max: An n x m matrix defines the maximum demand of each process. If Max [i, j] = k, then process P. may request at most k instances of resource type R_r3)   Allocation: An n x m matrix defines the number of resources of each type currently allocated to each process. If allocation [i, j] = k, then P. is currently allocated k instances of resource type R
4)  Need: An n x m matrix indicates the remaining resource need of each process. If Need |i, j] = k, then process P. may need k more instances of resource type R, to complete its task. Need [i, j] – Allocation [i, j].
Safety algorithm: Safety algorithm is used to find the state of the system: That is, system may be safe state or unsafe state. Method for this is as follows:
1)   Let work and finish be vector of length m and n respectively. Initialize work = Available and Finish [i] = False for i = 1, 2, 3, 4, … n.
2)   Find an i such that both
a) Finish [i] = False b) Need fj] < work
If no such i exist, go to step 4.
3)    Work : = Work + Allocation i
Finish [i] = true to step 2
4)    If Finish [i] = true for all i, then the system is in a safe state. Resource-request algorithm: Let request, be the request vector for process P. If Request, fj] = k, then process P. wants k instances of resource type R.. When a request for resources is made by process P, the following actions are taken.
1)     If Request. < Need₍, then go to step 2. Otherwise, raise an eitor condition since the process has exceeded its maximum claim.
2)    If Request < Available, then go to step 3. Otherwise, P. must wait since the resources are not available.
3)        Available : = Available – Request.; Allocation : = Allocation + Request.; Need_; : = Need_t – Request.;
If the resulting resource allocation stale is safe, the transaction is completed and process P. is allocated its resources. If the new state is unsafe, then P. must wait to the Request, and the old resource allocation state is restored.

Coding

#include<stdio.h>
#include<stdlib.h>
struct bank
{
 int alloc[10];
 int max[10];
 int need[10];
 int c;
 }p[10];

 int av[10];
 int m,n;
 char res[5]={'D','E','B','A','S'};
 int safe[20];
 int grant[10];
 int g=0;


void read()
{
 printf("\nEnter the number of processes--");
 scanf("%d",&n);
 int i,j;
 printf("\nEnter the number of resorces--");
 scanf("%d",&m);
 for(i=0;i<n;i++)
 {
   p[i].c=0;
   printf("\n\nEnter the details of the process %d--\n",i+1);
   for(j=0;j<m;j++)
    {
      printf("\nEnter the instances of %c allocated--",res[j]);
      scanf("%d",&p[i].alloc[j]);
    }
   for(j=0;j<m;j++)
    {
      printf("\nEnter the instances of %c maximum",res[j]);
      scanf("%d",&p[i].max[j]);
      p[i].need[j]=p[i].max[j]-p[i].alloc[j];
    }

 }


 printf("\nEnter the total instances of available resources--\n");
 for(i=0;i<m;i++)
 {
 printf("%c\t",res[i]);
 scanf("%d",&av[i]);
 }
}


void display()
{
 int i,j;
 printf(" \t Alloc \t Max \t Need \t Avail \n");
 printf(" \t ");
 for(j=0;j<4;j++,printf("\t "))
 for(i=0;i<m;i++)
 printf("%c",res[j]);
 printf("\n");
 for(i=0;i<n;i++)
 {
   printf("P%d\t",i);
   for(j=0;j<m;j++)
   printf("%d",p[i].alloc[j]);
   printf("\t");
   for(j=0;j<m;j++)
   printf("%d",p[i].max[j]);
   printf("\t");
   //printf("dev test 1");
   for(j=0;j<m;j++)
   printf("%d",p[i].need[j]);
   printf("\t");
   if(i==0)
   {
   for(j=0;j<m;j++)
   printf("%d\t",av[j]);
   }
   printf("\n");
   }
   }


int over()
{
  int i,j;
  for(i=0;i<n;i++)
  for(j=0;j<m;j++)
  if(p[i].need[j]!=0)
  return 1;
  return 0;
  }
void banker()
{
  int i,j,k,l;
  for(i=0,l=0;;i++,l++,i=i%n)
  {
   if(over()==0)
    {
     printf("\nAll processes complete\n\nNo Deadlock");
     printf("\n\nSafe state<");
     for(i=0;i<g;i++)
     printf("P%d",safe[i]);
     printf(">");
     break;
  }
  //printf("debasis");
  else
  {
    if(p[i].c==0)
    {
      for(j=0;j<m;j++)
      if(p[i].need[j]>av[j])
      break;
      if(j==m)
      {
        safe[g]=i;
        g++;
        p[i].c=1;
        for(j=0;j<m;j++)
         {
           av[j]=av[j]-p[i].need[j];
           p[i].need[j]=0;
           p[i].alloc[j]=p[i].max[j];
         }
        printf("\n\nProcess P%d is executing---\n\n",i);
        display();
        for(j=0;j<m;j++)
        {
         av[j]=av[j]+p[i].alloc[j];
         p[i].alloc[j]=0;
         p[i].max[j]=0;
        }
        printf("\n\nProcess P%d is completed---\n\n",i);
        display();
        }
 }
 }
 if(l==25)
 {
  printf("---Deadlock---");
  break;
  }
  }
  }


void req()
{
  int i,j,k=0;
  printf("\nEnter the process number--");
  scanf("%d",&i);
  for(j=0;j<m;j++)
  {
   printf("\nEnter the number of instances of resource %c--",res[j]);
   scanf("%d",&grant[j]);
  }
 for(j=0;j<m;j++)
 if(p[i].need[j]<grant[j])
 k=1;
 for(j=0;j<m;j++)
 if(av[j]<grant[j])
 k=2;
 if(k==1)
 {
  printf("Need is less than request cannt be allocated--");
  }
 if(k==2)
 {
  printf("Available is less than reuest cannot be allocated");
 }
 if(k==0)
 {
  for(j=0;j<m;j++)
  {
   p[i].alloc[j]+=grant[j];
   p[i].need[j]-=grant[j];
   av[j]-=grant[j];
   }
   }
   banker();
 }

  main()
  {
   int ch;
   do
   {
    printf("\n\nDEVS TEST BANKERS ALGORITHM");
    printf("\n1.Read devs input data file \n2.Display devs Input data file\n3.Generate devs Safe sequence\n4.Request for resource\n5.Exit\nEnter you choice dev :-)");
    scanf("%d",&ch);
    switch(ch)
    {
     case 1:read();break;
     case 2:display();break;
     case 3:banker();break;
     case 4:req();break;
     case 5:break;
    }
  }while(ch!=5);
 }