Banker’s Algorithm – is a technique used for deadlock avoidance when there are multiple instances of a resource.
This algorithm requires four data structures to be implemented:
Request = request vector for process Pi. If Requesti [j] = k then
process Pi wants k instances of resource type Rj.
Note: Clicking on the “next” slide button will not display any animation. Hence, Click within the slide area for animations.
Q. Consider a system with five processes Po through P4 and three resource types A, B, and C. Resource type A has 10 instances, resource type B has 5 instances, and resource type C has 7 instances. Suppose that, at time T0 , the following snapshot of the system has been taken:
Available instaces of A = Total – Allocated = 10 – (0+2+3+2+0) = 3
Similarly, Available instaces of B = Total – Allocated = 5 – (1+0+0+1+0) = 3
Finally, Available instaces of C = Total – Allocated = 7 – (0+0+2+1+2) = 2
Next, Calculate Need by using the formula
Need = Max – Allocation
………………………A B C
Need for P0 = 7 4 3
Hence, the entire scenario looks like
Now find out any process whose Need can be satisfied with Available. P1 is one such process. So, Add P1 to safe sequence <P1>.
Update the Available by using formula
Available = Available + Allocation of process added to safe sequence (P1)
So, new Available is 5 3 2
Next, find out another process whose Need is less than the updated Available i.e., 5 3 2.
P3 is one such process. Hence, Add P3 to safe sequence <P1, P3>.
Now, Update Available by adding Allocation of P3 to current Available.
Proceed in the same manner. If all the process can be added to the safe sequence then the system is in safe state otherwise not.
Q1. Consider a system with four processes Po through P3 and four resource types A, B, C and D. Resource type A has 6 instances, resource type B has 9 instances, resource type C has 6 instances, and D has 9 instances. Suppose that, at time T0 , the following snapshot of the system has been taken:
Is the system in safe state or not?
Can a request of P3 for <1,1,1,1> be granted?
Galvin, P. B., Gagne, G., & Silberschatz, A. Operating system concepts. John Wiley & Sons, 8th Edition
Previous Next Resource Allocation Graph Deadlock Detection and Recovery