操作系統(tǒng)課件：08_deadlocks

1、1DEADLOCK 6.1. Resource 6.2. Basics 6.3. The ostrich algorithm 6.4. Deadlock detection and recovery 6.5. Deadlock avoidance 6.6. Deadlock prevention 6.7. Other issues Real World Deadlocks?Truck A has to waitfor truck B tomoveNotdeadlockedReal World Deadlocks?Gridlock4ResourcesExamples of computer re

2、sources:- hardware device (e.g. printers) or- piece of information(e.g. locked record in a database)Suppose a process holds resource A and requests resource B and at same time another process holds B and requests A Both are blocked and remain so.5Resources (1)Preemptable resourcescan be taken away f

3、rom a process with no ill effects, e.g. main memoryNonpreemptable resourceswill cause the process to fail if taken away, e.g. CD-Rom6Resources (2)Sequence of events required to use a resourcerequest the resourceuse the resourcerelease the resource Must wait if request is deniedrequesting process may

4、 be blockedmay fail with error codeSystem calls: request or open a special fileCode in figure 6-27Introduction 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 cause.Usually the event is releas

5、e of a currently held resourceNone of the processes can runrelease resourcesbe awakened8Resource Allocation GraphDirected graph with process and resource nodes,arrows indicate request and allocationa) resource R assigned to process Ab) process B is requesting/waiting for resource Sc) process C and D

6、 are in deadlock over resources T and U9A B CHow Deadlock Occurs10A Deadlock-free Run(o) (p) (q)11Four Conditions for DeadlockMutual exclusion conditioneach resource assigned to at most one processHold and wait conditionprocess holding resources can request additional resourceNo preemption condition

7、previously granted resources cannot forcibly taken awayCircular wait conditionmust be a circular chain of two or more processes such thateach is waiting for resource held by next member of the chain12Handling DeadlocksStrategies for dealing with Deadlocksjust ignore the problem altogether prevention

8、 by negating one of the four necessary conditionsdetection and recoverydynamic avoidance by careful resource allocation13The 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 c

9、onveniencecorrectness14Detection with One Resource of Each Type (1)Deadlock occurs if and only if there is a cycle in the resource allocation graph.Cycles can be checked by a depth-first search.15Detection with Multiple Resources of Each Type (1)Deadlock occurs if each process request is unsatisfiab

10、le.16An example for the deadlock detection algorithm Process 3s request can be granted.What happens if process 3 wants an additional CD-Rom?ExampleFinished = F, F, F, F; Work = Available = (0, 0, 1);R1R2R3P1111P2212P3110P4111R1R2R3P1321P2221P3001P4111AllocationRequestExampleFinished = F, F, T, F; Wo

11、rk = (1, 1, 1);R1R2R3P1111P2212P3110P4111R1R2R3P1321P2221P3P4111AllocationRequestExampleFinished = F, F, T, T; Work = (2, 2, 2);R1R2R3P1111P2212P3110P4111R1R2R3P1321P2221P3P4AllocationRequestExampleFinished = F, T, T, T; Work = (4, 3, 2);R1R2R3P1111P2212P3110P4111R1R2R3P1321P2P3P4AllocationRequestWh

12、en to run Detection Algorithm?For every resource request?For every request that cannot be immediately satisfied?Once every hour?When CPU utilization drops below 40%? 22Recovery from Deadlock (1)Recovery through preemptiontake a resource from some other processdepends on nature of the resourceRecover

13、y through rollbackcheckpoint a process periodicallyuse this saved state restart the process if it is found deadlocked23Recovery 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 re

14、sources choose process that can be rerun from the beginning24Deadlock AvoidanceResource TrajectoriesTwo process resource trajectories25Safe StateA state is safe if it is not deadlocked and there is some scheduling order in which every process can run to completion even if they request their maximum

15、number of resources immediately.An unsafe state is a state that is not safe.Note that unsafe does not necessary mean deadlocked.Safe State ExampleSuppose there are 12 tape drives max need current usage could ask forp01055p1422p29273 drives remaincurrent state is safe because a safe sequence exists:

16、p1 can complete with current resourcesp0 can complete with current+p1p2 can complete with current +p1+p0if p2 requests 1 drive, then it must wait to avoid unsafe state.Bankers AlgorithmSuppose we know the “worst case” resource needs of processes in advanceA bit like knowing the credit limit on your

17、credit cards. (This is why they call it the Bankers Algorithm)Observation: Suppose we just give some process ALL the resources it could need Then it will execute to completion. After which it will give back the resources.Like a bank: If Visa just hands you all the money your credit lines permit, at

18、the end of the month, youll pay your entire bill, right?Bankers AlgorithmDecides whether to grant a resource request. Data structures:n: integer # of processesm: integer # of resourcesavailable1.m - availablei is # of avail resources of type imax1.n,1.m- max demand of each Pi for each Riallocation1.

19、n,1.m - current allocation of resource Rj to Pineed1.n,1.mmax # resource Rj that Pi may still requestlet requesti be vector of # of resource Rj Process Pi wantsBasic AlgorithmIf requesti needi then error (asked for too much)If requesti availablei then wait (cant supply it now)Resources are available

20、 to satisfy the requestLets assume that we satisfy the request. Then we would have:available = available - requestiallocationi = allocation i + requestineedi = need i - request iNow, check if this would leave us in a safe state:if yes, grant the request, if no, then leave the state as is and cause p

21、rocess to wait.Safety Checkfree1.m = available /* how many resources are available */finish1.n = false (for all i) /* none finished yet */Step 1: Find an i such that finishi=false and needi = work /* find a proc that can complete its request now */ if no such i exists, go to step 3 /* were done */St

22、ep 2: Found an i:finish i = true /* done with this process */ free = free + allocation i /* assume this process were to finish, and its allocation back to the available list */go to step 1Step 3: If finishi = true for all i, the system is safe. Else NotBankers Algorithm: Example Allocation Max Avail

23、able A B C A B C A B CP0 0 1 0 7 5 3 3 3 2P1 2 0 0 3 2 2 P2 3 0 2 9 0 2 P3 2 1 1 2 2 2 P4 0 0 2 4 3 3 this is a safe state: safe sequence Suppose that P1 requests (1,0,2) - add it to P1s allocation and subtract it from AvailableBankers Algorithm: Example Allocation Max Available A B C A B C A B CP0

24、0 1 0 7 5 3 2 3 0P1 3 0 2 3 2 2 P2 3 0 2 9 0 2 P3 2 1 1 2 2 2 P4 0 0 2 4 3 3 This is still safe: safe seq In this new state,P4 requests (3,3,0) not enough available resources P0 requests (0,2,0) lets check resulting stateBankers Algorithm: Example Allocation Max Available A B C A B C A B CP0 0 3 0 7

25、 5 3 2 1 0P1 3 0 2 3 2 2 P2 3 0 2 9 0 2 P3 2 1 1 2 2 2 P4 0 0 2 4 3 3 This is unsafe state (why?)So P0s request will be deniedProblems with Bankers Algorithm?34Deadlock PreventionAttacking the Mutual Exclusion ConditionSome devices (such as printer) can be spooledonly the printer daemon uses printer

26、 resourcethus deadlock for printer eliminatedNot all devices can be spooledPrinciple:avoid assigning resource when not absolutely necessaryas few processes as possible actually claim the resource35Attacking 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 needed36Attacking the No Preemption ConditionThis is not a viable optionCons