操作系统 第3章.ppt

第三章处理机调度与死锁 操作系统 本章重点 3 1处理机调度的基本概念 1 3 2调度算法 2 3 3产生死锁的原因和必要条件 3 4 3 4预防死锁的方法 3 5死锁的检测与解除 5 3 1处理机调度的基本概念 在多道程序系统中 用户进程数往往超过处理机数 另外 操作系统还要建立若干个系统进程完成系统功能 多进程竞争处理机 将处理机动态地分配给系统中的各个就绪进程 使之执行 进程调度程序完成分配处理机的任务 系统运行性能在很大程度上取决于调度 吞吐量大小 周转时间长短 响应及时性 3 1处理机调度的基本概念 一个作业从提交到执行 通常都要经过多级调度 如作业调度 进程调度和交换调度等 一 高级 中级和低级调度作业调度 又称宏观调度或高级调度 把外存上处于后备队列中的作业调入内存 并为之创建进程 分配必要的资源 然后再将新创建的进程排在就绪队列上 准备执行 用于批处理系统 在分时和实时系统 通常无须作业调度 3 1处理机调度的基本概念 进程调度 又成微观调度或低级调度 按照某种策略和方法选取一个处于就绪状态的进程 将处理机分配给它 运行频率很高 一般几十毫秒要运行一次 交换调度 又称中级调度 按照某种策略 将处于外存交换区中的重又具备运行条件的就绪进程调入内存 或将处于内存就绪状态或内存阻塞状态的进程交换到外存交换区 它主要涉及内存管理与扩充 3 1处理机调度的基本概念 高级调度 作业调度 长程调度 接纳调度 接纳多少个作业接纳哪些作业低级调度 进程调度 短程调度 非抢占方式抢占方式 时间片 优先权 短作业优先 中级调度 中程调度 3 1处理机调度的基本概念 进程调度的方式和调度时机1 进程调度方式 1 非剥夺方式 Nonpreemptivemode 一旦把CPU分配给某一进程后 便让它一直运行下去 直到进程完成或发生某事件而不能运行时 才将CPU分给其它进程 该方式通常用在批处理系统中 主要优点是简单 系统开销小 3 1处理机调度的基本概念 2 剥夺方式 Preemptivemode 允许调度程序基于某种策略 优先级策略 时间片策略等 剥夺现行进程的CPU给其它进程 该方式通常用在分时系统和实时系统中 以便及时响应各进程的请求 3 1处理机调度的基本概念 2 进程调度的时机进程调度的时机 是指什么情况下引起进程调度程序工作 1 现行进程完成或错误终止 2 现行进程提出I O请求 等待I O完成时 转进程调度 3 在分时系统 按照时间片轮转 分给进程的时间片用完时 4 优先级调度时 有更高优先级进程变为就绪时 5 在进程通讯中 执行中的进程执行了某种原语操作 如P操作 阻塞原语和唤醒原语时 都可能引起进程调度 3 1处理机调度的基本概念 调度队列模型 仅有进程调度的调度队列模型 列 对 绪 就 列 对 塞 阻 CPU 等待事件 进程调度 进程完成 时间片完 交互用户 事件出现 3 1处理机调度的基本概念 具有高级和低级调度的调度队列模型 列 队 绪 就 1 列 队 塞 阻 CPU 等待事件 1 进程调度 进程完成 时间片完 作业调度 事件出现 列 队 备 后 2 列 队 塞 阻 N 列 队 塞 阻 等待事件 2 等待事件 N 事件出现 事件出现 3 1处理机调度的基本概念 同时具有三级调度的调度队列模型 列 对 绪 就 对 起 挂 绪 就 CPU 进程调度 进程完成 时间片完 事件出现 列 对 备 后 列 阻 队 起 挂 塞 列 列 对 塞 阻 等待事件 作业调度 交互型作业 挂起 事件出现 中级调度 3 1处理机调度的基本概念 选择调度方式和算法的若干准则 面向用户的准则周转时间短 平均周转时间 带权周转时间 响应时间快截止时间的保证优先权准则面向系统的准则系统吞吐量高处理机利用率好各类资源的平衡利用 3 2调度算法 所采用的进程调度算法是与整个系统的设计目标相一致的 在批处理系统中 系统的设计目标是增加系统吞吐量和提高系统资源的利用率 分时系统则保证每个分时用户能容忍的响应时间 因此 调度通常采用如下一些算法 3 2调度算法 FCFS调度算法 FCFS算法比较有利于长作业 而不利于短作业FCFS调度算法有利于CPU繁忙型的作业 而不利于I O繁忙型的作业 3 2调度算法 短作业 进程 优先调度算法 短作业 SJF 短进程 SPF 调度算法 3 2调度算法 SJ P F 优 有效降低作业的平均等待时间和提高系统的吞吐量缺 对长作业非常不利未考虑作业的紧迫程度使用估计执行时间 不能真正做到短作业优先调度 3 2调度算法 高优先权优先调度算法 一 优先权调度算法的类型非抢占式优先权算法抢占式优先权算法 3 2调度算法 二 优先权的类型当发生进程调度时 将CPU分配给就绪队列中优先级最高的进程 静态优先级 在进程创建时确定的 运行时保持不变 通常赋予系统进程较高优先级 申请资源量少的赋予较高优先级 优点是简单 动态优先级 原优先级可随进程的推进而改变 以便获得更好的调度性能 通常根据进程占用CPU时间的长短或等待CPU时间的长短动态调整 3 2调度算法 三 高响应比优先调度算法 RP 优先权 等待时间 要求服务时间 要求服务时间 响应时间 要求服务时间如等待时间 要求服务时间 则优先权 因而该算法有利于短作业当要求服务时间 优先权取决于等待时间 因而实现了FCFS对长作业 当等待时间 优先权 从而也可获得处理机 3 2调度算法 基于时间片的轮转调度算法 时间片轮转法通常用在分时系统 它轮流地调度系统中所有就绪进程 实现 利用一个定时时钟 使之定时地发出中断 时钟中断处理程序在设置新的时钟常量后 即转入进程调度程序 选择一个新的进程占用CPU 时间片长短的确定原则 既要保证系统各个用户进程及时地得到响应 又不要由于时间片太短而增加调度的开销 降低系统的效率 3 2调度算法 多级反馈队列调度算法 调度算法设置多个就绪队列 并为各个队列赋予不同的优先权 其次赋予各个队列中进程执行时间片的大小也各不相同 优先权 时间片 有新进程进入 先放入第一队队尾 按FCFS调度 运行一次后放入第二队队尾 再按FCFS调度 依此递减 仅当第一队空时才调度第二队 如正在运行第i队的进程 有高优先级进程进入 则抢占CPU 被抢占者放回第i队队尾 3 2调度算法 就绪进程的种类 刚刚被创建的进程等待进程调度 已经被调度执行过 但还没有执行完 等待下一次调度 正在执行的进程还未用完时间片 因请求I O 等待I O完成被迫放弃CPU 当等待原因解除后 进入就绪队列等待运行 系统通常设置多个就绪队列 且进程在其生命期内可能在多队列中存在 3 2调度算法 多级反馈队列调度算法 就绪队列 1 就绪队列 n 就绪队列 3 就绪队列 2 S 1 S 2 S 3 C P U 时间片 S 1 S 2 S 3 3 2调度算法 各个队列赋予不同的优先权 第一个队列的优先权最高 其余队列的优先权逐个降低 各个队列中进程执行时间片的大小也不相同 刚创建的进程和因请求I O未用完时间片的进程排在最高优先级队列 在这个队列中运行2 3个时间片未完成的进程排到下一个较低优先级队列 调度时 总是先调度优先级高的队列 仅当该队列空时 才调度次高优先级队列 以此类推 第n个队列进程被调度时 必须是前n 1个队列为空 既能使分时用户作业得到满意的响应时间 又能使批处理用户的作业获得较合理的周转时间 3 2调度算法 多级反馈队列调度算法的性能 终端型作业用户一般在一个时间片内完成短批处理作业用户一般在第二 第三队列执行完成长批处理作业用户用户不必担心其作业长期得不到处理 3 2调度算法 前后台法用在批处理和分时相结合的系统中 将分时用户作业放在前台 把批处理作业放在后台 系统对前台作业按照时间片轮转法进行调度 仅当前台无作业时 才把处理机分配给后台作业的进程 后台进程通常按先来先服务方式运行 这样既能使分时用户进程得到及时响应 又提高了系统资源的利用率 例 有5个进程P1 P2 P3 P4 P5 他们依次进入就绪队列 时间差距忽略不计 他们的优先数 优先数值小的优先级高 和需要的处理器时间如下表所示 忽略进行调度等待所花费的时间 请回答下列问题 1 写出分别采用先来先服务和非抢占式的优先数调度算法选中进程执行的次序 2 分别计算两种算法使各进程在就绪队列中的等待时间以及平均等待时间 3 3产生死锁的原因和必要条件 在多道程序系统中 并发进程改善了系统资源利用率和提高系统的吞吐量 但可能死锁 例 一个计算机系统 它有4台磁带机和2个并发执行的进程 某一时刻 每一进程都已占有2台磁带机 还要再请求一台磁带机才能完成它们的任务 这时 由于系统再无空闲的磁带机 两个进程就处于永远的等待状态 我们就说系统产生了死锁 3 3产生死锁的原因和必要条件 一 资源的特性硬件资源 如打印机 磁带机 主存等 软件资源 如共享变量 数据库中的加锁记录 可剥夺资源 是这样一类资源 当资源从占用进程剥夺走时 对进程不产生什么破坏性的影响 如主存 CPU 不可剥夺资源 一旦分配 不能强收回 只能由其自动释放 如打印机 磁带机 通常情况下 死锁涉及的是不可剥夺资源 3 3产生死锁的原因和必要条件 必须按下述三个顺序事件使用资源 1 请求资源 若请求不能立即满足 则申请者等待 2 使用资源 获得资源后 可使用它 3 释放资源 使用完毕 将资源归还系统 二 死锁的定义死锁 是指多个进程因竞争资源而造成的一种僵局 若无外力作用 这些进程都将永远不能向前推进 3 3产生死锁的原因和必要条件 图中圆圈代表进程 方块代表资源 资源已经分配给进程用从资源 方块 到进程 圆圈 的有向弧表示 进程请求该资源用从进程到资源的有向弧表示 下图给出进程对资源的可能情况 3 3产生死锁的原因和必要条件 T D U C 资源分配图 a 分配了一个资源 b 进程B请求一个资源 c 进程D和进程C已处于死锁状态 R S A B 3 3产生死锁的原因和必要条件 三 产生死锁的原因1 竞争资源引起进程死锁2 进程推进顺序不当引起死锁进程的资源轨迹避免死锁的主要方法是以系统的安全状态为基础的 先引入一个容易理解的图讨论安全的概念 3 3产生死锁的原因和必要条件 3 3产生死锁的原因和必要条件 1 Q获得B 然后获得A 然后释放B和A 当P恢复执行时 它可以获得全部资源 2 Q获得B 然后获得A P执行并阻塞在对A的请求上 Q释放B和A 当P恢复执行时 它可以获得全部资源 3 Q获得B 然后P获得A 由于在继续执行时 Q阻塞在A上而P阻塞在B上 死锁是不可避免的 4 P获得A 然后Q获得B 由于在继续执行时 Q阻塞在A上而P阻塞在B上 死锁是不可避免的 5 P获得A 然后获得B Q执行并阻塞在对B的请求上 P释放A和B 当Q恢复执行时 它可以获得全部资源 6 P获得A 然后获得B 然后释放A和B 当Q获得执行时 它可以获得全部资源 3 3产生死锁的原因和必要条件 四 死锁产生的必要条件 1 互斥条件 指进程对所分配到的资源进行排它性使用 每个资源是不可共享的 它或者已经分配给一个进程 或者空闲 2 保持请求和保持条件 进程已保持了至少一个资源 但又请求新资源 无时 阻塞等待 但又对已经分配给它的资源保持不放 3 不剥夺条件 资源已获得 未用完不被剥夺 用完时自己释放 4 环路等待条件 存在一个进程循环链 链中有二个或多个进程 每一个进程正在等待链中的下一个成员保持的资源 五 处理死锁的方法预防死锁 通过设置某些限制条件 去破坏产生死锁的四个必要条件中的一个或几个条件 来防止发生死锁 避免死锁 是在资源的动态分配过程中 用某种方法去防止系统进入不安全状态 从而避免发生死锁 检测死锁 允许死锁发生 通过设置检测机构 及时检测出死锁的发生 解除死锁检测出死锁的发生 然后采取适当措施解除死锁 3 3产生死锁的原因和必要条件 不太可能避免死锁 因为有些进程无法事先提供最大资源需求量 因产生死锁须四个必要条件 若能破坏其中的一个或几个条件 则死锁不发生 一 预防死锁 1 破坏互斥条件资源的互斥使用条件是由资源本身的性质决定的 因此不能破坏 但如果采用spooling技术 就可以将一台独享设备改造成多台设备 满足多个进程的需求 可预防死锁 实际中 不是所有设备都能采用spooling技术的 即使采用spooling技术 由于多个进程竞争磁盘空间 磁盘空间的不足 仍可能导致死锁 3 4预防死锁的方法 2 破坏保持和请求条件让进程在开始运行前 必须获得其所需的全部资源 若系统不能满足 则该进程等待 然而 许多进程在开始运行之前 不能精确提出所用资源数量 如果它能提出 那么就可以采用银行家算法避免死锁了 3 破坏非剥夺条件当一个进程已占有某些资源 又申请新的资源而不能立即得到满足时 则在进入阻塞状态前强行使其释放已经占有的资源 以后运行时 再重新申请 这个办法显然也不行 因为保护进程放弃资源时的现场以及之后的恢复现场 系统要付出很高的代价 3 4预防死锁的方法 4 破坏环路等待条件将系统全部资源按类进行全局编号排序 进程对资源的请求必须按照资源的序号 递增或递减顺序 申请 这样 在资源分配图中就不会出现环路 使进程一直运行 而不出现死锁 例 系统拥有资源为 输入机 1 打印机 2 绘图机 3 磁带机 4 光盘 5 系统有两个进程A和B 所有进程对资源的请求必须严格按序号递增顺序进行 如果A请求到资源j B请求到资源i 若i j 允许A请求B占有的资源i 但绝不允许B请求A占有的资源j 故进程资源图绝不会形成环路 但找到能满足所有进程要求的资源编号不可能 到目前为止 还没有一个有效办法来预防死锁 3 4预防死锁的方法 3 4预防死锁的方法 二 系统的安全状态死锁的避免基本思想 允许进程动态地申请资源 一次申请一部分资源 系统在进行资源分配之前 先计算资源分配的安全性 若此次分配不会导致系统进入不安全状态 便将资源分配给进程 否则 进程等待 安全状态 是指系统能按某种顺序 如p1 p2 pn 安全序列 来为每个进程分配其所需资源 直至最大需求 使每个进程都可顺序完成 若没有这样的安全序列 则称系统处于不安全状态 安全状态向不安全状态的转移 三 利用银行家算法 Banker sAlgorithm 避免死锁最具代表性的避免死锁的算法是Dijkstra的银行家算法 是在1965年提出的 这是由于该算法能用于银行系统现金贷款的发放而得名 这个算法正是利用了前面介绍的避免进程进入不安全区的原理 3 4预防死锁的方法 例 银行家算法是用来模拟一个小城镇的银行家为一批顾客贷款的问题 有四个顾客 A B C D 每个顾客提出的最大贷款数量分别为6 5 4 7 以千美元为单位 银行家知道不是所有顾客都马上需要其全部贷款 22 因此 他只保留10个单位数量 而不是全部22个单位 为这些顾客服务 在这个模型中 顾客是进程 资源单位是磁带驱动 而银行家就是操作系统 如图3 3所示 3 4预防死锁的方法 3 4预防死锁的方法 系统拥有量 10 a 初始状态 当前剩余量 2 b 安全状态 当B请求1个时 当前剩余量 1 c 不安全状态 图3 3资源的三种分配状态 C得到全部贷款后 很快将其全部贷款还清 银行家算法 Available 可用资源向量 一个含有m个元素的数组 每个元素代表一类资源可用的数目 Max 最大需求矩阵 n m矩阵 Max i j k表示进程i需要j类资源最大数目为k Allocation 分配矩阵 n m矩阵 Allocation i j k表示进程i当前已分得j类资源数目为k Need 需求矩阵 n m矩阵 Need i j k表示进程i还需要j类资源k个 3 4预防死锁的方法 设Requesti是进程Pi的请求向量 若Requesti j k 表示进程Pi需要k个j类资源 当Pi发出资源请求后 系统按下述步骤进行检查 若Requesti Needi 则转 否则 认为出错 因为它所需要的资源数已超过它所宣布的最大值 若Requesti Available 则转 否则 表示系统中尚无足够的资源 Pi必须等待 3 4预防死锁的方法 系统试探把要求的资源分配给进程Pi 并修改下面数据结构中的数值 Available Available RequestiAllocationi Allocationi RequestiNeedi Needi Requesti 系统执行安全性算法 检测此次资源分配后 系统是否处于安全状态 若安全 才正式将资源分给进程Pi 否则 将试探分配作废 恢复资源状态 让Pi等待 3 4预防死锁的方法 3 4预防死锁的方法 安全性算法 1 设置两个向量Work Finish 2 从进程集合中找到一个能满足下述条件的进程 Finish i false Needi Work 如找到 转步骤3 否则转步骤43 Pi获得资源后可顺利执行 直到完成 并释放资源 Work Work Allocationi Finish i true gotostep24 如所有进程的Finish i true 则系统处于安全状态 否则 不安全 系统中有五个进程 P0 P1 P2 P3 P4 和三种类型的资源 A B C 资源的数量分别为10 5 7T0时刻的安全性P1请求资源 1 0 2 P4请求资源 3 3 0 P0请求资源 0 2 0 进行安全性检查 3 4预防死锁的方法 例 某系统中仅有5个并发进程竞争某类资源 并都需要该类资源4个 那么至少有该类资源 个 这个系统就不会发生死锁 A 15B 16C 17D 18 解 每个进程最多申请使用5个资源 所以最坏的情况是每个进程都得到了3个资源 并且现在都申请所需要最后一个资源 所以系统所需要的资源数等于5 4 1 1 16 例 当前某系统有某同类互斥资源10个 进程P Q R所需资源总数分别是Request P Q R 8 4 9 它们向系统申请资源的次序和数量如表所示 1 系统采用银行家算法分配资源 请写出系统完成第6次分配后各进程的状态及进程所占资源数量 2 在没完成的各次申请中 哪次的申请要求可以先得到满足 一 死锁的检测和解除技术 是指定期启动一个软件检测系统的状态 若发现有死锁存在 则采取措施恢复之 3 5死锁的检测和解除 死锁的检测资源分配图死锁定理S为死锁状态的充分条件是 当且仅当S状态的资源分配图是不可完全简化的 3 5死锁的检测和解除 死锁检测中的数据结构 可利用资源向量Available把不占用资源的进程并入表L中 即Li L从进程集合中找到一个Requesti Work的进程做如下处理将其资源分配图简化 释放出资源 增加工作向量Work Work Allocation 将它并入L表中若不能将所有进程都并入L表中 则表明系统状态S的资源分配图是不可完全简化的 3 5死锁的检测和解除 死锁检测算法 Work Available L Li Allocationi 0 Requesti 0 forallnot Li L dobeginforallRequesti WorkdobeginWork Work Allocation Li L endenddeadlock NOT L P1 P2 Pn 死锁的另外一个检测方法 方法 由软件检查系统中由进程和资源构成的有向图是否构成一个或多个环路 若是 则存在死锁 否则不存在 3 5死锁的检测和解除 3 5死锁的检测和解除 例 假定一个系统有七个进程 A G 六个资源 R W 资源的使用情况如下 进程A保持资源R 请求资源S 进程B没有保持资源 请求资源T 进程C也没有保持资源 请求S资源 进程D保持资源U 请求S和T资源 进程E保持T 请求V资源 进程F保持W 请求S资源 进程G保持V 请求U资源 进程资源图如图3 4 3 5死锁的检测和解除 一个简单的死锁检测算法需要一个数据结构L 用来记录系统中各节点的情况 执行过程中 标记已检测过的弧 类似于有向图的遍历 对于图中的每个节点N 以N为起始节点 执行以下5步 将L初始化为空表 以表示所有弧都未标记过 将当前节点加到L的末端 检查这个节点在表中是否出现过 如果是 这个图包含一个环路 算法终止 如果没有 转 3 5死锁的检测和解除 由这个节点再看 是否有未标记的引出弧 如果有 转 若