OS05存储管理

《OS05存储管理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章死锁与饥饿死锁的概念死锁的类型死锁的条件死锁处理资源分配图死锁预防死锁避免死锁发现死锁恢复饥饿与活锁第五章死锁与饥饿重点:死锁的概念;产生死锁的条件,如何判断是否产生死锁—死锁发现.死锁预防,以及如何避免死锁:银行家算法.难点:死锁避免:银行家算法死锁发现学习指导本章介绍的预防、避免、检测与恢复策略，在大多数实际系统中并未采用，一方面因为开销，另一方面因为使用的方便性。然而本章内容仍是重要的，尤其是死锁避免与检测。包括安全状态与安全序列的定义和检查算法、避免死锁的资源分配算法。读者应当认真区分死锁避

2、免算法与死锁检测算法之间的本质差别，尽管这两个算法在结构上很相似，差别只在Need与Work的比较和Request与Work的比较。饥饿与饿死反映了资源分配策略的不公平性，应当从进程状态方面理解饥饿与死锁之间的差别。学习指导死锁是操作系统的棘手问题，因为不存在处理死锁的完美方法。从理论上来说，如果给定进程有关资源的命令序列，可以给出避免死锁的充分必要算法，尽管其开销很大（NP完全），但实际以序列形式给出的资源需求对于稍微复杂一点的程序都是不现实的。第五章死锁与饥饿死锁与饥饿死锁:indefinitewai

3、t.可察觉饥饿:notnecessarilyinwaitstate.?死锁和饥饿都是由于进程竞争资源而引起的.5.1死锁的概念例子：r1和r2为可再用资源;P1:applyforr1;...applyforr2;...returnr1;...returnr2;P2:applyforr2;...applyforr1;...returnr1;...returnr2;12死锁定义一组进程中的每一个进程，均无限期地等待此组进程中某个其他进程占有的，因而永远无法得到的资源，这种现象称为进程死锁。定义死锁时刻：无限等

4、待发生时；等待发生前（已注定死锁）。由定义得到的结论几个有用的结论：参与死锁的进程至少有二个；每个参与死锁的进程均等待资源；参与死锁的进程中至少有两个进程占有资源；死锁进程是系统中当前进程集合的一个子集。5.2死锁类型1.竞争资源引起的死锁（1）不同种资源（2）同种资源4台打印机，申请:a,释放aP1:aaaaaaaaP2:aaaaDBACW:直行E：左转S：左转5.2死锁类型(Cont.)2.进程通讯引起的死锁P1：receive(P2,M1);P2:receive(P3,M2);P3:receive(

5、P1,M3);M1M2M3P1P2P3其它原因引起的死锁Afteryou/afteryou5.3死锁的条件Coffman条件（必要条件）资源独占（mutualexclusion）不可抢占（nonpreemption）保持申请（hold-while-applying）循环等待（circularwait）当每类资源只有一个实例时，充要条件。破坏上述任意一个条件可以消除死锁。5.4死锁的处理不让死锁发生：预防（deadlockprevention）-静态死锁避免（deadlockavoidance）--动态允许

6、死锁：检测+消除死锁检测（deadlockdetection）死锁恢复（deadlockrecovery）5.5资源分配图定义:G=(V,E),V=PR,P={p1,p2,…,pn},R={r1,r2,…,rm},E={(pi,rj)}{(rj,pi)},piP,rjR.申请边(pi,rj):pi申请rj；分配边(rj,pi):rj分配pi;图示：进程：资源：申请边：由进程到资源类；分配边：由资源实例到进程。5.5资源分配图申请：pi申请rj中的一个资源实例，由pi向rj画一申请边，如可满足，改为

7、分配边。释放：去掉分配边。例子（无环路，无死锁）例1.P={p1,p2,p3},R={r1(1),r2(2),r3(1),r4(3)}E={(p1,r1),(p2,r3),(r1,p2),(r2,p1),(r2,p2),(r3,p3)}p1p2p3r1r3r2r4例子（有环路，有死锁）p1p2p3r1r3r2r4增加边（p3,r2)例子（有环路，无死锁）p1p2p3p4r1r2资源分配图约简与死锁定理p1p2p3r1r2找到一个非孤立且没有请求边，或有请求边但资源可以满足其要求的节点。去除其请求边和分配边

8、，使其成为孤立节点。寻找可满足请求的进程，将其请求边改为分配边，然后去除其全部分配边。重复上述步骤，直到不能再进行为止。如果上述过程结束，所有节点均为孤立节点，则称该资源分配图可以完全约简，否则为不可完全约简。死锁定理：S为死锁状态的充分必要条件是S的资源分配图不可完全约简。5.6死锁预防对进程有关资源的活动加限制，所有进程遵循这种限制，即可保证没有死锁发生。优点：简单，系统不需要做什么。缺点：对进程的约束，违反约束仍可能死锁