第 7 章 进程调度：介绍

思维导图

图 7.0 进程调度思维导图

引言

到目前为止，关于运行进程的底层机制（例如上下文切换）应该是清楚的；如果不清楚，可以回到前面的章节重新阅读关于这些内容的描述。然而，我们还没有理解操作系统调度程序采用的高级策略。现在我们将做到这一点，介绍一系列调度策略（有时被称为学科），这些策略是各种聪明而勤奋的人多年来开发出来的。

事实上，调度的起源早于计算机系统；早期的方法来自运营管理领域，应用于计算机。这个事实应该不足为奇：装配线和许多其他人类工作也需要调度，其中存在许多相同的问题，包括对效率的强烈追求。

因此，我们的问题是：

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

我们应该如何开发一个关于调度策略的基本框架？有哪些关键假设？哪些指标是重要的？在最早的计算机系统中使用了哪些基本方法？

7.1 工作负载假设

在讨论可能的策略范围之前，让我们首先对运行在系统中的进程进行一些简化的假设，有时将它们统称为工作负载。确定工作负载是制定策略的关键部分，而您对工作负载了解得越多，策略就可以更加精细化。

我们在这里所做的工作负载假设大部分都是不现实的，但这没关系（暂时），因为随着我们的进展，我们将放宽这些假设，并最终开发出我们将称之为...（戏剧性的停顿）...

完全运行调度规则（a fully-operational scheduling discipline）。

对在系统中运行的进程（有时称为作业）的做出如下假设：

1. 每个作业运行相同的时间；
2. 所有作业在同一时间到达。
3. 一旦开始，每个作业都运行到完成。
4. 所有作业只使用 CPU（即，它们不执行 I/O 操作）
5. 每个作业的运行时间是已知的。

我们说这些假设中有许多是不现实的，但就像在奥威尔的《动物农场》中一些动物比其他动物更平等一样，本章中有些假设比其他假设更不现实。特别是，您可能会感到困扰的是每个作业的运行时间都是已知的：这将使调度程序无所不知，尽管这将是伟大的（可能），但不太可能在短时间内发生。

7.2 调度指标

除了做出工作负载假设外，我们还需要一件东西来使我们能够比较不同的调度策略：调度指标。指标只是我们用来衡量某些东西的东西，而在调度中有许多不同的指标是有意义的。然而，暂时让我们简化生活，只使用一个指标：周转时间。作业的周转时间被定义为作业完成的时间减去作业到达系统的时间。更正式地说，周转时间$T_{turnaround}$如下：

$$T_{turnaround} = T_{completion} − T_{arrival}$$

因为我们假设所有作业都在同一时间到达，所以目前 $T_{arrival} = 0$，因此$T_{turnaround} = T_{completion}$。随着我们放宽前述的假设，这个事实将发生改变。

您应该注意，周转时间是一种性能指标，它将是本章的主要关注点。另一个感兴趣的指标是公平性，可以通过Jain公平性指数[J91]等来衡量。性能和公平性在调度中经常相互矛盾；例如，调度程序可能优化性能，但以阻止一些作业运行为代价，从而降低公平性。这个困境告诉我们，生活并不总是完美的。

7.3 先进先出（FIFO）

我们可以实现的最基本的调度算法之一被称为先进先出（FIFO）调度，有时也称为先来先服务（FCFS）。FIFO 具有许多积极的特性：它显然很简单，因此易于实现。并且，在我们的假设下，它工作得相当不错。

让我们一起快速举个例子。想象一下，系统中有三个作业，A、B 和 C，它们几乎在同一时间到达（Tarrival = 0）。因为 FIFO 必须首先放置某个作业，让我们假设虽然它们都是同时到达的，A 比 B 稍微早到一点，B 比 C 稍微早到一点。还假设每个作业运行 10 秒。这些作业的平均周转时间将是多少？

图 7.1 简单的 FIFO 例子

从图 7.1 中，您可以看到 A 在 10 时完成，B 在 20 时完成，C 在 30 时完成。因此，这三个作业的平均周转时间简单地是 $\frac{10 + 20 + 30}{3} = 20$。计算周转时间就是这么简单。

现在让我们放宽我们的一个假设。特别是，让我们放宽假设 1，因此不再假设每个作业运行的时间相同。FIFO 现在的表现如何？您能构建什么样的工作负载来使 FIFO 的性能变差？

（在阅读以下内容之前，请考虑一下...继续思考...搞清楚了吗？！）

您现在可能已经弄清楚了，但以防万一，让我们再举一个示例，以展示不同长度的作业怎么让 FIFO 调度出现问题。特别是，让我们再次假设有三个作业（A、B 和 C），但这次A运行100 秒，而 B 和 C 各自运行10秒。

图 7.2 为什么 FIFO 并不那么好

如您在图 7.2 中所见，作业 A 在 B 或 C 甚至有机会运行之前，首先运行了整整 100 s。因此，系统的平均周转时间很高：110 s（$\frac{100 + 110 + 120}{3} = 110$）。

这个问题通常被称为护航效应（convey effect），其中一些相对较短的潜在资源使用者排在一个重量级资源使用者后面。这种调度情景可能让你想起杂货店里的一个排队等待的场景，当你看到前面的人推着三车食品并拿出支票簿时，你知道要等一段时间。

那么我们该怎么办呢？如何开发一个更好的算法来处理运行时间不同的作业？先自己思考一下，然后再阅读下文。

7.4 最短任务优先（SJF）

解决这个问题的方法非常简单，事实上是从运筹学[1954 年的参考文献，1956 年的参考文献]中借鉴过来的，应用到了计算机系统中的作业调度。这个新的调度策略被称为“最短作业优先”（Shortest Job First，SJF），这个名字应该很容易记住，因为它完全描述了这个策略：首先运行最短的作业，然后是下一个最短的，以此类推。

SJF 调度算法的原则

SJF 原则表示了一个通用的调度原则，可以应用于任何关心每个客户（或在我们的情况下，作业）的周转时间的系统。想象一下你等过的任何队列：如果相关的机构关心客户满意度，他们很可能已经考虑了 SJF。例如，杂货店通常设有一个“十件或以下”的队伍，以确保只购买少量商品的顾客不会被堵在准备应对未来核冬天的家庭后面。

7.3 简单的 SJF 例子

让我们继续使用上面的示例，但将 SJF 作为我们的调度策略。图7.3显示了运行 A、B 和 C 的结果。希望这个图表清楚地表明了为什么 SJF 在平均周转时间方面表现得更好。通过在运行 A 之前先运行 B 和 C，SJF 将平均周转时间从 110 秒减少到 50 秒（$\frac{10 + 20 + 120}{3} = 50$），性能提高了两倍多。

事实上，根据我们关于所有作业同时到达的假设，我们可以证明 SJF 确实是一种最优的调度算法。然而，您正在上系统课程，而不是理论或运筹学课程；所以在这里就不给出它的证明。

因此，我们已经找到了一个很好的 SJF 调度方法，但我们的假设仍然相当不现实。让我们放宽一些。具体来说，我们可以针对假设 2，现在假设作业可以在任何时间到达，而不是一次性到达。这会导致什么问题呢？ （再次思考...你在思考吗？）

在这里，我们可以通过一个示例再次说明问题。这一次，假设 A 在 t = 0 时到达，需要运行100 秒，而 B 和 C 在 t = 10 时到达，每个都需要运行 10 秒。使用纯 SJF，我们将得到图 7.4 中所示的时间表。

图 7.4 SJF 例子：晚到的作业 B 和 C

如图 7.4 所示，尽管 B 和 C 在 A 之后不久到达，但它们仍然被迫等待 A 完成，因此遭受了相同的车队问题。这三个作业的平均周转时间为 103.33 秒（$\frac{100 +(110-10) + (120-10)}{3} = 103.33$）。调度程序可以采取什么措施呢？

7.5 最短完成时间优先（STCF）

为解决这个问题，我们需要放宽第 3 个假设（即作业必须运行到完成），因此让我们这样做。此外，调度程序本身需要一些机制。如您可能猜到的，考虑到我们之前关于定时器中断和上下文切换的讨论，调度程序可以在 B 和 C 到达时采取其他措施：它可以抢占作业 A，并决定运行另一个作业，或许稍后继续 A。根据我们的定义，SJF 是一个非抢占式调度程序，因此存在上述问题。

图 7.5 简单的 STCF 例子

幸运的是，有一个调度程序可以做到这一点：为 SJF 添加抢占功能，即最短剩余运行时间优先（STCF）或抢占式最短作业优先（PSJF）调度程序。每当新作业进入系统时，STCF 调度程序确定剩余作业（包括新作业）中哪个作业剩余时间最少，并安排运行该作业。因此，在我们的示例中，STCF将抢占A并运行B和C直到完成；只有在它们完成后，才会安排A的剩余时间。图7.5显示了一个示例。

结果是平均周转时间大大提高：50 秒（$\frac{(120−0)+(20−10)+(30−10)}{3}$）。与以前一样，根据我们的新假设，STCF 是可证明的最优的；考虑到如果所有作业同时到达，则 SJF 是最优的，您可能能够理解 STCF 最优性背后的直觉。

7.6 新度量指标：响应时间

因此，如果我们知道作业的长度，且作业只使用 CPU，而我们唯一的指标是周转时间，那么 STCF 将是一个很好的策略。实际上，对于早期的批处理计算系统，这些类型的调度算法是有道理的。然而，分时共享计算机的引入改变了一切。现在，用户会坐在终端前，要求系统具有交互性能。因此，产生了一个新的度量标准：响应时间。

我们将响应时间定义为作业到达系统后首次被调度的时间。更正式地说：

$$T_{response} = T_{firstrun} − T_{arrival}$$

例如，如果我们有图7.5的时间表（A 在时间 0 到达，B 和 C 在时间 10 到达），则每个作业的响应时间如下：作业 A 为 0，作业 B 为 0，作业 C 为 10（平均值：3.33）。

正如你可能想的那样，STCF 和相关的调度方法对于响应时间来说并不特别好。例如，如果有三个作业同时到达，第三个作业必须等待前两个作业完全运行后才能被调度一次。尽管对于周转时间来说效果很好，但这种方法对于响应时间和交互性来说非常不利。想象一下坐在终端前输入内容，由于某个其他作业排在你前面而不得不等待10秒才能看到系统的响应：这并不怎么愉快。

因此，我们面临另一个问题：如何构建一个对响应时间敏感的调度器？

7.7 时间片轮转调度

为了解决这个问题，我们将引入一种新的调度算法，经典地称为轮转（Round-Robin，简称RR）调度。其基本思想很简单：RR 不是运行作业直到完成，而是为每个作业分配一个时间片（有时被称为调度量子），然后切换到运行队列中的下一个作业。它反复这样做，直到所有作业完成。因此，RR 有时被称为时间片轮转。请注意，时间片的长度必须是计时器中断周期的倍数；因此，如果计时器每 10 毫秒中断一次，时间片可以是 10、20或 10 毫秒的任何倍数。

图 7.6 SJF 的响应时间不怎么好。

图 7.7 时间片轮转调度

为了更详细地了解 RR，让我们看一个例子。假设有三个作业 A、B 和 C 在同一时间到达系统，它们每个都希望运行 5 秒。使用 SJF 调度器会在运行下一个作业之前将每个作业运行到完成（如图 7.6 所示）。相比之下，具有 1 秒时间片的RR会迅速循环运行作业（如图7.7所示）。

RR的平均响应时间是：$\frac{0+1+2}{3} = 1$；而 SJF 的平均响应时间是：$\frac{0+5+10}{3} = 5$。

正如您所看到的，时间片的长度对RR非常重要。它越短，在响应时间指标下 RR 的性能越好。然而，将时间片设得太短会导致问题：突然之间，上下文切换的成本将支配整体性能。因此，决定时间片的长度对系统设计者来说是一个权衡，要让它足够长以摊销切换的成本，但又不要让它太长，以至于系统不再响应。

请注意，上下文切换的成本不仅仅源于操作系统保存和恢复一些寄存器的操作。当程序运行时，它们会在 CPU 缓存、TLB、分支预测器和其他芯片上的硬件中积累大量状态。切换到另一个作业会导致这些状态被刷新，并且会将与当前运行作业相关的新状态加载进来，这可能会对性能产生明显的成本。

因此，带有合理时间片的 RR 是一个在响应时间是唯一度量标准的情况下的出色调度器。但是，对于我们的老朋友周转时间呢？让我们再次看看上面的示例。具有 5 秒运行时间的 A、B 和 C 在相同时间到达，RR 是具有（较长）1 秒时间片的调度程序。从上面的图片中，我们可以看到 A 在 13 时结束，B 在 14 时结束，C 在 15 时结束，平均为 14。非常糟糕！

因此，RR在周转时间是我们的度量标准时的确是最差的策略之一。直观地来看，这是有道理的：RR所做的是尽量延长每个作业的时间，只在移至下一个作业之前运行每个作业一小段时间。因为周转时间只关心作业何时完成，所以 RR 几乎是最差的，甚至在许多情况下比简单的 FIFO 还要糟糕。

更一般地说，任何公平的策略（如 RR），即在较小的时间尺度上均匀分配 CPU 给活跃进程，都会在周转时间等度量标准上表现不佳。这实际上是一种固有的权衡：如果你愿意不公平对待，你可以运行较短的作业直到完成，但以响应时间为代价；如果你更重视公平性，响应时间会降低，但以周转时间为代价。这种权衡在系统中很常见；你不能既要鱼，又要熊掌。

我们已经开发了两种类型的调度程序。第一种类型（SJF、STCF）优化周转时间，但在响应时间方面表现不佳。第二种类型（RR）优化响应时间，但在周转时间方面表现不佳。而我们仍然需要舍弃两个假设：假设4（作业不进行 I/O）和假设5（作业的运行时间已知）。

7.8 结合 I/O

首先，我们将舍弃第 4 个假设——当然，所有程序都执行 I/O。想象一个不需要任何输入的程序：它每次都会产生相同的输出。再想象一个没有输出的程序：那就像是树在森林中倒下，无人看到；它运行与否都无关紧要。

当作业发起 I/O 请求时，调度程序显然需要做出决策，因为当前正在运行的作业在 I/O 期间不会使用 CPU；它被阻塞等待 I/O 完成。如果 I/O 被发送到硬盘驱动器，取决于驱动器的当前 I/O 负载情况，该进程可能会被阻塞几毫秒或更长时间。因此，在这个时候，调度程序可能应该在 CPU 上安排另一个作业运行。

当 I/O 完成时，调度程序还必须做出决策。当发生这种情况时，会引发一个中断，操作系统会运行并将发出 I/O 的进程从阻塞状态移回就绪状态。当然，它甚至可以决定在那时运行该作业。操作系统应该如何处理每个作业？

为了更好地理解这个问题，让我们假设有两个作业 A 和 B，它们都需要 50 毫秒的 CPU 时间。然而，有一个明显的区别：A 运行了 10 毫秒，然后发出了一个 I/O 请求（在这里假设每个 I/O 需要 10 毫秒），而 B 只是在 CPU 上运行了 50 毫秒，没有进行任何 I/O 操作。调度程序首先运行 A，然后运行 B（见图 7.8）。

图 7.8 资源的利用率低

假设我们正在尝试构建一个 STCF 调度程序。这样的调度程序应该如何处理A被分为5个10毫秒子作业，而 B 只是一个需要 50 毫秒 CPU 时间的作业？很明显，仅仅按顺序运行一个作业，然后再运行另一个作业，而不考虑如何处理 I/O 是没有意义的。

一种常见的方法是将 A 的每个 10 毫秒子作业视为独立的作业。因此，当系统启动时，它可以选择是调度一个 10 毫秒的 A 还是一个 50 毫秒的 B。对于 STCF，选择是明显的：选择较短的那一个，即 A。然后，当 A 的第一个子作业完成时，只剩下 B，它开始运行。然后提交一个新的 A 子作业，它会抢占 B 并运行 10 毫秒。这样可以实现重叠，即在等待另一个进程的 I/O 完成时，CPU 被另一个进程使用；因此，系统被更好地利用（见图 7.9）。

图 7.9 重叠可以让资源更好地得到利用

因此，我们可以看到调度程序如何处理 I/O。通过将每个 CPU 突发作为一个作业处理，调度程序确保“交互式”的进程频繁运行。当这些交互式作业执行 I/O 操作时，其他 CPU 密集型作业会运行，从而更好地利用处理器。

重叠操作可以提高利用率。

当可能的时候，重叠操作以最大化系统的利用。重叠在许多不同领域都很有用，包括在执行磁盘 I/O 或发送消息给远程机器时；在这两种情况下，启动操作然后切换到其他工作是一个好主意，可以提高系统的整体利用率和效率。

7.9 No More Oracle

有了基本的 I/O 方法，我们来到了最后一个假设：调度程序知道每个作业的长度。正如我们之前所说，这可能是我们能够做出的最糟糕的假设。事实上，在通用操作系统（我们关心的那种）中，操作系统通常对每个作业的长度知之甚少。那么，如何构建一个行为类似 SJF/STCF 的方法，而不需要这样的先验知识？此外，如何结合我们在 RR 调度程序中看到的一些想法，使响应时间也非常好？

7.10 小结

我们已经介绍了调度背后的基本思想，并开发了两类调度策略。第一类策略运行剩余时间最短的作业，从而优化周转时间；第二类策略在所有作业之间交替，从而优化响应时间。在一个领域表现良好的地方，它们在另一个领域表现不佳，这是系统中常见的固有权衡。我们还看到了如何将 I/O 纳入考虑，但仍然没有解决操作系统无法预测未来的基本问题。不久以后，我们将看到如何克服这个问题，通过构建一个调度程序，利用最近的过去来预测未来。这个调度程序被称为多级反馈队列，它是下一章的主题。