操作系统ppt课件第4章.ppt

1 第4章死锁处理 本章知识点 4 1死锁问题概述4 2死锁处理4 3哲学家用餐问题 2 4 1死锁问题概述 死锁是由于进程间相互竞争系统资源或通信而引起的一种阻塞现象 如果操作系统不采取特别的措施 这种阻塞将永远存在 最终可能导致整个系统处于瘫痪状态 因此 死锁问题是操作系统中需要考虑的重要问题 3 4 1 1可重用资源 下面是一个使用可重用资源而发生死锁的例子 两个进程P1和P2竞争必须互斥访问的磁盘文件D和磁带机T 程序重复地执行以下操作 P1P2repeatrepeat Request D Request T Request T Request D Release T Release D Release D Release T foreverforever 4 4 1 2消耗型资源 下面是使用消耗型资源而发生死锁的例子 P1P2 Receive P2 M Receive P1 Q Send P2 N Send P1 R 如果Receive阻塞就会发生死锁 5 4 1 3产生死锁的条件 系统产生死锁有四个必要条件 互斥 占用并等待非强占循环等待 6 4 2死锁处理 为了使系统不发生死锁 必须设法破坏产生死锁的四个必要条件之一 或者允许死锁产生 但当死锁发生时能检测出死锁 并有能力实现恢复 7 4 2 1死锁预防 死锁预防是设法至少破坏产生死锁的必要条件之一 除互斥条件之外 从而消除产生死锁的任何可能性 严格地防止死锁的出现 但方法过于保守 对资源限制严格 使资源利用率和进程执行效率大大降低 它是以降低处理速度作为代价的 8 4 2 1死锁预防 1 互斥可用第3章介绍的解决互斥问题的思想和技术来解决有关由于互斥条件不满足而产生的死锁问题 9 4 2 1死锁预防 2 破坏 占用并等待 条件采用资源的静态预分配策略 一次申请所有的资源 优点 简单安全 易于实施 在进程的活动较单一时性能好 无须抢占 缺点 资源利用率低 启动进程慢 效率低 有 饥饿 现象存在 10 4 2 1死锁预防 3 破坏 非抢占 条件方法1 若拥有某种资源的进程在申请其他资源时遭到拒绝 则它必须释放其占用的资源 以后若有必要可再次申请上述资源 方法2 当一进程申请的资源正被其他进程占用时 可通过操作系统抢占该资源 此方法在两个进程优先级相同时 不能防止死锁 优点 对状态容易保留和恢复的资源较为方便 缺点 实现困难 恢复现场代价高 导致过多的不必要抢占 易导致循环重启 11 4 2 1死锁预防 4 破坏 循环等待 条件采用资源定序方法 将所有资源按类型线性排队 并按递增规则编号 进程只能以递增方式申请资源 因而不会导致循环等待 优点 资源的申请与分配逐步进行 比预分配策略的资源利用率高 易实现编译期间的检查 无须执行时间 在系统设计阶段问题就已解决 缺点 严格限制资源的顺序性 不允许增加资源请求 在使用资源的顺序与系统规定不一致时 资源利用率降低 不能抢占 12 4 2 2死锁避免 死锁避免方法并不是严格限制产生死锁必要条件的存在 只是防止系统进入不安全状态 从而避免死锁的发生 死锁避免算法就是避免系统进入不安全状态的算法 银行家 Banker 算法是最著名的死锁避免算法 13 4 2 2死锁避免 1 避免启动新进程执行一个新进程 当且仅当当前所有进程和新进程的最大资源需求量之和能被系统满足时 才能启动一个新的进程 这个方法并不是最优的 因为它考虑的是最坏的情况 即所有的进程都使用它们最大的资源需求量 这会导致很多实际上可以运行的进程被剥夺了运行的权利 14 4 2 2死锁避免 2 避免分配资源避免分配资源也称作Banker 银行家 算法 Banker算法的主要思想 若进程Pi的申请超过了其申报的最大需求数 则报错 若进程Pi的申请超过了可用资源数 则Pi必须等待 系统暂时为进程Pi分配其所需要的资源 修改资源分配状态 调用安全算法检查系统当前状态 若导致不安全状态 则推迟这种分配 15 4 2 2死锁避免 优点 无须抢占 比死锁预防限制少 允许更多的进程并发执行 缺点 必须知道未来的资源请求信息 要预先声明资源的最大需求量 进程必须是独立的 其执行顺序不受同步要求的约束 资源和进程的数目必须固定 可能导致进程的长时间阻塞 16 4 2 3死锁检测 基本思想 在某时刻t 求得系统中各类可利用资源的数目向量w t 对于系统中的一组进程 p1 p2 pi pn 找出那些对各类资源请求数目均小于系统现在所拥有的各类资源数目的进程 这样的进程能够获得它们所需要的全部资源并运行结束 当它们运行结束后释放所占有的全部资源 从而使可用资源数目增加 这样的进程加入到可运行结束的进程序列L中 然后对剩下的进程再作上述考查 如果一组进程 p1 p2 pn 中有几个进程不属于序列L中 那么它们会被死锁 17 4 2 3死锁检测 优点 不会推迟进程的启动 在线处理比较便利 缺点 丢失了固有的抢占 执行检测算法需要一定的CPU开销 18 4 2 4死锁恢复 一旦检测到死锁 就要有恢复的方法 恢复死锁的基本方法是剥夺 通常恢复方法是人工抽去一些作业 释放它们占有的资源 再重新启动系统 19 4 2 5处理死锁的综合方法 处理死锁的方法有多种 它们各有优缺点 在不同的环境中使用不同的方法就比只用一种方法要好得多 对资源进行分类对不同类型资源 使用资源定序的方法 对同一类资源 使用最佳的处理方法 20 4 3哲学家用餐问题 哲学家用餐问题是一个死锁和饥饿的典型问题 也是一大类并发控制所面临的问题 方法1 每个哲学家先拿其左