操作系统需要遵循一定的规律去安排进程的运行，既要照顾到每个进程也要安排好它们的优先级。

两种类型的调度器

长期调度器 (Long-term scheduler) 用于决定哪些进程应该进入就绪队列。短期调度器 (Short-term scheduler) 用于决定哪一个处于就绪态的进程需要被移到运行态。

LT-ST

两种类型的调度

之前我们讲进程控制块 (PCB) 的时候，提到它有一个记录调度信息的值。它里面包含了一个进程/线程的优先级信息。利用这个优先级信息，就可以对进程进行抢占式调度了。

抢占式调度 (Preemptive scheduling) 允许高优先级的进程中断正在运行的低优先级进程，而非抢占式调度 (Non-preemptive scheduling) 一旦进程获得 CPU，就会一直运行直到结束或阻塞。

注：英文原文中的 competitive/non-competitive scheduling 在中文技术语境中通常被称为抢占式 (Preemptive) 和非抢占式 (Non-preemptive) 调度。

p-np

调度规则

决定一个进程优先级的因素有很多，操作系统需要参考调度规则 (Scheduling rules) 来给出优先级。下面这些是常见的参考信息。

参数 解释
到达时间 (Arrival Time) 进程到达就绪队列的时间
离开时间 (Departure Time) 进程离开就绪队列的时间（完成或被抢占）
已使用 CPU 时间 (Attained CPU time) 进程在运行态累计的时长
系统内运行时间 (Real time in system) 进程从创建开始在系统里面的总时长（包括等待和运行）

长期调度和短期调度都需要参考这些信息，但是相对来说长期调度的操作频率较低。另外，对于短期调度来说，它的到达时间是从进程被放进就绪队列的时候开始的，也就是下图中 $t_1, t_4$ 这两个时间，而长期调度则是 $t_1$；对于短期调度来说，它的 CPU 时间是该次 CPU 开始运行到结束的时长，这是从 $t_2, t_5$ 开始算起的，而长期调度则是记录所有这些运行时间的总和。不过，不同操作系统的参数和计算方式也是不尽相同的。

frequency-lt-st

批处理任务

批处理任务 (Batch process) 是指那些无需人工干预的进程。计算机会提取需要的数据，然后一个个处理它们再输出。

先进先出算法 (First-In-First-Out algorithm, FIFO)

fifo

这是最简单的调度算法了。先进入就绪队列的进程，被最先执行。在进程 $P_{1}$ 运行到 $t_{1}$ 的时候，进程 $P_{2}$ 进入到了就绪队列，但他需要等到 $t_{2}$，也就是 $P_{1}$ 终止了以后才开始运行。

最短进程优先算法 (Shortest Job Next algorithm, SJN)

sjs

最短进程优先算法 (Shortest Job Next algorithm, SJN，也常称为 Shortest Job First, SJF)，光看名字就知道是什么意思了。系统会对进程所需要的 CPU 时间进行一个估算，然后把需要 CPU 时间最短的进程排在前面。如上图，在 $P_{1}$ 还在运行的时候，$P_{2}$ 和 $P_{3}$ 被放进了就绪队列。当 $P_{1}$ 运行结束的时候，系统会选择能更快结束的 $P_{3}$ 来运行。其次才是较之更长的 $P_{2}$ 运行。

最短剩余时间优先算法 (Shortest Remaining Time First algorithm, SRTF)

srtf

最短剩余时间优先算法 (Shortest Remaining Time First algorithm, SRTF) 是 SJN 的抢占式版本。它会根据进程所需要剩余的时间来决定是否进行调度。上图中，当 $P_{1}$ 执行到 $t_{1}$ 的时候，新进程 $P_{3}$ 被放进了就绪队列。因为 $P_{3}$ 剩余还需要的 CPU 时间比 $P_{1}$ 少，于是 $P_{1}$ 被抢占，$P_{3}$ 被调度到运行状态。当 $P_{3}$ 运行完了以后，就绪队列里面有 $P_{1}$ 和 $P_{2}$ 两个进程。因为 $P_{1}$ 剩下所需要的 CPU 时间比 $P_{2}$ 少，于是 $P_{1}$ 被优先执行。

算法的性能

我们对比一下这些算法的性能。在比较之前我们要了解几个概念：

  1. 周转时间 (Turnaround Time): 进程从提交（进入就绪状态）一直到运行状态结束（完成）的时间。
  2. 平均周转时间 (Average Turnaround Time): 所有进程周转时间的平均数。
  3. 进程饥饿 (Starvation)：一个进程相对于其它进程而言长久的被留在就绪状态，无法获得 CPU 运行，我们称这个现象为进程饥饿。

algorithm_analysis

如上图所示，在就绪队列中有三个进程 $P_{1}, P_{2}, P_{3}$。我们用白色框来表示在就绪队列中等待（延迟）的时间。等待时间加上运行的时间就是周转时间。由此我们可得平均周转时间公式：

$$ATT = \frac{1}{n}\sum_{i=1}^{n} (WaitTime_i + RunTime_i)$$

其中，$WaitTime_i$ 为进程 $i$ 的等待时间，$RunTime_i$ 为进程 $i$ 的运行时间。

如果用 FIFO 算法，$P_{1}$ 无等待，$P_{2}$ 需要等待 3 个单位的时间再执行，$P_{3}$ 需要等待 7 个单位的时间再执行（等待 $P_{1}$ 和 $P_{2}$ 完成）。平均周转时间 (ATT) 是：

$$ATT_{FIFO} = \frac{(0+4) + (3+5) + (7+1)}{3} = \frac{4+8+8}{3} = 6.67$$

依此计算（假设 $P_{1}, P_{2}, P_{3}$ 同时在 $t=0$ 到达，SJN 和 SRTF 才能进行比较），我们找到 SJN 和 SRTF 的平均周转时间：

  • SJN 调度顺序: $P_{3} (1) \to P_{1} (4) \to P_{2} (5)$
    $$ATT_{SJN} = \frac{(0+1) + (1+4) + (5+5)}{3} = \frac{1+5+10}{3} = 5.33$$

  • SRTF 调度: (假设 $P_{1}$ 先运行，$P_{2}, P_{3}$ 随后在很短时间内到达并触发抢占) 实际复杂场景取决于具体到达时间。若按图示 $P_{3}$ 抢占 $P_{1}$ 后又被 $P_{1}$ 抢占的逻辑：
    $$ATT_{SRTF} = \frac{(1+4) + (4+5) + (0+1)}{3} = \frac{5+9+1}{3} = 5.00$$

我们看到在上图这种情况下，SRTF 这种算法是最高效的，因为所有进程从等待到执行再到阻塞或者结束的平均时间是最短的。然而，这并不意味着 SRTF 和 SJN 两种算法一定优于 FIFO。因为我们看到图中 SRTF 和 SJN 都将 $P_{2}$ 延后了。如果系统不断有短进程加入，那么长进程（如 $P_{2}$）可能由于需要的时间比新来的进程都要久，而长久的得不到调度，进程饥饿这种情况就会出现。在最坏的情况下，$P_{2}$ 永远都不会被执行！

交互进程

跟批处理任务不同，交互进程 (Interactive Process) 需要和用户交互。比如说我们经常使用的终端就是一个交互进程。给这些进程调度有不一样的一些算法。

轮转调度算法

现在很多人直接用轮转调度算法的英文名 Round-Robin Scheduling, 更熟悉的叫法：时间片轮转算法，RR 算法，或者 Round-Robin 算法。

我们把时间分成很小的单位，称之为时间片^1 (Time Quantum, 通常是 10-100 毫秒不等)。它会将就绪队列里面的进程，以每个进程运行 1 个单位时间片的方式轮流运行，直到进程结束 (见下图, 注意横坐标单位)。如果在时间片结束时进程未完成，它会被剥夺 CPU 并放回就绪队列末尾。

RR_scheduling

多级队列调度算法

RR 算法将所有的进程都一视同仁了，多级队列调度算法 (Multilevel Queue Scheduling) 在 RR 算法的基础上区分了进程的优先级。

multilevel_scheduling

如上图所示，所有的进程都会根据其属性被分配到一个具有不同优先级的多级队列中（例如，前台交互进程队列，后台批处理队列）。这个算法会先从最高优先级的队列中选择进程开始运行，通常每个队列内部使用 RR 算法。如果在执行的过程中有新的更高优先级的进程进入了高优先级队列，这个算法会抢占当前运行的低优先级进程，跳到那个最高的优先级进程重新向下执行。

多级反馈队列算法

在多级队列调度算法的基础上，多级反馈队列算法 (Multilevel Feedback Queue algorithm, MLFQ) 会动态改变进程的优先级，而且每层的时间片长度通常是不一样的。进程在第 $N$ 层（最高优先级）运行一个时间片后如果没有完成，它会降级到第 $N-1$ 层；在 $N-1$ 层，它能被运行 $2 \times$ 第 $N$ 层运行的时间片长度，之后如果还没完成则再降到下一层中。最低优先级的进程通常拥有最长的时间片（甚至是无限长）以保证所有长进程最终都能跑完。

优先级 时间片配额（示例）
$N$ (最高) 1 个单位
$N-1$ 2 个单位
$N-2$ 4 个单位
$N-3$ 8 个单位
… …
1 (最低) $\infty$ (或极长)

当然，这个算法对运行次数（时间片长度）的增率在不同的操作系统中也是有不同的策略的。由上表可见，多级反馈队列算法对短进程是欢迎的，越短的进程能越快被完成（在高级别队列），而越长的进程会在下一层中给以更多的时间片来完成，减少了频繁调度的开销。

时间片的影响

响应时间 (Response Time) 是一个进程从提交请求到系统开始首次响应所需要的时长。我们敲下的键盘，点击的鼠标都有一个响应时间。时间片的长短严重影响了程序的响应时间。如下图，红色方块表示响应时间。时间片越长，响应时间越长（因为需要等待其他进程运行完其超长的时间片），CPU 时间的使用率（用于上下文切换的开销占比）可能会变高，但对于交互式系统来说体验会变差。

multilevel_scheduling

实时进程

实时进程 (Real-time process) 相比交互进程，需要更严格的时间保证，往往需要一直持续运转。它要达到一定的速度才能够不停的输出。常见的实时进程：流媒体播放器、工业控制程序。想想如果不能够实时的输入和输出，听到的一定是噪音，看到的一定是连环画【笑】。

跟交互进程一样，实时进程需要将时间切割成片段，称之为周期 (Period，一个周期通常是毫秒甚至微秒之间)。

速率单调调度

速率单调算法 (Rate-monotonic algorithm, RM) 是一种静态优先级算法，通过进程的周期来调度进程。在这个算法里面，周期越短（即速率越高）的进程优先权越高。在一个周期之内，某个进程的任务必须要被在该周期内处理掉。

rm_scheduling

如上图，$P_{1}$ 的周期是 4，所需的 CPU 时间是 1；$P_{2}$ 的周期是 5，所需的 CPU 时间是 3。因为 $P_{1}$ 的周期比 $P_{2}$ 短，所以它的优先权更高。速率单调算法会优先选择 $P_{1}$ 执行，在 $P_{1}$ 执行完后，因为还在 $P_{2}$ 的周期内，所以可以选择 $P_{2}$ 运行；很快，因为进入了 $P_{1}$ 的第二次周期（$t=4$），其优先权较高，所以调度算法选择执行 $P_{1}$。依此类推，就是速率单调算法了。

最早截止时间优先调度

就像名字一样，最早截止时间优先调度 (Earliest Deadline First, EDF) 是一种动态优先级算法，会将那些距离截止时间 (Deadline) 最近的进程先执行。在实时系统中，截止时间通常与周期的结束时间一致。

edf_scheduling

如上图，和速率单调中的图一样，$P_{1}$ 的周期是 3（截止时间是 3, 6, 9…），所需的 CPU 时间是 1；$P_{2}$ 的周期是 4（截止时间是 4, 8, 12…），所需的 CPU 时间是 3。

  1. 在 $t=0$，P1 截止时间 3，P2 截止时间 4，P1 更早，先运行 P1。
  2. 在 $t=1$，P1 完成，运行 P2。
  3. 在 $t=3$，新的 P1 周期开始，截止时间变为 6。当前运行的 P2 截止时间仍为 4。因为 P2 的截止时间 (4) 比新 P1 的截止时间 (6) 早，所以 P2 继续运行（不被抢占）。
  4. 在 $t=4$，P2 完成，运行 P1。
    依此类推，就是最早截止时间优先调度了。

算法的性能

对于实时进程来说，最好的状态是所有的进程都能在其周期内完成所需的运算。我们称一个调度是可行 (Feasible) 的，如果所有的进程都能在其周期内完成所需的运算（不发生截止时间错失）。

用进程的总 CPU 时间除以进程的周期，我们可以得到一个 CPU 利用率 (CPU utilization rate)^2

$$U = \sum_{i=1}^{n} \frac{C_{i}}{T_{i}}$$

其中，$i$ 为某一进程，$C_i$ 是它在每个周期内所需的 CPU 时间，$T_i$ 是它的周期。对于 EDF 算法，只要 $U \le 1$，调度就是可行的。对于 RM 算法，可行的充分条件通常要求利用率更低（有一个随 $n$ 增加而略微下降的上限，约 $n(\sqrt[n]{2}-1)$）。

对比 RM 和 EDF

从上面两个图中我们发现，在 EDF 下 $P_{1}$ 和 $P_{2}$ 都在其截止时间前完成了任务，而在 RM 下，由于静态优先级导致 $P_{2}$ 即使更接近截止时间也被 $P_{1}$ 抢占，最终图示显示第一个 $P_{2}$ 在其周期内（$t=5$前）少运行了一个单位的时间（只运行了 2 个单位，需要 3 个）。这意味着 RM 下该任务组可能不可行，而 EDF 是可行的。

综合解决方案

通用的操作系统同时要能够给批处理进程，交互进程，和实时进程调度。所以我们需要一个综合的解决方案。

双层调度

双层调度 (2-tier approach) 将进程分成两组，一组是实时进程，另一组是批处理进程和交互进程。
对于第一组实时进程，赋予极高的优先级。其中优先级高的进程因为速度快，而且短，只要用 FIFO 调度就好了，对于优先级低的实时进程可以使用 RR 保证一定的公平性；而另一组普通的批处理以及交互进程可以用 MLFQ 调度，在没有实时进程需要运行时才会被执行。

2-tier

带变动优先权的双层调度

在双层调度的基础上加上了动态权重调整。除了实时进程的极高优先级保持不变之外，其它类型的进程会一开始被分配一个默认的优先权。在运行过之后，系统会根据进程的行为调整其优先级：那些请求的资源响应越快的进程（通常是 I/O 密集型/交互式进程），优先权会被提高以保证交互体验；一个进程如果是由于需要访问远程计算机的资源（网络 I/O）导致带来了很高需要等待的延迟，那么它的优先权可能会被稍微降低以便让 CPU 先处理其他任务；一个进程如果只和键盘打交道，而键盘的响应速度相对于 CPU 慢但对用户来说需要快，它的优先权就会被提高。