计算机操作系统（杨海秀）第三章 处理机调度与死锁.pptVIP

五、死锁的检测与解除 完全化简：逐个找出既不阻塞又非独立的进 程结点，消去其请求边和分配边，直至所有 进程结点都孤立。 五、死锁的检测与解除 死锁的解除 剥夺资源：代价最小地选择一个牺牲品。从其它进程剥夺足够数量的资源给死锁进程。 撤消进程：代价最小地将死锁进程撤消。终止所有死锁进程，或每次终止一个死锁进程，直至死锁环解除。 习题 设有4个作业同时到达，每个作业的执行时间均为2个小时，它们在一台处理机上按单道方式执行，则平均周转时间为（ ） A、2小时， B、5小时 C、2.5小时 D、8小时 答案：B 习题 某系统采用短作业优先的调度策略，现有作业序列：作业1（提交时间：8:00,运行时间1.50） 作业2（提交时间：8:30,运行时间0.80） 作业3（提交时间：9:00,运行时间0.10） 作业4（提交时间：9:30,运行时间0.30） 其平均带权周转时间为____。 答案：3.00 习题 死锁预防是保证系统不进入死锁状态的静态策略,其解决办法是破坏产生死锁的四个必要条件之一.下列方法中哪一个是破坏了“循环等待”条件 A、银行家算法B、一次性分配策略C、剥夺资源法D、资源有序分配策略 答案：D 习题 银行家算法是一种 ( )算法. A、死锁解除 B、死锁避免C、死锁预防 D、死锁检测 答案：B 习题 死锁的4个必要条件无法破坏的是( ) A、互斥条件 B、请求与保持条件 C、非抢夺条件 D、循环等待条件 答案：A * * * * 竞争资源引起进程死锁 竞争临时性资源 临时性资源：指由一个进程产生，被另一进程使用一短暂时间后便无用的资源。 例子 竞争资源引起进程死锁 竞争临时性资源 P1：…Release(S1)；Request(S3)… P2：…Release(S2)；Request(S1)… P3：…Release(S3)；Request(S2)… 如改成： P1：…Request(S3)；Release(S1)… P2：…Request(S1)；Release(S2)… P3：…Request(S2)；Release(S3)… 可能发生死锁。 进程推进顺序不当引起死锁 进程推进顺序合法 不会引起进程死锁的推进顺序是合法的。 进程推进顺序非法 引起死锁。 申请r1 申请r2 释放r2 释放r1 申请r1 申请r2 释放r1 释放r2 两进程均占用r1 两进程均占用r2 x y P2进展 P1进展 0 A 死锁点 路线1 路线2 t t t2 t1 申请r1 申请r2 释放r2 释放r1 申请r1 申请r2 释放r1 释放r2 两进程均占用r1 两进程均占用r2 x y P2进展 P1进展 0 死锁点 路线1 路线2 问题：那么为什么没有斜线的推进的进程顺序呢？ t t 3、产生死锁的必要条件 死锁的发生有以下四个必要条件： 互斥条件：指进程对所分配到的资源进行排它性使用。 请求和保持条件：进程申请资源而阻塞时，不释放已占用资源。 不剥夺条件：进程已占用的资源未使用完前不可剥夺，只能由进程资源释放。 环路等待条件：死锁时进程间形成一个等待资源的循环链。 4、处理死锁的基本方法 预防死锁：破坏四个必要条件。 避免死锁：不破坏条件，系统允许进程动态申请资源。在分配资源之前，先计算资源分配的安全性。若将导致不安全状态，则不分配，该进程等待。 检测死锁：检查系统是否死锁，以及哪些进程和资源涉及死锁。 解除死锁：撤消死锁进程或剥夺资源以摆脱死锁. 四、死锁的预防 预防死锁 系统安全状态 利用银行家算法避免死锁 1、预防死锁 预防死锁的方法是使四个必要条件之一不能成立，来避免发生死锁。 互斥条件 请求和保持条件 不剥夺条件 环路等待条件 1、预防死锁 互斥条件：不能破坏。 摒弃“请求和保持”条件：系统规定所有进程开始运行之前，都必须一次性地申请其在整个运行过程中所需的全部资源。 再分配资源时，只要有一种资源不能满足某进程的要求，即使其它所需的各资源都空闲，也不分配给该进程，而让进程等待。 缺点：资源严重浪费。 1、预防死锁 摒弃“不剥夺”条件：进程申请新资源不能满足而阻塞时: 释放所有已占用的资源 逐个资源地被剥夺并分配给其它需要该资源的进程。本进程需要时再重新申请。 缺点：资源被迫释放可能会造成前段工作的失效。 1、预防死锁 摒弃“环路等待”条件：系统给每个资源一个编号，各进程对资源的申请必须严格按编号递增顺序进行。释放资源时按编号递减顺序进行。 2、系统安全状态 安全状态：存在一个由所有进程构成的安全序列。如果系统按照这个顺序为每个进程分配所需资源，直至最大需求，可以使每个进程都运行完。不会产生死锁。 不安全状态：系统中不存在