操作系统

• 1: 基本概念
• 2: 抽象-进程
• 3: 插叙-进程 API
• 4: 机制-受限直接执行
• 5: 进程调度
• 6: 调度-多级反馈队列
• 7: 调度-比例份额
• 8: 多处理器调度
• 9: 抽象-地址空间
• 10: 内存接口
• 11: 地址转换
• 12: 分段

1 - 基本概念

一个正在运行的程序会做一件非常简单的事情：指令执行。处理器从内存中获取一条指令，对其进行解码，然后执行这条指令。完成这条指令后，处理器会继续执行下一条指令，以此类推，直到程序最终完成。

这就是冯诺依曼计算模型的基本概念。但实际上，在一个程序运行的同时，还有很多其他疯狂的事情正在同步进程——主要是为了让系统易于使用。

有一类软件负责让程序的运行变得更加容易，甚至允许你通知运行多个程序，允许程序共享内存，让程序能够与设备交互，以及其他类似的有趣工作。这些软件统称为操作系统，因为它们负责确保系统能够易于使用且能高效的运行。

要做到这一点，操作系统主要利用一种通用的技术——虚拟化。也就是说，操作系统将物理资源转换为更加通用、更加强大且更易于使用的虚拟形式。因此我们有时也将操作系统称为虚拟机。

为了让用户可以告诉操作系统做什么，从而利用虚拟机的功能(如运行程序、分配内存或访问文件)。操作系统还提供了一些接口供你调用。实际上，典型的操作系统会提供几百个系统调用以供程序调用。由于操作系统提供这些调用来运行程序、访问内存和设备，并进行其他相关的操作，我们有时也会说操作系统为应用程序提供了一个标准库。

最后，因为虚拟化让许多程序运行(从而共享 CPU)，让许多程序可以同时访问自己的指令和数据(从而共享内存)，让许多程序访问设备(共享磁盘)，所以操作系统有时又被称为资源管理器。每个 CPU、内存和磁盘都是系统的资源，因此操作系统扮演的主要角色就是管理这些资源，以做到高效公平，或者实际上会考虑其他更多的指标。

虚拟化 CPU

图 2-1 展示了我们第一个程序，所做的只是调用 spin 函数，该函数会反复检查时间并在运行一秒后返回。然后它会打印出用户在命令行中传入的字符串，并一直重复上述过程。

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <assert.h>
#include "common.h"

int main(int argc, char *argv[]) {
	if(argc != 2) {
		fprintf(stderr, "usage: cpu <string>\n");
		exit(1);
	}
	char *str = argv[1];
	while(1) {
		Spin(1);
		pringf("s%\n", str);
	}
	return 0;
}

假设我们将这段代码保存为 cpu.c，并决定在一个单处理器的系统上编译运行。以下是我们看到的内容：

prompt> gcc -o cpu cpu.c -Wall
prompt> ./cpu "A"
A
A
A
A
^C
prompt>

系统开始运行时，该程序会反复检查时间，直到一秒钟过去。一秒钟过去之后，代码打印用户传入的字符串并继续。注意：该程序将永远保持执行，只有按下 CTRL + C，才能终止该程序。

现在我们做同样的事情，让我们运行同一个程序的多个不同实例，图 2-2 展示了这个稍复杂的例子的结果：

prompt> ./cpu A & ; ./cpu B & ; ./cpu C & ; ./cpu D &
[1] 7353
[2] 7354
[3] 7355
[4] 7356
A
B
D
C
A
B
D
C
A
C
B
D
...

尽管我们只有一个处理器，但这 4 个程序几乎同时都在运行。

事实证明，在硬件的一些帮助下，操作系统负责提供这种假象，即系统拥有非常多的虚拟 CPU 的假象。将单个 CPU (或其中一小部分)转换为看似无限数量的 CPU，从而让许多程序看似同时运行，这就是所谓的虚拟化 CPU，这是本书第一大部分的关注点。

需要一些接口来运行程序或终止程序，接口是大多数用户与操作系统交互的主要方式。

一次运行多个程序可能会引发各种新的问题，比如两个程序都想要在特定的时间执行，哪又该运行哪个呢？该问题由操作系统的策略来解决。操作系统的各种组件采用了一些不同的策略来解决该问题，所以我们将在学习操作系统实现的基本机制时研究这些策略。因此，操作系统承担了资源管理器的角色。

虚拟化内存

现代机器提供的物理内存模型非常简单。内存就是一个字节数组。要读取内存必须指定一个地址，才能访问存储在其中的数据。要写入或更新内存，也必须指定要写入给定数据的地址。

程序在运行时一直需要访问内存。程序将所有数据结构保存在内存中，并通过各种指令来访问这些数据，比如加载或保存，或利用其它明确的指令来在工作中访问内存。程序的每个指令都保存在内存中，因此每次读取指令都会访问内存。

下面的程序通过 malloc 来分配一些内存：

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include "common.h"

int main(int argc, char *argv[]) {
	int *p = malloc(sizeof(int));	// a1
	assert(p != NULL);
	printf("(d%) memory address of p: %08x\n", 
		getpid(),(unsigned) p); 	// a2
	*p = 0;							// a3
	while(1) {
		Spin(1);
		*p = *p + 1;
		printf("(d%) p: %d\n", getpid(), *p); // a4
	}
	return 0;
}

该程序的输出如下：

prompt> ./mem
(2134) memory address of p: 00200000
(2134) p: 1
(2134) p: 2
(2134) p: 3
(2134) p: 4
(2134) p: 5

首先，它分配了一些内存(a1)。然后，打印出内存的地址(a2)，然后将数字 0 放入新分配的内存(a3)的第一个空位中。最后，程序循环，延迟一秒钟并递增 p 中保存的地址值。在每个打印语句中，它还会打印出所谓的正在执行的进程标示符(PID)。每个运行进程都有一个唯一的 PID。

现在，我们再次运行同一个程序的多个实例，看看会发生什么。我们从示例中看到，每个正在运行的程序都在相同的地址分配了内存，但每个程序似乎都独立的更新了该地址的值。就好像每个正在运行的程序都有自己的私有内存，而不是与其他正在运行的程序共享相同的物理内存。

prompt> ./mem &; ./mem & 
[1] 24113
[2] 24114
(24113) memory address of p: 00200000
(24114) memory address of p: 00200000
(24113) p: 1
(24114) p: 1
(24114) p: 2
(24113) p: 2
(24113) p: 3
(24114) p: 3
(24113) p: 4
(24114) p: 4

实际上，这正是操作系统虚拟化内存时发生的情况。每个进程访问自己的私有虚拟内存地址空间，操作系统以这种方式映射到机器的物理内存上。一个正在运行的程序中的内存引用不会影响其他进程(或操作系统本身)的地址空间。对于正在运行的程序，它完全拥有自己的物理内存。但实际情况是，物理内存是由操作系统管理的共享资源。

并发

并发问题首先会出现在操作系统本身，比如上面关于虚拟化的例子中，操作系统同时处理很多事情，它首先运行一个程序，然后再运行一个程序，等等。

同时，并发问题并不局限于操作系统本身。事实上，现代多线程程序也存在相同的问题。

1    #include <stdio.h>
2    #include <stdlib.h>
3    #include "common.h"
4
5    volatile int counter = 0;
6    int loops;
7
8    void *worker(void *arg) {
9        int i;
10       for (i = 0; i < loops; i++) {
11           counter++;
12       }
13       return NULL;
14   }
15
16   int
17   main(int argc, char *argv[])
18   { 
19       if (argc != 2) {
20           fprintf(stderr, "usage: threads <value>\n");
21           exit(1);
22       }
23       loops = atoi(argv[1]);
24       pthread_t p1, p2;
25       printf("Initial value : %d\n", counter);
26
27       Pthread_create(&p1, NULL, worker, NULL);
28       Pthread_create(&p2, NULL, worker, NULL);
29       Pthread_join(p1, NULL);
30       Pthread_join(p2, NULL);
31       printf("Final value    : %d\n", counter);
32       return 0;
33   }

主程序利用 Pthread_create 创建了两个线程。你可以将线程看做与其他函数在同一内存空间中运行的函数，并且每次都有多个线程处于活动状态。在这个例子中，每个线程开始在一个名为 worker 的函数中运行，在该函数中，它只是一个递增计数器，循环 loops 次。

prompt> gcc -o thread thread.c -Wall -pthread
prompt> ./thread 1000
Initial value : 0
Final value   : 

你可能会猜到，两个线程完成时计数器的结果为 2000，因为每个线程都将计数器增加 1000 次。也就是说，当 loops 的输入值设为 N 时，我们预计程序的最终输出为 2N。但事实证明并非如此。

prompt> ./thread 100000 
Initial value : 0
Final value   : 143012     // huh?? 
prompt> ./thread 100000
Initial value : 0
Final value  : 137298    

在这次运行中我们提供 100000 作为输入值，得到的最终值却不是 200000。然后当我们再次运行该程序时，不仅得到了错误的结果，而且每次错误的结果还都不相同。事实上，如果以多次使用较高的 loops 值来运行该程序，甚至有可能得到正确的答案。

事实证明，这些奇怪的结果与指令如何执行有关。指令每次执行一条。遗憾的是，上面的程序中关键部分是增加共享计数器的地方，它需要 3 条指令：一条将计数器的值从内存加载到寄存器，一条将其递增，另一条将递增后的值保存到内存中。因为这 3 条指令并非以原子的方式执行，所以会发生如上奇怪的结果。

持久性

在系统内存中，数据容易丢失，因为像 DRAM 这样的设备已易失的方式存储数据。如果断电或系统崩溃，内存中的所有数据将会丢失。因此，我们需要硬件和软件来持久的存储数据。

硬件以某种输入/输出设备的形式出现。在现代系统中，硬盘驱动器是存储长期保存的信息的通用存储库，同时固态磁盘(SSD)也正在这个领域取得领先地位。

操作系统中管理磁盘的软件通常称为文件系统。因此它负责以可靠和高效的方式，将用户创建的任何文件存储在系统的磁盘上。

不像操作系统为 CPU 和内存提供的抽象，操作系统不会为每个应用程序创建专用的虚拟磁盘。相反，它假设用户经常需要共享文件中的信息。比如，在编写 C 程序时，你可能首先使用编辑器，之后，可以使用编译器将源代码转换为可执行文件，再之后，你可以运行新的可执行文件。因此，你可以看到文件如何在不同的进程之间共享。首先，编辑器创建一个文件，作为编译器的输入。编译器使用该输入文件创建一个新的可执行文件。最后，运行新的可执行文件。这样一个新的程序就诞生了。

1    #include <stdio.h>
2    #include <unistd.h>
3    #include <assert.h>
4    #include <fcntl.h>
5    #include <sys/types.h>
6
7    int
8    main(int argc, char *argv[])
9    {
10       int fd = open("/tmp/file", O_WRONLY | O_CREAT | O_TRUNC, S_IRWXU);
11       assert(fd > -1);
12       int rc = write(fd, "hello world\n", 13);
13       assert(rc == 13);
14       close(fd);
15       return 0;
16   }

为了完成这个任务，该程序向操作系统发出 3 个调用。第一个是对 open 的调用，它打开文件并创建。第二个是 write，将一些数据写入文件。第三个是 close，只是简单的关闭文件，从而表名程序不会再向其写入更多的数据。这些系统调用被转到称为文件系统的操作系统部分，然后操作系统处理这些请求，并向用户返回某些错误代码。

文件系统必须做很多操作：首先确定新数据将驻留在磁盘的哪个位置上，然后在文件系统所维护的各种结构中对其进行记录。这样做需要向底层存储系统发出 IO 请求，已读取现有结果或更新。所有编写过设备驱动程序的人都知道，让设备代表你来执行某项操作是一项复杂而详细的过程。它需要深入了解低级别设备接口的确切含义。幸运的是，操作系统提供了一种通过系统调用来访问设备的标准又简单的方法。因此，操作系统有时又被称为标准库。

当然，关于如何访问设备、文件系统如何在所述设备上持久的管理数据，还有更多细节。处于性能访问的考虑，大多数文件系统首先会延迟这些写操作一段时间，希望将其批量分组为较大的组。为了处理写入期间系统崩溃的问题，大多数文件系统都包含某种复杂的写入协议，如日志或写时复制，仔细排序写入磁盘的操作，以确保如果在写入序列期间发生故障，系统可以在之后恢复到合理的状态。为了使不同的通用操作更加高效，文件系统采用了许多不同的数据结构和访问方法，从简单的列表到复杂的 B 树。

设计目标

操作系统的工作是：它获得 CPU、内存、磁盘等物理资源，并对它们进行虚拟化；它处理并发相关的棘手问题；它之久的存储文件以确保文件长期安全。鉴于我们希望建立这样一个系统，所以要有一些目标，以帮助我们集中设计和实现，并在必要时进行折中。找到合适的折中是建立系统的关键。

一个最基本的目标是建立一些抽象，让系统变得易于使用。抽象对我们在计算机科学中做的每件事都有帮助。抽象使得编写一个大型程序称为可能，将其划分为更小且更易理解的部分，用 C 这样高级的语言编写这样的程序不用考虑汇编，用汇编代码则不用考虑逻辑门，用逻辑门来构建处理器则不用太多考虑晶体管。抽象是如此重要，以至于我们会忘记其重要性，但在这里我们会谨记。因此，在每一部分中，我们将讨论随着时间的推移而发展的一些主要抽象，为你提供一种思考操作系统各个部分的方法或思路。

**设计和实现操作系统的一个目标是提供高性能。**换言之，我们的目标是最小化操作系统的开销。虚拟化让系统变得易于使用是非常值得的，但也不会不计成本。因此，我们必须努力提供虚拟化和其他操作系统功能，同时避免过多的开销。这些开销会以多种形式出现：额外时间(更多指令)和额外空间(更多内存/磁盘)。如果有可能，我们会寻求解决方案以尽量减少这些形式的开销。但是完美并非总是可以实现的，我们会注意到这一点并在适当的情况下让人这种情况。

另一个设计目标是在应用程序之间、操作系统和应用程序之间提供保护。因为我们希望许多程序同时运行，所以要确保一个程序的恶意或偶然的不良行为不会损害其他程序。我们当然不希望应用程序能够损害操作系统本身。保护是操作系统基本原理之一的核心，这就是隔离。让进程彼此隔离是保护的关键，因此决定了 OS 必须执行的大部分任务。

**操作系统必须能够不间断运行。**当它失效时，系统上运行的所有应用程序也会失效。由于这种依赖性，操作系统往往力求提供高度的可靠性。随着操作系统变得越来越复杂，构建一个可靠的操作系统是一个相当大的挑战：事实上，该领域的许多正在进行的研究，正式专注于该问题。

其他目标也是有道理的：在我们日益增长的绿色世界中，能源效率非常重要；安全性对于恶意应用程序直观重要，尤其是在当前高度联网的时代。随着操作系统在越来越小的设备上运行，移动性变得越来越重要。根据系统的使用方式，操作系统将有不同的目标，因此可能至少以稍微不同的方式实现。但是我们会看到，我们将要介绍的关于如何构建操作系统的许多原则，则各种不同的设备上都很有意义。

简单历史

早期操作系统：只是一些库

一开始操作系统并没有做太多事情。基本是，它只是一些常用函数库。比如，不是让系统中每个程序员都编写低级 IO 处理代码，而是让 OS 提供这样的 API，以提升开发效率。

通常在这些老的大型机系统上，一次运行一个程序，并由操作员来控制。该操作员完成了你认为现代操作系统会做的所有事情，比如决定运行作业的顺序。如果你是一个聪明的开发人员，就会对这个操作员很好，这样他们可以将你的工作移到到队列的前端以尽快执行。

这种计算模式被称为批处理，先把一些工作准备好，然后由操作员以“分批”的方式运行。此时，计算机并没有以交互的方式被使用，因为这样做成本太高：让用户坐在计算机前使用它，大部分时间都会闲置，所以会导致设备每小时浪费数千美元。

超越库：保护

在超越常用服务的简单库的发展过程中，操作系统在管理机器方面扮演者更为重要的角色。其中一个重要方面是意识到代表操作系统运行的代码是特殊的。它控制了设备，因此对打它的凡事应该与对待正常应用程序的代码有所不同。不然的话，假设允许任何应用程序能够从磁盘的任何地方读取数据。因为任何程序都可以读取数据，隐私的概念就消失了。因此，将一个文件系统实现为一个库是没有意义的。

因此，系统调用的概念诞生了，它由 Atlas 计算系统率先采用。不是将操作系统例程作为一个库来提供，这里的想法是添加一些特殊的硬件指令和硬件状态，让操作系统过度变为正式的、受控的过程。

系统调用和过程调用的关键区别在于，系统调用将控制转移到 OS 中，同时提高硬件特权级别。用户应用程序以所谓的用户模式运行，这意味着硬件限制了应用程序的功能。比如，以用户模式运行的应用程序通常不能发起对磁盘的 IO 请求，不能访问任何物理内存页或在网络上发送数据包。在发起系统调用时(通常通过一个称为“trap”的特殊硬件指令)，硬件将控制转移到预先指定的陷阱处理程序，并同时将特权级别提升到内核模式。在内核模式下，操作系统可以完全访问系统的硬件，因此可以执行诸如发起 IO 请求或为程序提供更多的内存等功能。当操作系统完成请求的服务时，他通过特殊的陷阱返回(return-from-trap)指令将控制权交还给用户，该指令返回到用户模式，同时将控制权交还给应用程序，回到应用离开的地方。

多道程序时代

操作系统的真正兴起是在大主机计算时代之后，即小型机时代。像数字设备公司的 PDP 系列这样经典机器，让计算机变得更加实惠。因此，不再是每个大型组织都需要拥有一台主机，而是组织内的一小群人可以拥有自己的计算机。毫不奇怪，这种成本下降的主要影响之一就是开发者活动的增加。更聪明的人接触到计算机，从而让计算机系统做出更有趣和漂亮的事情。

特别是，由于希望更好的利用资源，多道程序开始变得很普遍。操作系统不是一次只运行一项作业，而是将大量作业加载到内存中并在它们之间切换，从而提供 CPU 利用率。这种切换非常重要，因为 IO 设备很慢。在处理 IO 时让程序占用着 CPU 则会浪费 CPU 时间。

在 IO 进行和任务中断时，要支持多道程序和重叠运行。这一愿望使得操作系统开始创新，沿着多个方向进行概念发展。内存保护等问题开始变得重要。我们不希望一个程序能够访问另一个程序的内存。了解如何处理多道程序引入的并发问题也很关键。在中断存在的情况下，确保操作系统正常运行是一个很大的挑战。

当时主要的实际进展之一是引入了 UNIX 操作系统，主要归功与贝尔实验室和 Ken Thompson、Dennis Ritchie。UNIX 从不同的操作系统获得了很多好的想法，并让这些想法变得更简单易用。很快，该团队就向世界各地的人们发送含有 UNIX 源代码的磁带，其中很多人随后参与并加入到系统中。

摩登时代

除了小型计算机之外还有一种新型机器，更加便宜快速且适用于大众：今天我们称之为个人计算机。在苹果公司早期的机器和 IBM PC 的引领下，这种新机器很快就称为计算的主导力量，因为它们的低成本让每个桌子上都有一台机器，而不是每个工作小组共享一台小型机器。

遗憾的是，对于操作系统来说，个人计算机起初代表了一次巨大的倒退，因为早期的系统忘记了小型机时代的经验教训。比如早期的操作系统如 DOS 并不认为内存保护很重要。因此，恶意程序或者编写质量欠佳的程序可能会在整个内存中写入乱七八糟的数据。第一代 MacOS 采取合作的方式进行作业调度。因此，意外陷入无限循环的线程可能会占用整个系统，从而导致重新启动。这一代系统中遗漏的操作系统功能造成的痛苦列表很长，因此无法在这里给出完整的讨论。

幸运的是，进过一段时间的苦难后，小型计算机操作系统的老功能开始进入台式机。比如 MaxOS X 的核心是 UNIX，包括人们期望从这样一个成熟系统中获得的所有功能。Windows 在计算机历史中同样采用了许多伟大的思想，特别是从 Windows NT 开始，这是微软操作系统技术的一次伟大飞跃。即使在今天的手机上运行的操作系统(如 Linux)，也更像小型机在 20 世纪 70 年代运行的，而不是像 20 世纪 80 年代 PC 运行的那种操作系统。很高兴看到在操作系统开发鼎盛时期出现的好想法已经进入了现代世界。更好的是，这些想法不断发展，为用户和应用程序提供了更多功能，让现代系统更加完善。

补充：UNIX 的重要性 在操作系统的历史中，UNIX 的重要性举足轻重。受早期系统的影响，尤其是 MIT 的 Multics 系统，UNIX 汇集了很多了不起的思想，创造了既简单又强大的系统。 最初的贝尔实验室 UNIX 的基础是统一原则，即构建小二强大的程序，这些程序可以连接在一起形成更大的工作流。在你输入命令的地方，shell 提供了诸如管道之类的原语，来支持这样的元编程，因此很容易将程序串起来完成更大规模的任务。 UNIX 环境对于程序开发人员很友好，并为新的 C 语言提供了编译器。程序员很容易编写自己的程序并将其分享，这使得 UNIX 大受欢迎。作为开源软件的早期形式，作者向所有请求的人免费提供副本，这种方式的帮助很大。 代码的可得性和可读性非常重要。用 C 语言编写的美丽的小内核吸引其他人来摆弄内核，添加新的、很酷的功能。 遗憾的是，随着公司试图维护其所有权和利润，UNIX 的传播速度有所降低，这是律师参与其中的不幸结果。很多公司开始拥有自己的 UNIX 变种。

补充：然后出现了 Linux 幸运的是，对于 UNIX 来说，一位名叫 Linus Torvalds 的年轻芬兰黑客决定编写它自己的 UNIX 版本，该版本严重依赖最初系统背后的原则和思想，但没有借用原来的代码集，从而避免了合法性问题。他征集了世界各地其他人的帮助，不久之后 Linux 就诞生了。

2 - 抽象-进程

进程的非正式定义非常简单：进程就是运行中的程序。程序本身没有生命周期，它只是保存在磁盘上的一些指令或静态数据。是操作系统让这些字节运行起来、让程序发挥作用。

事实表明，人们常常系统同时运行多个程序。比如：在使用计算机或笔记本的时候，我们会同时运行浏览器、邮件、游戏等。实际上，一个正常的系统可能会有上百个进程同时在运行。如果能实现这样的系统，人们就不需要考虑当时是哪个 CPU 是可用的，使用起来非常简单。因此我们的挑战是：

关键问题：如何提供有许多 CPU 的假象？

操作系统通过虚拟化 CPU 来提供这种假象。通过让一个进程只运行一个时间片，然后切换到其他进程，操作系统提供了存在多个虚拟 CPU 的假象。这就是 分时共享 CPU 技术，允许用户如愿运行多个并发进程。潜在的开销是性能损失，因为如果 CPU 必须共享，每个进程的运行过程都会慢一点。

要实现 CPU 的虚拟化并能实现的足够好，操作系统就需要一些低级机制和一些高级智能。我们将低级机制称为机制。机制是一些低级方法或协议，实现了所需要的功能。比如稍后我们将学习如何实现上下文切换，它让操作系统能够停止运行一个程序，并开始在指定的 CPU 上运行另一个程序。所有现代操作系统都采用了这种分时机制。

提示：使用分时共享(和空分共享) 分时共享是操作系统共享资源所使用的最基本的技术之一。通过运行资源由一个实体使用一小段时间，然后由另一个实体使用一小段时间，如此下去，所谓的资源(CPU/网络)可以被许多人共享。 分时共享的自然对应技术是空分共享，资源在空间上被划分给希望使用它的多个人。比如磁盘空间自然就是一个空分共享资源，因为一旦将块分配给文件，在用户删除文件之前，不可能将它分配给其它文件。

在这些机制之上，操作系统中有一些智能以策略的形式存在。策略是在操作系统内做出某种决定的算法。比如，给定一组可能的程序要在 CPU 上运行，操作系统应该运行哪个程序？操作系统中调度策略会做出这个决定，可能利用历史信息、工作负载知识、性能指标来做出决定。

抽象：进程

操作系统为正在运行的程序提供的抽象，就是所谓的进程。 一个进程只是一个正在运行的程序。在任何时刻，我们都可以清点它在执行过程中访问或影响了操作系统的哪些部分，从而概况为一个进程。

为了理解进程的构成，我们必须理解它的机器状态：程序在运行时可以读取或更新的内容。在任何时刻，机器的哪些部分对该程序的执行很重要？

进程的机器状态有一个明显的组成部分——内存。指令被保存在内存中，正在运行的程序读写的数据也保存在内存中。因此进程可以访问的内存(地址空间)是该进程的一部分。

进程的机器状态的另一部分是寄存器。许多指令明确的读取或更新寄存器，因此显然它们对于执行该进程很重要。

请注意，有一些非常特殊的寄存器构成了该机器状态的一部分。比如程序计数器告诉我们程序当前正在执行哪个指令；类似的，栈指针和先关的帧指针用户管理函数参数栈、局部变量和返回地址。

提示：分离策略和机制 在许多操作系统中，一个通用的设计范式是将高级策略与其低级机制分开。你可以将机制看成对系统的“HOW”问题提供的答案。例如操作系统如何执行上下文切换？策略为“WHICH”问题提供答案。例如操作系统现在应该运行哪个进程？将两者分开可以轻松改变策略，而不用重新考虑机制，因此这是一种模块化的形式，一种通用的软件设计原则。

最后，程序也经常访问持久存储设备。此类 IO 信息可能包含当前打开的文件列表。

进程 API

虽然讨论真实的进程 API 将会在第五章进行，但这里先介绍一下操作系统的所有接口必须包含哪些内容。所有现代操作系统都以某种形式提供这些 API。

• 创建：操作系统必须包含一些创建新进程的方法。在 shell 中键入命令或双击应用程序图标时，会调用操作系统来创建新进程，运行指定的程序。
• 销毁：由于存在创建进程接口，因此系统还提供了一个强制销毁进程的接口。当然，很多进程会在运行完成后自行退出。但是，如果它们不退出，用户可能希望终止它们，因此停止失控进程的接口非常有用。
• 等待：有时等待进程停止运行是有用的，因此经常提供某种等待接口。
• 控制：除了杀死或等待进程外，有时还可能存在其他控制。比如大多数操作系统提供了某种方法来暂停进程、恢复进程。
• 状态：通常也有一些接口可以获得有关集成的状态信息，例如运行了多长时间，或者处于什么状态。

进程创建：细节

**操作系统运行进程要做的第一件事情就是将代码和所有静态数据(如初始化变量)加载到内存中，即加载到进程的地址空间中。**程序最初以某种可执行的格式保存在磁盘上。因此，将程序和静态数据加载到内存中的过程，需要操作系统从磁盘上读取这些字节，并将它们放在内存中的某处。

**在早期的操作系统中，加载过程会尽早(eagerly)完成，即在运行程序之前全部完成。现代操作系统则会惰性(lazily)执行该过程，即仅在程序执行期间需要的时候才会加载代码或数据片段。**要真正理解代码和数据的惰性加载过程是如何工作的，必须更多的了解分页和交换的机制，这是我们将来讨论内存虚拟化时要涉及的主题。现在，只要记住在运行任何程序之前，操作系统显然必须要执行一些工作，才能将重要的程序字节从磁盘读入内存。

将代码和静态数据加载到内存之后，操作系统在运行该进程之前还要执行一些其他操作。必须为程序的运行时栈分配一些内存。你可能已经知道，C 程序使用栈存放局部变量、函数参数和返回地址。操作系统分配这些内存并提供给进程。操作系统也可能会用参数初始化栈。具体来说，它会将参数填入 mian 函数，即 argc 和 argv 数组。

**操作系统也可能会程序的堆分配一些内存。在 C 程序中，堆用于显式请求的动态分配数据。**程序通过调用 malloc 来请求这样的内存空间，并通过调用 free 来显式释放。数据结构需要堆。起初堆会很小，随着程序的运行，通过 malloc 库 API 请求更多内存，操作系统可能会参与分配更多内存给进程，以满足这些调用。

操作系统还将执行一些其他初始化任务，特别是与输入/输出先关的任务。比如，在 UNIX 系统中，默认情况下每个进程都有 3 个打开的文件描述符，分别用于标准输入、输出和错误。这些描述符让程序轻松读取来自中断的输入以及打印输出到屏幕。

通过将代码和静态数据加载到内存中，通过创建和初始化栈以及执行与 IO 设置相关的其他工作，OS 现在终于为程序执行搭好了舞台。然后它还有最后一项任务：启动程序，在入口处执行，即 main。通过调转到 main 例程，OS 将 CPU 的控制权转移到新创建的进程中，从而程序开始执行。

进程状态

进程在特定的时间可能处于不同的状态。在早期的计算机系统中，出现了一个进程可能处于多种状态的概念。简而言之，进程可以处于以下 3 种状态之一：

• 运行：在运行状态下，进程正在处理器上运行，这意味着它正在执行指令。
• 就绪：在就绪状态下，进程已经准备好运行，但由于某种原因，操作系统选择不在此时运行它。
• 阻塞：在阻塞状态下，一个进程执行了某种操作，直到发生其他事件时才会准备开始运行。一个常见的例子就是，当进程向磁盘发起 IO 请求时，进程会被阻塞，这时其他进程可以使用该处理器。

如上图所示，可以根据操作系统的负载，让进程在就绪和运行状态之间切换。从就绪到运行意味着该进程已经被调度；从运行到就绪则意味着该进程已经被取消调度；一旦进程被阻塞，OS 将保持进程的这种状态，直到发生某种事件。此时，进程再次转入就绪状态(或立即再次运行)。

我们来看一个例子，看两个进程如何通过这些状态转换。首先想象两个正在运行的进程，每个进程只使用 CPU。在这种情况下，每个进程的状态可能如下所示：

在下一个例子中，第一个进程在运行一段时间之后发起 IO 请求。此时该进程被阻塞，让另一个进程有机会运行：

更具体的说，Process0 发起 IO 并被阻塞，等待 IO 完成。OS 发现 Process0 不使用 CPU，因此开始运行 Process1。当 Process1 运行时，Process0 的 IO 完成，状态变为就绪。最后 Process1 结束，Process0 运行，然后完成。

请注意，即使是在这个简单的例子中，操作系统也必须做出很多决定。首先，系统必须决定在 Process0 发出 IO 时运行 Process1。这样做可以通过保持 CPU 繁忙来提供资源利用率。其次，当 IO 完成时，系统决定不立即切换为 Process0。目前还不清楚这是不是一个很好的决定。这类决策由操作系统调度程序完成，后续几章将会展开详细的讨论。

数据结构

操作系统是一个程序，和其他程序一样，它拥有一些关键的数据结构来跟踪各种相关的信息。比如，为了跟踪每个进程的状态，操作系统可能会为所有就绪的进程保留某种进程列表，以及跟踪当前正在运行的进程的一些附加信息。操作系统还必须以某种方式跟踪阻塞的进程。当 IO 事件完成时，操作系统应确保唤醒正确的进程，使其准备好再次运行。

// the registers xv6 will save and restore
// to stop and subsequently restart a process
struct context {
  int eip;
  int esp;
  int ebx;
  int ecx;
  int edx;
  int esi;
  int edi;
  int ebp;
};

// the different states a process can be in
enum proc_state { UNUSED, EMBRYO, SLEEPING,
                  RUNNABLE, RUNNING, ZOMBIE };

// the information xv6 tracks about each process
// including its register context and state
struct proc {
  char *mem;                   // Start of process memory
  uint sz;                     // Size of process memory
  char *kstack;                // Bottom of kernel stack
                               // for this process
  enum proc_state state;       // Process state
  int pid;                     // Process ID
  struct proc *parent;         // Parent process
  void *chan;                  // If non-zero, sleeping on chan
  int killed;                  // If non-zero, have been killed
  struct file *ofile[NOFILE];  // Open files
  struct inode *cwd;           // Current directory
  struct context context;      // Switch here to run process
  struct trapframe *tf;        // Trap frame for the
                               // current interrupt
};

上面的代码展示了 OS 需要跟踪 xv6 内核中每个进程的信息类型。“真正的”操作系统中存在类似的进程结构。

从上面的代码可以看到操作系统跟踪进程的一些重要信息。对于停止的进程，寄存器上下文将保存其寄存器的内容。当一个进程停止时，它的寄存器将被保存到该内存位置。通过恢复这些寄存器(将它们的值放回实际的物理寄存器中)，操作系统可以恢复运行该进程。我们将在后面的章节中详细了解该技术，即上下文切换。

从上面的代码中还可以看到，除了运行、就绪、阻塞之外，进程还可能处于一些其他状态。有时候系统会有一个初始状态，表示进程在创建时处于的状态。另外，一个进程可以处于已退出但尚未清理的最终状态(UNIX 中的僵尸状态)。这个最终状态非常有用，因为它运行其他进程(通常是该进程的父进程)检查进程的返回代码，并查看刚刚完成的进程是否执行成功。完成后，父进程将进行最后一次调用，以等待子进程的完成，并告诉操作系统可以清理这个正在结束的进程的所有相关数据结构。

补充：数据结构——进程列表 操作系统充满了我们将要在本书中讨论的各种重要的数据结构。进程列表是第一个这样的结构。这种结构比较简单，但是任何能够同时运行多个程序的操作系统当然都会有这种类似的结构，以便跟踪系统中运行的所有程序。有时人们会将存储关于进程信息的个体结构称为进程控制块(PCB)，这是谈论包含每个进程信息的 C 结构的一种方式。

3 - 插叙-进程 API

关键问题：如何创建并控制进程

fork 系统调用

系统调用 fork 用户创建新的进程，但要小心，这可能是你使用过的最奇怪的接口。具体来说，你可以运行一个程序，如下面的代码所示。

1    #include <stdio.h>
2    #include <stdlib.h>
3    #include <unistd.h>
4
5    int
6    main(int argc, char *argv[])
7    {
8        printf("hello world (pid:%d)\n", (int) getpid());
9        int rc = fork();
10       if (rc < 0) {        // fork failed; exit
11           fprintf(stderr, "fork failed\n");
12           exit(1);
13       } else if (rc == 0) { // child (new process)
14           printf("hello, I am child (pid:%d)\n", (int) getpid());
15       } else {             // parent goes down this path (main)
16           printf("hello, I am parent of %d (pid:%d)\n",
17                   rc, (int) getpid());
18       }
19       return 0;
20    }

运行这段程序你将看到以下输出：

prompt> ./p1
hello world (pid:29146)
hello, I am parent of 29147 (pid:29146) 
hello, I am child (pid:29147)
prompt>

让我们更详细的了解以下上面的程序发生了什么。当它开始运行时，进程输出一条 hello workd 信息，以及自己的进程描述符(PID)。该进程的 PID 是 29146。在 UNIX 系统中，如果要操作某个进程，就要通过 PID 来指明。到目前为止一切正常。

紧接着有趣的事情发生了。进程调用了 fork 系统调用，这是操作系统提供了创建新进程的方法。新创建的进程几乎与调用进程完全一样，对操作系统来说，这时看起来有两个完全一样的的程序在运行，并都从 fork 系统调用中返回。新创建的进程称为子进程，原来的进程称为父进程。子进程不会从 main 方法开始执行，而是直接从 fork 系统调用返回，就好像是它自己调用了 fork。

你可能已经注意到，子进程并不是完全拷贝了父进程。具体来说，虽然它拥有自己的地址空间(自己的私有内存)、寄存器、程序计数器等，但是它从 fork 返回的值是不同的。父进程获得的返回值是新创建子进程的 PID，而子进程获得的返回值是 0。这个差别非常重要，因为这样很容易来编写代码以处理两种不同的情况。

你可能还会注意到，该程序的输出是不确定的。子进程被创建后，我们就需要关心系统中的两个活动进程了：子进程和父进程。假设我们在单个 CPU 的系统上运行，那么子进程或父进程在此时都有可能运行。在上面的例子中，父进程先运行并输出信息。在其他情况下，子进程可能先运行，会有以下输出结果：

prompt> ./p1
hello world (pid:29146) 
hello, I am child (pid:29147)
hello, I am parent of 29147 (pid:29146) 
prompt>

CPU 调度程序决定了某个时刻哪个进程应该被执行，我们稍后将详细介绍这部分内容。由于 CPU 调度程序非常复杂，所以我们不能假设哪个进程会首先执行。事实表明，这种不确定性会导致一些有趣的问题，特别是在多线程程序中。

wait 系统调用

到目前为止，我们只是创建了一个进程，打印信息然后退出。事实表明，有时候父进程需要等待子进程执行完毕。这项任务由 wait 系统调用(或更完整的接口 waitpid)来完成。

1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <unistd.h>
4 #include <sys/wait.h>
5
6    int
7    main(int argc, char *argv[])
8    {
9        printf("hello world (pid:%d)\n", (int) getpid());
10       int rc = fork();
11       if (rc < 0) {        // fork failed; exit
12           fprintf(stderr, "fork failed\n");
13           exit(1);
14       } else if (rc == 0) { // child (new process)
15           printf("hello, I am child (pid:%d)\n", (int) getpid());
16       } else {    // parent goes down this path (main)
17           int wc = wait(NULL);
18           printf("hello, I am parent of %d (wc:%d) (pid:%d)\n",
19                   rc, wc, (int) getpid());
20       }
21       return 0;
22    }

在上面的例子中，父进程调用 wait，延迟自己的执行，直到子进程执行完毕。当子进程结束时，wait 才返回父进程。以下是输出结果：

prompt> ./p2
hello world (pid:29266) 
hello, I am child (pid:29267)
hello, I am parent of 29267 (wc:29267) (pid:29266) 
prompt>

通过这段代码，现在我们知道子进程总是先输出结果。其实，子进程可能只是碰巧先运行，因此会先于父进程输出结果。但是，如果碰上父进程先运行，它会立即调用 wait。该系统调用会在子进程运行结束后才返回。因此，即使父进程先于子进程运行，它也会礼貌的等待子进程运行完毕，然后 wait 返回，接着父进程才输出自己的信息。

exec 系统调用

它是创建进程 API 的重要部分。该系统调用可以让子进程执行与父进程完全不同的程序。比如上面提到的 fork，只有你想运行与父进程相同程序的考培时才有用。但是，我们经常需要运行不同的程序。

1    #include <stdio.h>
2    #include <stdlib.h>
3    #include <unistd.h>
4    #include <string.h>
5    #include <sys/wait.h>
6
7    int
8    main(int argc, char *argv[])
9    {
10       printf("hello world (pid:%d)\n", (int) getpid());
11       int rc = fork();
12       if (rc < 0) {        // fork failed; exit
13           fprintf(stderr, "fork failed\n");
14           exit(1);
15       } else if (rc == 0) { // child (new process)
16           printf("hello, I am child (pid:%d)\n", (int) getpid());
17           char *myargs[3];
18           myargs[0] = strdup("wc");   // program: "wc" (word count)
19           myargs[1] = strdup("p3.c"); // argument: file to count
20           myargs[2] = NULL;          // marks end of array
21           execvp(myargs[0], myargs); // runs word count
22           printf("this shouldn't print out");
23       } else {    // parent goes down this path (main)
24           int wc = wait(NULL);
25           printf("hello, I am parent of %d (wc:%d) (pid:%d)\n",
26                   rc, wc, (int) getpid());
27       }
28       return 0;
29	  }

输出结果为：

prompt> ./p3
hello world (pid:29383) 
hello, I am child (pid:29384)
      29     107   1030 p3.c
hello, I am parent of 29384 (wc:29384) (pid:29383)
prompt>

在上面的例子中，子进程调用 execvp 来运行字符计数程序 wc。实际上，它针对源代码文件 p3.c 运行 wc，从而告诉我们该文件有多少行、多少单词以及多少字节。

fork 系统调用很奇怪，它的伙伴 exec 也不简单。给定可执行程序的名称以及需要的参数后，exec 会从可执行程序中加载代码和静态数据，并用它覆盖自己的代码段，堆、栈以及其他内存空间也会被重新初始化。然后操作系统就执行该程序，将参数通过 argv 传递给该进程。因此，它并没有创建新进程，而是直接将当前运行的程序替换为不同的运行程序。子进程执行 exec 后，几乎就像 p3.c 从未运行过一样。对 exec 的成功调用永远不会返回。

为什么这样设计 API

为什么设计如此奇怪的接口来完成简单的、创建新进程的任务？事实证明，这种分离 fork 和 exec 的做法在构建 UNIX shell 的时候非常有用，因此这给了 shell 在 fork 之后 exec 执行前运行代码的机会，这些代码可以在运行新程序前改变环境，从而让一系列有趣的功能得以实现。

提示：重要的是做对事(LAMPSON 定律) Lampson 在他的著名论文《Hints for Computer Systems Design》中曾经说过：“做对事。抽象和简化不能替代做对事。”有时你必须做正确的事，当你这样做时，总是好过其他方案。有许多方式来设计创建进程的 API，但 fork 和 exec 的组合既简单又极其强大。因此 UNIX 的设计师们做对了。

shell 也是一个用户程序，它首先显示一个提示符，然后等待用户输入。你可以向它输入一个命令，大多数情况下，shell 可以在文件系统中找到这个可执行程序，调用 fork 来创建新的进程，并调用 exec 的某个变体来执行这个可执行程序，调用 wait 等待该命令完成。子进程执行结束后，shell 从 wait 返回并再次输出一个提示符，等待用户输入下一条命令。

fork 和 exec 的分离，然 shell 可以方便的实现很多有用的功能。比如：

prompt> wc p3.c > newfile.txt

在上面的例子中，wc 的输出结果被重定向到文件 newfile.txt 中。shell 实现重定向的方式很简单，当完成子进程的创建后，shell 在滴啊用 exec 之前先关闭了标准输出，打开了文件 newfile.txt。这样，即将运行的程序 wc 的输出结果就被发送到该文件，而不是打印在屏幕上。

1    #include <stdio.h>
2    #include <stdlib.h>
3    #include <unistd.h>
4    #include <string.h>
5    #include <fcntl.h>
6    #include <sys/wait.h>
7
8    int
9    main(int argc, char *argv[])
10   {
11       int rc = fork();
12       if (rc < 0) {    // fork failed; exit
13           fprintf(stderr, "fork failed\n");
14           exit(1);
15       } else if (rc == 0) { // child: redirect standard output to a file
16           close(STDOUT_FILENO);
17           open("./p4.output", O_CREAT|O_WRONLY|O_TRUNC, S_IRWXU);
18
19           // now exec "wc"...
20           char *myargs[3];
21           myargs[0] = strdup("wc");       // program: "wc" (word count)
22           myargs[1] = strdup("p4.c");      // argument: file to count
23           myargs[2] = NULL;               // marks end of array
24           execvp(myargs[0], myargs);     // runs word count
25       } else {                           // parent goes down this path (main)
26           int wc = wait(NULL);
27       }
28       return 0;
29   }

prompt> ./p4
prompt> cat p4.output
      32     109    846 p4.c
prompt>

上面的代码展示了这样做的一个程序。重定向的工作原理，是基于对操作系统管理文件描述符方式的假设。具体来说，UNIX 系统从 0 开始寻找可以使用的文件描述符。在该例子中，STDOUT_FILENO 将成为第一个可用的文件描述符，因此在 open 被调用时，得到赋值。然后子进程像标准输出文件描述符的写入，都会被透明的转向新打开的文件，而不是屏幕。

关于这个输出，你至少会注意到两个有趣的地方。首先，当运行完 p4 程序后，好像什么也没有发生。shell 只是打印了提示符，等待用户的下一个命令。但事实并非如此，p4 确实调用了 fork 来创建新的子进程，之后调用 execvp 来执行 wc。屏幕上没有看到输出，是由于结果被重定向到 p4.output。其次，当用 cat 命令打印输出文件时，能看到运行 wc 的所有预期输出。

UNIX 管道也是用类似的方式实现的，但用的是 pipe 系统调用。在这种情况下，一个进程的输出被链接到了一个内核管道(pipe)上(队列)，另一个进程的输入也被连接到了同一个管道上。因此，前一个进程的输出无缝的作为后一个进程的输入，许多命令可以用这种方式串联在一起，共同完成某项任务。比如通过将 grep、wc 命令用管道连接可以完成从一个文件查找某个词，并统计其出现次数的可能：grep -o foo file | wc -l。

最后，我们刚才只是从较高层面上简单介绍了进程 API，关于这些系统调用的细节，还有更多的内容需要学习和理解。

其他 API

除了上面提到过的 API，在 UNIX 中还有其他许多与进程交互的方式。比如可以通过 kill 系统调用向进程发送信号，包括要求进程睡眠、终止或其他有用的指令。实际上，整个信号子系统提供了一套丰富的向进程传递外部事件的途径，包括接受和执行这些信号。

此外还有很多非常有用的命令行工具。比如通过 ps 命令来查看当前运行的进程，阅读 man 手册来了解 ps 命令所能接受的参数。

4 - 机制-受限直接执行

为了虚拟化 CPU，操作系统需要以某种方式让许多任务共享物理 CPU，让它们看起来像是在同时运行。基本思想很简单：运行一个进程一段时间，然后运行另一个进程，如此轮换。通过这种方式分时共享 CPU，就实现了虚拟化。

然而，在构建这样的虚拟化机制时存在一些挑战。第一个是性能：如何在不增加系统开销的情况下实现虚拟化？第二个是控制权：如何有效的运行进程，同时保留对 CPU 的控制？控制权对于操作系统尤为重要，因为操作系统负责管理资源。如果没有控制权，一个进程可以简单的无限制运行并接管机器，或者访问原本没有权限的信息。因此，在保持控制权的同时获得高性能，是构建操作系统的主要挑战之一。

关键问题：如果高效可控的虚拟化 CPU 操作系统必须以高性能的方式虚拟化 CPU，同时保持对系统的控制。为此，需要硬件和操作系统的支持。操作系统通常会明智的利用硬件的支持，以便高效的实现其工作。

基本技巧：受限直接执行

为了使程序尽可能快的执行，操作系统开发人员想出了一种技术——我们称之为受限的直接执行。这个概念的“直接执行”部分很简单：只需直接在 CPU 上运行程序即可。因此，当 OS 希望启动程序运行时，它会在进程列表中为其创建一个进程条目，为其分配一些内存，将程序代码从磁盘加载到内存中，找到入口点并跳转到那里，然后开始执行用户的代码。下表展示了这种基本的直接执行协议(没有任何限制)，使用正常的调用并返回跳转到程序的 mian，并在稍后回到内核。

听起来很简单，但是这种方法在我们虚拟化 CPU 时产生了一些问题。第一个问题很简单：如果我们只运行一个程序，操作系统怎么能确保程序不做任何我们不希望它做的事情，同时仍然能够高效执行？第二个问题：当我们运行一个进程时，操作系统如何让它停下来并切换到另一个进程，从而实现虚拟化 CPU 所需要的分时共享？

下面在回到这些问题时，我们将更好的了解虚拟化 CPU 需要什么。在开发这些技术时，我们还会看到标题中的“受限”部分来自哪里。如果对运行程序没有限制，操作系统无法控制任何事情，因此会成为“仅仅是一个库”——对应有抱负的操作系统而言，这真是令人悲伤的事情！

问题 1：受限制的操作

直接执行的明显优势是快速。该程序直接在硬件 CPU 上执行，因此执行速度与预期的一样快。但是，在 CPU 上运行会带来一个问题——如果进程希望执行某种受限操作，比如向磁盘发起 IO 请求或获得更多系统资源，该怎么办？

提示：采用受保护的控制权转移 硬件通过提供不同的执行模式来协助操作系统。在用户模式下，应用程序不能完全访问硬件资源。在内核模式下，操作系统可以访问机器的全部资源。还提供了陷入内核和从陷阱返回到用户模式程序的特别说明，以及一些指令，让操作系统告诉硬件陷阱表在内存中为位置。

对于 IO 和其他相关操作，一种方法就是让所有进程做所有它想做的事情。但是，这样做导致无法构建许多我们想要的系统。例如，如果我们希望构建一个在授予文件访问权限前检查权限的文件系统，就不能简单的让任何用户进程都可以向磁盘发起 IO 请求。如果这样做，一个进程就可以读写整个磁盘，这样所有的保护都将失效。

因此，我们采用的方法是引入一种新的处理器模式，称为用户模式。在用户模式下运行的代码会收到限制。比如，在用户模式下运行时，进程不能发出 IO 请求。这样做会导致处理器引发异常，操作系统可能会终止进程。

与用户模式不同的内核模式，操作系统就可以以这种模式运行。在该模式下，运行的代码可以做它喜欢的事情，包括特权操作，如果发出 IO 请求或执行所有类型的受限指令。

但是，我们仍然面临一个挑战——如果用户希望执行某种特权操作，应该怎么办？为了实现这一点，几乎所有的现代硬件都提供了用户程序执行系统调用的能力。系统调用是在 Atlas 等古老机器上开创的，它允许内核小心的向用户程序暴露某些关键功能，例如访问文件系统、创建和销毁进程、与其他进程通信，以及分配更多内存。大多数操作系统能提供几百个调用。早期的 UNIX 系统公开了更加简洁的子集，大约 20 个调用。

要执行系统调用，程序必须执行特殊的陷阱指令。该指令同时跳入内核并将特权界别提升到内核模式。一旦进入内核，系统即可以执行任何允许的特权操作，从而为调用进程执行需要的工作。完成后，操作系统调用一个特殊的从陷阱返回的指令，如你期望的那样，该指令返回到发起调用的用户程序中，同时将特权级别降低，回到用户模式。

执行陷阱时，硬件需要小心，因为它必须确保存储足够的调用者寄存器，以便在操作系统发出从陷阱返回的指令时能够正确返回。比如在 X86 上，处理器会将程序计数器、标志和其他一些寄存器推送到每个进程的内核栈上。从陷阱返回将从栈弹出这些值，并恢复执行用户模式程序。其他硬件系统使用不同的约定，但基本概念在各个平台上是类似的。

补充：为什么系统调用看起来像是过程调用？ 你可能想知道，为什么系统调用(open/read)看起来完全像是 C 中典型的过程调用。也就是说，如果它看起来像是一个过程调用，系统又是如何知道它是一个系统调用呢，并做出正确的响应？原因很简单：它是一个过程调用，但隐藏在过程调用内部的是著名的陷阱指令。 更具体的说，当你调用 open 时，你正在执行对 C 库的过程调用。其中，无论是对于 open 还是提供的其他系统调用，库都使用与内核一致的调用约定来将参数放在众所周知的位置(如栈中或特定的寄存器中)，将系统调用号也放在一个众所周知的位置，然后再执行上述陷阱指令。 在库中，陷阱之后的代码准备好返回值，并将控制权返回给发出系统调用的程序。因此，C 库中进行系统调用的部分是用汇编手工编码的，因为它需要仔细遵循约定，以便正确的处理参数和返回值，以及执行硬件特定的陷阱指令。 现在你知道为什么你自己不必编写汇编来陷入操作系统内核了吧，因为已经有人完成了这些工作。

还有一个重要的细节没有讨论：陷阱如何知道在 OS 内执行哪些代码？显然，发起调用的过程不能指定要跳转到的地址(就像你在进行过程调用时一样)，这样做让程序可以跳转到内核中的任意位置，这显然是一个糟糕的主意。因此内核必须谨慎的控制在陷阱中执行的代码。

内核通过在启动时设置陷阱表来实现。当机器启动时，它在特权(内核)模式下执行，因此可以根据需要自由配置机器硬件。操作系统做的第一件事就是告诉硬件在发生某些异常事件时要运行哪些代码。比如，当发生磁盘中断、发生键盘中断或程序进行系统调用时，应该运行哪些代码。操作系统通常通过某种特殊的指令，通知硬件这些陷阱处理程序的位置。一旦硬件被通知，它就会记住这些处理程序的位置，直到下一次重启机器，并且硬件知道在发生系统调用和其他异常事件时要做什么(即跳转到那段代码)。

最后，能够执行指令来告诉硬件陷阱表的位置是一个非常强大的功能。因此你可能已经猜到，这也是一项特权操作。如果你试图在用户模式下执行这些指令，硬件是不会允许的。如果你可以自己设置陷阱表，你可以对系统做些什么呢？你能接管机器码？

时间线总结了该协议。我们假设每个进程都有一个内核栈，在进入内核和离开内核时，寄存器分别被保存和恢复。

下表是“受限直接运行协议”：

LDE 协议有两个阶段。第一个阶段(在系统引导时)，内核初始化陷阱表，并且 CPU 记住他的位置以供随后使用。内核通过特权指令来执行此操作。第二个阶段(运行进程时)，在使用从陷阱返回指令开始执行进程之前，内核设置了一些内容。这会将 CPU 切换到用户模式并开始运行该程序。当进程希望发出系统调用时，它会重新陷入操作系统，然后再次通过从陷阱返回，将控制权还给进程。该进程然后完成它的工作，并从 main 返回。这通常会返回到一些存根代码，它将正确退出该程序。此时，OS 清理干净，任务完成。

问题 2：进程间切换

直接执行的下一个问题是进程间切换。实际上这个问题很棘手，特别是，如果一个进程在 CPU 上运行，这就意味着这时操作系统没有运行。如果操作系统没有处于运行状态，它又怎么做事情？虽然这听起来几乎是哲学，但这是真正的问题——如果操作系统没有在 CPU 上运行，那么显然操作系统没有办法采取行动。因此，我们遇到了关键问题。

协作方式：等待系统调用

过去某些系统采用的一种方式成为“协作方式”。在这种形式下，操作系统会相信系统中的进程会合理运行。运行时间过长的进程被假定会定期放弃 CPU，以便操作系统可以决定运行其他任务。

因此你可能会问，在这个虚拟的世界中，一个友好的进程如何放弃 CPU？事实证明，大多数进程通过执行调用，将 CPU 的控制权转移给操作系统，比如打开文件并随后读取文件，或者向另一台机器发送消息或创建新的进程。像这样的系统通常包括一个显式的 yield 系统调用，它什么也不干，只是将控制权交给操作系统，以便操作系统可以运行其他进程。

如果应用程序执行了某些非法操作，也会将控制权转移给操作系统。比如，如果应用程序已 0 为除数，或者尝试访问无法访问的内存，就会陷入操作系统。操作系统将再次控制 CPU，并可能终止违规进程。

因此，在协作调度系统中，OS 通过等待系统调用，或某种非法操作发生，从而重新获得 CPU 的控制权。你也许会想到，这种被动方式是不是不太理想？比如，如果某个进程进入无线循环并且从不进行系统调用，或发生什么情况？那么操作系统又能做什么？

非协作方式：操作系统进行控制

事实证明，没有硬件的额外帮助，如果进程拒绝执行系统调用而且不出错，从而将控制权交还给操作系统，那么操作系统无法做什么事情。事实上，在协作方式中，当进程陷入无限循环时，唯一的办法就是使用古来的解决方案来处理计算机系统中的所有问题——重新启动计算机。因此，我们又遇到了请求获得 CPU 控制权的一个子问题。

关键问题：如何在没有协作的情况下获得控制权？ 即使进程不协作，操作系统如何获得 CPU 控制权？操作系统如何保证流氓进程不会占有机器？

答案很简单，很多年前构建计算机系统的人都发现了：时钟中断。时钟设备可以变成为每隔几毫秒产生一次中断。产生中断时，当前正在运行的进程停止，操作系统中预先配置的中断处理程序会运行。这时，操作系统重新获得了 CPU 的控制权，因此可以做它想做的事情：停止当前进程，并启动另一个进程。

提示：利用时钟中断重新获得控制权 即使进程以非协作的方式运行，添加时钟中断也让操作系统能够在 CPU 上重新运行。因此，该硬件功能对于操作系统维持机器的控制权至关重要。

首先，正如我们之前讨论过的系统调用一样，操作系统必须通知硬件哪些代码需要在发生中断时运行。因此，在启动时，操作系统就是这样做的。其次，在启动过程中，操作系统也必须启动时钟，这当然是一项特权操作。一旦时钟开始运行，操作系统就感到安全了，因为控制权最终会归还给他，因此操作系统可以自由运行用户程序。时钟也可以关闭，在稍后对并发的讲解中我们会进行讨论。

请注意，硬件在发生中断时有一定的责任，尤其是在发生中断时，要为正在运行的程序保存足够的状态，以便随后从陷阱返回指令能够正确的恢复该程序。这一组操作与硬件在显式系统调用陷入内核时的行为非常相似，其中各种寄存器因此会被保存，因此可以很容易的从陷阱返回指令恢复。

保存和恢复上下文

既然操作系统已经重新获得了控制权，无论是通过系统调用协作，还是通过时钟中断强制执行，都必须决定：是继续运行当前正在运行的进程，还是切换到另一个进程。这个决定是由调度程序做出的，它是操作系统的一部分。我们将在接下来的几章中详细讨论调度策略。

如果决定进行切换，OS 就会执行一些底层代码，即所谓的上下文切换。上下文切换在概念上很简单：操作系统要做的就是为当前正在执行的进程保存一些寄存器的值，并未即将执行的进程恢复一些寄存器的值。这样一来，操作系统就可以确保最后执行从陷阱返回指令时，不是返回到之前运行的进程，而是继续执行另一个进程。

为了保存当前正在运行的进程的上下文，操作系统会执行一些底层汇编代码，来保存通用寄存器、程序计数器，以及当前正在运行的进程的内核栈指针，然后恢复寄存器、程序计数器，并切换内核栈，供即将运行的进程使用。通过切换栈，内核在进入切换代码调用时，是一个(被中断的)进程的上下文，返回时，是另一个(即将执行的)进程的上下文。当操作系统最终执行从陷阱返回指令时，即将执行的进程编程了当前运行的进程。至此，一次上下文切换过程完成。

上表展示了完整的时间线。在这个例子中，进程 A 正在运行，然后被时钟中断。硬件(在内核栈中)保存其寄存器，并进入内核栈(切换到内核模式)。在时钟中断处理程序中，操作系统决定从正在运行的进程 A 切换到进程 B。此时，它调用 switch 例程，该例程仔细保存当前寄存器的值(保存到 A 的进程结构)，恢复寄存器进程 B(从 B 的进程结构)，然后切换上下文，具体来说是通过改变栈指针来使用 B 的内核栈(而不再是 A)。最后，操作系统从陷阱返回，恢复 B 的寄存器并开始运行 B。

请注意，在此协议中，有两种类型的寄存器保存和恢复。第一种是发生时钟中断的时候，在这种情况下，运行进程的用户寄存器由硬件隐式保存，使用的是该进程的内核栈。第二种是当操作系统决定从 A 切换到 B。在这种情况下，内核寄存器被软件(即 OS)明确的保存，但这次被存储在该进程的进程结构对应的内存中。后一个操作让系统从好像刚刚 A 陷入内核，编程好像刚刚从 B 陷入内核。

为了更好的理解如何实现这种切换，下面的代码展示了具体的实现过程。context 结构的 old 和 new 分别在老的和新的进程的进程结构中。

1    # void swtch(struct context **old, struct context *new);
2    #
3    # Save current register context in old
4    # and then load register context from new.
5    .globl swtch
6    swtch:
7      # Save old registers
8      movl 4(%esp), %eax # put old ptr into eax
9      popl 0(%eax)        # save the old IP
10     movl %esp, 4(%eax) # and stack
11     movl %ebx, 8(%eax) # and other registers
12     movl %ecx, 12(%eax)
13     movl %edx, 16(%eax)
14     movl %esi, 20(%eax)
15     movl %edi, 24(%eax)
16     movl %ebp, 28(%eax)
17
18     # Load new registers
19     movl 4(%esp), %eax # put new ptr into eax
20     movl 28(%eax), %ebp # restore other registers
21     movl 24(%eax), %edi
22     movl 20(%eax), %esi
23     movl 16(%eax), %edx
24     movl 12(%eax), %ecx
25     movl 8(%eax), %ebx
26     movl 4(%eax), %esp  # stack is switched here
27     pushl 0(%eax)       # return addr put in place
28     ret                 # finally return into new ctxt

并发问题

作为细心的读者，你们可能会想到：在系统调用期间发生时钟中断会发生什么？或者，在处理一个中断时又发生了另一个中断，这时会发生什么？这不会让内核难以处理吗？

如果在中断或陷阱处理过程中发生另一个中断，那么操作系统确实需要关心发生了什么。实际上，这正是本书第二部分关于并发的主题。

补充：上下文切换的耗时 一个自然的问题是：上下文切换需要多久，或者系统调用需要多久。 随着时间的推移，结果有了很大的提高，大致跟上了处理器你的性能提升。比如，1996 年在 200-MHz P6 CPU 上运行 Linux 1.3.37，系统调用花费了 4us，上下文切换的时间大致为 6us。现代操作系统的性能几乎可以提高一个数量级，在具有 2GHz 或 3GHz 处理器的系统上的性能可以达到亚微秒级。 应该注意的是，并非所有的操作系统都会跟踪 CPU 的性能。正如 Ousterhout 所说，许多操作系统的操作都是内存密集型的，而随着时间的推移，但随着时间的推移，内存带宽并没有像处理器速度那样显著提高。因此，根据你的工作负载，购买最新的、性能好的处理器可能不会像你期望的那样加速操作系统。

为了让你开开胃，我们只是简单介绍了操作系统如何处理这些棘手的情况。操作系统可能简单的决定，在中断处理期间禁止中断。这样做可以确保在处理一个中断时，不会将其他中断交给 CPU。当然，操作系统这样做必须小心。禁用中断时间过长则可能导致中断丢失，这在技术上是不好的。

操作系统还开发了许多复杂的加锁方案，以保护对内部数据结构的并发访问。这使得多个活动可以同时在内核中进行，特别适用于多处理器。我们将在后续章节中看到，这种锁可能会变得复杂，并导致各种有趣且难发现的错误。

小结

我们已经描述了一些实现 CPU 虚拟化的关键底层机制，并将其统称为受限直接执行。基本思路很简单：就让你想运行的程序在 CPU 上运行，但首先要确保设置好硬件，以便在没有操作系统帮助的情况下限制进程可以执行的操作。

这种一般方法在现实生活中也适用。比如，有些孩子会熟悉宝宝防护房间的概念——锁好包含危险物品的柜子，并掩盖电源插座。当这些都准备妥当时，你可以让宝宝自由行动，确保房间最危险的方面受到限制。

提示：重新启动是有用的 之前我们指出，在协作式抢占时，无限循环的唯一解决方案是重启机器。虽然你可能嘲笑这种粗暴的做法，但研究表明，重启(软件)可能构建强大系统的一个非常有用的工具。 具体来说，重新启动很有用，因为它让软件回到已知的状态，很可能是经过更多测试的状态。重新启动还可以回收旧的或泄露的资源，否则这些资源可能很难处理。最后，重启很容易自动化。由于所有这些原因，在大规模互联网服务中，系统管理软件定期重启一些机器，重置它们并因此获得以上好处，这并不少见。

通过类似的方式，OS 首先在启动时设置陷阱处理程序并启动中断时钟，然后仅在受限模式下运行进程，以此为 CPU 提供宝宝防护。这样做，操作系统能确信进程可以高效运行，只在执行特权操作，或者让它们独占 CPU 时间过长并因此需要切换时，才需要操作系统干预。

至此，我们有了虚拟化 CPU 的基本机制。但一个主要问题还没有答案：在特定时间，我们应该运行哪个进程？调度程序可以解答这个问题。

5 - 进程调度

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

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

工作负载假设

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

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

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

• 每个工作运行相同的时间。
• 所有的工作同时到达。
• 一旦开始，每个工作保持运行直到完成。
• 所有的工作只使用 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 结合到场景中，但仍未解决操作系统根本无法看到未来的问题。稍后，我们将看到如何构建一个调度程序，利用最近的历史预测未来。这个调度程序被称为多级反馈队列。

6 - 调度-多级反馈队列

本章将介绍一种著名的调度方法——多级反馈队列(MLFQ)。1962 年，Corbato 首次提出多级反馈队列，应用于兼容分时共享系统。Corbato 因在 CTSS 中的贡献和后来的 Multics 中的贡献，获得了 ACM 颁发的图灵奖。该调度程序经过多年的一系列优化，出现在许多现代操作系统中。

多级反馈队列需要解决两方面的问题。首先需要优化周转时间。上一章我们看到，可以通过先执行较短工作来实现。然而，操作系统通常不知道工作的长度，而这又是 SJF/STCF 等算法所必须的。其次，MLFQ 希望给交互用户带来更好的交互体验，因此需要降低响应时间。然而，像轮转这样的算法虽然降低了响应时间，周转时间却很差。所以这里的问题是：通常我们对进程一无所知，应该如何构建调度程序来实现这些目标？调度程序如何在运行过程中学习进程的特征，从而做出更好的调度决策？

提示：从历史中学习 多级反馈队列是使用历史的经验来预测未来的典型实例，操作系统中有很多地方采用了这种技术。如果工作有明显的阶段性行为，因此可以预测，这种方式会很有效。当然，必须小心使用这种技术，因为它可能出错，让系统做出比一无所知还要糟的决定。

MLFQ：基本规则

为了构建这样的调度程序，本章将介绍多级反馈队列背后的基本算法。虽然对应的实现有很多，但大都类似。

MLFQ 中有许多独立的队列，每个队列有不同的优先级。任何时刻，一个工作只能存在于一个队列中。MLFQ 总是优先执行较高优先级的工作(即在较高级队列中的工作)。

当然，每个队列中可能会有多个工作，因此它们具有相同的优先级。在这种情况下，我们就对这些工作采用轮转调度。

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

至此，我们得到了 MLFQ 的两条基本规则。

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

如果要在某个特定的时刻展示这些队列，可能会看到类似上面的内容。最高优先级中有两个工作 AB，工作 C 位于中等优先级队列，而 D 的优先级最低。按刚才介绍的基本规则，由于 A 和 B 有最高优先级，调度程序将交替的调度它们，可怜的 C 和 D 永远没有机会运行，太气人了！

当然，这只是展示了一些队列的静态快照，并不能让你真正明白 MLFQ 的工作原理。我们需要理解工作的优先级如何随时间变化。

尝试 1：如何改变优先级

我们必须决定，在一个工作的生命周期中，MLFQ 如何改变其优先级。要做到这一点，我们必须记得工作负载：既有时间很短、频繁放弃 CPU 的交互型工作，也有需要很多 CPU 时间、响应时间缺不重要的长时间计算密集型工作。下面是我们第一次尝试优先级调整算法。

• 规则 3：工作进入系统时，放在最高优先级。
• 规则 4a：工作用完真个时间片后，降低其优先级。
• 规则 4b：如果工作在其时间片以内主动释放 CPU，则优先级不变。

实例 1：单个长工作

如果系统中有一个需要长时间运行的工作，看看会发生什么。下图展示了在一个拥有 3 个队列的调度程序中，随着时间的推移，这个工作的运行情况。

从这个例子可以看出，该工作首先进入最高优先级。执行一个 10ms 的时间片后，调度程序将工作的优先级减低 1，因此进入 Q1。在 Q1 执行一段时间后，最终降低优先级进入到系统的最低优先级队列 Q0，并一直留在那里。

实例 2：来了一个短工作

再看一个复杂的例子，看看 MLFQ 如何近似 SJF。在这个例子中有两个工作：A 是一个长时间运行的 CPU 密集型工作，B 是一个运行时间很短的交互型工作。假设 A 执行一段时间后 B 到达，会发生什么？对 B 来说，MLFQ 会近似于 SJF 吗？

上图展示了该场景的结果。A 在最低优先级队列执行，B 在时间 100 时到达，并被加入到最高优先级队列。由于它的运行时间很短，经过两个时间片，在被移入最低优先级队列之前，B 执行完毕。然后 A 继续执行。

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

实例 3：结合 IO

根据规则 4b，如果进程在时间片用完之前主动放弃 CPU，则保持它的优先级不变。这条规则的意图很简单：假设交互型工作中有大量的 IO 操作，它会在时间片用完之前放弃 CPU。在这种情况下我们不想惩罚它，只是保持它的优先级不变。

上图展示了这种运行过程，交互性工作 B 没执行 1ms 便需要进行 IO 操作，他与长时间运行的工作 A 竞争 CPU，MLFQ 算法保持 B 在最高优先级，因为 B 总是让出 CPU。如果 B 是交互型工作，MLFQ 就进一步实现了它的目标，让交互型工作快速运行。

当前 MLFQ 问题

至此我们有了基本的 MLFQ。看起来似乎不错，长时间工作可以公平的分享 CPU，又能给段工作或交互型工作很好的响应时间。然而，这种算法有一些非常严重的缺点。

首先，会有饥饿问题。如果系统有太多交互型工作，就会不断中断 CPU，导致长工作永远无法得到 CPU。即使在这种情况下，我们也希望这些厂工作保持进展。

其次，聪明的用户会重写程序来愚弄调度程序。愚弄调度程序指的是用一些卑鄙的手段欺骗调度程序，让它给你远超公平的资源。上述算法对如下的攻击束手无策：进程在时间片用完之前，调用一个 IO 操作(比如访问一个没有意义的文件)，从而主动释放 CPU。如此便可以保持在高优先级，占用更多的 CPU 时间。做的好时，工作几乎可以独占 CPU。

最后，一个程序可能在不同时间表现不同。一个计算密集型的进程可能在某段时间表现为一个交互型的进程。用我们目前的方法，它不会享受系统中其他交互工作的待遇。

尝试 2：提升优先级

让我们试着改变之前的规则，看看是否能避免饥饿问题。要让 CPU 密集型工作也能保持进展(即使不多)。

一个简单的思路是周期性的提升所有工作的优先级。可以有很多方法做到，但我们这里使用最简单的一种：将所有工作放到最高优先级队列。于是有了如下的新规则：

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

新规则一下解决了两个问题。首先，进程不会饥饿——在最高优先级队列中，它会以轮转的方式，与其他高由下级工作分享 CPU，从而最终获得执行。其次，如果一个 CPU 密集型工作变成了交互型，当它优先级提升时，调度程序则会正确的对待他。

我们来看一个例子。在这种场景下，我们展示了长工作与两个交互型段工作竞争 CPU 时的行为。左图没有优先级提升，长工作在两个段工作到达后被饿死。右边每 50ms 就有一次优先级提升，因此至少能够保证长工作会取得一些进展，没过 50ms 就被提神到最高优先级，从而定期获得执行。

当然，添加时间段 S 导致了明显的问题：S 的值应该如何设置？德高望重的系统研究员 John Ousterhout 曾将这种值称为巫毒常量，因为似乎需要一些黑魔法才能正确设置。如果 S 设置的太高，长工作会出现一定程度的饥饿；如果设置的太低，交互型工作又得不到合适的 CPU 时间比例。

尝试 3：更好的计时方式

现在有一个问题需要解决：如何阻止调度程序被愚弄？可以看出，这里的元凶是 4a 和 4b，导致工作在时间片内释放 CPU，就保留它的优先级。那么应该怎么做？

这里的解决方案，是为 MLFQ 的每层队列提供更完善的 CPU 计时方式。调度程序应该记录一个进程在某一层中消耗的总时间，而不是在调度时重新计时。只要进程耗尽了自己的配额，就将它降低到低一级的队列中去。不论是它是一次用完的，还是拆成很多次用完。因此我们需要改变规则 4a 和 4b。

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

来看一个例子。下图对比了在规则 4ab 的策略下和在新规则 4 的策略下，同样视图愚弄调度程序的进程表现。在没有规则 4 保护时，进程可以在每个时间片结束前发起一次 IO 操作，从而垄断 CPU 时间。有了这样的保护后，不论进程的 IO 行为如何，都会慢慢的降低优先级，因为无法获得超过公平的 CPU 时间比例。

MLFQ 调优及其他问题

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

比如，大多数的 MLFQ 变体都支持不同队列可变的时间片长度。高优先等级队列通常只有较小的时间片，因此这一层的交互工作可以更快的切换。相反，低优先级队列中更多的是 CPU 密集型工作，配置更长的时间片会取得更好的效果。下图展示了一个例子，两个长工作在高优先级队列执行 10ms，中间队列执行 20ms，最后在最低优先级队列执行 40ms。

提示：避免巫毒常量 尽可能避免巫毒常量是个好主意。然而，从上面的例子可以看出，这通常很难。当然，我们也可以让系统自己去学习一个很优化的值，但这同样也不太容易。因此，通常我们会有一个写满各种参数默认值的配置文件，使得系统管理员可以方便的进行调整。然而，大多数使用者并不会去修改这些值，这时就寄希望于默认值合适了。

Solaris 的 MLFQ 实现很容易配置。它提供了一组表来决定进程在其生命周期中如何调整优先级，每层的时间片多大，以及多久提升一个工作的优先级。管理员可以通过这些表让调度程序的行为方式不同。该表默认有 60 层队列，时间片长度从 20ms 到数百 ms，每 1s 左右提升一次进程的优先级。

其他一些 MLFQ 调度程序没有使用表，甚至没有使用本章中讲到的规则，有些采用数学公式来调整优先级。比如，FreeBSD 调度程序，会基于当前进程使用了多少 CPU，通过公式计算出某个工作的当前优先级。另外，使用量会随时间衰减，这提供了期望的优先级提升，但与这里的描述方式不同。

最后，许多调度程序有些我们没有提到特征，比如，有效调度程序将最高优先级队列留给操作系统使用，因此通常的用户工作是无法得到系统的最高优先级的。有些系统允许用户给出优先级设置的建议，比如通过命令行工具 nice，可以稍微提升或降低工作的优先级，从而增加或减低它在某个时刻运行的机会。

小结

本章介绍了一种调度方式，MLFQ。总的来说就是：以史为鉴，关注进程的一贯表现，然后区别对待。

提示：尽可能多的使用建议 操作系统很少知道什么策略对系统中的单个进程或每个进程是友好的，因此提供接口并允许用户给操作系统一些提示常常很有用。我们通常称之为建议，因为操作系统不一定要关注它，但是可能会将建议考虑在内，以便做出更好的决定。这种用户建议的方式在操作系统的各个领域经常十分有用，包括调度程序、内存管理、文件系统。

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

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

7 - 调度-比例份额

在本章中，我们卡一个不同类型的调度程序——比例份额调度程序，有时也称为公平份额调度程序。基于一个简单的思想：调度程序的最终目标是确保每个工作都能获得一定比例的的 CPU 时间，而不是优化周转时间和响应时间。

比例份额调度程序有一个非常优秀的现代实例，名为彩票调度。基本思想很简单：每个一段实现，都会举行一次彩票抽奖，以确定接下来应该运行哪个进程，越是应该频繁运行的进程，越是应该拥有更多的赢得彩票的机会。

基本概念：彩票数表示份额

彩票调度背后是一个非常基本的概念：彩票数代表了进程占有某个资源的份额。一个进程拥有的彩票数占总彩票数的百分比，就是它占有资源的份额。

下面来看一个例子。假设有两个进程 AB，A 拥有 75 张彩票，B 拥有 25 张。因此我们希望 A 占用 75% 的 CPU 时间，而 B 占用 25%。

通过不断定时(比如每个时间片)的抽取彩票，彩票调度从概率上获得这种份额比例。抽取彩票的过程很简单：调度程序知道总的彩票数。调度程序抽取中奖彩票，即 0~99 之间的一个数字，拥有这个数对应的彩票的进程中奖。假设进程 A 拥有 0~74 共 75 张彩票，进程 B 拥有 75~99 共 25 张彩票，中奖的彩票就决定了运行 A 还是 B。调度程序然后加载中奖进程的状态并使其运行。

提示：利用随机性 彩票调度最精彩的地方在于利用了随机性。当你需要作出决定时，采用随机的方式常常是既简单又可靠的选择。 随机方法限度与传统的决策方式，至少有 3 点优势。第一，随机方法常常可以避免奇怪的边角情况，较传统的算法可能在处理这些情况时遇到麻烦。例如 LRU 替换策略。虽然 LRU 是很好的替换算法，但在有重复序列的负载时表现很差。但随机方法就没有这种最差情况。 第二，随机方法很轻量，几乎不需要记录任何状态。在传统的公平份额调度算法中，记录每个集成已经获得了多少的 CPU 时间需要对每个进程计时，这必须在每次运行结束后更新。而采用随机方式后每个进程只需要非常少的状态记录。 第三，随机方法很快。只要能够很快的产生随机数，做出决策就很快。因此，随机方式在对运行速递要求很高的场景非常适用。当然，越是需要快的计算速度，随机就越倾向于伪随机。

下面是彩票调度程序输出的中奖彩票：

63 85 70 39 76 17 29 41 36 39 10 99 68 83 63 62 43 0 49 49

下面是对应的调度结果：

A     A  A       A  A  A  A  A  A       A       A  A  A  A  A  A
   B		 B						B        B

从这个例子中可以看出，彩票调度中利用了随机性，这实现了从概率上满足期望的比例，但并不能保证。在上面的例子中，工作 B 运行了 20 个时间片中的 4 个，只是占了 20%，而不是期望的 25%。但是，这两个工作运行的时间越长，它们得到的 CPU 时间比例就会越接近期望。

提示：用彩票来表示份额 彩票(步长)调度的设计中，最强大最基本的机制是彩票。在这些例子中，彩票用于表示一个进程占有 CPU 的份额，但也可以用在更多的地方。比如在迅疾管理程序的虚拟管理的最新研究工作中，Waldspurger 提出了用彩票来表示用户占用操作系统内存的方法。因此，如果你需要通过什么机制来表示所有权比例，这个概念可能就是彩票。

彩票机制

彩票调度还提供了一种机制，以不同且有效的方式来调度彩票。一种方式是利用彩票货币的概念。这种方式允许拥有一组彩票的用户以它们喜欢的某种货币，将彩票分给自己的不同工作。之后操作系统再自动将这种货币兑换为正确的全局彩票。

比如，假设用户 A 和 B 每人拥有 100 张彩票。用户 A 有两个工作 A1 和 A2，他以自己的货币，给每个工作 500 张彩票(共 1000 张)。用户 B 只运行一个工作，给它 10 张彩票(共 10 张)。操作系统将进行兑换，将 A1 和 A2 拥有的 A 的货币个 500 张兑换成全局货币个 50 张。类似的，兑换给 B1 的 10 张彩票兑换成 100 张。然后会对全局彩票货币进行抽奖(共 200 张)，决定哪个工作运行。

User A -> 500 (A's currency) to A1 -> 50 (global currency)
       -> 500 (A's currency) to A2 -> 50 (global currency)
User B -> 10 (B's currency) to B1 -> 100 (global currency)

另一个有用的机制是彩票转让。通过转让，一个进程可以临时将自己的彩票交给另一个进程。这种机制在客户端-服务器交互的场景中尤其有用，在这种场景中，客户端进程向服务端发送消息，请求其按自己的需求执行工作，为了加速服务端的执行，客户端可以将自己的彩票转让给服务端，从而尽可能加速服务端执行自己请求的速度。服务端执行结束后会将这部分彩票归还给客户端。

最后，彩票通胀有时也很有用。利用通胀，一个进程可以临时提升或降低自己拥有的彩票的数量。当然在竞争环境中，进程之间互相不信任，这种机制就没有意义。一个贪婪的进程可能给自己非常多的彩票，从而接管机器。但是，通胀可以用于进程之间互相信任的环境。在这种情况下，如果一个进程知道它需要更多 CPU 时间，就可以增加自己的彩票，从而将自己的需求告知操作系统，这一切不需要与任何其他进程通信。

实现

彩票调度中最不可思议的部分可能是其简单的实现。只需要一个不错的随机数生成器来选择中奖彩票和一个记录系统中所有进程的数据结构，以及所有彩票的总数。

假设我们用列表记录进程。下面的例子中有 ABC 三个进程，每个进程有一定数量的彩票。

在做出调度之前，首相要从彩票总数中选择一个随机数(中奖号码)。假设选择了 300，然后遍历链表，用一个简单的计数器帮助我们找到中奖者：

1    // counter: used to track if we've found the winner yet
2    int counter = 0;
3
4    // winner: use some call to a random number generator to
5    //         get a value, between 0 and the total # of tickets
6    int winner = getrandom(0, totaltickets);
7
8    // current: use this to walk through the list of jobs
9    node_t *current = head;
10
11   // loop until the sum of ticket values is > the winner
12   while (current) {
13       counter = counter + current->tickets;
14       if (counter > winner)
15           break; // found the winner
16       current = current->next;
17   }
18   // 'current' is the winner: schedule it...

这段代码从前向后遍历进程列表，将每张彩票的值加到 counter 上，直至查过 winner。这时，当前的列表元素所对应的进程就是中奖者。在我们的例子中，中奖彩票是 300。首先，计 A 的票后，counter 增加到 100。因为 100 小于 300，继续遍历。然后 counter 增加到 150 即 B 的彩票，仍然小于 300，继续遍历。最后，counter 增加到 400，因此退出遍历，current 指向中奖者 C。

要让这个过程更加高效，建议将列表项按照彩票数递减排序。这个顺序不会影响算法的正确性，但能保证用最小的迭代次数找到需要的节点，尤其当大多数彩票被少数进程掌握时。

一个例子

为了更好的理解彩票调度的运行过程，我们现在简单研究一下两个互相竞争工作的完成时间，每个工作都有相同数目的 100 张彩票，以及相同的运行时间 R。

在这种情况下，我们希望两个工作能够在大约相同的时间完成，但由于彩票调度算法的随机性，有时一个工作会先于另一个完成。为了量化这种区别，我们顶一个了一个简单的不公平指标 U，将两个工作完成时刻相除得到 U 的值。比如运行时间 R 为 10，第一个工作在时刻 10 完成，另一个在 20，U = 10/20 = 0.5。如果两个工作几乎同时完成，U 的值将接近于 1。在这种情况下我们的目标是：完美的公平调度程序可以做到 U=1。

上图展示了两个工作的运行时间从 1 到 1000 变化时，30 次实验的平均 U 值。可以看出，当工作时间执行很短时，平均不公平度非常糟糕。只有当工作执行非常多的时间片时，彩票调度算法才能得到期望的结果。

如何分配彩票

关于彩票调度还有一个问题没有提到，那就是如何为工作分配彩票？这是一个非常棘手的问题，系统的运行严重依赖于彩票的分配。假设用户自己知道如何分配，因此可以给每个用户一定量的彩票，由用户按照需要自主分配自己的工作。然而这种方案似乎什么也没有解决——还是没有给出具体的分配策略。因此对于给定的一组工作，彩票分配的问题依然没有最佳答案。

为什么是不确定的

你可能还想知道，究竟为什么要利用随机性？从上面的内容可以看出，虽然随机方式可以使调度程序的实现变得简单且大致正确，但偶尔并不能产生正确的比例，尤其是在工作时间较短的情况下。由于这个原因，Waldspurger 提出了步长调度，一个确定性的公平分配算法。

步长调度也很简单。系统中的每个工作都有自己的步长，这个值与票数值成反比。在上面的例子中，ABC 这 3 个工作的票数分别是 100、50、250，我们通过用一个大数分别除以他们的票数来获得每个进程的步长。比如用 1000 除以这些票数值，得到了 3 个进程的步长分别为 100、200、40。我们称这个值为每个进程的步长。每次进程运行后，我们会让他的计数器(行程值)增加它的步长，以记录它的总体进展。

之后，调度程序使用进程的步长以及行程值来确定调度哪个进程。基本思路很简单：当需要进行调度时，选择目前拥有最小行程值的进程，并且在运行之后将该进程的行程值增加一个步长。下面是是 Waldspurger 给出的伪代码：

current = remove_min(queue);       // pick client with minimum pass
schedule(current);                 // use resource for quantum
current->pass += current->stride;  // compute next pass using stride
insert(queue, current);			   // put back into the queue

在我们的例子中三个进程的步长分别为 100、200、40，初始行程都是 0。因此，最初所有进程都可能被选择调度。假设选择 A，执行一个时间片后行程值为 100。然后运行 B，行程值为 200。最后运行 C，行程值为 40。这时，算法选择最小的行程值，即 C，执行并增加为 80。然后 C 会再次运行，行程增加为 120。现在需要运行 A，行程值增加到 200。然后 C 再次连续运行两次，行程值为 200。此时，所有行程值再次相等，这个过程会无限重复下去。下图展示了一段时间内的变化过程：

可以看出 C 运行了 5 次、A 为 2 次、B 为 1 次，真好是票数的比例——200、100、50。彩票调度算法只能一段时间后在概率上实现比例，而步长调度算法可以在每个调度周期后做到完全正确。

你可能想知道，既然有了可以精确控制的步长算法，为什么还需要彩票算法呢？好吧，彩票调度有一个步长调度没有的优势——不需要全局状态。假如有个新的进程在上面的步长调度执行过程中假如系统，应该怎样设置它的行程值呢？设置为 0 则会使其独占 CPU。而彩票调度算法不需要对每个进程记录全局状态，只需要用新进程的票数更新全局的总票数即可。因此彩票调度算法能够更加合理的处理新加入的进程。

小结

本章介绍了比例份额调度的概念，并简单讨论了两种实现：彩票调度和步长调度。彩票调度通过随机值，聪明的做到了按比例分配。步长调度算法能够确定的获得需要的比例。虽然两者都很有趣，但由于一些原因，并没有作为 CPU 调度程序被广泛使用。一个原因是这两种方式都不能很好的适合 IO；另一个原因是其中最难的票数分配问题并没有确定的解决方式。比如，如何知道浏览器进程拥有多少票数？通用调度程序(类似 MLFQ)做的更好，因此得到了广泛的应用。

结果，比例份额调度程序只有在这些问题可以相对容易解决的领域才更有用。比如虚拟数据中心，你可能会希望分配 1/4 的 CPU 周期给 Windows 虚拟机，剩余的则分配给 Linux 系统，比例分配的方式则会更加简单高效。

8 - 多处理器调度

过去很多年，多处理器系统只存在于高端服务器中。现在，它们越来越多的出现在个人电脑、笔记本电脑甚至移动设备上。多核处理器将多个 CPU 组装在一块芯片上，是这种扩展的根源。由于计算机的构架师们当时很难让单核 CPU 更快，同时又不增加太多功耗，所以这种多核 CPU 很快就变得流行。

当然，多核 CPU 也带来和很多困难。主要困难是典型的应用程序都只使用一个 CPU，增加更多的 CPU 并没有让这类程序运行的更快。为了解决该问题不得不重新这些程序，使之能够并行执行，或者使用多线程。多线程应用可以将工作分散到多个 CPU 上，因此 CPU 资源越多运行的也就越快。

除了应用程序，操作系统遇到的一个新的问题是多处理器调度。到目前为止，我们讨论了很多单处理器调度的原则，那么如何将这些想法扩展到多处理器上呢？

背景：多处理器架构

为了了解多处理器调度带来的新问题，必须先知道它与单 CPU 之间的基本区别。区别的核心在于对硬件缓存的使用，以及多处理器之间共享数据的方式。

在单 CPU 系统中，存在多级的硬件缓存，一般来说会让处理器更快的执行程序。缓存是很小但很快的存储设备，通常拥有内存中最热数据的备份。相比之下，内存很大且拥有所有的数据，但访问速度较慢。通过将频繁访问的数据放在缓存中，系统似乎拥有又大又快的内存。

举个例子，假设一个程序需要从内存中加载指令并读取一个值，系统只有一个 CPU，拥有较小的缓存和较大的内存。

程序第一次读取数据时，数据在内存中，因此需要花费较长的时间。处理器判断该数据可能被再次使用，因此将其放入 CPU 缓存中。如果之后程序需要再次使用该数据，CPU 会先查找缓存。因为在缓存中找到了数据，所以取数据会快的多，程序则会运行的更快。

缓存是基于局部性的概念，局部性有两种，即时间局部性和空间局部性。时间局部性指当一个数据被访问后，它很有可能在不久的将来被再次访问，比如循环代码中的数据或指令本身。而空间局部性指的是，当程序访问地址为 X 的数据时，很有可能会紧接着访问 X 周围的数据，比如遍历数组或指令的顺序执行。由于这两种局部性存在于大多数程序中，硬件系统可以很好的预测哪些数据可以放入缓存，从而运行的更快。

有趣的是，如果系统有多个处理器，并共享同一个内存，会怎样呢？

事实证明，多 CPU 的情况下缓存要复杂的多。假设运行一个在 CPU1 上的程序从内存地址 A 读取数据。由于不再 CPU1 的缓存中，所以系统会直接访问内存，得到值 D。程序然后修改了 A 处的值，只是将其缓存更新会新的值 D1。将数据写回内存比较慢，因此系统通常稍后再执行写入操作。假设这时系统中断了该程序的运行，并将其交给 CPU2，重新读取地址 A 的数据，由于 CPU2 的缓存中没有该数据，所以会直接从内存读取，得到了旧的值 D，而不是正确的 D1。

这一普遍的问题被称为缓存一致性问题，有大量的研究文献描述了解决该问题的微妙之处。这里我们仅提几个要点。

硬件提供了该问题的基本解决方案：通过监控内存访问，硬件可以保证获得正确的数据，并保证共享内存的唯一性。在基于总线的系统中，一种方式是使用总线窥探。每个缓存都通过监听链接了所有缓存和内存的总线，来发现内存访问操作。如果 CPU 发现对它放在缓存中的数据的更新，会作废本地副本，或将其更新。而回写缓存，则会让事情变得更加复杂。

同步

跨 CPU 访问(尤其是写入)时共享数据或数据结构，需要使用互斥原语才能保证正确性。比如多 CPU 并发访问一个共享队列。如果没有锁，即使有底层一致性协议，并发的从队列增加或删除元素依然不会得到正确的结果。需要使用锁来保证数据结构状态更新的原子性。

为了更具体，我们设想这样的代码序列，用于删除共享链表的一个元素。

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 }

假设两个 CPU 上的不同线程同时进入这个函数。如果线程 1 执行第一行，会将 head 的当前值存入它的 tmp 变量。如果线程 2 接着也执行第一行，他也会将同样的 head 值存入自己的私有 tmp 变量。tmp 变量在栈上分配，两个线程拥有各自的私有存储。因此，两个线程会尝试删除同一个链表头，而不是每个线程各移除一个元素，这导致了各种问题。

当然，让这类函数正确工作的方式是使用锁。这里只需要一个互斥锁，然后在函数开始时调用 lock，在结束时条用 unlock，确保代码的执行符合预期。我们会看到，这里依然会有问题，尤其是性能方面。具体来说，随着 CPU 数量的增加，访问同步共享的数据结构会变得很慢。

缓存亲和度

在设计多处理器调度时遇到的最后一个问题，是所谓的缓存亲和度。这个概念很简单：一个进程在某个 CPU 上运行时，会在该 CPU 的缓存中维护很多状态。下次该进程在相同的 CPU 上运行时，由于缓存中的数据而执行的更快。相反，在不同的 CPU 上执行，会由于需要重新加载数据而变慢。因此多处理器调度应该考虑到这种缓存亲和度，并尽可能将进程保持在相同的 CPU 上执行。

单队列调度

现在我们来讨论如何设计一个多处理器调度程序。最基本的方式是简单的复用单处理器调度的基本结构，将所有需要调度的工作放在一个单独的队列中，我们称之为单队列多处理器调度(SQMS)。该方法最大的优点是简单，不需要做过多的修改，就可以将原有的策略应用于多 CPU，以选择最合适的工作来运行。

然而，SQMS 有几个明显的缺陷。第一个是缺乏扩展性。为了保证在多个 CPU 上正确运行，调度程序的开发者需要在代码中通过加锁来保证原子性。在 SQMS 访问单个队列时，锁能确保得到正确的结果。

然而，锁可能带来巨大的性能损失，尤其是随着系统中的 CPU 数增加时。随着这种单个锁的争用增加，系统花费了越来越多的时间在锁的开销上，较少的时间用于系统应该完成的工作。

SQMS 的第二个主要问题是缓存亲和度。比如，假设我们有 5 个工作 ABCDE 和 4 个 CPU。调度队列如下：

一段时间后，假设每个工作依次执行一个时间片，然后选择另一个工作，下面是每个 CPU 可能的调度队列：

由于每个 CPU 都简单的从全局共享的队列中选取下一个要执行的工作，因此每个工作都不断的在不同 CPU 之间转移，这与缓存亲和度的目标背道而驰。

为了解决该问题，大多数 SQMS 调度程序都引入了一些亲和机制，尽可能让进程在同一个 CPU 上运行。保持一些工作的亲和度的同时，可能需要牺牲其他的亲和度来实现负载均衡。比如，针对同样的 5 个工作的调度如下：

这种情况下，ABCD 都保持在同一个 CPU 上运行，只有工作 E 在不断的来回转移，从而尽可能多的获得缓存亲和度。为了公平起见，之后我们可以选择不同的工作来转移。但实现这种策略可能会很复杂。

我们看到，SQMS 调度方式有优势但也有不足。优势是能够从单 CPU 调度程序很简单的发展而来，根据定义，它只有一个队列。然而，它的扩展性不好(由于同步开销)，并且不能很好的保证缓存亲和度。

多队列调度

正是由于但队列调度的这些问题，有些系统使用了多队列方案，比如每个 CPU 一个队列。我们称之为多队列多处理器调度(MQMS)。

在 MQMS 中，基本调度框架包含多个调度队列，每个队列可以使用不同的调度规则，比如轮转或者其他任何可能的算法。当一个工作进入系统后，系统会依靠一些启发性规则将其放入某个队列来调度。这样一来，每个 CPU 调度之间互相独立，就避免了但队列的方式中由于数据共享及同步带来的问题。

例如，假设系统中有两个 CPU。这时一些工作进入系统。由于每个 CPU 都有自己的调度队列，操作系统需要决定每个工作放入哪个队列。可能像下面这样：

根据不同队列的调度侧列，每个 CPU 从两个工作中选择，决定谁将运行。比如利用轮转，调度结果可能如下所示：

MQMS 比 SQMS 有明显的优势，它天生具有可扩展性。队列的数量会随着 CPU 的增加而增加，因此锁和缓存争用的开销不是大问题。此外，MQMS 天生具有良好的缓存亲和度。所有工作都保持在固定的 CPU 上，因而可以很好的利用缓存数据。

但是，如果稍加注意你可能会发现一个新的问题，即负载不均衡。假定和上面的设定一样，但假设一个工作执行完毕，现在的调度队列如下：

如果对系统中每个队列都执行轮转调度策略，会得到如下调度结果：

从上图可以看出，A 获得了 BD 两倍的 CPU 时间，这不是期望的结果。更糟的是，假设 A 和 C 都执行完毕，系统中只有 B 和 D，调度队列看起来如下：

因此 CPU 使用时间线看起来令人难过：

所以可怜的多队列多处理器调度程序应该怎么办呢？最明显的答案是让工作移动，这种技术我们称之为迁移。通过工作的跨 CPU 迁移，可以实现真正的负载均衡。

来看两个例子就更清楚了。同样，一个 CPU 空闲，另一个 CPU 有一些工作：

在这种情况下，期望的迁移很容易理解：操作系统应该讲 B 或 D 迁移到 CPU0。这次工作迁移使得负载均衡，皆大欢喜。

更棘手的情况是较早的一些例子，A 肚子留在 CPU0 上，BD 在 CPU1 上交替执行。

在这种情况下，单次迁移并不能解决问题。应该怎么做呢？答案是不断的迁移一个或多个工作。一种可能的方案是不断切换工作，如下面的时间线所示。可以看到，开始的时候 A 独享 CPU0，BD 在 CPU1。一些时间片后，B 迁移到 CPU0 与 A 竞争，D 则独享 CPU1 一段时间。这样就实现了负载均衡。

当然，还有其他不同的迁移模式。但现在是最棘手的部分：系统如何决定发起这样的迁移？

一个基本的方法是采用一种技术，名为工作窃取。通过这种方法，工作量少的队列不定期的偷看其他队列是不是比自己的工作多。如果目标队列比源队列中的工作显著较多，就从目标队列窃取一个或多个工作，实现负载均衡。

当然，这种方法也有让人抓狂的地方——如果太频繁的检查其他队列就会带来较高的开销，可扩展性不好，而这时多队列调度最初的全部目标。相反，如果检查间隔较长，又可能会带来严重的负载不均。找到合适的阈值仍然是黑魔法，这在系统策略设计中很常见。

Linux 多处理器调度

有趣的是，在构建多处理器调度程序方面，Linux 社区一直没有达成共识。一直以来，存在 3 种不同的调度程序：O(1)调度程序、完全公平调度程序(CFS)、BF 调度程序(BFS)。从 Meehean 的论文中可以找到对这些不同调度程序优缺点的对比总结。

O(1) CFS 采用多队列，而 BFS 采用单队列，这说明两种方法都可以成功。当然它们之间还有很多不同的细节。比如 O(1) 调度程序是基于优先级的，类似之前讲过的 MLFQ，随时间推移改变进程的优先级，然后调度优先级最高的进程，来实现各种调度目标。交互性得到了特别的关注。与之不同，CFS 是确定的比例调度方法，类似之前介绍的步长调度。BFS 作为 3 个算法中唯一采用单队列的算法，也是基于比例调度，但采用了更复杂的方案，称为最早合适虚拟截止时间优先算法(EEVEF)。

小结

本章介绍了多处理器调度程序的不同实现方法。其中单队列的方式比较容易构建，负载均衡较好，但在扩展性和缓存亲和度方面有着天生的缺陷。多队列的方式有很好的扩展性和缓存亲和度，但实现负载均衡却很困难，也更复杂。无论采用哪种方式，都没有简单的答案：构建一个通用的调度程序仍然是一项令人生畏的任务，因为即使很小的代码改动，也有可能导致巨大的行为差异。

9 - 抽象-地址空间

在早期，构建计算机操作系统非常简单。原因是用户对操作系统的期望不高。然而一些烦人的用户提出要易于使用、高性能、可靠性等，这导致了所有这些令人头疼的问题。

早期系统

从内存来看，早期的机器并没有提供多少抽象给用户。基本上机器的物理内存看起来如下图所示：

操作系统曾经是一组函数(一个库)，在内存中，然后有一个正在运行的程序(进程)，目前在物理内存中，并使用剩余的内存。这里几乎没有任何抽象，用户对操作系统的要求也不多。

多道程序与分时共享

过了一段时间，由于机器昂贵，人们开始更有效的共享机器。因此多道程序系统时代开启，其中多个进程在指定时间准备运行，比如当有一个进程在等待 IO 操作的时候，操作系统会切换这些进程，这样增加了 CPU 的有效利用率。那时候，效率的提高尤其重要，因为每台机器的成本是数十万元甚至数百万元。

但很快，人们开始对机器要求更多，分时系统的时代诞生了。具体来说，很多人意识到批量计算的局限性，尤其是程序员本身，他们厌倦了长时间的编程-调试循环。交互性变得很重要，因为许多用户可能同时在使用机器，每个人都在等待他们执行的任务及时响应。

一种实现分时共享的方法，是让一个进程单独占用全部内存运行一小段时间，然后停止它，并将它所有的状态信息保存在磁盘上(包含所有的物理内存)，记载其他进程的状态信息，再运行一段时间，这就实现了某种比较粗糙的机器共享。

遗憾的是，这种方法有一个大问题：太慢了，特别是当内存增长的时候。虽然保存和恢复集群器级别的状态信息相对较快，但将全部的内存信息保存到磁盘就太慢了。因此，在进程切换的时候，我们仍然将进程信息放在内存中，这样操作系统可以更有效的实现分时系统。

在上图中，有 3 个进程 ABC，每个进程拥有从 512KB 物理内存中切分出来给他们使用的一小部分内存。假定只有一个 CPU，操作系统选择运行其中一个进程，同时其他进程则在队列中等待运行。

随着分时系统变得更加流行，人们对操作系统又有了新要求。特别是多个程序同时驻留在内存中，使保护称为重要问题。人们不希望一个进程可以读写其他进程的内存。

地址空间

然而，我们必须将这些烦人的用户的需求放在心上。因此操作系统需要提供一个易用的物理内存抽象。这个抽象叫做地址空间，是运行的程序能够看到的系统中的内存。理解这个基本的抽象系统内存抽象，是了解内存虚拟化的关键。

一个进程的地址空间包含运行程序的所有内存状态。比如：程序的代码必须在内存中，因此它们也在地址空间中。当程序在运行时，利用栈来保存当前的函数调用信息，分配空间给局部变量，传递参数和函数返回值。最后，堆用户管理动态分配的、用户管理的内存，就像你从 C 语言中调用 malloc 或面向对象语言中调用 new 关键字获得内存。当然，还有其他的东西(如静态初始化的变量)，但现在假设只有这 3 部分：代码、堆、栈。

上图是一个很小的地址空间。程序代码位于地址空间的顶部。代码是静态的，所以可以将其放在地址空间的顶部，我们知道程序在运行时，代码不会再需要额外的空间。

接下来在程序运行时，地址空间有两个区域可能增长，那就是堆和栈。把它们放在底部，是因为它们都希望能够增长。通过将它们放在地址空间的两端，我们可以运行这样的增长：它们只需要在相反的方向上增长。因此堆在代码之下 1KB 开始并向下增长，栈从 16KB 开始并向上增长。然而，堆和栈的这种放置方式只是一种约定，如果你愿意，可以用不同的方式来安排地址空间，当多个线程在地址空间中共存时，就没有像这样分配空间的好办法了。

当然，当我们描述地址空间时，所描述的是操作系统提供给运行程序的抽象。程序不再物理地址 0~16KB 的内存中，而是加载在任意的物理地址。回顾前图中的进程 ABC，你可以看到每个进程如何加载到内存中的不同地址。因此问题来了？

关键问题：如何虚拟化内存 操作系统如何在单一的物理内存上为多个运行的进程构建一个私有的、可能很大的地址空间的抽象？

当操作系统这样做时，我们说操作系统在虚拟化内存，因为运行的程序认为它被加载到特定地址的内存中，并且具有非常大的地址空间。现实很不一样。

比如，当前图中的进程 A 尝试在地址 0 执行加载操作时，然而操作系统在硬件的支持下，处于某种原因，必须确保不是加载到物理地址 0，而是物理地址 320KB，即 A 载入内存的地址。这是内存虚拟化的关键，这是世界上每个现代计算机系统的基础。

提示：隔离原则 隔离是构建可靠系统的关键原则。如果两个实体相互隔离，这意味着一个实体的失败不会影响另一个实体。操作系统力求让进程彼此隔离，从而防止互相造成伤害。通过内存隔离，操作系统进一步确保运行程序不会影响底层操作系统的操作。一些现代操作系统通过将某些部分与操作系统的其他部分分离，实现进一步的隔离。这样的微内核可以比整体内核提供更大的可靠性。

目标

补充：你看到的所有地址都不是真的 编写过打印指针的 C 程序吗？你看到的值是虚拟地址。有没有想过你的程序代码到底在哪里？你也可以将其打印出来，但它也是一个虚拟地址。实际上，作为用户级程序的成员，可以看到的任何地址都是虚拟地址。只有操作系统通过精妙的内存虚拟化技术，知道这些指令和数据所在的物理内存地址。所以永远不要忘记：如果你在程序中打印一个地址，那是一个虚拟地址。虚拟地址只是提供地址如何在内存中分布的假象，只有操作系统才知道物理地址。

在这一章中我们将触及操作系统的工作——虚拟化内存。操作系统不仅虚拟化内存，而且还遵循了一定的风格。为了确保操作系统这样做，我们需要一些目标来指导。

虚拟内存系统的一个主要目标是透明。操作系统实现虚拟内存的方式，应该让运行的程序看不见。因此，程序不应该感知到内存被虚拟化的事实。相反，程序的行为就好像它拥有自己的私有物理地址。在幕后，操作系统和硬件完成了所有的工作，让不同的工作复用内存，从而实现了这种假象。

虚拟内存的另一个目标是效率。操作系统应该追求虚拟化尽可能高效，包括时间上和空间上的高效。在实现高效虚拟化时，操作系统将不得不依赖硬件支持，包括 TLB 这样的硬件功能。

1    #include <stdio.h>
2    #include <stdlib.h>
3    int main(int argc, char *argv[]) {
4        printf("location of code : %p\n", (void *) main);
5        printf("location of heap : %p\n", (void *) malloc(1));
6        int x = 3;
7        printf("location of stack : %p\n", (void *) &x);
8        return x;
9    }

最后，虚拟内存的第三个目标是保护。操作系统应该确保进程受到保护，不会受其他进程影响，操作系统本省也不会受进程影响。当一个进程执行加载、存储或指令提取时，它不应该以任何方式访问或影响任何其他进程或操作系统本身的内存内容。因此，保护让我们能够在进程之间提供隔离性，每个进程都应该在自己的独立环境中运行，避免其他出错或恶意进程的影响。

在接下来的章节中，我们将重点介绍虚拟化内存所需的基本机制，包括硬件和操作系统的支持。我们还将研究一些相关的策略，包括如何管理可用内存，以及值空间不足的情况下该释放那些内存。

小结

我们介绍了操作系统的一个重要子系统：虚拟内存。虚拟内存负责为程序提供一个聚到的、稀疏的、私有的地址空间假象。其中保存了程序的所有指令和数据。操作系统在专门硬件的帮助下，通过每一个虚拟内存的索引，将其转换为物理地址，物理内存根据获得的物理地址来获取所需的信息。操作系统会同时对许多进程执行此操作，并且确保程序之间互相不影响，也不会影响操作系统。真个方法需要大量的机制和策略。

10 - 内存接口

在本章中，我们将介绍 UNIX 操作系统的内存管理接口。操作系统提供的接口非常简洁，因此本章简明扼要。

内存类型

在运行一个 C 程序的时候，会分配两种类型的内存。第一种称为栈内存，它的申请和释放操作是编译器来隐式管理的，所以有时也称为自动内存。

C 申请栈内存很容易。比如，假设需要在 func 函数中为一个整形变量 x 申请空间。为了声明这样一块内存，只需要这样做：

void func() {
	int x; // declares an integer on the stack
	...
}

编译器将完成剩下的工作，确保你进入 func 函数的时候，在栈上开辟空间。当你从该函数退出时，编译器释放内存。因此，如果你希望某些信息存在于函数调用之外，建议不要将其放在栈上。

就是这种对长期内存的需求，所以我们才需要第二种类型的内存，即堆内存。其中所有的申请和释放操作都有程序员显式完成。毫无疑问，这是一项艰巨的任务。这确实导致了很多缺陷。但如果小心并加以注意，就会正确的使用这些接口，没有太多的麻烦。下面的例子展示了如何在堆上分配一个整数，并得到指向它的指针：

void func() {
	int *x = (int *) malloc(sizeof(int));
	...
}

关于这一段代码有两点说明。首先，你可能会注意到栈和堆的分配都发生在同一行：首先编译器看到指针的声明 (int * x)，知道为一个整形指针分配空间，随后，当程序调用 malloc 时，它会在堆上请求整数的空间，函数返回这样一个整数的地址，然后将其存储在栈中一共程序使用。

因为它的显式特性，以及它富于变化的用法，堆内存对用户和系统提出了更大的挑战。所以这也是我们接下来要讨论的重点。

malloc 调用

malloc 函数非常简单：传入要申请的堆空间的大小，它成功就返回一个指向新申请空间的指针，失败就返回 NULL。

man 手册展示了使用 malloc 需要怎么做，在命令行输入 man malloc 即可：

#include <stdlib.h>
...
void *malloc(size_t size);

从这段信息可以看到，只要包含头文件 stdlib.h 就可以使用 malloc 了。但实际上，甚至都不要这样做，因为 C 库是程序默认链接的，其中就有 malloc 的代码，加上头文件只是让编译器检查你是否正确调用了 malloc。

malloc 只需要一个 size_t 类型参数，该参数表示你需要多少个字节。然而，大多数程序员并不会直接传入数字。实际上，这样做会被认为是不好的形式。替代方案是使用各种函数或宏。比如为了给双精度浮点分配空间会这样做：

double *d = (double *) malloc(sizeof(double));

对 malloc 的调用是用 sizeof 操作符来申请正确大小的空间。在 C 中，这通常被认为是编译时操作符，意味着这个大小是在编译时已经知道的，因此被替换为一个数，再作为 malloc 的参数。处于这个原因，sizeof 被正确的认为是一个操作符，而不是一个函数调用，因为函数调用发生在运行时。

你可以可以传入一个变量的名字给 sizeof，但在一些情况下，可能得不到你想要的结果，所以要小心使用。

另一个需要注意的地方是使用字符串。如果为一个字符串分配空间，请使用以下惯用法：malloc(strlen(s) + 1)，它使用函数 strlen 获取字符串的长度并加上 1，以便给字符串结束符留出空间。这里使用 sizeof 可能会导致麻烦。

你也许注意到 malloc 返回一个指向 void 类型的指针。这样做只是 C 中传回地址的形式，让程序员决定如何处理它。程序员进一步使用所谓的强制类型转换，在我们上面的例子中，程序员将返回类型的 malloc 强制转换为指向 double 的指针。强制类型转换实际上没干什么，只是告诉编译器和其他可能正在读你代码的程序员：是的，我知道正在做什么。通过强制转换 malloc 的结果，程序员只是在给人一些信息，并非必须。

free 调用

事实证明，分配内存是等式的简单部分。知道何时、如何以及是否释放内存是困难的部分。要释放不再使用的堆内存，程序员只需调用 free。

int *x = malloc(10 * sizeof(int));
...
free(x);

该函数接收一个参数，即一个由 malloc 返回的指针。因此你会注意到，分配区域的大小不会被传入，必须由内存分配库自己来记录追踪。

常见错误

在使用 malloc 和 free 时会出现一些常见的错误。以下是我们在教授本科操作系统课程时反复看到的情形。所有使用的这些例子都可以通过编译器编译并运行。对于构建一个正确的 C 程序来说，通过编译是必要的，但这还远远不够，你会懂的。

实际上，正确的内存管理就是这样一个问题，许多新语言都支持自动内存管理。在这样的语言中，当你调用类似 malloc 的机制来分配内存时，你永远不需要调用某些东西来释放空间。实际上，来及收集器会运行，找出你不再引用的内存并将其释放。

忘记分配内存

许多例程在调用之前，都希望你为它们分配内存，比如 strcpy(dst,src) 将源字符串中的字符串复制到目标指针。但是，如果不小心，你可能会这样做：

char *src = "hello";
char *dst;			// oops! unallocated
strcoy(dst, src);	// segfault and die

运行这段代码将会导致段错误，这是一个很奇怪的术语，表示你对内存犯了一个错误。

正确的代码应该向下面这样：

char *src = "hello";
char *dst = (char *)malloc(strlen(src)+1);
strcpy(dst, src);
``

或者你可以使用 strdup 来让生活更加轻松。

### 没有分配足够的内存

另一个相关的错误是没有分配足够的内存，有时称为缓冲区溢出。在上面的例子中，一个常见的错误是为目标缓冲区仅仅留出几乎足够的空间：

```c
char *src = "hello";
char *dst = (char *) malloc(strlen(src)); // too small!
strcpy(dst, src); // work properly

奇怪的是，这个程序通常看起来会正确运行，这取决于如何实现 malloc 和许多其他细节。在某些情况下，当字符串拷贝执行时，它会在超过分配空间的末尾处写入一个字节，但在某些情况下，这是无害的，可能会覆盖不再使用的变量。在某些情况下，这些溢出可能具有令人难以置信的危害，实际上是系统中许多安全漏洞的来源。在其他情况下，malloc 库总是分配一些额外空间，因此你的程序实际上不会在其他某个变量的值上涂写，并能工作的很好。还有一些情况，该程序确实会发生故障和崩溃。因此，我们学到了另一个宝贵的教训：即使它正确运行过一次，也不意味着它是正确的。

忘记初始化分配的内存

在这个错误中，你正确的调用 malloc，但忘记在新分配的数据类型中填写数值。不要这样做。如果你忘记了，你成程序最终会遇到未初始化的读取，它从堆中读取了一些未知的数值。谁知道都是些什么数值！如果走运，读到的值使程序仍然有效。如果不走运，将会读到一些有害的数值。

忘记释放内存

另一个常见错误是内存泄露，如果忘记释放内存，就会发生。在长时间运行的程序或系统中，这是一个巨大的问题。因为缓慢泄露的内存会导致内存不足，此时需要重新启动。因此一般来说，当你用完一段内存后应该确保将其释放。请注意，使用垃圾回收语言在这里没有什么帮助：如果你仍然持有对某块内存的引用，那么垃圾收集器就不会将其释放，因此即使在较现代的语言中，内存泄露仍然是一个问题。

在某些情况下，不调用 free 似乎是合理的。比如你的程序运行时间很短，很快就会退出。在这种情况下，当进程死亡时，操作系统将清理其分配的所有内存，因此将不会发生内存泄露。虽然这肯定有效，但这可能是一个坏习惯，所以请谨慎使用这种策略。

在用完之前释放内存

有时候程序会提前释放内存，这种错误被称为悬挂指针，正如你猜测的那样，这也是不对的。随后的使用可能会导致程序错误或覆盖有效的内存。

反复释放内存

程序有时还会不止一次的释放内存，这种操作被称为重复释放。这样做的结果是未定义的。正如你所能想到的那样，内存分配库可能会感到困惑，并且会做出各种奇怪的事情，崩溃是常见的结果。

错误的调用 free

我们讨论的最后一个问题是 free 的错误调用。free 期望你只传入之前从 malloc 得到的指针。如果传入一些其他值，就会发生错误。因此这种无效的释放是危险的。

底层操作系统支持

你可能已经注意到，在讨论 malloc 和 free 时，我们没有提到系统调用。原因很简单：它们不是系统调用，而是库调用。因此 malloc 库管理虚拟地址空间，但是它本身是建立在一些系统调用之上的，这些系统调用会进入操作系统，来请求更多内存或释放内存。

一个这样的系统条用叫做 brk，它被用来改变程序分断的位置：堆结束的位置。它需要一个参数，从而根据新分断是大于还是小于当前分断，来增加或减少堆的大小。另一个调用 sbrk 要求传入一个增量，但目的类似。

请注意，你不应该直接调用 brk 或 sbrk。它们被内存分配库使用。如果你尝试使用它们，很可能会犯一些错误。

最后，你还可以通过 mmap 调用从操作系统获取内存。通过传入正确的参数，mmap 可以在程序中创建一个匿名内存区域——该区域不与任何特定文件关联，而是与交换空间关联，稍后将详细讨论。这种内存也可以像堆一样被管理。

其他调用

内存分配库还支持一些其他调用。比如 calloc 分配内存，并在返回之前将其置零。如果你认为内存已归零并忘记自己初始化它，这可以放置出现一些错误。当你为某些东西分配空间，然后还需要添加一些东西时，例程 realloc 也会很有用。realloc 创建一个新的更大的内存区域，将旧区域复制到其中，并返回新区域的指针。

11 - 地址转换

在实现 CPU 虚拟化时，我们遵循的一般准则被称为受限直接访问(LDE)。LDE 背后的想法很简单：让程序运行的大部分指令直接访问硬件，只在一些关键点由操作系统介入，以确保“在正确的时间地点，做正确的事情”。为了实现高效的虚拟化，操作系统应该尽量让程序自己运行，同时通过在关键点的及时介入，来保持对硬件的控制。高效和控制是现代操作系统的两个主要目标。

在实现虚拟内存时，我们将追求类似的战略，在实现高效和控制的同时，提供期望的虚拟化。高效决定了我们要利用硬件的支持，这在开始的时候非常初级，但会逐渐变得相当复杂。控制意味着操作系统要确保应用程序只能访问它自己的内存空间。因此，要保护应用程序不会互相影响且不影响操作系统本身，我们还是需要硬件的帮助。最后，我们对虚拟内存还有一点要求，即灵活性。具体来说，我们希望程序能够以任何方式访问它自己的地址空间，从而让操作系统更易编程。所以关键问题在于：

关键问题：如何高效、灵活的虚拟化内存

我们利用了一种通用技术，有时被称为硬件的地址转换，简称地址转换。它可以被看做是受限执行这种一般方法的补充。利用地址转换，硬件对每次的内存访问都进行处理，将指令中的虚拟地址转换为实际存储数据的物理地址。因此，在每次内存引用时，硬件都会进行地址转换，将应用程序的内存引用重定位到内存中实际的位置。

当然，仅仅依靠硬件不足以实现虚拟内存，因为它只提供了底层机制来提供效率。操作系统必须在关键的位置介入，设置好硬件，以便完成正确的地址转换。因此它必须管理内存，记录被占用和空闲的内存位置，并明智而谨慎的介入，保持对内存使用的控制。

同样，所有这些工作都是为了创造一种美丽的假象：每个程序都拥有私有的内存，那里存放着它自己的代码和数据。虚拟现实的背后是丑陋的物理现实：许多程序其实是在同一时间共享着内存，就像 CPU 在不同的程序之间切换运行。通过虚拟化，操作系统将丑陋的机器现实转换为一种有用的、强大的、且易于使用的抽象。

假设

我们先假设用户的地址空间必须连续的存放在物理内存中。同时为了简单，我们假设地址空间不是很大，小于物理内存的大小。最后，假设每个地址空间的大小完全一样。

实例

为了更好的理解地址转换的实现，我们先来看一个例子。设想一个进程的地址空间如下图所示。这里我们需要检查一小段代码，它从内存加载一个值，对其加 3，让后再放回内存。

void func() {
	int x;
	x = x + 3;
}

编译器将这段代码转换为类似如下汇编代码：

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 中的值写回到内存的同一位置。

提示：介入很强大 介入是一种很常见又很强大的技术，计算机系统中使用介入常常能带来很好的效果。在虚拟内存中，硬件可以介入到每次内存访问中，将进程提供的虚拟地址转换为数据实际存储的物理地址。但是，一般化的介入技术有更加广阔的应用空间，实际上几乎所有良好定义的接口都应该提供介入机制，以便增加功能或在其他方面提升系统。这种方式最基本的特点是透明，介入完成时通常不需要改动接口的客户端，因此客户端不需要任何改动。

在前面的图中，可以看到代码和数据都位于进程的地址空间，3 条指令序列位于地址 128，变量 x 的值位于地址 15KB。如前图所示，x 的初始值为 3000。

如果这 3 条指令执行，从进程的角度来看，发生了以下几次内存访问：

• 从内存 128 获得指令。
• 执行指令(从地址 15KB 加载数据)。
• 从地址 132 获得命令。
• 执行命令(没有内存访问)。
• 从地址 135 获得指令。
• 执行指令(新值存入地址 15KB)。

从程序的角度来看，它的地址空间从 0 开始到 16KB 结束。它包含的所有内存引用都应该在该范围呢。然而，对虚拟内存来说，操作系统希望将该进程地址空间放在物理内存的其他位置，并不一定从地址 0 开始。因此我们遇到如下问题：怎样在内存中重定位该进程，同时对该进程透明？怎样提供一种虚拟地址空间从 0 开始的假象，而实际上地址空间位于另外某个物理地址？

上图展示了一个例子，说明该进程的地址空间被放入物理内存后可能的样子。从上图可以看到，操作系统将第一块物理内存留给了自己，并将上述例子中的进程地址空间重定位到从 32KB 开始的物理内存地址。剩下的两块内存空闲。

硬件动态重定位

为了更好的理解基于硬件的地址转换，我们先来讨论他的第一次应用。在 20 世纪 50 年代后期，它首次出现在分时系统中，那时只是一个简单的思想，称为地址加界限机制，有时又称为动态重定位，我们将交叉使用这两个术语。

具体来说，每个 CPU 需要两个硬件寄存器：基址寄存器和界限寄存器，或称为限制寄存器。这两个寄存器能够支持我们将地址空间放在屋里内存的任何位置，同时又能确保进程只能访问自己的地址空间。

采用这种方式，在编写和编译程序时假设地址空间从 0 开始。但是，当程序真正执行时，操作系统会决定其在物理内存中的实际加载地址，并将其实地址记录在基址寄存器中。在上面的例子中，操作系统决定加载在物理地址 32KB 的进程，因此将基址寄存器设置为这个值。

当进程运行时，有趣的事情发生了。现在，该进程产生的所有内存引用，都会被处理器通过以下方式转换为物理地址：

physical address = virtual address + base

补充：基于软件的重定位 在早期，在硬件支持重定位之前，一些系统曾经采用基于软件的重定位方式。基本技术被称为静态重定位，其中一个名为加载程序的软件接收将要运行的可执行程序，将它的地址重写到物理内存中期望的便宜位置。 然而，静态重定位存在很多问题，首先也是最重要的是不提供访问保护，进程中的错误地址可能导致对其他进程或操作系统内存的非法访问，一般来说，需要硬件支持来实现真正的访问保护。静态重定位的另一个缺点是一旦完成，稍后很难将内存空间重定位到其他位置。

进程中使用的内存引用都是虚拟地址，硬件接下来将虚拟地址加上基址寄存器中的内容，得到物理地址，再发给内存系统。

为了更好的理解，我们来追踪一条指令执行的过程。

128: movl 0x0(%ebx), %eax

程序计数器首先被设置为 128.当硬件需要获取该指令时，它先将该值加上基址寄存器中的 32KB(32768)，得到实际的物理地址为 32896，然后硬件从该地址获取指令。接下来，处理器开始执行该指令。这时，进程发起从虚拟地址 15KB 的加载，处理器同样将虚拟地址加上基址寄存器的内容(32KB)，得到最终的物理地址为 47KB，从而获得需要的数据。

将虚拟地址转换为物理地址，这正是所谓的地址转换技术。也就是说，硬件取得进程认为要访问的地址，将它转换成数据实际位于的物理地址。由于这种重定位是在运行时发生的，而且我们甚至可以在进程开始运行后改变其地址空间，这种技术一般被称为动态重定位。

提示：基于硬件的动态重定位 在动态定位的过程中，只有很少的硬件参与，但获得了很好的效果。一个基址寄存器将虚拟地址转换为物理地址，一个界限寄存器将确保这个地址在进程地址空间的范围内。它们一起提供了简单高效的虚拟内存机制。

现在你可能会问，界限寄存器去哪了？不是基址加上界限机制吗？正如你猜测的那样，界限寄存器提供了访问保护。在上面的例子中，界限寄存器被设置为 16KB。如果进程需要访问超过了该界限或者为负数的虚拟地址，CPU 将触发异常，进程可能被终止。界限寄存器的用处在于，它确保了进程产生的所有地址都在进程地址的界限内。

这种基址寄存器配合界限寄存器的硬件结构位于芯片内，每个 CPU 一对。有时我们将 CPU 的这个负责地址转换的部分统称为内存管理单元(MMU)。随着我们开发更加复杂的内存管理技术，MMU 也将拥有更为复杂的电路和功能。

关于界限寄存器再补充一点，它通常有两种使用方式。像上面这种方式中，它记录地址空间的大小，硬件在将虚拟地址与基址寄存器内容求和前，就检查这个界限。另一种方式是界限寄存器中记录地址空间结束的物理地址，硬件在转化虚拟地址到物理地址之后采取检查该界限。这两种方式在逻辑上是等价的。简单起见，我们这里假设采用第一种方式。

转换示例

为了更好的理解基址加界限的地址转换机制，我们来看一个例子。设想一个进程拥有 4KB 大小的地址空间，它被加载到从 16KB 开始的物理内存中。一些转换过程如下：

从例子可以看出，通过基址加虚拟地址(可以看做是地址空间的偏移量)的方式，很容易得到物理地址。虚拟地址过大或为负数，均会导致异常。

补充：数据结构——空闲列表 操心系统必须记录哪些空闲内存没有被使用，以便能够为进程分配内存。很多不同的数据结构可以用于这项任务，其中最简单的是空闲列表。它实际上是一个列表，记录了当前没有被使用的物理内存的范围。

硬件支持总结

首先，正如在 CPU 虚拟化中提到的，我们需要两种 CPU 模式。操作系统在特权模式运行，可以访问整个机器资源。应用程序在用户模式，只能执行有限的操作。只要一个位，也许保存在处理器状态字中，就能说明当前 CPU 的运行模式。在一些特殊的时刻，CPU 会切换状态，如系统调用、中断、异常。下图则是动态重定位的硬件要求：

硬件还必须提供基址和界限寄存器，因此每个 CPU 的内存管理单元都需要这两个额外的寄存器。用户程序运行时，硬件会转换每个地址，即将用户程序产生的虚拟地址加上基址寄存器的内容。硬件也必须能够检查地址是否有效，通过界限寄存器和 CPU 内的一些电路来实现。

硬件应该提供一些特殊指令，用于修改基址寄存器和界限寄存器，允许操作系统在切换进程时改变它们。这些指令是特权指令，只有在内核模式下才能修改这些寄存器。

最后，在用户程序尝试非法访问内存时，CPU 必须能够产生异常。在这种情况下，CPU 应该阻止用户程序的执行，并安排操作系统的越界异常处理程序来处理。操作系统的处理程序会做出正确的响应，比如在这种情况下终止进程。类似的，如果用户程序尝试修改基址或者界限寄存器，CPU 也应该产生异常，并调用“用户模式尝试执行特权指令”的异常处理程序。CPU 还必须提供一种方法，来通知它这些处理程序的位置，因此又需要一些特权指令。

操作系统的问题

为了支持动态重定位，硬件添加了新的功能，使得操作系统有了一些必须处理的新问题。硬件支持和操作系统管理结合在了一起，实现了一个简单的虚拟内存。具体来说，在一些关键时刻需要操作系统的接入，以实现基址和界限方式的虚拟内存。如下表。

第一，在进程创建时，操作系统必须采取行动，为进程的地址空间找到内存空间。由于我们假设每个进程的地址空间小于物理内存的大小，并且大小相同，这对操作系统来说很容易实现。它可以把整个物理内存看做一组槽块，并标记为空闲或已用。当新进程创建时，操作系统加锁这个数据结构，为新的地址空间找到位置，并将其标记与已用。如果地址空间可变，那么就会变得复杂，我们将在后续章节中讨论。

我们来看一个例子，在前一节的图中，操作系统将物理内存的第一个槽块分配给自己，然后将例子中的进程重定位到物理内存地址 32KB。另两个槽块空闲，因此空闲列表中就包含了这两个空闲槽块。

第二，在进程终止时，操作系统也必须做一些工作，回收进程的所有内存，以便给其他进程或操作系统使用。在进程终止时，操作系统会将这些内存放回到空闲列表，并根据需要清除相关的数据结构。

第三，在上下文切换时，操作系统也必须执行一些操作。每个 CPU 毕竟只有一个基址寄存器和一个界限寄存器，但对于每个运行的程序，它们的值都不同，因为每个程序被加载到内存中不同的物理地址。因此，在切换进程时，操作系统必须保存和恢复基址和界限寄存器。具体来说，当操作系统决定中止当前进程时，它必须将当前基址寄存器和界限寄存器中的内存保存在内存中，放在每个进程都拥有的结果中，如进程结构或进程控制块中。类似的，当操作系统恢复执行某个进程时，也必须给基址寄存器和界限寄存器恢复正确的值。

需要注意，当进程停止时，操作系统可以改变其地址空间的物理位置，这很容易。要移动进程的地址空间，操作系统首先让进程停止运行，然后将地址空间拷贝到新的位置，最后更新保存的基址寄存器，指向新的位置。当进程恢复执行时，它的新基址寄存器会被恢复，它再次开始运行，显然它的指令和数据都在新的内存位置了。

第四，操作系统必须提供异常处理程序，或需要一些调用的函数。操作系统在启动时加载这些处理程序。比如，当一个进程视图越界访问内存时，CPU 会触发异常。在这种异常产生时，操作系统必须准备采取行动。通常操作系统会做出充满敌意的反应：终止错误进程。操作系统应该尽力保护它运行的机器，因此它不会对那些企图访问非法地址或执行非法指令的进程客气。

下表展按时间线展示了大多数硬件与操作系统的交互。可以看出，操作系统在启动时做了什么，为我们准备好机器，然后在进程开始运行时发生了什么。请注意，地址转换过程完全由硬件处理，没有操作系统的介入。在这个时候，发生时钟中断，操作系统切换到进程 B 运行，它执行了“错误的加载”，这时操作系统必须介入，终止该进程，清理并释放进程 B 占用的内存，将它从进程表中移除。从表中可以看出，我们仍然遵循受限直接访问的基本方法，大多数情况下，操作系统正确设置硬件后，就任凭进程直接运行在 CPU 上，只有进程行为不端时才介入。

小结

本章通过虚拟内存使用的一种特殊机制，即地址转换，扩展了受限直接访问的概念。利用地址转换，操作系统可以控制进程的所有内存访问，确保访问在地址空间的界限内。该技术高效的关键在于硬件支持，硬件快速的将所有内存访问操作中的虚拟地址转换为物理地址。所有的这一切对进程来说是透明的，进程并不知道自己使用的内存引用已经被重定位。

我们还看到了一种特殊的虚拟化方式，称为基址界限的动态重定位。基址界限的虚拟化方式非常高效，因为只需要非常少的硬件逻辑，就可以将虚拟地址和寄存器地址相加，并检查进程产生的地址是否越界。基址界限也提供了保护，操作系统和硬件的协作，确保没有进程能够访问到其他地址空间的内容。保护肯定是操作系统最重要的目标之一。没有保护，操作系统也就无法控制机器。

遗憾的是，这个简单动态重定位技术有效率低下的问题。比如前面的例子中，重定位的进程使用了从 32KB 到 48KB 的物理内存，但由于该进程的栈区和堆区并不是很大，导致这块内存区域中大量的空间被浪费。这种浪费通常称为内部碎片，指的是已经分配的内存单元内部未有使用的空间，造成了浪费。在我们当前的方式中，即使有足够的内存容纳更多进程，但我们目前要求将地址空间放在固定的槽块中，因此会出现内存碎片。所以我们还需要一些复杂的机制，以便更好的利用物理内存，避免内部碎片。第一次尝试是将基址界限的概念稍微泛化，得到分段(segmentation)的概念。

12 - 分段

到目前为止，我们一直假设将所有进程的地址空间完整的加载到内存中。利用基址和界限寄存器，操作系统很容易将不同进程重定位到不同的物理内存区域。但是，对于这些内存区域，你可能会注意到：栈和堆之间，有一大块空闲空间。

从上图可知，如果我们将整个地址空间放入物理内存，那么栈和堆之间的空间并没有被进程使用，却依然占用了实际的物理内存。因此，简单的通过基址寄存器和界限寄存器实现的虚拟内存很浪费。另外，如果剩余物理内存无法提供连续区域来放置完整的内存空间，进程便无法运行。这种基址加界限的方式看起来并不像我们想象的那样灵活。

关键问题：怎样支持大地址空间 怎样支持大的地址空间，同时栈和堆之间又可能存在大量空间空间？在之前的例子中，地址空间非常小，所以这种浪费并不明显。但假设一个 32 位 4GB 的地址空间，通常的程序只会使用几兆的内存，但需要整个地址空间都放在内存中。

分段：泛化的基址/界限

为了解决该问题，分段概念应运而生。分段并非一个新概念，它甚至可以追溯到 20 时机 60 年代初期。这个想法很简单，在 MMU 中引入不止一个基址和界限寄存器对，而是为地址空间内的每个逻辑段配置一对。一个段只是地址空间中一个连续定长的区域，在典型的地址空间中有 3 个逻辑不同的段：代码、栈、堆。分段的机制使得操作系统能够将不同的段放到不同的物理内存区域，从而避免了虚拟地址空间中未使用部分仍然占用内存。

我们来看一个例子，假设我们系统将上图中的地址空间放入物理内存。通过给每个段一对基址和界限寄存器，可以将每个段独立放入物理空间。如下图所示，64KB 的物理内存中放置了 3 个段，为操作系统保留 16KB。

从上图可以看到，只有已使用的内存才在物理内存中分配空间，因此可以容纳巨大的地址空间，其中包含大量未使用的地址空间，有时又称为稀疏地址空间。

你会想到，需要 MMU 中的硬件结构来支持分段：在这种情况下，需要一组 3 对基址和界限寄存器。下表展示了上面例子中的寄存器值，每个界限寄存器都记录了一个段的大小。

我们来看一个地址转换的例子。假设现在要引用虚拟地址 100，MMU 将基址值加上偏移量 100 得到实际的物理地址：100+32KB=32868。然后它会检查该地址是否在界限内，验证通过，于是发起对物理内存地址 32868 的引用。

补充：段错误 段错误指的是在支持分段的机器上发生了非法内存访问。有趣的是，即使在不支持分段的机器上这个术语依然保留。

来看一个堆中的地址，虚拟地址 4200。如果用虚拟地址 4200 加上堆的基址 32KB，得到 39016，这是不正确的。我们首先应该减去堆的偏移量，即该地址指的是这个段中的哪个字节。因为堆从虚拟地址 4KB 开始，4200 的偏移量实际上是 4200 减去 4096，即 104，然后用这个偏移量加上基址寄存器中的物理地址 3KB，得到真正的物理地址 34920。

如果试图访问非法的地址，如 7KB，你可以想象发生的情况：硬件会发现该地址越界，因此陷入操作系统，和可能导致终止出错进程。这就是段异常或段错误。

我们引用哪个段

硬件在地址转换时使用寄存器，它如何知道段内的偏移量呢，以及地址引用了哪个段？

一种常见的方式是，有时称为显式方式，就是用虚拟地址的开头几位来标识不同的段，VAX/VMS 系统使用了这种技术。在我们之前的例子中有 3 个段，因此需要两位来标识。如果我们用 14 位虚拟地址的前两位来标识，那么虚拟地址如下所示：

那么在我们的例子中，如果前两位是 00，硬件就知道这是属于代码段的地址，因此使用代码段的基址和界限来定位到正确的物理地址。如果前两位是 01，则是堆地址，对应的使用堆的基址和界限。下面来看一个 4200 之上的虚拟地址进行转换。虚拟地址 4200 的二进制形式如下：

从图中可以看到，前两位 01 告诉硬件我们引用的是哪个段。剩下的 12 位是段内偏移量。因此，硬件就使用前两位来决定使用哪个段寄存器，然后用后 12 位作为段内偏移。偏移量与基址相加，硬件就得到了物理地址。请注意，偏移量也简化了对段边界的判断。我们只要检查偏移量是否小于界限，大于界限的则为非法地址。因此，如果基址和界限放在数组中，为了获得需要的物理地址，硬件或做以下操作：

1    // get top 2 bits of 14-bit VA
2    Segment = (VirtualAddress & SEG_MASK) >> SEG_SHIFT
3    // now get offset
4    Offset = VirtualAddress & OFFSET_MASK
5    if (Offset >= Bounds[Segment])
6        RaiseException(PROTECTION_FAULT)
7    else
8        PhysAddr = Base[Segment] + Offset
9    Register = AccessMempory(PhysAddr)

在我们的例子中，可以为上面的常量填上值。具体来说，SEG_MASK 为 0x3000，SEG_SHIFT 为 12，OFFSET_MASK 为 0xFFF。

你或许已经注意到，上面使用两位来区分段，但实际只有 3 个段，因此有一段的地址空间被浪费。因此有些系统中会将堆和栈作为一个段，因此只需要一位来做标识。

硬件还提供了其他方法来决定特定地址在哪个段。在隐式方式中，硬件通过地址产生的方式来确定段。比如，如果地址由程序计数器产生，那么地址在代码段。如果基于栈或基址指针，他一定在栈段。其他地址则在堆段。

栈怎么办

到目前为止，我们一直没有将地址空间中的一个重要部分：栈。在前面的例子中，栈被定位到物理地址 28KB。但有一点关键区别，它反向增长。在物理内存中，它始于 28KB，增长回到 26KB，响应虚拟地址从 16KB 到 14KB。地址转换必须有所不同。

首先，我们需要一点硬件支持。除了基址和界限外，硬件还需要知道段的增长方向(使用 1 位来区分)。在下表中，我们更新了硬件的视图。

硬件理解段可以反向增长后，这种虚拟地址的地址转化必须有所不同。下面来看一个例子。

在该例子中，假设要访问虚拟地址 15KB，它映射到物理地址为 27KB。该虚拟地址的二进制形式为 11 1100 0000 0000(十六进制 0x3C00)。硬件利用前两位 11 来指定段，但然后我们要处理偏移量 3KB。为了得到正确的反向偏移，我们必须从 3KB 中减去最大的段地址：在这个例子中，段可以是 4KB，因此正确的偏移量是 3KB 减去 4KB，即 -1KB。只要用这个偏移量加上基址 28KB，就能得到正确的物理地址 27KB。用户可以进行越界检查，确保反向偏移量的绝对值小于段的大小。

支持共享

随着分段机制的不断改进，系统设计人员很快意识到，通过再多一点的硬件支持，就能实现新的效率提升。具体来说，要节省内存，有时候在地址空间之间共享某些内存段是有用的。尤其是，代码共享很常见，今天的系统仍然在用。

为了支持共享，需要一些额外的支持，这就是保护位。基本为每个段增加了一个位，标识程序是否能够读写该段，或执行其中的代码。通过将代码段标记为只读，同样的代码可以被多个进程共享，而不用担心破坏隔离。虽然每个进程都认为自己独占这块内存，但操作系统秘密的共享了内存，进程不能修改这些内存，所以假象得以保持。

下表展示了一个例子，是硬件记录的额外信息。可以看到，代码段的权限是可读和可执行，因此物理内存中的一个段可以映射到多个虚拟地址空间。

有了保护位，前面描述的硬件算法也必须改变。除了检查地址是否越界，还需要检查特定访问是否允许。如果用户试图写入只读段，或从非执行段执行指令，硬件会触发异常，并让操作系统来处理出错进程。

分段粒度

到目前为止，我们的例子大多针对只有很少几个段的系统(代码、堆、栈)。我们可以认为这种分段是粗粒度的，因为它将地址空间分为较大的、粗粒度的块。但是，一些早期的系统更灵活，允许将地址空间划分为大量较小的段，被称为细粒度分段。

支持大量分段需要硬件的支持，并在内存中保存某种段表。这种分段表通常支持创建非常多的段，因此系统使用段的方式比之前讨论的方式更加灵活。比如，像 Burroughs B5000 这样的早期机器可以支持成千上万的段，有了操作系统和硬件的支持，编译器可以将代码段和数据段划分为许多不同的部分。当时的考虑是，通过耕细粒度的分段，操作系统可以更好的了解哪些段在使用、哪些段未被使用，从更加高效的利用内存。

操作系统支持

现在你应该了解了基本的分段原理。系统运行时，地址空间中的不同段被重定位到物理内存中。与我们之前介绍的整个地址空间只有一个基址/界限寄存器对的方式相比，节省了大量物理内存。具体来说，栈和堆之间没有使用的区域就不再需要分配物理内存，让我们可以将更多的地址空间放入物理内存。

然而，分段带来了一些新的问题。我们先介绍必须关注的操作系统相关的问题。第一个是老问题：操作系统在上下文切换时应该怎么做？你可能已经猜到了：各个段寄存器中的内存必须被保存和恢复。显然，每个进程都有自己独立的虚拟地址空间，操作系统必须在进程运行之前，确保这些寄存器被正确的赋值。

第二个问题更重要，即管理物理内存的空闲空间。新的地址空间被创建时，操作系统需要在物理内存中为它的段找到空间。之前，我们假设所有的地址空间大小相同，物理内存可以被认为是一些槽块，进程可以放进去。现在，每个进程都有一些段，每个段的大小也可能不同。

一般会遇到的问题是，物理内存很快充满了很多小的空闲空间，因而很难分配给新的段，或扩大已有的段。这种问题被称为外部碎片，如下图所示。

在这个例子中，一个进程需要分配一个 20KB 的段。当前只有 24KB 空闲，但并不连续。因此，操作系统无法满足这个 20KB 的请求。

该问题的一种解决方案是紧凑物理内存，重新安排原有的段。比如，操作系统先中止运行的进程，将它们的数据复制到连续的内存区域中去，改变它们的段寄存器中的值，指向新的物理地址，从而得到足够大的连续空闲空间。这样做，操作系统能让新的内存分配请求成功。但是，内存紧凑的成本很高，因为拷贝是内存密集型的，一般会占用大量的处理器时间。如下图所示。

一种跟简单的方案是利用空闲列表管理算法，试图保留大的内存块用于分配。相关的算法可能有成千上百种，包括传统的最优匹配、最坏匹配、首次匹配、伙伴算法等。Wilson 等人做过一个很好的调查。

小结

分段解决了一些问题，帮助我们实现了高效的虚拟内存。不只是动态重定位，通过避免地址空间的逻辑段之间潜在的大量内存浪费，分段能够更好的支持稀疏地址空间。它还很快，因为分段需要的算法很简单，很适合由硬件完成，地址转换的开销极小。分段还有一个附加好处是代码共享。如果代码放在独立的段中，这样段就可以被多个运行的程序共享。

但我们已经知道，在内存中分配不同大小的段会导致一些问题，我们希望客服。首先，是我们上面讨论的外部碎片。由于段的大小不同，空闲内存被割裂成各种奇怪的大小，因此满足内存分配请求可能会很难。用户可以尝试采用聪明的算法，或定义紧凑内存，但问题很根本，难以避免。

第二个问题也许更重要，分段还是不足以支持更一般化的稀疏地址空间。比如，如果有一个很大但是稀疏的堆，都在一个逻辑段中，整个堆仍然必须完整的加载到内存中。换言之，如果使用地址空间的方式不能很好的匹配底层分段的设计目标，分段就不能很好的工作。因此我们需要找到新的解决方案。