进程调度

现在，运行进程的底层机制应该清楚了。然而，我们还不知道操作系统调度程序采用的上层策略。

事实上，调度的起源早于计算机系统。早期调度策略取自于操作管理领域，并应用于计算机。对于这个事实不必惊讶：装配线以及许多人类活动都需要调度，而且许多关注点是一样的，包括像激光一样对效率的渴望。

工作负载假设

探讨可能的策略范围之前，我们先做一些假设。这些假设与系统中运行的进程有关，有时候统称为工作负载。确定工作负载是构建调度策略的关键部分。工作负载了解的越多，你的策略就越优化。

我们这里做的工作负载的假设是不切实际的，但目前这不算问题，因为我们将来会放宽这些假设，并最终开发出我们所谓的——一个完全可操作的调度准则。

我们对操作系统中运行的进程做出如下假设：

• 每个工作运行相同的时间。
• 所有的工作同时到达。
• 一旦开始，每个工作保持运行直到完成。
• 所有的工作只使用 CPU，不执行 IO 操作。
• 每个工作的运行时间是已知的。

调度指标

除了做出工作负载假设，还需要一个东西能让我们比较不同的调度策略：调度指标。指标是我们衡量某些东西标准，在调度进程中，一些不同的指标是有意义的。

现在让我们简化一下，只用一个指标：周转时间。任务的周转时间定义为任务完成时间减去任务到达系统的时间，即：周转时间 = 完成时间 - 到达时间。

因为我们假设所有的任务都在同一时间到达，那么 到达时间=0，因此 周转时间=完成时间。随着我们放宽上述假设，该情况将会改变。

你应该注意到，周转时间是一个性能指标，这将是本章的首要关注点。另一个有趣的指标是公平，比如 Jian’s Fariness Index。性能和公平在调度系统中往往是矛盾的。比如，调度程序可以优化性能，但代价是阻止一些任务的执行，这也就降低了公平性。

先进先出

我们可以实现的最基本的算法为 FIFO，或称为先到先服务(FCFS)。FIFO 有一些积极的特性：它很简单，而且易于实现。而且，对于我们的假设，它的效果很好。

我们一起看一个简单的例子。想象一下，3 个工作 A、B、C 在大致相同的时间到达系统。因为 FIFO 必须将某个工作放在前面，所以我们假设当它们都同时到达时，A 比 B 早一点点，然后 B 比 C 早一点点。假设每个工作运行 10 秒。这些工作的平均周转周期是多少？

从上图可以看出，A 在 10s 时完成，B 在 20s 时完成，C 在 30s 时完成。因此这 3 个任务的平均周转时间就是 (10+20+30)/3=20。

现在让我们放宽假设 1，因此不再认为所有任务的运行时间是相同的。FIFO 表现如何？你可以构建什么样的工作负载来让 FIFO 表现的不好？

这次我们假设 3 个任务，A 运行 100s，B 和 C 都运行 10s。

如上图，A 先运行 100s，B 或 C 才有机会运行。因此，系统的平均周转时间是比较高的，达到 110s。

该问题通常被称为护航效应，一些耗时较少的潜在资源消费者被排在重量级的资源消费者之后。

提示：SJF 原则 最短任务优先代表一个总体调度原则，可以应用于所有系统，只要其中平均客户周转时间很重要。

最短任务优先

实际上这是才从运筹学中借鉴的一个想法，然后应用到计算机系统的任务调度中。这个新的调度准则被称为最短任务优先：先运行最短的任务，然后是次短的任务，以此类推。

我们用上面的例子，但以 SJF作为调度策略。下图展示的是三个任务的执行情况。它清除的表明了为什么在考虑平均周转时间的情况下，SJF 的表现会更好。这里的平均周转时间降到了 50s。

事实上，考虑到所有工作同时到达的假设，我们可以证明 SJF 确实是一个最优的调度算法。

补充：抢占式调度程序 在过去的批处理计算中，开发了一些非抢占式调度程序。这样的系统会将每项工作做完，再考虑是否允许新工作。几乎所有现代优化的调度程序都是抢占式的，非常愿意停止一个进程以运行另一个进程，这意味着调度程序采用了我们之前学习的机制。特别是调度程序可以进行上下文切换，临时停止一个运行进程，并回复或启动另一个进程。

因此我们找到了一个用 SJF 进行调度的好方法，但是我们的假设仍然是不切实际的。让我们放宽假设 2，现在假设工作可以随时到达，而不再是同时到达。

现在假设 A 在 t=0 时到达，且需要运行 100s。而 B 和 C 在 t=10 到达，且各需运行 10s。如果使用纯粹的 SJF，则会得到下面的调度过程：

从图中可以看出，即使 B 和 C 在 A 之后不久到达，但它们仍然需要等待 A 完成之后才能开始运行，从而遭遇同样的护航问题。它们的平均周转时间为 103.33s。

最短完成时间优先

为了解决该问题，需要放款假设条件：工作必须保持运行直到完成。我们还需要调度程序本身的一些机制。你可能已经猜到，鉴于我们之前讨论过的关于时钟中断和上下文切换技术，当 B 和 C 到达时，调度程序当然可以做其他事情：它可以抢占工作 A，并决定运行另一个工作，后续稍后会继续运行工作 A。根据我们的定义，SJF 是一种非抢占式调度程序，因此存在上述问题。

幸运的是，有一个调度程序完全就是这样做的：向 SJF 添加抢占能力，称为最短完成时间优先，或抢占式最短作业优先。每当新工作进入系统时，它就会确定剩余工作和新工作中谁的剩余时间最少，然后调度该工作。因此，在我们的例子中，STCF 将抢占 A 并运行 B 和 C。只有在它们完成之后才能调度 A 的剩余时间。

结果是平均周转时间大大减少：50s。和以前一样，考虑到我们的新架设，STCF 可证明是最优的。考虑到所有工作如果同时到达，则 SJF 是最优的，那么你应该能够看到 STCF 的最优性是符合直觉的。

新度量指标：响应时间

因此，如果我们知道任务长度，而且任务只使用 CPU，而我们唯一的衡量标准是周转时间，STCF 将是一个很好的策略。事实上，对于许多早期批处理系统，这些类型的调度算法有一定的意义。然而，引入分时系统改变了这一切。现在，用户将会坐在终端前面，同时也要求系统的交互性好。因此，一个新的度量指标诞生了：响应时间。

响应时间定义为从任务到达系统到开始首次运行的时间：响应时间=首次运行-到达时间。

比如，如果我们有上面的调度(A 在时间 0 到达，BC 在时间 10 到达)，每个作业的响应时间如下：

• A：0
• B：0
• C：10

平均为 3.3s。

你可能会想到，STCF 和相关方法在响应时间上的表现并不好。比如，如果 3 个工作同时到达，第三个工作必须等待前两个工作完全运行后才能开始运行。这种方法虽然有很好的周转时间，但对于响应时间和交互性是相当糟糕的。假设你在终端前输入，不得不等待 10s 才能看到系统的回应，只是因为其他一些工作已经在你之前被调度了。

因此我们还有另一个问题：如何构建对响应时间敏感的调度程序？

轮转

为了解决这个问题，我们将介绍一种新的调度算法：轮转调度(Round-Robin)。基本思想很简单：RR 在一个时间片内运行一个工作，然后切换到运行队列中的下一个任务，而不是运行一个任务直到结束。它反复执行，直到所有任务执行完成。因此，RR 有时被称为时间切片。注意，时间片长度必须是时钟中断周期的倍数。因此，如果时钟中断是每 10ms 一次，则时间片可以是 10ms、20ms 等等。

为了更详细的理解 RR，我们来看一个例子。假设 3 个任务 ABC 同时到达，并且都希望运行 5 秒。SJF 调度程序必须运行网当前任务才能运行下一个任务。相比之下，1s 时间片的 RR 可以快速的循环工作。

RR 的平均响应时间为 1s，而 SJF 的平均响应时间为 5s。

如果你所见，时间片长度对于 RR 是至关重要的。越短，RR 在响应时间上的表现越好。然而，时间片太短也会有问题：突然上下文切换的成本将影响整体性能。因此，系统设计者需要权衡时间片的长度，使其足够长以分摊上下文切换的成本，而又不会使系统无法及时响应。

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

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

如果响应时间是我们的唯一指标，那么带有合理时间片的 RR，就会是非常好的调度程序。但是周转时间呢？再来看看我们的例子。ABC 各自的运行时间为 5s，同时到达，RR 是具有 1s 时间片的调度程序。从上面的图中可以看到，平均周转时间为 14s，相当可怕。

这并不奇怪，如果周转时间是我们的指标，那么 RR 确实是最糟糕的策略之一。直观的说，这应该是有意义的：RR 所做的真是延伸每个工作，只运行每个工作一小段时间，就转向下一个工作。因为周转时间只关心作业何时完成，RR 几乎是最差的，在很多情况下甚至比简单的 FIFO 还要差。

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

我们开发了两种调度程序。第一种类型(SJF/STCF)优化周转时间，但对响应时间不利。第二种类型(RR)优化响应时间，但对周转时间不利。我们还有两个假设需要放宽：作业没有 IO、每个作业的运行时间是已知的。接下来我们来解决这些假设。

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

结合 IO

首先，我们将放宽假设 4：所有程序都执行 IO。想象一下没有任何输入的程序：每次都会产生相同的输出。设想一个没有输出的程序：没有人会看到它，它的运行没有意义。

调度程序显然要在工作发起 IO 请求时做出决定，因为当前正在运行的作业在 IO 期间不会使用 CPU，它被阻塞直到等待 IO 完成。如果将 IO 请求发送到磁盘驱动器，则进程可能会被阻塞几毫秒甚至更长时间，具体取决于驱动器当前的 IO 负载。因此，这时调度程序应该在 CPU 上安排其他工作。

调度程序还必须在 IO 完成时做出决定。发生这种情况时，会产生中断，操作系统运行并将发出 IO 的进程从阻塞状态转换为就绪状态。当然，它甚至可以决定在哪个时候运行该项工作。操作系统应该如何处理每项工作？

为了更好的理解这个问题，我们假设两个工作 AB，每项工作都需要 50ms 的 CPU 时间。但是有一个明显的区别，A 运行 10ms，然后发起 IO 请求，假设每个 IO 需要 10ms。而 B 只是使用 CPU 50ms，不执行 IO。调度程序先运行 A，然后运行 B。

假设我们正在尝试构建 STCF 调度程序。这样的调度程序应该如何考虑这样的事实，即 A 分解成 5 个 10ms 子工作，而 B 仅仅是单个 50ms CPU 的需求？显然，仅仅运行一个工作然后运行另一个工作，而不考虑 IO，是没有意义的。

一种常见的方法是将 A 的每个 10ms 的子工作视为一项独立的工作。因此，当系统启动时，它的选择是调度 10ms 的 A，还是 50ms 的 B，对于 STCF 来说选择是明确的：选择较短的一个，这种情况下是 A。然后 A 的工作已经完成，只剩下 B，并开始运行。然后提交 A 的一个新子工作，它抢占 B 并运行 10ms。这样做可以实现重叠，一个进程在等待另一个进程 IO 完成时使用 CPU，系统因此得到更好的利用。

这样我们就看到了调度程序可能如何结合 IO。通过将每个 CPU 突发作为一项工作，调度程序确保“交互”的进程正常运行。当这些交互式作业正在执行 IO 时，其他 CPU 密集型作业将运行，从而更好的利用处理器。

无法预知

有了应对 IO 的基本方法，我们来到最后的假设：调度程序知道每个工作的长度。如前所述，这可能是最糟糕的假设。事实上，在一个通用的操作系统中，操作系统通常对每个作业的长度知之甚少。因此我们如何建立一个没有这种先验知识的 SJF/STCF？更进一步，我们如何能够将已经看到的一些想法与 RR 调度程序结合，以便响应时间也能表现的更好？

小结

我们介绍了调度的基本思想，并开发了两类方法。第一类是运行最短的工作，从而优化周转时间。第二类是交替运行所有工作，从而优化响应时间。但很难做到鱼与熊掌兼得，这是系统中最常见、固有的折中。我们也看到了如何将 IO 结合到场景中，但仍未解决操作系统根本无法看到未来的问题。稍后，我们将看到如何构建一个调度程序，利用最近的历史预测未来。这个调度程序被称为多级反馈队列。