《操作系统原理第六章死锁.ppt》由会员分享，可在线阅读，更多相关《操作系统原理第六章死锁.ppt（29页珍藏版）》请在三一办公上搜索。
1、第六章 死锁,若对资源不加限制的分配可能导致进程间由于竞争资源而相互制约以至无法继续运行的局面，这就是死锁。,一、死锁的基本概念1、死锁产生的原因 系统中两个或两个以上的进程无限期的等待永远不可能发生的事件，则称这些进程处于死锁状态中。,进程执行的速度 例6-1对临时资源使用不加限制 例6-2例6-3生活中的例子：独木桥其他：wait signal操作顺序不对,产生死锁的原因有两个：1 系统资源不足 产生死锁的根本原因在于系统提供的资源个数少于并发进程所需要的资源总数。2 进程推进次序不合理,2、死锁的必要条件1）互斥条件2）保持和请求条件3）不剥夺条件4）环路条件,3、死锁的对策1）鸵鸟策略
2、忽略死锁的发生,unix和linux中会如此处理2）预防策略 破坏四个必要条件中的一个，但会影响资源利用率和系统吞吐量3）避免策略 与预防策略不同，预防策略要求破坏一个必要条件，而避免策略不必严格限制必要条件的存在，因为必要条件存在也不一定发生死锁。因此死锁避免使在事先加以较弱的限制条件，目的是提高系统资源利用率。4）死锁的检查和解除 通过系统设置检查机构、及时检查死锁的发生，并确定死锁进程和卷入死锁的资源，并采取适当措施，将死锁进程从死锁中解除。,二、死锁预防1、破坏互斥条件允许多个进程同时访问资源2、破坏不剥夺条件 在允许进程动态申请资源的前提下：一个进程在申请新资源的要求不能立刻得到满足
3、时，便处于等待状态。而一个处于等待状态的进程的全部资源可以被剥夺。,3、破坏“请求和保持”条件静态资源分配法 资源预分配:进程开始之前，一次性分配他所需要的全部资源。主要问题：进程因等待所需要的资源阻塞时间过长 部分资源可能在相当长的时间内变得不可用；进程一次性知道所需全部资源不太可能。,4、破坏“循环等待”条件针对环路条件的，资源的动态分配有序资源使用法：将系统中的所有资源顺序编号，一般原则是，较为紧缺、稀少的的资源编号较大。进程申请资源时，必须严格按照资源编号的顺序进行，否则系统不予分配。即一进程只有得到编号小的资源，才能申请编号较大的资源，释放资源是，应该按编号递减的次序进行。,三、死锁
4、避免 系统对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，如果分配后系统可能发生死锁，则不予分配，否则予以分配，这是一种保证系统不进入死锁状态的动态策略。,1、安全和不安全状态 安全状态：在某一时刻，系统能按照某种次序，如来为并发进程分配所需要的资源，直到最大需求，使每个进程都顺利完成，则程此时的系统状态为安全状态。此序列为安全序列。不安全状态：某一时刻，不存在这样的一个安全序列，则称为不安全状态。,不安全状态一定导致死锁，但不安全状态不一定是死锁。,2、利用银行家算法避免死锁一个银行家把他的固定资金贷给若干顾客。只要不出现一个顾客借走所有资金后还还不够，
5、银行家的资金应是安全的。银行家需一个算法保证借出去的资金在有限时间内可收回。为保证资金的安全，银行家规定：1）当一个顾客对资金的最大需求量不超过银行家现有的资金时可以接纳该顾客。2）顾客可以分期贷款，但贷款的总数不能超过最大需求量。3）当银行家现有的资金不能满足顾客尚须得贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间能得到贷款。4）当顾客得到所需的全部资金后，能在有限的时间里归还所有的资金。,推广到操作系统，操作系统按照银行家的规定为进程分配资源，进程首先提出对资源的最大需求量，当进程在执行过程中每次申请资源时，系统测试该进程已占用的资源与本次申请的资源之和是不是超过了该进程对资
6、源的最大需求量。若超过则拒绝分配资源，若没有超过，则系统再测试系统现存的资源是否能满足该进程尚需要的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。,（一）数据结构可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。最大需求矩阵Max。这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。分配矩阵Allocation。这也是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。需求矩阵Need。这也是一个nm的矩阵，用以表示每一个进程尚需的各类资源数。注意：Needi,j=Maxi,j-
7、Allocationi,j,（二）银行家算法 设Requesti是进程Pi的请求向量，如果Requestij=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：(1)如果RequestijNeedi,j，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。(2)如果RequestijAvailablej，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。,(3)系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Availablej:=Availablej-Requestij Allocationi,j:=Allocation
8、i,j+Requestij;Needi,j:=Needi,j-Requestij;(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。,（三）安全性问题（1）设置两个向量：工作向量Work:它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available;Finish:它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi=false;当有足够资源分配给进程时，再令Finishi=tru
9、e。,(2)从进程集合中找到一个能满足下述条件的进程：Finishi=false;Needi,jWorkj；若找到，执行步骤(3)，否则，执行步骤(4)。(3)当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行Workj=Worki+Allocationi,jFinishi=true;go to step（2）;(4)如果所有进程的Finishi=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。,例：假定系统中有五个进程P0,P1,P2,P3,P4和三类资源A,B,C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图 所示。,(1)分析
10、此状态是否为安全状态(2)P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查是否安全(3)P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查是否安全,银行家算法在理论上是出色的，能保证系统一直工作在安全状态下。此外，作为资源分配的一种算法，银行家算法允许互斥条件、请求和保持条件以及不剥夺条件成立，相比死锁预防，其限制条件放松，资源利用率得到改善，但仍有不足：1）算法要求分配的资源数量不定不变2）算法要求用户数目也不定不便。3）算法保证所有用户的资源要求能在有限时间内得到相应，但实时用户要求有更好的相应速度。4）算法要求用户
11、在提交作业时说明对各类资源请求的最大数量，这对于用户而言不方便也很困难。,四、死锁的检测 系统如果没有防范机制，则系统在运行过程中可能存在死锁。为此，在操作系统中通常设立一个检测进程，它平时处于睡眠状态，周期性的或发现系统性能下降时被唤醒以检查系统中有无死锁进程。采用这种技术时，系统需要监视资源的申请和释放，其中广为应用的是以描述系统内资源使用与申请状况的有向图，叫做资源分配图。,1、资源分配图 系统由若干类资源构成，一类资源称为一个资源类；每个资源类中包含若干个同种资源，称为资源实例。资源类:用方框表示（资源的不同类型）资源实例:用方框中的黑圆点表示（存在于每个资源中）进程:用圆圈中加进程名
12、表示分配边：资源实例进程 的一条有向边申请边：进程资源类 的一条有向边,2、死锁定理1）找一个非孤立点进程结点且只有分配边，去掉分配边，将其变为孤立结点2）再把相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边,某状态为死锁的充分条件是：当且仅当该状态的资源分配图是完全化简得，经过化简后非孤立的进程是死锁进程。死锁的环路条件与资源分配图中有环路时等价的，系统中出现死锁，资源分配图必然有环路，但有环路不一定死锁。,环路有死锁 环路无死锁,五、死锁的解除常用方法：1、撤销所有死锁进程 2、若系统提供设置检查点和重新启动机制，则将死锁进程退回到前一个检查点，并重新从检查点启动进程 3、逐个撤销死锁进程直到死锁不再存在 4、逐个抢占死锁进程的资源，给剩余进程使用直到死锁不存在,六、死锁的综合处理资源顺序分类法：1、内部资源（系统所用资源，如pcb表等）预分配法2、内存资源 资源剥夺法3、作业资源（打印机、文件等）死锁避免法4、外存资源 预分配法资源排序：在不同资源类之间规定次序，对不同资源类中的资源采用线性按序申请的方法针对性优化：对同一资源类中的资源，采用适当的方法。如：进程资源避免，外存交换区空间，主存，内部资源预防,
