4. 进程调度策略

本节将阐述实现 CPU 虚拟化的机制。

关键问题：如何开发调度策略？

讲述方法如下：运行中的进程可以统称为 工作负载（Workload），我们首先将对工作负载提出一系列理想化的假设，讨论理想情况下的最优策略，随后逐步去掉这些假设，讨论现实情况中的调度算法。

工作负载假设与衡量指标

我们最初提出的对工作负载的假设如下：

  1. 每个工作运行相同的时间。
  1. 所有工作同时到达。
  1. 工作一旦开始，将持续执行直到结束，中间不可被打断。
  1. 所有工作只需要 CPU。
  1. 每个工作的运行时间已知。

为了衡量调度算法的性能，我们需要提出一些指标。其中有三个重要指标：周转时间（Turnaround Time），指任务完成的时间减去任务到达系统的时间；响应时间（Response Time），指任务首次开始运行的时间减去任务到达系统的时间；公平，指在一定时间内资源被多平均地分配到每个任务上。显然，周转时间与响应时间是一种 性能 指标，分别指示了所有任务能被多快完成，与系统的交互性如何。

性能与公平

在任何调度系统中，性能与公平总是矛盾的，开发调度算法时必须在两者之间做折中。追求性能就意味着先全力完成一项任务，而让所有任务等候；追求公平就意味着所有任务几乎被同时完成，且各自用时都远远大于单独运行时的用时。

Step 1. 先进先出（FIFO）调度

我们最先能够想到的基本算法就是 先进先出（First In First Out，FIFO） 调度。它简单且易于实现。

Step 2. 最短任务优先（SJF）调度

我们去掉第一条假设，FIFO 的缺点立刻暴露出来：当一个耗时较长的任务先于一些耗时很短的任务到达时，即使这个时差十分小，所有短任务也必须等待长任务完成才能开始执行，大大增加了这些短任务的周转时间与响应时间，这被称作 护航效应（Convoy Effect）。

该问题的解决方法很简单：我们采用名为 最短任务优先（Shortest Job First，SJF） 的调度策略。当短任务与长任务几乎同时到达时，先运行最短的任务。可以证明，在当前的假设下 SJF 策略具有最优的平均周转时间。

Step 3. 最短完成时间优先（STCF）调度

我们继续去掉第二条假设。SJF 的缺点也显而易见：当一个耗时较长的任务先于一些耗时很短的任务到达时（这次有一定时差），我们又遇到了护航效应的问题。

在当前的假设下我们所采取的调度策略都是一种 非抢占式（Non-preemptive）调度，然而我们已经实现了上下文切换。这允许我们去掉第三条假设，向 SJF 添加抢占机制，得到 最短完成时间优先（Shortest Time-To-Completion FIrst，STCF） 调度策略，又称 抢占式最短作业优先（Preemptive Shortest Job First，PSJF） 调度策略。其含义是：每当有一个新工作到达系统时，调度程序判断当前工作的剩余部分与新工作相比，哪个耗时更少，并调度耗时少的程序使用资源。可以证明，在当前的假设下 STCF 策略具有最优的平均周转时间。

Step 4. 轮转调度

仅使用周转时间为指标衡量，STCF 是一个十分高效的调度策略，然而如果将响应时间也纳入考量，STCF 存在严重的响应时间问题。

轮转（Round-Robin） 调度具有优良的平均响应时间。其基本思路为：将时间划分为大量 时间片（Time Slice），在一个时间片内运行一个工作，下一个时间片运行另一项工作，以此类推，每个工作周期性获得一个时间片进行工作，直到所有任务完成。在实现时，显然时间片的长度必须为时钟中断周期的整数倍。如何选择时间片长度决定了轮转调度的效率：过长则工作的平均响应时间增大，导致系统响应速度减慢；过短则上下文切换的开销（例如保存与恢复寄存器、刷新在 CPU 高速缓存、分支预测器等硬件上的状态的成本）占整个轮转过程的份额过大，难以摊销（Amortize）。

轮转不仅具有良好的平均响应时间，其也是一个 公平 的的调度策略。但正如 前文 所述，轮转策略具有很差的平均周转时间，甚至可能差于 FIFO。

Step 5. I/O 操作

接下来我们去掉第四条假设。此时进程会进行如发出 I/O 请求等系统调用，在这段时间进程本身会被阻塞，不再使用 CPU。显然这些空闲时间可以被利用起来运行其它程序。

在这种情况下，我们可以以系统中断为分界将工作划分为多个子工作再套用 STCF 或其它调度策略。子工作在进行系统调用时即视作完成，从系统调用中恢复时视作新的子任务到达。这时调度程序会将每个子程序视作独立的工作进行调度，同时实现了 重叠（Overlap） 操作，提高了资源的利用率。

Step 6. 多级反馈队列（MLFQ）调度

接下来我们去掉第五条假设，进入通用操作系统面临的现实状况：其没有任何关于工作长度的先验（priori）知识，而无论是 SJF 与 STCF 都需要关于工作长度的知识才能正确进行调度。这个问题至今并没有一个理论最优的解决方法。

关键问题：如何在没有关于工作的先验知识的情况下进行调度？

本小节介绍目前广泛用于各种操作系统中的解决方法：多级反馈队列（Multi-level Feedback Queue，MLFQ）。MLFQ 希望能够同时提供虽然不是最优但优良的平均周转时间与平均响应时间。

多级反馈队列是利用历史经验预测未来的一个典型例子，操作系统乃至整个计算机科学都广泛运用了这样的思想。

MLFQ 的基本思路如下：维护多个独立的队列，每个队列具有不同的 优先级。每个工作无论何时都只能存在于一个队列中。MLFQ 先使用轮转调度执行优先级高的队列内的工作，再执行优先级低的队列的工作。即如下两条基本规则：

  1. 若工作 A 的优先级高于工作 B 的优先级，运行 A。
  2. 若工作 A 的优先级与工作 B 的优先级相同，轮转运行 A 与 B。

显然，如何设置优先级是 MLFQ 调度策略的关键。为了同时兼顾响应时间，以频繁执行系统调用为特征的交互型工作应当获得一个较高的优先级，而长时间占用 CPU 的计算密集工作优先级级较低。一个工作的行为特征并非一成不变，因此 MLFQ 需要根据观察到的行为调整优先级。因此我们考虑新增如下的规则：
3. 工作初次到达系统时总是处于最高优先级。

当前引入的新规则效果似乎不错。当一个任务到来时，我们假设其是短工作并赋予最高优先级。如果其确实是短工作，则它很快就会执行完毕；否则，其优先级会逐渐降低，工作也被认为是长工作了。对于带有大量 I/O 操作的交互型程序，由于其总是没用完一个时间片就主动放弃了 CPU，其优先级不会发生改变，仍然会保持高优先级执行。

然而，我们的算法并非完美，存在一些致命问题，考虑如下极端情况：

第一个类型很好解决，我们不应在程序发生系统调用后就重新计时，而应记录某个程序在某一优先级上消耗的总时间，因此有规则：
4. 一旦工作用完了某一优先级的配额，就降低其优先级，无论中间工作主动放弃了多少次 CPU。

后两种类型的解决方法是一致的：定期提升所有工作的优先级。这样长工作不会饿死，交互性程序也会在回归高优先级后被正确对待。因此我们有规则：
5. 每经过一段时间 S，就将系统中的所有工作重新加入最高优先级队列。

与上面的时间片的长度一样，此处的 S 也面临一个权衡：设置得太高，长工作会饿死；太低，长工作反复获得高优先级会挤占交互型工作的资源份额。类似的，关于 MLFQ，应配置多少队列，每一层队列的时间片配置为多大，这些都是配置调度程序时需要考虑的重要问题。

大多数 MLFQ 的实现都允许为不同队列设置可变的时间片长度，随优先级升高时间片长度一般会减少；其它的一些 MLFQ 实现使用其它规则（如数学公式）调整优先级；有些调度程序会将最高优先级预留给操作系统使用；还有一些系统允许用户给出优先级设置的建议，例如通过 nice 就可以设置程序运行的优先级。

多用建议

操作系统并不总是知道什么策略对进程与整个系统是最好的，因为它只能按照设定的程序运行，而人类可以观察并知道在某些特定情况下应采用哪种策略。因此操作系统提供了一些接口与工具来接受人类给出的建议。例如 nice 影响调度策略，madvise 影响内存管理。

总结一下 MLFQ 的机制：

  1. 若工作 A 的优先级高于工作 B 的优先级，运行 A。
  2. 若工作 A 的优先级与工作 B 的优先级相同，轮转运行 A 与 B。
  3. 工作初次到达系统时总是处于最高优先级。
  4. 一旦工作用完了某一优先级的配额，就降低其优先级，无论中间工作主动放弃了多少次 CPU。
  5. 每经过一段时间 S，就将系统中的所有工作重新加入最高优先级队列。

Step 6.1. 比例份额调度

本小节所介绍的内容并没有被现代工业界广泛使用。

本小节将简要介绍 比例份额（Proportional Share）调度程序，又称 公平份额（Fair Share）调度程序。其基于一个简单的想法：调度程序的最终目的是确保每个工作获得一定比例的 CPU 时间，而非优化周转时间与响应时间。它的基本规则很简单：每当决定接下来调度哪个程序时举行一次“抽奖”，越应被频繁执行的程序中奖概率越大，最终中奖的程序执行一段时间，然后进行下一次“抽奖”。因此，中奖概率就代表了进程占有某个资源的份额，而调度策略就是让每个程序从概率上获得这种份额比例，因此这种策略具有随机性，并不能确保资源实际分配的比例符合期望，但随着运行时间变长，最终的结果就会逐渐趋向于期望值。

这种基于随机化的调度策略被称作 彩票调度。彩票调度还有许多机制，例如 彩票货币：获得彩票的用户可以发行自己的货币给每个工作，操作系统在调度这些工作时将货币换算回实际的彩票；彩票转让：一个程序可以临时将自己的彩票交给另一个进程，以此加速另一个进程的执行。彩票通胀：在信任环境中，一个进程可以临时提升或减少自己拥有的彩票数量因此影响所有程序最终获得的 CPU 运行份额。

然而，彩票调度拥有一个致命的问题：调度程序的运行严重依赖于彩票的分配策略，而后者至今没有一个理想的答案（要知道通用的操作系统是没有关于工作的任何先验信息的！）。

彩票分配是一个基于随机的算法，具有不确定性，尤其是在运行时间很短的情况下很可能产生不理想的比例。因此提出了 步长调度（Stride Scheduling）策略，这是一种确定性的公平算法。思路如下：系统中的每个工作都有一个 步长，其反比于工作拥有的彩票数；每次工作选择当前行程值最小的进程运行一个时间片，随后该工作的行程值增加一个步长。

可以证明，步长调度算法可以在每个调度周期中满足每个程序按照票数比例获得对应的 CPU 时间份额。

步长调度算法虽然具有确定性，但其与彩票调度算法相比的问题在于：

此外，无论是彩票调度还是步长调度都存在共同的问题：