操作系统原理：CH08_Deadlock

Module 8:Deadlocks（死锁）nSystem Model（系统模型）系统模型）nDeadlock Characterization（死锁特征）（死锁特征）nMethods for Handling Deadlocks（处理死锁的方（处理死锁的方法）法）nDeadlock Prevention（预防死锁）（预防死锁）nDeadlock Avoidance（死锁避免）（死锁避免）nDeadlock Detection（死锁检测）（死锁检测）nRecovery from Deadlock（死锁恢复）（死锁恢复）nCombined Approach to Deadlock Handling（综合处理（综合处理方法）方法）The Deadlock Problem（死锁问题）nA set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set.（一组等待的进程，其中每一个进程都持有资源，并且（一组等待的进程，其中每一个进程都持有资源，并且等待着由这个组中其他进程所持有的资源）等待着由这个组中其他进程所持有的资源）n死锁死锁Deadlock：计算机系统中多道程序并发执行时，：计算机系统中多道程序并发执行时，两个或两个以上的进程由于竞争资源而造成的一种互相两个或两个以上的进程由于竞争资源而造成的一种互相等待的现象（僵局），如无外力作用，这些进程将永远等待的现象（僵局），如无外力作用，这些进程将永远不能再向前推进。不能再向前推进。The Deadlock ProblemnExample 1nSystem has 2 tape drives.（系统有两个磁带设备）（系统有两个磁带设备）nP1 and P2 each hold one tape drive and each needs another one.（进程（进程P1和和P2各占有一个磁带设备并且实际各占有一个磁带设备并且实际需要两个磁带）需要两个磁带）nExample 2nsemaphores A and B,initialized to 1（信号量信号量A，B初始初始化为化为1）P0 P1wait(A);wait(B)wait(B);wait(A)n如果一个进程要使用如果一个进程要使用OS管理的资源，需先向系统提出管理的资源，需先向系统提出申请，如果有可用资源，系统才进行分配。申请，如果有可用资源，系统才进行分配。n资源的分类资源的分类,根据资源性质：根据资源性质：n可抢占资源可抢占资源指资源占有进程虽然需要使用该资源，指资源占有进程虽然需要使用该资源，但另一个进程却可强行把资源从占有者进程处抢来。但另一个进程却可强行把资源从占有者进程处抢来。n不可抢占资源不可抢占资源指只有占用者进程不再需要使用该指只有占用者进程不再需要使用该资源而主动释放资源外，其它进程不得在占有者进资源而主动释放资源外，其它进程不得在占有者进程使用资源过程中强行抢占。程使用资源过程中强行抢占。n根据使用方式：共享资源和独占资源。根据使用方式：共享资源和独占资源。n根据使用期限；永久资源和临时性资源根据使用期限；永久资源和临时性资源。资源资源共享共享:CPU、主存、硬盘主存、硬盘独占独占:打印机，读卡机，磁带驱动器打印机，读卡机，磁带驱动器可顺序重复使用的资源可顺序重复使用的资源由一个进程产生，被另外一个进程使用短暂时间由一个进程产生，被另外一个进程使用短暂时间之后便无用的资源之后便无用的资源Bridge Crossing Example（过桥的例子）nTraffic only in one direction.（只有一个方向）（只有一个方向）nEach section of a bridge can be viewed as a resource.（桥的每一个部分都可以看成资源）（桥的每一个部分都可以看成资源）nIf a deadlock occurs,it can be resolved if one car backs up(preempt resources and rollback).（如果死锁发生，它可以由一辆车返回而解决，抢占资源并（如果死锁发生，它可以由一辆车返回而解决，抢占资源并回退）回退）nSeveral cars may have to be backed upif a deadlock occurs.（如果死锁发生，可能很多车都不得不返回）（如果死锁发生，可能很多车都不得不返回）nStarvation is possible.（有可能产生饥饿）（有可能产生饥饿）死锁的原因和条件n竞争资源引起死锁竞争资源引起死锁n当系统中供多个进程所使用的资源，不足以同时满足它们的需要当系统中供多个进程所使用的资源，不足以同时满足它们的需要时，引起它们对资源的竞争而产生死锁时，引起它们对资源的竞争而产生死锁n进程推进顺序不当引起死锁进程推进顺序不当引起死锁n在多道程序系统中，并发执行的进程推进序列不可予测在多道程序系统中，并发执行的进程推进序列不可予测n有些推进顺序，进程可以顺利完成有些推进顺序，进程可以顺利完成n有的推进顺序会引起进程无限期地等待永远不会发生的条件而不有的推进顺序会引起进程无限期地等待永远不会发生的条件而不能向前推进，造成死锁能向前推进，造成死锁P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)进程进程P1、P2并发执行。并发执行。资源资源R1、R2各有一个各有一个曲线曲线4将进入不安全区域（进程推将进入不安全区域（进程推进顺序非法）进顺序非法）P1S1S3P2P3S2P1：Release(S1);Request(S3)P2：Release(S2);Request(S1)P3：Release(S3);Request(S2)不可能发生死锁不可能发生死锁P1：Request(S3);Release(S1)P2：Request(S1);Release(S2)P3：Request(S2);Release(S3)可能发生死锁可能发生死锁S1、S2、S3是临时资源是临时资源Deadlock Characterization（死锁的特性）nMutual exclusion:only one process at a time can use a resource.（互斥：一次只有一个进程可以使用一（互斥：一次只有一个进程可以使用一个资源）个资源）nHold and wait:a process holding at least one resource is waiting to acquire additional resources held by other processes.（占有并等待：一个至少持有一个资源的进程等待获得额（占有并等待：一个至少持有一个资源的进程等待获得额外的由其他进程所持有的资源）外的由其他进程所持有的资源）(请求与保持请求与保持)Deadlock can arise if four conditions hold simultaneously.（四个条件同时出现，死锁将会发生）（四个条件同时出现，死锁将会发生）Deadlock Characterization（死锁的特性）nNo preemption:a resource can be released only voluntarily by the process holding it,after that process has completed its task.（不可抢占：一个资源只有当持有它的进程完成任务后，自由的不可抢占：一个资源只有当持有它的进程完成任务后，自由的释放）释放）(非剥夺非剥夺)nCircular wait:there exists a set P0,P1,P0 of waiting processes such that P0 is waiting for a resource that is held by P1,P1 is waiting for a resource that is held by P2,Pn1 is waiting for a resource that is held by Pn,and P0 is waiting for a resource that is held by P0.（循环等待：等待（循环等待：等待资源的进程之间存在环）资源的进程之间存在环）System Model（系统模型）nResource types（资源类型）（资源类型）R1,R2,.,Rm CPU cycles,memory space,I/O devices（CPU周期，内存空间，周期，内存空间，I/O设备）设备）nEach resource type Ri has Wi instances.（每一种资源（每一种资源Ri有有Wi 种实例）种实例）nEach process utilizes a resource as follows（每一个进程如下的利用资源）（每一个进程如下的利用资源）nrequest（申请）（申请）nuse（使用）（使用）nRelease（释放）（释放）Resource-Allocation Graph（资源分配图）nV is partitioned into two types:（V被分为两个部分）被分为两个部分）nP=P1,P2,Pn,the set consisting of all the processes in the system.（P：含有系统中全部的进：含有系统中全部的进程）程）nR=R1,R2,Rm,the set consisting of all resource types in the system.（R：含有系统中全部：含有系统中全部的资源）的资源）nrequest edge directed edge P1 Rj（请求边：直接请求边：直接P1 Rj）nassignment edge directed edge Rj Pi（分配边：分配边：P1 Rj）A set of vertices V and a set of edges E.（一个顶点的集合（一个顶点的集合V和边的集合和边的集合E）Resource-Allocation Graph(Cont.)资源分配图续nProcess进程进程nResource Type with 4 instances有四个实例的资源类有四个实例的资源类型型nPi requests instance of Rj（Pi 请求一个请求一个Rj的实例）的实例）nPi is holding an instance of Rj（Pi 持有一个持有一个Rj的实例）的实例）PiPiRjRjExample of a Resource Allocation Graph资源分配图的例子Resource Allocation Graph With A Deadlock有死锁的资源分配图Resource Allocation Graph With A Cycle But No Deadlock有环但没有死锁的资源分配图Basic Facts（基本事实）nIf graph contains no cycles no deadlock.n（如果图没有环，那么不会有死锁）（如果图没有环，那么不会有死锁）nIf graph contains a cycle（如果图有环）（如果图有环）nif only one instance per resource type,then deadlock.（如果每一种资源类型只有一个实例，那么死锁发（如果每一种资源类型只有一个实例，那么死锁发生）生）nif several instances per resource type,possibility of deadlock.（如果一种资源类型有多个实例，可能死锁）（如果一种资源类型有多个实例，可能死锁）Methods for Handling Deadlocks处理死锁的方法n忽略、预防、避免、检测、解除忽略、预防、避免、检测、解除nIgnore the problem and pretend that deadlocks never occur in the system;used by most operating systems,including UNIX.（忽略这个问（忽略这个问题，假装系统中从未出现过死锁。这个方法被大部分的题，假装系统中从未出现过死锁。这个方法被大部分的操作系统采用，包括操作系统采用，包括UNIX）鸵鸟策略）鸵鸟策略nEnsure that the system will never enter a deadlock state.（确保系统永远不会进入死锁状态）预防死锁，避免死锁（确保系统永远不会进入死锁状态）预防死锁，避免死锁nAllow the system to enter a deadlock state and then recover.（允许系统进入死锁状态，然后恢复系统）死锁检测（允许系统进入死锁状态，然后恢复系统）死锁检测鸵鸟策略n象鸵鸟一样对死锁视而不见n处理死锁的代价很大，而且常常给用户带来许多不便的限制。n大多数用户宁可在极偶然的情况下发生死锁，也不愿限制每个用户只能创建一个进程、只能打开一个文件等等。n于是不得不在方便性和正确性之间作出折衷。Deadlock Prevention（死锁的预防）nMutual Exclusion not required for sharable resources;must hold for nonsharable resources.（互斥：共享资源不是必须的，必须保持非共享资源）（互斥：共享资源不是必须的，必须保持非共享资源）nHold and Wait must guarantee that whenever a process requests a resource,it does not hold any other resources.（占有并等待：必须保证进程申请资源的时候没有占有其他资源）（占有并等待：必须保证进程申请资源的时候没有占有其他资源）nRequire process to request and be allocated all its resources before it begins execution,or allow process to request resources only when the process has none.（要求进程在执行前一次申请全部的资源，只有没有占有资（要求进程在执行前一次申请全部的资源，只有没有占有资源时才可以分配资源）源时才可以分配资源）nLow resource utilization;starvation possible.（利用率低，可能出现饥饿）（利用率低，可能出现饥饿）Restrain the ways request can be made.（抑制死锁发生的必要条件）（抑制死锁发生的必要条件）Deadlock Prevention(Cont.)死锁的预防（续）nNo Preemption（非抢占）（非抢占）nIf a process that is holding some resources requests another resource that cannot be immediately allocated to it,then all resources currently being held are released.（如果一个进程的申（如果一个进程的申请没有实现，它要释放所有占有的资源）请没有实现，它要释放所有占有的资源）nPreempted resources are added to the list of resources for which the process is waiting.（先占的资源放入进程等待资源列表先占的资源放入进程等待资源列表中）中）nProcess will be restarted only when it can regain its old resources,as well as the new ones that it is requesting.（进程在有新的资源请求时，若能够重新得到旧的资源，可以重新开始）（进程在有新的资源请求时，若能够重新得到旧的资源，可以重新开始）nNo Preemption（非抢占）另外一种解决方案（非抢占）另外一种解决方案:n当进程当进程A提出资源申请时提出资源申请时,首先检查这些资源是否可用首先检查这些资源是否可用n是是,则分配之则分配之,否则检查这些资源是否已分配给了另外的进程否则检查这些资源是否已分配给了另外的进程(而这个进程又在等待其他的资源而这个进程又在等待其他的资源)n如果存在这样的进程如果存在这样的进程B,从进程从进程B剥夺进程剥夺进程A所需的资源分配给所需的资源分配给进程进程A使用使用.相反相反,则进程则进程A等待等待,当进程当进程A在等待的过程中在等待的过程中,它所它所持有资源可能会被剥夺分配给其他的进程持有资源可能会被剥夺分配给其他的进程.这样这样,进程进程A只有得只有得到了它正在申请有资源以及等待过程中被剥夺的资源后到了它正在申请有资源以及等待过程中被剥夺的资源后,才能才能恢复运行恢复运行.nCircular Wait impose a total ordering of all resource types,and require that each process requests resources in an increasing order of enumeration.（循环等待：将所有（循环等待：将所有的资源类型放入资源列表中，并且要求进程按照资源表申请资源）的资源类型放入资源列表中，并且要求进程按照资源表申请资源）n所有进程对资源的请求必须严格按资源序号递增的次序提出。所有进程对资源的请求必须严格按资源序号递增的次序提出。n总有一个进程占据了较高序号的资源，它继续请求的资源必总有一个进程占据了较高序号的资源，它继续请求的资源必然是空闲的，可以一直向前推进。然是空闲的，可以一直向前推进。n在资源分配图中不可能出现环路，因而摒弃了在资源分配图中不可能出现环路，因而摒弃了“环路等待环路等待”条件条件n这种策略可以提高资源利用率，但在进程使用各类资源的顺这种策略可以提高资源利用率，但在进程使用各类资源的顺序与系统规定的顺序不同时会造成资源浪费的情况。序与系统规定的顺序不同时会造成资源浪费的情况。n上述预防死锁的方法通过限制资源请求来打破死锁的四个必要条件之一，从而预防死锁的发生。n其可能的副作用：n降低设备利用率和吞吐量n可能有进程饥饿Deadlock Avoidance（死锁避免）n允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性n若此次分配不会导致系统从安全状态向不安全状态转换，便可将资源分配给进程；否则不分配资源，进程必须阻塞等待。Safe Staten安全状态安全状态是指系统的一种状态，在此状态下是指系统的一种状态，在此状态下,系统系统能按某种顺序（例如能按某种顺序（例如P P1 1、P P2 2P Pn n）来为各个进程来为各个进程分配其所需资源，直至最大需求，使每个进程都可分配其所需资源，直至最大需求，使每个进程都可顺序地一个个地完成。这个序列（顺序地一个个地完成。这个序列（P P1 1、P P2 2.P Pn n）称为称为安全序列安全序列。n若某一时刻不存在一个安全序列，则称系统处于不若某一时刻不存在一个安全序列，则称系统处于不安全状态。安全状态。Safe State（安全状态）nWhen a process requests an available resource,system must decide if immediate allocation leaves the system in a safe state.（当进程申请一个有效的资源的时候，系统必须确定分配后是安全的）（当进程申请一个有效的资源的时候，系统必须确定分配后是安全的）nSystem is in safe state if there exists a safe sequence of all processes.（如果存在一个安全序列系统处于安全态）（如果存在一个安全序列系统处于安全态）nSequence is safe if for each Pi,the resources that Pi can still request can be satisfied by currently available resources+resources held by all the Pj,with j P2 4 2 2 =因为找不到一个安全序列使所有进程顺序地一个个地运行完毕，所以T1状态是不安全状态，由于实施分配给1台磁带机给P3的操作会引起系统状态由安全状态T0向不安全状态下的转换，所以为了避免死锁，上述的分配只是安全检测，检测后判定这样的申请不能满足，P3为申请1台磁带机而必须阻塞等待。Basic Facts（基本事实）nIf a system is in safe state no deadlocks.（如果一个系统在安全状态，就没有死锁）（如果一个系统在安全状态，就没有死锁）nIf a system is in unsafe state possibility of deadlock.（如果一个系统不是处于安全状态，就有可能死锁）（如果一个系统不是处于安全状态，就有可能死锁）nAvoidance ensure that a system will never enter an unsafe state.（避免：确保系统永远不会进入死锁状态）（避免：确保系统永远不会进入死锁状态）Safe,unsafe,deadlock state spaces安全、不安全、死锁状态空间Deadlock Avoidance（死锁避免）nSimplest and most useful model requires that each process declare the maximum number of resources of each type that it may need.（一个简单而有效的模型要求每（一个简单而有效的模型要求每一个进程声明它所需要的资源的最大数）一个进程声明它所需要的资源的最大数）nThe deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition.（死锁避免（死锁避免算法动态检查资源分配状态以确保不会出现循环等待的情况）算法动态检查资源分配状态以确保不会出现循环等待的情况）nResource-allocation state is defined by the number of available and allocated resources,and the maximum demands of the processes.（资源分配状态定义为可用的与（资源分配状态定义为可用的与已分配的资源数，和进程所需的最大资源量）已分配的资源数，和进程所需的最大资源量）Requires that the system has some additional a priori information available.（需要系统有一些额外的信息）（需要系统有一些额外的信息）nSingle instance of a resource type 资源有单个实例nUse a resource-allocation graph资源分配图nMultiple instances of a resource type 资源有多个实例n Use the bankers algorithm银行家算法Resource-Allocation Graph Algorithm资源分配图算法nClaim edge Pi Rj indicated that process Pj may request resource Rj;represented by a dashed line.(claim edge 申请边申请边Pi Rj代表进程代表进程Pi可能会申请资源可能会申请资源Ri，表示为虚线），表示为虚线）nClaim edge converts to request edge when a process requests a resource.（一个进程申请资源的（一个进程申请资源的时候，申请边转化为请求边）时候，申请边转化为请求边）nWhen a resource is released by a process,assignment edge reconverts to a claim edge.（当（当资源被进程释放的时候，分配边转化为申请边）资源被进程释放的时候，分配边转化为申请边）nResources must be claimed a priori in the system.（系统中的资源必须被事先声明）（系统中的资源必须被事先声明）n当一个进程Pi 申请资源Rj时，由循环检测算法来检查:n如果把图中的申请边Pi Rj转为分配边Rj Pi，图中是否会出现环路，只有不出现环路，才实施资源分配。Resource-Allocation Graph For Deadlock Avoidance死锁避免的资源分配图Unsafe State In A Resource-Allocation Graph不安全的状态图Bankers Algorithm（银行家算法）nMultiple instances.（多个实例）（多个实例）nEach process must a priori claim maximum use.（每一个进程必须事先声明使用的最大量）（每一个进程必须事先声明使用的最大量）nWhen a process requests a resource it may have to wait.（当一个进程请求资源，它可能要等待）（当一个进程请求资源，它可能要等待）nWhen a process gets all its resources it must return them in a finite amount of time.（当一个进程得到所有的资源，它必须在有限的时间（当一个进程得到所有的资源，它必须在有限的时间释放它们）释放它们）Data Structures for the Bankers Algorithm银行家算法的数据结构 nAvailable:Vector of length m.If available j=k,there are k instances of resource type Rj available.（如果（如果availablej=k,那么资源那么资源Rj有有k个实例有效）个实例有效）nMax:n x m matrix.If Max i,j=k,then process Pi may request at most k instances of resource type Rj.（如果（如果Maxi,j=k,那么进程那么进程Pi可以最多请求资源可以最多请求资源Rj的的k个个实例）实例）Let n=number of processes,and m=number of resources types.N为进程的数目，为进程的数目，M为资源类型的数目为资源类型的数目nAllocation:n x m matrix.If Allocationi,j=k then Pi is currently allocated k instances of Rj.（如果（如果Allocationi,j=k,那么进程那么进程Pj当前分配了当前分配了k个个资源资源Rj的实例）的实例）nNeed:n x m matrix.If Needi,j=k,then Pi may need k more instances of Rj to complete its task.（如果（如果Needi,j=k,那么进程那么进程Pi 还需要还需要k个资源个资源Rj的的实例）实例）Need i,j=Maxi,j Allocation i,j.Data Structures for the Bankers Algorithm银行家算法的数据结构 Safety Algorithm（安全算法）1.Let Work and Finish be vectors of length m and n,respectively.Initialize（让（让Work和和Finish作为长度为作为长度为m和和n的向量）的向量）Work:=AvailableFinish i=false for i-1,3,n.2.Find and i such that both:（找到（找到i）(a)Finish i=false(b)Needi WorkIf no such i exists,go to step 4.3.Work:=Work+AllocationiFinishi:=truego to step 2.4.If Finish i=true for all i,then the system is in a safe state.Resource-Request Algorithm for Process Pi进程Pi的资源请求 Requesti=request vector for process Pi.If Requesti j=k then process Pi wants k instances of resource type Rj.1.If Requesti Needi go to step 2.Otherwise,raise error condition,since process has exceeded its maximum claim.2.If Requesti Available,go to step 3.Otherwise Pi must wait,since resources are not available.3.Pretend to allocate requested resources to Pi by modifying the state as follows:Available:=Available Requesti;Allocationi:=Allocationi+Requesti;Needi:=Needi Requesti;4.用安全算法进行检查用安全算法进行检查,看系统是否处于安全状态看系统是否处于安全状态If safe the resources are allocated to Pi.If unsafe Pi must wait,and the old resource-allocation state is restoredExample of Bankers Algorithm银行家算法的例子n5 processes P0 through P4;3 resource types A(10 instances),B(5instances,and C(7 instances).（5个进程个进程P0到到P4:3个资源类型个资源类型A(10个实例），个实例），B（5个实例），个实例），C（7个实例）个实例）nSnapshot at time T0:（时刻（时刻T0的片段）的片段）Allocation Max AvailableA B CA B C A B CP00 1 07 5 3 3 3 2 P12 0 0 3 2 2 P23 0 2 9 0 2 P32 1 1 2 2 2 P40 0 24 3 3 Example(Cont.)（例子续）nThe content of the matrix.Need is defined to be Max Allocation.（矩阵的内容。需要被定义为最大值）（矩阵的内容。需要被定义为最大值）NeedA B C P07 4 3 P11 2 2 P26 0 0 P30 1 1 P44 3 1 nThe system is in a safe state since the sequence satisfies safety criteria.（系统在安全的（系统在安全的状态因为序列状态因为序列P1,P3,P4,P2,P0满足了安全的标准）满足了安全的标准）n用安全检测算法看能否找到一个安全序列用安全检测算法看能否找到一个安全序列nWork=available=(3,3,2)nFinishi=false (i=0.4)n n Work need allocation finishn P1 3 3 2 1 2 2 2 0 0 Tn P3 5 3 2 0 1 1 2 1 1 Tn P4 7 4 3 4 3 1 0 0 2 Tn P2 7 4 5 6 0 0 3 0 2 Tn P0 10 4 7 7 4 3 0 1 0 Tn存在安全序列：（存在安全序列：（P1，P3，P4，P2，P0）Example(Cont.)n通常，安全序列不是唯一的通常，安全序列不是唯一的nWork=available=(3,3,2)nFinishi=false (i=0.4)n n Work need allocation finishn P3 3 3 2 0 1 1 2 1 1 Tn P4 5 4 3 4 3 1 0 0 2 Tn P1 5 4 5 1 2 2 2 0 0 Tn P2 7 4 5 6 0 0 3 0 2 Tn P0 10 4 7 7 4 3 0 1 0 Tn安全序列：（安全序列：（P3，P4，P1，P2，P0）Example(Cont.)Example(Cont.):P1 request(1,0,2)例子续nCheck that Request Available(that is,(1,0,2)(3,3,2)true.(检查请求小于有效（就是说，检查请求小于有效（就是说，(1,0,2)(3,3,2)为真）为真）AllocationNeedAvailableA B CA B CA B C P00 1 0 7 4 3 2 3 0P13 0 20 2 0 P23 0 2 6 0 0 P32 1 1 0 1 1P40 0 2 4 3 1 nExecuting safety algorithm shows that sequence satisfies safety requirement.（执行安全算法表明序列p1,p3,p4,p0,p2满足要求）nCan request for(3,3,0)by P4 be granted?（p4的(3,3,0)可以通过？）nCan request for(0,2,0)by P0 be granted?（p0的(0,2,0)可以通过？）Deadlock Detection（死锁检测）nAllow system to enter deadlock state（允（允许进入死锁状态）许进入死锁状态）nDetection algorithm（检测死锁）（检测死锁）nRecovery scheme（恢复策略）（恢复策略）Single Instance of Each Resource Type每一种资源类型只有一个实例nMaintain wait-for graph（维护等待图）（维护等待图）nNodes are processes.（节点是进程）（节点是进程）nPi Pj if Pi is waiting for Pj.（Pi Pj表明表明Pi在等在等待待Pj.）nPeriodically invoke an algorithm that searches for acycle in the graph.（定期调用算法来检查是否有环）（定期调用算法来检查是否有环）nAn algorithm to detect a cycle in a graph requires an order of n2 operations,where n is the number of vertices in the graph.（一个检查图中是否有环的算（一个检查图中是否有环的算法需要法需要n2的操作来进行，的操作来进行，n为图中的节点数）为图中的节点数）Resource-Allocation Graph And Wait-for Graph资源分配图和等待图Resource-Allocation GraphCorresponding wait-for graphSeveral Instances of a Resource Type一个资源类型的多个实例nAvailable:A vector of length m indicates the number of available resources of each type.（可用：一个长度（可用：一个长度m的向量代表每种资源类型的有效数目）的向量代表每种资源类型的有效数目）nAllocation:An n x m matrix defines the number of resources of each type currently allocated to each process.（分配：一个（分配：一个n x m 的矩阵定义了当前分配的每一种资源类型的实的矩阵定义了当前分配的每一种资源类型的实例数目）例数目）nRequest:An n x m matrix indicates the current request of each process.If Request i,j=k,then process Pi is requesting k more instances of resource type.Rj.（请求：一个（请求：一个n x m 的矩阵使命了当前的进程请求。如果的矩阵使命了当前的进程请求。如果Requesti,j=k,那么进程那么进程Pi请求请求k个个Rj资源的实例）资源的实例）Detection Algorithm(检测算法）1.Let Work and Finish be vectors of length m and n,respectively Initialize(让让Work和和Finish作为长度为作为长度为m和和n的向量）的向量）(a)Work:=Available(b)For i=1,2,n,if Allocationi 0,then Finishi:=false;otherwise,Finishi:=true.2.Find an index i such that both（找到下标（找到下标i）(a)Finishi=false(b)Requesti WorkIf no such i exists,go to step 4.（如果没有这样的（如果没有这样的i存存在，转在，转4）Detection Algorithm(Cont.)3.Work:=Work+AllocationiFinishi:=truego to step 2.4.If Finishi=false,for some i,1 i n,then the system is in deadlock state.Moreover,if Finishi=false,then Pi is deadlocked.Algorithm requires an order of m x n2 operations to detect whether the system is in deadlocked state.算法需要算法需要m x n2 的操作来判断是否系统处于死锁状态Example of Detection Algorithm检测算法的例子nFive processes P0 through P4;three resource types A(7 instances),B(2 instances),and C(6 instances).（五个进程p0到p4,三个资源类型A（7个实例），B（2个实例）,C（6个实例）nSnapshot at time T0（时刻Tn的状态）AllocationRequestAvailableA B C A B C A B CP00 1 0 0 0 0 0 0 0P12 0 0 2 0 2P23 0 30 0 0 P32 1 1 1 0 0 P40 0 2 0 0 2nSequence will result in Finishi=true for all i.Example(Cont.)（例子续）nP2 requests an additional instance of type C.（P2请求C的实例）RequestA B C P00 0 0 P12 0 1P20 0 1P31 0 0 P40 0 2nState of system?（系统的状态）nCan reclaim resources held by process P0,but insufficient resources to fulfill other processes;requests.（可以归还P0所有的资源，但是资源不够完成其他进程的请求）nDeadlock exists,consisting of processes P1,P2,P3,and P4.（死锁存在，包括进程P1,P2,P3和P4)Detection-Algorithm Usage检测算法的应用nWhen,and how often,to invoke depends on:（何时，如何频度的调用取决于）何时，如何频度的调用取决于）nHow often a deadlock is likely to occur?（死锁可能发生的频度）（死锁可能发生的频度）nHow many processes will need to be rolled back?（多少进程可能需要反转）（多少进程可能需要反转）none for each disjoint cycle（每一个独立的环需要一个）（每一个独立的环需要一个）nIf detection algorithm is invoked arbitrarily,there may be many cycles in the resource graph and so we would not be able to tell which of the many deadlocked processes“caused”the deadlock.（如果检测算法被随意的调用，可能图中存在很多的环以至于我们无（如果检测算法被随意的调用，可能图中存在很多的环以至于我们无法判断是哪一个进程引起了死锁的发生）法判断是哪一个进程引起了死锁的发生）n只有某个进程的资源申请不能马上满足时，才有可能产生死锁。所以，一种策略是只要有进程的资源申请不能得到满足，就调用检测算法。但这种策略的代价太高。n一种可行的策略是周期性地调用。比如，每小时一次，或当CPU利用率降低至40%。Recovery from Deadlock:Process Termination从死锁中恢复：进程终止nAbort all deadlocked processes.（终止所有的死（终止所有的死锁进程）锁进程）nAbort one process at a time until the deadlock cycle is eliminated.（一次终止一个进程直到死锁环消失）（一次终止一个进程直到死锁环消失）nIn which order should we choose to abort?（选（选择终止顺序）择终止顺序）nPriority of the process.（进程的优先级（进程的优先级)nHow long process has computed,and how much longer to completion.（进程计算了多少（进程计算了多少时间，还需要多长时间）时间，还需要多长时间）nResources the process has used.（进程使用的进程使用的资源）资源）nResources process needs to complete.（进程完成还需要多少资源）（进程完成还需要多少资源）nHow many processes will need to be terminated.（多少个进程需要被终止）（多少个进程需要被终止）nIs process interactive or batch?（进程是交互的还是批处理）（进程是交互的还是批处理）Recovery from Deadlock:Process Termination从死锁中恢复：进程终止Recovery from Deadlock:Resource Preemption从死锁中恢复：资源优先级nSelecting a victim minimize cost.（选择一个：最小化代价）（选择一个：最小化代价）nRollback return to some safe state,restart process fro that state.（回退：返回到安全的状态，然后重新开始进程）（回退：返回到安全的状态，然后重新开始进程）nStarvation same process may always be picked as victim,include number of rollback in cost factor.（饥饿：同一个进程可能总是被选中，包括在回退时）（饥饿：同一个进程可能总是被选中，包括在回退时）Combined Approach to Deadlock Handling综合死锁处理方式nCombine the three basic approaches（把三种方式组合起来）把三种方式组合起来）nPrevention（预防）（预防）nAvoidance（避免）（避免）nDetection（检测）（检测）allowing the use of the optimal approach for each of resources in the system.（允许使用优化的方式来使用系（允许使用优化的方式来使用系统中的资源）统中的资源）nPartition resources into hierarchically ordered classes.（把资源划分为不同的等级）（把资源划分为不同的等级）nUse most appropriate technique for handling deadlocks within each class.（对每一类使用适当的技术来处理死锁）（对每一类使用适当的技术来处理死锁）