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

> 本文由 [简悦 SimpRead](http://ksria.com/simpread/) 转码， 原文地址 [waiterxiaoyy.github.io](https://waiterxiaoyy.github.io/2020/04/30/%E4%BD%9C%E4%B8%9A%E8%B0%83%E5%BA%A6%E7%AE%97%E6%B3%95%EF%BC%88FCFS%EF%BC%8CSJF%EF%BC%8C%E4%BC%98%E5%85%88%E7%BA%A7%E8%B0%83%E5%BA%A6%EF%BC%8C%E6%97%B6%E9%97%B4%E7%89%87%E8%BD%AE%E8%BD%AC%EF%BC%8C%E5%A4%9A%E7%BA%A7%E5%8F%8D%E9%A6%88%E9%98%9F%E5%88%97%EF%BC%89/)

### [](#作业调度 "作业调度")作业调度

#### [](#1-作业调度的主要任务 "1. 作业调度的主要任务")1. 作业调度的主要任务

根据 JCB 中的信息，检查系统中的资源能否满足作业对资源的需求，以及**按照一定的调度算法**，从外存的**后备队列**中选取某些作业调入内存，并为它们创建进程、分配必要的资源。

#### [](#2-作业运行的三个阶段和三个状态 "2. 作业运行的三个阶段和三个状态")2. 作业运行的三个阶段和三个状态

*   **收容阶段：**

操作员把用户提交的作业通过某种方式或 SPOOLiing 系统输入到硬盘上，再为该作业建立 JCB ，并把它放入都作业**后备队列**中。此时作业状态为 **后备状态** 。

*   **运行阶段：**

当作业被作业调度选中后，便为它分配必要的资源和建立进程，并把它放入**就绪队列**。此时作业的状态为就绪状态，但作业可能多次在就绪状态和运行状态之间转换，所以，在一个作业从第一次进入就绪状态开始，直到运行结束，此期间的作业状态为 **运行状态**。

*   **完成阶段**

当作业运行完成、或发生异常情况而提前结束时，作业便进入完成阶段，系统中的 “终止作业” 程序将会回收已分配给该作业的作业控制块和所有资源。此时作业的状态为 **完成状态**。

#### [](#3-作业调度常用的算法 "3. 作业调度常用的算法")3. 作业调度常用的算法

先来先服务（FCFS）、短作业优先（SJF）、优秀级调度算法（PSA）、高响应比优先调度算法（HRRN）、时间片轮转（RR）、多级反馈队列算法。

### [](#几种时间的概念 "几种时间的概念")几种时间的概念

**到达时间：**作业来到的时刻

**服务时间：**作业占用 CPU 的时间

**完成时间：**作业执行完的时刻

**周转时间：**完成时间 - 到达时间

**带权周转时间：**周转时间 / 服务时间

**平均周转时间：**周转时间 / 作业个数

**平均带权周转时间：**带权周转时间 / 作业个数

### [](#先来先服务（FCFS "先来先服务（FCFS)")先来先服务（FCFS)

#### [](#算法特点 "算法特点")算法特点

*   按照作业提交或变为后备状态的先后次序分配 CPU
*   新作业只有当当前的作业执行完成或者阻塞才能获得 CPU
*   被唤醒的作业不会立即恢复执行，默认是非抢占式，通常要等到当前的作业让出 CPU

#### [](#算法的优缺点 "算法的优缺点")算法的优缺点

有利于 CPU 繁忙型的作业，不利于 I/O 繁忙的作业，如果后备队列中作业过多，新加入的作业等待的时间会很长。

一般 FCFS 算法在单处理机中已很少作为主调度算法，但经常把它与其他调度算法相结合使用，形成一种更为有效的调度算法。

**例题:**

作业 A、B、C、D、E，分别在 0，1，2，3，4 时刻到达，需要服务时间分别为 4，3，5，2，4，试用**先来先服务**算法，计算它们的完成时间，周转时间，带权周转时间，平均周转时间，平均带权周转时间。

![](https://note.youdao.com/yws/api/personal/file/WEB0d52da2f6daf1f5cfe1df89fbfe5ee51?method=download&shareKey=c43ac6aad1b460ff772dff8926b968e4)

作业的执行状态：

![](https://note.youdao.com/yws/api/personal/file/WEB940ceb65f08f0ca3751769c0b4b36045?method=download&shareKey=c3a0067240848d201d31df474a58d25d)

### [](#短作业优先（SJF） "短作业优先（SJF）")短作业优先（SJF）

#### [](#算法特点-1 "算法特点")算法特点

*   按照作业的长短来计算优先级，作业越短，其优先级越高
*   作业长度是按照作业所需要占用的 CPU 时间来衡量的
*   属于非抢占式，只有当当前的作业释放出 CPU，新作业才可能获得 CPU

#### [](#算法的优缺点-1 "算法的优缺点")算法的优缺点

SJF 算法对短作业有利，能有效的降低作业的平均等待时间，提高系统的吞吐量。

但未考虑作业的紧迫程度，因而不能保证紧迫性作业的及时处理；

还必须预知作业的运行时间，作业的运行时间需要进行估计，如果估计过低，作业未完成就会提前终止，所以一般都会偏长估计；

对长作业非常不利，长作业的周转时间明显偏长。

完全忽略作业的等待时间，可能使作业等待时间过长，出现饥饿现象；

人机无法交互。

**例题**

作业 A、B、C、D、E，分别在 0，1，2，3，4 时刻到达，需要服务时间分别为 4，3，5，2，4，试用**短作业优先**算法，计算它们的完成时间，周转时间，带权周转时间，平均周转时间，平均带权周转时间。

![](https://note.youdao.com/yws/api/personal/file/WEB5f636a237153aa4ce527f39604ed2cc2?method=download&shareKey=3a0ccd4ac253581887c161b2e4f15e0a)

作业的执行状态：

![](https://note.youdao.com/yws/api/personal/file/WEBaf5324832f5baa223c4cb92092bc5433?method=download&shareKey=8ddef30b8bfd304d0fd19f6c0ee6472d)

### [](#高响应比优先调度算法（HRRN） "高响应比优先调度算法（HRRN）")高响应比优先调度算法（HRRN）

#### [](#算法特点-2 "算法特点")算法特点

*   高响应比调度算法既考虑了作业的等待时间，又考虑作业运行时间。因此既照顾了短作业，又不致长作业的等待时间过长。
*   为每个作业引入动态优先权，使作业的优先级随着等待时间的增加而以提高

##### [](#优先权的动态规律 "优先权的动态规律")优先权的动态规律

$$  
优先权 = \frac{等待时间 + 要求服务时间}{要求服务时间}=\frac{响应时间}{要求服务时间}  
$$

##### [](#计算响应比优先权的几个时刻 "计算响应比优先权的几个时刻")计算响应比优先权的几个时刻

作业完成时、新作业产生时、时间片完成时、进程阻塞。

#### [](#算法优缺点 "算法优缺点")算法优缺点

如果作业的等待时间相同，则要求服务的时间越短，其优先权越高，类似 SJF 算法；

如果要求的服务时间相同，优先权则取决于等待时间，类似 FCFS 算法；

既照顾了短作业，又不致长作业等待过长的时间，长作业的优先权会随着等待时间的增加而提高。

但每次在调度前，都需要先进行响应比的计算，显然会增加系统开销。

**例题**

作业 A、B、C、D、E，分别在 0，1，2，3，4 时刻到达，需要服务时间分别为 4，3，5，2，4，试用**高响应比优先调度**算法，计算它们的完成时间，周转时间，带权周转时间，平均周转时间，平均带权周转时间。

![](https://note.youdao.com/yws/api/personal/file/WEB0096d32874fa40b2da34a1c639559fc6?method=download&shareKey=7e84002cf6bc66cd113c795c4a92ccb8)

作业的执行状态：

![](https://note.youdao.com/yws/api/personal/file/WEB0fd6271a21696c3002584a5328710741?method=download&shareKey=868a89ab72ab6338b8d6b56197f2f06b)

### [](#时间片轮转（RR） "时间片轮转（RR）")时间片轮转（RR）

#### [](#算法特点-3 "算法特点")算法特点

根据 FCFS 的策略，将所有就绪的进程排成一个就绪队列，并设置一定时间间隔，每隔一定时间间隔就发生一次中断，激活系统中的进程调度程序，完成一次调度，将 CPU 分配给队首进程，若时间间隔到，但原本 CPU 中的进程未执行完将被转入到就绪队列的队尾，等待下一次调度。

时间片轮转（RR）是抢占式的。

##### [](#进程切换时机 "进程切换时机")进程切换时机

*   若一个时间尚未用完，正在运行的进程已经完成，就理科激活调度程序，将它从就绪队列中删除，再调度就绪队列中队首的进程运行，并启动一个新的时间片。
*   若一个时间用完，此时正在运行的进程若还未完成，调度程序将把它送往就绪队列的末尾。

#### [](#算法的优缺点-2 "算法的优缺点")算法的优缺点

无法保障系统的实时性，因为任务的执行周期不一定，高优先级的任务无法随时抢占低优先级任务。

时间片过短，会造成频繁的进程调度和进程上下文的切换，增加了系统开销。

时间片过长，有可能会退化为 FCFS 算法。

但使每个进程都得到公平的分配。

**例题**

作业 A、B、C、D、E，分别在 0，1，2，3，4 时刻到达，需要服务时间分别为 4，3，5，2，4，试用**时间片轮转**算法，计算它们的完成时间，周转时间，带权周转时间，平均周转时间，平均带权周转时间。

![](https://note.youdao.com/yws/api/personal/file/WEB8687bb97fa81c82a449fed682baeda85?method=download&shareKey=7f048d6d865efe557d030d220c060da7)

![](https://note.youdao.com/yws/api/personal/file/WEBbd898b95b1dae550f01aa06b20158027?method=download&shareKey=27cb91d400276e10939931461ceda795)

### [](#优先级调度算法 "优先级调度算法")优先级调度算法

#### [](#优先级的类型 "优先级的类型")优先级的类型

##### [](#静态优先级 "静态优先级")静态优先级

静态优先级是在创建进程的时候确定的，在进程的整个运行期间保持不变。

##### [](#静态优先级的特点 "静态优先级的特点")静态优先级的特点

简单易行，系统开销小，但不够精确，可能会出现优先级低的进程长期没有被调度的情况。

##### [](#动态优先级 "动态优先级")动态优先级

是指在创建进程之初，先赋予一个优先级，然后其值随进程的推进或等待时间的增加而改变。

##### [](#动态优先级的特点 "动态优先级的特点")动态优先级的特点

可以动态改变进程优先级，不会造成进程一直等待，也可以防止一个长作业长期的垄断处理机。

#### [](#优先级调度算法的类型 "优先级调度算法的类型")优先级调度算法的类型

##### [](#非抢占式优先级调度算法 "非抢占式优先级调度算法")非抢占式优先级调度算法

一旦把处理机分配给就绪队列中优先级最高的进程后，该进程遍一直执行下去直至完成，或者因该进程发生某事件而放弃处理机时，系统方可将处理机重新分配给另一个优先级最高的进程。

##### [](#抢占式优先级调度算法 "抢占式优先级调度算法")抢占式优先级调度算法

把处理机分配给优先级最高的进程，使之执行，但在其执行期间，只要出现了另一个其优先级更高的进程，调度程序就将处理机分配给新到的优先级最高的进程。此时称处理机被抢占。

### [](#多级反馈队列 "多级反馈队列")多级反馈队列

#### [](#算法特点-4 "算法特点")算法特点

*   设置多个就绪队列

设置多个就绪队列，第一个队列的优先级最高，第二个次之；而时间片是随着队列的优先级增加而减少，比如第二队列的时间片比第一队列的时间片长一倍。

*   每个队列都采用 FCFS 算法

当新进程进入内存后，首先将它放入第一队列末尾，按照 FCFS 原则等待调度。当轮到该进程执行时，若能在第一队列规定的时间片内完成，便撤离系统。否则，调度程序将其转入第二队列的末尾等待调度……。**当进程到达第 n 队列的时候，在第 n 队列中便采取按 RR 方式运行。**

*   按队列优先级调度

仅当高优先级的队列为空时才会轮到调度次优先级的队列，比如第一队列，如果一直都有进程进来，那么将一直在第一队列，直到第一队列为空才会调度第二队列。当处理机正在第二队列提供服务时，进来一个进程到第一队列，此时正在运行的进程就会被调度到第二队列的末尾，处理机转而去服务刚进来的进程。

整理于 2020.4.30