第四章 处理机调度.ppt

1、第四章 处理机调度,一、分级调度,处理机调度可分为四级： 作业调度（宏观调度或高级调度）：负责从后备作业中选择若干作业调到内存，并为它们分配相应的资源，当作业运行完毕时，负责回收资源。 交换调度（中级调度）：负责外存交换区域内存中的就绪状态或等待状态的进程进行交换。 进程调度（微观调度或低级调度）负责选取适当的进程占有处理机 线程调度,二、作业调度,1、主要功能 审查系统能否满足用户作业的资源要求，较容易，只要通过调用相应的资源管理程序的有关部分，审核其表中是否能满足作业说明书中的要求即可。 按照一定的算法丛输入井中的后备作业中选取作业。,调度的关键在选择恰当的算法 2、调度算法的评价 调度实

2、质上是一个策略问题，设定的目标往往是相互冲突的。 目标： 单位时间内运行尽可能多的作业 是处理机尽可能保持“忙碌” 使各种I/O设备得以充分利用 对所有的作业都是公平合理的 要设计一个理想的调度算法是一件十分困难的事，在实际系统中，调度算法往往折衷考虑,设计调度算法时应考虑的因素： 调度算法应与系统设计目标保持一致 注意系统资源均衡使用 保证提交的作业在截止时间内完成 设法缩短作业平均周转时间 大多数操作系统都采用比较简单的调度算法,3、调度算法性能的衡量 （1）作业平均周转时间：假定某一作业进入“输入井”的时间为Si，它被选中执行，得到计算结果的时间为Ei，它的周转时间为Ti=Ei-Si 则

3、作业平均周转时间为：T=（ ）1/n 其中，n为被测定作业流中的作业数,（2）平均带权某周转时间 W=（ ）1/n 其中，ri为作业i的实际执行时间 T：衡量不同调度算法对同一个作业流的性能 W：同一调度算法对不同作业流的性能衡量,4、系统进行作业调度的决策因素 作业到达时间 预先为作业确定的优先级,三、常见的批处理作业调度算法,1、先来先服务（FCFS:First Come First Serve) 2、最短作业优先算法（SJF: Shortest Job First) 3、最高响应比优先算法（HRN:Highest Response Ratio Next) 响应比R=作业周转时间/作业处理

4、时间 =（作业处理时间+作业等待时间）/作业处理时间 =1+作业等待时间/作业处理时间,4、基于优先数调度算法（HPF：Heghest Priority First） （1）由用户规定优先数（外部优先数） 用户提交作业时，根据急迫程度规定适当的优先数。 作业调度程序根据JCB优先数决定适当的优先数 （2）由系统计算优先数（内部优先数） 例：可按如下公式计算作业的优先数： 优先数=用户规定优先数-作业处理时间+作业等待时间-输出量,5、轮转法 基本思路：让每个进程在就绪队列中的等待时间与享受服务的时间成正比。 时间片的选择是根据系统对响应时间的要求R和就绪队列中所允许的最大进程数Nmax确定的。

5、表示为：q=R/ Nmax 只能用来调度那些可以抢占的资源。 该方法不用于作业调度,6、均衡调度算法（分类排队算法） 基本思想： 根据系统运行情况和作业属性将作业分类 轮流从不同的作业类中挑选作业 目标： 力求均衡地利用各种系统资源，发挥资源使用效率 力求使用户满意,例1：将待处理作业分成如下队列： 队列1：计算量大的作业 队列2：I/O量大的作业 队列3：计算量与I/O量均衡的作业 调度时，在三个队列中各取一些作业 在内存中的作业有的使用处理机 有的使用外部设备 使得系统的各种资源能得到充分利用,例2：将待处理作业分成如下三个队列： 队列1：长作业 队列2：中等长度作业 队列3：短作业 调度

6、时 取队列1一作业，队列2一作业，队列3一作业 长作业用户和短作业用户均比较满意,四、调度算法举例,例1：假设在单道批处理环境下有四个作业，已知它们进入系统的时间、估计运行时间 应用先来先服务、最短作业优先和最高响应比优先作业调度算法，分别计算出作业的平均周转时间和带权的平均周转时间,先来先服务：,短作业优先：,最高响应比优先：,例2：在两道环境下有四个作业 已知它们进入系统的时间、估计运行时间 系统采用短作业优先作业调度算法，作业被调度运行后不再退出 当一新作业投入运行后，可按照作业运行时间长短调整作业执行的次序 请给出这四个作业的执行时间序列，并计算出平均周转时间及带权平均周转时间,短作业

7、优先：,四个作业的执行时间序列为： JOB1：10：0010：05，10：4011：05 JOB2：10：0510：25 JOB3：10：2510：30 JOB4：10：3010：40,在两道批处理系统中，短作业优先算法的分析： 10：00，JOB1进入，只有一作业，JOB1被调入执行 10：05，JOB2到达，最多允许两作业同时进入 所以JOB2也被调入 内存中有两作业，哪一个执行？题目规定当一新作业运行后，可按作业运行时间长短调整执行次序 即基于优先数可抢占式调度策略 优先数是根据作业估计运行时间大小来决定的 由于JOB2运行时间（20分）比JOB1少 （到10：05，JOB1还需25分钟） 所以JOB2运行