操作系統(tǒng)英文課件：ch6 Deadlocks

1、1DeadlocksChapter 66.1Resource6.2Introduction to deadlocks6.3The ostrich algorithm6.4Deadlock detection and recovery6.5Deadlock avoidance6.6Deadlock prevention6.7Other issues2ResourcesA resource is anything that can be used by a single process at any instant of time, and that must be acquired, used,

2、 and released over the course of time.Resource types R1, R2, . . ., RmCPU cycles, memory space, I/O devices ,record in a databaseEach resource type Ri has Wi instances.Preemptable resources可搶占資源can be taken away from a process with no ill effects (e.g. memory)Nonpreemptable resourceswill cause the p

3、rocess to fail if taken away (e.g. CD recorder)3ResourcesEach process utilizes a resource as follows:request the resourceuse the resourcerelease the resourceMust wait if request is deniedrequesting process may be blockedmay fail with error code4ResourcesProcesses need access to resources in reasonab

4、le orderSuppose a process holds resource A (e.g. scanner) and requests resource B (e.g. CD recorder)at same time another process holds B and requests Aboth are blocked and remain soDeadlocks occur when processes are granted exclusive access to devices5Using Semaphore to Share ResourceProcess P(); A.

5、Down(); B.Down(); use both resource B.Up(); A.Up(); Process Q(); A.Down(); B.Down(); use both resource B.Up(); A.Up(); 423 External Semaphore A(0), B(1);2External Semaphore A(0), B(0);3External Semaphore A(0), B(1);4External Semaphore A(1), B(1);5516External Semaphore A(1), B(1);116But Deadlock can

6、Happen!Process P(); A.Down(); B.Down(); use both resources B.Up(); A.Up(); Process Q(); B.Down(); A.Down(); use both resources A.Up(); B.Up(); 3211External Semaphore A(1), B(1);1External Semaphore A(0), B(1);2External Semaphore A(0), B(0);3DEADLOCK7Bridge Crossing ExampleTraffic only in one directio

7、n.Each section of a bridge can be viewed as a resource. If a deadlock occurs, it can be resolved if one car backs up (preempt resources and rollback). Several cars may have to be backed up if a deadlock occurs. 8Introduction to DeadlocksFormal definition :A set of processes is deadlocked if each pro

8、cess in the set is waiting for an event that only another process in the set can cause.Usually the event is release of a currently held resourceNone of the processes can runrelease resourcesbe awakened9Four Conditions for DeadlockMutual exclusion conditioneach resource assigned to 1 process or is av

9、ailableHold 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 chainDeadlock can

10、arise if four conditions hold simultaneously.10Deadlock ModelingModeled 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 U11Resource-Allocation GraphA set of vertices V and a set of edges E.V is par

11、titioned into two types:P = P1, P2, , Pn, the set consisting of all the processes in the system.R = R1, R2, , Rm, the set consisting of all resource types in the system.request edge directed edge Pi Rjassignment edge directed edge Rj Pi12Resource-Allocation GraphProcessResource Type with 4 instances

12、Pi requests an instance of RjPi is holding an instance of RjPiPiRjRj13Example of a Resource Allocation Graph14Resource Allocation Graph With A Deadlock15Resource Allocation Graph With A Cycle But No Deadlock16Basic FactsIf graph contains no cycles no deadlock.If graph contains a cycle if only one in

13、stance per resource type, then deadlock.if several instances per resource type, possibility of deadlock.17How deadlock occurs A B CDeadlock Modeling18Deadlock ModelingHow deadlock can be avoided (o) (p) (q)19Methods for Handling處理 DeadlocksIgnore the problem and pretend that deadlocks never occur in

14、 the systemAllow the system to enter a deadlock state and then recover. detection and recoveryEnsure that the system will never enter a deadlock state dynamic avoidance (careful resource allocation)prevention (negating one of the four necessary conditions)20(1) The Ostrich Algorithm鴕鳥(niǎo)算法Pretend there

15、 is no problemReasonable if deadlocks occur very rarely cost of prevention is highUNIX and Windows takes this approachIt is a trade off between conveniencecorrectness21(2) Deadlock DetectionAllow system to enter deadlock state Detection algorithmRecovery scheme22Detection with One Resource of Each T

16、ype Note the resource ownership and requestsA cycle can be found within the graph, denoting deadlock23An algorithm for detecting cycles in directed graphA data structure, L, a list of nodes.Arcs will be marked to indicate that they have already been inspected, to prevent repeated inspections.For eac

17、h node, N, in the graph, performing the following 5 steps with N as the starting node.Periodically invoke an algorithm that searches for a cycle in the graph.24An algorithm for detecting cycles in directed graphInitialize L to the empty list, and designate all the arcs as unmarked.Add the current no

18、de to the end of L and check to see if the node now appears in L two times. If it does, the graph contains a cycle (listed in L) and the algorithm terminates.From the given node, see if there are any unmarked outgoing arcs. If so, go to step 4; if not, go to step 5.Pick an unmarked outgoing arc at r

19、andom and mark it. Then follow it to the new current node and go to step 2.We have now reached a dead end. Remove it and go back to the previous node, make it the current node, and go to step 3. If this node is the initial node, the graph does not contain any cycles and the algorithm terminates. 25E

20、xample1Start at R and initialize L to the empty list.From R we go to S, giving L=R, A, S. S has no outgoing arcs (a dead end).Go backtrack to A. A has no unmarked outgoing arcs, go backtrack to R.R is the initial node, so no cycles. 26Example2Start at B and initialize L to the empty list.From B, we

21、follow outgoing arcs until we get to D, giving L=B, T, E, V, G, U, D. Pick S randomly and we come to a dead end, then backtrack to D. Now pick T and update L to be B, T, E, V, G, U, D, T. T appears two times in L, we discover cycle.27Detection with Multiple Resources of Each Type Data structures nee

22、ded by deadlock detection algorithm Cij + Aj = Eji=1n28Deadlock Detection AlgorithmBased on comparing vectors.(AB hold if and only if Ai Bi for 1=i not safe. If such a row exists, the process may finish. Mark that process (row) as terminate and add all of its resources to A.Repeat Steps 1 and 2 unti

23、l all rows are marked = safe state or not marked = not safe.43How to Compute SafetyGiven: n kinds of resourcesp processesSet P of processesstruct resource needsn, ownsn ToDop resource availablenwhile there exists a p in P such that for all i (ToDop.needsi availablei ) do for all i availablei += ToDo

24、p.ownsi; P = P - p; If P is empty then system is safe.44Is Allocation (1 0 2) to P1 Safe?ProcessAllocMaxNeedAvailableABCABCABCABCP00107537431055P1200322122332P2300902602P3211222011P400243343145And Run Safety Test: Group DiscussionIf P1 requests max resources, can completeProcessAllocMaxNeedAvailable

25、ABCABCABCABCP00107537431055P1302322020230P2300902602P3211222011P400243343146Allocate to P1, Then 47Release - P1 Finishes Now P3 can acquire max resources and release48Release P3 Finishes Now P4 can acquire max resources and releaseProcessAllocMaxNeedAvailableABCABCABCABCP00107537431055P1000322322743

26、P2300902602P4002433431P300022222249Release - P4 Finishes Now P2 can acquire max resources and release50Release - P2 Finishes Now P0 can acquire max resources and release51So P1 Allocation (1 0 2) Is SafeThere exists a safe sequence: P1, P3, P4, P2, P052Is allocation (0 2 0) to P0 Safe?Try to Allocat

27、e 2 B to P053Run Safety TestNo Processes may get max resources and release54So Unsafe State - Do Not EnterReturn to Safe State and do not allocate resourceProcessAllocMaxNeedAvailableABCABCABCABCP00107537431055P1302322020230P2300902602P3211222011P400243343155P0 Suspended Pending RequestWhen enough r

28、esources become available, P0 can awake56ResultsP0s request for 2 Bs cannot be granted because that would prevent any other process from completing if they need their maximum claim.57Just Because Its Unsafe-P0 could have been allocated 2 Bs and a deadlock might not have occurred if:P1 say didnt use

29、its maximum resources but finished using the resources it had58Allocate to P0(0 2 0)P1 can finish its work using the resources it just had 59If P1 Doesnt Need Max-Then P1 would have finishedProcessAllocMaxNeedAvailableABCABCABCABCP00307537231055P1000322322512P2300902602P3211222011P400243343160Banker

30、 Solution IssuesTrade-off: The bankers algorithm is conservative保守的 - it reduces parallelism for safety sake目的 Not very practicableProcesses rarely know advance what their maximum resource needs will beThe number of processes is not fixedResources that were thought to be available can suddenly vanis

31、h (tape drive can break)61(4) Deadlock PreventionRestrain控制 the ways request can be made.Mutual ExclusionHold and WaitNo PreemptionCircular Wait62Attacking the Mutual Exclusion ConditionSome devices (such as printer) can be spooledonly the printer daemon uses printer resourcethus deadlock for printe

32、r eliminatedNot all devices can be spooledPrinciple:avoid assigning resource when not absolutely necessaryas few processes as possible actually claim the resource63Attacking the Hold and Wait ConditionRequire processes to request all resources before startinga process never has to wait for what it n

33、eedsProblemsmay not know required resources at start of runalso ties up resources other processes could be usingVariation: process requesting a resource must give up all the resources it currently holds, then request all immediately needed64Attacking the No Preemption ConditionThis is not a viable o

34、ptionConsider a process given the printerhalfway through its jobnow forcibly take away printer!? 65Attacking the Circular Wait ConditionNormally ordered resourcesA resource graphNumber all resources and require all requests to be made in numerical order. (a) (b)66Summary of approaches to deadlock pr

35、evention67Other IssuesTwo-Phase LockingPhase Oneprocess tries to lock all records it needs, one at a timeif needed record found locked, start overIf 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 stop