Concurrency: Deadlock and StarvationChapter 6Outline 6.1 Principle of Deadlock6.2 Deadlock prevention(死锁预防)6.3 Deadlock avoidance(死锁避免)6.4 Deadlock detection(死锁检测)6.1 Principle of deadlockDefinition: Permanent blocking of a set of processes that either compete for system resources or communicate with each otherNo efficient solutionInvolve conflicting needs for resources by two or more processes1、Reusable ResourcesUsed by one process at a time and not depleted (消耗掉消耗掉)by that useProcesses obtain resources that they later release for reuse by other processesProcessors, I/O channels, main and secondary memory, files, databases, and semaphoresDeadlock occurs if each process holds one resource and requests the otherExample of Deadlock, D & TAnother Example of DeadlockSpace is available for allocation of 200K bytes, and the following sequence of events occurDeadlock occurs if both processes progress to their second requestP1. . . . .Request 80K bytes;Request 60K bytes;P2. . . . .Request 70K bytes;Request 80K bytes;2、Consumable ResourcesCreated (produced) and destroyed (consumed) by a processInterrupts, signals, messages, and information in I/O buffersDeadlock may occur if a Receive message is blockingMay take a rare combination of events to cause deadlockExample of DeadlockDeadlock occurs if receive is blockingP1. . . . .Receive(P2);Send(P2, M1);P2. . . . .Receive(P1);Send(P1, M2);3、Resource Allocation GraphsDirected graph that depicts a state of the system of resources and processesResource Allocation Graphs4、Conditions for DeadlockMutual exclusion(互斥排它性访问资源)only one process may use a resource at a timeHold-and-wait(占有且等待拥有部分资源,还要请求新的)A process does not request all of its required resources at one timeConditions for DeadlockNo preemption(非剥夺性排他性访问资源)If a process holding certain resources is denied a further request, that process must not release its original resourcesIf a process requests a resource that is currently held by another process, the operating system is not allowed to preempt the second process and require it to release its resourcesConditions for DeadlockCircular wait(循环等待在进程资源图中有环路)Possibility of DeadlockMutual ExclusionNo preemptionHold and waitExistence of DeadlockMutual ExclusionNo preemptionHold and waitCircular waitNecessary condition6.2 Deadlock PreventionIndirect method: prevent the occurrence of one of the three necessary conditions(items 1 through 3)Direct method:prevent the occurrence of a circular wait(item 4)1、Mutual exclusionCannot be disallowed2、Hold and Wait静态分配：Resources are allocated statically, dynamic requests are not permitted.Inefficient:Be held up for a long time waiting for all its resourceResource allocated to a process may remain unused for a long time3、No Preemption剥夺调度：When request further resource, release its original resources first; operating system is allowed to preempt the resources held by other process.Only applied to processor or memory4、Circular wait层次分配：define a linear ordering of resource types and allocate them according to the order6.3 Deadlock AvoidanceAllows the three necessary conditions but make judicious choices to assure that the deadlock point is never reached.A decision is made dynamically whether the current resource allocation request will, if granted, potentially lead to a deadlockRequires knowledge of future process requestTwo Approaches to Deadlock AvoidanceDo not start a process if its demands might lead to deadlockDo not grant an incremental resource request to a process if this allocation might lead to deadlock银行家算法银行家算法银行家拥有一笔周转资金银行家拥有一笔周转资金客户一开始必须说明其最大需求客户一开始必须说明其最大需求客户要求分期贷款，如果客户能够得到各期贷客户要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款，否则就一定不能归款，就一定能够归还贷款，否则就一定不能归还贷款还贷款只要客户所要求的最大资金量不超过总周转资只要客户所要求的最大资金量不超过总周转资金，银行家总会在有限时间内满足其需求。金，银行家总会在有限时间内满足其需求。银行家应谨慎的贷款，防止出现坏帐银行家应谨慎的贷款，防止出现坏帐用银行家算法避免死锁用银行家算法避免死锁操作系统（银行家）操作系统（银行家）操作系统管理的资源操作系统管理的资源( (周转资金周转资金) )进程（要求贷款的客户）进程（要求贷款的客户）Single-resourceTotal resource: 10Cash=2P:2(4)Q:4(2)R:2(6)Cash=6P:2(4)R:2(6)Cash=8R:2(6)Cash=2P:2(4)Q:4(2)R:2(6)Cash=1P:4(2)Q:2(2)R:3(5)Cash=0P:5(1)Q:2(2)R:3(6)不死锁不死锁死锁死锁SafetySafetyunsafetyAnother example1、Process initiation denialOnlyRi C(n+1)i+ Cki 对i=1,.,m,k=1,.,n; A new process will be started.2、Resource Allocation DenialReferred to as the bankers algorithmState of the system is the current allocation of resources to processSafe state is where there is at least one sequence that does not result in deadlockUnsafe state is a state that is not safeBanker algorithm基本思想是：系统中的所有进程进入进程集合，在安全基本思想是：系统中的所有进程进入进程集合，在安全状态下系统收到一个进程的资源请求后，先把资源试探性状态下系统收到一个进程的资源请求后，先把资源试探性分配给它。现在，系统用剩下的可用资源和每个进程集合分配给它。现在，系统用剩下的可用资源和每个进程集合中其他进程还要的资源数作比较，在进程集合中找到剩余中其他进程还要的资源数作比较，在进程集合中找到剩余资源能满足最大需求量的进程，从而，保证这个进程运行资源能满足最大需求量的进程，从而，保证这个进程运行完毕并归还全部资源。这时，把这个进程从集合中去掉，完毕并归还全部资源。这时，把这个进程从集合中去掉，系统的剩余资源更多了，再反复执行上述步骤。最后，检系统的剩余资源更多了，再反复执行上述步骤。最后，检查进程集合，若为空表明本次申请可行，系统处于安全状查进程集合，若为空表明本次申请可行，系统处于安全状态，可真正实施本次分配；否则，只要有进程执行不完，态，可真正实施本次分配；否则，只要有进程执行不完，系统便处于不安全状态，本次资源分配暂不实施，让申请系统便处于不安全状态，本次资源分配暂不实施，让申请进程等待进程等待设设RequestRequest是进程是进程PiPi的请求向量。如果的请求向量。如果Requestj=k,Requestj=k,表表示进程示进程PiPi需要需要k k个个RiRi类型的资源，进程类型的资源，进程PiPi发出请求后，系统发出请求后，系统按下述步骤进行检查：按下述步骤进行检查：(1)(1)如果如果RequestjClaimij-Allocij,RequestjClaimij-Allocij,认为出认为出错，因为所需资源数超过了它所宣布的最大值；否则转错，因为所需资源数超过了它所宣布的最大值；否则转(2).(2).(2)(2)如果如果RequestjAvailablej,RequestjAvailablej,目前尚无足够资源目前尚无足够资源分配，等待；否则转分配，等待；否则转(3)(3)。(3)(3)系统尝试将所需资源分配给系统尝试将所需资源分配给PiPi，并修改以下数据结，并修改以下数据结构中的值：构中的值： Availablej=Availablej-Requestj;Availablej=Availablej-Requestj; Allocij=Allocij+Requestj; Allocij=Allocij+Requestj;(4)(4)进行安全性检查。如果进行了此次资源分配后，系进行安全性检查。如果进行了此次资源分配后，系统仍处于安全状态，则分配，否则，尝试分配作废，恢复统仍处于安全状态，则分配，否则，尝试分配作废，恢复原来数值，让进程原来数值，让进程PiPi等待。等待。Safety check定义工作向量定义工作向量currentavail currentavail 和布尔型标志和布尔型标志possiblepossible；初始化初始化 currentavail:=available,possible:=truecurrentavail:=available,possible:=true；保持保持possible:=truepossible:=true，从进程集合，从进程集合rest rest 中找出中找出claimk,*-allocationk,*currentavail claimk,*-allocationk,*currentavail 的进程来，如找到，则释放这个进程的进程来，如找到，则释放这个进程P Pk k 的全部资源、的全部资源、执行以下操作执行以下操作 currentavail:=currentavail+allocationk,*currentavail:=currentavail+allocationk,*，把，把P Pk k 从进程集合中去掉从进程集合中去掉rest:=rest-Prest:=rest-Pk k ；否则否则Possible:=falsePossible:=false，停止执行算法；，停止执行算法；最后查看进程集最后查看进程集restrest，若为空集返回安全标记；否则，若为空集返回安全标记；否则返回不安全标记。返回不安全标记。Determination of a Safe StateInitial StateDetermination of a Safe StateP2 Runs to CompletionDetermination of a Safe StateP1 Runs to CompletionDetermination of a Safe StateP3 Runs to CompletionDetermination of an Unsafe StateDetermination of an Unsafe StateDeadlock Avoidance LogicDeadlock Avoidance LogicDeadlock AvoidanceMaximum resource requirement must be stated in advanceProcesses under consideration must be independent; no synchronization requirementsThere must be a fixed number of resources to allocateNo process may exit while holding resources6.4 Deadlock Detection定义布尔型向量possiblek，k=1,.,n。检测死锁算法如下：（1）标记Allocationk,*全为0的进程，即possiblek:=true;(2)currentavail:=available；（3）在rest 中查每一个进程Pk,如果claimk,*-allock,*=0，则possiblek:=true；否则possiblek:=false；这里k=1,.,n。（4）在rest 中找一个进程Pk，需满足条件：possiblek=false&(request*currentavail)找到这样的Pk 便转（5）；否则转（6）；（5）currentavail:=currentavail+allocation；possiblek:=true；然后转（4）；(6) 如果对k=1,.,n 若possiblek=true 不成立，那么，系统出现了死锁，并且possiblek=false 的Pk 为死锁进程。Strategies once Deadlock DetectedAbort all deadlocked processesBack up each deadlocked process to some previously defined checkpoint, and restart all processoriginal deadlock may occurSuccessively abort deadlocked processes until deadlock no longer existsSuccessively preempt resources until deadlock no longer existsSelection Criteria Deadlocked ProcessesLeast amount of processor time consumed so farLeast number of lines of output produced so farMost estimated time remainingLeast total resources allocated so farLowest priorityStrengths and Weaknesses of the Strategies6.5 An integrated deadlock strategyGroup resources into a number of different resource classesUse the linear ordering strategy defined previously for the prevention of circular wait to prevent deadlocks between recourse classesWithin a resource class,use the algorithm that is most appropriate for that classAn exampleresourcesSwappable space: on secondary storage for use in swapping processesProcess resource:assignable devices,such as tape drives,and filesMain memory:Internal resources:such as I/O channelstrategiesSwappable space: allocated at one time,or deadlock avoidanceProcess resource: deadlock avoidance,or resource orderingMain memory:prevention by preemptionInternal resources:prevention by means of resource orderingUNIX Concurrency MechanismsPipesMessagesShared memorySemaphoresSignalsSolaris Thread Synchronization PrimitivesMutual exclusion (mutex) locksSemaphoresMultiple readers, single writer (readers/writer) locksCondition variablesWindows 2000 Concurrency MechanismsProcessThreadFileConsole inputFile change notificationMutexSemaphoreEventWaitable timer