第3讲死锁.ppt

第3讲 死锁 为什么会产生死锁？ 如何解决？ 17 什么是死锁 在两个或多个并发进程中，如果每个进程持有某种 资源而又都等待着别的进程释放它或它们现在保持 着的资源，否则就不能向前推进。这组进程互相等待对方释放资源，都不能向前推进，称这一组进程产生了死锁。 资源分配与调度——死锁 为什么会发生死锁？ 系统资源不足 进程推进顺序非法 解决办法 预防死锁 破坏四个必要条件 避免死锁 检测状态是否安全 检测并解除死锁 19 资源分配与调度——死锁 互斥条件 涉及的资源是非共享的，即为临界资源。 不剥夺条件 进程所获得的资源在未使用完毕之前，不能被其 他进程强行夺走。 产生死锁的必要条件 20 资源分配与调度——死锁 部分分配 进程每次申请它所需要的一部分资源。在等待一新 资源的同时，进程继续占用已分配到的资源。 环路条件 存在一种进程的循环链，链中的每一个进程已获得 的资源同时被链中下一个进程所请求。 进程资源图 P1 P2 F 申请不同类型的资源 T 简单的死锁例子 F T P2 P1 请 求 已 分 配 请 求 配 分 已 预防死锁 破坏部分分配必要条件（3个） 资源全部分配 在作业调度时为选中的作业分配它所需要的所有资源，当资源一旦分配给该作业后，在其整个运行期间这些资源为它独占。 破坏不剥夺必要条件 剥夺 破坏环路必要条件 资源的有序分配 系统中所有资源都给定一个唯一的编号，所有分配请求必须以上升的次序进行。当遵守上升次序的规则时，若资源可用，则予以分配；否则，请求者等待。 避免死锁 在分配资源之前检测系统状态是否安全，安全就分配，不安全就不分配。 安全状态 所谓安全状态，是指系统能按某种进程顺序(P1，P2，…，Pn)(称〈P1，P2，…，Pn〉序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。 银行家算法 允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，令进程等待。 21 资源分配与调度——死锁 银行家算法相关数据结构 初始状态描述 假定一个系统包括n个进程和m类资源，表示如下 ① 一组确定的进程集合，记作： p={p1，p2，…，pi，…，pn} ② 一组不同类型的资源集合，记作： r={r1，r2，…，rj，…，rm} ③ 矢量w说明各类可利用资源的总的数目 w={w1，w2，…，wj，…，wm} 22 资源分配与调度——死锁 某时刻的资源请求矩阵 在时刻 t 资源请求矩阵，表示如下 d(t) = dij 表示进程pi还需要j类资源的数目 23 资源分配与调度——死锁 某时刻的资源分配矩阵 在时刻 t 资源分配矩阵，表示如下 a(t) = aij 表示进程pi已占有j类资源的数目 什么情况下系统安全的？ 　安全状态之例 　　我们通过一个例子来说明安全性。假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示： 这个状态是否安全？ T0时刻的资源分配表 安全吗？ 图3-16 T0时刻的资源分配表 解决办法 预防死锁 破坏四个必要条件 避免死锁 检测状态是否安全 检测并解除死锁 死锁检测 检测算法如下: （进程资源图的化简） (1) 把未阻塞(Ci=0)的进程Pi记录在L表中(其全部资源请求已得到满足的进程)； (2) 从L表中选择一进程，根据资源分配表S释放分配给该进程的所有资源； (3) 由进程等待表W依次检查和修改需要该进程释放资源的每一个进程的等待计数器Cj； (4) 若Cj=0，则表示该进程所请求的资源已得到满足，不再阻塞，将Pj记入L表中； (5)再从L表中选取另一进程，重复上述操作； (6) 若所有的进程都记入L表中，则系统初始状态为非死锁状态，否则为死锁状态。 解除死锁 撤销死锁中的进程，释放出资源。 撤销进程的代价 进程优先级 进程运行代价（已运行的%） 进程类型 等等 对于安全要求的操作系统要解决死锁 * * * * * * 假定系统有n个进程P1，P2，…，Pn和m种类型资源R1，R2，…，Rm建立资源分配表S和进程等待表W，分别如表3-1和表3-2所示，其中aij表示分配给进程Pi