Bankers Algorithm in Operating System (OS)

What is Bankers Algorithm in Operating System?

Banker’s Algorithm is a resource allocation and deadlock avoidance algorithm. This name has been given since it is one of most problem in Banking Systems these days.

  • In this, as a new process P1 enters, it declares the maximum number of resource it needs.
    • The system looks at those and checks if allocating those resources to P1 will leave system in safe state or not.
    • If after allocation, it will be in safe state , the resources are allocated to process P1.
  • Otherwise, P1 should wait till other process release some resource.

This is the basic idea of Banker’s Algorithm.

A state is safe if the system can allocate all resources requested by all processes ( up to their stated maximums ) without entering a deadlock state.(MCQ Question in CoCubes)

Now, Let’s have a look at how these are implemented . They are implemented using 4 data structure.

Let n be the number of process in system.

Let m be no of resources in system.

  • Available
    • 1 D Array of Size m.
    • Each element Available[i] indicates the number of resources of i type available. Denoted by Ri
  • Maximum
    • 2 D Array of size n*m
    • Determines maximum demand of each process.
    • Maximum[i,j] tells the maximum demand an ith process will request of jth type resource.
  • Allocation
    • 2 D Array of size n*m
    • Defines number of resources of each type currently allocated to each process.
    • Allocation[i,j] means i th process has current k instance of j th type resource
  • Need
    • 2D Array of size n*m
    • Tells about remaining resources type which are required by each process.
    • Need[i,j] means i th process needs k instance of j th resource type.
    • Need[i,j] = Maximum[i,j] – Allocation[i,j]

The above data Structures Size and value vary over time. There are 2 Algorithm on which banker’s Algorithm is build upon

  • Safety Algorithm : It finds out whether system is in safe state or not.
  • Resource Request Algorithm : It finds out if request can be safely granted.

Safety Algorithm –

Time Complexity of Above Algorithm = O(m*n*n)

Resource Request Algorithm

  • Tells if Resource can be safely Granted.
  • Request i is Request for Process i.

After a process makes a request, The following steps are followed-

Please Login/Signup to comment