Deadlock AvoidanceAnnouncementsFrom last time...Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Deadlock AvoidanceCSCI 3753 Operating SystemsSpring 2005Prof. Rick HanAnnouncements•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 profFrom 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 trueDeadlock 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 processDeadlock 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 resourcesDeadlock 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 accessesDeadlock 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 safedeadlockedunsafesafeDeadlock Avoidance•Example 1:–12 instances of a resource–At time t0, P0 holds 5, P1 holds 2, P2 holds 2–Available = 3 free instancesprocesses max needs allocatedP0 10 5P1 4 2P2 9 2Deadlock 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 sequenceDeadlock Avoidance•Example 2:–at time t1, process P2 requests and is given 1 more instance of the resource, then processes max needs allocatedP0 10 5P1 4 2P2 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 deadlockDeadlock 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 applicabilityDeadlock 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 itP1 P2R2R1claimedgegrantedrequestcreatesloopclaimedgeDeadlock 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 unrealisticDeadlock 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