Methods for handling deadlock

Methods for hand ling deadlock: prevention,avoidance and detection

1. Unit 4 : Deadlocks Prepared By: Mr. Sangram A. Patil Assistant Professor PVPIT,Budhgaon

2. Methods for handling deadlocks We can deal with deadlock in one of three ways we can use protocol to prevent or avoid deadlock, ensure that system will never enters into deadlock state . Allow system to enter in deadlock state, detect it and recover. We ignore the problem and behaves like deadlock never occurs. To ensure deadlock never occurs system can use either a deadlock prevention or deadlock avoidance scheme. Deadlock prevention scheme ensure that at least one of necessary condition can not hold. Deadlock avoidance requires that the operating system be given in advance additional information concerning which resources a process will request and use during its lifetime.

3. Deadlock Prevention Deadlock to occur each of four necessary conditions must hold. If one of these condition not hold it prevents deadlock from occur. Mutual Exclusion: ME condition must hold for non-sharable resources such as printers. also for sharable resources Hold and wait : to ensure that hold and wait condition never occurs in the system we must guarantee that whenever process request a resource it does not hold any other resource. Example of disk drive, file and printer

4. 3. No preemption: there be no preemption of resources that have already been allocated . Process is holding some resources and request another resource that cannot be immediately allocated to it ,then all resources the process is currently holding are preempted. 4. Circular wait: to ensure this condition never holds is to impose a total ordering of all resource types and to require that each process request resources in increasing order of enumeration. R={R1,R2,….Rm} resource types assign to each unique number, which allow us to compare two resource and determine whether one precedes another in our ordering. Define one to one function F: R  N F(tape drives)=1 F(disk drive)=5 F(printers)=12

5. Deadlock Avoidance Require additional information how resources are to be requested. Simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need. The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition. Resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes.

6. Safe state When a process requests an available resource, system must decide if immediate allocation leaves the system in a safe state. System is in safe state if there exists a safe sequence. A sequence of processes < P 1 , P 2 , …, P n > is safe sequence for current allocation state if, of ALL the processes in the systems such that for each P i , the resources requestes that P i can still make 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.

7. Basic facts If a system is in safe state  no deadlocks. If a system is in unsafe state  possibility of deadlock. Avoidance  ensure that a system will never enter an unsafe state.

8. Safe, Unsafe , Deadlock State

9. Resource-Allocation Graph Scheme Claim edge P i  R j indicated that process P j may request resource R j ; represented by a dashed line. Claim edge converts to request edge when a process requests a resource. Request edge converted to an assignment edge when the resource is allocated to the process. When a resource is released by a process, assignment edge reconverts to a claim edge. Resources must be claimed a priori in the system

10. Unsafe State In Resource-Allocation Graph

11. Suppose that process P i requests a resource R j The request can be granted only if converting the request edge to an assignment edge does not result in the formation of a cycle in the resource allocation graph

12. Banker’s Algorithm Multiple instances. Each process must claim maximum need in advance. When a process requests a resource it may have to wait. When a process gets all its resources it execute successfully and must return them in a finite amount of time.

13. D a t a S t r u c t u r e s f o r t h e B a n k e r ’ s Algorithm 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 R j available. Max : n x m matrix. If Max [ i ][j ] = k , then process P i may request at most k instances of resource type R j . Allocation : n x m matrix. If Allocation [ i ][j ] = k then P i is currently allocated k instances of R j . Need : n x m matrix. If Need [ i ][j ] = k , then P i may need k more instances of R j to complete its task. Need [ i ][j] = Max [ i ][j] – Allocation [ i ][j]

14. Safety Algorithm Let Work and Finish be vectors of length m and n , respectively. Initialize: Work = Available Finish [ i ] = false for i = 0, 1, …, n- 1 . Find and i such that both: Finish [ i ] = false Need i  Work If no such i exists, go to step 4. Work = Work + Allocation i Finish [ i ] = true go to step 2. If Finish [ i ] == true for all i , then the system is in a safe state.

15. Resource-Request Algorithm for Process Request = request vector for process P i . If Request i [ j ] = k then process P i wants k instances of resource type R j . When request for resource made by process Pi then following actions are taken If Request i  Need i go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim. If R eq u es t i  Ava i la b l e , go to step 3. O t h er w ise P i m u st wait, since resources are not available. Pretend to allocate requested resources to P i by modifying the state as follows: Available = Available – Request; Allocation i = Allocation i + Request i ; Need i = Need i – Request i ; If safe  the resources are allocated to Pi. If unsafe  Pi must wait, and the old resource-allocation state is restored

16. Example of Banker’s Algorithm 5 processes P through P 4 ; 3 resource types: A (10 instances), B (5instances), and C (7 instances). Snapshot at time T : Allocation Max Available A B C A B C A B C P 0 1 7 5 3 3 3 2 P 1 2 0 3 2 2 P 2 3 0 2 9 0 2 P 3 2 1 1 2 2 2 P 4 0 0 2 4 3 3

17. E x a m p l e (C on t . ) The content of the matrix Need is defined to be Max – Allocation . Need A B C P 7 4 3 P 1 1 2 2 P 2 6 0 P 3 0 1 1 P 4 4 3 1 The system is in a safe state since the sequence < P 1 , P 3 , P 4 , P 2 , P > satisfies safety criteria.

18. Example: P 1 Request ( 1,0,2) Check that Request  Available (that is, (1,0,2)  (3,3,2)  true . Allocation Need Available A B C A B C A B C P 0 1 7 4 3 2 3 P 1 3 0 2 0 2 P 2 3 0 1 6 0 P 3 2 1 1 0 1 1 P 4 0 0 2 4 3 1 Executing safety algorithm shows that sequence < P 1 , P 3 , P 4 , P , P 2 > satisfies safety requirement. Can request for (3,3,0) by P 4 be granted? Can request for (0,2,0) by P be granted?

19. Deadlock Detection Allow system to enter deadlock state Detection algorithm Recovery scheme

20. Single Instance of Each Resource Type Maintain wait-for graph Nodes are processes. P i  P j if P i is waiting for P j . Periodically invoke an algorithm that searches for a cycle in the graph. If there is a cycle, there exists a deadlock. An algorithm to detect a cycle in a graph requires an order of n 2 operations, where n is the number of vertices in the graph.

21. Resource- Allocation Graph and Wait- for graph

22. S e v e r a l I n s t a n c e s o f a each R e s ou r c e type Available : A vector of length m indicates the number of available resources of each type. Allocation : An n x m matrix defines the number of resources of each type currently allocated to each process. R e q u e s t : An n x m m a t r i x i n d icates the curr e nt r e q u est of each process. If Request [ i j ] = k , then process P i is requesting k more instances of resource type. R j .

23. Detection Algorithm Let Work and Finish be vectors of length m and n , respectively Initialize: Work = Available For i = 1,2, …, n , if Allocation i  0, then Finish [ i ] = false;otherwise , Finish [ i ] = true . Find an index i such that both: Finish [ i ] == false Request i  Work If no such i exists, go to step 4.

24. Detection Algorithm (Cont.) Work = Work + Allocation i Finish [ i ] = true go to step 2. If Finish [ i ] == false, for some i , 1  i  n , then the system is in deadlock state. Moreover, if Finish [ i ] == false , then P i is deadlocked. Algorithm requires an order of O( m x n 2) operations to detect whether the system is in deadlocked state .

25. Example of Detection Algorithm Five processes P through P 4 ; three resource types A (7 instances), B (2 instances), and C (6 instances). Snapshot at time T : 0 0 0 0 1 3 1 3 5 2 4 7 2 4 7 2 6 A B C

26. E x a m p l e (C on t . ) P 2 requests an additional instance of type C . Re q ue s t A B C P P 1 2 1 P 2 1 P 3 1 P 4 2 State of system? Can reclaim resources held by process P , but insufficient resources to fulfill other processes; requests. Deadlock exists, consisting of processes P 1 , P 2 , P 3 , and P 4 .

27. Recovery from Deadlock: Process Termination Abort all deadlocked processes. Abort one process at a time until the deadlock cycle is eliminated. In which order should we choose to abort? Priority of the process. How long process has computed, and how much longer to completion. Resources the process has used. Resources process needs to complete. How many processes will need to be terminated. Is process interactive or batch?

28. Recovery from Deadlock: Resource Preemption Selecting a victim – minimize cost. Rollback – return to some safe state, restart process for that state. Starvation – same process may always be picked as victim, include number of rollback in cost factor.

29. Detection-Algorithm Usage When, and how often, to invoke depends on: How often a deadlock is likely to occur? How many processes will need to be rolled back?  one for each disjoint cycle If detection algorithm is invoked arbitrarily, there may be many cycles in the resource graph and so we would not be able to tell which of the many deadlocked processes “caused” the deadlock.