Banker’s Algorithm in OS

Facebooktwitterredditpinterestlinkedinmailby feather

What is Banker’s Algorithm?

Bankers algorithm is an algorithm which is used for deadlock avoidance and resource allocation. It was established by Edsger Dijkstra. The reason behind the name ‘banker’s algorithm’ is that it is mostly used in banking systems. Banker’s algorithm helps to identify whether a loan should be provided or not.

Characteristics of Banker’s Algorithm

The characteristics of Banker’s algorithm are:

Disadvantages of Banker’s Algorithm

The disadvantages of banker’s algorithm are:

 Data Structures used to implement the Banker’s Algorithm

There are four types of data structures used to implement Banker’s algorithm:

Available

Max

Allocation

Need

[i, j]

= k indicates that for the execution of ‘Pi’ process, presently ‘k’ instances of resource type ‘Rj’ are required.

Banker’s algorithm comprises of two algorithms:

Safety algorithm

The safety algorithm is used to check the system state means whether the system is in a safe state or not.

The safety algorithm contains the following steps:

Banker’s Algorithm

Resource Request Algorithm

         Let Requesti is the request array for the process ‘Pi’. Requesti [j] = k means ‘Pi’ process needs k instances of Rj resource type. At the time   when a process Pi demands  resources, then we follow the below steps.

Banker’s Algorithm

Example of Banker’s Algorithm

Consider the following snapshot of a system:

Processes Allocation A   B    C       Max  A   B   C Available A   B   C
      P0 1     1     2  4    3    3   2    1    0
      P1 2     1     2  3    2    2  
      P2 4     0     1  9    0    2  
      P3 0     2     0  7    5    3  
      P4 1     1     2  1    1    2  

           Solution:

          1. Content of the need matrix can be calculated by using the below formula

                Need = Max – Allocation

 Process                   Need
      A      B    C
         P0       3        2     1
         P1       1        1     0
         P2       5        0               1
         P3       7                        3     3
         P4       0        0     0

⸫⸫

          2. Now, we check for a safe state

  Safe sequence:

                           Available = (2, 1, 0)

             Need ≤ Available = False

   So, the system will move for the next process.

                 Available = (2, 1, 0)

    Need ≤ Available = True

              Request of P1 is granted.

                ⸫                          Available = Available +Allocation

                                                             = (2, 1, 0) + (2, 1, 2)

                                                             = (4, 2, 2) (New Available)

                  Available = (4, 2, 2)

     Need ≤ Available = False

So, the system will move to the next process.

                 Available = (4, 2, 2)

          Need ≤ Available = False

So, the system will move to the next process.

                   Available = (4, 2, 2)

              Need ≤ Available = True

                Request of P4 is granted.

                ⸫                          Available = Available +Allocation

                                       = (4, 2, 2) + (1, 1, 2)

                                       = (5, 3, 4) now, (New Available)

                                              Available = (5, 3, 4)

                                                         Need ≤ Available = True

                Request of P2 is granted.

                ⸫                          Available = Available +Allocation

                                                                                                  = (5, 3, 4) + (4, 0, 1)

                                                             = (9, 3, 5) now, (New Available)

                                              Available = (9, 3, 5)

                                                                                         Need ≤ Available = True

                Request of P3 is granted.

                ⸫                          Available = Available +Allocation

                                                                                                    = (9, 3, 5) + (0, 2, 0) = (9, 5, 5)

                                                     = Available (9, 5, 5)

                        Need ≤ Available = True

               So, the request will be granted to P0.

            Safe sequence: < P1, P4, P2, P3, P0>

                     The system allocates all the needed resources to each process. So, we can say that system is in a safe state.

           3. The total amount of resources = sum of columns of allocation + Available

                                                             = [8 5 7] + [2 1 0] = [10 6 7]

Facebooktwitterredditpinterestlinkedinmailby feather