Understanding the Banker’s Algorithm for Deadlock Avoidance

Posted on Dec 7, 2024 in Computers

  • Explain the use of Banker’s Algorithm for Deadlock Avoidance with Illustration.

Deadlock Avoidance and Banker’s Algorithm Deadlock can be avoided by allocating resources carefully.

  • Carefully analyze each resource request to see if it can be safely granted.
      • Need an algorithm that can always avoid deadlock by making the right choice all the time.

Banker’s Algorithm for Single Resource Deadlock

  • A scheduling algorithm that can avoid deadlocks is due to Dijkstra (1965); it is known as the Banker’s Algorithm and is an extension of the deadlock detection algorithm.
      • It is modeled on the way a small-town banker might deal with a group of customers to whom he has granted lines of credit.
      • What the algorithm does is check to see if granting the request leads to an unsafe state. If it does, the request is denied.
      • If granting the request leads to a safe state, it is carried out.
      • In Fig. 4-8, we see four customers, A, B, C, and D, each of whom has been granted a certain number of credit units.
      • The banker knows that not all customers will need their maximum credit at a time, so he has reserved only 10 units rather than 22 to service them.

Z

Figure 4-8. Three Resource Allocation States: (a) Safe. (b) Safe. (c) Unsafe.

  • The customers go about their respective businesses, making loan requests from time to time (i.e., asking for resources).
      • First, if we have a situation as per Fig. 4-8 (a), then it is a safe state because with 10 free units, one by one, all customers can be served.
      • The second situation is as shown in Fig. 4-8 (b). This state is safe because with two units left (free units), the banker can allocate units to C, thus letting C finish and release all four of his resources.
      • With those four free units, the banker can let either D or B have the necessary units.

And so on.

  • Consider the third situation: what would happen if a request from B for one more unit were granted as shown in Fig. 4-8 (c)? Then it becomes an unsafe state.
      • In this situation, we have only one free unit and a minimum of 2 units are required by C. No one can get all resources to complete their work, so it is an unsafe state.

Banker’s Algorithm for Multiple Resources

  • The Banker’s Algorithm can be generalized to handle multiple resources.
      • In Fig. 4-9, we see two matrices. The one on the left shows how many of each resource are currently assigned to each of the five processes.
      • The matrix on the right shows how many resources each process still needs in order to complete the operation.
      • These matrices are labeled as C and R, respectively.

2Q==

Figure 4-9. The Banker’s Algorithm with Multiple Resources.

  • The three vectors at the right of the figure show the existing (total) resources E, the held resources P, and the available resources A, respectively.
      • From E, we see that the system has six tape drives, three plotters, four printers, and two CD ROM drives. Of these, five tape drives, three plotters, two printers, and two CD ROM drives are currently assigned.
      • This fact can be seen by adding up the four resource columns in the left-hand matrix.
      • The available resource vector is simply the difference between what the system has and what is currently in use, i.e., A = E – P.
      • The algorithm for checking to see if a state is safe can now be stated.
          1. Look for each row in R, whose unmet resource needs are all smaller than or equal to A. If no such row exists, the system will eventually deadlock since no process can run to completion (assuming processes keep all resources until they exit).
          2. Assume the process of the row chosen requests all the resources it needs (which is guaranteed to be possible) and finishes. Mark that process as terminated and add all its resources to the vector A.
          3. Repeat steps 1 and 2 until either all processes are marked terminated (in which case the initial state was safe) or no process is left whose resource needs can be met (in which case there is a deadlock).
      • If several processes are eligible to be chosen in step 1, it does not matter which one is selected: the pool of available resources either gets larger or, at worst, stays the same.
      • Now let us get back to the example of Fig. 4-9. The current state is safe. Suppose that process B now makes a request for the printer. This request can be granted because the resulting state is still safe (process D can finish, and then processes A or E, followed by the rest).
      • Now imagine that if process D requests 1 printer and 1 CD ROM, then there is a deadlock.