操作系统课件5_2.pptVIP

5.8.1 死锁检测算法 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. 上述算法可以检测到参与死锁的全部进程，包括占有资 源和不占有资源的进程。 如果存在i，1=i=n，finish[i]=false，则系统处于死锁状态，且pi参与了死锁。 对当前不占有资源的进程直接将finish置为true 定理5-2：令p是系统中所有的进程集合，p’是p的子集且为系统中占有资源的进程集合，则p中存在死锁的充要条件是p’中存在死锁。 * 死锁例子 例子：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 死锁检测时刻 何时进行死锁检测主要取决于两个因素 死锁发生的频率； 死锁所涉及的进程个数 通常在如下时刻进行死锁检测 进程等待时检测 定时检测 资源利用率降低时检测 * 5.9 死锁的恢复 重新启动(system restart) 简单，代价大，涉及未参与死锁的进程 终止进程(terminating processes) 终止参与死锁的进程并收回所占资源, 死锁得以解除 两种处理策略:? 一次性撤销所有参与死锁的全部进程, 方法简单, 代价较高 逐一撤销参与死锁的进程 按照某种算法选择一个参与死锁的进程 将其撤销并收回其占有的全部资源 判断是否还存在死锁, 如果是选择下一个将被淘汰的进程 重复直至死锁解除 * 5.9 死锁的恢复 剥夺资源(preempting resources) 剥夺死锁进程所占有的全部或部分资源 实现时分为两种情形: 逐步剥夺: 一次剥夺死锁进程所占有的一个或一组资源, 如死锁尚未解除继续剥夺, 直至死锁解除 一次剥夺: 一次性地剥夺参与死锁进程所占有的全部资源 进程回退(process rollback) 让参与死锁的进程回退到以前没有发生死锁的某个点处, 并由此点开始继续, 希望进程交叉执行时不再发生死锁 * 5.10 鸵鸟算法(ostrich algorithm) 仿鸵鸟遇到危险时将头埋在沙子里的传说而得名 对死锁采取视而不见的处理方法 是目前实际系统采用最多的策略 当死锁真正发生且影响系统正常运行时，手工干预—重新启动 * 5.10 鸵鸟算法 视而不见 工程师观点(考虑死锁发生的频率,危害,处理代价) 死锁发生频率其它故障引起的系统瘫痪的频率 死锁处理constant overhead 危害 数学家观点 必须处理，无论代价如何 * 5.11 有关问题的讨论 关于充要性算法 是一个复杂的问题, 不存在完美的死锁处理方法 关于两阶段封锁 在数据库管理系统中，一个原子事务可能涉及多个数据项 为保证数据完整性，在访问数据项之前需要对其加锁(共享锁或排它锁) 当多个事务同时运行时，加锁冲突可能会导致死锁 * 5.11 有关问题的讨论 关于可剥夺资源问题 进程不会因为处理机而死锁 当内存和虚存均不能满足时会发生死锁，如果有足够大的虚存，则不会死锁 * 5.11 有关问题的讨论 关于消耗型资源问题 前面有关死锁的讨论基本针对可重用资源(reusable resource) 这类资源一次只能分给一个进程，使用完后资源仍存在，可分配给其它进程使用，这是操作系统管理的主要资源 另一类资源称为消耗型资源(consumable resource)，亦称生灭资源，指在系统运行过程中动态产生、动态消亡的资源 对消耗型资源死锁的处理比较困难 * 5