中科大操作系统原理与实现课件7_deadlock.pdf

.操作系统原理与设计第7章 Deadlocks（死锁）陈香兰中国科学技术大学计算机学院2009年11月05日.提纲Background and System ModelDeadlock CharacterizationNecessary ConditionsResource-Allocation GraphMethods for Handling DeadlocksDeadlock PreventionDeadlock AvoidanceSafe StateResource-Allocation Graph SchemeBankers AlgorithmDeadlock Detection小结和作业.OutlineBackground and System ModelDeadlock CharacterizationNecessary ConditionsResource-Allocation GraphMethods for Handling DeadlocksDeadlock PreventionDeadlock AvoidanceSafe StateResource-Allocation Graph SchemeBankers AlgorithmDeadlock Detection小结和作业.The Deadlock Problemdeadlock situationA set of blocked processes each holding a resource and waiting toacquire a resource held by another process in the set.ExampleISystem has 2 disk drives.IP1and P2each hold one disk drive and each needs another one.ExampleIsemaphores A and B,initialized to 1P0P1wait(A);wait(B)wait(B);wait(A).Bridge Crossing ExampleITraffic only in one direction.IEach section of a bridge can be viewed as a resource.IIf a deadlock occurs,it can be resolved if one car backs up(preempt resources and rollback).ISeveral cars may have to be backed up if a deadlock occurs.IStarvation is possible.System ModelIResource types R1,R2,.,RmICPU cycles,memory space,I/O devicesIEach resource type Rihas Wiinstances.IEach process utilizes a resource as follows:IrequestIuseIrelease.OutlineBackground and System ModelDeadlock CharacterizationNecessary ConditionsResource-Allocation GraphMethods for Handling DeadlocksDeadlock PreventionDeadlock AvoidanceSafe StateResource-Allocation Graph SchemeBankers AlgorithmDeadlock Detection小结和作业.Deadlock Characterization:Necessary ConditionsIDeadlock can arise if four conditions hold simultaneously.IMutual exclusion:only one process at a time can use aresource.IHold and wait:a process holding at least one resource iswaiting to acquire additional resources held by other processes.INo preemption:a resource can be released only voluntarily bythe process holding it,after that process has completed itstask.ICircular wait:there exists a set P0,P1,.,P0 of waitingprocesses such that P0is waiting for a resource that is held byP1,P1is waiting for a resource that is held by P2,.,Pn1iswaiting for a resource that is held by Pn,and Pnis waiting fora resource that is held by P0.Resource-Allocation Graph.IA set of vertices V and a set of edges E.IV is partitioned into two types:IP=P1,P2,.,Pn,the set consisting of all the processesin the system.IR=R1,R2,.,Rm,the set consisting of all resource typesin the system.Irequest edge directed edge Pi RjIassignment edge directed edge RjPiIProcessIResource Type with 4 instancesIPirequests instance of RjIPiis holding an instance of Rj.Example of a Resource Allocation Graph.Resource Allocation Graph With A Deadlock.Graph With A Cycle But No Deadlock.Basic FactsIIf graph contains no cycles no deadlock.IIf graph contains a cycle Iif only one instance per resource type,then deadlock.Iif several instances per resource type,possibility of deadlock.Methods for Handling DeadlocksIEnsure that the system will never enter a deadlock state.IAllow the system to enter a deadlock state and then recover.IIgnore the problem and pretend that deadlocks never occur inthe system;used by most operating systems,including UNIX.OutlineBackground and System ModelDeadlock CharacterizationNecessary ConditionsResource-Allocation GraphMethods for Handling DeadlocksDeadlock PreventionDeadlock AvoidanceSafe StateResource-Allocation Graph SchemeBankers AlgorithmDeadlock Detection小结和作业.Deadlock Prevention IRestrain the ways request can be made.IMutual ExclusionInot required for sharable resources;must hold fornonsharable resources.IHold and WaitImust guarantee that whenever a process requests a resource,itdoes not hold any other resources.1.Require process to request and be allocated all its resourcesbefore it begins execution,or2.allow process to request resources only when the process hasnone.ILow resource utilization;starvation possible.Deadlock Prevention IIINo Preemption1.If a process that is holding some resources requests anotherresource that cannot be immediately allocated to it,then allresources currently being held are released.IPreempted resources are added to the list of resources forwhich the process is waiting.IProcess will be restarted only when it can regain its oldresources,as well as the new ones that it is requesting.2.preempt the desired resources from the waiting process andallocate them to the requesting processIif the resource are neither available nor held by a waitingprocess,the requesing process must wait.Deadlock Prevention IIIICircular WaitIimpose a total ordering of all resource types,and require thateach process requests resources in an increasing order ofenumeration.1.always in an increasing order2.may release some higher ordered resource before requestinglower ordered resource.OutlineBackground and System ModelDeadlock CharacterizationNecessary ConditionsResource-Allocation GraphMethods for Handling DeadlocksDeadlock PreventionDeadlock AvoidanceSafe StateResource-Allocation Graph SchemeBankers AlgorithmDeadlock Detection小结和作业.Deadlock AvoidanceIRequires that the system has some additional a prioriinformation available.ISimplest and most useful model requires that each processdeclare the maximum number of resources of each type that itmay need.IThe deadlock-avoidance algorithm dynamically examines theresource-allocation state to ensure that there can never be acircular-wait condition.IResource-allocation state is defined by the number ofavailable and allocated resources,and the maximumdemands of the processes.Safe State.IWhen a process requests an available resource,system mustdecide if immediate allocation leaves the system in a safestate.ISystem is in safe state if there exists a sequence of ALL the processes in the systems such that foreach Pi,the resources that Pican still request can be satisfiedby currently available resources+resources held by all the Pj,with j i.IThat is:IIf Piresource needs are not immediately available,then Picanwait until all Pjhave finished.IWhen Pjis finished,Pican obtain needed resources,execute,return allocated resources,and terminate.IWhen Piterminates,Pi+1can obtain its needed resources,andso on.Basic Facts:Safe,Unsafe,Deadlock State IIIf a system is in safe state no deadlocks.IIf a system is in unsafe state possibility of deadlock.IAvoidance ensure that a system will never enter an unsafestate.Basic Facts:Safe,Unsafe,Deadlock State IIIExample,12 tape drives and 3 processes,at T0MaxNeedscurrentP0105P142P292IIif at T2,P2request and is allocated one more tape drive,?.Avoidance algorithmsISingle instance of a resource type.IUse a resource-allocation graphIMultiple instances of a resource type.IUse the bankers algorithm.Resource-Allocation Graph SchemeIClaim edge(需求边)PiRjindicated that process Pjmayrequest resource Rj;represented by a dashed line.IClaim edge converts to request edge when a processrequests a resource.IRequest edge converted to an assignment edge when theresource is allocated to the process.IWhen a resource is released by a process,assignment edgereconverts to a claim edge.IResources must be claimed a priori in the system.Resource-Allocation Graph.Unsafe State In Resource-Allocation Graph.Resource-Allocation Graph AlgorithmISuppose that process Pirequests a resource RjIThe request can be granted only if converting therequest edge to an assignment edge does not result inthe formation of a cycle in the resource allocation graph.Bankers AlgorithmIMultiple instances.IEach process must a priori claim maximum use.IWhen a process requests a resource it may have to wait.IWhen a process gets all its resources it must return them in afinite amount of time.Data Structures for the Bankers AlgorithmLetn=number of processesm=number of resources types.IAvailable:Vector of length m.If availablej=k,there are kinstances of resource type Rjavailable.IMax:n m matrix.If Maxi,j=k,then process Pimayrequest at most k instances of resource type Rj.IAllocation:n m matrix.If Allocationi,j=k then Piiscurrently allocated k instances of Rj.INeed:n m matrix.If Needi,j=k,then Pimay need kmore instances of Rjto complete its task.Needi,j=Maxi,j Allocationi,j.Safety Algorithm.1.Let Work and Finish be vectors of length m and n,respectively.Initialize:Work=AvailableFinishi=false for i=0,1,.,n 1.2.Find an i such that both:2.1 Finishi=false2.2 Needi WorkIf no such i exists,go to step 4.3.Work=Work+Allocationi,Finishi=true,go to step 2.4.If Finishi=true for all i,then the system is in a safe state.Resource-Request Algorithm for Process Pi.Request=request vector for process Pi.If Requestij=k thenprocess Piwants k instances of resource type Rj.1.If Requesti Needigo to step 2.Otherwise,raise errorcondition,since process has exceeded its maximum claim.2.If Requesti Available,go to step 3.Otherwise Pimust wait,since resources are not available.3.Pretend to allocate requested resources to Piby modifyingthe state as follows:Available=Available Request;Allocationi=Allocationi+Requesti;Needi=Needi Requesti;IIf safe the resources are allocated to Pi.IIf unsafe Pimust wait,and the old resource-allocation stateis restored.Example of Bankers Algorithm II5 processes:P0 P4;I3 resource types:A(10 instances),B(5instances),and C(7 instances).ISnapshot at time T0:AllocationMaxAvailableA B CA B CA B CP00 1 07 5 33 3 2P12 0 03 2 2P23 0 29 0 2P32 1 12 2 2P40 0 24 3 3.Example of Bankers Algorithm IIIThe content of the matrix Need is defined to beMax-Allocation.NeedA B CP07 4 3P11 2 2P26 0 0P30 1 1P44 3 1IThe system is in a safe state since the sequence satisfies safety criteria.Example:P1Request(1,0,2)ICheck that Request Available(that is,(1,0,2)(3,3,2)true.AllocationNeedAvailableA B CA B CA B CP00 1 07 4 32 3 0P13 0 20 2 0P23 0 16 0 0P32 1 10 1 1P40 0 24 3 1IExecuting safety algorithm shows that sequence satisfies safety requirement.ICan request for(3,3,0)by P4be granted?ICan request for(0,2,0)by P0be granted?.OutlineBackground and System ModelDeadlock CharacterizationNecessary ConditionsResource-Allocation GraphMethods for Handling DeadlocksDeadlock PreventionDeadlock AvoidanceSafe StateResource-Allocation Graph SchemeBankers AlgorithmDeadlock Detection小结和作业.Deadlock DetectionIAllow system to enter deadlock stateIDetection algorithmIRecovery scheme1.single instance2.several instances.Single Instance of Each Resource Type IIMaintain wait-for graphINodes are processes.IPiPj,if Piis waiting for Pj.Single Instance of Each Resource Type IIIPeriodically invoke an algorithm that searches for a cycle inthe graph.If there is a cycle,there exists a deadlock.IAn algorithm to detect a cycle in a graph requires an order ofn2operations,where n is the number of vertices in the graph.Several Instances of a Resource TypeIAvailable:A vector of length m indicates the number ofavailable resources of each type.IAllocation:An n m matrix defines the number of resourcesof each type currently allocated to each process.IRequest:An n m matrix indicates the current request ofeach process.If Requestij=k,then process Piis requestingk more instances of resource type Rj.Detection Algorithm I1.Let Work and Finish be vectors of length m and n,respectively Initialize:1.1 Work=Available1.2 For i=1,2,.,n,if Allocationi=0,thenFinishi=false;otherwise,Finishi=true.2.Find an i such that both:2.1 Finishi=false2.2 Requesti WorkIf no such i exists,go to step 4.3.Work=Work+Allocationi,Finishi=true,go to step 2.4.If Finishi=false,for some i,1 i n,then the system isin deadlock state.Moreover,if Finishi=false,then Piisdeadlocked.IAlgorithm requires an order of O(m n2)operations todetect whether the system is in deadlocked state.Example of Detection Algorithm IIFive processesIP0 P4;Ithree resource typesIA(7 instances),B(2 instances),and C(6 instances).ISnapshot at time T0:AllocationRequestAvailableA B CA B CA B CP00 1 00 0 00 0 0P12 0 02 0 2P23 0 20 0 0P32 1 11 0 0P40 0 20 0 2ISequence will result in Finishi=truefor all i.Example of Detection Algorithm IIIP2requests an additional instance of type C.RequestA B CP00 0 0P12 0 1P20 0 1P31 0 0P40 0 2IState of system?ICan reclaim resources held by process P0,but insufficientresources to fulfill other processes requests.IDeadlock exists,consisting of processes P1,P2,P3,and P4.Detection-Algorithm UsageIWhen,and how often,to invoke depends on:IHow often a deadlock is likely to occur?IHow many processes will need to be rolled back?Ione for each disjoint cycleIIf detection algorithm is invoked arbitrarily,there may bemany cycles in the resource graph and so we would not beable to tell which of the many deadlocked processes“caused”the deadlock.Recovery from Deadlock:Process TerminationIAbort all deadlocked processes.IAbort one process at a time until the deadlock cycle iseliminated.IIn which order should we choose to abort?IPriority of the process.IHow long process has computed,and how much longer tocompletion.IResources the process has used.IResources process needs to complete.IHow many processes will need to be terminated.IIs process interactive or batch?.Recovery from Deadlock:Resource PreemptionISelecting a victim minimize cost.IRollback return to some safe state,restart process for thatstate.IStarvation same process may always be picked as victim,include number of rollback in cost factor.OutlineBackground and System ModelDeadlock CharacterizationNecessary ConditionsResource-Allocation GraphMethods for Handling DeadlocksDeadlock PreventionDeadlock AvoidanceSafe StateResource-Allocation Graph SchemeBankers AlgorithmDeadlock Detection小结和作业.小结Background and System ModelDeadlock CharacterizationNecessary ConditionsResource-Allocation GraphMethods for Handling DeadlocksDeadlock PreventionDeadlock AvoidanceSafe StateResource-Allocation Graph SchemeBankers AlgorithmDeadlock Detection小结和作业.作业I华夏班：7.1，7.7，7.11I非华夏班：8.4，8.13.谢谢！