操作系统死锁.pptx

《操作系统死锁.pptx》由会员分享，可在线阅读，更多相关《操作系统死锁.pptx（16页珍藏版）》请在课桌文档上搜索。

1、操作系统,死 锁,目 录,死锁的基本概念,01,基本概念,死锁的定义：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。,从死锁的定义中可以得到几个推论：1.参与死锁的所有进程都在等待资源。2.参与死锁的进程是当前系统中所有进程的子集。,死锁的产生的原因：资源数量有限、锁和信号量错误使用都可能导致死锁，锁和信号量的使用可能是开发人员编程导致的。下面着重介绍一下有限资源导致的死锁问题：在操作系统中资源使用的一般模式是：进程提出申请，操作系统进行相应的分配，如果

2、进程所需要的资源不能满足的话，这个进程就进入阻塞或者等待状态，如果可以满足的话进程就直接使用资源，当进程使用完毕之后就释放资源。由于资源的使用方式就是申请-分配-使用-释放，因此有些进程得不到资源就会处理阻塞等待状态，资源有限的话就有可能出现死锁。,基本概念,一个资源每次只能给一个进程使用,互 斥 使 用(资源独占),进程在申请新的资源的同时保持对原有资源的占有,占 有 且 等 待(请求和保持，部分分配),资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放,不 可 抢 占(不可剥夺),存在一个进程等待队列 P1,P2,Pn，其中P1等待P2占有的资源，P2等待P3占有的资源

3、，Pn等待P1占有的资源，形成一个进程等待环路。,循 环 等 待,产生死锁的必要条件,当死锁产生的时候一定会有这四个条件，有一个条件不成立都不会造成死锁。,资源的分布图（RAG）,02,资源分布图,资源分配图(RAG)用有向图描述系统资源和进程的状态，从图的角度为解决死锁提供理论和依据。定义一个二元组G=（V，E）有两个集合组成。其中V是结点的集合，分为P(进程)，R(资源)两部分，P=P1,P2,Pn，R=R1,R2,Rm。E是有向边的集合，其元素为有序二元组，可以是进程节点指向资源节点的有向边后者资源节点指向进程节点的有序边。,资源分配图图画法说明 系统由若干类资源构成，一类资源称为一个资

4、源类；每个资源类中包含若干个同种资源，称为资源实例。使用用方框表示资源类；用方框中的黑圆点表示资源实例；用圆圈中加进程名表示进程。分配边是资源实例指向的进程有向边，而申请边是进程指向资源实例的有向边。,分配,申请,资源分布图,由资源分配图得到的死锁定理：如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中可能存在死锁；如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件。,有环有死锁,有环无死锁,可以对资源分配图进行化简来查看是否有死锁产生，简化步骤：(1)找一个非孤立、且只有分配边的进程结点去掉分配边，将其变为孤立结点。(2）再把相应的资源分配给一个等待该资源的

5、进程即将该进程的申请边变为分配边。反复进行(1)(2)直到找不到满足非孤立并且只有分配边的进程节点。简化之后如果系统中的进程节点都是孤立的，那么系统中既没有死锁发生；否则系统中一定有环路存在。,处理死锁的方法,03,处理死锁,目前处理死锁的方法可以归纳为如下：(1)不考虑此问题（鸵鸟算法）：把头埋在沙子里，假装根本没发生问题。因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。(2)不让死锁发生

6、，分为以下两种：死锁预防：不让死锁发生的静态策略，通过设计合适的资源分配算法，由资源分配策略保证不让死锁发生死锁避免：不让死锁发生的动态策略，以不让死锁发生为目标，跟踪并评估资源分配过程，根据评估结果决策是否分配(3)让死锁发生 通过死锁的检测判断死锁是否真的发生，然后采用一些方法来解除死锁的问题。,处理死锁,总体解决锁死发生的方法可以分为四类：,鸵 鸟 算 法,死 锁 预 防,死 锁 避 免,死锁检测与解除,1,2,3,4,破坏“互斥使用/资源独占”条件资源本身的特性是独占的，是排他性使用的，所以要使用一种资源转换技术，把独占资源变为共享资源。例如针对于打印机，SPOOLing技术的引入解决

7、不允许任何进程直接占有打印机的问题。设计一个“守护进程/线程”负责管理打印机，进程需要打印时，将请求发给该daemon，由它完成打印任务。,破坏“占有且等待”条件指一个进程占有了一部分资源，在申请其他资源的时候由于得不到满足而进入等待状态。有下面两种方案实现：实现方案1：要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配。这种实现会使得资源的利用率很低，当一个进程所需要的资源不能同时满足的情况下可能一直处于等待状态，会产生饥饿现象。实现方案2：在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已

8、占有的全部资源，若需要再重新申请。,破坏“不可抢占”条件实现方案是当一个进程申请的资源被其他进程占用时，可以通过操作系统抢占这一资源(两个进程优先级不同)。这种方法具有局限性，适用于状态易于保存和恢复的资源，如CPU、内存资源。,破坏“循环等待”条件主要思想是通过定义资源类型的线性顺序实现，实现方案是资源有序分配法，把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配。实现资源的有序分配时需要考虑如何对资源进行编号，通常可以利用资源使用的频繁性进行排序。,死锁预防,在设计系统时，通过确定资源分配算法，排除发生死锁的可能性。具体做法是防止产生死锁的四个必要

9、条件中任何一个条件发生即破坏产生死锁的四个条件之一。,死锁避免,通过一个例子来讨论死锁避免的设计思想：,如下图(a)有两个进程P和Q，系统中一共有M个资源，假设A为进程P对资源需求的最大量，B是进程Q对资源需求的最大量，如果P进程对资源的占用量超过X则Q进程无法运行，如果Q进程对资源的占用量超过Y，则P进程无法运行。(b)中X1为进程P的资源占用量，Y1是Q进程的占有量，那么剩余的资源能满足P或Q进程对资源的需求量；(c)中X2为进程P的资源占用量，Y1是Q进程的占有量，那么剩余的资源可以满足P进程对资源的最大需求量，等P进程释放资源后Q进程就可以继续执行，这时对资源的分配就是有条件的；(d)

10、中剩余资源既不能满足P进程也不能满足Q进程对资源的最大需求量。,(a),(b),(c),(d),死锁避免,根据以上分析，在进程执行过程中，提出资源申请时，操作系统应该根据当时系统所处的状态或者把资源分配给该进程后进入的一个新的状态来调整资源分配策略。具体分析如下：OXO3Y区域，P进程Q进程提出申请资源时操作系统都可以满足；XAO2O3区域内，如果P进程提出申请可以无条件满足，Q进程提出申请总数只要不超过Y就可以满足；同时操作系统应该控制不要让资源的申请分配出现在O1O2O3区域，否则系统剩余的资源数量既不能满足P进程也不能满足Q进程，会导致死锁。,通过上面的例子可以给出死锁避免的设计思想：在

11、系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统发生死锁或可能发生死锁，则不予分配，否则予以分配，即在资源动态分配过程中，防止系统进入不安全状态，以避免死锁的发生。,死锁避免,利用银行家算法避免死锁：,银行家算法是仿照银行发放贷款时采取的控制方式而设计的一种死锁避免算法，起这样的名字是因为该算法原本是为银行系统设计的，以确保银行在发放贷款时，不会发生不满足客户需要的情况，在操作系统中也可以用它来避免死锁。为实现银行家算法，每一个进程进入系统时，他它须申明在运行过程中，可能需要每种资源类型的最大数目，其数目不能超过系统所拥有的资源

12、总量。当进程请求一组资源时，系统必须首先确定是否有足够的资源分配给该进程。若有，再进一步计算在将这资源分配给进程后，是否会使系统处于不安全状态。如果不会，才将资源分配给它，否则让进程等待。,应用条件如下：在固定数量的进程中共享数量固定的资源每个进程预先指定完成工作所需的最大资源数量进程不能申请比系统中可用资源总数还多的资源进程等待资源的时间是有限的如果系统满足了进程对资源的最大需求，那么，进程应该在有限的时间内使用资源，然后归还给系统,死锁的检测与解除,死锁检测与解除：允许死锁发生，但是操作系统会不断监视系统进展情况，判断死锁是否真的发生；一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢

13、复操作系统运行。,检测死锁是否发生有三个典型的检测时机：(1)当进程由于资源请求不满足而等待时检测死锁，缺点是系统开销大。(2)定时检测。(3)系统资源利用率下降时检测死锁。,一个简单的死锁检测算法给每个进程、每个资源指定唯一编号；设置一张资源分配表记录各进程与其占用资源之间的关系；设置一张进程等待表记录各进程与要申请资源之间的关系。从资源等待表出发，看有没有形成等待的环路。即可以利用资源分配图的思想来检测是否有死锁发生。,死锁避免：死锁避免的重要是以最小的代价恢复系统的运行，具体的死锁解除的方法有几个：(1)撤消所有死锁进程，代价较大；(2)进程回退（Roll back）再启动，进程在执行过程中，系统会为进程记录一些中间节点，当出现死锁的时候进行回退再一起重新运行，由于需要记录每个进程的现场，所以系统代价也比较大；(3)按照某种原则逐一撤消死锁进程，直到没有死锁；(4)按照某种原则逐一抢占资源（资源被抢占的进程必须回退到之前的对应状态），直到没有死锁。,