现代操作系统第3章死锁.ppt

《现代操作系统第3章死锁.ppt》由会员分享，可在线阅读，更多相关《现代操作系统第3章死锁.ppt（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、死锁第3章1 1 3.1.资源 3.2.死锁概述 3.3.驼鸟算法 3.4.死锁检测和死锁恢复 3.5.死锁避免 3.6.死锁预防 3.7.其他问题死锁的概念：可能死锁我需要A和B道我需要B和C道我需要C和B道我需要D和A道发生死锁停止直到B可以通车停止直到C可以通车停止直到D可以通车停止直到A可以通车资源一些独占性资源一些独占性资源 打印机打印机 磁带磁带 系统内部表中的表项系统内部表中的表项进程需要一个合理的顺序去访问资源进程需要一个合理的顺序去访问资源假设一个进程拥有资源假设一个进程拥有资源 A A 并请求资源并请求资源 B B 同时另一个进程拥有同时另一个进程拥有B B 并请求并请求A

2、 A 两个进程都被阻塞两个进程都被阻塞,并且一直处于这样的状态并且一直处于这样的状态4 4资源(1)死锁有可能出现,当进程对设备、文件等取得了排他性访问权时进程对设备、文件等取得了排他性访问权时我们把这类需要排他性使用的对象称为资源我们把这类需要排他性使用的对象称为资源resourcesresources可抢占资源可以从拥有它的进程中抢占而不会产生任何副作可以从拥有它的进程中抢占而不会产生任何副作用用不可抢占资源指在不引相关的计算失败的情况下，无法把它从指在不引相关的计算失败的情况下，无法把它从占有它的进程处抢占过来占有它的进程处抢占过来5 5进程推进顺序不当产生死锁进程程P请求求读卡机卡机请

3、求打印机求打印机释放放读卡机卡机释放打印机放打印机进程进程Q请求请求打印机打印机请求读卡机请求读卡机释放读卡机释放读卡机释放打印机释放打印机PV操作使用不当产生死锁进程程Q1.P(S1)P(S2).使用使用r1和和r2V(s1)V(s2)进程进程Q2.P(S2)P(S1).使用使用r1和和r2V(s2)V(s1)同类资源分配不当若系若系统中有中有m个个资源被源被n个个进程共享，程共享，当每个当每个进程都要求程都要求K个个资源，而源，而mn*k时，即，即资源数小于源数小于进程所要求的程所要求的总数数时，如果分配不得当就可能引起死如果分配不得当就可能引起死锁例如，例如，m=5 n=5 k=2，分配

4、策略，分配策略为每每个个进程程轮流分配，首先第一次每个流分配，首先第一次每个进程程都分配一个，在第二都分配一个，在第二轮分配分配时就会出就会出现死死锁资源(2)使有一人资源所需要的事件顺序可以用抽象的形式表示如下：1.请求资源请求资源2.使用资源使用资源3.释放资源释放资源 若请求资源不可用，则请求进程被迫等待请求进程可能被阻塞请求进程可能被阻塞资源请求返回一个错误代码资源请求返回一个错误代码1010死锁的概述形式化定义形式化定义:如果一个进程集合中的每个进程都在等待只能由该进程集合中如果一个进程集合中的每个进程都在等待只能由该进程集合中的其他进程才能引发的事个，那么该进程集合就是死锁的其他进

5、程才能引发的事个，那么该进程集合就是死锁在大多数情况下，每个进程所等待的事件是释放该进在大多数情况下，每个进程所等待的事件是释放该进程集合中其他进程所占有的资源程集合中其他进程所占有的资源没有一个进程可以没有一个进程可以 运行运行 释放资源释放资源 被唤醒被唤醒1111死锁的正式定义假假设1：任意一个：任意一个进程要求程要求资源的最大数量不超源的最大数量不超过系系统能提供的最大量能提供的最大量假假设2：如果一个：如果一个进程在程在执行中所提出的行中所提出的资源要源要求能求能够得到得到满足，那么，它一定能在有限的足，那么，它一定能在有限的时间内内结束束假假设3：一个：一个资源在任何源在任何时间最

6、多只有一个最多只有一个进程程所占有所占有假定假定4：一个：一个进程一次申程一次申请一个一个资源，且只在申源，且只在申请资源得不到的源得不到的满足足时才才处于等待状于等待状态。（即不。（即不考考虑人工干人工干预，等，等 待外待外设的情况）的情况）死锁的正式定义假定假定5：一个：一个进程程结束束时释放它占有的全部放它占有的全部资源源假定假定6：系：系统具有有限个具有有限个进程和有限个程和有限个资源源定定义：如果一个：如果一个进程集合中的每个程集合中的每个进程都在等待程都在等待只能由只能由该集合中的其他一个集合中的其他一个进程才能引程才能引发的事件，的事件，则称一称一组进程或系程或系统此此时发生了死

7、生了死锁。竞争资源引起进程死锁可剥可剥夺和和非剥非剥夺性性资源源竞争非剥争非剥夺性性资源源竞争争临时性性资源源永久性永久性资源：可以被多个源：可以被多个进程多次使用程多次使用（可再用（可再用资源）源）1.可可抢占占资源源2.不可不可抢占占资源源临时性性资源：只可使用一次的源：只可使用一次的资源；如信源；如信号量号量,1.中断信号，同步信号等（可消耗性中断信号，同步信号等（可消耗性资源）源）2.“申申请-分配分配-使用使用-释放放”模式模式死锁的四个条件1.1.互斥条件互斥条件 每个资源要么已经分配给了一个进程，要么就是可用每个资源要么已经分配给了一个进程，要么就是可用的的2.2.占有和等待条件

8、占有和等待条件 已经得到了某个资源的进程可以再请求新的资源已经得到了某个资源的进程可以再请求新的资源3.3.不可抢占条件不可抢占条件 已经分配给一个进程的资源不能强制性地被抢占，它已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放只能被占有它的进程显式地释放4.4.环路等待条件环路等待条件 一定有由两个或两个以上的进程组成的一条环路一定有由两个或两个以上的进程组成的一条环路 该环路中的每个进程都在等待着下一个进程所占有的该环路中的每个进程都在等待着下一个进程所占有的资源资源1515死锁建模(2)有向图建模（资源分配图）有向图建模（资源分配图）资源资源 R R 分配给进程

9、分配给进程A A 进程进程B B 请求或等待资源请求或等待资源S S 进程进程 C C和和D D为得到资源为得到资源T T 和和U U处于死锁处于死锁1616死锁建模(3)处理死锁的策略1.1.忽略问题忽略问题2.2.检测并恢复检测并恢复3.3.动态避免动态避免 仔细对资源分配仔细对资源分配4.4.防止防止 破坏引起死锁的四个必要条件之一破坏引起死锁的四个必要条件之一1717死锁建模(4)死锁是如何发生的1818A B C死锁建模(5)死锁是如何避免的1919(o)(p)(q)驼鸟算法假装根本没有问题发生可以接受，如果如果死锁发生频率低如果死锁发生频率低防止死锁的成本太高了防止死锁的成本太高了

10、UNIX 和Windows 采用此算法它是下面两者的折衷 方便性方便性正确性正确性2020每种类型一个资源的死锁检测(1)注意资源的所属和请求关系注意资源的所属和请求关系如果图中包含一个或一个以上的环，那么死锁就存在如果图中包含一个或一个以上的环，那么死锁就存在2121资源分配图化简化简：一个进程的所有资源要求均能被满足，则该进化简：一个进程的所有资源要求均能被满足，则该进程得到其所需全部资源从而不断取得进展，直至完成程得到其所需全部资源从而不断取得进展，直至完成全部任务并释放出全部资源。全部任务并释放出全部资源。在有向图中找到既非阻塞又非孤立的结点，分配在有向图中找到既非阻塞又非孤立的结点，

11、分配它所需的全部资源后，当它继续执行并完成然后它所需的全部资源后，当它继续执行并完成然后释放其全部资源而使之成为孤立结点。释放其全部资源而使之成为孤立结点。把孤立结点释放的资源分配给阻塞进程，使之能把孤立结点释放的资源分配给阻塞进程，使之能继续运行，并且在有限时间后完成，再释放其全继续运行，并且在有限时间后完成，再释放其全部资源而成为新的鼓励结点。部资源而成为新的鼓励结点。经过一系列上述步骤，若能消去图中所有的边，经过一系列上述步骤，若能消去图中所有的边，使所有进程都成为孤立结点，则图可完全化简。使所有进程都成为孤立结点，则图可完全化简。否则为不可完全化简。否则为不可完全化简。死死锁定理：当且

12、定理：当且仅当系当系统某状某状态S所所对应的的资源分配源分配图是不可化是不可化简的，的，则S是是死死锁状状态。而不可被化。而不可被化简的的进程即是被程即是被死死锁的的进程。反之，若状程。反之，若状态S所所对应的的资源分配源分配图是可化是可化简的，的，则S是安全状是安全状态。资源分配源分配图的化的化简结果与化果与化简顺序无关，序无关，最最终结果是相同的果是相同的每种类型多个资源的死锁检测(2)死锁检测算法的数据结构死锁检测算法的数据结构2424每种类型多个资源的死锁检测(3)死锁检测算法的例子死锁检测算法的例子2525从死锁中恢复(1)利用抢占恢复将某一资源从一个进程强行取走给另一个进将某一资源

13、从一个进程强行取走给另一个进程使用程使用取决于该资源本身的特性。取决于该资源本身的特性。利用回滚恢复周期性对进程进程进行检查点检查周期性对进程进程进行检查点检查使用检查点保存资源状态使用检查点保存资源状态如果发现死锁回滚进程如果发现死锁回滚进程2626从死锁中恢复(2)通过杀死进程恢复最直接也是最简单的解决死锁的方法最直接也是最简单的解决死锁的方法杀掉环中的一个进程杀掉环中的一个进程环外的进程释放其资源环外的进程释放其资源杀死可以从头开始重新运行而且不会带来副作用杀死可以从头开始重新运行而且不会带来副作用的进程的进程2727资源轨迹图替代方案3.5.2 产生死锁的必要条件互斥互斥：竞争的争的资

14、源一次只能被一个源一次只能被一个进程使用。程使用。请求和保持条件；求和保持条件；当一个当一个进程已程已经占有了一些占有了一些资源，同源，同时又要申又要申请新的新的资源，若新源，若新资源申源申请失失败，进程将占有程将占有资源且阻塞等待。源且阻塞等待。不剥不剥夺条件（不可条件（不可强占）占）:一个一个资源源仅能被占有它的能被占有它的进程所程所释放放,而而不能被不能被别的的进程程强行行强占占环路等待条件路等待条件:若干个若干个进程构成程构成环行行请求求链,其中每个其中每个进程均占有若程均占有若干种干种资源中的某一种源中的某一种,同同时每个每个进程程还要求要求(链上上)下一下一进程所占有的程所占有的资

15、源源.以上前三个条件是死以上前三个条件是死锁存在的必要条件，但不是充分条件。第四个存在的必要条件，但不是充分条件。第四个条件是前三个条件同条件是前三个条件同时存在存在时产生的生的结果。所以果。所以这些条件不是完全些条件不是完全 独立的独立的3.5.2 产生死锁的必要条件破坏第一个条件（互斥条件），使资源破坏第一个条件（互斥条件），使资源可同时访问而不是互斥使用，是简单的可同时访问而不是互斥使用，是简单的方法。磁盘可以用这种方法管理，但许方法。磁盘可以用这种方法管理，但许多资源往往是不能同时访问的，这种做多资源往往是不能同时访问的，这种做法许多场合行不通法许多场合行不通3.5.2 产生死锁的必要

16、条件采用抢占式的调度方法可以破坏第三个采用抢占式的调度方法可以破坏第三个条件（不剥夺条件），但剥夺调度方法条件（不剥夺条件），但剥夺调度方法目前只适用于对主存资源和处理器资源目前只适用于对主存资源和处理器资源的分配。的分配。比较实用的方法是破坏第二个条件或第比较实用的方法是破坏第二个条件或第四个条件四个条件3.5.2 产生死锁的必要条件静态分配策略（破坏占有和等待条件）静态分配策略（破坏占有和等待条件）层次分配策略（阻止环路等待条件）：层次分配策略（阻止环路等待条件）：一个进程得到某一层的一个资源后，它一个进程得到某一层的一个资源后，它只能再申请在较高一层的资源。只能再申请在较高一层的资源。3

17、.5.3 处理死锁的基本方法1.预防死防死锁(破坏破坏4条件之一，缺点：低效条件之一，缺点：低效)。2.避免死避免死锁(属于事先属于事先预防，在防，在资源的源的动态分配分配过程程中，用某种方法去防止系中，用某种方法去防止系统进入不安全状入不安全状态)。3.检测死死锁(不事先采取任何措施，也不必不事先采取任何措施，也不必检查是否是否进入不安全区，而是允入不安全区，而是允许系系统在运行的在运行的 过程中程中发生死生死锁。但可以通。但可以通过系系统所所设置的置的检测机构，机构，实时检测出死出死锁的的发生，并精确的确定与死生，并精确的确定与死锁有关有关的的进程和程和资源；然后，采取适当措施从系源；然后

18、，采取适当措施从系统中将中将已已经发生的死生的死锁清除掉清除掉)。4.解除死解除死锁(与与检验死死锁相配套的一套措施相配套的一套措施)。3.5.3 处理死锁的基本方法 1.预防死防死锁的方法的方法 在系在系统设计时确定确定资源分配算法，保源分配算法，保证不不发生生死死锁。具体的做法是破坏。具体的做法是破坏产生死生死锁的四个必要条件之的四个必要条件之一一 1)资源一次性分配；源一次性分配；(破坏破坏请求和保持条件求和保持条件)2)可剥可剥夺资源；即当某源；即当某进程新的程新的资源未源未满足足时，释放已占有的放已占有的资源源(破坏不可剥破坏不可剥夺条件条件)3)资源有序分配法；做法：系源有序分配法

19、；做法：系统给每每类资源源赋予予一个一个编号，每一个号，每一个进程按程按编号号递增的增的顺序序请求求资源，源，释放放则相反相反(破坏破坏环路等待条件路等待条件)死锁避免资源轨迹图两个进程的资源轨迹图3838确定是否安全状态在P2完成之后P2完成P1完成安全状态不安全状态 假设这时假设这时P1申请一个申请一个R1和一个和一个R3，状态还是安状态还是安全吗？是否全吗？是否拒绝拒绝P1?安全状态和不安全状态(1)说明（a）中的状态为安全状态4444(a)(b)(c)(d)(e)安全状态和不安全状态(2)说明（b）中的状态为不安全状态safe4545(a)(b)(c)(d)单个资源的银行家算法三个资源

20、分配状态三个资源分配状态 安全安全 安全安全 不安全不安全4646(a)(b)(c)多个资源的银行家算法多个资源的银行家算法例子多个资源的银行家算法例子4747银行家算法实例假定系假定系统中有五个中有五个进程程P0,P1,P2,P3,P4和三和三类资源源A,B,C，各种，各种资源的数量分源的数量分别为10、5、7，在，在T0时刻的刻的资源分配情况如源分配情况如图 3-15 所示。所示。T0时刻的安全性：(2)P1请求求资源源：P1发出出请求求向向量量Request1(1，0，2)，系系统按按银行家算法行家算法进行行检查：Request1(1,0,2)Need1(1,2,2)Request1(1

21、,0,2)Available1(3,3,2)系系统先先假假定定可可为P1分分配配资源源，并并修修改改Available,Allocation1和和Need1向向量量，由由此此形形成成的的资源源变化化情情况况如如图 3-16 中的中的圆括号所示。括号所示。再利用安全性算法再利用安全性算法检查此此时系系统是否安全。是否安全。先看进程已拥有的资源数目以及还需要的资源数目，先看进程已拥有的资源数目以及还需要的资源数目，看系统可提供的资源数目是否满足该进程还需要的资看系统可提供的资源数目是否满足该进程还需要的资源数目，若可以满足则将资源分配给该进程，该进程源数目，若可以满足则将资源分配给该进程，该进程用

22、完后释放，释放后系统重新计算可提供的资源数目，用完后释放，释放后系统重新计算可提供的资源数目，再分配给下一个可以满足需求的进程。再分配给下一个可以满足需求的进程。(3)P4请求求资源：源：P4发出出请求向量求向量Request4(3，3，0)，系系统按按银行家算法行家算法进行行检查：Request4(3,3,0)Need4(4,3,1);Request4(3,3,0)Available(2,3,0)，让P4等等待待。(4)P0请求求资源源：P0发出出请求求向向量量Requst0(0，2，0)，系，系统按按银行家算法行家算法进行行检查：Request0(0,2,0)Need0(7,4,3);Re

23、quest0(0,2,0)Available(2,3,0);系系统暂时先假定可先假定可为P0分配分配资源，并修改有关数源，并修改有关数据，如据，如图 3-18 所示。所示。3.7 死锁的检测条件条件：允：允许死死锁必要条件存在，也未采用避免死必要条件存在，也未采用避免死锁的的算法（提高算法（提高资源利用率）源利用率）故死故死锁可能可能发生，需生，需检测！定定义：实际地地检查系系统中是否存在死中是否存在死锁，并，并标出那些出那些进程和程和资源被源被牵扯在死扯在死锁中。中。应用用：允：允许前三个死前三个死锁的必要条件存在的系的必要条件存在的系统中，中，检查系系统中是否存在循中是否存在循环等待条件。

24、等待条件。方法方法：资源分配源分配图死锁预防破坏互斥条件一些设备(例如打印机)假脱机惟一真正请求使用物理打印机的进程是打印机惟一真正请求使用物理打印机的进程是打印机的守护进程的守护进程这样消除因打印机产生死锁这样消除因打印机产生死锁并不是所有的设备都可以使用假脱机技术原理:避免分配那些不是绝对必需的资源避免分配那些不是绝对必需的资源尽量做到尽可能少的进程可以真正请求资源尽量做到尽可能少的进程可以真正请求资源5555破坏占有和等待条件所有进程在开始执行前请求所需的全部资源所有进程在开始执行前请求所需的全部资源 一个进程不会因其他资源而等待一个进程不会因其他资源而等待问题问题 很多进程直到运行时才

25、知道它需要多少资源很多进程直到运行时才知道它需要多少资源 资源利用率不是最优的资源利用率不是最优的变种变种:进程请求先暂时释放其当前占用的所有资源进程请求先暂时释放其当前占用的所有资源 然后再尝试一次获得所需的全部资源然后再尝试一次获得所需的全部资源5656破坏不可抢占条件破坏第三个条件也是可能的假若一个进程已分配到一台打印机正在打印输出正在打印输出现在强制地把它占有的打印机抢占现在强制地把它占有的打印机抢占!?!?5757 破坏环路等待条件(1)对资源排序编号资源分配图资源分配图5858(a)(b)破坏环路等待条件(1)死锁预防方法汇总死锁预防方法汇总5959其他问题两阶段加锁第一阶段第一阶

26、段 进程试图对所有所需的记录进行加锁，一次锁一个进程试图对所有所需的记录进行加锁，一次锁一个记录记录 如果第一阶段加锁成功如果第一阶段加锁成功,就开始第二阶段就开始第二阶段(在第一阶段并没有做实际的工作在第一阶段并没有做实际的工作)如果第一阶段成功，那以开始第二阶段如果第一阶段成功，那以开始第二阶段,执行更新执行更新 释放锁释放锁注意这类似于同时请求所有资源注意这类似于同时请求所有资源算法只有当程序员仔细安排了程序算法只有当程序员仔细安排了程序 使得第一阶段程序在任意一点停下来，并重新开始使得第一阶段程序在任意一点停下来，并重新开始而不会产生错误而不会产生错误6060通信死锁两个进程通信可能会

27、导致死锁每个进程因为等待另外一个进程引发的事件每个进程因为等待另外一个进程引发的事件而产生阻塞而产生阻塞通过超时技术解决书P258例子通过信号量解决进程通过含有两个信号量的函数进程通过含有两个信号量的函数 (mutexmutex 和和另一个信号量另一个信号量)如果以错误的顺序工作，那么会导致死锁如果以错误的顺序工作，那么会导致死锁6161活锁（livelock）活锁是死锁的一个特例因为没有出现死锁现象，进程没有阻塞，但是进程也无法推进解决方法：让程序等待一段随机长的时间，然后再尝试运行活锁一般出现在表抢占的情况。如果有n个进程，每个进程都申请了1/n个资源，那么就会占用1个表，如何解决？多尝试或使用鸵鸟算法6262饥饿算法分配资源可能短作业优先可能短作业优先在系统中多个短作业可以工作得很好可能导致长作业无限期推后尽管它没有被阻塞尽管它没有被阻塞解决方案:先来先服务资源分配策略先来先服务资源分配策略6363