作业调度算法（FCFS，SJF，优先级调度，时间片轮转，多级反馈队列）

阅读数：1103次

2020-04-30

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