第4章 处理机调度.ppt

1、第四章 处理机调度,调度的层次 作业调度 进程调度 实时调度,如何充分利用CPU？,多道批处理系统： 合理搭配作业，充分利用系统资源 分时系统： 每个作业得到处理机的均等性 实时系统： 处理机的响应时间,4.1 调度的层次,作业的状态及其转换,作业和进程的状态转换图,处理机调度分成三个层次,处理机是计算机系统中的重要资源 处理机调度算法对整个计算机系统的综合性能指标有重要影响 可把处理机调度分成三个层次： 高级调度 中级调度 低级调度,高级调度也称为作业调度或宏观调度 高级调度的时间尺度通常是分钟、小时或天 中级调度涉及进程在内外存间的交换，从存储器资源管理的角度来看，把进程的部分或全部换出到

2、外存上，可为当前运行进程的执行提供所需内存空间，将当前进程所需部分换入到内存。指令和数据必须在内存里才能被处理机直接访问 低级调度也称微观调度，从处理机资源分配的角度来看，处理机需要经常选择就绪进程或线程进入运行状态，低级调度的时间尺度通常是毫秒级的。由于低级调度算法的频繁使用，要求在实现时做到高效,作业与进程的关系,作业是任务实体，如：一次计算，一个控制过程 进程是执行实体，是系统分配资源的基本单位 一个作业由一个以上进程组成,作业如何分解为进程？,系统创建根进程 创建子进程 为子进程分配资源 调度子进程执行,4.2 作业调度,主要功能： 审查系统能否满足用户作业的资源要求 较容易 只要通过

3、调用相应的资源管理程序的有关部分，审核其表中是否能满足作业说明书中的要求即可 按照一定的算法从输入井中的后备作业中选取作业 调度的关键在选择恰当的算法,1调度算法评价,调度实质上是一个策略问题 设定的目标往往是相互冲突的 目标： 单位时间内运行尽可能多的作业 使处理机尽可能保持“忙碌” 使各种I/O设备得以充分利用 对所有的作业都是公平合理的,要设计一个理想的调度算法是一件十分困难的事 在实际系统中，调度算法往往折衷考虑 设计调度算法时应考虑的因素： 调度算法应与系统设计目标保持一致 注意系统资源均衡使用 保证提交的作业在截止时间内完成 设法缩短作业平均周转时间 大多数操作系统都采用比较简单的

4、调度算法,假定某一作业进入“输入井”的时间为Si， 它被选中执行，得到计算结果的时间为Ei 它的周转时间为Ti Ei Si 则作业平均周转时间为： T（ ） 其中，n为被测定作业流中的作业数,作业平均周转时间,2调度算法性能的衡量,平均带权周转时间,W（ ） 其中，ri 为某作业i的实际执行时间,T：衡量不同调度算法对同一个作业流的性能 W：同一调度算法对不同作业流的性能衡量,3系统进行作业调度的决策因素,作业到达时间 预先为作业确定的优先级 系统可测定的其他因素： 作业所需的CPU时间C 存储要求M 打印输出的行数L 其他的资源要求,4常见的批处理作业调度算法,（1）先来先服务算法 （FCF

5、S：First Come First Serve） （2）最短作业优先算法 （SJF：Shortest Job First） （3）最高响应比优先算法 （HRN：Highest Response Ratio Next） 响应比R = 作业周转时间 / 作业处理时间 =（作业处理时间 + 作业等待时间）/ 作业处理时间 = 1 +（作业等待时间 / 作业处理时间） （4）基于优先数调度算法 （HPF：Highest Priority First）,（a）由用户规定优先数（外部优先数） 用户提交作业时，根据急迫程度规定适当的优先数 作业调度程序根据JCB优先数决定进入内存的次序 （b）由系统计算优

6、先数(内部优先数) 例：可按如下公式计算作业的优先数： 优先数 = 用户规定优先数 作业处理时间 + 作业等待时间 输出量,（5）均衡调度算法(分类排队算法),基本思想： 根据系统运行情况和作业属性将作业分类 轮流从不同的作业类中挑选作业 目标： 力求均衡地利用各种系统资源，发挥资源使用效率 力求使用户满意,例1：将待处理作业分成如下队列： 队列1：计算量大的作业 队列2：I/O量大的作业 队列3：计算量与I/O量均衡的作业 调度时，在三个队列中各取一些作业 在内存中的作业有的使用处理机 有的使用外部设备 使得系统的各种资源能得到充分利用,例2：将待处理作业分成如下三个队列： 队列1：长作业

7、队列2：中等长度作业 队列3：短作业 调度时 取队列1一作业，队列2一作业，队列3一作业 长作业用户和短作业用户均比较满意,5作业调度算法应用例子1,假设在单道批处理环境下有四个作业，已知它们进入系统的时间、估计运行时间 应用先来先服务、最短作业优先和最高响应比优先作业调度算法，分别计算出作业的平均周转时间和带权的平均周转时间,先来先服务调度算法计算结果,最短作业优先作业算法计算结果,最高响应比优先作业算法计算结果,4.3 进程调度,要解决的问题 WHAT：按什么原则分配CPU 进程调度算法 WHEN：何时分配CPU 进程调度的时机 HOW： 如何分配CPU CPU调度过程（进程的上下文切换）

8、,4.3.1 进程调度算法,1进程调度 进程调度的任务是控制协调进程对CPU的竞争即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程,2确定算法的原则,具有公平性 资源利用率高（特别是CPU利用率） 在交互式系统情况下要追求响应时间（越短越好） 在批处理系统情况下要追求系统吞吐量,3各种进程调度算法,先进先出进程调度算法（FIFO） 按照进程就绪的先后次序来调度进程 优点:实现简单 缺点:没考虑进程的优先级,基于优先数的调度（HPFHighest Priority First）,优先选择就绪队列中优先级最高的进程投入运行 优先级根据优先数来决定,确定优先数的方法 静态

9、优先数法： 在进程创建时指定优先数，在进程运行时优先数不变 动态优先数法： 在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变,两种占用CPU的方式,可剥夺式（可抢占式Preemptive）： 当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用 不可剥夺式（不可抢占式 Non-preemptive ）： 某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去,时间片轮转程序调度算法(RRRound Robin),把CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程，进程轮流

10、占有CPU，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列末尾。同时系统选择另一个进程运行,分时系统中常用时间片轮转法,时间片选择问题： 固定时间片 可变时间片 与时间片大小有关的因素： 系统响应时间 就绪进程个数 CPU能力,多队列反馈调度算法：,将就绪队列分为N级，每个就绪队列分配给不同的时间片，队列级别越高，时间越长，级别越小，时间片越小，最后一级采用时间片轮转，其他队列采用先进先出； 系统从第一级调度，当第一级为空时，系统转向第二个队列，.当运行进程用完一个时间片，放弃CPU时，进入下一级队列；等待进程被唤醒时，进入原来的就绪队列；当进程第一次就绪时

11、，进入第一级队列,* 首先系统中设置多个就绪队列 * 每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大 * 各个队列按照先进先出调度算法 * 一个新进程就绪后进入第一级队列 * 进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列 * 当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾 * 当第一级队列空时，就去调度第二级队列，如此类推 * 当时间片到后，进程放弃CPU，回到下一级队列,4.3.2 进程调度的时机,当一个进程运行完毕，或由于某种错误而终止运行 当一个进程在运行中处于等待

12、状态（等待I/O） 分时系统中时间片到 当有一个优先级更高的进程就绪（可抢占式） 例如：新创建一个进程，一个等待进程变成就绪 在进程通信中，执行中的进程执行了某种原语操作（P操作，阻塞原语，唤醒原语）,4.3.3 CPU调度过程,* 保存现场：顺序保存，最后一步保存PSW * 选择要运行的程序 （如果没有就绪进程,系统会安排一个闲逛进程(idle),没有其他进程时该进程一直运行,在执行过程中可接收中断） * 恢复现场：最后一步恢复选中进程的PSW,在进程（上下文）中切换的步骤,保存处理器的上下文，包括程序计数器和其它寄存器 用新状态和其它相关信息更新正在运行进程的PCB 把原来的进程移至合适的

13、队列-就绪、阻塞 选择另一个要执行的进程 更新被选中进程的PCB 从被选中进程中重装入 CPU 上下文,4.4 作业调度与进程调度,在多道批处理系统中，同时存在作业调度和进程调度的问题 作业能否占用处理器？什么时间能够占用处理器？ 由进程调度来决定 进程的初始状态为就绪状态 进程调度选择当前可占用 CPU处理进程，当它让出处理器时，进程调度就再选另一作业的进程 作业调度与进程调度相互配合，实现作业的并行,例1：在一个多道批处理系统中，有两个作业进程。有一作业序列，其到达时间及估计运行时间列表见下表：,系统采用最高响应比优先的作业调度算法（响应比=等待时间/估计运行时间）。作业进程的调度采用短作

14、业优先的抢占式调度算法。1）列出各作业的执行时间片段；2）计算这批作业的平均周转时间。,分析本题的作业和进程的推进过程如下： 10：00 作业1到达,被作业调度程序调度 进入系统,被进程调度程序调度 开始运行,10：10 作业1运行10分钟，剩余25分钟 由于作业较长，被进程调度程 序调度处于就绪状态 作业2到达，由作业调度程序调 度进入系统,由于作业较短，被 进程调度程序调度开始运行,10：15 作业1等待5分钟，剩余25分钟 作业2运行5分钟，剩余25分钟 作业3到达，等待作业调度进程 调度,10：20 作业1等待10分钟，剩余25分钟 作业2运行10分钟，剩余20分钟 作业3等待5分钟

15、作业4到达，等待作业调度进程 调度,10：30 作业1等待20分钟，剩余25分钟 作业2运行20分钟，剩余10分钟 作业3等待15分钟 作业4等待10分钟 作业5到达，等待作业调度进程 调度,10：40 作业1等待30分钟，剩余25分钟 作业2运行30分钟，运行结束 作业3等待25分钟，响应比为25/45 作业4等待20分钟，响应比为20/20 因响应比较高，被作业调度程序 调度进入系统,由于作业较短， 被进程调度程序调度开始运行 作业5等待10分钟，响应比为10/30,11：00 作业1等待50分钟，剩余25分钟 由于作业较短，被进程调度程序调 度开始运行 作业3等待45分钟，响应比为45/

16、45 因响应比相同，按序被作业调度程 序调度进入系统 由于作业较长，被进程调度程序调 度处于就绪状态 作业4运行20分钟，运行结束 作业5等待30分钟，响应比为30/30,11：25 作业1运行35分钟，运行结束 作业3等待(在内存)25分钟， 因作业较长，被作业调度程序调 度处于就绪状态 作业5等待55分钟，被作业调度程序 调度进入系统 由于作业较短，被进程调度程序 调度开始运行,11：55 作业3等待(在内存)55分钟，被 进程调度程序调度开始运行 作业5运行30分钟，运行结束 12：40 作业3运行45分钟，运行结束,解答1）各作业的执行时间序列如下： 作业1：10：0010：10， 1

17、1：0011：25（结束） 作业2：10：1010：40（结束） 作业3：11：5512：40（结束） 作业4：10：4011：00（结束） 作业5：11：2511：55（结束）,2）各作业执行时的周转时间为： 作业1 85分钟 作业2 30分钟 作业3 145分钟 作业4 40分钟 作业5 85分钟 作业的平均周转时间为77分钟,例2:有一个具有两道作业的批处理系统,作业调度采用短作业优先的调度算法,进程调度采用以优先数为基础的抢占式调度算法(优先数数值越小优先级越高), 1)列出所有作业进入内存时间及结束时间 2)计算平均周转时间,10:00 A作业到达,被作业调度程序调度进 入系统,被进

18、程调度程序调度开始 运行,10:20 A作业运行20分钟,剩余20分钟 由于优先级低,被进程调度程序调 度处于就绪状态 B作业到达,被作业调度程序调度进 入系统,由于优先级高,被进程调度 程序调度开始运行,10:30 A作业等待10分钟,剩余20分钟 继续等待 B作业运行10分钟,剩余20分钟 继续运行 C作业到达,等待被作业调度程序调度,10:50 A作业等待30分钟,剩余20分钟 由于优先级高,被进程调度程序调 度开始运行 B作业运行30分钟,结束运行 C作业等待20分钟,由于估计运行时 间较长,仍未被调入系统中运行 D作业到达,由于估计运行时间较短, 被作业调度程序调入系统,由于优 先级

19、低,被进程调度程序调度处于 就绪状态,11:10 A作业运行40分钟,结束运行 C作业等待30分钟,被作业调度程序 调入系统,由于优先级高,被进程调 度程序调度开始运行 D作业等待10分钟,由于优先级低,被 进程调度程序调度处于就绪状态,12:00 C作业运行50分钟,结束运行 D作业等待60分钟,被进程调度程序 调度开始运行 12:20 D作业运行20分钟,结束运行,各作业执行时的周转周期为: 作业A 70分钟 作业B 30分钟 作业C 90分钟 作业D 90分钟 作业的平均周转时间为70分钟,4.5 实时系统调度方法,4.5.1 实时系统的特点 根据对处理外部事件的时限要求，实时系统中处理

20、的外部事件可分为硬实时任务和软实时任务。 硬实时任务要求系统必须完全满足任务的时限要求。 软实时任务则允许系统对任务的时限要求有一定的延迟，其时限要求只是一个相对条件。,实时系统的另一个特点是它所处理的外部任务可分为周期性的与非周期性的两大类。 对于非周期性任务来说，存在有一个完成或开始进行处理时限。 而周期性任务只要求在周期T内完成或开始进行处理。,实时系统具有以下特点： (1) 有限等待时间 (2) 有限响应时间 (3) 用户控制 (4) 可靠性高 (5) 系统出错处理能力强,实时操作系统具有下述能力： (1) 很快的进程或线程切换速度 (2) 快速的外部中断响应能力 (3) 基于优先级的

21、随时抢先式调度策略,基于优先级的调度策略大致有以下4种 优先级+时间片轮转调度策略； 基于优先级的非抢先式调度策略； 基于优先级的固定点抢先式调度策略； 基于优先级的随时抢先式调度策略。 哪些策略可用于实时调度？ 和,4.5.2 实时调度算法的分类,4类实时调度算法： (1) 静态表格驱动类 (2) 静态优先级驱动抢先式调度算法类 (3) 动态计划调度算法类 (4) 尽力而为调度算法类,4.5.3 时限调度算法与频率单调调度算法,1. 时限调度算法 时限调度算法是一种以满足用户要求的时限为调度原则的算法。 在实时系统中的用户要求时限有两种，即处理开始时限和处理结束时限。时限调度算法可以使用任一

22、种时限。时限调度算法可用于周期性调度与非周期性调度两种。,时限调度算法所需要的相关输入信息： (1) 任务就绪时间或事件到达时间 指进程进入就绪状态，可以被调度执行的时间。 对于周期性任务来说，该时间是可以预知的，而且时间间隔是周期性的。 对于非周期性任务来说，这些时间可能是可预知的，但大部分时候是不可预知的，需要事件发生来驱动。,(2) 开始时限 处理机必须开始对任务进行处理的时限。 (3) 完成时限 指的是任务必须完成的时间 (4) 处理时间 完成相关任务所需占用处理机的时间。 (5) 资源需求 除了处理机之处，还需要的其他硬软件资源。 (6) 优先级 可由分析计算后获得，也可根据时限要求

23、，由用户指定。,时限调度算法的基本思想： 按用户的时限要求顺序设置优先级，优先级高者占据处理机，也就是说，时限要求最近的任务优先占有处理机。 时限调度是抢先式的。抢先式时限调度算法必须把新到达任务的时限要求和当前正在执行任务的时限要求进行比较，如果新到达任务的时限要求更近，则应执行新到达的任务。,例题,设实时系统从两个不同的数据源DA和D周期性地收集数据并进行处理，其中DA的时限要求以30 ms为周期，DB的时限要求以75 ms为周期。设DA所需处理时限为15 ms，DB所需处理时限为38 ms，则与DA和DB有关进程的事件发生时限（就绪时限），执行时限以及结束时限如图所示。,周期性任务的预计发生、执行与结束时限,2.频率单调调度算法 频率单调调度算法是一种被广泛用于多周期性实时处理的调度算法。 频率单调调度算法的基本原理是频率越低（周期越长）的任务的优先级越低。 任务的执行时间为C，则使用频率单调调度算法的必要条件是C T。,对于n(n1)个周期的不同任务来说，设每个周期为Ti，其相应任务的执行时间为Ci，则使用频率单调调度算法的充分条件是 例如，对于由3个周期