Bankers Algorithm in Operating System (OS)

Bankers Algorithm in OS

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.

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-