OS - Unit 3 Deadlock (Bankers Algorithm).pptx

Deadlock Prevention using Banker's Algorithm

1. Operating Systems

2. Unit 3 CPU Scheduling: Scheduling Concepts, Performance Criteria, Process States, Process Transition Diagram, Schedulers, Process Control Block (PCB), Process address space, Process identification information, Threads and their management, Scheduling Algorithms, Multiprocessor Scheduling. Deadlock: System model, Deadlock characterization, Prevention, Avoidance and detection, Recovery from deadlock.

3. Deadlock : System model Deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process. Consider an example when two trains are coming toward each other on the same track and there is only one track, none of the trains can move once they are in front of each other. Deadlock can arise if the following four conditions hold simultaneously (Necessary Conditions) Mutual Exclusion : Two or more resources are non-shareable (Only one process can use at a time) Hold and Wait : A process is holding at least one resource and waiting for resources. No Preemption : A resource cannot be taken from a process unless the process releases the resource. Circular Wait : A set of processes are waiting for each other in circular form.

4. Understanding Conditions for Deadlock Mutual Exclusion : When two people meet in the landings, they can’t just walk through because there is space only for one person. This condition allows only one person (or process) to use the step between them (or the resource) is the first condition necessary for the occurrence of the deadlock. Hold and Wait : When the two people refuse to retreat and hold their ground, it is called holding. This is the next necessary condition for deadlock. No Preemption : For resolving the deadlock one can simply cancel one of the processes for other to continue. But the Operating System doesn’t do so. It allocates the resources to the processors for as much time as is needed until the task is completed. Hence, there is no temporary reallocation of the resources. It is the third condition for deadlock. Circular Wait: When the two people refuse to retreat and wait for each other to retreat so that they can complete their task, it is called circular wait. It is the last condition for deadlock to occur.

5. Resource-Allocation Graph In RAG vertices are two type – 1. Process vertex – Every process will be represented as a process vertex. Generally, the process will be represented with a circle. 2. Resource vertex – Every resource will be represented as a resource vertex. It represents as a box, inside the box, there will be one dot. So the number of dots indicate how many instances are present of each resource type. A set of vertices V and a set of edges E. V is partitioned into two types: P = {P1, P2, …, Pn }, the set consisting of all the processes in the system R = {R1, R2, …, Rm}, the set consisting of all resource types in the system request edge – directed edge Pi  Rj assignment edge – directed edge Rj  Pi

6. Example of a Resource Allocation Graph With A Deadlock With A Cycle But No Deadlock If graph contains no cycles : no deadlock If graph contains a cycle : if only one instance per resource type, then deadlock if several instances per resource type, possibility of deadlock

7. Methods for Handling Deadlocks Two ways to ensure that the system will never enter a deadlock state: Deadlock prevention Deadlock avoidance System is in safe state if there exists a sequence <P 1 , P 2 , …, P n > of ALL the processes in the systems such that for each P i , the resources that P i can still request can be satisfied by currently available resources + resources held by all the P j , with j < I That is: If P i resource needs are not immediately available, then P i can wait until all P j have finished When P j is finished, P i can obtain needed resources, execute, return allocated resources, and terminate When P i terminates, P i +1 can obtain its needed resources, and so on

8. Deadlock avoidance Single instance of a resource type Use a resource-allocation graph Multiple instances of a resource type Use the banker’s algorithm

9. Banker’s Algorithm The banker’s algorithm is a resource allocation and deadlock avoidance algorithm that tests for safety by simulating the allocation for predetermined maximum possible amounts of all resources, then makes an “s-state” check to test for possible activities, before deciding whether allocation should be allowed to continue. Let n = number of processes, and m = number of resources types. Available : Vector of length m. If available [j] = k, there are k instances of resource type Rj available Max : n x m matrix. If Max [ i,j ] = k, then process Pi may request at most k instances of resource type Rj Allocation : n x m matrix. If Allocation[ i,j ] = k then Pi is currently allocated k instances of Rj Need: n x m matrix. If Need[ i,j ] = k, then Pi may need k more instances of Rj to complete its task Need [ i,j ] = Max[ i,j ] – Allocation [ i,j ]

10. Banker’s Algorithm Banker’s algorithm consists of Safety algorithm and Resource request algorithm Safety Algorithm : The algorithm for finding out whether or not a system is in a safe state can be described as follows: Let Work and Finish be vectors of length ‘m’ and ‘n’ respectively. Initialize: Work = Available Finish[ i ] = false; for i =1, 2, 3, 4….n 2) Find an i such that both a) Finish[ i ] = false b) Needi <= Work if no such i exists goto step (4) 3) Work = Work + Allocation[ i ] Finish[ i ] = true goto step (2) 4) if Finish [ i ] = true for all i then the system is in a safe state Resource-Request Algorithm : Let Request i be the request array for process P i . Requesti [j] = k means process P i wants k instances of resource type R j . When a request for resources is made by process P i , the following actions are taken: 1) If Request i <= Need i Goto step (2) ; otherwise, raise an error condition, since the process has exceeded its maximum claim. 2) If Request i <= Available Goto step (3); otherwise, Pi must wait, since the resources are not available. 3) Have the system pretend to have allocated the requested resources to process Pi by modifying the state as follows: Available = Available – Request i Allocation i = Allocation i + Request i Need i = Need i – Request i

11. Bankers Algorithm Example 1 Consider the following snapshot of a system- Answer the following questions using the Banker’s algorithm- ( i ) What is the content of the matrix need? (ii) Is the system in a safe state? (iii) If a request from process P1 arrives for (0,4,2,0), can the request be granted immediately?

12. Bankers Algorithm Example Process Allocation Max Available Need A B C D A B C D A B C D A B C D P0 1 2 1 2 1 5 2 P1 1 1 7 5 1 5 3 2 7 5 P2 1 3 5 4 2 3 5 6 1 5 3 2 1 2 P3 6 3 2 6 5 2 2 8 8 6 2 P4 1 4 6 5 6 2 14 11 8 6 4 2 P1 1 1 7 5 2 14 12 12 7 5 Step 1-Need =Max-Allocation, make a matrix of need column.(Written in green below) Step 2-Check Need <= Available (check individual variables of both corresponding columns). If available < need then write same available as in last row. For example for P1- Need B(7)> Available B(5) (See in red) and so system is not in safe state. If Available > Need then write next Process availability as: Available= Available + Allocation (written in yellow) So safe sequence is (P0,P2,P3,P4,P0)

13. Bankers Algorithm Example 1 Step3 : To Check if a request from process P1 arrives for (0,4,2,0), can the request be granted immediately Compare Given Allocation with Corresponding Need: For P1 (0,4,2,0)< (0,7,5,0) Compare Given Allocation with Corresponding Available: For P1 (0,4,2,0) <(1,5,2,0) So new Available= (1,5,2,0)-(0,4,2,0)=(1,1,0,0) And so new Allocation= (1,0,0,0)+(0,4,2,0)=(1,4,2,0) And so new need for P1=(0,7,5,0) – (0,4,2,0) =(0,3,3,0) Now replace the previous values of process P1 with new values: Process Allocation Max Available Need A B C D A B C D A B C D A B C D P0 1 2 1 2 1 1 P1 1 4 2 1 7 5 3 3 P2 1 3 5 4 2 3 5 6 1 2 P3 6 3 2 6 5 2 2 P4 1 4 6 5 6 6 4 2 Step 4: Now repeat Step1 t- Step 2 and find safe sequence.

14. Bankers Algorithm Example 2 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: Solution: Available instances of A = Total – Allocated = 10 – (0+2+3+2+0) = 3 Similarly, Available instances of B = Total – Allocated = 5 – (1+0+0+1+0) = 3 Finally, Available instances 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

15. Bankers Algorithm Example 2 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.

16. Bankers Algorithm Example 3 Considering a system with five processes P0 through P4 and three resources of type A, B, C. Resource type A has 10 instances, B has 5 instances and type C has 7 instances. Suppose at time t0 following snapshot of the system has been taken: What will be the content of the Need matrix? Need [ i , j] = Max [ i , j] – Allocation [ i , j]

17. Bankers Algorithm Example 3 Is the system in a safe state? If Yes, then what is the safe sequence?

18. Bankers Algorithm Example 3 What will happen if process P1 requests one additional instance of resource type A and two instances of resource type C?

19. Bankers Algorithm Example 3