操作系统——进程调度笔记

0. 进程上下文切换

进程调度的两个指标：性能和公平。
性能的两个指标：响应时间和周转时间。
T 周转时间 = T 完成时间 −T 到达时间
T 响应时间 = T 首次运行 −T 到达时间

在过去的批处理计算中，开发了一些非抢占式（non-preemptive）调度程序。这样的系统会将每项
工作做完，再考虑是否运行新工作。几乎所有现代化的调度程序都是抢占式的（preemptive），非常愿意
停止一个进程以运行另一个进程。这意味着调度程序采用了我们之前学习的机制。特别是调度程序可以
进行上下文切换，临时停止一个运行进程，并恢复（或启动）另一个进程。
调度程序可以优化性能，但代价是以阻止一些任务运行，这就降低了公平。

1. 先进先出（FIFO:First In First Out）

即先来到的进程先执行。
此种调度算法会有下面的问题：

• 假设最先到来的进程是一个长进程，即执行时间很长。那么此时在该进程之后的进程都需要等待这个长进程执行完毕后才能接着执行，很明显将导致进程的周转时间增加。
  此种方式就好比你去超市买东西，你只买了一点东西，然而在你前面那个人他买了老多东西了，那么你要是想结账就不得不在他后面慢慢等着。因此，考虑这种情况，或许我们会想让我先执行吧，我没买多少东西，瞬间就能结账完毕。基于此，为了不让长进程占用太多的时间，就有了后面的调度算法。

2. 最短任务优先（SJF:Shortest Job First）

先运行最短的任务，然后是次短的任务，如此下去。由于SJF 是一种非抢占式（non-preemptive）调度程序，如果在短程序到达之前，已经有了长程序到达，由于非抢占，故又演变成了上面那种情况，既不得不等上一个任务完成，因此同样存在上述问题。为了解决该问题，同样又衍生出了下面的调度算法。

3. 最短完成时间优先（STCF:Shortest Time-to-Completion First）

向 SJF 添加抢占，称为最短完成时间优先（Shortest Time-to-Completion First，STCF）或抢占式最短作业优先（Preemptive Shortest JobFirst ，PSJF）调度程序。每当新工作进入系统时，它就会确定剩余工作和新工作中，谁的剩余时间最少，然后调度该工作。

4. 轮转（RR:Round-Robin）

RR 在一个时间片（time slice，有时称为调度量子，scheduling quantum）内运行一个工作，然后切换到运行队列中的下一个任务，而不是运行一个任务直到结束。它反复执行，直到所有任务完成。因此，RR 有时被称为时间切片（time-slicing）。时间片长度对于 RR 是至关重要的。越短，RR 在响应时间上表现越好。然而，时间片太短是有问题的：突然上下文切换的成本将影响整体性能。因此，系统设计者需要权衡时间片的长度，使其足够长，以便摊销（amortize）上下文切换成本，而又不会使系统不及时响应。

当系统某些操作有固定成本时，通常会使用摊销技术（amortization）。通过减少成本的频度（即执行较少次的操作），系统的总成本就会降低。例如，如果时间片设置为 10ms，并且上下文切换时间为 1ms，那么浪费大约 10%的时间用于上下文切换。如果要摊销这个成本，可以把时间片增加到 100ms。在这种情况下，不到 1%的时间用于上下文切换，因此时间片带来的成本就被摊销了。

请注意，上下文切换的成本不仅仅来自保存和恢复少量寄存器的操作系统操作。程序运行时，它们在 CPU 高要缓存、TLB、分支预测器和其他片上硬件中建立了大量的状态。切换到另一个工作会导致此状态被刷新，且与当前运行的作业相关的新状态被引入，这可能导致显著的性能成本。

更一般地说，任何公平（fair）的政策（如 RR），即在小规模的时间内将 CPU 均匀分配到活动进程之间，在周转时间这类指标上表现不佳。事实上，这是固有的权衡：如果你愿意不公平，你可以运行较短的工作直到完成，但是要以响应时间为代价。如果你重视公平性，则响应时间会较短，但会以周转时间为代价。这种权衡在系统中很常见。你不能既拥有你的蛋糕，又吃它 。

如有可能，重叠（overlap）操作可以最大限度地提高系统的利用率。重叠在许多不同的领域很有用，包括执行磁盘 I/O 或将消息发送到远程机器时。在任何一种情况下，开始操作然后切换到其他工作都是一个好主意，这也提高了系统的整体利用率和效率。

5. 多级反馈队列（MLFQ:Multi-level Feedback Queue）

多级反馈队列需要解决两方面的问题。首先，它要优化周转时间。在第 7 章中我们看到，这通过先执行短工作来实现。然而，操作系统通常不知道工作要运行多久，而这又是SJF（或 STCF）等算法所必需的。

轮转这样的算法虽然降低了响应时间，周转时间却很差。

5.1 MLFQ：基本规则

MLFQ结构

• MLFQ 中有许多独立的队列（queue），每个队列有不同的优先级（priority level）。任何时刻，一个工作只能存在于一个队列中。MLFQ 总是优先执行较高优先级的工作（即在较高级队列中的工作）。
• 每个队列中可能会有多个工作，因此具有同样的优先级。在这种情况下，我们就对这些工作采用轮转调度。

因此，MLFQ 调度策略的关键在于如何设置优先级。MLFQ 没有为每个工作指定不变的优先情绪而已，而是根据观察到的行为调整它的优先级。

MLFQ规则

• 规则 1：如果 A 的优先级 > B 的优先级，运行 A（不运行 B）。
• 规则 2：如果 A 的优先级 = B 的优先级，轮转运行A 和 B。

公平吗？C,D运行不了怎么办？

5.2 改变优先级

在一个工作的生命周期中，MLFQ 如何改变其优先级（在哪个队列中）。要做到这一点，我们必须记得工作负载：既有运行时间很短、频繁放弃 CPU 的交互型工作，也有需要很多 CPU 时间、响应时间却不重要的长时间计算密集型工作。

优先级调整算法

• 规则 3：工作进入系统时，放在最高优先级（最上层队列）。
• 规则 4a：工作用完整个时间片后，降低其优先级（移入下一个队列）。
• 规则 4b：如果工作在其时间片以内主动释放 CPU，则优先级不变。

这个算法的一个主要目标：如果不知道工作是短工作还是长工作，那么就在开始的时候假设其是短工作，并赋予最高优先级。如果确实是短工作，则很快会执行完毕，否则将被慢慢移入低优先级队列，而这时该工作也被认为是长工作了。通过这种方式，MLFQ 近似于 SJF。

一个有 I/O 的例子。根据上述规则 4b，如果进程在时间片用完之前主动放弃 CPU，则保持它的优先级不变。这条规则的意图很简单：假设交互型工作中有大量的 I/O 操作（比如等待用户的键盘或鼠标输入），它会在时间片用完之前放弃 CPU。在这种情况下，我们不想处罚它，只是保持它的优先级不变。

图 8.4 展示了这个运行过程，交互型工作 B（用灰色表示）每执行 1ms 便需要进行 I/O操作，它与长时间运行的工作 A（用黑色表示）竞争 CPU。MLFQ 算法保持 B 在最高优先级，因为 B 总是让出 CPU。如果 B 是交互型工作，MLFQ 就进一步实现了它的目标，让交互型工作快速运行。

MLFQ还有啥缺点呢？

• 首先，会有饥饿（starvation）问题。如果系统有“太多”交互型工作，就会不断占用CPU，导致长工作永远无法得到 CPU（它们饿死了）。
• 其次，聪明的用户会重写程序，愚弄调度程序（game the scheduler）。愚弄调度程序指的是用一些卑鄙的手段欺骗调度程序，让它给你远超公平的资源。

5.3 提升优先级

要让 CPU 密集型工作也能取得一些进展（即使不多），一个简单的思路是周期性地提升（boost）所有工作的优先级。可以有很多方法做到，但我们就用最简单的：将所有工作扔到最高优先级队列。

规则

• 规则 5：经过一段时间 S，就将系统中所有工作重新加入最高优先级队列。

S的值如何设置？

5.4 更好的计时方式

现在还有一个问题要解决：如何阻止调度程序被愚弄？可以看出，这里的元凶是规则4a 和 4b，导致工作在时间片以内释放 CPU，就保留它的优先级。那么应该怎么做？这里的解决方案，是为 MLFQ 的每层队列提供更完善的 CPU 计时方式（accounting）。调度程序应该记录一个进程在某一层中消耗的总时间，而不是在调度时重新计时。只要进程用完了自己的配额，就将它降到低一优 先级的队列中去。不论它是一次用完的，还是拆成很多次用完。因此，我们重写规则 4a 和 4b。

• 规则 4：一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU），就降低其优先级（移入低一级队列）。

5.5 调优及其他问题

关于 MLFQ 调度算法还有一些问题。其中一个大问题是如何配置一个调度程序，例如，配置多少队列？每一层队列的时间片配置多大？为了避免饥饿问题以及进程行为改变，应该多久提升一次进程的优先级？这些问题都没有显而易见的答案，因此只有利用对工作负载的经验，以及后续对调度程序的调优，才会导致令人满意的平衡。

为了方便查阅，我们重新列在这里。

• 规则 1：如果 A 的优先级 > B 的优先级，运行 A（不运行 B）。
• 规则 2：如果 A 的优先级 = B 的优先级，轮转运行 A 和 B。
• 规则 3：工作进入系统时，放在最高优先级（最上层队列）。
• 规则 4：一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU），就降低其优先级（移入低一级队列）。
• 规则 5：经过一段时间 S，就将系统中所有工作重新加入最高优先级队列。

MLFQ 有趣的原因是：它不需要对工作的运行方式有先验知识，而是通过观察工作的运行来给出对应的优先级。通过这种方式，MLFQ 可以同时满足各种工作的需求：对于短时间运行的交互型工作，获得类似于 SJF/STCF 的很好的全局性能，同时对长时间运行的CPU 密集型负载也可以公平地、不断地稳步向前。因此，许多系统使用某种类型的 MLFQ作为自己的基础调度程序。

参考书籍：操作系统导论书籍