操作系统2002--死锁.ppt

死锁,死锁的定义死锁的描述死锁的预防和避免死锁的检测死锁的解除,一、死锁定义死锁定义：多个进程由于竞争资源（或者等待对方消息）而造成的彼此无休止的互相等待，在无外力作用下，永远不能向前推进，这种僵持局面称为死锁。（也可以叙述为：一组进程处于死锁状态，仅当这组中的每一进程都在等待一个事件，且这个事件仅被同组中的另一进程所引发）,例子：设有进程P1、P2和I/O设备DI、DOP1P2,申请一台输入设备DI申请一台输出设备DO使用之释放输入设备DI释放输出设备DO,申请一台输出设备DO申请一台输入设备DI使用之释放输出设备DO释放输入设备DI,例子：哲学家用餐问题定义信号量fork5:semaphore，初值均为1。,PROCESSPibeginL1:思考;P(forki);P(fork(i+1)mod5;用餐;V(forki);V(fork(i+1)mod5;gotoL1;end;,例子：生产者消费者问题（多缓冲区）,定义：整型变量：k=0,t=0整型数组：B0n-1信号量：SP=n,SG=0,PROCESSProducerbeginL1:produceaproduct;P(SP);Bk:=product;k:=(k+1)modn;V(SG);gotoL1end,PROCESSConsumerbeginL2:P(SG);TakeaproductformBt;t:=(t+1)modnV(SP);consumer;gotoL2end,能否这样改写：定义：信号量：mutex=1,empty=nfull=0;,PROCESSProducerbeginL1:produceaproduct;P(mutex);P(empty);送一个产品到有界缓冲区;k:=(k+1)modn;V(mutex);V(full);gotoL1end,PROCESSProducerbeginL1:produceaproduct;P(mutex);P(empty);送一个产品到有界缓冲区;k:=(k+1)modn;V(mutex);V(full);gotoL1end,当缓冲区满时，生产者仍可顺利执行p(mutex)操作，于是它对缓冲区有控制权，然后，当它执行p(empty)时，由于没有空缓冲区被挂起。能将这个生产者释放的是有一个消费者从缓冲区中取走一个产品，并执行v(empty)操作，但由于缓冲区已被生产者占用，出现了死锁。,死锁的必要条件：互斥：资源是独占的且排它使用（至少有一个资源处于非共享方式）；占用并等待：已获得资源未获释放，又有新的申请请求（至少存在一个进程，它至少占用一个以上的资源并等待得到另外的被其它进程占用的资源）；非抢占：进程已获得的资源只能由它自己释放，不允许剥夺（资源不可抢占）；循环等待：在发生死锁时，必然存在一个进程资源的环形链，即前一个进程保持后一个进程所申请的资源（存在一组等待进程P0，P1，Pn，其中P0要等待P1占用的资源，P1等待P2占用的资源，Pn等待P0占用的资源）。,二、死锁的描述（资源分配图方法）死锁的一种描述方法资源分配图：资源分配图定义为G（V，E），其中V是顶点集，E是边集。顶点集分两类：集合SpP1,P2,Pn包括系统中所有进程，集合SrR1,R1,Rm包括系统中的所有资源。边集E中的每个元素均为有序对（Pi,Rj）或（Rj,Pi）。若（Pi,Rj）E说明进程Pi正等待系统分配资源Rj，此边称作请求边；若（Rj,Pi）E说明资源Rj的一个示例已分配给了进程Pi，此边称作分配边。,有死锁的资源分配图,p1r1p2r3p3r2p1,有环路但没有死锁的资源分配图,死锁产生的原因：竞争资源引起死锁可剥夺和非剥夺性资源竞争非剥夺性资源竞争临时性资源,P1：;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);则可能发生死锁,进程推进顺序不当死锁进程推进顺序合法进程推进顺序非法,P1:P1req(R1)P1req(R2)P1rel(R1)P1rel(R2)P1:P2req(R2)P2req(R1)P2rel(R2)P2rel(R1),P1req(R1)P1req(R2)P1rel(R1)P1rel(R2)P2req(R2)P2req(R1)P2rel(R2)P2rel(R1),进程推进顺序不当,P1req(R1)P2req(R2)P1req(R2)P2req(R1),用资源分配图讨论死锁问题，可得到如下结论：如果资源分配图中无环路，则系统中没有死锁发生如果资源分配图有环路，且每个资源类中只有一个资源，则环路的存在就意味着死锁如果资源分配图有无环路，但涉及到的资源类中有多个资源，则环路的存在未必就有死锁形成。,例题：考虑下列资源分配策略：对资源的申请和释放可以在任何时刻进行。如果一进程的资源得不到满足，则检查所有由于等待资源而被阻塞的进程。如果它们有申请进程所需要资源，则将这些资源取出分配给申请进程。例如，考虑一个有三类资源的系统，系统所有可用资源为（4，2，2），进程A申请（2，2，1），可满足，进程B申请（1，0，1），也可满足，若A再请求（0，0，1），则被阻塞。此时，若C请求（2，0，0），它可以分到剩余资源（1，0，0），并从A已分到的资源中获得一个资源，于是，进程A的分配向量变为（1，2，1），而需求向量变成（1，0，1）。这种分配方式会导致死锁吗？如果会，请举一个例子；如果不会，请说明死锁的那一个必要条件不成立？这种分配方式会导致某些进程的无限等待吗？,解答：本方法不会产生死锁，因为它破坏了死锁的不可抢夺条件。这种方法会导致某些进程无限期的等待。,例题：一个操作系统有20个进程，竞争使用65个同类资源，申请方式是逐个进行的，一旦某进程获得它所需要的全部资源，立即归还所有资源。每个进程最多使用三个资源。若仅考虑这类资源，该系统有无可能全部死锁，为什么？,解答：不会产生死锁,例题：一个计算机有8台磁带机，它们由N个进程竞争使用，每个进程可能需要三台磁带机，请问N为多少时，系统没有死锁的危险？,解答：当N为3或更少时，系统没有死锁的危险。,解决死锁的基本方法A、预防死锁破坏四个必要条件之一，防止发生死锁（但可能导致资源利用率降低）。B、避免死锁在资源的动态分配过程中，采用某种方法防止系统进入不安全状态，比如银行家算法。C、检测死锁允许死锁发生，但通过某种检测机构及时检测出死锁的发生，并精确的确定与死锁有关的进程和资源，然后采取适当措施解除死锁。D、解除死锁一般采用资源剥夺和资源抢占方式。解除死锁需付出代价，原则上以代价越小越好。,三、死锁的预防和避免,1、死锁的预防思路是破坏四个必要条件之一（死锁的条件1是固有的，一般不能改变），或者在分配临界资源分之前，检查系统的状态，如是安全的，则分配之。破坏“占用并等待”条件资源作为一个整体，一次性分配。优点是简单、安全、易于实现，缺点是资源浪费严重，进程延迟运行。可制定相应的规则，例如，当一个进程（程序）申请某资源被拒绝，则必须释放已占用的资源，如需要再与其它所需资源一起申请。对CPU还可进行可剥夺分配。,破坏“非抢占”条件进程已经占有的资源，运行时可以暂时释放，以后再次申请。问题：实现复杂，且要付出代价。由于可能反复的释放和申请资源，因而可能极大的延迟进程的完成时间。破坏“循环等待”条件进程有序的申请资源。与前两种方法相比，资源的使用效率和系统性能都有较明显地改善。问题：限制了新设备的增加；用户需求与系统规定有冲突；对用户不方便。,系统的安全状态,安全状态一般地，称系统处于安全状态，仅当存在一个安全（进程）序列P1,P2,Pn，其中任一进程Pi所可能请求的最大资源数可被当前可用资源加上所有Pj（ji）已占用的资源所满足。例子：三个进程，共有12台设备,不安全状态当不存在上述的安全序列时，系统状态称之为不安全的。注意：不安全状态不等于死锁，不安全状态仅仅意味着系统将可能进入死锁状态。,由安全状态向不安全状态的转换如果在t1时刻P3又申请1台设备，若系统满足P3的要求，分配给P3一台设备，则系统将进入不安全状态。,此时存在安全序列P2,P1,P3,因此，避免死锁就是找出安全状态和不安全状态的临界点，以确定能否分配资源。,银行家算法,银行家算法的数据结构：可利用资源向量Available：m个元素的数组，其中每个元素代表一类可利用的资源数目，其数值随该类资源的分配和回收而动态的改变，初值为系统中可利用的该类全部资源的数目。如Availablejk，表示Rj类资源全部有k个。,最大需求矩阵Max：nm矩阵，定义了系统中n个进程中每个进程对m类资源的最大需求。如Max(i,j)k，表示进程i需要Rj类资源的最大数为k个。分配矩阵Allocation：nm矩阵，定义了系统中每一类资源当前已分配给每个进程的资源数。如果Allocationi,jk，表示进程i当前已分得Rj类资源的数目为k个。需求矩阵Need：nm矩阵，表示每个进程尚需的各类资源数。如果Needi,jk，表示进程i还需要Rj类资源k个方能完成任务。,上述矩阵存在如下关系：Needi,jMaxi,jAllocationi,j,银行家算法：设Requesti是进程Pi的请求向量。如果Requestijk，表示进程Pi需要k个Rj类的资源。当Pi发出资源申请Requesti后，系统按下述步骤检查：如果RequestiNeedi，则转步骤，否则认为出错（所需资源已超过宣布的最大值）。如果RequestiAvailablei，则转向步骤，否则表示尚无足够资源，Pi必须等待。系统试探把资源分配给进程Pi，并修改下面数据结构中的数值：,AvailableAvailableRequestiAllocationAllocationRequestiNeediNeediRequesti,系统执行安全性算法，检查资源分配后，系统是否处于安全状态。如安全，则正式分配，否则上述试探作废，恢复原来的资源分配状态，让进程Pi等待。,安全性算法：设初值：工作向量Work(长度m)表示系统可提供的资源数目。Work的初值为Allocation。向量Finish(长度n)表示系统是否有足够的资源分配给进程，使之运行完成。初始的Finishifalse，当有足够的资源分配给Pi时，令FinishiTrue。从进程集合中找一个能满足下述条件的进程：FinishifalseNeediWork如找到，执行步骤，否则执行步骤。,当进程Pi获得资源后，顺利执行，直至完成并释放出分配给它的资源，故应执行WorkWorkAllocationiFinishitrue转步骤。如果所有进程的Finishitrue，则表示系统处于安全状态，否则系统处于不安全状态。,例子：现有五个进程P0，P1，P2，P3，P4和资源A,B,C=10，5，7。T0时刻的资源分配表为：,T0时刻的安全性T0时刻可找出安全序列P1，P3，P4，P2，P0，故此时系统是安全的。,P1请求Request1(1,0,2)，系统按银行家算法检查：Request1(1,0,2)=Need1(1,2,2)Request1(1,0,2)=Available(3,3,2)假定可分配，修改Available，Allocation和Need向量，由此形成资源变化：,经安全性检查，可以找出一个安全序列P1,P3,P4,P0,P2。系统是安全的，可以实施分配。,P4请求Request4(3,3,0)，系统按银行家算法检查：Request4(3,3,0)=Need4(4,3,1)Request4(3,3,0)!=Available(2,3,0)P4必须等待。P0请求Request0(0,2,0)，系统按银行家算法检查：Request0(0,2,0)=Need0(7,4,3)Request0(0,2,0)0。,对每一进程Pi，1P13P31P13-P33,直观的解释：资源分配图中如有环路存在，则发生死锁，环路上的进程都卷入死锁中.,2、资源类中含有若干个资源,可以利用把资源分配图加以简化的方法来检测系统在某状态下是否处于死锁。在资源分配图中，方框表示资源的类，方框中的点的个数表示资源的数量。我们可以通过对资源分配图的化简来判断系统是否处于死锁状态，具体方法如下：在资源分配图中找出一个既不阻塞又非独立的进程结点P，在顺利情况下，结点P可获得所需资源而继续执行，直至运行完毕，在释放其占有的所有资源，这相当于消取P所有的请求边和分配边，使之称为孤立结点。P释放资源后，继续寻找下一个既不阻塞又非独立的结点，使它获得资源而继续执行，直至该结点完成后又释放出它所占用的全部资源。在进行了一系列的简化后，若能消取图中所有的边，使所有进程都成为孤立结点，则称该图为可完全简化的，否则该图使不可完全简化的。,第一步在资源分配图中找出一个既非阻塞又不孤立且它的资源申请数量可以得到系统满足的任何一个结点Pi，如果不存在这样的Pi，则系统已经处于不安全或死锁状态，检测结束。第二步去掉Pi的所有请求边和分配边，使之成为孤立结点，并在Pi所归还的资源的类方框中添加与归还资源数量相对应的圆点，然后转第一步。如果所有结点都成为孤立结点，则称资源分配图可完全简化，否则为不可完全简化。资源分配图的化简过程（或者说得到的进程化简序列）可以不同，但可以证明，它们都将得到相同的不可简化图。同样可以证明，系统的资源分配图不可完全简化是死锁的充分条件。,例子,P1,P2,r1,r2,P1,P2,r1,r2,a结点P1既不阻塞也不孤立,b给P1分配资源变请求边为分配边,P1,P2,r1,r2,cP1释放资源成为孤立结点,P1,P2,r1,r2,d给P2分配资源变请求边为分配边,P1,P2,r1,r2,eP2释放资源成为孤立结点,例子,P1,P2,r1,r2,a初始态,P3,r3,P1,P2,r1,r2,b变P1的申请边为分配边,P3,r3,对上述方法进行形式化，可分为三步来进行：第一步找出资源已经满足的进程，将它们所占用的资源和系统中还剩余的资源加在一起作为“可分配的资源”，对这些处理过的进程加上标志；第二步在新的“可分配资源”的约束下，继续从未加上标志的进程中查找资源可以满足的进程，如果有这样的进程，转第一步，否则转下一步；第三步如系统中所有进程均有标志，表明系统没有死锁，否则说明系统处于死锁状态，没有标志的那一组进程就是死锁进程。,死锁检测中的数据结构：可利用资源向量Available：表示了m类资源中的每一类资源的可用数目。请求矩阵Request：一个nm矩阵，用以表示进程当前对各类资源的请求数目。分配矩阵Allocation：一个nm矩阵，用以表示某一时刻的资源分配情况。工作向量Work：表示系统可提供给进程继续运行的各类资源数目。进程向量Finish：记录进程当前是否还占有资源。,死锁检测算法,work:=available;L:=Pi|allocationi=0requesti=0forallPi!Ldobeginforallrequesti=workdobeginwork:=work+allocati