操作系统导论笔记1
受限制直接运行
为了使程序尽可能快地运行，操作系统开发人员想出了一种技术——我们称之为受限的 直接执行（limited direct execution）。这个概念的“直接执行”部分很简单：只需直接在 CPU 上运行程序即可。因此当OS希望启动程序运行时，它会在进程列表中为其创建一个进程条目，为其分配一些内存，将程序代码（从磁盘）加载到内存中，找到入口点（main函数或者类似）跳转到哪里，并开始执行用户代码
| 操作系统 | 程序 |
|---|---|
| 在进程列表上创建条目 为程序分配内存 将程序加载到内存中 根据 argc/argv 设置程序栈 | |
| 清除寄存器 执行 call main() 方法 | |
| 执行 main() 从 main 中执行 return | |
| 释放进程的内存将进程 从进程列表中清除 |
听起来很简单，不是吗？但是，这种方法在我们的虚拟化 CPU 时产生了一些问题。第 一个问题很简单：如果我们只运行一个程序，操作系统怎么能确保程序不做任何我们不希 望它做的事，同时仍然高效地运行它？第二个问题：当我们运行一个进程时，操作系统如 何让它停下来并切换到另一个进程，从而实现虚拟化 CPU 所需的时分共享？
受限制的操作
直接执行的明显优势是快速。该程序直接在硬件 CPU 上运行，因此执行速度与预期的 一样快。但是，在 CPU 上运行会带来一个问题——如果进程希望执行某种受限操作（如向 磁盘发出 I/O 请求或获得更多系统资源（如 CPU 或内存）），该怎么办
硬件通过提供不同的执行模式来协助操作系统。在用户模式（user mode）下，应用程序不能完全访 问硬件资源。在内核模式（kernel mode）下，操作系统可以访问机器的全部资源。还提供了陷入（trap） 内核和从陷阱返回（return-from-trap）到用户模式程序的特别说明，以及一些指令，让操作系统告诉硬 件陷阱表（trap table）在内存中的位置
对于 I/O 和其他相关操作，一种方法就是让所有进程做所有它想做的事情。但是，这样 做导致无法构建许多我们想要的系统。例如，如果我们希望构建一个在授予文件访问权限 前检查权限的文件系统，就不能简单地让任何用户进程向磁盘发出 I/O。如果这样做，一个 进程就可以读取或写入整个磁盘，这样所有的保护都会失效。 因此，我们采用的方法是引入一种新的处理器模式，称为用户模式（user mode）。在用 户模式下运行的代码会受到限制。例如，在用户模式下运行时，进程不能发出 I/O 请求。这 样做会导致处理器引发异常，操作系统可能会终止进程。 与用户模式不同的内核模式（kernel mode），操作系统（或内核）就以这种模式运行。 在此模式下，运行的代码可以做它喜欢的事，包括特权操作，如发出 I/O 请求和执行所有类 型的受限指令。 但是，我们仍然面临着一个挑战——如果用户希望执行某种特权操作（如从磁盘读取）， 应该怎么做？为了实现这一点，几乎所有的现代硬件都提供了用户程序执行系统调用的能 力。系统调用是在 Atlas [K+61，L78]等古老机器上开创的，它允许内核小心地向用户程序 暴露某些关键功能，例如访问文件系统、创建和销毁进程、与其他进程通信，以及分配更多内存。大多数操作系统提供几百个调用（详见 POSIX 标准[P10]）。早期的 UNIX 系统公 开了更简洁的子集，大约 20 个调用。 要执行系统调用，程序必须执行特殊的陷阱（trap）指令。该指令同时跳入内核并将特 权级别提升到内核模式。一旦进入内核，系统就可以执行任何需要的特权操作（如果允许）， 从而为调用进程执行所需的工作。完成后，操作系统调用一个特殊的从陷阱返回 （return-from-trap）指令，如你期望的那样，该指令返回到发起调用的用户程序中，同时将 特权级别降低，回到用户模式。 执行陷阱时，硬件需要小心，因为它必须确保存储足够的调用者寄存器，以便在操作 系统发出从陷阱返回指令时能够正确返回。例如，在 x86 上，处理器会将程序计数器、标 志和其他一些寄存器推送到每个进程的内核栈（kernel stack）上。从返回陷阱将从栈弹出这 些值，并恢复执行用户模式程序（有关详细信息，请参阅英特尔系统手册[I11]）。其他硬件 系统使用不同的约定，但基本概念在各个平台上是相似的
为什么系统调用看起来像过程调用 你可能想知道，为什么对系统调用的调用（如 open()或 read()）看起来完全就像 C 中的典型过程调用。 也就是说，如果它看起来像一个过程调用，系统如何知道这是一个系统调用，并做所有正确的事情？原因 很简单：它是一个过程调用，但隐藏在过程调用内部的是著名的陷阱指令。更具体地说，当你调用 open() （举个例子）时，你正在执行对 C 库的过程调用。其中，无论是对于 open()还是提供的其他系统调用，库 都使用与内核一致的调用约定来将参数放在众所周知的位置（例如，在栈中或特定的寄存器中），将系统 调用号也放入一个众所周知的位置（同样，放在栈或寄存器中），然后执行上述的陷阱指令。库中陷阱之 后的代码准备好返回值，并将控制权返回给发出系统调用的程序。因此，C 库中进行系统调用的部分是用 汇编手工编码的，因为它们需要仔细遵循约定，以便正确处理参数和返回值，以及执行硬件特定的陷阱指 令。现在你知道为什么你自己不必写汇编代码来陷入操作系统了，因为有人已经为你写了这些汇编
还有一个重要的细节没讨论：先进如何知道在OS内运行哪些代码？显然，发起调用的过程不能指定要跳转到的地址（这就和你在尽显过程调用时一样），这样做让程序可以跳转到 内核中的任意位置，这显然是一个糟糕的主意（想象一下跳到访问文件的代码，但在权限 检查之后。实际上，这种能力很可能让一个狡猾的程序员令内核运行任意代码序列[S07]）。 因此内核必须谨慎地控制在陷阱上执行的代码。
内核通过在启动时设置陷阱表（trap table）来实现。当机器启动时，它在特权（内核）模式下执行，因此可以根据需要自由配置机器硬件。操作系统做的第一件事，就是告诉硬件在发生某些异常事件时需要执行哪些代码。例如，当硬盘终端，发生键盘终端或进程终端或程序进行系统调用时，应该运行哪些代码？操作系统通过某中特殊指令，通知硬件这些陷阱处理 程序的位置。一旦硬件被通知，它就会记住这些处理程序的位置，直到下一次重新启动机器， 并且硬件知道在发生系统调用和其他异常事件时要做什么（即跳转到哪段代码）
最后再插一句：能够执行指令来告诉硬件陷阱表的位置是一个非常强大的功能。因此， 你可能已经猜到，这也是一项特权（privileged）操作。如果你试图在用户模式下执行这个 指令，硬件不会允许，你可能会猜到会发生什么（提示：再见，违规程序）。思考问题：如 果可以设置自己的陷阱表，你可以对系统做些什么？你能接管机器吗
LDE 协议有两个阶段。第一个阶段（在系统引导时），内核初始化陷阱表，并且 CPU 记住它 的位置以供随后使用。内核通过特权指令来执行此操作（所有特权指令均以粗体突出显示）。第 二个阶段（运行进程时），在使用从陷阱返回指令开始执行进程之前，内核设置了一些内容（例 如，在进程列表中分配一个节点，分配内存）。这会将 CPU 切换到用户模式并开始运行该进程。 当进程希望发出系统调用时，它会重新陷入操作系统，然后再次通过从陷阱返回，将控制权还给 进程。该进程然后完成它的工作，并从 main()返回。这通常会返回到一些存根代码，它将正确退 出该程序（例如，通过调用 exit()系统调用，这将陷入 OS 中）。此时，OS 清理干净，任务完成了。
进程之间切换
直接执行的下一个问题是实现进程之间的切换。在进程之间切换应该很简单，对吧？
作系统应该决定停止一个进程并开始另一个进程。有什么大不了的？但实际上这有点棘 手，特别是，如果一个进程在 CPU 上运行，这就意味着操作系统没有运行。如果操作系统 没有运行，它怎么能做事情？（提示：它不能）虽然这听起来几乎是哲学，但这是真正的 问题——如果操作系统没有在 CPU 上运行，那么操作系统显然没有办法采取行动。因此， 我们遇到了关键问题。
关键问题：如何重获 CPU 的控制权 操作系统如何重新获得 CPU 的控制权（regain control），以便它可以在进程之间切换？
等待系统调用
过去某些系统采用的一种方式（例如，早期版本的 Macintosh 操作系统[M11]或旧的 Xerox Alto 系统[A79]）称为协作（cooperative）方式。在这种风格下，操作系统相信系统的 进程会合理运行。运行时间过长的进程被假定会定期放弃 CPU，以便操作系统可以决定运 行其他任务。 因此，你可能会问，在这个虚拟的世界中，一个友好的进程如何放弃 CPU？事实证 明，大多数进程通过进行系统调用，将 CPU 的控制权转移给操作系统，例如打开文件并 随后读取文件，或者向另一台机器发送消息或创建新进程。像这样的系统通常包括一个 显式的 yield 系统调用，它什么都不干，只是将控制权交给操作系统，以便系统可以运行 其他进程。
操作系统通常必须处理不当行为，这些程序通过设计（恶意）或不小心（错误），尝试做某些不应 该做的事情。在现代系统中，操作系统试图处理这种不当行为的方式是简单地终止犯罪者。一击出局！ 也许有点残酷，但如果你尝试非法访问内存或执行非法指令，操作系统还应该做些什么?
如果应用程序执行了某些非法操作，也会将控制转移给操作系统。例如，如果应用程 序以 0 为除数，或者尝试访问应该无法访问的内存，就会陷入（trap）操作系统。操作系统 将再次控制 CPU（并可能终止违规进程）。 因此，在协作调度系统中，OS 通过等待系统调用，或某种非法操作发生，从而重新获 得 CPU 的控制权。你也许会想：这种被动方式不是不太理想吗？例如，如果某个进程（无 论是恶意的还是充满缺陷的）进入无限循环，并且从不进行系统调用，会发生什么情况？ 那时操作系统能做什么？
操作系统进行控制
事实证明，没有硬件的额外帮助，如果进程拒绝进行系统调用（也不出错），从而将控 制权交还给操作系统，那么操作系统无法做任何事情。事实上，在协作方式中，当进程陷 入无限循环时，唯一的办法就是使用古老的解决方案来解决计算机系统中的所有问题——重 新启动计算机。因此，我们又遇到了请求获得 CPU 控制权的一个子问题
关键问题：如何在没有协作的情况下获得控制权 即使进程不协作，操作系统如何获得 CPU 的控制权？操作系统可以做什么来确保流氓进程不会占 用机器
答案很简单，许多年前构建计算机系统的许多人都发现了：时钟中断（timer interrupt） [M+63]。时钟设备可以编程为每隔几毫秒产生一次中断。产生中断时，当前正在运行的进 程停止，操作系统中预先配置的中断处理程序（interrupt handler）会运行。此时，操作系统 重新获得 CPU 的控制权，因此可以做它想做的事：停止当前进程，并启动另一个进程。
提示：利用时钟中断重新获得控制权 即使进程以非协作的方式运行，添加时钟中断（timer interrupt）也让操作系统能够在 CPU 上重新运 行。因此，该硬件功能对于帮助操作系统维持机器的控制权至关重要。
首先，正如我们之前讨论过的系统调用一样，操作系统必须通知硬件哪些代码在发生 时钟中断时运行。因此，在启动时，操作系统就是这样做的。其次，在启动过程中，操作 系统也必须启动时钟，这当然是一项特权操作。一旦时钟开始运行，操作系统就感到安全 了，因为控制权最终会归还给它，因此操作系统可以自由运行用户程序。时钟也可以关闭 （也是特权操作），稍后更详细地理解并发时，我们会讨论。 请注意，硬件在发生中断时有一定的责任，尤其是在中断发生时，要为正在运行的程 序保存足够的状态，以便随后从陷阱返回指令能够正确恢复正在运行的程序。这一组操作 与硬件在显式系统调用陷入内核时的行为非常相似，其中各种寄存器因此被保存（进入内 核栈），因此从陷阱返回指令可以容易地恢复。
保存和恢复上下文 既然操作系统已经重新获得了控制权，无论是通过系统调用协作，还是通过时钟中断 更强制执行，都必须决定：是继续运行当前正在运行的进程，还是切换到另一个进程。这 个决定是由调度程序（scheduler）做出的，它是操作系统的一部分。我们将在接下来的几章 中详细讨论调度策略。 如果决定进行切换，OS 就会执行一些底层代码，即所谓的上下文切换（context switch）。 上下文切换在概念上很简单：操作系统要做的就是为当前正在执行的进程保存一些寄存器 的值（例如，到它的内核栈），并为即将执行的进程恢复一些寄存器的值（从它的内核栈）。 这样一来，操作系统就可以确保最后执行从陷阱返回指令时，不是返回到之前运行的进程， 而是继续执行另一个进程。 为了保存当前正在运行的进程的上下文，操作系统会执行一些底层汇编代码，来保存 通用寄存器、程序计数器，以及当前正在运行的进程的内核栈指针，然后恢复寄存器、程 序计数器，并切换内核栈，供即将运行的进程使用。通过切换栈，内核在进入切换代码调 用时，是一个进程（被中断的进程）的上下文，在返回时，是另一进程（即将执行的进程） 的上下文。当操作系统最终执行从陷阱返回指令时，即将执行的进程变成了当前运行的进 程。至此上下文切换完成
进程调度
调度指标
除了做出工作负载假设之外，还需要一个东西能让我们比较不同的调度策略：调度指 标。指标是我们用来衡量某些东西的东西，在进程调度中，有一些不同的指标是有意义的。 现在，让我们简化一下生活，只用一个指标：周转时间（turnaround time）。任务的周转 时间定义为任务完成时间减去任务到达系统的时间。更正式的周转时间定义 T 周转时间是： T 周转时间= T 完成时间−T 到达时间 （7.1） 因为我们假设所有的任务在同一时间到达，那么 T 到达时间= 0，因此 T 周转时间= T 完成时间。随 着我们放宽上述假设，这个情况将改变。 你应该注意到，周转时间是一个性能（performance）指标，这将是本章的首要关注点。 另一个有趣的指标是公平（fairness），比如 Jian's Fairness Index[J91]。性能和公平在调度系 统中往往是矛盾的。例如，调度程序可以优化性能，但代价是以阻止一些任务运行，这就 降低了公平。这个难题也告诉我们，生活并不总是完美的
- 先进先出
- 最短任务优先
- 最短完成时间优先
- 响应时间
轮转
为了解决这个问题，我们将介绍一种新的调度算法，通常被称为轮转（Round-Robin， RR）调度[K64]。基本思想很简单：RR 在一个时间片（time slice，有时称为调度量子，scheduling quantum）内运行一个工作，然后切换到运行队列中的下一个任务，而不是运行一个任务直 到结束。它反复执行，直到所有任务完成。因此，RR 有时被称为时间切片（time-slicing）。 请注意，时间片长度必须是时钟中断周期的倍数。因此，如果时钟中断是每 10ms 中断一次， 则时间片可以是 10ms、20ms 或 10ms 的任何其他倍数。 为了更详细地理解 RR，我们来看一个例子。假设 3 个任务 A、B 和 C 在系统中同时到达， 并且它们都希望运行 5s。SJF 调度程序必须运行完当前任务才可运行下一个任务（见图 7.6）。相 比之下，1s 时间片的 RR 可以快要地循环工作（见图 7.7）
RR 的平均响应时间是：（0 + 1 + 2）/3 = 1; SJF 算法平均响应时间是：（0 + 5 + 10）/ 3 = 5。 如你所见，时间片长度对于 RR 是至关重要的。越短，RR 在响应时间上表现越好。然而，时间片太短是有问题的：突然上下文切换的成本将影响整体性能。因此，系统设计者 需要权衡时间片的长度，使其足够长，以便摊销（amortize）上下文切换成本，而又不会使 系统不及时响应。
提示：摊销可以减少成本 当系统某些操作有固定成本时，通常会使用摊销技术（amortization）。通过减少成本的频度（即执 行较少次的操作），系统的总成本就会降低。例如，如果时间片设置为 10ms，并且上下文切换时间为 1ms， 那么浪费大约 10%的时间用于上下文切换。如果要摊销这个成本，可以把时间片增加到 100ms。在这种 情况下，不到 1%的时间用于上下文切换，因此时间片带来的成本就被摊销了。
请注意，上下文切换的成本不仅仅来自保存和恢复少量寄存器的操作系统操作。程序 运行时，它们在 CPU 高要缓存、TLB、分支预测器和其他片上硬件中建立了大量的状态。 切换到另一个工作会导致此状态被刷新，且与当前运行的作业相关的新状态被引入，这可 能导致显著的性能成本[MB91]。 如果响应时间是我们的唯一指标，那么带有合理时间片的 RR，就会是非常好的调度程 序。但是我们老朋友的周转时间呢？再来看看我们的例子。A、B 和 C，每个运行时间为 5s， 同时到达，RR 是具有（长）1s 时间片的调度程序。从图 7.7 可以看出，A 在 13 完成，B 在 14，C 在 15，平均 14。相当可怕！ 这并不奇怪，如果周转时间是我们的指标，那么 RR 确实是最糟糕的策略之一。直观地 说，这应该是有意义的：RR 所做的正是延伸每个工作，只运行每个工作一小段时间，就转 向下一个工作。因为周转时间只关心作业何时完成，RR 几乎是最差的，在很多情况下甚至 比简单的 FIFO 更差。 更一般地说，任何公平（fair）的政策（如 RR），即在小规模的时间内将 CPU 均匀分配 到活动进程之间，在周转时间这类指标上表现不佳。事实上，这是固有的权衡：如果你愿 意不公平，你可以运行较短的工作直到完成，但是要以响应时间为代价。如果你重视公平 性，则响应时间会较短，但会以周转时间为代价。这种权衡在系统中很常见。你不能既拥 有你的蛋糕，又吃它①。 我们开发了两种调度程序。第一种类型（SJF、STCF）优化周转时间，但对响应时间不 利。第二种类型（RR）优化响应时间，但对周转时间不利。我们还有两个假设需要放宽： 假设 4（作业没有 I/O）和假设 5（每个作业的运行时间是已知的）。接下来我们来解决这些 假设
重叠可以提高利用率 如有可能，重叠（overlap）操作可以最大限度地提高系统的利用率。重叠在许多不同的领域很有用， 包括执行磁盘 I/O 或将消息发送到远程机器时。在任何一种情况下，开始操作然后切换到其他工作都是 一个好主意，这也提高了系统的整体利用率和效率。
：当然所有程序都执行 I/O。想象一下没有任何输入的程序： 每次都会产生相同的输出。设想一个没有输出的程序：它就像谚语所说的森林里倒下的树， 没有人看到它。它的运行并不重要。 调度程序显然要在工作发起 I/O 请求时做出决定，因为当前正在运行的作业在 I/O 期间 不会使用 CPU，它被阻塞等待 I/O 完成。如果将 I/O 发送到硬盘驱动器，则进程可能会被阻 塞几毫秒或更长时间，具体取决于驱动器当前的 I/O 负载。因此，这时调度程序应该在 CPU 上安排另一项工作。 调度程序还必须在 I/O 完成时做出决定。发生这种情况时，会产生中断，操作系统运行 并将发出 I/O 的进程从阻塞状态移回就绪状态。当然，它甚至可以决定在那个时候运行该项 工作。操作系统应该如何处理每项工作？ 为了更好地理解这个问题，让我们假设有两项工作 A 和 B，每项工作需要 50ms 的 CPU 时间。但是，有一个明显的区别：A 运行 10ms，然后发出 I/O 请求（假设 I/O 每个都需要 10ms），而 B 只是使用 CPU 50ms，不执行 I/O。调度程序先运行 A，然后运行 B（见图 7.8）。 假设我们正在尝试构建 STCF 调度程序。这样的调度程序应该如何考虑到这样的事实， 即 A 分解成 5 个 10ms 子工作，而 B 仅仅是单个 50ms CPU 需求？显然，仅仅运行一个工作， 然后运行另一个工作，而不考虑如何考虑 I/O 是没有意义的。 一种常见的方法是将 A 的每个 10ms 的子工作视为一项独立的工作。因此，当系统启动 时，它的选择是调度 10ms 的 A，还是 50ms 的 B。对于 STCF，选择是明确的：选择较短的 一个，在这种情况下是 A。然后，A 的工作已完成，只剩下 B，并开始运行。然后提交 A 的一个新子工作，它抢占 B 并运行 10ms。这样做可以实现重叠（overlap），一个进程在等 待另一个进程的 I/O 完成时使用 CPU，系统因此得到更好的利用（见图 7.9）。
这样我们就看到了调度程序可能如何结合 I/O。通过将每个 CPU 突发作为一项工作， 调度程序确保“交互”的进程经常运行。当这些交互式作业正在执行 I/O 时，其他 CPU 密 集型作业将运行，从而更好地利用处理器.
MLFQ多级反馈队列
本章将介绍一种著名的调度方法——多级反馈队列（Multi-level Feedback Queue， MLFQ）。1962 年，Corbato 首次提出多级反馈队列[C+62]，应用于兼容时分共享系统（CTSS）。 Corbato 因在 CTSS 中的贡献和后来在 Multics 中的贡献，获得了 ACM 颁发的图灵奖（Turing Award）。该调度程序经过多年的一系列优化，出现在许多现代操作系统中。 多级反馈队列需要解决两方面的问题。首先，它要优化周转时间。在第 7 章中我们看 到，这通过先执行短工作来实现。然而，操作系统通常不知道工作要运行多久，而这又是 SJF（或 STCF）等算法所必需的。其次，MLFQ 希望给交互用户（如用户坐在屏幕前，等 着进程结束）很好的交互体验，因此需要降低响应时间。然而，像轮转这样的算法虽然降 低了响应时间，周转时间却很差。所以这里的问题是：通常我们对进程一无所知，应该如 何构建调度程序来实现这些目标？调度程序如何在运行过程中学习进程的特征，从而做出 更好的调度决策？
关键问题：没有完备的知识如何调度？ 没有工作长度的先验（priori）知识，如何设计一个能同时减少响应时间和周转时间的调度程序？
提示：从历史中学习 多级反馈队列是用历史经验预测未来的一个典型的例子，操作系统中有很多地方采用了这种技术 （同样存在于计算机科学领域的很多其他地方，比如硬件的分支预测及缓存算法）。如果工作有明显的阶 段性行为，因此可以预测，那么这种方式会很有效。当然，必须十分小心地使用这种技术，因为它可能 出错，让系统做出比一无所知的时候更糟的决定
基本规则
为了构建这样的调度程序，本章将介绍多级消息队列背后的基本算法。虽然它有许多 不同的实现[E95]，但大多数方法是类似的。 MLFQ 中有许多独立的队列（queue），每个队列有不同的优先级（priority level）。任何 时刻，一个工作只能存在于一个队列中。MLFQ 总是优先执行较高优先级的工作（即在较 高级队列中的工作）。 当然，每个队列中可能会有多个工作，因此具有同样的优先级。在这种情况下，我们 就对这些工作采用轮转调度。 因此，MLFQ 调度策略的关键在于如何设置优先级。MLFQ 没有为每个工作指定不变
的优先情绪而已，而是根据观察到的行为调整它的优先级。例如，如果一个工作不断放弃 CPU 去等待键盘输入，这是交互型进程的可能行为，MLFQ 因此会让它保持高优先级。相 反，如果一个工作长时间地占用 CPU，MLFQ 会降低其优先级。通过这种方式，MLFQ 在 进程运行过程中学习其行为，从而利用工作的历史来预测它未来的行为。
规则 1：如果 A 的优先级 > B 的优先级，运行 A（不运行 B）。 规则 2：如果 A 的优先级 = B 的优先级，轮转运行 A 和 B。
如果要在某个特定时刻展示队列，可能会看到如下内容 （见图 8.1）。图 8.1 中，最高优先级有两个工作（A 和 B）， 工作 C 位于中等优先级，而 D 的优先级最低。按刚才介绍的 基本规则，由于 A 和 B 有最高优先级，调度程序将交替的调 度他们，可怜的 C 和 D 永远都没有机会运行，太气人了！ 当然，这只是展示了一些队列的静态快照，并不能让你 真正明白 MLFQ 的工作原理。我们需要理解工作的优先级如 何随时间变化。初次拿起本书阅读一章的人可能会吃惊，这 正是我们接下来要做的事。
如何改变优先级
我们必须决定，在一个工作的生命周期中，MLFQ 如何改变其优先级（在哪个队列中）。 要做到这一点，我们必须记得工作负载：既有运行时间很短、频繁放弃 CPU 的交互型工作， 也有需要很多 CPU 时间、响应时间却不重要的长时间计算密集型工作。下面是我们第一次 尝试优先级调整算法。
- 规则 3：工作进入系统时，放在最高优先级（最上层队列）。
- 规则 4a：工作用完整个时间片后，降低其优先级（移入下一个队列）。
- 规则 4b：如果工作在其时间片以内主动释放 CPU， 则优先级不变。
单个长工作
实例1
我们来看一些例子。首先，如果系统中有一个需要长 时间运行的工作，看看会发生什么。图 8.2 展示了在一个有 3 个队列的调度程序中，随着时间的推移，这个工作的运行 情况。 从这个例子可以看出，该工作首先进入最高优先级 （Q2）。执行一个 10ms 的时间片后，调度程序将工作的优先 级减 1，因此进入 Q1。在 Q1 执行一个时间片后，最终降低优先级进入系统的最低优先级 （Q0），一直留在那里。相当简单，不是吗？
实例2
再看一个较复杂的例子，看看 MLFQ 如何近似 SJF。在这个例子中，有两个工作：A 是一个长时间运行的 CPU 密集型工作，B 是一个运行时间很短的交互型工作。假设 A 执行 一段时间后 B 到达。会发生什么呢？对 B 来说，MLFQ 会近似于 SJF 吗？ 图 8.3 展示了这种场景的结果。A（用黑色表示）在最低优先级队列执行（长时间运行 的 CPU 密集型工作都这样）。B（用灰色表示）在时间 T=100 时到达，并被加入最高优先级 队列。由于它的运行时间很短（只有 20ms），经过两个时间片，在被移入最低优先级队列之 前，B 执行完毕。然后 A 继续运行（在低优先级）。 通过这个例子，你大概可以体会到这个算法的一个主要目标：如果不知道工作是短工 作还是长工作，那么就在开始的时候假设其是短工作，并赋予最高优先级。如果确实是短 工作，则很快会执行完毕，否则将被慢慢移入低优先级队列，而这时该工作也被认为是长 工作了。通过这种方式，MLFQ 近似于 SJF
实例3
看一个有 I/O 的例子。根据上述规则 4b，如果进程在时间片用完之前主动放弃 CPU， 则保持它的优先级不变。这条规则的意图很简单：假设交互型工作中有大量的 I/O 操作（比 如等待用户的键盘或鼠标输入），它会在时间片用完之前放弃 CPU。在这种情况下，我们不 想处罚它，只是保持它的优先级不变。 图 8.4 展示了这个运行过程，交互型工作 B（用灰色表示）每执行 1ms 便需要进行 I/O 操作，它与长时间运行的工作 A（用黑色表示）竞争 CPU。MLFQ 算法保持 B 在最高优先 级，因为 B 总是让出 CPU。如果 B 是交互型工作，MLFQ 就进一步实现了它的目标，让交 互型工作快速运行。
问题
至此，我们有了基本的 MLFQ。它看起来似乎相当不错，长工作之间可以公平地分享 CPU，又能给短工作或交互型工作很好的响应时间。然而，这种算法有一些非常严重的缺点。
你能想到吗？ （暂停一下，尽量让脑筋转转弯） 首先，会有饥饿（starvation）问题。如果系统有“太多”交互型工作，就会不断占用 CPU，导致长工作永远无法得到 CPU（它们饿死了）。即使在这种情况下，我们希望这些长 工作也能有所进展。 其次，聪明的用户会重写程序，愚弄调度程序（game the scheduler）。愚弄调度程序指 的是用一些卑鄙的手段欺骗调度程序，让它给你远超公平的资源。上述算法对如下的攻击 束手无策：进程在时间片用完之前，调用一个 I/O 操作（比如访问一个无关的文件），从而 主动释放 CPU。如此便可以保持在高优先级，占用更多的 CPU 时间。做得好时（比如，每 运行 99%的时间片时间就主动放弃一次 CPU），工作可以几乎独占 CPU。 最后，一个程序可能在不同时间表现不同。一个计算密集的进程可能在某段时间表现为 一个交互型的进程。用我们目前的方法，它不会享受系统中其他交互型工作的待遇。
提升优先级
让我们试着改变之前的规则，看能否避免饥饿问题。要让 CPU 密集型工作也能取得一 些进展（即使不多），我们能做些什么？ 一个简单的思路是周期性地提升（boost）所有工作的优先级。可以有很多方法做到， 但我们就用最简单的：将所有工作扔到最高优先级队列。于是有了如下的新规则。 规则 5：经过一段时间 S，就将系统中所有工作重新加入最高优先级队列。 新规则一下解决了两个问题。首先，进程不会饿死——在最高优先级队列中，它会以轮 转的方式，与其他高优先级工作分享 CPU，从而最终获得执行。其次，如果一个 CPU 密集 型工作变成了交互型，当它优先级提升时，调度程序会正确对待它。 我们来看一个例子。在这种场景下，我们展示长工作与两个交互型短工作竞争 CPU 时 的行为。图 8.5 包含两张图。左边没有优先级提升，长工作在两个短工作到达后被饿死。右 边每 50ms 就有一次优先级提升（这里只是举例，这个值可能过小），因此至少保证长工作 会有一些进展，每过 50ms 就被提升到最高优先级，从而定期获得执行。
当然，添加时间段 S 导致了明显的问题：S 的值应该如何设置？德高望重的系统研究
John Ousterhout[O11]曾将这种值称为“巫毒常量（voo-doo constant）”，因为似乎需要一些黑 魔法才能正确设置。如果 S 设置得太高，长工作会饥饿；如果设置得太低，交互型工作又 得不到合适的 CPU 时间比例。
更好的计时方式
现在还有一个问题要解决：如何阻止调度程序被愚弄？可以看出，这里的元凶是规则 4a 和 4b，导致工作在时间片以内释放 CPU，就保留它的优先级。那么应该怎么做？ 这里的解决方案，是为 MLFQ 的每层队列提供更完善的 CPU 计时方式（accounting）。 调度程序应该记录一个进程在某一层中消耗的总时间，而不是在调度时重新计时。只要进 程用完了自己的配额，就将它降到低一优先级的队列中去。不论它是一次用完的，还是拆 成很多次用完。因此，我们重写规则 4a 和 4b
规则 4：一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次 CPU），就降低其优先级（移入低一级队列）。 来看一个例子。图 8.6 对比了在规则 4a、4b 的策略下（左图），以及在新的规则 4（右 图）的策略下，同样试图愚弄调度程序的进程的表现。没有规则 4 的保护时，进程可以在 每个时间片结束前发起一次 I/O 操作，从而垄断 CPU 时间。有了这样的保护后，不论进程 的 I/O 行为如何，都会慢慢地降低优先级，因而无法获得超过公平的 CPU 时间比例。
MLFQ 调优及其他问题
关于 MLFQ 调度算法还有一些问题。其中一个大问题是如何配置一个调度程序，例如， 配置多少队列？每一层队列的时间片配置多大？为了避免饥饿问题以及进程行为改变，应 该多久提升一次进程的优先级？这些问题都没有显而易见的答案，因此只有利用对工作负 载的经验，以及后续对调度程序的调优，才会导致令人满意的平衡。 例如，大多数的 MLFQ 变体都支持不同队列可变的时间片长度。高优先级队列通常只 有较短的时间片（比如 10ms 或者更少），因而这一层的交互工作可以更快地切换。相反，低优先级队列中更多的是 CPU 密集型工作，配置更长的时间片会取得更好的效果。图 8.7 展示了一个例子，两个长工作在高优先级队列执行 10ms，中间队列执行 20ms，最后在最低 优先级队列执行 40ms。
提示：避免巫毒常量（Ousterhout 定律） 尽可能避免巫毒常量是个好主意。然而，从上面的例子可以看出，这通常很难。当然，我们也可以 让系统自己去学习一个很优化的值，但这同样也不容易。因此，通常我们会有一个写满各种参数值默认 值的配置文件，使得系统管理员可以方便地进行修改调整。然而，大多数使用者并不会去修改这些默认 值，这时就寄希望于默认值合适了。这个提示是由资深的 OS 教授 John Ousterhout 提出的，因此称为 Ousterhout 定律（Ousterhout’s Law）
Solaris 的 MLFQ 实现（时分调度类 TS）很容易配置。它提供了一组表来决定进程在其 生命周期中如何调整优先级，每层的时间片多大，以及多 久提升一个工作的优先级[AD00]。管理员可以通过这些 表，让调度程序的行为方式不同。该表默认有 60 层队列， 时间片长度从 20ms（最高优先级），到几百 ms（最低优 先级），每一秒左右提升一次进程的优先级。 其他一些 MLFQ 调度程序没用表，甚至没用本章中 讲到的规则，有些采用数学公式来调整优先级。例如， FreeBSD 调度程序（4.3 版本），会基于当前进程使用了多 少 CPU，通过公式计算某个工作的当前优先级[LM+89]。 另外，使用量会随时间衰减，这提供了期望的优先级提升，但与这里描述方式不同。阅读 Epema 的论文，他漂亮地概括了这种使用量衰减（decay-usage）算法及其特征[E95]。 最后，许多调度程序有一些我们没有提到的特征。例如，有些调度程序将最高优先级 队列留给操作系统使用，因此通常的用户工作是无法得到系统的最高优先级的。有些系统 允许用户给出优先级设置的建议（advice），比如通过命令行工具 nice，可以增加或降低工 作的优先级（稍微），从而增加或降低它在某个时刻运行的机会。更多信息请查看 man 手册。
提示：尽可能多地使用建议 操作系统很少知道什么策略对系统中的单个进程和每个进程算是好的，因此提供接口并允许用户或管理 员给操作系统一些提示（hint）常常很有用。我们通常称之为建议（advice），因为操作系统不一定要关注它， 但是可能会将建议考虑在内，以便做出更好的决定。这种用户建议的方式在操作系统中的各个领域经常十分 有用，包括调度程序（通过 nice）、内存管理（madvise），以及文件系统（通知预取和缓存[P+95]）。
本章包含了一组优化的 MLFQ 规则。为了方便查阅，我们重新列在这里
- 规则 1：如果 A 的优先级 > B 的优先级，运行 A（不运行 B）。
- 规则 2：如果 A 的优先级 = B 的优先级，轮转运行 A 和 B。
- 规则 3：工作进入系统时，放在最高优先级（最上层队列）。
- 规则 4：一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次 CPU），就降低其优先级（移入低一级队列）。
- 规则 5：经过一段时间 S，就将系统中所有工作重新加入最高优先级队列
MLFQ 有趣的原因是：它不需要对工作的运行方式有先验知识，而是通过观察工作的 运行来给出对应的优先级。通过这种方式，MLFQ 可以同时满足各种工作的需求：对于短 时间运行的交互型工作，获得类似于 SJF/STCF 的很好的全局性能，同时对长时间运行的 CPU 密集型负载也可以公平地、不断地稳步向前。因此，许多系统使用某种类型的 MLFQ 作为自己的基础调度程序，包括类 BSD UNIX 系统[LM+89，B86]、Solaris[M06]以及 Windows NT 和其后的 Window 系列操作系统
多核处理器调度
本章将介绍多处理器调度（multiprocessor scheduling）的基础知识。由于本章内容相对 较深，建议认真学习并发相关的内容后再读。 过去很多年，多处理器（multiprocessor）系统只存在于高端服务器中。现在，它们越来 越多地出现在个人 PC、笔记本电脑甚至移动设备上。多核处理器（multicore）将多个 CPU 核组装在一块芯片上，是这种扩散的根源。由于计算机的架构师们当时难以让单核 CPU 更 快，同时又不增加太多功耗，所以这种多核 CPU 很快就变得流行。现在，我们每个人都可 以得到一些 CPU，这是好事，对吧？ 当然，多核 CPU 带来了许多困难。主要困难是典型的应用程序（例如你写的很多 C 程 序）都只使用一个 CPU，增加了更多的 CPU 并没有让这类程序运行得更快。为了解决这个 问题，不得不重写这些应用程序，使之能并行（parallel）执行，也许使用多线程（thread， 本书的第 2 部分将用较多篇幅讨论）。多线程应用可以将工作分散到多个 CPU 上，因此 CPU 资源越多就运行越快。 补充：高级章节 需要阅读本书的更多内容才能真正理解高级章节，但这些内容在逻辑上放在一章里。例如，本章是 关于多处理器调度的，如果先学习了中间部分的并发知识，会更有意思。但是，从逻辑上它属于本书中 虚拟化（一般）和 CPU 调度（具体）的部分。因此，建议不按顺序学习这些高级章节。对于本章，建 议在本书第 2 部分之后学习。 除了应用程序，操作系统遇到的一个新的问题是（不奇怪！）多处理器调度（multiprocessor scheduling）。到目前为止，我们讨论了许多单处理器调度的原则，那么如何将这些想法扩展 到多处理器上呢？还有什么新的问题需要解决？因此，我们的问题如下。 关键问题：如何在多处理器上调度工作 操作系统应该如何在多 CPU 上调度工作？会遇到什么新问题？已有的技术依旧适用吗？是否需要 新的思路
多核处理器架构
为了理解多处理器调度带来的新问题，必须先知道它与单 CPU 之间的基本区别。区别 的核心在于对硬件缓存（cache）的使用（见图 10.1），以及多处理器之间共享数据的方式。 本章将在较高层面讨论这些问题。更多信息可以其他地方找到[CSG99]，尤其是在高年级或研究生计算机架构课程中。 在单 CPU 系统中，存在多级的硬件缓存（hardware cache），一般来说会让处理器更快 地执行程序。缓存是很小但很快的存储设备，通常拥有内存中最热的数据的备份。相比之 下，内存很大且拥有所有的数据，但访问速度较慢。通过将频繁访问的数据放在缓存中， 系统似乎拥有又大又快的内存。 举个例子，假设一个程序需要从内存中加载指令并读取一个值，系统只有一个 CPU， 拥有较小的缓存（如 64KB）和较大的内存。 程序第一次读取数据时，数据在内存中，因此需要花费较长的时间（可能数十或数百 纳秒）。处理器判断该数据很可能会被再次使用，因此将其放入 CPU 缓存中。如果之后程序 再次需要使用同样的数据，CPU 会先查找缓存。因为在缓存中找到了数据，所以取数据快 得多（比如几纳秒），程序也就运行更快。 缓存是基于局部性（locality）的概念，局部性有两种，即时间局部性和空间局部性。 时间局部性是指当一个数据被访问后，它很有可能会在不久的将来被再次访问，比如循 环代码中的数据或指令本身。而空间局部性指的是，当程序访问地址为 x 的数据时，很 有可能会紧接着访问 x 周围的数据，比如遍历数组或指令的顺序执行。由于这两种局部 性存在于大多数的程序中，硬件系统可以很好地预测哪些数据可以放入缓存，从而运行 得很好。 有趣的部分来了：如果系统有多个处理器，并共享同一个内存，如图 10.2 所示，会怎样呢？
事实证明，多 CPU 的情况下缓存要复杂得多。例如，假设一个运行在 CPU 1 上的程序 从内存地址 A 读取数据。由于不在 CPU 1 的缓存中，所以系统直接访问内存，得到值 D。 程序然后修改了地址 A 处的值，只是将它的缓存更新为新值 D'。将数据写回内存比较慢， 因此系统（通常）会稍后再做。假设这时操作系统中断了该程序的运行，并将其交给 CPU 2， 重新读取地址 A 的数据，由于 CPU 2 的缓存中并没有该数据，所以会直接从内存中读取， 得到了旧值 D，而不是正确的值 D'。哎呀！ 这一普遍的问题称为缓存一致性（cache coherence）问题，有大量的研究文献描述了解 决这个问题时的微妙之处[SHW11]。这里我们会略过所有的细节，只提几个要点。选一门计 算机体系结构课（或 3 门），你可以了解更多。 硬件提供了这个问题的基本解决方案：通过监控内存访问，硬件可以保证获得正确的 数据，并保证共享内存的唯一性。在基于总线的系统中，一种方式是使用总线窥探（bussnooping）[G83]。每个缓存都通过监听链接所有缓存和内存的总线，来发现内存访问。如 果 CPU 发现对它放在缓存中的数据的更新，会作废（invalidate）本地副本（从缓存中移除）， 或更新（update）它（修改为新值）。回写缓存，如上面提到的，让事情更复杂（由于对内 存的写入稍后才会看到），你可以想想基本方案如何工作.
同步
既然缓存已经做了这么多工作来提供一致性，应用程序（或操作系统）还需要关心 共享数据的访问吗？依然需要！本书第 2 部分关于并发的描述中会详细介绍。虽然这里 不会详细讨论，但我们会简单介绍（或复习）下其基本思路（假设你熟悉并发相关内容）。 跨 CPU 访问（尤其是写入）共享数据或数据结构时，需要使用互斥原语（比如锁），才 能保证正确性（其他方法，如使用无锁（lock-free）数据结构，很复杂，偶尔才使用。详情 参见并发部分关于死锁的章节）。例如，假设多 CPU 并发访问一个共享队列。如果没有锁， 即使有底层一致性协议，并发地从队列增加或删除元素，依然不会得到预期结果。需要用 锁来保证数据结构状态更新的原子性。 为了更具体，我们设想这样的代码序列，用于删除共享链表的一个元素，如图 10.3 所 示。假设两个 CPU 上的不同线程同时进入这个函数。如果线程 1 执行第一行，会将 head 的 当前值存入它的 tmp 变量。如果线程 2 接着也执行第一行，它也会将同样的 head 值存入它 自己的私有 tmp 变量（tmp 在栈上分配，因此每个线程都有自己的私有存储）。因此，两个 线程会尝试删除同一个链表头，而不是每个线程移除一个元素，这导致了各种问题（比如 在第 4 行重复释放头元素，以及可能两次返回同一个数据）。
1 typedef struct __Node_t {
2 int value;
3 struct __Node_t *next;
4 } Node_t;
5
6 int List_Pop() {
7 Node_t *tmp = head; // remember old head ...
8 int value = head->value; // ... and its value
9 head = head->next; // advance head to next pointer
10 free(tmp); // free old head
11 return value; // return value at head
12 }
图 10.3 简单的链表删除代码 当然，让这类函数正确工作的方法是加锁（locking）。这里只需要一个互斥锁（即 pthread_mutex_t m;），然后在函数开始时调用 lock(&m)，在结束时调用 unlock(&m)，确保代 码的执行如预期。我们会看到，这里依然有问题，尤其是性能方面。具体来说，随着 CPU 数量的增加，访问同步共享的数据结构会变得很慢
缓存亲合度
在设计多处理器调度时遇到的最后一个问题，是所谓的缓存亲和度（cache affinity）。这 个概念很简单：一个进程在某个 CPU 上运行时，会在该 CPU 的缓存中维护许多状态。下次 该进程在相同 CPU 上运行时，由于缓存中的数据而执行得更快。相反，在不同的 CPU 上执 行，会由于需要重新加载数据而很慢（好在硬件保证的缓存一致性可以保证正确执行）。因 此多处理器调度应该考虑到这种缓存亲和性，并尽可能将进程保持在同一个 CPU 上。
单队列调度
上面介绍了一些背景，现在来讨论如何设计一个多处理器系统的调度程序。最基本的 方式是简单地复用单处理器调度的基本架构，将所有需要调度的工作放入一个单独的队列 中，我们称之为单队列多处理器调度（Single Queue Multiprocessor Scheduling，SQMS）。这 个方法最大的优点是简单。它不需要太多修改，就可以将原有的策略用于多个 CPU，选择 最适合的工作来运行（例如，如果有两个 CPU，它可能选择两个最合适的工作）。 然而，SQMS 有几个明显的短板。第一个是缺乏可扩展性（scalability）。为了保证在多 CPU 上正常运行，调度程序的开发者需要在代码中通过加锁（locking）来保证原子性，如 上所述。在 SQMS 访问单个队列时（如寻找下一个运行的工作），锁确保得到正确的结果。 然而，锁可能带来巨大的性能损失，尤其是随着系统中的 CPU 数增加时[A91]。随着这 种单个锁的争用增加，系统花费了越来越多的时间在锁的开销上，较少的时间用于系统应 该完成的工作（哪天在这里加上真正的测量数据就好了）。 SQMS 的第二个主要问题是缓存亲和性。比如，假设我们有 5 个工作（A、B、C、D、 E）和 4 个处理器。调度队列如下：
一段时间后，假设每个工作依次执行一个时间片，然后选择另一个工作，下面是每个 CPU 可能的调度序列
由于每个 CPU 都简单地从全局共享的队列中选取下一个工作执行，因此每个工作都不 断在不同 CPU 之间转移，这与缓存亲和的目标背道而驰。 为了解决这个问题，大多数 SQMS 调度程序都引入了一些亲和度机制，尽可能让进程在同一个 CPU 上运行。保持一些工作的亲和度的同时，可能需要牺牲其他工作的亲和度来 实现负载均衡。例如，针对同样的 5 个工作的调度如下
这种调度中，A、B、C、D 这 4 个工作都保持在同一个 CPU 上，只有工作 E 不断地来 回迁移（migrating），从而尽可能多地获得缓存亲和度。为了公平起见，之后我们可以选择 不同的工作来迁移。但实现这种策略可能很复杂。 我们看到，SQMS 调度方式有优势也有不足。优势是能够从单 CPU 调度程序很简单地 发展而来，根据定义，它只有一个队列。然而，它的扩展性不好（由于同步开销有限），并 且不能很好地保证缓存亲和度。
多级队列
正是由于单队列调度程序的这些问题，有些系统使用了多队列的方案，比如每个 CPU 一个队列。我们称之为多队列多处理器调度（Multi-Queue Multiprocessor Scheduling，MQMS） 在 MQMS 中，基本调度框架包含多个调度队列，每个队列可以使用不同的调度规则， 比如轮转或其他任何可能的算法。当一个工作进入系统后，系统会依照一些启发性规则（如 随机或选择较空的队列）将其放入某个调度队列。这样一来，每个 CPU 调度之间相互独立， 就避免了单队列的方式中由于数据共享及同步带来的问题。 例如，假设系统中有两个 CPU（CPU 0 和 CPU 1）。这时一些工作进入系统：A、B、C 和 D。由于每个 CPU 都有自己的调度队列，操作系统需要决定每个工作放入哪个队列。可 能像下面这样做：
根据不同队列的调度策略，每个 CPU 从两个工作中选择，决定谁将运行。例如，利用 轮转，调度结果可能如下所示
根据不同队列的调度策略，每个 CPU 从两个工作中选择，决定谁将运行。例如，利用 轮转，调度结果可能如下所示
MQMS 比 SQMS 有明显的优势，它天生更具有可扩展性。队列的数量会随着 CPU 的增 加而增加，因此锁和缓存争用的开销不是大问题。此外，MQMS 天生具有良好的缓存亲和 度。所有工作都保持在固定的 CPU 上，因而可以很好地利用缓存数据。 但是，如果稍加注意，你可能会发现有一个新问题（这在多队列的方法中是根本的）， 即负载不均（load imbalance）。假定和上面设定一样（4 个工作，2 个 CPU），但假设一个工
作（如 C）这时执行完毕。现在调度队列如下：
Q0->A Q1->B->D
如果对系统中每个队列都执行轮转调度策略，会获得如下调度结果
所以可怜的多队列多处理器调度程序应该怎么办呢？怎样才能克服潜伏的负载不均问 题，打败邪恶的……霸天虎军团关键问题：如何应对负载不均 多队列多处理器调度程序应该如何处理负载不均问题，从而更好地实现预期的调度目标？ 最明显的答案是让工作移动，这种技术我们称为迁移（migration）。通过工作的跨 CPU 迁移，可以真正实现负载均衡。 来看两个例子就更清楚了。同样，有一个 CPU 空闲，另一个 CPU 有一些工作。 在这种情况下，期望的迁移很容易理解：操作系统应该将 B 或 D 迁移到 CPU0。这次 工作迁移导致负载均衡，皆大欢喜。 更棘手的情况是较早一些的例子，A 独自留在 CPU 0 上，B 和 D 在 CPU 1 上交替运行。 在这种情况下，单次迁移并不能解决问题。应该怎么做呢？答案是不断地迁移一个或 多个工作。一种可能的解决方案是不断切换工作，如下面的时间线所示。可以看到，开始 的时候 A 独享 CPU 0，B 和 D 在 CPU 1。一些时间片后，B 迁移到 CPU 0 与 A 竞争，D 则 独享 CPU 1 一段时间。这样就实现了负载均衡。如何才能不要问这些与这本好书几乎无关的问题？
当然，还有其他不同的迁移模式。但现在是最棘手的部分：系统如何决定发起这样的迁移？ 一个基本的方法是采用一种技术，名为工作窃取（work stealing）[FLR98]。通过这种方法， 工作量较少的（源）队列不定期地“偷看”其他（目标）队列是不是比自己的工作多。如果目 标队列比源队列（显著地）更满，就从目标队列“窃取”一个或多个工作，实现负载均衡。 当然，这种方法也有让人抓狂的地方——如果太频繁地检查其他队列，就会带来较高的 开销，可扩展性不好，而这是多队列调度最初的全部目标！相反，如果检查间隔太长，又 可能会带来严重的负载不均。找到合适的阈值仍然是黑魔法，这在系统策略设计中很常见。
Linux 多处理器调度
有趣的是，在构建多处理器调度程序方面，Linux 社区一直没有达成共识。一直以来， 存在 3 种不同的调度程序：O(1)调度程序、完全公平调度程序（CFS）以及 BF 调度程序（BFS） ①。从 Meehean 的论文中可以找到对这些不同调度程序优缺点的对比总结[M11]。这里我们 只总结一些基本知识。 O(1) CFS 采用多队列，而 BFS 采用单队列，这说明两种方法都可以成功。当然它们之 间还有很多不同的细节。例如，O(1)调度程序是基于优先级的（类似于之前介绍的 MLFQ）， 随时间推移改变进程的优先级，然后调度最高优先级进程，来实现各种调度目标。交互性 得到了特别关注。与之不同，CFS 是确定的比例调度方法（类似之前介绍的步长调度）。BFS 作为三个算法中唯一采用单队列的算法，也基于比例调度，但采用了更复杂的方案，称为 最早最合适虚拟截止时间优先算法（EEVEF）[SA96]读者可以自己去了解这些现代操作系 统的调度算法，现在应该能够理解它们的工作原理了
地址空间
早期，构建计算机操作系统非常简单。你可能会问，为什么？因为用户对操作系统的 期望不高。然而一些烦人的用户提出要“易于使用”“高性能”“可靠性”等，这导致了所 有这些令人头痛的问题。下次你见到这些用户的时候，应该感谢他们，他们是这些问题的 根源
早期系统
从内存来看，早期的机器并没有提供多少抽象给用户。基本上，机器的物理内存看起来 如图 13.1 所示。 操作系统曾经是一组函数（实际上是一个库），在内存中（在 本例中，从物理地址 0 开始），然后有一个正在运行的程序（进 程），目前在物理内存中（在本例中，从物理地址 64KB 开始）， 并使用剩余的内存。这里几乎没有抽象，用户对操作系统的要 求也不多。那时候，操作系统开发人员的生活确实很容易，不 是吗？
多道程序和时分共享
过了一段时间，由于机器昂贵，人们开始更有效地共享机器。因此，多道程序 （multiprogramming）系统时代开启[DV66]，其中多个进程在给定时间准备运行，比如当有 一个进程在等待 I/O 操作的时候，操作系统会切换这些进程，这样增加了 CPU 的有效利用 率（utilization）。那时候，效率（efficiency）的提高尤其重要，因为每台机器的成本是数十 万美元甚至数百万美元（现在你觉得你的 Mac 很贵！） 但很快，人们开始对机器要求更多，分时系统的时代诞生了[S59，L60，M62，M83]。 具体来说，许多人意识到批量计算的局限性，尤其是程序员本身[CV65]，他们厌倦了长时 间的（因此也是低效率的）编程—调试循环。交互性（interactivity）变得很重要，因为许多 用户可能同时在使用机器，每个人都在等待（或希望）他们执行的任务及时响应。 一种实现时分共享的方法，是让一个进程单独占用全部内存运行一小段时间（见图 13.1），然后停止它，并将它所有的状态信息保存在磁盘上（包含所有的物理内存），加载其 他进程的状态信息，再运行一段时间，这就实现了某种比较粗糙的机器共享[M+63]。 遗憾的是，这种方法有一个问题：太慢了，特别是当内存增长的时候。虽然保存和恢复寄存器级的状态信息（程序计数器、通用寄存器等）相对较 快，但将全部的内存信息保存到磁盘就太慢了。因此，在进程 切换的时候，我们仍然将进程信息放在内存中，这样操作系统 可以更有效率地实现时分共享（见图 13.2）。 在图 13.2 中，有 3 个进程（A、B、C），每个进程拥有从 512KB 物理内存中切出来给它们的一小部分内存。假定只有一 个 CPU，操作系统选择运行其中一个进程（比如 A），同时其 他进程（B 和 C）则在队列中等待运行。 随着时分共享变得更流行，人们对操作系统又有了新的要 求。特别是多个程序同时驻留在内存中，使保护（protection） 成为重要问题。人们不希望一个进程可以读取其他进程的内 存，更别说修改了
地址空间
然而，我们必须将这些烦人的用户的需求放在心上。因此操作系统需要提供一个易用 （easy to use）的物理内存抽象。这个抽象叫作地址空间（address space），是运行的程序看到 的系统中的内存。理解这个基本的操作系统内存抽象，是了解内存虚拟化的关键。 一个进程的地址空间包含运行的程序的所有内存状态。比如：程序的代码（code，指令） 必须在内存中，因此它们在地址空间里。当程序在运行的时候，利用栈（stack）来保存当 前的函数调用信息，分配空间给局部变量，传递参数和函数返回值。最后，堆（heap）用于 管理动态分配的、用户管理的内存，就像你从 C 语言中调用 malloc()或面向对象语言（如 C ++ 或 Java）中调用 new 获得内存。当然，还有其 他的东西（例如，静态初始化的变量），但现在 假设只有这 3 个部分：代码、栈和堆。 在图 13.3 的例子中，我们有一个很小的地址 空间① （只有 16KB）。程序代码位于地址空间的 顶部（在本例中从 0 开始，并且装入到地址空间 的前 1KB）。代码是静态的（因此很容易放在内 存中），所以可以将它放在地址空间的顶部，我 们知道程序运行时不再需要新的空间。 接下来，在程序运行时，地址空间有两个区 域可能增长（或者收缩）。它们就是堆（在顶部） 和栈（在底部）。把它们放在那里，是因为它们都希望能够增长。通过将它们放在地址空间 的两端，我们可以允许这样的增长：它们只需要在相反的方向增长。因此堆在代码（1KB） 之下开始并向下增长（当用户通过 malloc()请求更多内存时），栈从 16KB 开始并向上增长
（当用户进行程序调用时）。然而，堆栈和堆的这种放置方法只是一种约定，如果你愿意， 可以用不同的方式安排地址空间 [稍后我们会看到，当多个线程（threads）在地址空间中共 存时，就没有像这样分配空间的好办法了]。 当然，当我们描述地址空间时，所描述的是操作系统提供给运行程序的抽象（abstract）。 程序不在物理地址 0～16KB 的内存中，而是加载在任意的物理地址。回顾图 13.2 中的进程 A、B 和 C，你可以看到每个进程如何加载到内存中的不同地址。因此问题来了：
关键问题：如何虚拟化内存 操作系统如何在单一的物理内存上为多个运行的进程（所有进程共享内存）构建一个私有的、可能 很大的地址空间的抽象？
当操作系统这样做时，我们说操作系统在虚拟化内存（virtualizing memory），因为运行 的程序认为它被加载到特定地址（例如 0）的内存中，并且具有非常大的地址空间（例如 32 位或 64 位）。现实很不一样。 例如，当图 13.2 中的进程 A 尝试在地址 0（我们将称其为虚拟地址，virtual address） 执行加载操作时，然而操作系统在硬件的支持下，出于某种原因，必须确保不是加载到物 理地址 0，而是物理地址 320KB（这是 A 载入内存的地址）。这是内存虚拟化的关键，这是 世界上每一个现代计算机系统的基础。
提示：隔离原则 隔离是建立可靠系统的关键原则。如果两个实体相互隔离，这意味着一个实体的失败不会影响另一 个实体。操作系统力求让进程彼此隔离，从而防止相互造成伤害。通过内存隔离，操作系统进一步确保 运行程序不会影响底层操作系统的操作。一些现代操作系统通过将某些部分与操作系统的其他部分分 离，实现进一步的隔离。这样的微内核（microkernel）[BH70，R+89，S+03] 可以比整体内核提供更大 的可靠性。
目标
在这一章中，我们触及操作系统的工作——虚拟化内存。操作系统不仅虚拟化内存， 还有一定的风格。为了确保操作系统这样做，我们需要一些目标来指导。以前我们已经看 过这些目标（想想本章的前言），我们会再次看到它们，但它们肯定是值得重复的。 虚拟内存（VM）系统的一个主要目标是透明（transparency）①。操作系统实现虚拟内 存的方式，应该让运行的程序看不见。因此，程序不应该感知到内存被虚拟化的事实，相 反，程序的行为就好像它拥有自己的私有物理内存。在幕后，操作系统（和硬件）完成了 所有的工作，让不同的工作复用内存，从而实现这个假象
虚拟内存的另一个目标是效率（efficiency）。操作系统应该追求虚拟化尽可能高效 （efficient），包括时间上（即不会使程序运行得更慢）和空间上（即不需要太多额外的内存 来支持虚拟化）。在实现高效率虚拟化时，操作系统将不得不依靠硬件支持，包括 TLB 这样 的硬件功能（我们将在适当的时候学习）。 最后，虚拟内存第三个目标是保护（protection）。操作系统应确保进程受到保护（protect）， 不会受其他进程影响，操作系统本身也不会受进程影响。当一个进程执行加载、存储或指 令提取时，它不应该以任何方式访问或影响任何其他进程或操作系统本身的内存内容（即 在它的地址空间之外的任何内容）。因此，保护让我们能够在进程之间提供隔离（isolation） 的特性，每个进程都应该在自己的独立环境中运行，避免其他出错或恶意进程的影响。
补充：你看到的所有地址都不是真的 写过打印出指针的 C 程序吗？你看到的值（一些大数字，通常以十六进制打印）是虚拟地址（virtual address）。有没有想过你的程序代码在哪里找到？你也可以打印出来，是的，如果你可以打印它，它也 是一个虚拟地址。实际上，作为用户级程序的程序员，可以看到的任何地址都是虚拟地址。只有操作系 统，通过精妙的虚拟化内存技术，知道这些指令和数据所在的物理内存的位置。所以永远不要忘记：如 果你在一个程序中打印出一个地址，那就是一个虚拟的地址。虚拟地址只是提供地址如何在内存中分布 的假象，只有操作系统（和硬件）才知道物理地址。。所有 这些地址都是虚拟的，并且将由操作系统和硬件翻译成物理地址，以便从真实的物理位置获取该地址的值
在接下来的章节中，我们将重点介绍虚拟化内存所需的基本机制（mechanism），包括 硬件和操作系统的支持。我们还将研究一些较相关的策略（policy），你会在操作系统中遇 到它们，包括如何管理可用空间，以及在空间不足时哪些页面该释放。通过这些内容，你 会逐渐理解现代虚拟内存系统真正的工作原理①
地址转换（一般不用）
在实现 CPU 虚拟化时，我们遵循的一般准则被称为受限直接访问（Limited Direct Execution，LDE）。LDE 背后的想法很简单：让程序运行的大部分指令直接访问硬件，只在 一些关键点（如进程发起系统调用或发生时钟中断）由操作系统介入来确保“在正确时间， 正确的地点，做正确的事”。为了实现高效的虚拟化，操作系统应该尽量让程序自己运行， 同时通过在关键点的及时介入（interposing），来保持对硬件的控制。高效和控制是现代操 作系统的两个主要目标。 在实现虚拟内存时，我们将追求类似的战略，在实现高效和控制的同时，提供期望的 虚拟化。高效决定了我们要利用硬件的支持，这在开始的时候非常初级（如使用一些寄存 器），但会变得相当复杂（比如我们会讲到的 TLB、页表等）。控制意味着操作系统要确保 应用程序只能访问它自己的内存空间。因此，要保护应用程序不会相互影响，也不会影响 操作系统，我们需要硬件的帮助。最后，我们对虚拟内存还有一点要求，即灵活性。具体 来说，我们希望程序能以任何方式访问它自己的地址空间，从而让系统更容易编程。所以， 关键问题在于： 关键问题：如何高效、灵活地虚拟化内存 如何实现高效的内存虚拟化？如何提供应用程序所需的灵活性？如何保持控制应用程序可访问的 内存位置，从而确保应用程序的内存访问受到合理的限制？如何高效地实现这一切？ 我们利用了一种通用技术，有时被称为基于硬件的地址转换（hardware-based address translation），简称为地址转换（address translation）。它可以看成是受限直接执行这种一般方 法的补充。利用地址转换，硬件对每次内存访问进行处理（即指令获取、数据读取或写 入），将指令中的虚拟（virtual）地址转换为数据实际存储的物理（physical）地址。因此， 在每次内存引用时，硬件都会进行地址转换，将应用程序的内存引用重定位到内存中实际 的位置。 当然，仅仅依靠硬件不足以实现虚拟内存，因为它只是提供了底层机制来提高效率。 操作系统必须在关键的位置介入，设置好硬件，以便完成正确的地址转换。因此它必须管 理内存（manage memory），记录被占用和空闲的内存位置，并明智而谨慎地介入，保持对 内存使用的控制。 同样，所有这些工作都是为了创造一种美丽的假象：每个程序都拥有私有的内存，那 里存放着它自己的代码和数据。虚拟现实的背后是丑陋的物理事实：许多程序其实是在同 一时间共享着内存，就像 CPU（或多个 CPU）在不同的程序间切换运行。通过虚拟化， 操作系统（在硬件的帮助下）将丑陋的机器现实转化成一种有用的、强大的、易于使用的 抽象。
例子
为了更好地理解实现地址转换需要什么，以及为什么需要，我们先来看一个简单的例子。 设想一个进程的地址空间如图 15.1 所示。这里我们要检查一小段代码，它从内存中加载一 个值，对它加 3，然后将它存回内存。你可以设想，这段代码的 C 语言形式可能像这样
void func() {
int x;
x = x + 3; // this is the line of code we are interested in编译器将这行代码转化为汇编语句，可能像下面这样（x86 汇编）。我们可以用 Linux 的 objdump 或者 Mac 的 otool 将它反汇编：
128: movl 0x0(%ebx), %eax ;load 0+ebx into eax
132: addl $0x03, %eax ;add 3 to eax register
135: movl %eax, 0x0(%ebx) ;store eax back to mem这段代码相对简单，它假定 x 的地址已经存入寄存器 ebx，之后通过 movl 指令将这个 地址的值加载到通用寄存器 eax（长字移动）。下一条指令对 eax 的内容加 3。最后一条指令 将 eax 中的值写回到内存的同一位置。
提示：介入（Interposition）很强大 介入是一种很常见又很有用的技术，计算机系统中使用介入常常能带来很好的效果。在虚拟内存中， 硬件可以介入到每次内存访问中，将进程提供的虚拟地址转换为数据实际存储的物理地址。但是，一般 化的介入技术有更广阔的应用空间，实际上几乎所有良好定义的接口都应该提供功能介入机制，以便增 加功能或者在其他方面提升系统。这种方式最基本的优点是透明（transparency），介入完成时通常不需 要改动接口的客户端，因此客户端不需要任何改动
在图 15.1 中，可以看到代码和数据都位于进程的地址空间，3 条指令序列位于地址 128 （靠近头部的代码段），变量 x 的值位于地址 15KB（在靠近底部的栈中）。如图 15.1 所示，x 的初始值是 3000
如果这 3 条指令执行，从进程的角度来看，发生了以下几次内存访问：
- 从地址 128 获取指令；
- 执行指令（从地址 15KB 加载数据）；
- 从地址 132 获取命令； 执行命令（没有内存访问）；
- 从地址 135 获取指令； 执行指令（新值存入地址 15KB）。
从程序的角度来看，它的地址空间（address space）从 0 开始到 16KB 结束。它包含的 所有内存引用都应该在这个范围内。然而，对虚拟内存来说，操作系统希望将这个进程地 址空间放在物理内存的其他位置，并不一定从地址 0 开始。因此我们遇到了如下问题：怎 样在内存中重定位这个进程，同时对该进程透明（transparent）？怎么样提供一种虚拟地址 空间从 0 开始的假象，而实际上地址空间位于另外某个物理地址？ 图 15.2 展示了一个例子，说明这个进程的地址空间被放入物理内存后可能的样子。从 图 15.2 中可以看到，操作系统将第一块物理内存留给了自己，并将上述例子中的进程地址空 间重定位到从 32KB 开始的物理内存地址。剩下的两块内存空闲（16～32KB 和 48～64KB）
动态（基于硬件）重定位
为了更好地理解基于硬件的地址转换，我们先来讨论它的第一次应用。在 20 世纪 50 年代后期，它在首次出现的时分机器中引入，那时只是一个简单的思想，称为基址加界限 机制（base and bound），有时又称为动态重定位（dynamic relocation），我们将互换使用这两 个术语[SS74]。 具体来说，每个 CPU 需要两个硬件寄存器：基址（base）寄存器和界限（bound）寄存 器，有时称为限制（limit）寄存器。这组基址和界限寄存器，让我们能够将地址空间放在物 理内存的任何位置，同时又能确保进程只能访问自己的地址空间。 采用这种方式，在编写和编译程序时假设地址空间从零开始。但是，当程序真正执行时， 操作系统会决定其在物理内存中的实际加载地址，并将起始地址记录在基址寄存器中。在上 面的例子中，操作系统决定加载在物理地址 32KB 的进程，因此将基址寄存器设置为这个值。 当进程运行时，有趣的事情发生了。现在，该进程产生的所有内存引用，都会被处理 器通过以下方式转换为物理地址： physical address = virtual address + base 补充：基于软件的重定位 在早期，在硬件支持重定位之前，一些系统曾经采用纯软件的重定位方式。基本技术被称为静态重 定位（static relocation），其中一个名为加载程序（loader）的软件接手将要运行的可执行程序，将它的 地址重写到物理内存中期望的偏移位置。 例如，程序中有一条指令是从地址 1000 加载到寄存器（即 movl 1000，%eax），当整个程序的地址 空间被加载到从 3000（不是程序认为的 0）开始的物理地址中，加载程序会重写指令中的地址（即 movl 4000, %eax），从而完成简单的静态重定位。 然而，静态重定位有许多问题，首先也是最重要的是不提供访问保护，进程中的错误地址可能导致 对其他进程或操作系统内存的非法访问，一般来说，需要硬件支持来实现真正的访问保护[WL+93]。静 态重定位的另一个缺点是一旦完成，稍后很难将内存空间重定位到其他位置 [M65]。 进程中使用的内存引用都是虚拟地址（virtual address），硬件接下来将虚拟地址加上基 址寄存器中的内容，得到物理地址（physical address），再发给内存系统。 为了更好地理解，让我们追踪一条指令执行的情况。具体来看前面序列中的一条指令： 128: movl 0x0(%ebx), %eax 程序计数器（PC）首先被设置为 128。当硬件需要获取这条指令时，它先将这个值加上基 址寄存器中的 32KB(32768)，得到实际的物理地址 32896，然后硬件从这个物理地址获取指令。 接下来，处理器开始执行该指令。这时，进程发起从虚拟地址 15KB 的加载，处理器同样将虚 拟地址加上基址寄存器内容（32KB），得到最终的物理地址 47KB，从而获得需要的数据。 将虚拟地址转换为物理地址，这正是所谓的地址转换（address translation）技术。也就 是说，硬件取得进程认为它要访问的地址，将它转换成数据实际位于的物理地址。由于这种重定位是在运行时发生的，而且我们甚至可以在进程开始运行后改变其地址空间，这种 技术一般被称为动态重定位（dynamic relocation）[M65]。
提示：基于硬件的动态重定位 在动态重定位的过程中，只有很少的硬件参与，但获得了很好的效果。一个基址寄存器将虚拟地址 转换为物理地址，一个界限寄存器确保这个地址在进程地址空间的范围内。它们一起提供了既简单又高 效的虚拟内存机制。
现在你可能会问，界限（限制）寄存器去哪了？不是基址加界限机制吗？正如你猜测 的那样，界限寄存器提供了访问保护。在上面的例子中，界限寄存器被置为 16KB。如果进 程需要访问超过这个界限或者为负数的虚拟地址，CPU 将触发异常，进程最终可能被终止。 界限寄存器的用处在于，它确保了进程产生的所有地址都在进程的地址“界限”中。 这种基址寄存器配合界限寄存器的硬件结构是芯片中的（每个 CPU 一对）。有时我们将 CPU 的这个负责地址转换的部分统称为内存管理单元（Memory Management Unit，MMU）。 随着我们开发更复杂的内存管理技术，MMU 也将有更复杂的电路和功能。 关于界限寄存器再补充一点，它通常有两种使用方式。在一种方式中（像上面那样），它记 录地址空间的大小，硬件在将虚拟地址与基址寄存器内容求和前，就检查这个界限。另一种方 式是界限寄存器中记录地址空间结束的物理地址，硬件在转化虚拟地址到物理地址之后才去检 查这个界限。
通过基址加虚拟地址（可以看作是地址空间的偏移量）的方式， 很容易得到物理地址。虚拟地址“过大”或者为负数时，会导致异常
补充：数据结构——空闲列表 操作系统必须记录哪些空闲内存没有使用，以便能够为进程分配内存。很多不同的数据结构可以用 于这项任务，其中最简单的（也是我们假定在这里采用的）是空闲列表（free list）。它就是一个列表， 记录当前没有使用的物理内存的范围。
硬件支持
我们来总结一下需要的硬件支持（见表 15.2）。首先，正如在 CPU 虚拟化的章节中提到 的，我们需要两种 CPU 模式。操作系统在特权模式（privileged mode，或内核模式，kernel mode），可以访问整个机器资源。应用程序在用户模式（user mode）运行，只能做有限的操 作。只要一个位，也许保存在处理器状态字（processor status word）中，就能说明当前的 CPU 运行模式。在一些特殊的时刻（如系统调用、异常或中断），CPU 会切换状态。
硬件还必须提供基址和界限寄存器（base and bounds register），因此每个 CPU 的内存管 理单元（Memory Management Unit，MMU）都需要这两个额外的寄存器。用户程序运行时， 硬件会转换每个地址，即将用户程序产生的虚拟地址加上基址寄存器的内容。硬件也必须 能检查地址是否有用，通过界限寄存器和 CPU 内的一些电路来实现。 硬件应该提供一些特殊的指令，用于修改基址寄存器和界限寄存器，允许操作系统在 切换进程时改变它们。这些指令是特权（privileged）指令，只有在内核模式下，才能修改 这些寄存器。想象一下，如果用户进程在运行时可以随意更改基址寄存器，那么用户进程 可能会造成严重破坏①。想象一下吧！然后迅速将这些阴暗的想法从你的头脑中赶走，因为 它们很可怕，会导致噩梦。 最后，在用户程序尝试非法访问内存（越界访问）时，CPU必须能够产生异常（exception）。 在这种情况下，CPU 应该阻止用户程序的执行，并安排操作系统的“越界”异常处理程序 （exception handler）去处理。操作系统的处理程序会做出正确的响应，比如在这种情况下终 止进程。类似地，如果用户程序尝试修改基址或者界限寄存器时，CPU 也应该产生异常， 并调用“用户模式尝试执行特权指令”的异常处理程序。CPU 还必须提供一种方法，来通 知它这些处理程序的位置，因此又需要另一些特权指令。
操作系统的问题
为了支持动态重定位，硬件添加了新的功能，使得操作系统有了一些必须处理的新问
题。硬件支持和操作系统管理结合在一起，实现了一个简单的虚拟内存。具体来说，在一 些关键的时刻操作系统需要介入，以实现基址和界限方式的虚拟内存，见表 15.3。 第一，在进程创建时，操作系统必须采取行动，为进程的地址空间找到内存空间。由 于我们假设每个进程的地址空间小于物理内存的大小，并且大小相同，这对操作系统来说 很容易。它可以把整个物理内存看作一组槽块，标记了空闲或已用。当新进程创建时，操 作系统检索这个数据结构（常被称为空闲列表，free list），为新地址空间找到位置，并将其 标记为已用。如果地址空间可变，那么生活就会更复杂，我们将在后续章节中讨论。 我们来看一个例子。在图 15.2 中，操作系统将物理内存的第一个槽块分配给自己，然 后将例子中的进程重定位到物理内存地址 32KB。另两个槽块（16～32KB，48～64KB）空 闲，因此空闲列表（free list）就包含这两个槽块。 第二，在进程终止时（正常退出，或因行为不端被强制终止），操作系统也必须做一些 工作，回收它的所有内存，给其他进程或者操作系统使用。在进程终止时，操作系统会将 这些内存放回到空闲列表，并根据需要清除相关的数据结构。 第三，在上下文切换时，操作系统也必须执行一些额外的操作。每个 CPU 毕竟只有一 个基址寄存器和一个界限寄存器，但对于每个运行的程序，它们的值都不同，因为每个程 序被加载到内存中不同的物理地址。因此，在切换进程时，操作系统必须保存和恢复基础 和界限寄存器。具体来说，当操作系统决定中止当前的运行进程时，它必须将当前基址和 界限寄存器中的内容保存在内存中，放在某种每个进程都有的结构中，如进程结构（process structure）或进程控制块（Process Control Block，PCB）中。类似地，当操作系统恢复执行 某个进程时（或第一次执行），也必须给基址和界限寄存器设置正确的值。
需要注意，当进程停止时（即没有运行），操作系统可以改变其地址空间的物理位置，这 很容易。要移动进程的地址空间，操作系统首先让进程停止运行，然后将地址空间拷贝到新 位置，最后更新保存的基址寄存器（在进程结构中），指向新位置。当该进程恢复执行时，它 的（新）基址寄存器会被恢复，它再次开始运行，显然它的指令和数据都在新的内存位置了。 第四，操作系统必须提供异常处理程序（exception handler），或要一些调用的函数，像 上面提到的那样。操作系统在启动时加载这些处理程序（通过特权命令）。例如，当一个进 程试图越界访问内存时，CPU 会触发异常。在这种异常产生时，操作系统必须准备采取行 动。通常操作系统会做出充满敌意的反应：终止错误进程。操作系统应该尽力保护它运行 的机器，因此它不会对那些企图访问非法地址或执行非法指令的进程客气。再见了，行为 不端的进程，很高兴认识你。 表 15.4 为按时间线展示了大多数硬件与操作系统的交互。可以看出，操作系统在启动时做了什么，为我们准备好机器，然后在进程（进程 A）开始运行时发生了什么。请注意，地 址转换过程完全由硬件处理，没有操作系统的介入。在这个时候，发生时钟中断，操作系统 切换到进程 B 运行，它执行了“错误的加载”（对一个非法内存地址），这时操作系统必须介 入，终止该进程，清理并释放进程 B 占用的内存，将它从进程表中移除。从表中可以看出， 我们仍然遵循受限直接访问（limited direct execution）的基本方法，大多数情况下，操作系统 正确设置硬件后，就任凭进程直接运行在 CPU 上，只有进程行为不端时才介入.
| 操作系统@启动（内核模式） | 硬件 | |
|---|---|---|
| 初始化陷阱表 | ||
| 记住以下地址： 系统调用处理程序 时钟处理程序 非法内存处理程序 非常指令处理程序 | ||
| 开始中断时钟 | ||
| 开始时钟，在 x ms 后中断 | ||
| 初始化进程表 初始化空闲列表 | ||
| 操作系统@运行（核心模式） | 硬件 | 程序（用户模式 |
| 为了启动进程 A： 在进程表中分配条目 为进程分配内存 设置基址/界限寄存器 从陷阱返回（进入 A） | ||
| 恢复 A 的寄存器 转向用户模式 跳到 A（最初）的程序计数器 | ||
| 进程 A 运行 获取指令 | ||
| 转换虚拟地址并执行获取 | ||
| 执行指令 | ||
| 如果显式加载/保存 确保地址不越界 转换虚拟地址并执行 加载/保存 | ||
| …… | ||
| 时钟中断 转向内核模式 跳到中断处理程序 | ||
| 处理陷阱 调用 switch()例程 将寄存器（A）保存到进程结构（A） （包括基址/界限） 从进程结构（B）恢复寄存器（B） （包括基址/界限） 从陷阱返回（进入 B） | ||
| 恢复 B 的寄存器 转向用户模式 跳到 B 的程序计数器 | ||
| 进程 B 运行 执行错误的加载 | ||
| 加载越界 转向内核模式 跳到陷阱处理程序 | ||
| 处理本期报告 决定终止进程 B 回收 B 的内存 移除 B 在进程表中的条目 |
本章通过虚拟内存使用的一种特殊机制，即地址转换（address translation），扩展了受限 直接访问的概念。利用地址转换，操作系统可以控制进程的所有内存访问，确保访问在地 址空间的界限内。这个技术高效的关键是硬件支持，硬件快速地将所有内存访问操作中的 虚拟地址（进程自己看到的内存位置）转换为物理地址（实际位置）。所有的这一切对进程 来说都是透明的，进程并不知道自己使用的内存引用已经被重定位，制造了美妙的假象。 我们还看到了一种特殊的虚拟化方式，称为基址加界限的动态重定位。基址加界限的 虚拟化方式非常高效，因为只需要很少的硬件逻辑，就可以将虚拟地址和基址寄存器加起 来，并检查进程产生的地址没有越界。基址加界限也提供了保护，操作系统和硬件的协作， 确保没有进程能够访问其地址空间之外的内容。保护肯定是操作系统最重要的目标之一。 没有保护，操作系统不可能控制机器（如果进程可以随意修改内存，它们就可以轻松地做 出可怕的事情，比如重写陷阱表并完全接管系统）。 遗憾的是，这个简单的动态重定位技术有效率低下的问题。例如，从图 15.2 中可以看到，
重定位的进程使用了从 32KB 到 48KB 的物理内存，但由于该进程的栈区和堆区并不很大， 导致这块内存区域中大量的空间被浪费。这种浪费通常称为内部碎片（internal fragmentation）， 指的是已经分配的内存单元内部有未使用的空间（即碎片），造成了浪费。在我们当前的方式 中，即使有足够的物理内存容纳更多进程，但我们目前要求将地址空间放在固定大小的槽块 中，因此会出现内部碎片①。所以，我们需要更复杂的机制，以便更好地利用物理内存，避免 内部碎片。第一次尝试是将基址加界限的概念稍稍泛化，得到分段（segmentation）的概念， 我们接下来将讨论。
分段
到目前为止，我们一直假设将所有进程的地址空间完整地加载到内存中。利用基址和 界限寄存器，操作系统很容易将不同进程重定位到不同的物理内存区域。但是，对于这些 内存区域，你可能已经注意到一件有趣的事：栈和堆之间，有一大块“空闲”空间。 从图 16.1 中可知，如果我们将整个地址空间放入物理内存，那么栈和堆之间的空间并 没有被进程使用，却依然占用了实际的物理内存。因此，简单的通过基址寄存器和界限寄 存器实现的虚拟内存很浪费。另外，如果剩余物理内存无法提供连续区域来放置完整的地 址空间，进程便无法运行。这种基址加界限的方式看来并不像我们期望的那样灵活。因此：
关键问题：怎样支持大地址空间 怎样支持大地址空间，同时栈和堆之间（可能）有大量空闲空间？在之前的例子里，地址空间非常 小，所以这种浪费并不明显。但设想一个 32 位（4GB）的地址空间，通常的程序只会使用几兆的内存， 但需要整个地址空间都放在内存中。
分段：泛化的基址/界限
为了解决这个问题，分段（segmentation）的概念应运而生。分段并不是一个新概念， 它甚至可以追溯到 20 世纪 60 年代初期[H61, G62]。这个想法很简单，在 MMU 中引入不止 一个基址和界限寄存器对，而是给地址空间内的每个逻辑段（segment）一对。一个段只是 地址空间里的一个连续定长的区域，在典型的地址空间里有 3 个逻辑不同的段：代码、栈 和堆。分段的机制使得操作系统能够将不同的段放到不同的物理内存区域，从而避免了虚 拟地址空间中的未使用部分占用物理内存。 我们来看一个例子。假设我们希望将图 16.1 中的地址空间放入物理内存。通过给每个 段一对基址和界限寄存器，可以将每个段独立地放入物理内存。如图 16.2 所示，64KB 的物 理内存中放置了 3 个段（为操作系统保留 16KB）。 从图中可以看到，只有已用的内存才在物理内存中分配空间，因此可以容纳巨大的地 址空间，其中包含大量未使用的地址空间（有时又称为稀疏地址空间，sparse address spaces）。 你会想到，需要 MMU 中的硬件结构来支持分断：在这种情况下，需要一组 3 对基址 和界限寄存器。表 16.1 展示了上面的例子中的寄存器值，每个界限寄存器记录了一个段 的大小
如表 16.1 所示，代码段放在物理地址 32KB，大小是 2KB。堆在 34KB，大小也是 2KB。 利用图 16.1 中的地址空间，我们来看一个地址转换的例子。假设现在要引用虚拟地址 100（在代码段中），MMU 将基址值加上偏移量（100）得到实际的物理地址：100 + 32KB = 32868。然后它会检查该地址是否在界限内（100 小于 2KB），发现是的，于是发起对物理地 址 32868 的引用。
补充：段错误
段错误指的是在支持分段的机器上发生了非法的内存访问。有趣的是，即使在不支持分段的机器上 这个术语依然保留。但如果你弄不清楚为什么代码老是出错，就没那么有趣了。
来看一个堆中的地址，虚拟地址 4200（同样参考图 16.1）。如果用虚拟地址 4200 加上
堆的基址（34KB），得到物理地址 39016，这不是正确的地址。我们首先应该先减去堆的偏 移量，即该地址指的是这个段中的哪个字节。因为堆从虚拟地址 4K（4096）开始，4200 的 偏移量实际上是 4200 减去 4096，即 104，然后用这个偏移量（104）加上基址寄存器中的 物理地址（34KB），得到真正的物理地址 34920。 如果我们试图访问非法的地址，例如 7KB，它超出了堆的边界呢？你可以想象发生的情况： 硬件会发现该地址越界，因此陷入操作系统，很可能导致终止出错进程。这就是每个 C 程序员 都感到恐慌的术语的来源：段异常（segmentation violation）或段错误（segmentation fault）。
空闲空间管理
本章暂且将对虚拟内存的讨论放在一边，来讨论所有内存管理系统的一个基本方面， 无论是 malloc 库（管理进程中堆的页），还是操作系统本身（管理进程的地址空间）。具体 来说，我们会讨论空闲空间管理（free-space management）的一些问题。
问题更明确一点。管理空闲空间当然可以很容易，我们会在讨论分页概念时看到。 如果需要管理的空间被划分为固定大小的单元，就很容易。在这种情况下，只需要维护这 些大小固定的单元的列表，如果有请求，就返回列表中的第一项。
如果要管理的空闲空间由大小不同的单元构成，管理就变得困难（而且有趣）。这种情 况出现在用户级的内存分配库（如 malloc()和 free()），或者操作系统用分段（segmentation） 的方式实现虚拟内存。在这两种情况下，出现了外部碎片（external fragmentation）的问题： 空闲空间被分割成不同大小的小块，成为碎片，后续的请求可能失败，因为没有一块足够 大的连续空闲空间，即使这时总的空闲空间超出了请求的大小。
假设
我们假定基本的接口就像 malloc()和 free()提供的那样。具体来说，void malloc(size t size)需要一个参数 size，它是应用程序请求的字节数。函数返回一个指针（没有具体的类型， 在 C 语言的术语中是 void 类型），指向这样大小（或较大一点）的一块空间。对应的函数 void free(void ptr)函数接受一个指针，释放对应的内存块。请注意该接口的隐含意义，在释 放空间时，用户不需告知库这块空间的大小。因此，在只传入一个指针的情况下，库必须 能够弄清楚这块内存的大小。我们将在稍后介绍是如何得知的
该库管理的空间由于历史原因被称为堆，在堆上管理空闲空间的数据结构通常称为空 闲列表（free list）。该结构包含了管理内存区域中所有空闲块的引用。当然，该数据结构不 一定真的是列表，而只是某种可以追踪空闲空间的数据结构。
进一步假设，我们主要关心的是外部碎片（external fragmentation），如上所述。当然， 分配程序也可能有内部碎片（internal fragmentation）的问题。如果分配程序给出的内存块超 出请求的大小，在这种块中超出请求的空间（因此而未使用）就被认为是内部碎片（因为 浪费发生在已分配单元的内部），这是另一种形式的空间浪费。但是，简单起见，同时也因 为它更有趣，这里主要讨论外部碎片。
我们还假设，内存一旦被分配给客户，就不可以被重定位到其他位置。例如，一个程 序调用 malloc()，并获得一个指向堆中一块空间的指针，这块区域就“属于”这个程序了， 库不再能够移动，直到程序调用相应的 free()函数将它归还。因此，不可能进行紧凑 （compaction）空闲空间的操作，从而减少碎片①。但是，操作系统层在实现分段（segmentation） 时，却可以通过紧凑来减少碎片（正如第 16 章讨论的那样）
最后我们假设，分配程序所管理的是连续的一块字节区域。在一些情况下，分配程序 可以要求这块区域增长。例如，一个用户级的内存分配库在空间快用完时，可以向内核申 请增加堆空间（通过 sbrk 这样的系统调用），但是，简单起见，我们假设这块区域在整个生 命周期内大小固定。
底层机制
在深入策略细节之前，我们先来介绍大多数分配程序采用的通用机制。首先，探讨空 间分割与合并的基本知识。其次，看看如何快速并相对轻松地追踪已分配的空间。最后， 讨论如何利用空闲区域的内部空间维护一个简单的列表，来追踪空闲和已分配的空间。
分裂与合并
空闲列表包含一组元素，记录了堆中的哪些空间还没有分配。假设有下面的 30 字节的
任何大于 10 字节的分配请求都会失败（返回 NULL），因为 没有足够的连续可用空间。而恰好 10 字节的需求可以由两个空闲块中的任何一个满足。但 是，如果申请小于 10 字节空间，会发生什么？
为了避免这个问题，分配程序会在释放一块内存时合并可用空间。想法很简单：在归 还一块空闲内存时，仔细查看要归还的内存块的地址以及邻它的空闲空间块。如果新归还 的空间与一个原有空闲块相邻（或两个，就像这个例子），就将它们合并为一个较大的空闲 块。
基本策略
理想的分配程序可以同时保证快速和碎片最小化。遗憾的是，由于分配及释放的请求 序列是任意的（毕竟，它们由用户程序决定），任何特定的策略在某组不匹配的输入下都会 变得非常差。所以我们不会描述“最好”的策略，而是介绍一些基本的选择，并讨论它们 的优缺点。
最优匹配
最优匹配(best fit)策略非常简单：首先便利整个空闲链表，找到和请求大小一样或更大的空闲块，然后返回这组候选者中最小的一块。这就是所谓的最优匹配（也可以称为最小匹配）。只需要遍历一次空闲链表，就可以找到正确的块病返回。
最优匹配背后的想法很简单：选择最接它用户请求大小的块，从而尽量避免空间浪费。 然而，这有代价。简单的实现在遍历查找正确的空闲块时，要付出较高的性能代价。
最差匹配
最差匹配（worst fit）方法与最优匹配相反，它尝试找最大的空闲块，分割并满足用户 需求后，将剩余的块（很大）加入空闲列表。最差匹配尝试在空闲列表中保留较大的块， 而不是向最优匹配那样可能剩下很多难以利用的小块。但是，最差匹配同样需要遍历整个 空闲列表。更糟糕的是，大多数研究表明它的表现非常差，导致过量的碎片，同时还有很 高的开销。
首次匹配
首次匹配（first fit）策略就是找到第一个足够大的块，将请求的空间返回给用户。同样， 剩余的空闲空间留给后续请求。 首次匹配有速度优势（不需要遍历所有空闲块），但有时会让空闲列表开头的部分有很 多小块。因此，分配程序如何管理空闲列表的顺序就变得很重要。一种方式是基于地址排 序（address-based ordering）。通过保持空闲块按内存地址有序，合并操作会很容易，从而减 少了内存碎片。
下次匹配
不同于首次匹配每次都从列表的开始查找，下次匹配（next fit）算法多维护一个指针， 指向上一次查找结束的位置。其想法是将对空闲空间的查找操作扩散到整个列表中去，避 免对列表开头频繁的分割。这种策略的性能与首次匹配很接它，同样避免了遍历查找。
其他方式
分离空闲列表
一直以来有一种很有趣的方式叫作分离空闲列表（segregated list）。基本想法很简单： 如果某个应用程序经常申请一种（或几种）大小的内存空间，那就用一个独立的列表，只 管理这样大小的对象。其他大小的请求都一给更通用的内存分配程序。
这种方法的好处显而易见。通过拿出一部分内存专门满足某种大小的请求，碎片就不再 是问题了。而且，由于没有复杂的列表查找过程，这种特定大小的内存分配和释放都很快。
就像所有好主意一样，这种方式也为系统引入了新的复杂性。例如，应该拿出多少内 存来专门为某种大小的请求服务，而将剩余的用来满足一般请求？超级工程师 Jeff Bonwick 为 Solaris 系统内核设计的厚块分配程序（slab allocator），很优雅地处理了这个问题。
具体来说，在内核启动时，它为可能频繁请求的内核对象创建一些对象缓存（object cache），如锁和文件系统 inode 等。这些的对象缓存每个分离了特定大小的空闲列表，因此 能够很快地响应内存请求和释放。如果某个缓存中的空闲空间快耗尽时，它就向通用内存 分配程序申请一些内存厚块（slab）（总量是页大小和对象大小的公倍数）。相反，如果给定 厚块中对象的引用计数变为 0，通用的内存分配程序可以从专门的分配程序中回收这些空 间，这通常发生在虚拟内存系统需要更多的空间的时候。
厚块分配程序比大多数分离空闲列表这得更多，它将列表中的空闲对象保持在预初始 化的状态。Bonwick 指出，数据结构的初始化和销毁的开销很大[B94]。通过将空闲对象保 持在初始化状态，厚块分配程序避免了频繁的初始化和销毁，从而显著降低了开销。
伙伴系统
因为合并对分配程序很关键，所以人们设计了一些方法，让合并变得简单，一个好例 子就是二分伙伴分配程序（binary buddy allocator）[K65]。 在这种系统中，空闲空间首先从概念上被看成大小为 2N 的大空间。当有一个内存分配 请求时，空闲空间被递归地一分为二，直到刚好可以满足请求的大小（再一分为二就无法 满足）。这时，请求的块被返回给用户。在下面的例子中，一个 64KB 大小的空闲空间被切 分，以便提供 7KB 的块：
在这个例子中，最左边的 8KB 块被分配给用户（如上图中深灰色部分所示）。请注意， 这种分配策略只允许分配 2 的整数次幂大小的空闲块，因此会有内部碎片（internal fragment） 的麻烦
伙伴系统的漂亮之处在于块被释放时。如果将这个 8KB 的块归还给空闲列表，分配程 序会检查“伙伴”8KB 是否空闲。如果是，就合二为一，变成 16KB 的块。然后会检查这 个 16KB 块的伙伴是否空闲，如果是，就合并这两块。这个递归合并过程继续上溯，直到合 并整个内存区域，或者某一个块的伙伴还没有被释放
伙伴系统运转良好的原因，在于很容易确定某个块的伙伴。怎么找？仔细想想上面例 子中的各个块的地址。如果你想得够仔细，就会发现每对互为伙伴的块只有一位不同，正 是这一位决定了它们在整个伙伴树中的层次。现在你应该已经大致了解了二分伙伴分配程 序的工作方式。更多的细节可以参考 Wilson 的调查[W+95]
其他想法
上面提到的众多方法都有一个重要的问题，缺乏可扩展性（scaling）。具体来说，就是 查找列表可能很慢。因此，更先进的分配程序采用更复杂的数据结构来优化这个开销，牺 牲简单性来换取性能。例子包括平衡二叉树、伸展树和偏序树[W+95]。 考虑到现代操作系统通常会有多核，同时会运行多线程的程序（本书之后关于并发的 章节将会详细介绍），因此人们这了许多工作，提升分配程序在多核系统上的表现。两个很 棒的例子参见 Berger 等人的[B+00]和 Evans 的[E06]，看看文章了解更多细节。 这只是人们为了优化内存分配程序，在长时间内提出的几千种想法中的两种。感兴趣 的话可以深入阅读。或者阅读 glibc 分配程序的工作原理[S15]，你会更了解现实的情形。
现代操作系统实际情况
学完了这两种内存管理方式，很多人就要懵了：
现在操作系统到底用的哪种方式？ 好像是分页，但为什么段寄存器好像还是有，到底是怎么一回事？
先说结论，答案就是：分段+分页相结合的内存管理方式
首先要明确一个前提，这一点非常非常重要：无论是分段还是分页，这都是x86架构CPU的内存管理机制，这俩是同时存在的（保护模式下），并不是让操作系统二选一！
既然是同时存在的，那为什么现在将内存地址翻译时，都是讲分页，而很少谈到分段呢？
这一切的一切，都是因为一个原因：操作系统通过巧妙的设置，‘屏蔽’了段的存在。
现代操作系统内存管理到底是分段还是分页，段寄存器还有用吗？ - 知乎 (zhihu.com)
分页
有时候人们会说，操作系统有两种方法，来解决大多数空间管理问题。第一种是将空 间分割成不同长度的分片，就像虚拟内存管理中的分段。遗憾的是，这个解决方法存在固 有的问题。具体来说，将空间切成不同长度的分片以后，空间本身会碎片化（fragmented）， 随着时间推移，分配内存会变得比较困难。 因此，值得考虑第二种方法：将空间分割成固定长度的分片。在虚拟内存中，我们称 这种思想为分页，可以追溯到一个早期的重要系统，Atlas[KE+62, L78]。分页不是将一个进 程的地址空间分割成几个不同长度的逻辑段（即代码、堆、段），而是分割成固定大小的单 元，每个单元称为一页。相应地，我们把物理内存看成是定长槽块的阵列，叫作页帧（page frame）。每个这样的页帧包含一个虚拟内存页。我们的挑战是：
关键问题：如何通过页来实现虚拟内存 如何通过页来实现虚拟内存，从而避免分段的问题？基本技术是什么？如何让这些技术运行良好， 并尽可能减少空间和时间开销?
例子
为了让该方法看起来更清晰，我们用一个简单例子来说明。图 18.1 展示了一个只有 64 字节的小地址空间，有 4 个 16 字节的页（虚拟页 0、1、2、3）。真实的地址空间肯定大得 多，通常 32 位有 4GB 的地址空间，甚至有 64 位①。在本书中，我们常常用小例子，让大家 更容易理解。
物理内存，如图 18.2 所示，也由一组固定大小的槽块组成。在这个例子中，有 8 个页 帧（由 128 字节物理内存构成，也是极小的）。从图中可以看出，虚拟地址空间的页放在物 理内存的不同位置。图中还显示，操作系统自己用了一些物理内存。
可以看到，与我们以前的方法相比，分页有许多优点。可能最大的改进就是灵活性： 通过完善的分页方法，操作系统能够高效地提供地址空间的抽象，不管进程如何使用地址 空间。例如，我们不会假定堆和栈的增长方向，以及它们如何使用。
另一个优点是分页提供的空闲空间管理的简单性。例如，如果操作系统希望将 64 字节 的小地址空间放到 8 页的物理地址空间中，它只要找到 4 个空闲页。也许操作系统保存了 一个所有空闲页的空闲列表（free list），只需要从这个列表中拿出 4 个空闲页。在这个例子里，操作系统将地址空间的虚拟页 0 放在物理页帧 3，虚拟页 1 放在物理页帧 7，虚拟页 2 放在物理页帧 5，虚拟页 3 放在物理页帧 2。页帧 1、4、6 目前是空闲的
为了记录地址空间的每个虚拟页放在物理内存中的位置，操作系统通常为每个进程保 存一个数据结构，称为页表（page table）。页表的主要作用是为地址空间的每个虚拟页面保 存地址转换（address translation），从而让我们知道每个页在物理内存中的位置。对于我们的 简单示例（见图 18.2），页表因此具有以下 4 个条目：（虚拟页 0→物理帧 3）、（VP 1→PF 7）、 （VP 2→PF 5）和（VP 3→PF 2）。
重要的是要记住，这个页表是一个每进程的数据结构（我们讨论的大多数页表结构都 是每进程的数据结构，我们将接触的一个例外是倒排页表，inverted page table）。如果在上 面的示例中运行另一个进程，操作系统将不得不为它管理不同的页表，因为它的虚拟页显 然映射到不同的物理页面（除了共享之外）
页表存在哪里
页表可以变得非常大，比我们之前讨论过的小段表或基址/界限对要大得多。例如，想 象一个典型的 32 位地址空间，带有 4KB 的页。这个虚拟地址分成 20 位的 VPN 和 12 位的 偏移量（回想一下，1KB 的页面大小需要 10 位，只需增加两位即可达到 4KB）。
一个 20 位的 VPN 意味着，操作系统必须为每个进程管理 220个地址转换（大约一百万）。 假设每个页表格条目（PTE）需要 4 个字节，来保存物理地址转换和任何其他有用的东西， 每个页表就需要巨大的 4MB 内存！这非常大。现在想象一下有 100 个进程在运行：这意味 着操作系统会需要 400MB 内存，只是为了所有这些地址转换！即使是现在，机器拥有千兆 字节的内存，将它的一大块仅用于地址转换，这似乎有点疯狂，不是吗？我们甚至不敢想 64 位地址空间的页表有多大。那太可怕了，也许把你吓坏了。
由于页表如此之大，我们没有在MMU中利用任何特殊的偏上硬件，来存储当前正在运行的进程页表，而是将每个进程的页表存储在内存中。现在让我们假设页表存 在于操作系统管理的物理内存中，稍后我们会看到，很多 操作系统内存本身都可以虚拟化，因此页表可以存储在操 作系统的虚拟内存中（甚至可以交换到磁盘上），但是现在 这太令人困惑了，所以我们会忽略它。图 18.4 展示了操作 系统内存中的页表，看到其中的一小组地址转换了吗？
页表结构
让我们来谈谈页表组织。页表就是一种数据结构，用于将虚拟地址（或者实际上， 是虚拟页号）映射到物理地址（物理帧号）。因此，任何数据结构都可以采用。最简单的形 式称为线性页表（linear page table），就是一个数组。操作系统通过虚拟页号（VPN）检索 该数组，并在该索引处查找页表项（PTE），以便找到期望的物理帧号（PFN）。现在，我们 将假设采用这个简单的线性结构。在后面的章节中，我们将利用更高级的数据结构来帮助 解决一些分页问题。
至于每个 PTE 的内容，我们在其中有许多不同的位，值得有所了解。有效位（valid bit） 通常用于指示特定地址转换是否有效。例如，当一个程序开始运行时，它的代码和堆在其 地址空间的一端，栈在另一端。所有未使用的中间空间都将被标记为无效（invalid），如果 进程尝试访问这种内存，就会陷入操作系统，可能会导致该进程终止。因此，有效位对于 支持稀疏地址空间至关重要。通过简单地将地址空间中所有未使用的页面标记为无效，我 们不再需要为这些页面分配物理帧，从而节省大量内存。
我们还可能有保护位（protection bit），表明页是否可以读取、写入或执行。同样，以这 些位不允许的方式访问页，会陷入操作系统。
还有其他一些重要的部分，但现在我们不会过多讨论。存在位（present bit）表示该页 是在物理存储器还是在磁盘上（即它已被换出，swapped out）。当我们研究如何将部分地址 空间交换（swap）到磁盘，从而支持大于物理内存的地址空间时，我们将进一步理解这一 机制。交换允许操作系统将很少使用的页面移到磁盘，从而释放物理内存。脏位（dirty bit） 也很常见，表明页面被带入内存后是否被修改过。
参考位（reference bit，也被称为访问位，accessed bit）有时用于追踪页是否被访问，也 用于确定哪些页很受欢迎，因此应该保留在内存中。这些知识在页面替换（page replacement） 时非常重要，我们将在随后的章节中详细研究这一主题。
TLB
用分页作为核心机制来实现虚拟内存，可能会带来较高的性能开销。因为要使用分 页，就要将内存地址空间切分成大量固定大小的单元（页），并且需要记录这些单元的地址 映射信息。因为这些映射信息一般存储在物理内存中，所以在转换虚拟地址时，分页逻辑 上需要一次额外的内存访问。每次指令获取、显式加载或保存，都要额外读一次内存以得 到转换信息，这慢得无法接受。因此我们面临如下问题
关键问题：如何加速地址转换 如何才能加速虚拟地址转换，尽量避免额外的内存访问？需要什么样的硬件支持？操作系统该如何 支持？
想让某些东西更快，操作系统通常需要一些帮助。帮助常常来自操作系统的老朋友：硬 件。我们要增加所谓的（由于历史原因[CP78]）地址转换旁路缓冲存储器（translation-lookaside buffer，TLB[CG68,C95]），它就是频繁发生的虚拟到物理地址转换的硬件缓存（cache）。因 此，更好的名称应该是地址转换缓存（address-translation cache）。对每次内存访问，硬件先 检查 TLB，看看其中是否有期望的转换映射，如果有，就完成转换（很快），不用访问页表 （其中有全部的转换映射）。TLB 带来了巨大的性能提升，实际上，因此它使得虚拟内存成 为可能[C95]。