处理机调度与死锁续ppt课件.ppt

第四章 续 死锁 死锁的基本概念死锁的解决方案 预防 避免 检测及解除 资源分配图 死锁的现象 一 死锁的基本概念 1 死锁的定义一组进程中 每个进程都无限等待被该组进程中另一进程所占有的资源 因而永远无法得到的资源 这种现象称为进程死锁 这一组进程就称为死锁进程 死锁 Deadlock 饥饿 Starvation 参与死锁的进程最少是两个 两个以上进程才会出现死锁 参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集注 如果死锁发生 会浪费大量系统资源 甚至导致系统崩溃 关于死锁的一些结论 2 产生死锁的原因 1 争夺资源引起死锁例1 P1 P2两个进程争夺打印机和读卡机 P1 P2 打印机 P1已经申请到打印机 又申请读卡机 P2已经申请到读卡机 又申请打印机 打印机和读卡机为非剥夺性资源 读卡机 例2 P1 P2 P3三个进程之间通信 P1产生消息S1 接收P3产生的消息S3 P2产生消息S2 接收P1产生的消息S1 P3产生消息S3 接收P2产生的消息S2 按以下次序运行 P1 Request S3 Release S1 P2 Request S1 Release S2 P3 Request S2 Release S3 2 进程推动顺序不当引起的死锁 P1 P3 S2 S3 S1 P1 P2 P3 按照以上的顺序执行会产生死锁吗 Si临时性资源 获得A 获得B 获得A 获得B 释放A 释放B 释放B 释放A P请求A P请求B Q请求A Q请求B 死锁区 P Q都申请A P Q都申请B 资源 永久性资源 可以被多个进程多次使用 可再用资源 可抢占资源不可抢占资源临时性资源 只可使用一次的资源 如信号量 中断信号 同步信号等 可消耗性资源 申请 分配 使用 释放 模式 3 产生死锁的四个必要条件 互斥使用 资源独占 不可强占 不可剥夺 请求和保持 部分分配 占有申请 循环等待 1 互斥使用 资源独占 一个资源每次只能给一个进程使用2 不可强占 不可剥夺 资源申请者不能强行的从资源占有者手中夺取资源 资源只能由占有者自愿释放 3 请求和保持 部分分配 占有申请 一个进程在申请新的资源的同时保持对原有资源的占有 只有这样才是动态申请 动态分配 4 循环等待存在一个进程等待队列 P1 P2 Pn 其中P1等待P2占有的资源 P2等待P3占有的资源 Pn等待P1占有的资源 形成一个进程等待环路 二 死锁的解决方案 1 产生死锁的例子申请不同类型资源产生死锁 P1 申请打印机申请扫描仪使用释放打印机释放扫描仪 P2 申请扫描仪申请打印机使用释放打印机释放扫描仪 申请同类资源产生死锁 如内存 设有资源R R有m个分配单位 由n个进程P1 P2 Pn n m 共享 假设每个进程对R的申请和释放符合下列原则 一次只能申请一个单位 满足总申请后才能使用 使用完后一次性释放 m 2 n 3资源分配不当导致死锁产生 2 解决死锁的方法 鸵鸟策略不理睬死锁 从工程角度考虑死锁概率及解决的代价预防策略破坏死锁的四个必要条件之一避免策略采用某种算法判断资源申请是否满足 以动态地回避死锁检测和解除检测出发生的死锁并采取措施予以解除 3 死锁预防 定义 在系统设计时确定资源分配算法 保证不发生死锁具体的做法是破坏产生死锁的四个必要条件之一 死锁预防 破坏 不可剥夺 条件在允许进程动态申请资源前提下规定 一个进程在申请新的资源不能立即得到满足而变为等待状态之前 必须释放已占有的全部资源 若需要再重新申请 破坏 请求和保持 条件要求每个进程在运行前必须一次性申请它所要求的所有资源 且仅当该进程所要资源均可满足时才给予一次性分配 死锁预防 破坏 循环等待 条件采用资源有序分配法 把系统中所有资源编号 进程在申请资源时必须严格按资源编号的递增次序进行 否则操作系统不予分配 死锁预防 如何证明按资源有序分配法进行分配肯定不会产生死锁 i j表示 资源Ri先于资源Rj假设进程A和B处于死锁状态 因为A已经拥有了Ri并申请Rj 同时B已经拥有了Rj并申请Ri 即 PA Ri Rj即有i jPB Rj Ri即有j i 破坏 循环等待 条件 回顾 进程调度调度算法死锁预防破环必要条件 4 死锁避免 允许死锁前三个条件的成立 但作一定的判断选择以确保永远不会达到死锁点采用某种算法动态判断当前资源分配请求是否有可能导致死锁 如可能导致死锁 则拒绝本次资源申请要求或是中止该进程的运行 死锁避免定义 定义 在系统运行过程中 对进程发出的每一个系统能够满足的资源申请进行动态检查 并根据检查结果决定是否分配资源 若分配后系统可能发生死锁 则不予分配 否则予以分配死锁避免和死锁预防的区别 安全状态与不安全状态 安全状态 如果存在一个由系统中所有进程构成的安全序列P1 Pn 则系统处于安全状态 死锁避免 安全序列 一个进程序列 P1 Pn 是安全的 如果对于每一个进程Pi 1 i n 它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj j i 当前占有资源量之和 系统处于安全状态 安全状态一定是没有死锁发生的 安全状态与不安全状态 不安全状态 不存在一个安全序列 不安全状态可能导致死锁 目前占有量 最大需求量 尚需要量 P1 5 10 5 P2 2 4 2 P3 2 9 7 系统剩余量 3 共有12台磁带机T0时刻分配情况如下 T0时刻是否安全 如果此时P3又请求一台磁带机 又是否安全 银行家算法 n 系统中进程的总数m 资源类总数Available ARRAY 1 m ofinteger Max ARRAY 1 n 1 m ofinteger 银行家算法 Allocation ARRAY 1 n 1 m ofinteger Need ARRAY 1 n 1 m ofinteger Request ARRAY 1 n 1 m ofinteger 银行家算法 简记符号 AvailableMax i Allocation i Need i Request i 必须满足的关系 1 资源总数 可用资源数 已分配资源数Ri Available Allocation i 2 申请量不能超过需求量Request i Need i 3 已分配数不可能超过它所需的资源数Allocation i Max i 银行家算法 当进程pi提出资源申请时 系统执行下列步骤 1 若Request i Need i 转 2 否则错误返回 2 若Request i Available 转 3 否则进程等待 3 假设系统分配了资源 则有 Available Available Request i Allocation i Allocation i Request i Need i Need i Request i 若系统新状态是安全的 则分配完成若系统新状态是不安全的 则恢复原状态 进程等待 银行家算法 为进行安全性检查 定义数据结构 Work ARRAY 1 m ofinteger Finish ARRAY 1 n ofBoolean 银行家算法 安全性检查的步骤 1 Work Available Finish false 2 寻找满足条件的i a Finish i false b Need i Work 如果不存在 则转 4 银行家算法 3 Work Work Allocation i Finish i true 转 2 4 若对所有i Finish i true 则系统处于安全状态 否则处于不安全状态 假设系统中有5个进程和3类资源 各种资源的数量分别为10 5 7 在T0时刻的资源分配图如下 T0时刻的安全性 安全序列 若P1申请 1 0 2 能否分配 302 020 230 死锁避免策略 Deadlockavoidancestrategy 当一个进程请求一组资源时 假设请求得到准许 相应地改变系统状态 然后决定结果是否是安全状态 如果是的话 那么准许该请求 或者说给该进程分配相应的资源 否则 拒绝本次资源分配请求 即阻塞该进程直至准许该请求还能保证安全状态 即 通过银行家算法 确保进程和资源总是处于安全状态 死锁检测 允许死锁发生 操作系统不断监视系统进展情况 判断死锁是否发生一旦死锁发生则采取专门的措施 解除死锁并以最小的代价恢复操作系统运行 5 死锁的检测与解除 死锁的检测与解除 检测时机 当进程等待时检测死锁 其缺点是系统的开销大 定时检测系统资源利用率下降时检测死锁 死锁的解除 重要的是以最小的代价恢复系统的运行 有如下几种方法 1 重新启动2 撤消进程3 剥夺资源4 进程回退 三 资源分配图 用有向图描述进程的死锁准确 形象系统由若干类资源构成 一类资源称为一个资源类 每个资源类中包含若干个同种资源 称为资源实例 资源分配图 二元组G V E V 结点集 分为P R两部分P p1 p2 pn R r1 r2 rm E 边的集合 其元素为有序二元组 pi rj 或 rj pi 资源分配图 表示法资源类 资源的不同类型 用方框表示资源实例 存在于每个资源中 用方框中的黑圆点表示进程用圆圈中加进程名表示 资源分配图 分配边 资源实例 进程的一条有向边申请边 进程 资源类的一条有向边 有环有死锁 有环无死锁 资源分配图 死锁定理如果资源分配图中没有环路 则系统中没有死锁 如果图中存在环路则系统中可能存在死锁如果每个资源类中只包含一个资源实例 则环路是死锁存在的充分必要条件 资源分配图 资源分配图化简 1 找一个非孤立点进程结点且只有分配边 去掉分配边 将其变为孤立结点2 再把相应的资源分配给一个等待该资源的进程 即将某进程的申请边变为分配边 HowtoReduceaResourceAllocationGraph R1 R2 R3 P1 P3 P2 P4 HowtoReduceaResourceAllocationGraph R1 R2 R3 P1 P3 P2 P4 HowtoReduceaResourceAllocationGraph R1 R2 R3 P1 P3 P2 P4 死锁定理 引理 一个给定的进程 资源图的全部化简序列导致同一不可化简图 死锁定理 S是死锁状态 当且仅当S的进程 资源图不是可完全化简图 Summary 三级调度 Summary cont Summary cont 死锁 死锁 原因 资源 竞争 进程 推进 顺序 不当 死锁 必要 条件 环路 等待 条件 不剥 夺条 件 请求 和保 持条 件 互斥 条件 死锁 预防 死锁 避免 死锁 检测 死锁 解除 银行 家算 法 破坏 四个 必要 条件 中的 一个 化简 资源 分配 图 剥夺 资源 撤消 进程 死锁 处理 死锁 定理 Problem1 下列调度算法中 不是作业调度算法的有 A 轮转法B 优先数法C 先来先服务法D 多级反馈队列算法 思考与练习 某系统中有11台打印机 N个进程共享打印机资源 每个进程要求3台 当N的取值不超过时 系统不会发生死锁 Problem2 某个系统使用多级反馈队列法 总共设置了六级队列 假设第一级队列的时间片长度为2秒 以后每一级的时间片长度都是上一级长度的两倍 现在需要执行一个运行时间为31秒种的进程 则该进程的执行将被中断次 它在第级队列是完成运行 Problem3 设系统中仅有一个资源类 其中共有3个资源实例 使用此类资源的进程共有3个 每个进程至少请求一个资源 它们所需资源最大量的总和为X 则发生死锁的必要条件是 当X满足什么条件时 Problem4 现有如下作业序列作业1提交时间8 00 完成时间1 00 作业2提交时间8 30 完成时间3 00 作业3提交时间9 00 完成时间0 10 作业4提交时间9 30 完成时间0 50 试用FCFS和SJF调度算法处理 问哪种调度算法性能更好 Problem5 假定系统有进程集合P0 P1 P2 P3 P4 资源集合 A B C 资源数量为 10 8 7 某时刻系统状态如图 试给出进程的剩余请求矩阵并判断当前系统是否处于安全状态 Problem6 关于处理机调度 试问 1 什么是处理机三级调度 2 处理机三级调度分别在什么情况下发生 3 各级调度分别完成什么工作