《处理机调度》课件.ppt

第三章处理机调度 CPU调度 无论在多道批处理系统还是分时系统中 系统中的用户进程数都远远超过处理机数 除用户进程要占用处理机外 操作系统还要建立若干个系统进程完成系统功能 这么多的进程竞争处理机 就要求系统提供进程调度功能 以便采用一些策略 将处理机动态地分配给系统中的各个就绪进程 使之执行 分配处理机的任务是由处理机调度程序完成的 处理机是计算机最重要的资源 如何提高处理机的利用率及改善系统性能 在很大程度上取决于处理机调度性能的好坏 处理机调度成为操作系统设计中心工作 要解决的问题WHAT 按什么原则分配CPU 进程调度算法WHEN 何时分配CPU 进程调度的时机HOW 如何分配CPU CPU调度过程 进程的上下文切换 一批作业从进入系统到作业运行完毕可能经历三级调度 高级 低级和中级调度 一 高级调度 HighScheduling 又称为作业调度接纳调度或长程调度 用于批处理系统 确定将外存后备队列中哪些作业调入内存 并为它们创建进程 实时系统和分时系统的前台作业不需要作业调度 每次作业调度时 都必须做出两个决定 1 接纳多少个作业 取决于多道程序度 2 接纳哪些作业 用什么调度算法 先来先服务 短作业优先 优先权 响应比优先 3 1处理机调度的基本概念3 1 1高级 低级和中级调度 响应 运行 二 低级调度 进程调度 短程调度 进程调度的任务是控制协调进程对CPU的竞争 即按照一定的调度算法从就绪队列中选中一个进程 把CPU的使用权交给被选中的进程 它是最基本的一种调度 批处理系统 实时系统和分时系统都必须有进程调度 它通过进程调度程序来完成 1 进程调度程序的主要功能可描述如下 1 记录系统中各进程的状况为了很好地实现进程调度 进程调度程序首先必须管理系统中各进程的PCB 将进程的状态变化及资源需求情况及时地记录到PCB中 通过PCB变化来准确地掌握系统中所有进程的状态特征和执行情况 2 选择进程真正占有CPU这是进程调度的实质 即按照系统规定的调度策略从就绪队列中选择一个进程占有CPU执行 进程调度依据的算法与系统的设计目标相一致 对于不同的系统 通常采用不同的调度策略 对于批处理系统常采用短进程的进程优先 以减少各进程的周转时间 对于分时系统 更多地采用时间片轮转 3 进行进程上下文的切换当进程调度选中一个进程占有CPU时 进程调度程序要做的主要工作则是进行进程上下文切换 将正在执行进程的运行现场保留在该进程的PCB中 以便以后该进程恢复执行 将刚选中进程的运行现场恢复起来 并将CPU的控制权交给被选中进程 使其执行 2 进程调度方式 1 非抢占方式 Nonpreemptivemode 在非抢占方式下 调度程序一旦把CPU分配给某一进程后便让它一直运行下去 直到进程完成或发生某事件而不能运行时 才将CPU分给其它进程 这种调度方式通常用在批处理系统中 它的主要优点是简单 系统开销小 2 抢占方式 Preemptivemode 当一个进程正在执行时 系统可以基于某种策略剥夺CPU给其它进程 剥夺的原则有 优先权原则 短进程优先原则 时间片原则 显然这种调度方式多用在分时系统和实时系统中 以便及时响应各进程的请求 3 进程调度的时机所谓进程调度的时机 是指什么情况下引起进程调度程序工作 进程调度的时机是与进程调度的方式有关的 进程调度的时机如下 正在执行的进程正确完成 或由于某种错误而终止运行 陷阱或中断 执行中的进程提出I O请求 等待I O完成时 在分时系统中 按照时间片轮转 分给进程的时间片用完时 按照优先级调度时 有更高优先级进程变为就绪时 抢占方式 在进程通讯中 执行中的进程执行了某种原语操作 如wait操作 阻塞原语和唤醒原语时 都可能引起进程调度 三 中级调度 中程调度 中级调度使暂时停止的进程不再占用宝贵的内存资源 将它们调到外存上去成为挂起状态 当处于挂起就绪的进程重新具备运行条件且内存稍有空闲时 中级调度将它重新调入内存 挂在活动就绪队列上等待进程调度 中级调度实质上就是存储管理中的对换功能 进程调度频率最高 10 100ms 次 调度算法简单快速 作业调度频率最低约几分钟一次 调度算法允许花费较多的时间 中级调度介于两者之间 3 1 2 调度队列模型 1 仅有进程调度的调度队列模型在分时系统中 通常仅有进程调度 采用FIFO算法 CPU 就绪队列 阻塞队列 时间片完 进程调度 等待事件 事件出现 交互用户 完成 2 具有高级和低级调度的调度队列模型在批处理系统中 不仅需要进程调度而且需要作业调度 3 具有三级调度的调度队列模型在具有三级调度系统中 增加了在外存的挂起状态 对于不同的系统 有不同的设计目标 采用不同的调度算法 调度算法实质上是个策略问题面向用户的准则 周转时间短交互式系统的响应时间快截止时间保证优先权准则 公平合理 面向系统的准则 单位时间内运行尽可能多的进程 吞吐量高使处理机尽可能保持 忙碌 利用率高使内外存 I O设备得以均衡 充分利用 3 1 3 调度算法的评价准则 进程 作业 平均周转时间 周转时间 吞吐量 设某进程创建时间为Si 结束的时间为Ei它的周转时间 全过程所用时间 为Ti Ei Si系统为它提供的实际服务时间为Tsi则进程平均周转时间T 带权平均周转时间W为 T W 其中 n为被测定进程流中的进程数 要设计一个理想的调度算法是一件十分困难的事 在实际系统中 调度算法往往折衷考虑 大多数操作系统都采用比较简单的调度算法 3 2调度算法 1 先进先出调度算法 FIFO 先来先服务FCFS 作业调度按照进入后备队列的先后次序调度 进程调度按照进入进程就绪队列的先后次序来调度优点 实现简单缺点 不利于短作业 进程 紧迫性作业 进程 得不到及时处理2 短作业 进程 优先调度算法 SJF SPF 选择就绪队列中估计运行时间最短的进程投入运行优点 平均周转时间 带权平均周转时间都改善缺点 对长作业 进程 非常不利不能保证紧迫性作业 进程 得到及时处理估计运行时间不准确 3 优先权调度算法 HPF HighestPriorityFirst 优先选择就绪队列中优先权最高的进程投入运行非抢占式优先权算法 仅在事件发生放弃处理机时抢占式优先权算法 可将正在运行的运行权剥夺优先权的类型静态优先权 在进程创建时指定优先权 在进程运行时优先数不变动态优先权 在进程创建时创立一个优先权 但在其生命周期内优先数可以动态变化 如等待时间长优先数可改变确定优先权的依据进程类型 对资源的需求 根据用户要求 4 高响应比优先调度算法 改进短作业 进程 优先调度算法 优先权用下式动态计算出来优先权 上式可看出等待时间相同要求服务的时间越短优先权越高 有利于短作业要求服务时间相同 等待时间越长优先权越高 近似于先来先服务长作业的优先权会随等待时间加长而升高 长作业也会得到执行 把CPU划分成若干时间片 并且按顺序赋给就绪队列中的每一个进程 进程轮流占有CPU 当时间片用完时 即使进程未执行完毕 系统也剥夺该进程的CPU 将该进程排在就绪队列末尾 同时系统选择另一个进程运行分时系统中常用时间片轮转法时间片选择问题 固定时间片 可变时间片确定时间片大小的因素 系统响应时间 就绪进程个数 CPU能力 5 时间片轮转调度算法 6 多队列反馈调度算法 系统按优先级设置多级就绪队列第一级优先级最高各就绪队列分配不同的时间片 优先级高的第一级队列时间片最小 随着队列优先级的降低 时间片加大各个队列按照先进先出调度算法一个新进程就绪后进入第一级就绪队列进程由于等待事件而放弃CPU后 进入等待队列 一旦等待的事件发生 则回到原来的就绪队列当有一个优先级更高的进程就绪时 可以抢占CPU 被抢占进程回到原来一级就绪队列末尾当第一级队列空时 就去调度第二级队列 如此类推时间片用完后进程放弃CPU 进入下一级就绪队列 实时系统中 对实时进程的调度有截止时间的要求1 实现实时调度的基本条件1 提供必要的信息就绪时间 开始截止时间或完成截止时间 处理时间 资源要求 优先级 硬实时任务赋绝对优先级 2 系统处理速度快若系统中有m个周期性硬实时任务 处理时间为Ci周期时间为Pi 则处理机处理速度应达到可调度条件 1 单处理机 n 多处理机 3 采用抢占式调度机制以满足对截止时间的要求4 具有快速切换机制 快速中断响应 快速任务分派 3 3实时调度 2 实时调度算法的分类1 非抢占式调度算法非抢占式轮转调度算法 响应时间数秒到数十秒 轮转一圈后调度非抢占式优先权调度算法 响应时间数百毫秒 当前进程完成 或被阻塞 后调度2 抢占式调度算法严格要求的实时系统 响应时间在数十毫秒以内基于时钟中断的抢占式调度算法时钟中断到来时调度立即抢占的优先权调度算法立即剥夺当前进程调度时间见P83图3 6 3 几种常见的实时调度算法1 最早截止时间优先算法 EarliestDeadlineFirst 根据任务的开始截止时间确定优先级 2 最低松弛度优先算法 LeastLaxityFirst 根据任务的松弛度 紧急程度 确定优先级根据任务完成截止时间和本身运行时间确定松弛度松弛度 必须完成时间 本身运行时间 当前时间P85图3 9 保存现场 顺序保存进程的上下文 包括程序计数器和其它寄存器用新状态和相关信息更新正在运行进程的PCB把该进程移至合适的队列 就绪 阻塞选择另一个要执行的进程 更新该进程的PCB从被选中进程中重装入CPU上下文 恢复现场若无就绪进程 系统会安排一个闲逛进程 idle 一直运行 在执行过程中可接收中断 3 4CPU调度的实现 操作系统的核心向上提供无中断的虚拟机器 在核心内不允许中断特点 核心常驻内存 短小精焊 为进程运行提供舞台核心的组成中断处理 时钟 I O 虚拟存储器进程管理 调度控制通讯互斥同步等原语管理 提供一系列原语 同步 通信 创建 撤消等队列管理 中断之后调度之前 运行 就绪 等待队列 现场管理 保存现场 恢复现场时钟管理 绝对时钟 间隔时钟 虚时钟 保存现场 分析中断源处理中断原语管理 队列管理 时钟管理 进程调度恢复现场 中断 核心入口 核心处理流程唯一入口 中断 由硬件完成 作业 P1012 3 5 3 5死锁 死锁的基本概念死锁的解决方案 预防 避免 检测及解除 资源分配图 3 5 1死锁的基本概念 死锁 Deadlock 的定义 一组进程中 每个进程都无限等待被该组进程中另一进程所占有的资源 因而永远无法得到的资源 这种现象称为进程死锁 这一组进程就称为死锁进程说明 参与死锁的进程最少是两个参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源注意 如果死锁发生 会浪费大量系统资源 甚至导致系统崩溃 死锁产生的原因1 竞争资源引起永久性资源 可被多个进程多次使用 可再用资源 剥夺性资源 CPU 内存 非剥夺性资源 磁带机 打印机 竞争非剥夺性资源会引起死锁临时性资源 只可使用一次的资源 如信号量 中断信号 同步信号等 可消耗性资源 竞争临时性资源也会引起死锁2 进程推进顺序不当引起对资源采用 申请 分配 使用 释放 模式 由于推进顺序不当两进程都要申请对方已占有的资源 P1 申请打印机申请扫描仪使用释放打印机释放扫描仪 P2 申请扫描仪申请打印机使用释放打印机释放扫描仪 死锁的例子 竞争非剥夺性资源进程推进顺序不当引起死锁 Req R1 Req R2 Rel R1 Rel R2 Rel R1 Rel R2 Req R1 Req R2 P2 P1 不安全区 竞争非剥夺性资源 推进顺序不当进入不安全区 3 5 2产生死锁的四个必要条件 1 互斥条件 资源独占 一个资源每次只能给一个进程使用2 请求和保持条件 部分分配 占有申请 在申请新资源的同时保持对原有资源的占有3 不可剥夺条件 不可强占 资源申请者不能强行的从资源占有者手中夺取资源 资源只能由占有者自愿释放4 循环等待条件 存在进程 等待资源环形链 P1 P2 Pn 其中P1等待P2占有的资源 P2等待P3占有的资源 Pn等待P1占有的资源 3 6死锁的预防3 6 1强限制预防 确定资源分配算法 保证不发生死锁 做法是破坏产生死锁的四个必要条件之一 1 破坏 请求和保持 部分分配 条件每个进程运行前必须一次性申请运行期所需全部资源 若所需资源均可满足则全部分配 该进程运行中不再请求资源 屏弃请求条件 简单 安全 但资源利用率低 要长期等待 2 破坏 不可剥夺 条件在允许进程动态申请资源前提下 规定 某进程在申请新的资源不能立即满足而被阻塞之前 必须释放已占有的资源 可能造成前一段工作失效 若需要再重新申请 增加开销 3 破坏 循环等待 条件采用资源有序分配法 允许进程动态申请资源 对系统中所有资源编号 进程申请资源时应严格按资源编号递增次序进行 否则不予分配 缺点 资源利用仍不充分 3 6 2避免死锁的银行家算法 前面的三种方法由于限制太强 资源利用率都不太高 能否放宽限制条件 E W Dijkstra于1968年提出银行家算法 此算法要事先知道每个进程对资源的最大需求量 算法的基本思路 允许进程动态申请资源 但在每次分配资源前先对本次分配的安全性进行检查 以判断这种分配是否可能导致死锁 若分配可能导致系统死锁 则不予分配 否则分配该资源 检查每次分配后是否仍存在安全分配序列 显然 此法避免了死锁且资源利用率高 1 安全序列 如果进程序列 P1 Pn 对每个Pi 1 i n 进程 它以后尚需要的资源量不超过系统当前剩余资源量与所有Pj j i 进程当前占有资源量之和 则系统处于安全状态 不会发生死锁 称此序列为安全序列 若系统不存在这样一个安全序列 则称系统处于不安全状态 不安全状态可能引起系统死锁 例如 避免死锁的实质是如何使系统不进入不安全状态 安全序列 P2 P1 P3 2 银行家算法 发贷款检查安全性 先给能及时还贷者 算法使用的数据结构 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 Need i j MAX i j Allocatin i j 本次请求向量Request ARRAY 1 m ofinteger 进程Pi的资源向量为 Max i Allocation i Need i 算法 当进程Pi提出资源申请Request时 执行下列步骤 1 若Request Need i 转 2 否则错误返回 2 若Request Available 转 3 否则进程等待 3 系统试探分配资源 修改数据 则有 Available Available Request Allocation i Allocation i Request Need i Need i Request 4 系统执行安全性算法 检查如果按此分配后 系统新状态是安全的 则将资源正式分配给进程Pi 若新状态是不安全的 则恢复原状态进程Pi等待 3 安全性算法设置工作向量Work 系统可供给进程继续运行所需的m类资源数目Finish 能执行完标志 可提供足够资源使进程完成 安全性检查的步骤 1 初值 Work Available Finish false 2 寻找满足条件的Pk Finish k false 且Need k Work 向量比较 如果不存在 则转 4 3 Work Work Allocation k Finish k true 转 2 4 若对所有k Finish k true 则系统处于安全状态 否则处于不安全状态 进程最大需求已分配尚需要可用P110553P2422P3927 4 银行家算法实例 一种资源 安全序列 P2 P1 P3 银行家算法实例 多种资源 假定系统有五个进程 P0 P1 P2 P3 P4 和三类资源 ABC 资源总数为10 5 7 T0时刻资源分配情况为 1 检查T0时刻的安全性 P1332200122532true 安全 P3532211011743true P4743002431745true P27453026001047true P010470107431057true 检查此刻的安全性 安全 可将 1 0 2 分配给P1 2 T1时P1发出请求Request 1 0 2 假定分配 资源变为 P1230302020532true P3532211011743true P4743002431745true P0745010743755true P27553026001057true 3 假定P4请求资源 发出请求向量Request 3 3 0 Request 3 3 0 Available 2 3 0 让P4等待4 若P0请求资源 发出请求向量Request 0 2 0 假定分配 资源为 检查此刻的安全性 Available 2 1 0 已不满足任何进程的需要 不安全 不予分配Available仍为 2 3 0 检查此刻的安全性 安全 可将 0 1 0 分配给P0 若将P0请求改为Request 0 1 0 假定分配 资源变为 P1220302020522true P3522211011733true P4733002431735true P0735020733755true P27553026001057true 3 7死锁的检测与解除 允许死锁发生 系统必须提供检测和解除死锁的手段 操作系统应不断监视系统进展情况 判断死锁是否发生 3 7 1死锁的检测 1 资源分配图用有向图描述进程的死锁 准确 形象系统由若干类资源构成 一类资源称为一个资源类 每个资源类中包含若干个同种资源 称为资源实例 二元组G V E V 结点集 分为P R两部分P p1 p2 pn R r1 r2 rm E 边的集合 其元素为有序二元组分配边 rj pi 资源实例 进程的一条有向边申请边 pi rj 进程 资源类的一条有向边 有环有死锁 有环无死锁 2 死锁定理如果资源分配图中没有环路 则系统中没有死锁 如果图中存在环路则系统中可能存在死锁 如果每个资源类中只包含一个资源实例 则资源分配图环路是死锁存在的充分必要条件 资源分配图化简方法 1 找一个非孤立点进程结点且只有分配边 去掉分配边 将其变为孤立结点 2 再把相应的资源分配给一个等待该资源的进程 即将某进程的申请边变为分配边 3 重复 1 2 操作直到无法再化简 若所有结点都为孤立结点则无死锁 否则死锁发生 3 7 2死锁的解除 一旦死锁发生则采取专门的措施 解除死锁并以最小的代价恢复操作系统运行 死锁的解除 关键是代价最小 1 重新启动2 撤消进程3 剥夺资源4 进程回退 处理机调度 1 高级调度 作业调度接纳调度或长程调度 将后备队列中作业调入内存 并创建进程 2 低级调度 进程调度 短程调度 从就绪队列中选中一进程 把CPU使用权交给它 3 中级调度 内存紧张时将内存的进程挂起调到外存或内存稍有空闲时将它激活重新调入内存2 进程调度方式 1 非抢占方式 Nonpreemptivemode 2 抢占方式 Preemptivemode 3 进程调度的时机 1 执行进程正确完成或错误终止 2 执行进程提出I O请求 等待I O完成时 3 分时系统时间片轮转 分给进程的时间片用完时 4 优先级调度 抢占方式中有更高优先级进程就绪 5 执行进程执行wait 阻塞原语和唤醒原语等操作 4 调度算法 1 先进先出调度算法 FIFO 先来先服务FCFS 2 短作业 进程 优先调度算法 SJF SPF 3 优先权调度算法 HPF HighestPriorityFirst 4 高响应比优先调度算法 5 时间片轮转调度算法 6 多队列反馈调度算法5 常见的实时调度算法 1 最早截止时间优先算法 EarliestDeadlineFirst 2 最低松弛度优先算法 LeastLaxityFirst 6 调度的实现过程保存现进程现场 更新它的PCB 把它移至合适队列选择要执行的进程 更新它的PCB 恢复新进程现场 7 死锁 Deadlock 的定义 进程组中各进程都无限等待被该组另一进程所占的资源注意 参与死锁的进程最少是两个 至少有两个已占有资源 该组所有进程都在等待资源8 产生死锁的四个必要条件 1 互斥条件 资源独占 一个资源只能给一个进程使用 2 请求和保持条件 部分分配 保持原资源申请新资源 3 不可剥夺条件 不可强占 只能由占有者自愿释放 4 循环等待条件 形成等待环9 死锁的预防 强限制 破坏产生死