chapter3调度与死锁16-2.ppt

1、3.5 死锁的基本概念,一、死锁 二、产生死锁的原因 三、产生死锁的必要条件 四、处理死锁的基本方法,返回目录,进程控制不但要控制进程之间的同步和互斥,确保进程之间正常通信,还要解决进程死锁问题. 一旦出现进程死锁,相应的进程将无法向前推进.如果系统内绝大多数或者全部进程死锁,将造成系统瘫痪,或者”死机”.,死锁引出,3.5 死锁的基本概念,例：设有一台输入机和一台输出机，进程P1和P2需要使用这两个资源。设两个进程的活动分别为：,P1的活动： 申请输入机 申请输出机 释放输出机 释放输入机,P2的活动： 申请输出机 申请输入机 释放输入机 释放输出机,P1与P2均因得不到资源而无法继续向前推

2、进，这种由于进程竞争资源而引起的僵持称为死锁。,指多个进程在运行过程中因争夺资源,推进顺序不当或进程通信而造成的一种僵局（deadly-Embrace)，若无外力作用，这些进程都将无法向前推进。 如图,注意： （1）参与死锁的进程数至少为2 （2）参与死锁的所有进程均等待资源 （3）参与死锁的进程至少有两个占有资源 （4）参与死锁的进程是系统中当前正在运行进程的一部分。,返回,一、死锁,二、产生死锁的原因,竞争资源 竞争非剥夺性资源,进程A、B并发执行。 资源S1、S2,曲线4将进入不安全区域（进程推进顺序非法）,二、产生死锁的原因,进程间推进顺序非法,返回,三、产生死锁的必要条件,产生死锁必

3、须具备以下四个条件，这四个条件是Coffman首先提出的，所以称为Coffman 条件： 互斥条件（资源独占条件） 请求和保持条件（部分分配条件） 不剥夺条件 循环等待条件（环路条件）,返回,四、处理死锁的基本方法,不让死锁发生 预防死锁（静态策略） 避免死锁（动态策略） 让死锁发生 检测死锁 解除死锁,四、处理死锁的基本方法,鸵鸟算法：指像鸵鸟一样对死锁视而不见，即不理睬死锁。 预防死锁：指通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来防止死锁的发生。 避免死锁：指在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。 检测死锁：允许系统在

4、运行过程中发生死锁，但可设置检测机构及时检测死锁的发生，并采取适当措施加以清除。 解除死锁：当检测出死锁后，便采取适当措施将进程从死锁状态中解脱出来。,返回,通过破坏死锁的四个必要条件中的一个或多个以确保系统绝不会产生死锁。 1互斥条件 ：无法破环，资源本身固有特性限制 2破坏请求和保持条件 ：采用预先分配的策略 3破坏循环等待条件：采用有序分配的策略 4破坏非剥夺条件 ：可以收回已分给进程且尚未使用完毕的资源。采用策略,一、死锁的预防,3.6 死锁的预防和避免方法,预先分配策略,系统要求任一进程必须预先申请它所需的全部资源，而且仅当该进程的全部资源要求能得到满足时，系统才能给予一次性分配，然

5、后启动该进程运行，但是在分配时只要有一种资源不满足，系统就不会给进程分配资源。进程运行期间，不会再请求新的资源。 缺点：资源严重浪费 进程延迟进行,有序分配策略,把系统中所有资源编号，进程在申请资源时必须按资源编号的递增次序进行，否则操作系统不予分配,优点：资源利用率和系统吞吐量与另两种方法相比有较明显的改善。 缺点： 1 为系统中各种类型的资源所分配的序号必须相对稳定，这就限制了新设备类型的增加； 2 作业实际使用资源的顺序与系统规定的顺序不同而造成资源的浪费； 3 限制了用户简单、自主地编程。,有序分配策略,破坏非剥夺条件,采用的策略：一个已经保持了某些资源的进程，当它再提出新的资源要求而

6、不能立即得到满足时，必须释放它已经保持的所有资源，待以后需要时再重新申请。 实现比较复杂，且要付出很大代价；此外，还因为反复地申请和释放资源，而使进程的执行无限地推迟，延长了周转时间，增加了系统的开销，降低了系统吞吐量。（例如打印机打印的结果不连续）,死锁的避免,3.6 死锁的预防和避免方法,定义:系统运行过程中， 允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程； 否则，令进程等待。 最具有代表性的避免死锁算法是银行家算法 Bankers Algorithm 。,二、系统的安全状态,安全状态：如果系统能按

7、某种顺序（如P4，P1，,Pn, 称为安全序列）为每个进程分配其所需的资源，直至每个进程都能顺利地完成，称系统处于安全状态。若不存在这样一个安全序列称系统处于不安全状态。 安全状态一定是没有死锁发生的。,在死锁避免的方法中，允许进程动态申请资源，系统在进行资源分配之前，先计算资源分配的安全性，若此次分配不会导致系统进入不安全状态，便将资源分配给进程，否则进程等待。,二、系统的安全状态,安全、不安全、死锁状态空间,基本事实 如果一个系统在安全状态，就没有死锁 如果一个系统处于不安全状态，就有可能死锁 避免死锁的实质：确保系统不进入不安全状态）,安全状态实例,假定系统中有三个进程P1，P2和P3，

8、共有12台磁带机，三个进程对磁带机的需求和占有如下：,T0时刻，存在一个安全序列（P2，P1，P3）或（ P2，P3，P1 ），所以系统是安全的。,二、系统的安全状态,二、系统的安全状态,由安全状态向不安全状态的转换：如在T0以后，P3要求1台磁带机，若系统分给它一台，则系统进入不安全状态。,因为其余2台分给P2，P2完成后，只能释放4台，这既不能满足P1（5台），也不能满足P3（6台），将导致死锁。,三、避免死锁的算法-银行家算法,为实现银行家算法，系统中必须设置若干数据结构。假定系统中有n个进程（P1，P2，Pn），m类资源（R1，R2，Rm），银行家算法中使用的数据结构如下： 可利用资源

9、向量:availablej=k, 资源Rj类有k个可用 最大需求矩阵:Maxi,j=k,进程Pi最大请求k个Rj类资源 分配矩阵：Allocationi,j=k,进程Pi分配到k个Rj类资源 需求矩阵：Needi,j=k,进程Pi还需要k个Rj类资源 三个矩阵的关系： Need i,j = Maxi,j Allocation i,j.,银行家算法 设Requesti是进程Pi的请求向量，如果Requestij=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： (1)如果RequestijNeedi,j，便转向步骤2；否则认为出错，因为它所需要的资源数已超过

10、它所宣布的最大值。 (2)如果RequestijAvailablej，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。 (3)系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Availablej=Availablej-Requestij; Allocationi,j=Allocationi,j+Requestij; Needi,j=Needi,j-Requestij; (4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。,安全性算法 (

11、1)设置两个向量： 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available; Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi=false; 当有足够资源分配给进程时， 再令Finishi=true。 (2)从进程集合中找到一个能满足下述条件的进程： Finishi=false; Needi,jWorkj； 若找到， 执行步骤(3)， 否则，执行步骤(4)。 (3)当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Workj=Worki+A

12、llocationi,j; Finishi=true; go to step 2; (4)如果所有进程的Finishi=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。,银行家算法的例子,假定系统中有5个进程3类资源及数量分别为10、5、7，T0时刻的资源分配情况。,（1） T0时刻的安全性,T0时刻存在着一个安全序列P1 P3 P4 P2 P0，故系统是安全的。,银行家算法的例子,(2) P1请求资源 Request1(1,0,2)执行银行家算法,银行家算法的例子,P1请求资源时的资源分配表,P1请求资源时的安全性检查表,存在着一个安全序列P1 P3 P4 P2 P0，故

13、系统是安全的，可以立即将P1所申请的资源分配给它。,银行家算法的例子,（3）P4请求资源Request4(3,3,0),P4发出请求向量Request4(3,3,0)，系统按银行家算法进行检查: 1) Request4(3,3,0)Need4 (4,3,1) 2) Request4 (3,3,0) Available (2,3,0),表示资源不够,则让P4等待,银行家算法的例子,(4) P0请求资源 Request0(0,2,0),银行家算法的例子,P0请求资源时的资源分配表,Available(2,1,0) 不能满足任何进程需要，所以系统进入不安全状态，P0的请求不能分配,返回目录,3.7

14、死锁的检测和解除,一、资源分配图 检测死锁的基本思想: 是在操作系统中保存资源的请求和分配信息，利用某种算法对这些信息加以检查，以判断是否存在死锁。为此，将进程和资源间的申请和分配关系描述成一个有向图-资源分配图。,3.7 死锁的检测和解除,允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生 一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行,一、资源分配图,资源分配图又称进程-资源图，它描述了进程和资源间的申请和分配关系，该图是一个有向图,进程,有三个资源,Pi 请求一个Rj,Pi 持有一个Rj,一、资源分配图,进程结点子集 P = P1,P2,P3 资源结点子集

15、 R = R1,R2,R3,R4 N=P R =P1,P2,P3R1,R2,R3,R4 =P1,P2,P3,R1,R2,R3,R4 E=(R2,P1),(R2,P2),(P1,R1),(R1,P2),(P2,R3),(R3,P3),进程,有三个资源,Pi 请求一个Rj,Pi 持有一个Rj,二、死锁判定法则,(1)如果资源分配图中没有环路，则系统内 没有死锁。 (2)如果图中有环路，且每类资源只有一个，则有环是系统存在死锁的必要充分条件。 (3)如果图中有环路，但每类资源的个数不全为1，则可以利用对图化简的方法，来检测系统是否存在死锁,二、死锁判定法则,有环无死锁,二、死锁判定法则,有环有死锁,

16、资源分配图的化简,（1）寻找一个即不阻塞又非孤立的进程结点Pi， 若无则算法结束； （2）去除Pi的所有分配边和请求边，使Pi成为一个孤立节点； （3） 转步骤（1）。 若所有进程成为孤立结点，称该图是可完全简化的，否则称该图是不可完全简化的。,二、死锁判定法则,该图是不可完全简化的,二、死锁判定法则,S为死锁状态的充分必要条件是，当且仅当S状态的资源分配图是不可完全简化的。（死锁定理）,二、死锁检测算法,基本思想 获得某时刻t系统中各类可利用资源的数目向量w(t),对于系统中的一组进程 p1,p2, ,pn，找出那些对各类资源请求数目均小于系统现有的各类可利用资源数目的进程。这样的进程可以获

17、得它们所需要的全部资源并运行结束，当它们运行结束后释放所占有的全部资源，从而可使资源数目增加，将这样的进程加入到可运行结束的进程序列L中，然后对剩下的进程再作上述考查。如果一组进程 p1,p2, ,pn中有几个进程不属于序列L中，那么它们会发生死锁。,类似于银行家算法中的数据结构： 可利用资源向量:availablej=k, 资源Rj有k个可用 最大需求矩阵:Maxi,j=k,进程Pi最大请求k个Rj资源 分配矩阵：Allocationi,j=k,进程Pj分配到k个Rj资源 需求矩阵： Request i,j=k,进程Pj申请k个Rj资源 三个矩阵的关系： Need i,j = Maxi,j

18、Allocation i,j.,二、死锁检测算法,检测算法*,1.让Work和Finish作为长度为m和n的向量 (a) Work := Available (b)For i = 1,2, , n, if Allocationi 0, then Finishi := false;otherwise, Finishi := true. 2.找到下标i (a)Finishi = false (b)Requesti Work 如果没有这样的i存在，转4 3.Work := Work + Allocationi Finishi := true go 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.,算