CSAPP 第 8 & 9 章 + OSTEP 虚拟化

异常控制流 + CPU 虚拟化

从给处理器加电开始，直到你断电为止，程序计数器假设一个值的序列 \(a_{0},a_{1},\cdots,a_{n-1}\) 其中，每个 \(a_{k}\) 是某个相应的指令 \(I_{k}\) 的地址。每次从 \(a_{k}\) 到 \(a_{k+1}\) 的过渡称为控制转移（control transfer）。这样的控制转移序列叫做处理器的控制流（flow of control，control flow）。

最简单的一种控制流是一个“平滑的”序列，其中每个 \(I_{k}\) 和 \(I_{k+1}\) 在内存中都是相邻的。这种平滑流的突变（也就是 \(I_{k+1}\) 与 \(I_{k}\) 不相邻）通常是由诸如跳转、调用和返回这样一些熟悉的程序指令造成的。这样一些指令都是必要的机制，使得程序能够对由程序变量表示的内部程序状态中的变化做出反应。

但是系统也必须能够对系统状态的变化做出反应，这些系统状态不是被内部程序变量捕获的，而且也不一定要和程序的执行相关。比如，一个硬件定时器定期产生信号，这个事件必须得到处理。包到达网络适配器后，必须存放在内存中。程序向磁盘请求数据，然后休眠，直到被通知说数据已就绪。当子进程终止时，创造这些子进程的父进程必须得到通知。

现代系统通过使控制流发生突变来对这些情况做出反应。一般而言，我们把这些突变称为异常控制流（Exceptional Control Flow，ECF）。异常控制流发生在计算机系统的各个层次。比如，在硬件层，硬件检测到的事件会触发控制突然转移到异常处理程序。在操作系统层，内核通过上下文切换将控制从一个用户进程转移到另一个用户进程。在应用层，一个进程可以发送信号到另一个进程，而接收者会将控制突然转移到它的一个信号处理程序。一个程序可以通过回避通常的栈规则，并执行到其他函数中任意位置的非本地跳转来对错误做出反应。

异常

异常是异常控制流的一种形式，它一部分由硬件实现，一部分由操作系统实现。因为它们有一部分是由硬件实现的，所以具体细节将随系统的不同而有所不同。然而，对于每个系统而言，基本的思想都是相同的。

异常（exception）就是控制流中的突变，用来响应处理器状态中的某些变化。图 8-1 展示了基本的思想。在图中，当处理器状态中发生一个重要的变化时，处理器正在执行某个当前指令 \(I_{curr}\)。在处理器中，状态被编码为不同的位和信号。状态变化称为事件（event）。事件可能和当前指令的执行直接相关。比如，发生虚拟内存缺页、算术溢出，或者一条指令试图除以零。另一方面，事件也可能和当前指令的执行没有关系。比如，一个系统定时器产生信号或者一个 I/O 请求完成。

在任何情况下，当处理器检测到有事件发生时，它就会通过一张叫做异常表（exception table）的跳转表，进行一个间接过程调用（异常），到一个专门设计用来处理这类事件的异常处理程序（exception handler）。当异常处理程序完成处理后，根据引起异常的事件的类型，会发生以下 3 种情况中的一种：

• 处理程序将控制返回给当前指令 \(I_{curr}\)，即当事件发生时正在执行的指令。
• 处理程序将控制返回给 \(I_{next}\)，如果没有发生异常将会执行的下一条指令。
• 处理程序终止被中断的程序。

异常处理

系统中可能的每种类型的异常都分配了一个唯一的非负整数的异常号（exception number）。其中一些号码是由处理器的设计者分配的，其他号码是由操作系统内核（操作系统常驻内存的部分）的设计者分配的。前者的示例包括被零除、缺页、内存访问违例、断点以及算术运算溢出。后者的示例包括系统调用和来自外部 I/O 设备的信号。

在系统启动时（当计算机重启或者加电时），操作系统分配和初始化一张称为异常表的跳转表，使得表目 k 包含异常 k 的处理程序的地址。图 8-2 展示了异常表的格式。在运行时（当系统在执行某个程序时），处理器检测到发生了一个事件，并且确定了相应的异常号。随后，处理器触发异常，方法是执行间接过程调用，通过异常表的表目 k，转到相应的处理程序。图 8-3 展示了处理器如何使用异常表来形成适当的异常处理程序的地址。异常号是到异常表中的索引，异常表的起始地址放在一个叫做异常表基址寄存器（exception table base register）的特殊 CPU 寄存器里。

异常分类

中断

中断是异步发生的，是来自处理器外部的 I/O 设备的信号的结果。硬件中断不是由任何一条专门的指令造成的，从这个意义上来说它是异步的。硬件中断的异常处理程序常常称为中断处理程序（interrupt handler）。

陷阱

陷阱是有意的异常，是执行一条指令的结果。就像中断处理程序一样，陷阱处理程序将控制返回到下一条指令。陷阱最重要的用途是在用户程序和内核之间提供一个像过程一样的接口，叫做系统调用。

故障

故障由错误情况引起，它可能能够被故障处理程序修正。当故障发生时，处理器将控制转移给故障处理程序。如果处理程序能够修正这个错误情况，它就将控制返回到引起故障的指令，从而重新执行它。否则，处理程序返回到内核中的 abort 例程，abort 例程会终止引起故障的应用程序。例如：缺页异常。

终止

终止是不可恢复的致命错误造成的结果，通常是一些硬件错误，比如 DRAM 或者 SRAM 位被损坏时发生的奇偶错误。终止处理程序从不将控制返回给应用程序。处理程序将控制返回给一个 abort 例程，该例程会终止这个应用程序。

进程

进程就是运行中的程序。最简单的方式是一次只运行一个进程，等到它运行完成之后再运行下一个。但是，通常人们希望同时运行多个进程。解决方案是，使用时分共享 CPU 技术，并发地运行多个进程。要高效、可控的实现时分共享，需要使用操作系统来对进程进行管理，而操作系统进行管理的基础就是需要始终保留对 CPU 的控制权。如果没有控制权，进程可以无限制的使用 CPU，访问任意地址。使用异常机制结合用户/内核模式，使得 CPU 的控制权总会在特定的情况从进程转移给操作系统，从而能够高效、可控的实现时分共享。

创建进程

要运行可执行目标文件 prog，我们可以在 Linux shell 的命令行中输入它的名字 ./prog。因为 prog 不是一个内置的 shell 命令，所以 shell 会认为 prog 是一个可执行目标文件，shell 进程会生成一个子进程，它是父进程的一个复制。子进程通过 execve 系统调用启动加载器。加载器删除子进程现有的虚拟内存段，并创建一组新的代码、数据、堆和栈段。新的栈和堆段被初始化为零。通过将虚拟地址空间中的页映射到可执行文件的页大小的片（chunk），新的代码和数据段被初始化为可执行文件的内容。

最后，加载器跳转到程序的入口点，也就是 _start 函数的地址。这个函数是在系统目标文件 ctrl.o 中定义的，对所有的 C 程序都是一样的。_start 函数调用系统启动函数 __libc_start_main，该函数定义在 libc.so 中。它初始化执行环境，调用用户层的 main 函数，处理 main 函数的返回值，并且在需要的时候把控制返回给内核。

除了一些头部信息，在加载过程中没有任何从磁盘到内存的数据复制，直到 CPU 引用一个被映射的虚拟页时才会进行复制。此时，操作系统利用它的页面调度机制自动将页面从磁盘传送到内存。

Linux 系统中的每个程序都运行在一个进程上下文中，有自己的虚拟地址空间。在 Linux x86-64 系统中，代码段总是从地址 0×400000 处开始，后面是数据段。运行时堆在数据段之后，通过调用 malloc 库往上增长。堆后面的区域是为共享模块保留的。用户栈总是从最大的合法用户地址（\(2^{48}-1\)）开始，向较小内存地址增长。栈上的区域，从地址 \(2^{48}\) 开始，是为内核（kernel）中的代码和数据保留的，所谓内核就是操作系统驻留在内存的部分。

上图只是简化图。实际上，由于.data 段有对齐要求，所以代码段和数据段之间是有间隙的。同时，在分配栈、共享库和堆段运行时地址的时候，链接器还会使用地址空间布局随机化（ASLR）。虽然每次程序运行时这些区域的地址都会改变，但它们的相对位置是不变的。

用户模式和内核模式

为了使操作系统内核提供一个无懈可击的进程抽象，处理器必须提供一种机制，限制一个应用可以执行的指令以及它可以访问的地址空间范围。

处理器通常是用某个控制寄存器中的一个模式位（mode bit）来提供这种功能的，该寄存器描述了进程当前享有的特权。当设置了模式位时，进程就运行在内核模式中（有时叫做超级用户模式）。一个运行在内核模式的进程可以执行指令集中的任何指令，并且可以访问系统中的任何内存位置。

没有设置模式位时，进程就运行在用户模式中。用户模式中的进程不允许执行特权指令（privileged instruction），比如停止处理器、改变模式位，或者发起一个 I/O 操作。也不允许用户模式中的进程直接引用地址空间中内核区内的代码和数据。任何这样的尝试都会导致致命的保护故障。反之，用户程序必须通过系统调用接口间接地访问内核代码和数据。

运行应用程序代码的进程初始时是在用户模式中的。进程从用户模式变为内核模式的唯一方法是通过诸如中断、故障或者陷入系统调用这样的异常。当异常发生时，控制传递到异常处理程序，处理器将模式从用户模式变为内核模式。处理程序运行在内核模式中，当它返回到应用程序代码时，处理器就把模式从内核模式改回到用户模式。

上下文切换

内核为每个进程维持一个上下文（context），上下文就是内核重新启动一个被抢占的进程所需的状态。包括通用目的寄存器、浮点寄存器、程序计数器、用户栈、状态寄存器、内核栈和各种内核数据结构，比如描述地址空间的页表、包含有关当前进程信息的进程表，以及包含进程已打开文件的信息的文件表。

操作系统内核使用一种称为上下文切换（context switch）的较高层形式的异常控制流来实现多任务。上下文切换机制是建立在较低层异常机制之上的。在进程执行的某些时刻，内核可以决定抢占当前进程，并使用上下文切换来将控制转移到新的进程。这种决策就叫做调度（scheduling），是由内核中称为调度器（scheduler）的代码处理的。上下文切换的步骤：① 保存当前进程的上下文，② 恢复某个先前被抢占的进程被保存的上下文，③ 将控制传递给这个新恢复的进程。

图 8-14 展示了一对进程 A 和 B 之间上下文切换的示例。在这个例子中，进程 A 初始运行在用户模式中，直到它通过执行系统调用 read 陷入到内核。内核中的陷阱处理程序请求来自磁盘控制器的 DMA 传输，并且安排在磁盘控制器完成从磁盘到内存的数据传输后，磁盘中断处理器。

调度策略

调度指标：

• 周转时间：\(T_{周转时间}=T_{完成时间}-T_{到达时间}\)。（性能指标）
• 响应时间：\(T_{响应时间}=T_{首次运行}-T_{到达时间}\)。（公平指标）

护航效应（convoy effect），一些耗时较少的潜在资源消费者被排在重量级的资源消费者之后，使得平均周转时间增大。

如果你愿意不公平，你可以运行较短的工作直到完成，但是要以响应时间为代价。如果你重视公平性，则响应时间会较短，但会以周转时间为代价。

先进先出（FIFO）

最短任务优先（SJF）

最短完成时间优先（STCF）

时间片轮转（RR）

时间片越短响应时间越好，但是时间片太短会导致频繁的上下文切换，从而影响系统的整体性能。因此，系统设计者需要权衡时间片的长度，使其足够长，以便摊销（amortize）上下文切换成本，而又不会使系统不及时响应。

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

多级反馈队列（MLFQ）

关键问题：没有工作长度的先验（priori）知识，如何设计一个能同时减少响应时间和周转时间的调度程序？

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

因此，MLFQ 调度策略的关键在于如何设置优先级。MLFQ 没有为每个工作指定不变的优先顺序，而是根据观察到的行为调整它的优先级。例如，如果一个工作不断放弃 CPU 去等待键盘输入，这是交互型进程的可能行为，MLFQ 因此会让它保持高优先级。相反，如果一个工作长时间地占用 CPU，MLFQ 会降低其优先级。通过这种方式，MLFQ 在进程运行过程中学习其行为，从而利用工作的历史来预测它未来的行为。

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

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

虚拟内存 + 内存虚拟化

从内存层面来说，实现时分共享最简单的方式是，进程独占内存的使用，切换时将其保存到磁盘中，然后加载另一个进程。为了提高效率，我们让多个进程同时使用内存，但是如何实现进程内存之间的隔离呢？所以引入虚拟内存的概念，让操作系统管理内存实现虚拟化。

虚拟寻址

计算机系统的主存被组织成一个由 M 个连续的字节大小的单元组成的数组。每字节都有一个唯一的物理地址（Physical Address，PA）。使用虚拟寻址时，CPU 通过生成一个虚拟地址（Virtual Address，VA）来访问主存。之后 CPU 上被称为内存管理单元（Memory Management Unit，MMU）的专用硬件，利用存放在主存中的查询表来动态的将虚拟地址翻译为物理地址，该表的内容由操作系统管理。

页面缓存

概念上而言，虚拟内存被组织为一个由存放在磁盘上的 N 个连续的字节大小的单元组成的数组。每字节都有一个唯一的虚拟地址，作为到数组的索引。VM 系统通过将虚拟内存分割为固定大小的虚拟页（Virtual Page，VP），每个虚拟页的大小为 \(P=2^{p}\) 字节。类似地，物理内存被分割为物理页（Physical Page，PP），大小也为 \(P\) 字节。

虚拟页面的集合被分为三个不相交的子集：

• 未分配的：VM 系统还未分配（或者创建）的页。未分配的块没有任何数据和它们相关联，因此也就不占用任何磁盘空间。

• 已缓存的：已缓存在物理内存中的已分配页。

• 未缓存的：未缓存在物理内存中的已分配页。

图 9-3 的示例展示了一个有 8 个虚拟页的小虚拟内存。虚拟页 0 和 3 还没有被分配，因此在磁盘上还不存在。虚拟页 1、4 和 6 被缓存在物理内存中。页 2、5 和 7 已被分配，但是当前并未缓存在主存中。

页表

同任何缓存一样，虚拟内存系统必须有某种方法来判定一个虚拟页是否缓存在 DRAM 中的某个地方。如果是，系统还必须确定这个虚拟页存放在哪个物理页中。如果不命中，系统必须判断这个虚拟页存放在磁盘的哪个位置，在物理内存中选择一个牺牲页，并将虚拟页从磁盘复制到 DRAM 中，替换这个牺牲页。

这些功能是由软硬件联合提供的，包括操作系统软件、MMU（内存管理单元）中的地址翻译硬件和存放在物理内存中被称为页表（page table）的数据结构，页表将虚拟页映射到物理页。每次地址翻译硬件将一个虚拟地址转换为物理地址时，都会读取页表。操作系统负责维护页表的内容，以及在磁盘与 DRAM 之间来回传送页。

图 9-4 展示了一个页表的基本组织结构。页表就是一个页表条目（Page Table Entry，PTE）的数组。虚拟地址空间中的每个页在页表中一个固定偏移量处都有一个 PTE。目前，我们将假设每个 PTE 是由一个有效位（valid bit）和一个 n 位地址字段组成的。有效位表明该虚拟页当前是否被缓存在 DRAM 中。如果设置了有效位，那么地址字段就表示 DRAM 中相应的物理页的起始位置，这个物理页中缓存了该虚拟页。如果没有设置有效位，那么一个 null 地址表示这个虚拟页还未被分配，否则这个地址就指向该虚拟页在磁盘上的起始位置（即已分配但未缓存）。

缺页

在虚拟内存的习惯说法中，DRAM 缓存不命中称为缺页（page fault）。图 9-6 展示了在缺页之前我们的示例页表的状态。CPU 引用了 VP3 中的一个字，VP3 并未缓存在 DRAM 中。地址翻译硬件将虚拟地址作为索引来定位 PTE3，并从内存中读取它。从有效位推断出 VP3 未被缓存，从而触发一个缺页异常。缺页异常调用内核中的缺页异常处理程序，该程序会选择一个牺牲页，在此例中就是存放在 PP3 中的 VP4。如果 VP4 已被修改，那么内核会将它复制回磁盘。无论哪种情况，内核都会修改 VP4 的页表条目，反映出 VP4 不再缓存在主存中这一事实。

之后，内核从磁盘复制 VP3 到内存中的 PP3，更新 PTE3，随后返回。当异常处理程序返回时，它会重新启动导致缺页的指令，该指令会把导致缺页的虚拟地址重发送到地址翻译硬件。但是现在，VP3 已被缓存在主存中，那么页命中也能由地址翻译硬件正常处理。图 9-7 展示了在缺页之后我们的示例页表的状态。

内存管理

到目前为止，我们都假设有一个单独的页表，将一个虚拟地址空间映射到物理地址空间。实际上，操作系统为每个进程提供了一个独立的页表，因而也就是一个独立的虚拟地址空间。图 9-9 展示了基本思想。注意，多个虚拟页面可以映射到同一个物理页面上（页面共享）。

内存保护

任何现代计算机系统必须为操作系统提供手段来控制对内存系统的访问。不应该允许一个用户进程修改它的只读代码段。而且也不应该允许它读或修改任何内核中的代码和数据结构。不应该允许它读或者写其他进程的私有内存，并且不允许它修改任何与其他进程共享的虚拟页面，除非所有的共享者都显式地允许它这么做（通过调用明确的进程间通信系统调用）。

每次 CPU 生成一个虚拟地址时，地址翻译硬件都会读一个 PTE，所以可以在 PTE 上添加一些额外的许可位来控制对一个虚拟页面内容的访问。图 9-10 展示了基本思想。在这个示例中，每个 PTE 中添加了三个许可位。SUP 位表示进程是否必须运行在内核（超级用户）模式下才能访问该页。READ 位和 WRITE 位控制对页面的读写访问。如果一条指令违反了这些许可条件，那么 CPU 就触发一个一般保护故障，将控制传递给一个内核中的异常处理程序。Linux shell 一般将这种异常报告为“段错误（segmentation fault）”。

地址翻译

CPU 中的一个控制寄存器，页表基址寄存器（Page Table Base Register，PTBR）指向当前页表。\(n\) 位的虚拟地址包含两个部分：一个 \(p\) 位的虚拟页面偏移（Virtual Page Offset，VPO）和一个 \((n - p)\) 位的虚拟页号（Virtual Page Number，VPN）。MMU 利用 VPN 来选择适当的 PTE。将页表条目中物理页号（Physical Page Number，PPN）和虚拟地址中的 VPO 串联起来，就得到相应的物理地址。

快表

每次 CPU 产生一个虚拟地址，MMU 就必须查阅一个 PTE，以便将虚拟地址翻译为物理地址。在最糟糕的情况下，这会要求从内存多取一次数据，代价是几十到几百个周期。如果 PTE 碰巧缓存在 L1 中，那么开销就下降到 1 个或 2 个周期。然而，许多系统都试图消除即使是这样的开销，它们在 MMU 中包括了一个关于 PTE 的小缓存，称为快表（Translation Lookaside Buffer，TLB）。

多级页表

到目前为止，我们一直假设系统只用一个单独的页表来进行地址翻译。但是如果我们有一个 32 位的地址空间、4KB 的页面和一个 4 字节的 PTE，那么即使应用所引用的只是虚拟地址空间中很小的一部分，也总是需要一个 4MB 的页表驻留在内存中。对于地址空间为 64 位的系统来说，问题将变得更复杂。使用多级页表，时间换空间。