第6章 死锁.ppt

第6章 死锁 主要内容 引论 死锁的示例 死锁的定义与性质 死锁研究 从上面的分析可知会出现死锁，若上例中暂不调度B进程运行，而只运行A和C，则： A? C? A? C? A? C? 系统不会死锁。最后再运行B，也可完成。 四、死锁研究的主要内容 1. 死锁问题有许多内容有待研究，这里主要介绍解决死锁所采用的方法： 忽略此问题不做任何实际处理 (鸵鸟策略) 设计无死锁的系统 允许系统出现死锁后排除之 死锁防止 (deadlock prevention) 死锁避免 (deadlock avoidance) 死锁检测 (deadlock detection) 死锁恢复 (deadlock recovery) 2. 死锁的防止 通过破坏死锁存在的(4个)必要条件来防止死锁发生。我们不妨把死锁的四个必要条件记做C1， C2， C3， C4，把死锁记做D，则有逻辑公式：D? C1?C2? C3? C4，由离散数学公式推导得：? C1?? C2?? C3?? C4??D…(2)式中的“ ?”表示“ 蕴含”；“ ?”表示“ 与”；“ ?”表示“ 或”；“ ?”表示“ 非”。由(2) 式可知，只要系统中有一个必要条件不成立就能不出现死锁，此即死锁防止的思想基础。 (1) 破坏互斥条件 如果允许系统资源都能共享使用，则系统不会进入死锁状态。但这种方法不是切实可行的。因为有些资源若是共享使用。例如：打印机在多进程打印，不能每个进程打印一行，则无法保证其正确性。又如，对临界资源的访问就必须互斥进行。 (2) 破坏占有等待 (二个方法) 方法一：进程申请到它所需要的所有资源后，才能开始运行，又称预先静态分配法。例如，一个制表打印进程，需要有打印机，才能运行。此方法虽可保证无死锁，但是 ? 资源的利用率低 (在程序运行中，打印机空闲)；? 由于所需资源不能在一次中得到全部满足，而使作业无限期延长。 方法二：进程提出申请资源前必须释放已占有的一切资源。这些虽然能提高资源利用率，但要仔细进行程序设计，有时仍需提前申请资源才能保证正确性。这使用户倍感不便。 〖注〗要考虑无限等待现象 (其实质与死锁一样)。 例：P1申请r1, r2, r3，而仅有r3。这时P2申请r3；则把r3给P2，某一进程Pi又释放了r1, r2，而 P1又因无r3，仍需等待……直到饿死P1。 我们应有相应的防止措施。比如按申请资源的先后秩序给进程赋优先级。这种资源预先分配的方法，适于对外存空间的分配。因为作业运行期间所需外存变化不大。 (3) 破坏非剥夺性条件 在进程主动释放占有的资源前即予以剥夺，也能保证系统不出现死锁。 方法一：当进程Pi申请rj类资源时，检查rj中有无可分配的资源，有则分配给Pi；否则将Pi占有的资源全部释放进入等待状态。 方法二：当Pi申请rj时，检查rj中有无可分配的资源，有则分配；否则检查占有rj类资源的进程Pk。若Pk处于等待资源状态，则剥夺Pk的rj分给Pi；若Pk处于不等待资源状态，则置Pi于等待资源状态 (此时Pi原占有的资源可能被剥夺。) 〖注〗剥夺资源时，需保存中间信息。因使用资源的进程尚未主动释放资源，这样开销很大。故只宜在CPU和主存这类重要资源的管理上使用。不宜剥夺临介资源等类型资源。 (4) 破坏循环等待条件 采用资源顺序分配法，可以破坏循环等待条件。该方法首先给系统中的资源编号 (唯一)，即寻找一个函数F：R?N (R：表资源类集合) 即 r1, r2, …, ri ? ? ? 1 2 i F(ri) = i 每个进程只能按序号由小到大的顺序申请资源，而且对它所必须使用的且属于某一类的所有资源，必须一次申请完。 比如：某一进程已占有资源r1, r2, …, ri，又申请ri+1，资源分配程序则检查是否有 ?j?{1,2,…,i}，有F(rj) F(rj+1)，若不满足则拒绝分配。 采用资源顺序分配法，系统不会出现循环等待。因为在任何时刻，总有一个进程占有较高序号的资源，该进程继续请示的资源必然是空闲的。故该进程可一直向前推进。(换言之，系统中总有进程可以顺序运行完毕，这个进程执行结束后会释放它所占有的全部资源……唤醒等待中的进程或满足其它进程的请求。) [证明] 若存在循环等待的一组进程{P0, P1,…, Pn,}，且Pi拥有资源ri，又申请ri+1，根据资源顺序分配原则有： F(r0) F(r1) … F(rn) F(r0) 如右图， 则F(r0) F(r0) 矛盾 r1 P0 r