1DeadlocksChapter 3 3.1. Resource 3.2. Introduction to deadlocks 3.3. The ostrich algorithm 3.4. Deadlock detection and recovery 3.5. Deadlock avoidance 3.6. Deadlock prevention 3.7. Other issues

2Agenda3.1. Resource3.2. Introduction to deadlocks 3.3. The ostrich algorithm 3.4. Deadlock detection and recovery 3.5. Deadlock avoidance 3.6. Deadlock prevention 3.7. Other issues

3ResourcesExamples of computer resourcesprinterstape drivestablesProcesses need access to resources in reasonable orderSuppose a process holds resource A and requests resource Bat same time another process holds B and requests Aboth are blocked and remain so

4Resources (1)Deadlocks occur when …processes are granted exclusive access to deviceswe refer to these devices generally as resourcesPreemptable resourcescan be taken away from a process with no ill effectsNonpreemptable resourceswill cause the process to fail if taken away

5Resources (2)Sequence of events required to use a resourcerequest the resourceuse the resourcerelease the resource Must wait if request is deniedrequesting process may be blockedmay fail with error code

6Introduction to DeadlocksFormal definition :A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can causeUsually the event is release of a currently held resourceNone of the processes can …runrelease resourcesbe awakened

7Four Conditions for DeadlockMutual exclusion conditioneach resource assigned to 1 process or is availableHold and wait conditionprocess holding resources can request additionalNo preemption conditionpreviously granted resources cannot forcibly taken awayCircular wait conditionmust be a circular chain of 2 or more processeseach is waiting for resource held by next member of the chain

8Agenda3.1. Resource3.2. Introduction to deadlocks 3.3. The ostrich algorithm 3.4. Deadlock detection and recovery 3.5. Deadlock avoidance 3.6. Deadlock prevention 3.7. Other issues

9Deadlock Modeling (2)Modeled with directed graphsresource R assigned to process Aprocess B is requesting/waiting for resource Sprocess C and D are in deadlock over resources T and U

10Deadlock Modeling (3)Strategies for dealing with Deadlocksjust ignore the problem altogetherdetection and recoverydynamic avoidance careful resource allocationprevention negating one of the four necessary conditions

11How deadlock occursA B CDeadlock Modeling (4)

12Deadlock Modeling (5)How deadlock can be avoided(o) (p) (q)

13Agenda3.1. Resource3.2. Introduction to deadlocks 3.3. The ostrich algorithm 3.4. Deadlock detection and recovery 3.5. Deadlock avoidance 3.6. Deadlock prevention 3.7. Other issues

14The Ostrich AlgorithmPretend there is no problemReasonable if deadlocks occur very rarely cost of prevention is highUNIX and Windows takes this approachIt is a trade off between conveniencecorrectness

15Agenda3.1. Resource3.2. Introduction to deadlocks 3.3. The ostrich algorithm 3.4. Deadlock detection and recovery 3.5. Deadlock avoidance 3.6. Deadlock prevention 3.7. Other issues

16Detection with One Resource of Each TypeNote the resource ownership and requestsA cycle can be found within the graph, denoting deadlock

17Detection with Multiple Resource of Each Type (1)Data structures needed by deadlock detection algorithm

18Detection with Muliple Resource of Each Type (2)An example for the deadlock detection algorithm

19Recovery from Deadlock (1)Recovery through preemptiontake a resource from some other processdepends on nature of the resourceRecovery through rollbackcheckpoint a process periodicallyuse this saved state restart the process if it is found deadlocked

20Recovery from Deadlock (2)Recovery through killing processescrudest but simplest way to break a deadlockkill one of the processes in the deadlock cyclethe other processes get its resources choose process that can be rerun from the beginning

21Agenda3.1. Resource3.2. Introduction to deadlocks 3.3. The ostrich algorithm 3.4. Deadlock detection and recovery 3.5. Deadlock avoidance 3.6. Deadlock prevention 3.7. Other issues

22Deadlock AvoidanceResource TrajectoriesTwo process resource trajectories

23Safe and Unsafe States (1)Demonstration that the state in (a) is safe(a) (b) (c) (d) (e)

24Safe and Unsafe States (2)Demonstration that the sate in b is not safe(a) (b) (c) (d)

25The Banker's Algorithm for a Single ResourceThree resource allocation statessafesafeunsafe(a) (b) (c)

26Banker's Algorithm for Multiple ResourcesExample of banker's algorithm with multiple resources

27Agenda3.1. Resource3.2. Introduction to deadlocks 3.3. The ostrich algorithm 3.4. Deadlock detection and recovery 3.5. Deadlock avoidance 3.6. Deadlock prevention 3.7. Other issues

28Deadlock PreventionAttacking the Mutual Exclusion ConditionSome devices (such as printer) can be spooledonly the printer daemon uses printer resourcethus deadlock for printer eliminatedNot all devices can be spooledPrinciple:avoid assigning resource when not absolutely necessaryas few processes as possible actually claim the resource

29Attacking the Hold and Wait ConditionRequire processes to request resources before startinga process never has to wait for what it needsProblemsmay not know required resources at start of runalso ties up resources other processes could be usingVariation: process must give up all resourcesthen request all immediately needed

30Attacking the No Preemption ConditionThis is not a viable optionConsider a process given the printerhalfway through its jobnow forcibly take away printer!!??

31Attacking the Circular Wait Condition (1)Normally ordered resourcesA resource graph(a) (b)

32Attacking Deadlock ConditionSummary of approaches to deadlock prevention

33Agenda3.1. Resource3.2. Introduction to deadlocks 3.3. The ostrich algorithm 3.4. Deadlock detection and recovery 3.5. Deadlock avoidance 3.6. Deadlock prevention 3.7. Other issues

34Other IssuesTwo-Phase LockingPhase Oneprocess tries to lock all records it needs, one at a timeif needed record found locked, start over(no real work done in phase one)If phase one succeeds, it starts second phase, performing updatesreleasing locks Note similarity to requesting all resources at onceAlgorithm works where programmer can arrange program can be stopped, restarted

35Nonresource DeadlocksPossible for two processes to deadlockeach is waiting for the other to do some taskCan happen with semaphoreseach process required to do a down() on two semaphores (mutex and another)if done in wrong order, deadlock results

36StarvationAlgorithm to allocate a resource may be to give to shortest job firstWorks great for multiple short jobs in a systemMay cause long job to be postponed indefinitelyeven though not blockedSolution:First-come, first-serve policy