05第五章 死锁与饥饿1.ppt

第五章 死锁与饥饿 死锁与饥饿 死锁: indefinite wait. 可察觉 饥饿: not necessarily in wait state. ? 死锁和饥饿都是由于进程竞争资源而引起的. 5.1 死锁的概念 死锁定义 一组进程中的每一个进程，均无限期地等待此组进程中某个其他进程占有的，因而永远无法得到的资源，这种现象称为进程死锁。 定义死锁时刻： 无限等待发生时； 等待发生前（已注定死锁）。 由定义得到的结论 几个有用的结论： 参与死琐的进程至少有二个； 每个参与死锁的进程均等待资源； 参与死锁的进程中至少有两个进程占有资源； 死锁进程是系统中当前进程集合的一个子集。 5.2 死锁类型 5.2 死锁类型 5.2 死锁类型 5.2 死锁类型 5.2 死锁类型(Cont.) 5.3 死锁的条件 Coffman条件（必要条件） 资源独占（mutual exclusion） 不可抢占（non preemption） 保持申请（hold-while-applying） 循环等待（circular wait） 当每类资源只有一个实例时，充要条件。 破坏上述任意一个条件可以消除死锁。 5.4 死锁的处理 死锁预防（deadlock prevention）-静态 死锁避免（deadlock avoidance）--动态 死锁检测（deadlock detection） 死锁恢复（deadlock recovery） 5.5 资源分配图 5.5 资源分配图 申请：pi申请rj中的一个资源实例，由pi向rj画一条申请边，如可满足，改为分配边。 释放：去掉分配边。 例子（无环路，无死锁） 例子（有环路，有死锁） 例子（有环路，无死锁） 例子（有环路，无死锁） 资源分配图的约简 寻找一个非孤立且没有请求边的节点pi, 若无算法结束 去除pi的所有分配边使其成为一个孤立节点; 寻找所有请求边都可满足的进程pj, 将pj的所有请求边全部改为分配边; 转步骤1 死锁定理 若算法结束时,所有节点均为孤点,则称资源分配图是完全可约简的,否则称为不可完全约简的. 死锁定理: S为死锁状态的充分必要条件是S的资源分配图不可完全约简. 5.6 死锁预防 对进程有关资源的活动加限制，所有进程遵循这种限制，即可保证没有死锁发生。 优点：简单，系统不需要做什么。 缺点：对进程的约束，违反约束仍可能死锁。 预防方法： 预先分配法； 有序分配法。 预先分配法 进程：运行前申请所需全部资源； 系统： 能够满足，全部分配， 否则，一个也不分配。 破坏“hold-and-wait”条件 缺点： 资源利用效率低； 一次提出申请困难。 有序分配法 有序分配法 有序分配法 优点 与预先分配相比,资源利用率提高. 缺点 资源编号困难; 为保持按序申请,某些暂时不用的资源也需提前申请, 牺牲资源利用率. 例子 例子 例子 5.7 死锁避免 银行家算法(Cont.) 银行家算法(Cont.) 银行家算法(Cont.) 资源分配 安全性检测算法 银行家算法例子 银行家算法例子 银行家算法的保守性 银行家算法的保守性 讨论 5.8 死锁的检测 死锁检测算法 Remarks Remarks 令P是所有进程的集合，P’包含于P是所有占有资源的进程集合，则: P死锁?P’死锁。 死锁检测之后是恢复，只考虑P’中的进程。 死锁检测不考虑P-P’中的进程，缩小了检测范围，降低了系统开销。 死锁例子 死锁检测时刻 5.9 死锁的恢复 5.10 鸵鸟算法 视而不见 Pro: 工程师观点(考虑死锁发生的频率,危害,处理代价) 死锁发生频率 危害 Cont: 数学家观点 必须处理,无论代价如何 目前系统实际如此 Eg. UNIX proc结构(50 and up) 5.11 有关问题的讨论 关于充要性算法 已知进程关于资源活动序列 困难: 程序中的分枝与循环 复杂度高(NP Complete) 生灭资源问题 消息 消耗性资源与可重用资源并存 关于两阶段封锁 增长阶段有可能死锁 5.12 饥饿与活锁 饥饿(starvation)：当等待时间给进程推进和响应带来明显影响时,称发生了进程饥饿.饥饿到一定程度的进程所赋予的使命即使完成也不再具有实际意义时称该进程被饿死(starved to death). 没有时间上界的等待 排队等待 忙式等待 忙式等待条件下发生的饥饿,称为活锁(live lock). 死锁与饥饿 饥饿 vs 死锁 死锁进程处于等待状态，忙式等待的进程并非处于等待状态, 但却可能被饿死; 死锁进程等待永远不会释放的资源, 饿死进程等待可能被释放,但却不会分给自己的资源,其等待时间没有上界; 死锁一定发生了循环等待,饿死不然; 死锁至少涉及两个进程, 饿死进程可能只有