Unformatted text preview:

Deadlock Avoidance CSCI 3753 Operating Systems Spring 2005 Prof Rick Han Announcements HW 4 is due Tuesday March 8 11 am extra office hours Monday March 7 2 pm PA 2 assigned due Thursday March 17 11 55 pm Midterm is Thursday March 10 covers chapter 1 10 Midterm review is Tuesday March 8 Read chapter 10 Section this week is grader and prof From last time We discussed Deadlock Modeling 4 necessary conditions for deadlock mutex hold and wait no preemption circular waiting Deadlock Prevention ways to prevent at least 1 of these conditions from coming true Deadlock Avoidance Each process provides OS with information about its requests and releases for resources Ri OS decides whether deadlock will occur at run time e g batch jobs know a priori which resources they ll request and when weakness need a priori info simple strategy specify a maximum claim knowing all future requests and releases is difficult estimating a maximum demand for resources for each process is easier to produce A resource allocation state is defined by of available resources of allocated resources to each process maximum demands by each process Deadlock Avoidance A state is safe if there exists a safe sequence of processes P1 Pn for the current resource allocation state A sequence of processes is safe if for each Pi in the sequence the resource requests that Pi can still make can be satisfied by currently available resources all resources held by all previous processes in the sequence Pj j i If resources needed by Pi are not available Pi waits for all Pj to release their resources Deadlock Avoidance Intuition for a safe state given that the system is in a certain state we want to find at least one way out of trouble i e find a sequence of processes that even when they demand their maximum resources won t deadlock the system this is a worst case analysis it may be that during the normal execution of processes none ever demands its maximum in a way that causes deadlock to perform a more optimal less than worst case analysis is more complex and also requires a record of future accesses Deadlock Avoidance A safe state provides a safe escape sequence A deadlocked state is unsafe An unsafe state is not necessarily deadlocked A system may transition from a safe to an unsafe state if a request for resources is granted ideally check with each request for resources whether the system is still safe safe deadlocked unsafe Deadlock Avoidance Example 1 12 instances of a resource At time t0 P0 holds 5 P1 holds 2 P2 holds 2 Available 3 free instances processes max needs allocated P0 10 5 P1 4 2 P2 9 2 Deadlock Avoidance Example 1 cont Is the system in a safe state Can I find a safe sequence Yes I claim the sequence P1 P0 P2 is safe P1 requests its maximum currently has 2 so needs 2 more and holds 4 then there is only 1 free resource Then P1 then releases all of its held resources so that there are 5 free Next suppose P0 requests its maximum currently has 5 so needs 5 more and holds 10 so that there are 0 free Then P0 releases all of its held resources so that there are 10 free Next P2 requests its max of 9 leaving 3 free and then releases them all Thus the sequence P1 P0 P2 is safe and is able in the worst case to request maximum resources for each process in the sequence and release all such resources for the next process in the sequence Deadlock Avoidance Example 2 at time t1 process P2 requests and is given 1 more instance of the resource then processes max needs allocated P0 10 5 P1 4 2 P2 9 3 Available 2 free instances Is the system in a safe state Deadlock Avoidance Example 2 cont P1 can request its maximum currently holds 2 and needs 2 more of 4 so that there are 0 free P1 releases all its held resources so that available 4 free Neither P0 nor P2 can request their maximum resources P0 needs 5 P2 needs 6 and there are only 4 free Both would have to wait so there could be deadlock The system is deemed unsafe The mistake was granting P2 an extra resource at time t1 Forcing P2 to wait for P0 or P1 to release their resources would have avoided potential deadlock Deadlock Avoidance Policy before granting a request at each step perform a worst case analysis is there a safe sequence a way out If so grant request If not delay requestor and wait for more resources to be freed Banker s Algorithm takes this approach Resource allocation graph approach does not use a worst case analysis next slide but is limited in its applicability Deadlock Avoidance Using a Resource Allocation Graph for deadlock avoidance each process identifies possible future claims drawn as claim edges dotted lines If converting a claim edge to a request edge creates a loop then don t grant request limited applicability only valid when there is 1 instance of each resource example Granting P2 s request for R2 creates a loop so don t grant it R1 P1 claim edge P2 claim edge R2 granted request creates loop Deadlock Avoidance Banker s Algorithm when there is a request the system determines whether allocating resources for the request leaves the system in a safe state that avoids deadlock if no then wait for another process to release resources each process declares its maximum demands must be less than total resources in system Advantages generalization of earlier examples 1 and 2 to allow multiple types of resources works for multiple instances of resources unlike resource allocation graph adapts at run time to individual requests avoids deadlock individual requests don t need to be known a priori except for maximum demands which is not completely unrealistic Deadlock Avoidance Banker s Algorithm Define quantities Available resources in a vector or list Available j j 1 m resource types Available j k means that there are k instances of resource Rj available Maximum demands in a matrix or table Max i j where i 1 n processes and j 1 m resource types Max i j k means that process i s maximum demands are for k instances of resource Rj Allocated resources in a matrix Alloc i j Alloc i j k means that process i is currently allocated k instances of resource Rj Needed resources in a matrix Need i j Max i j Alloc i j Deadlock Avoidance Banker s Algorithm An example of the Alloc i j matrix Resources Processes Column j Row i 8 0 1 7 12 2 17 0 1 0 4 0 1 Alloci is shorthand for row i of matrix Alloc i j i e the resources allocated to process i Deadlock Avoidance Banker s Algorithm Some terminology let X and Y be two vectors Then we say X Y if and only if X i Y i for all i Example V1


View Full Document

CU-Boulder CSCI 3753 - Deadlock Avoidance

Download Deadlock Avoidance
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Deadlock Avoidance and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Deadlock Avoidance 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?