第五单元 死锁与饥饿.pptVIP

讨论 Remarks1: 银行家算法要求条件：进程所需资源最大量, 这个信息对于充要性分析是不够的。 Remarks2: 假设：进程预先给出有关资源的命令序列，则可以给出死锁避免的充要性算法，复杂度（NP Complete)。 Remarks3: 预先给出进程有关资源的命令序列是困难的(程序的分枝和循环）。 5.8 死锁的检测 数据结构： Available: array[1..m]of integer; Allocation: array[1..n,1..m]of integer; Request: array[1..n,1..m]of integer; 临时变量： Work: array[1..m]of integer; Finish: array[1..n]of boolean; 死锁检测算法 Work:=Available; Finish:=false; 有满足条件的i: Finish[i]=false Request[i]?Work Finish[i]=true; Work:=Work+Allocation[i] T ?i ,finish[i]=true T F F 无死锁 死锁 Finish[I]=true for allocation[I]=0 Remarks 1. 上述算法可以检测到参与死锁的全部进程，包括占有资 源和不占有资源的进程。 2. 如果希望只检测占有资源的进程，初始化时： Finish[i]=true, for allocation[I]=0 死锁例子 例子：R={A(7),B(2),C(6)}; P={p0,p1,p2,p3,p4} Allocation Request Available Work Finish A B C A B C A B C A B C p0: 0 1 0 0 0 0 0 0 0 p1: 2 0 0 2 0 2 p2: 3 0 3 0 0 0 p3: 2 1 1 1 0 0 p4: 0 0 2 0 0 2 未死锁。 此时，Request[2]=(0,0,1), 死锁，参与死锁进程{p1,p2,p3,p4} 5.8.2 死锁检测时刻 考虑因素： 死锁发生频度； 死锁影响进程。 1. 等待时检测： 发现早，恢复代价小，开销大（overhead)。 2. 定时检测： 3. 资源（eg. CPU）利用率下降时检测。 5.9 死锁恢复 1. 重新启动 简单，代价大，涉及未参与死锁的进程。 2. 终止进程(process termination) 环路上占有资源的进程。 (1) 一次性全部终止；(2) 逐步终止（优先级，代价函数） 3. 剥夺资源(resource preemption)+进程回退(rollback) (1) select a victim；(2) rollback. 问题: (1) 保存snapshot代价大；(2) 消除影响困难; (3) starvation. 5.10 鸵鸟算法 视而不见 Pro: 工程师观点(考虑死锁发生的频率,危害,处理代价) 死锁发生频率其它故障引起的系统瘫痪的频率 死锁处理constant overhead 危害 Cont: 数学家观点 必须处理,无论代价如何 目前系统实际如此 Eg. UNIX proc结构(50 and up) 5.11 有关问题的讨论 关于充要性算法 已知进程关于资源活动序列 困难: 程序中的分枝与循环 复杂度高(NP Complete) 生灭资源问题 消息 消耗性资源与可重用资源并存 关于两阶段封锁 增长阶段有可能死锁 5.12 饥饿与活锁 饥饿(starvation)：当等待时间给进程推进和响应带来明显影响时,称发生了进程饥饿.饥饿到一定程度的进程所赋予的使命即使完成也不再具有实际意义时称该进程被饿死(starved to death). 没有时间上界的等待 排队等待 忙式等待 忙式等待条件下发生的饥饿,称为活锁(live lock). 死锁与饥饿 饥饿 vs 死锁 死锁进程处于等待状态，忙式等待的进程并非处于等待状态