# 进程调度

多个进程同时处于就绪状态时，CPU只能先选一个执行。选择哪一个、让它运行多久，由操作系统的CPU调度决定。进程的状态与PCB见 [进程](/knowledge/cs/operating-systems/process/)；下面只讨论就绪进程之间怎样分配CPU。调度策略直接影响平均等待时间、响应速度和进程之间的公平性：进程集合相同，换一种执行顺序就可能让短进程多等很久，也可能让交互式操作变得迟钝。本页说明调度器在哪些队列之间做选择、四种常见调度算法各自怎样工作，以及用哪些指标比较它们的代价。

## 定义

操作系统的**调度器**决定哪个就绪进程获得CPU，以及获得多久。按能否打断正在运行的进程，调度分为两类：

* **非抢占式调度**：进程一旦获得CPU，就一直运行到结束或主动进入阻塞，中途不会被换下。
* **抢占式调度**：进程可以在运行途中被打断，例如时间片用完，或有更紧迫的进程变为就绪；被打断的进程回到就绪队列等待下一次调度。

一次调度决策通常出现在四种时机：进程从运行转为阻塞、时间片用完或进程被抢占、阻塞的进程转为就绪、进程终止。是否在这些时机立刻切换进程，取决于系统采用抢占式还是非抢占式调度。

## 调度队列

操作系统用不同的队列组织处于不同阶段的进程。

| 队列   | 存放的进程          | 说明               |
| :--- | :------------- | :--------------- |
| 作业队列 | 系统中的所有进程       | 包括尚未装入内存的进程      |
| 就绪队列 | 已装入内存、准备好运行的进程 | 调度器从这里选择下一个运行的进程 |
| 设备队列 | 等待特定I/O设备的进程   | 每个设备可以有一条自己的等待队列 |

作业队列包含尚未装入内存的进程；进程被装入内存后进入就绪队列，运行中请求I/O时转入对应设备的队列，I/O完成后再回到就绪队列。调度器操作的主要是就绪队列。

## 调度算法

### 先来先服务（FCFS）

最简单的调度算法，采用非抢占式策略。CPU按进程请求的顺序分配，像超市排队结账：一旦进程获得CPU，它就一直运行到完成或发生I/O阻塞。

* 优点：算法简单，容易理解和实现；对到达时间相同的进程按先后顺序处理，是公平的。
* 缺点：如果先运行的是一个长进程，后面的短进程都必须等待，平均等待时间变长，CPU和I/O设备的利用率下降，这种现象称为**护航效应**。FCFS也无法保证分时系统需要的响应时间。

### 短作业优先（SJF）

优先调度下一个CPU执行周期最短的进程。CPU执行周期指进程一次连续占用CPU的时间，下文也直接称为CPU执行时间。SJF可以是抢占式的，此时称为最短剩余时间优先；也可以是非抢占式的。

* 优点：在所有进程同时到达的情况下，SJF能给出最小的平均等待时间。
* 缺点：下一个CPU执行周期的长度难以准确预知，通常只能根据历史数据做指数平均预测；如果系统中不断有短进程到来，长进程可能永远得不到执行，形成**饥饿**。

### 轮转调度（RR）

为分时系统设计的抢占式算法。系统定义一个**时间片**，即CPU一次分配给进程连续运行的时间，通常为10–100 ms；就绪队列被视为循环队列，CPU轮流为每个进程服务一个时间片。

* 优点：每个进程都能在有限时间内获得CPU，响应时间短，适合交互式系统；没有进程会连续占用CPU太久。
* 缺点：时间片太短会让上下文切换过于频繁，切换开销吃掉大量CPU时间；时间片长到超过大多数进程的CPU执行时间时，进程在一次时间片内就运行完毕，算法退化为FCFS。

### 优先级调度

为每个进程分配一个优先级，CPU总是分配给优先级最高的进程。优先级可以在创建时静态确定，也可以在运行时动态调整。

* 优点：可以根据任务的重要性、紧迫程度灵活安排执行顺序。
* 缺点：低优先级的进程可能无限期等待，形成饥饿。常用的缓解办法是**老化**：随着等待时间增加，逐步提高进程的优先级。

## 比较

| 算法   | 抢占方式     | 饥饿风险         | 典型场景           |
| :--- | :------- | :----------- | :------------- |
| FCFS | 非抢占      | 一般没有         | 批处理、实现简单的场景    |
| SJF  | 可抢占或非抢占  | 有，长进程可能饥饿    | 执行时间已知或可预测的批处理 |
| RR   | 抢占（按时间片） | 没有           | 分时系统、交互式系统     |
| 优先级  | 可抢占或非抢占  | 有，低优先级进程可能饥饿 | 需要区分任务紧迫程度的系统  |

比较调度算法时，可以按下面的步骤算出一组进程的平均等待时间。

1. **画时间轴**

   按调度顺序标出每个进程实际占用CPU的区间，遇到I/O阻塞时留出空档。

2. **求完成时间**

   记下每个进程最后一次执行结束的时刻，这就是它的完成时间。

3. **算等待时间**

   不计调度开销时，用完成时间减去到达时间、CPU执行时间和阻塞等待时间，得到在就绪队列中等待的总时间。若进程从不阻塞，才可以直接用完成时间减到达时间和CPU执行时间。

4. **比较平均值与极端情况**

   求所有进程等待时间的平均值，同时看最长等待时间和响应时间。平均值小不代表每个进程都及时，交互式系统还要看最坏情况。

> [!NOTE]
> SJF的平均等待时间最优有前提：所有进程同时到达，并且每个进程的CPU执行时间已知。这两个条件在真实系统中通常不成立，所以SJF更多是衡量其他算法的一把尺子，而不是直接照搬的实现。

## 例子

**FCFS与SJF的平均等待时间**

三个进程P1、P2、P3都在0时刻到达，CPU执行时间分别为24、3、3。

按FCFS的顺序P1 → P2 → P3执行：

| 进程 | 等待时间 |
| :- | :--- |
| P1 | 0    |
| P2 | 24   |
| P3 | 27   |
| 平均 | 17   |

按SJF的顺序P2 → P3 → P1执行：

| 进程 | 等待时间 |
| :- | :--- |
| P1 | 6    |
| P2 | 0    |
| P3 | 3    |
| 平均 | 3    |

只改变了执行顺序，平均等待时间就从17降到3。SJF的代价是必须先知道每个进程要执行多久；真实系统只能预测，预测不准时这个最优性就不再成立。

**轮转调度的时间片与响应**

同样三个进程，P1、P2、P3都在0时刻到达，CPU执行时间分别为24、3、3，时间片取4。

| 进程 | 完成时间 | 等待时间  |
| :- | :--- | :---- |
| P1 | 30   | 6     |
| P2 | 7    | 4     |
| P3 | 10   | 7     |
| 平均 | —    | 约5.67 |

P2、P3都只用一个时间片就完成，不必等P1的24个时间单位全部跑完，响应时间比FCFS短；P1则被切成6段执行。时间片取得越小，短进程响应越快，但切换次数和开销也越大；取得越大，行为越接近FCFS。

## 交互探索

比较同一组进程在先来先服务和轮转调度下的执行顺序与等待时间。

交互演示：先来先服务和轮转怎样分配CPU？。比较同一组进程在两种调度策略下的执行顺序与等待时间。 请在站点操作演示。

## 练习

1. FCFS采用哪种调度策略？

   * A.  非抢占，按进程请求CPU的顺序分配
   * B.  抢占，按剩余执行时间分配
   * C.  按优先级高低分配
   * D.  每个进程固定运行一个时间片后轮换

   答案：A

   FCFS是非抢占式的先来先服务：进程按请求顺序获得CPU，一旦开始就运行到完成或主动阻塞。

2. 护航效应描述的是什么现象？

   * A.  长进程先占用CPU，后面的短进程长时间等待，平均等待时间变长
   * B.  短进程不断到达，长进程一直得不到执行
   * C.  时间片太短，上下文切换开销过大
   * D.  低优先级进程被逐渐提高优先级

   答案：A

   护航效应是FCFS的典型问题：一个长进程挡在前面，后面一批短进程只能排队，CPU与I/O设备的利用率也随之下降。短进程导致长进程饥饿是SJF的问题。

3. SJF的平均等待时间最短这一结论，在下列哪个前提下成立？

   * A.  所有进程同时到达，且每个进程的CPU执行时间已知
   * B.  进程按优先级从高到低到达
   * C.  时间片长度固定为10 ms
   * D.  系统中的进程不超过三个

   答案：A

   SJF的最优性建立在“所有进程都在0时刻到达且执行时间已知”之上；真实系统需要预测执行时间，预测误差会让最优性失效。

4. 轮转调度中时间片过短的主要后果是什么？

   * A.  上下文切换频繁，切换开销在总时间中的占比上升
   * B.  长进程永远得不到执行
   * C.  算法退化为FCFS
   * D.  低优先级进程发生饥饿

   答案：A

   时间片越短，单位时间内切换次数越多，保存和恢复现场的开销越大。时间片过长才会退化为FCFS；饥饿是SJF和优先级调度的问题。

5. 优先级调度中引入老化（aging）是为了解决什么问题？

   * A.  低优先级进程长期得不到CPU
   * B.  时间片过短导致切换开销大
   * C.  长进程总是先于短进程运行
   * D.  平均等待时间的计算出现误差

   答案：A

   老化随着等待时间增加逐步提高进程的优先级，使低优先级进程最终也能获得CPU，从而缓解饥饿。

6. 三个进程同时到达，CPU执行时间分别为24、3、3。

   1. 按FCFS调度（P1 → P2 → P3），平均等待时间是 \_\_\_\_\_\_（fcfs-avg）。

      答案：17

      P1等待0，P2等待24，P3等待27，平均为 `(0 + 24 + 27) / 3 = 17`。

   2. 按SJF调度（P2 → P3 → P1），平均等待时间是 \_\_\_\_\_\_（sjf-avg）。

      答案：3

      P2等待0，P3等待3，P1等待6，平均为 `(0 + 3 + 6) / 3 = 3`。