12-死锁幻灯片.pptVIP

* 第三章 处理机调度 * 第三章 处理机调度 第三章 处理机调度与死锁 3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度 3.4 多处理机系统中的调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除 上节回顾 实时调度的基本条件 实时调度算法分类：四种实时调度模型：P83 最早截止时间优先算法 最低松弛度优先： 松弛度=完成截止时间-需要运行时间-当前时间 每个周期任务只执行一次 在松弛度为0的时刻设置“地雷” 松弛度为0发生抢占 死锁原因：竞争资源，执行顺序不当 实验二（一节课） 2. 进程推进顺序不当引起死锁 1) 进程推进顺序合法 2) 进程推进顺序非法 若并发进程P1和P2按曲线④所示的顺序推进，它们将进入不安全区D内。此时P1保持了资源R1, P2保持了资源R2, 系统处于不安全状态。因为，这时两进程再向前推进，便可能发生死锁。例如，当P1运行到P1:Request(R2)时，将因R2已被P2占用而阻塞；当P2运行到P2: Request(R1)时，也将因R1已被P1占用而阻塞，于是发生了进程死锁。 3.5.2 产生死锁的必要条件 3.5.3 处理死锁的基本方法 3.6 预防死锁的方法 3.6.1 预防死锁 在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程； 否则，令进程等待。 3.6.2 系统安全状态 1. 安全状态 所谓安全状态，是指系统能按某种进程顺序(P1, P2, …，Pn)(称〈P1, P2, …, Pn〉序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。 2. 安全状态之例 我们通过一个例子来说明安全性。假定系统中有三个进程P1、 P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示： 3 5 2 2 10 4 9 P1 P2 P3 可 用 已 分 配 最 大 需 求 进 程 3. 由安全状态向不安全状态的转换 T0时刻以后 例如P3请求1台磁带机，若分配，系统进入不安全状态。 因为无法再找到一个安全序列。 因为其余2台分配给P2，P2完成后只能释放出4台，既不能满足P1，也不能满足P3，致使它们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。