77死锁

死锁死锁的定义资源的定义和分类解决死锁的策略分布式死锁的策略死锁的定义死锁(deadblock)是指两个或多个进程因无休止地互相等待永远不会成立的条件而形成的一种永久阻塞状态。一个进程集合是死锁的，如果集合中的每一个进程等待一个事件，该事件仅仅可以由集合中的另一个进程引起。死锁的定义一个计算机系统可以被抽象地表示为一个对偶(S,P)，其中S={所有的系统资源的全部可能的状态集合}P={进程集合}。S中的每个元素表示在资源分配中的一种可能的状态。P中的每个进程是一个函数，它将S中的每个系统状态映照到另一个状态集合（可能为空集合）。【例1】设S={S,T,U,V}及P={P1,P2}。P1(S)={T,U}P2(S)={U}P1(T)=P2(T)={S,V}P1(U)={V}P2(U)=P1(V)={U}P2(V)=死锁的定义我们可以用一个带标号的有向图中的节点（node）表示可能的状态，用有向弧表示可能的状态变化，而用有向弧旁的标号表示引起状态变化的进程。死锁的定义由进程i的一个操作将系统从状态S改变成状态T，我们将该操作缩写为S→i→T。在右图中我们有S→1→U，T→2→V等。如果存在进程i，j，…，k的一个操作序列使得有S→i→T，T→j→U，…，V→k→W，则我们将此该操作序列缩写为S→*→W，并且称从状态S可达到状态W。死锁的定义定义4.1如果不存在T使得S→i→T，则称进程Pi在状态S被阻塞(blocked)。进程P1在状态T被阻塞。定义4.2如果进程Pi在状态S被阻塞，并且对于所有满足S→*→T的状态T，进程Pi在状态T也被阻塞，则称进程Pi在状态S死锁（deadlocked）。进程P2在状态U和V死锁。进程P1在状态T不死锁，因为T→2→S不阻塞进程P1。死锁的定义定义4.3如果存在一个进程Pi在状态S死锁，则称状态S是一个死锁状态（deadlockstate）。状态U和V是死锁状态。定义4.4如果所有的进程Pi都在状态S死锁，则称状态S是一个完全死锁状态（totaldeadlockstate）。没有完全死锁状态。死锁的定义定义4.5如果状态S不是死锁状态并且对于任何从状态S可达到的状态T（即，S→*→T）都不是死锁状态，则称状态S是安全的（secure）。【例2】0：……do1：Request(D);2：……3：Request(T);4：……Release(T);5：……Release(D);od0：……do1：Request(T);2：……3：Request(D);4：……Release(D);5：……Release(T);od【例2】进程P1进程P20：不占用任何系统资源0:不占用任何系统资源1：不占用，申请D1：不占用，申请T2：占用D2：占用T3：占用D，申请T3：占用T，申请D4：占用D和T4：占用T和D5：占用D，T已释放5：占用T，D已释放进程执行顺序对引发死锁的影响系统状态图系统状态Sij表示进程P1处于状态Si，而进程P2处于状态Sj。水平方向的弧反映由于进程P1的操作所引起的状态变化，而垂直方向的弧反映由于进程P2的操作所引起的状态变化。进程P1在状态S14和S35被阻塞，但未死锁。进程P2在状态S41和S53被阻塞，但未死锁。系统状态图进程P1在状态S32死锁，进程P2在状态S23死锁，所以，状态S23和状态S32是死锁状态。进程P1和P2都在状态S33死锁，所以，状态S33是一个完全死锁状态。系统没有安全状态。死锁的例子P1P2P(S1);P(S2)临界区1......;临界区2......;P(S2);P(S1);临界区2......;临界区1......;V(S2);V(S1);V(S1);V(S2);死锁的例子P1P2......;......;Receive(P2,M);Receive(P1,M);......;......;Send(P2,M);Send(P1,M);......;......;死锁的例子P1P2Request(D);Reques(T);......;......;Request(T);Request(D);......;......;Release(T);Release(D);......;......;Release(D);Release(T);资源类型可重用性资源（reusable）和消耗性临时性资源（consumable）可重用性资源性质⑴存在一个固定的全部的详细清单。既不能创建也不能撤消增加的单位；⑵单位由进程从可供使用的单位的池中加以申请和获得，使用后，返回到池中供其它进程使用。可重用性资源的例子是处理机，输入/输出通道，主存和辅存，外设，总线等物理资源和诸如文件、数据库、互斥信号量等信息。消耗性资源性质⑴没有固定的全部的数目单位。单位可以被进程创建（产生或释放）或获得（消费）。⑵一个非阻塞的资源生产者可以发行任意个单位，然后，这些单位立即可供资源消费者使用。⑶一个获得的单位灭亡。消耗性资源的例子是中断和信号、消息及在输入/输出缓冲区中的信息等。解决死锁的策略死锁检测（deadlockdetection）死锁预防（deadlockprevention）死锁避免（deadlockavoidence）死锁恢复（deadlockrecovery）死锁检测即探查和识别死锁的方法。这种策略并不采取任何动作来使死锁不出现，而是系统事件触发执行一个检测算法。也即在系统运行过程中，及时地探查和识别死锁的存在，并识别出处于死锁之中的进程和资源等。死锁预防死锁预防是在系统运行之前，事先考虑防止死锁发生的对策，即在最初设计各种资源调度算法时，就没法防止在系统运行过程中可能产生的死锁。死锁避免死锁避免是在系统运行过程中注意避免死锁的发生。这就要求每当申请一个资源时，系统都应根据一定的算法判断是否认可这次申请，使得在今后一段时间内系统不会出现死锁。这面方最著名的算法首推Dijkstra[1965]提出的银行家(banker)算法。死锁的必要条件coffman[1971]提出⑴互斥使用（mutualexclusion）⑵占用并等待（resourceholdingandwaiting）⑶非抢占分配（nonpreemption）⑷部分地分配（partialallocation）或循环等待（circularwaiting）死锁预防Havender[1968]互斥使用假脱机Spooling占用并等待初始请求所有资源非抢占分配放弃资源部分地分配数值地给资源定序或循环等待死锁预防⑴每个进程必须一次性地请求它所需要的所有资源。若系统无法满足这一要求，则它不能执行。这是一种预分资源方法，它破坏了产生死锁的第三个必要条件。死锁预防⑵一个已占有资源的进程若要再申请新资源，它必须先释放已占资源。若随后它还需要它们，则需要重新提出申请。换言之，一个进程在使用某资源过程中可以放弃该资源，从而破坏了产生死锁的第二个必要条件。死锁预防⑶将系统中所有资源顺序编号，规定进程只能依次申请资源，这就是说，一个进程只有在前面的申请满足后，才能提出对其后面序号的资源的请求。这是一种有序使用资源法，它破坏了产生死锁的第四个必要条件。银行家（banker）算法一个可以避免死锁的调度算法是Dijkstra[1965]提出的银行家（banker）算法。这是以一个小镇上的银行家如何处理其顾客的存款为模型。假设有四位顾客A,B,C和D，每位顾客在银行中有如(a)所示的存款（一个单位为一万元）。银行家（banker）算法银行家知道不是所有的顾客立刻需要他们的最大存款，所以他仅保留10个单位而不是22个单位来为顾客服务。在这个模拟中银行家是操作系统，顾客是进程，存款是系统资源，譬如，是磁带机。银行家（banker）算法顾客们随时向银行家申请贷款（即请求资源）。在某一时刻，出现如(b)所示的情况。这个状态是安全的，因为，银行家用余下的2个单位推迟除C以外的请求，让C结束并释放他的所有的4个单位。银行家用这4个单位能够让B或D拥有必需的单位，等等。银行家（banker）算法(a)任何一个序列皆为安全序列。如A,B,C,D,A,D,C,B等。(b)C,D,B,A,C,D,A,B,C,B,D,A,C,B,A,D为安全序列。(c)不存在安全序列。银行家（banker）算法【定义】安全状态是指系统能按某种分配次序，例如P1,P2,…,Pn来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成。序列P1,P2,…,Pn称为安全序列。若系统不存在这样一个安全序列，则称系统处于不安全状态。银行家（banker）算法虽然并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进而进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁策略的实质就是如何使系统不进入不安全状态。银行家（banker）算法如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，B要求1，若系统分配1给B，则进入不安全状态，如图(C)所示。银行家（banker）算法考虑如果在(b)情况下，B再申请并得到1个单位，即出现如(c)所示的情况。这个状态是不安全的，因为，如果所有的顾客们突然都向银行家申请他们的全部贷款，银行家将不能满足他们中的任一位。此时出现死锁。一个不安全状态不一定就导致死锁，银行家（banker）算法因为，一个顾客不一定需要全部的存款，但是银行家将不能考虑这种情况。因此，银行家算法考察每一个出现的请求，并且看贷给此请求是否会导致一个安全状态。如果导致一个安全状态，则贷给他，否则推迟贷款直至导致一个安全状态。银行家（banker）算法为了检查一个状态是安全的，银行家检验他是否有充分的资源满足某个顾客。如果有，这些贷款被假定是要还贷的，并且检查该顾客现在最接近限额，等等。如果所有的贷款最终都能够还贷，则状态是安全的，可以贷给其初始的请求。图多资源的银行家算法多资源的银行家算法银行家算法可以推广到处理多资源的情况。在图中左边矩阵表示资源当前的赋予情况，右边矩阵表示每个进程为了完成仍然需要资源的情况。向量E表示系统所具有的资源，向量P表示当前进程所占有的资源，向量A表示系统可供使用的资源。银行家（banker）算法检查一个状态是否安全的算法如下：⑴寻找一行R它的未满足资源需求小于或等于A。如果不存在这样的行R，系统最终将死锁，因为没有一个进程能够运行完成。⑵假设所选中的行R的进程请求它所需的全部资源并结束，标志该进程终止并且将它的全部资源加到向量A上。银行家（banker）算法⑶重复步骤⑴和⑵直至所有的进程都被标志成终止，此时初始的状态是安全的，或者直至出现死锁，此时初始的状态是不安全的。在图中的状态是安全的。假设进程B请求一个打印机，这个请求可以被获得，因为结果状态仍旧是安全的，即进程D、C、A、E等可以依次结束。银行家（banker）算法现在假定在B得到余下的两台打印机之一后，E希望得到最后一台打印机。如果授予这个请求，将会使可用资源向量减少为(1,0,0,0)，这样导致死锁。显然，E的请求应该推迟一会儿。银行家（banker）算法虽然，银行家算法在理论上是美妙的，实际上，它没有实用价值。因为进程事先很少知道它们的最大资源需要。此外，进程的个数是不固定的，而且，想象可供使用的资源可能突然消失（例如磁带机损坏）。因此。在实用上，极少现存系统利用银行家算法避免死锁。银行家（banker）算法数据结构：①可利用资源向量Available[1:m]这是一个含有m个元素的数组，每一个元素代表一类可利用的资源数目，其初值是系统中所配置的该类全部可用资源数目。如果Available[j]=k，表示系统当前有Rj类资源k个。银行家（banker）算法②最大需求矩阵Max[1:n,1:m]这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=k，表示进程i需要Rj类资源的最大数目为k。银行家（