作业调度
1. 作业调度的主要任务
根据 JCB 中的信息,检查系统中的资源能否满足作业对资源的需求,以及按照一定的调度算法,从外存的后备队列中选取某些作业调入内存,并为它们创建进程、分配必要的资源。
2. 作业运行的三个阶段和三个状态
阶段 | 收容阶段 | 运行阶段 | 完成阶段 |
---|---|---|---|
状态 | 后备状态 | 运行状态 | 完成状态 |
- 收容阶段:
操作员把用户提交的作业通过某种方式或SPOOLiing 系统输入到硬盘上,再为该作业建立 JCB ,并把它放入都作业后备队列中。此时作业状态为 后备状态 。
- 运行阶段:
当作业被作业调度选中后,便为它分配必要的资源和建立进程,并把它放入就绪队列。此时作业的状态为就绪状态,但作业可能多次在就绪状态和运行状态之间转换,所以,在一个作业从第一次进入就绪状态开始,直到运行结束,此期间的作业状态为 运行状态。
- 完成阶段
当作业运行完成、或发生异常情况而提前结束时,作业便进入完成阶段,系统中的“终止作业”程序将会回收已分配给该作业的作业控制块和所有资源。此时作业的状态为 完成状态。
3. 作业调度常用的算法
先来先服务(FCFS)、短作业优先(SJF)、优秀级调度算法(PSA)、高响应比优先调度算法(HRRN)、时间片轮转(RR)、多级反馈队列算法。
几种时间的概念
到达时间:作业来到的时刻
服务时间:作业占用CPU的时间
完成时间:作业执行完的时刻
周转时间:完成时间 - 到达时间
带权周转时间:周转时间 / 服务时间
平均周转时间:周转时间 / 作业个数
平均带权周转时间:带权周转时间 / 作业个数
先来先服务(FCFS)
算法特点
- 按照作业提交或变为后备状态的先后次序分配CPU
- 新作业只有当当前的作业执行完成或者阻塞才能获得CPU
- 被唤醒的作业不会立即恢复执行,默认是非抢占式,通常要等到当前的作业让出CPU
算法的优缺点
有利于CPU繁忙型的作业,不利于I/O繁忙的作业,如果后备队列中作业过多,新加入的作业等待的时间会很长。
一般FCFS算法在单处理机中已很少作为主调度算法,但经常把它与其他调度算法相结合使用,形成一种更为有效的调度算法。
例题:
作业A、B、C、D、E,分别在0,1,2,3,4时刻到达,需要服务时间分别为4,3,5,2,4,试用先来先服务算法,计算它们的完成时间,周转时间,带权周转时间,平均周转时间,平均带权周转时间。
作业的执行状态:
短作业优先(SJF)
算法特点
- 按照作业的长短来计算优先级,作业越短,其优先级越高
- 作业长度是按照作业所需要占用的CPU时间来衡量的
- 属于非抢占式,只有当当前的作业释放出CPU,新作业才可能获得CPU
算法的优缺点
SJF算法对短作业有利,能有效的降低作业的平均等待时间,提高系统的吞吐量。
但未考虑作业的紧迫程度,因而不能保证紧迫性作业的及时处理;
还必须预知作业的运行时间,作业的运行时间需要进行估计,如果估计过低,作业未完成就会提前终止,所以一般都会偏长估计;
对长作业非常不利,长作业的周转时间明显偏长。
完全忽略作业的等待时间,可能使作业等待时间过长,出现饥饿现象;
人机无法交互。
例题
作业A、B、C、D、E,分别在0,1,2,3,4时刻到达,需要服务时间分别为4,3,5,2,4,试用短作业优先算法,计算它们的完成时间,周转时间,带权周转时间,平均周转时间,平均带权周转时间。
作业的执行状态:
高响应比优先调度算法(HRRN)
算法特点
- 高响应比调度算法既考虑了作业的等待时间,又考虑作业运行时间。因此既照顾了短作业,又不致长作业的等待时间过长。
- 为每个作业引入动态优先权,使作业的优先级随着等待时间的增加而以提高
优先权的动态规律
$$
优先权 = \frac{等待时间+要求服务时间}{要求服务时间}=\frac{响应时间}{要求服务时间}
$$
计算响应比优先权的几个时刻
作业完成时、新作业产生时、时间片完成时、进程阻塞。
算法优缺点
如果作业的等待时间相同,则要求服务的时间越短,其优先权越高,类似SJF算法;
如果要求的服务时间相同,优先权则取决于等待时间,类似FCFS算法;
既照顾了短作业,又不致长作业等待过长的时间,长作业的优先权会随着等待时间的增加而提高。
但每次在调度前,都需要先进行响应比的计算,显然会增加系统开销。
例题
作业A、B、C、D、E,分别在0,1,2,3,4时刻到达,需要服务时间分别为4,3,5,2,4,试用高响应比优先调度算法,计算它们的完成时间,周转时间,带权周转时间,平均周转时间,平均带权周转时间。
作业的执行状态:
时间片轮转(RR)
算法特点
根据FCFS的策略,将所有就绪的进程排成一个就绪队列,并设置一定时间间隔,每隔一定时间间隔就发生一次中断,激活系统中的进程调度程序,完成一次调度,将CPU分配给队首进程,若时间间隔到,但原本CPU中的进程未执行完将被转入到就绪队列的队尾,等待下一次调度。
时间片轮转(RR)是抢占式的。
进程切换时机
- 若一个时间尚未用完,正在运行的进程已经完成,就理科激活调度程序,将它从就绪队列中删除,再调度就绪队列中队首的进程运行,并启动一个新的时间片。
- 若一个时间用完,此时正在运行的进程若还未完成,调度程序将把它送往就绪队列的末尾。
算法的优缺点
无法保障系统的实时性,因为任务的执行周期不一定,高优先级的任务无法随时抢占低优先级任务。
时间片过短,会造成频繁的进程调度和进程上下文的切换,增加了系统开销。
时间片过长,有可能会退化为FCFS算法。
但使每个进程都得到公平的分配。
例题
作业A、B、C、D、E,分别在0,1,2,3,4时刻到达,需要服务时间分别为4,3,5,2,4,试用时间片轮转算法,计算它们的完成时间,周转时间,带权周转时间,平均周转时间,平均带权周转时间。
优先级调度算法
优先级的类型
静态优先级
静态优先级是在创建进程的时候确定的,在进程的整个运行期间保持不变。
静态优先级的特点
简单易行,系统开销小,但不够精确,可能会出现优先级低的进程长期没有被调度的情况。
动态优先级
是指在创建进程之初,先赋予一个优先级,然后其值随进程的推进或等待时间的增加而改变。
动态优先级的特点
可以动态改变进程优先级,不会造成进程一直等待,也可以防止一个长作业长期的垄断处理机。
优先级调度算法的类型
非抢占式优先级调度算法
一旦把处理机分配给就绪队列中优先级最高的进程后,该进程遍一直执行下去直至完成,或者因该进程发生某事件而放弃处理机时,系统方可将处理机重新分配给另一个优先级最高的进程。
抢占式优先级调度算法
把处理机分配给优先级最高的进程,使之执行,但在其执行期间,只要出现了另一个其优先级更高的进程,调度程序就将处理机分配给新到的优先级最高的进程。此时称处理机被抢占。
多级反馈队列
算法特点
- 设置多个就绪队列
设置多个就绪队列,第一个队列的优先级最高,第二个次之;而时间片是随着队列的优先级增加而减少,比如第二队列的时间片比第一队列的时间片长一倍。
- 每个队列都采用FCFS算法
当新进程进入内存后,首先将它放入第一队列末尾,按照FCFS原则等待调度。当轮到该进程执行时,若能在第一队列规定的时间片内完成,便撤离系统。否则,调度程序将其转入第二队列的末尾等待调度……。当进程到达第n队列的时候,在第n队列中便采取按RR方式运行。
- 按队列优先级调度
仅当高优先级的队列为空时才会轮到调度次优先级的队列,比如第一队列,如果一直都有进程进来,那么将一直在第一队列,直到第一队列为空才会调度第二队列。当处理机正在第二队列提供服务时,进来一个进程到第一队列,此时正在运行的进程就会被调度到第二队列的末尾,处理机转而去服务刚进来的进程。
整理于2020.4.30