OS03实时调度死锁2014-2015-2讲解.ppt

操作系统Operating Systems;;系统处理能力;讨论;实时调度算法的分类;非抢占式轮转调度算法;非抢占式优先调度算法; 基于时钟中断的抢占式优先权调度算法;立即抢占的优先权调度算法 ;常用的几种实时调度算法;通常的优先级调度不能适用于实时系统;通常的优先级调度不能适用于实时系统;EDF算法用于抢占调度方式;;利用LLF算法进行调度的情况;利用LLF算法进行调度的情况;3.5 产生死锁的原因和必要条件;产生死锁的原因 ;产生死锁的原因 ;系统有同类资源m个，被n个进程共享，当mn 和m≤n时，每个进程最多可以请求多少个这类资源时，系统一定不会发生死锁？ 当m ≤ n 时: 每个进程最多申请1个这类资源时，系统一定不会发生死锁 当mn时:假设每个进程最多申请x个这类资源 若每个进程申请x-1个这类资源后，系统还剩下一个资源，就能保证某一个进程能分配到全部x个资源，并能??行到底，最终释放这x个资源。即： n*（x -1） m x(m/n)+1;竞争资源引起进程死锁;在系统中所配置的不可抢占性资源，由于它们的数量不能满足诸进程运行的需要，会因争夺这些资源而陷入僵局。;m3;竞争可消耗资源引起进程死锁;2. 进程推进顺序不当引起死锁 ;进程推进顺序;死锁的基本概念;死锁的基本概念;3.5.3　产生死锁的必要条件;处理死锁的方法;3.6　预防死锁;1. 破坏“请求和保持”条件;2.破坏“不可抢占”条件;3.破坏“环路等待”条件;讨论;3.7　避免死锁; ; ; ;3．由安全状态向不安全状态的转换;3．由安全状态向不安全状态的转换;3．由安全状态向不安全状态的转换;3．由安全状态向不安全状态的转换;3.7.2　利用银行家算法避免死锁;银行家算法中的数据结构;银行家算法中的数据结构;银行家算法中的数据结构;2．银行家算法(1);2．银行家算法(2);3.安全性算法(1);3.安全性算法(2);实例说明系统所处的安全或不安全状态;（1）在时刻T0,系统目前资源分配情况如下： 每个进程目前还需资源为Need 进程 Max Allocation Available A B C A B C A B C P0 7 5 3 0 1 0 3 3 2 P1 3 2 2 2 0 0 P2 9 0 2 3 0 2 P3 2 2 2 2 1 1 P4 4 3 3 0 0 2; 进程 Work Need Allocation Work=Work+allocation A B C A B C A B C A B C;可以断言T0时刻，系统处于安全状态 因为序列{P1,P3,P4,P2,P0}能满足安全性条件。 （2）进程P1申请资源request1=(1,0,2) ，系统能将资源分配给它吗？ ;Need A B C 7 4 3 6 0 0 0 1 1 4 3 1 ;判定新状态是否安全? 找到一个进程序列 可保证进程P1运行完毕并归还资源 ;（3）进程P4申请资源request4=(3,3,0) 检查: request4(3,3,0) ≤ Need4(4,3,1) and request4 (3,3,0) ≥ Available(2,3,0) 让P4等待;（4） P0请求资源 request0=(0,2,0); 检查: request0 (0,2,0) ≤ Need0(7,4,3) and request0 (0,2,0) ≤ Available(2,3,0) 结果满足条件，试分配。 ;死锁避免;3.8　死锁的检测与解除 ;　1．资源分配图;2．死锁定理;资源分配图的简化;资源分配图的一个例子;3.8.2　死锁的解除;一、选择题 (1)产生死锁的基本原因是_______和_______，产生死锁的四个必要条件是互斥条件，_______，不可抢占条件和