Question-1 Explain the use of Banker’s Algorithm for Deadlock Avoidance with illustration.
Deadlock avoidance and bankers algorithm for deadlock avoidance
- 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 right choice all the time.
Banker’s algorithm for single resource
- 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. below 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.
- The customers go about their respective businesses, making loan requests from time to time (i.e. asking for resources).
- First if we have situation as per fig below (a) then it is safe state because with 10 free units one by one all customers can be served.
- Second situation is as shown in fig. below (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. below (c) then it becomes unsafe state.
- In this situation we have only one free unit and minimum 2 units are required by C. No one can get all resources to complete their work so it is unsafe state.
Banker’s algorithm for multiple resource
- The banker’s algorithm can be generalized to handle multiple resources.
- In fig. below 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 resource each process still needs in order to complete the operation.
- These matrices are labeled as C and R respectively.
- The three vectors at the right of the figure show the existing (total) resources E, the hold 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
- 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).
- 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.
- Repeat step 1 and 2 until either all processes are marked terminated (in which case the initial state was safe) or no process is left whose resources 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 figure above. 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 request for 1 printer and 1 CD ROM then there is deadlock.