操作系统原理第六章死锁课件

第六章

死锁若对资源不加限制的分配可能导致进程间由于竞争资源而相互制约以至无法继续运行的局面，这就是死锁。一、死锁的基本概念1、死锁产生的原因系统中两个或两个以上的进程无限期的等待永远不可能发生的事件，则称这些进程处于死锁状态中。

进程执行的速度

例6-1对临时资源使用不加限制

例6-2例6-3生活中的例子：独木桥其他：waitsignal操作顺序不对2、死锁的必要条件1）互斥条件2）保持和请求条件3）不剥夺条件4）环路条件

3、死锁的对策1）鸵鸟策略忽略死锁的发生,unix和linux中会如此处理2）预防策略

破坏四个必要条件中的一个，但会影响资源利用率和系统吞吐量3）避免策略

与预防策略不同，预防策略要求破坏一个必要条件，而避免策略不必严格限制必要条件的存在，因为必要条件存在也不一定发生死锁。因此死锁避免使在事先加以较弱的限制条件，目的是提高系统资源利用率。4）死锁的检查和解除通过系统设置检查机构、及时检查死锁的发生，并确定死锁进程和卷入死锁的资源，并采取适当措施，将死锁进程从死锁中解除。

二、死锁预防1、破坏互斥条件允许多个进程同时访问资源2、破坏不剥夺条件

在允许进程动态申请资源的前提下：一个进程在申请新资源的要求不能立刻得到满足时，便处于等待状态。而一个处于等待状态的进程的全部资源可以被剥夺。

4、

破坏“循环等待”条件针对环路条件的，资源的动态分配有序资源使用法

：将系统中的所有资源顺序编号，一般原则是，较为紧缺、稀少的的资源编号较大。进程申请资源时，必须严格按照资源编号的顺序进行，否则系统不予分配。即一进程只有得到编号小的资源，才能申请编号较大的资源，释放资源是，应该按编号递减的次序进行。三、死锁避免

系统对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，如果分配后系统可能发生死锁，则不予分配，否则予以分配，这是一种保证系统不进入死锁状态的动态策略。1、安全和不安全状态

安全状态：在某一时刻，系统能按照某种次序，如<P1,P2……Pn>来为并发进程分配所需要的资源，直到最大需求，使每个进程都顺利完成，则程此时的系统状态为安全状态。此序列为安全序列。

不安全状态：某一时刻，不存在这样的一个安全序列，则称为不安全状态。

2、利用银行家算法避免死锁一个银行家把他的固定资金贷给若干顾客。只要不出现一个顾客借走所有资金后还还不够，银行家的资金应是安全的。银行家需一个算法保证借出去的资金在有限时间内可收回。为保证资金的安全，银行家规定：1）

当一个顾客对资金的最大需求量不超过银行家现有的资金时可以接纳该顾客。2）

顾客可以分期贷款，但贷款的总数不能超过最大需求量。3）

当银行家现有的资金不能满足顾客尚须得贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间能得到贷款。4）

当顾客得到所需的全部资金后，能在有限的时间里归还所有的资金。推广到操作系统，操作系统按照银行家的规定为进程分配资源，进程首先提出对资源的最大需求量，当进程在执行过程中每次申请资源时，系统测试该进程已占用的资源与本次申请的资源之和是不是超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过，则系统再测试系统现存的资源是否能满足该进程尚需要的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。

（一）数据结构可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目

。最大需求矩阵Max。这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。分配矩阵Allocation。这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。

需求矩阵Need。这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数

。注意：Need［i,j］=Max［i,j］-Allocation［i,j］

(3)系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Available［j］:=Available［j］-Requesti［j］Allocation［i,j］:=Allocation［i,j］+Requesti［j］;

Need［i,j］:=Need［i,j］-Requesti［j］;(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。

若安全，才正式将资源分配给进程Pi，以完成本次分配；

否则，

将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。（三）安全性问题（1）设置两个向量：①

工作向量Work:它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work∶=Available;②Finish:它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］∶=false;当有足够资源分配给进程时，

再令Finish［i］∶=true。

(2)从进程集合中找到一个能满足下述条件的进程：

①Finish［i］=false;②Need［i,j］≤Work［j］；

若找到，

执行步骤(3)，

否则，执行步骤(4)。(3)当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行Work［j］∶=Work［i］+Allocation［i,j］Finish［i］∶=true;gotostep（2）;(4)如果所有进程的Finish［i］=true都满足，

则表示系统处于安全状态；否则，系统处于不安全状态。

(1)分析此状态是否为安全状态(2)P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查是否安全(3)P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查是否安全

银行家算法在理论上是出色的，能保证系统一直工作在安全状态下。此外，作为资源分配的一种算法，银行家算法允许互斥条件、请求和保持条件以及不剥夺条件成立，相比死锁预防，其限制条件放松，资源利用率得到改善，但仍有不足：1）算法要求分配的资源数量不定不变2）算法要求用户数目也不定不便。3）算法保证所有用户的资源要求能在有限时间内得到相应，但实时用户要求有更好的相应速度。4）算法要求用户在提交作业时说明对各类资源请求的最大数量，这对于用户而言不方便也很困难。

四、死锁的检测系统如果没有防范机制，则系统在运行过程中可能存在死锁。为此，在操作系统中通常设立一个检测进程，它平时处于睡眠状态，周期性的或发现系统性能下降时被唤醒以检查系统中有无死锁进程。采用这种技术时，系统需要监视资源的申请和释放，其中广为应用的是以描述系统内资源使用与申请状况的有向图，叫做资源分配图。

2、死锁定理1）找一个非孤立点进程结点且只有分配边，去掉分配边，将其变为孤立结点2）再把相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边

某状态为死锁的充分条件是：当且仅当该状态的资源分配图是完全化简得，经过化简后非孤立的进程是死锁进程。

死锁的环路条件与资源分配图中有环路时等价的，系统中出现死锁，资源分配图必然有环路，但有环路不一定死锁。六、

死锁的综合处理资源顺序分类法：1、内部资源（系统所用资源，如p