第4章 处理机调度

第4章处理机调度 分级调度作业调度进程调度调度算法实时系统调度方法 在计算机系统中 可能同时有数百个批处理作业存放在磁盘的作业队列中 或者有数百个终端与主机相连接 这样一来内存和处理器等资源便供不应求 如何从这些作业中挑选作业进入主存运行 如何在进程之间分配处理器时间 无疑是操作系统资源管理中的一个重要问题 处理器调度用来完成涉及处理器分配的工作 概述 作业的状态及其转换一个作业从提交给计算机系统到执行结束退出系统 一般都要经历提交 收容 执行和完成等4个状态 以前我们讲授过该部分内容 分级调度 图4 1作业的状态及其转换 一个作业在其处于从输入设备进入外部存储设备的过程称为提交状态 处于提交状态的作业 因其信息尚未全部进入系统 所以不能被调度程序选取 收容状态也称为后备状态 输入管理系统不断地将作业输入到外存中对应部分 或称输入井 即专门用来存放待处理作业信息的一组外存分区 若一个作业的全部信息已全部被输入进输入井 那么 在它还未被调度去执行之前 该作业处于收容状态 分级调度 作业调度程序从后备作业中选取若干个作业到内存投入运行 它为被选中作业建立进程并分配必要的资源 这时 这些被选中的作业处于执行状态 当作业运行完毕 但它所占用的资源尚未全部被系统回收时 该作业处于完成状态 在这种状态下 系统需做诸如打印结果 回收资源等类的善后处理工作 分级调度 调度的层次一般来说 处理机调度可以分为三级 高级调度 又称作业调度或长程调度 Long termScheduling 其主要任务是按一定的原则对外存输入井上的大量后备作业进行选择 给选出的作业分配内存 输入输出设备等必要的资源 并建立相应的进程 以使该作业的进程获得竞争处理机的权利 另外 当该作业执行完毕时 回收系统资源 分级调度 调度的层次中级调度 又称交换调度 平衡负载调度或中程调度 Medium termScheduling 中级调度根据存储资源量和进程的当前状态来决定辅存和主存中的进程的对换 它所使用的方法是通过把一些进程换出主存 从而 使之进入 挂起 状态 不参与低级调度 起到短期平滑和调整系统负荷的作用 交换调度主要涉及到内存管理与扩充 分级调度 调度的层次低级调度 又称进程调度 或线程调度 短程调度 Short termScheduling 其主要任务是按照某种策略和方法选取一个处于就绪状态的进程占用处理机 在确定了占用处理机的进程后 系统必须进行进程上下文切换以建立与占用处理机进程相适应的执行环境 通常 我们所说的调度一般指进程调度 分级调度 关于不同级别调度的说明 在多道批处理系统中 存在着作业调度和进程调度 在分时系统和实时系统中 一般不存在作业调度 而只有进程调度 交换调度 因而 这些系统中没有作业提交状态和后备状态 它们的输入信息经过终端缓冲区为系统所接收 或者立即处理 或者经交换调度暂存外存中 现代操作系统偏向于后者 分级调度 选择调度算法的原则资源利用率 使得CPU或其他资源的使用率尽可能高且能够并行工作 CPU利用率 CPU有效工作时间 CPU总运行时间 响应时间 交互式进程从提交一个请求 命令 到接收到响应之间的时间间隔称响应时间 使交互式用户的响应时间尽可能短 或尽快处理实时任务 分时系统和实时系统 调度算法设计原则 选择调度算法的原则周转时间 批处理用户从作业提交开始 到作业完成为止的时间间隔称作业周转时间 应使作业周转时间或平均作业周转时间尽可能短 批处理系统吞吐率 使单位时间内处理的作业数尽可能多 公平性 确保每个用户每个进程获得合理的CPU份额或其他资源份额 不会出现饿死情况 调度算法设计原则 周转时间与带权周转时间定义作业i的周转时间为 Ti Tei Tsi其中Tei为作业i的完成时间 Tsi为作业的提交时间 对于被测定作业流所含有的n n 1 个作业来说 其平均周转时间为 调度算法设计原则 周转时间与带权周转时间定义带权周转时间一个作业的周转时间说明了该作业在系统内停留的时间 包含两部分 等待时间 执行时间 即 Ti Twi Tri这里 Twi主要指作业i由后备状态到执行状态的等待时间 它不包括作业进入执行状态后的等待时间 调度算法设计原则 周转时间与带权周转时间定义带权周转时间带权周转时间是作业周转时间与作业执行时间的比 Wi Ti Tri对于被测定作业流所含有的几个作业来说 其平均带权周转时间为 调度算法设计原则 调度算法的执行方式非剥夺式 一个作业一旦投入运行 除非进程本身自愿让出CPU 否则一直运行完成 调度算法不得剥夺其运行权 剥夺式 系统实时地根据调度原则 当某就绪进程满足条件时 立即将正在运行的进程中断 并切换到其进程 调度算法设计原则 作业调度 批处理系统 作业调度主要是完成作业从后备状态到执行状态的转变 以及从执行状态到完成状态的转变 作业调度功能 1 记录系统中各作业的状况 系统为每个作业建立一个作业控制表JCB记录这些有关信息 系统通过JCB而感知作业的存在 JCB主要内容 作业名 作业类型 资源要求 当前状态 资源使用情况以及该作业的优先级等 作业调度 图4 2作业控制块JCB 作业调度 作业调度 批处理系统 作业调度功能 2 从后备队列中挑选出一部分作业投入执行 3 为被选中作业做好执行前的准备工作 为选中作业建立相应进程 并分配系统资源 4 在作业执行结束时做善后处理工作 主要是输出作业管理信息 回收该作业所占用的资源 撤消与该作业有关的全部进程和该作业的作业控制块等等 作业调度 进程调度无论是在批处理系统还是分时系统中 用户进程数一般都多于处理机数 这将导致用户进程互相争夺处理机 另外 系统进程也同样需要使用处理机 这就要求进程调度程序按一定的策略 动态地把处理机分配给处于就绪队列中的某一个进程 以使之执行 进程调度 进程调度进程调度的功能 1 记录系统中所有进程的执行情况 进程管理模块将进程的执行情况和状态记录在PCB中 进程调度模块根据PCB来控制进程的执行 2 选择占有处理机的进程 进程调度的主要功能是按照一定的策略选择一个处于就绪状态的进程 使其获得处理机执行 3 进行进程上下文切换一个进程的执行是在进程的上下文中执行 当进程调度时 如果发生新进程被选中 系统要完成进程的切换 进程调度 进程调度的时机进程调度发生在什么时机呢 这与引起进程调度的原因以及进程调度的方式有关 引起进程调度的原因有以下几类 1 正在执行的进程执行完毕 2 进程执行了阻塞原语进入睡眠状态 3 进程调用了PV操作 被阻塞或唤醒一进程 4 进程提出I O请求后被阻塞 进程调度 进程调度的时机 5 进程的时间片已经用完 6 在执行完系统调用 调度选择新用户进程执行 7 就绪队列中的某进程的优先级变得高于当前执行进程的优先级 从而也将引发进程调度 进程调度 进程上下文切换进程上下文由正文段 数据段 硬件寄存器的内容以及有关数据结构等组成 在发生进程调度时 系统要做进程上下文切换 进程上下文切换包括以下步骤 1 决定是否做上下文切换以及是否允许做上下文切换 包括对进程调度原因的检查分析 以及当前执行进程的资格和CPU执行方式的检查等 进程调度 进程上下文切换 2 保存当前执行进程的上下文 3 使用进程调度算法 选择一个处于就绪状态进程 4 恢复或装配调度选中进程的上下文 将CPU控制权交给该进程 进程调度 先来先服务 FCFS FirstComeFirstServe 算法该算法是按照作业进入系统的作业后备队列的先后次序来挑选作业 先进入系统的作业优先被挑选 这是一种非剥夺式算法 易实现 效率低 不利于短作业 但优待了长作业 可能使短作业周转时间变得很大 影响批作业的平均周转时间 该算法适用于作业调度和进程调度 调度算法 先来先服务 FCFS 在实际操作系统中 尽管很少单独使用FCFS算法 但和其他一些算法配合起来 FCFS算法还是使用得相当多的 例如基于优先级的调度算法就是对具有同样优先级的作业或进程采用的FCFS方式 调度算法 先来先服务 FCFS 例 下面三个作业同时到达系统并立即进入调度 调度算法 先来先服务 FCFS 假设系统中没有其他作业 现采用FCFS算法进行调度 那么 三个作业的周转时间分别为 28 37和40 因此 平均作业周转时间T 28 37 40 3 35若顺序改为2 1 3 则平均周转时间为约29 如顺序改为3 2 1 则平均周转时间为约18 可以看出 FCFS调度算法的平均作业周转时间与作业提交及调度的顺序有关 调度算法 最短作业优先SJF ShortestJobFirst 该算法是以进入系统的作业所要求的CPU时间长短为标准 总是选取估计计算时间最短的作业投入运行 这是一种非剥夺式调度算法 它克服了FCFS偏爱长作业的缺点 易于实现 但效率也不高 该算法适用于作业调度 调度算法 最短作业优先SJF ShortestJobFirst 主要不足 一是预先估计作业计算时间很难精确 二是忽视了长作业的等待时间 长作业可能会出现饥饿现象 三是该算法由于属于非剥夺机制 对分时 实时处理不理想 调度算法 最短作业优先SJF ShortestJobFirst 例 若有以下四个作业同时到达系统并立即进入调度 调度算法 最短作业优先SJF ShortestJobFirst 现对它们实施SJF调度算法 这时的作业调度顺序为作业2 4 1 3 则 平均周转时间T 4 12 21 31 4 17平均带权周转时间W 4 4 12 8 21 9 31 10 4 1 98如果对它们施行FCFS调度算法 则 平均周转时间T 9 13 23 31 4 19平均带权周转时间W 9 9 13 4 23 10 31 8 4 2 51 调度算法 最短作业优先SJF ShortestJobFirst SJF算法是非抢占式的 可以改进成抢占式的调度算法 当一个作业正在执行时 一个新作业进入就绪状态 如果新作业需要的CPU时间比当前正在执行的作业剩余下来还需的CPU时间短 抡占式短作业优先调度算法强行赶走当前正在执行的作业 这种方式叫最短剩余时间优先算法SRTF ShortestRemainingTimeFirst 算法 此算法适用于作业调度和进程调度 调度算法 最高响应比 HRRF HighestResponseRatioFirst 算法响应比定义 响应比 作业等待时间 作业计算时间每当调度一个作业运行时 都要计算后备作业队列中每个作业的响应比 选择响应比最高者投入运行 显然 短作业容易得到较高响应比 算法优待短作业 但长作业等待时间足够长 也将获得足够高的响应比 不至于长时间地等待下去 调度算法 最高响应比 HRRF HighestResponseRatioFirst 算法最高者优先算法既考虑作业等待时间 又考虑作业的运行时间 这样既照顾了短作业又不使长作业的等待时间过长 改进了调度性能 缺点是每次计算各道作业的响应比会有一定的时间开销 需要估计期待的服务时间 性能要比SJF差 调度算法 最高响应比 HRRF HighestResponseRatioFirst 算法例 若有以下四个作业先后到达系统进入调度 调度算法 最高响应比 HRRF HighestResponseRatioFirst 算法例 若有以下四个作业先后到达系统进入调度 对这个作业流执行HRRF调度算法 平均周转时间T 20 25 40 50 4 33 75平均带权周转时间W 20 20 25 5 40 15 50 10 4 3 4该算法的性能介于SJF和FCFS之间 自行计算验证一下 调度算法 优先级法优先级法可被用作作业或进程的调度策略 首先 系统或用户按某种原则为作业或进程指定一个优先级来表示其优先权 该算法的核心是确定进程或作业的优先级 确定优先级的方法可分为静态法和动态法 调度算法 优先级法静态优先级 作业的静态优先级按以下原则确定 1 由用户自己根据作业的紧急程度输入一个适当的优先级 系统对高优先级用户收取高费用 2 由系统或操作员根据作业类型指定优先级 作业类型一般由用户约定或由操作员指定 3 系统根据作业要求资源情况确定优先级 调度算法 优先级法静态优先级进程的静态优先级按以下原则确定 1 按进程的类型给予不同的优先级 系统进程和用户进程 2 将作业的静态优先级作为它所属进程的优先级 调度算法 优先级法动态优先级 进程 进程的动态优先级一般根据以下原则确定 1 根据进程占有CPU时间的长短来决定 一个进程占有处理机的时间愈长 则在被阻塞之后再次获得调度的优先级就越低 2 根据就绪进程等待CPU的时间长短来决定 一个进程在就绪队列中等待时间越长 它获得的优先级就越高 调度算法 轮转法 RR roundrobin 轮转法的基本思路是让每个进程在就绪队列中的等待时间与享受服务的时间成比例 轮转法的基本概念是将CPU的处理时间分成固定大小的时间片 如果一个进程在被调度选中之后用完了系统规定的时间片 但未完成要求的任务 则它自行释放自己所占有的CPU而排到就绪队列的末尾 等待下一次调度 调度算法 该算法一般仅适用于进程调度 不适用于作业调度 调度算法 轮转法 RR roundrobin 在轮转法中 时间片长度的选取非常重要 如果时间片长度过短 则调度程序剥夺处理机的次数增多 这将使进程上下文切换次数也大大增加 从而加重系统开销 反过来 如果时间片长度选择过长 可能变成了先来先服务法 时间片长度的选择是根据系统对响应时间的要求R和就绪队列中所允许的最大进程数Nmax确定的 它可表示为 q R Nmax 调度算法 多级反馈轮转法该方法又称反馈循环队列或多队列策略 主要思想是将就绪进程或线程分为多级就绪队列 较高优先级的队列分配时间片较短 调度算法每次先从高一级就绪队列中选取 同一队列中按FCFS原则