《进程死锁》PPT课件.ppt

第8章进程死锁 死锁的概念死锁产生的原因死锁的必要条件死锁预防死锁避免死锁检测与解除 死锁现象 引例 系统中有两个进程P1 P2 两份资源S1 S2 目前状况是 S1 P1 S2 P2 死锁现象 进程P1拥有资源S1 进程P2拥有资源S2 但他们都在不放弃已拥有资源的情况下 申请对方所占有的资源 出现 P1和P2相互等待对方资源的现象 死锁 系统中的一组进程 每一个进程都在等待另一个进程所占有的资源 使系统处于无限期的等待状态 死锁产生的原因 资源分配不合理进程推进速度不合理 著名的哲学家问题 哲学家问题 每个人必须同时拿到两根筷子才能吃到面条 如果每个人都拿到了一根筷子 就永远吃不到面条了 思考 哲学家之间是什么关系 如何用信号量和PV原语实现他们之间的制约关系 注意 死锁讨论的范畴 不属于讨论的范畴进程申请了不存在的资源申请资源最大数超过了系统拥有的最大数硬件故障或程序性错误引起的循环等待假定 任何一个进程要求资源的最大数不超过系统提供最大数量申请资源得到满足 一定在有限时间内完成只有在申请资源得不到满足时才处于等待状态 死锁存在的必要条件 资源的互斥使用资源的不可抢占占有并等待 资源的部分分配 资源的循环等待 S1 S2 P1 P2 资源分配图 用有向图来表示进程对资源的占有情况 顶点 进程 资源边 如果一个进程已经占有了一份资源 则画一条指向进程的边 如果一个进程申请一份资源 则画一条指向资源的边 如果同一份资源有多个 则用顶点中的圆点数表示 P1 P2 P3 r1 r2 r3 r4 资源分配图 用资源分配图判断死锁 如果没有环路 则一定没有死锁如果有环路 且环路中资源类只有一个资源 则有死锁 如果有环路 但环路中资源类有多个资源 则不一定有死锁 例题 假定某系统当时的资源分配图如下所示 1 分析当时系统是否存在死锁 2 若进程P3再申请R3时 系统将发生什么变化 说明原因 死锁的防止 原理 打破死锁存在的四个必要条件之一 互斥条件 不能人为打破 占有并等待 措施一 资源的静态分配 在进程运行前 将进程所需要的所有资源分配给进程 且在整个进程运行过程中 进程所占有资源不能被其他进程使用 释放已占资源 死锁的防止 不可抢夺允许抢占 资源尚未占用 进程处在等待状态只有处理器 主存资源可以抢占循环等待 资源的按序分配 将资源编号 紧缺资源的编号大 充裕资源的编号小 只有低编号的资源得到满足后 才能分配高编号资源 打破了资源的循环等待 按序分配的例 哲学家问题 将叉子编号 F1 F2 F3 F4 F5P1 P2 P3 L P F1 L P F2 L P F3 P F2 P F3 P F4 吃面吃面吃面V F1 V F2 V F3 V F2 V F3 V F4 GOTOLGOTOLGOTOL 按序分配的例 哲学家问题 P4 P5 L P F4 L P F1 P F5 P F5 吃面吃面V F4 V F1 V F5 V F5 GOTOLGOTOL 8 4死锁避免 资源的动态分配 允许根据用户需求分配资源 但每次分配之前都要检查系统是否安全 如果不安全 即使有资源 也不能分配给进程 安全的含义 如果系统中存在着一个进程序列 使所有的进程都能够运行结束 则称系统是安全的 否则是不安全的 如何判断系统是否安全 不安全 与死锁的区别 不安全 并不一定发生死锁死锁状态集是不安全状态集的子集 不安全状态 死锁状态 银行家算法 基本思想 一个用户对资金的最大需求量不超过银行家现有的资金用户可以分期贷款 但贷款总数不能超过最大需求量可以推迟支付 但总能在有限的时间内让用户得到贷款当用户得到所需全部资金后 一定能在有限的时间内归还 银行家算法 原理 当进程首次申请资源时 测试该进程对资源的最大需求量 如果系统现存的资源可以满足它的最大需求量 则按申请分配 否则推迟分配 执行过程中申请 先测试已占用的资源数与本次申请的资源数之和是否超过该进程对资源的最大需求量再测试系统现存的资源能否满足该进程尚需的最大资源量 银行家算法 数据结构 系统中总的资源进程运行所需的最大资源数已经分配的资源数P还需要申请的资源数R 银行家算法 过程 准备 计算系统中的剩余资源F 计算进程请求资源R 1 找到一个进程Pi 满足Ri Ri 则说明系统不安全 5 若所有进程都能够运行结束 则系统安全 例题 教材P240例1 银行家算法的应用实例 现有三个进程P1 P2 P3 共享A B C三类资源 进程对资源的需求量和目前分配情况如下表 进程已占有资源数最大需求数ABCABCP1263265P2201201P3210285若系统还有剩余资源分别为 A类2个 B类6个 C类2个 请回答下列问题 1 目前系统是否处于安全状态 2 如果进程P3提出申请 0 5 2 个资源 系统是否能为它分配资源 问题1 步骤一 计算 和 系统当前的空闲资源为 2 6 2 进程要运行结束 还需请求的资源 为 进程ABCP1002P2000P3075 步骤二 是否存在进程序列 由于P2不需要申请更多的资源 可以运行结束 释放它占有的资源 2 0 1 空闲资源变为 4 6 3 空闲资源满足P1的资源要求 P1运行结束 释放它占有的资源 2 6 3 空闲资源变为 6 12 6 空闲资源满足P3的资源请求 P3可以运行结束 系统中的进程能在有限时间内全部运行结束 2 1 3 所以系统是安全的 问题2 假设可以为进程P3分配它申请的资源 0 5 2 则系统当前状况是 空闲资源F为 2 1 0 进程要运行结束 还需请求的资源R为 进程ABCP1002P2000P3023 是否存在进程序列 进程P2运行 释放它所占有的资源 2 0 1 系统空闲资源变为 4 1 1 由于空闲资源不能满足系统中任一进程的资源请求 进程P1和P3陷入无限期等待 系统出现死锁 所以 系统不能为P2分配资源 银行家算法 基本公式 系统中资源数m个并发进程数 n个每个进程申请该类资源的最大数 x 1 x m 若满足 n x 1 1 m1m n时X 1 m 1 nm n时 8 5死锁检测 如果每次分配资源 都需要做一次银行家算法 系统效率会非常低 假设 系统中发生死锁的可能性很小 因此 没有必要每次都检查系统是否安全 只需定期检查以下系统是否存在死锁就可以了 当进程请求资源时 若系统中有资源 就分配给进程 如何检测系统是否死锁 死锁检测算法 原理 是否存在资源的循环等待 资源状态图 用有向图来表示进程对资源的占有情况 顶点 进程 资源边 如果一个进程已经占有了一份资源 则画一条指向进程的边 如果一个进程申请一份资源 则画一条指向资源的边 如果同一份资源有多个 则用顶点中的圆点数表示 P1 P2 P3 r1 r2 r3 r4 资源状态图 死锁判定法则 如果资源分配图中没有环路 则系统没有死锁 如果资源分配图中出现了环路 则系统可能存在死锁 如果处于环路中的每个资源类中均包含一个资源实例 则意味着死锁的存在 如果处于环路中的每个资源类中包含的资源实例个数不全为1 则环路的存在是必要条件 死锁的检测方法 每类资源中只有一个资源占用表 资源占用进程等待表 进程等待资源 见P242表8 8 判断是否有循环等待的进程等待占有关系与间接等待占有关系等待占有关系矩阵 见P243表8 9 当矩阵中有某个Bii i 1 2 n 1时 说明存在循环等待 死锁的检测方法 资源类中含有若干个资源按银行家算法检测 例题 1 进程资源的使用情况和可用情况如下表所示 四个进程和三类资源 1 请画出资源分配图 2 分析目前系统中是否会发生死锁 死锁解除 策略 重新启动系统 撤消所有进程 剥夺资源法逐一终止进程选择哪些进程剥夺资源或终止 最小代价原则 一个例子 甲 乙两个人 过一个独木桥 最小代价原则 甲 乙 1 甲 乙