Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

操作系统导论

如果你正在学习一门本科层次的操作系统课程，那么你应该已经大致了解一个计算机程序在运行时究竟在做什么。

如果还不了解，那么这本书（以及对应的课程）对你来说会比较困难——所以你最好先停下来，不要继续往下读；或者赶紧跑去最近的书店，迅速补完继续阅读所必需的背景知识（Patt 与 Patel 的 [PP03] 以及 Bryant 与 O’Hallaron 的 [BOH10] 都是相当不错的书）。

那么，一个程序运行时到底会发生什么呢？

其实，一个正在运行的程序只会做一件非常简单的事情：执行指令。处理器每秒会执行数百万次（如今甚至是数十亿次）如下过程：从内存中取出一条指令，译码它（也就是弄清楚这是一条什么指令），然后执行它（也就是完成它该做的事，例如把两个数相加、访问内存、检查某个条件、跳转到某个函数等等）。做完这一条指令之后，处理器再继续执行下一条指令，如此反复，直到程序最终执行结束。1

因此，我们刚刚描述的其实就是 冯·诺依曼（Von Neumann）计算模型 的基本内容。2 听起来很简单，对吧？但在这门课中，我们会学习到：当一个程序运行时，系统中其实还在发生许多“狂野”的事情，而它们的主要目标，是让整个系统更容易使用。

事实上，确实存在这样一套软件，它负责让程序运行变得简单（甚至让你看起来像是可以同时运行很多程序），让多个程序共享内存，使程序能够与设备交互，以及完成其他诸如此类的有趣工作。这套软件就叫做 操作系统（Operating System, OS）。3 它负责确保整个系统以一种既正确、又高效、还易于使用的方式运转。

操作系统完成这一目标的主要方法，是一种我们称为 虚拟化（virtualization） 的通用技术。也就是说，操作系统会接管某种物理资源（例如处理器、内存或磁盘），并把它转换成一种更通用、更强大、也更易使用的虚拟形式。因此，我们有时也把操作系统称为 虚拟机（virtual machine）。

当然，为了让用户能够告诉操作系统该做什么，从而真正使用这些“虚拟机”提供的功能（例如运行一个程序、分配一块内存、访问一个文件），操作系统还会提供一组你可以调用的接口（API）。事实上，一个典型的操作系统通常会向应用程序导出数百个 系统调用（system call）。由于操作系统通过这些调用来支持程序运行、内存访问、设备操作以及其他相关行为，我们有时也会说，操作系统为应用程序提供了一个 标准库（standard library）。

最后，正因为虚拟化使得许多程序能够同时运行（因此共享 CPU），许多程序能够并发地访问各自的指令和数据（因此共享内存），以及许多程序能够访问设备（因此共享磁盘等资源），所以操作系统有时也被称为 资源管理者（resource manager）。CPU、内存和磁盘，都是系统中的资源；因此，操作系统的职责之一，就是以高效、公平，或者围绕其他可能目标的方式来管理这些资源。为了更好地理解操作系统的角色，我们来看一些例子。

问题的关键：如何虚拟化资源

本书要回答的一个核心问题其实非常简单：操作系统是如何虚拟化资源的？ 这正是我们要解决问题的关键所在。

至于操作系统为什么要这样做，倒不是最主要的问题，因为答案其实很明显：为了让系统更易于使用。

因此，我们更关注的是“如何做到”：操作系统究竟实现了哪些机制（mechanisms）和策略（policies）来完成虚拟化？它是如何高效地做到这一点的？又需要哪些硬件支持？

在本书中，我们会像这样用带阴影效果的“问题的关键”小节，来点出在构建操作系统时我们试图解决的具体问题。因此，在某个主题的讲解中，你可能会看到一个或多个 crux（没错，这确实是它的正确复数形式：cruces），用来突出该主题真正要解决的问题。而章节中的具体内容，则会给出解决方案，或者至少说明解决方案的基本要点。

2.1 虚拟化 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);
        printf("%s\n", str);
    }
    return 0;
}

图 2.1：一个简单示例：循环打印的代码（cpu.c）

假设我们把这个文件保存为 cpu.c，然后在一台只有一个处理器（或者说一个 CPU）的系统上编译并运行它。下面就是我们会看到的结果：

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

这次运行并不算特别有意思——系统开始执行这个程序，程序不断检查时间，直到一秒过去。一秒之后，代码打印出用户传入的输入字符串（在这个例子里，是字母 A），然后继续重复。注意，这个程序会一直运行下去；只有按下 Control-C（在基于 UNIX 的系统中，这会终止当前前台运行的程序），我们才能把它停下来。

现在，让我们做同样的事情，但这一次，我们同时运行这个程序的多个不同实例。图 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
...

图 2.2：同时运行多个程序

好了，现在事情开始变得有趣一点了。尽管我们只有一个处理器，但这四个程序看起来却像是在同时运行！这种“魔法”到底是怎么发生的呢？4

答案是：这种假象是由操作系统在硬件的帮助下制造出来的。换句话说，操作系统制造出了一种错觉：仿佛系统拥有很多很多个 虚拟 CPU（virtual CPU）。把一个 CPU（或者少量几个 CPU）转换成看起来几乎无限多个 CPU，从而让多个程序看起来能够同时运行，这就是我们所说的 CPU 虚拟化（virtualizing the CPU）；而它正是本书第一大部分的核心主题。

当然，要运行程序、停止程序，或者以其他方式告诉操作系统应该运行哪些程序，就必须存在某些接口（API），供你把自己的意图传达给操作系统。我们会在本书中不断讨论这些 API；实际上，它们正是大多数用户与操作系统交互的主要方式。

你可能还会注意到，同时运行多个程序这件事，会引出许多新的问题。例如：如果两个程序都想在某个特定时刻运行，那么究竟应该让谁先运行？这个问题要由操作系统中的某种 策略（policy） 来回答；而策略在操作系统中的许多不同地方都会被用来回答类似问题。因此，在学习操作系统实现的基本 机制（mechanisms）（例如同时运行多个程序的能力）的同时，我们也会学习这些策略。这也正体现了操作系统作为 资源管理者 的角色。

2.2 虚拟化内存

现在我们来看看内存（memory）。现代机器所呈现的物理内存模型其实非常简单：内存就是一个字节数组（array of bytes）。要读取内存，你必须指定一个地址，以便访问存放在那里的数据；要写入（或者更新）内存，同样也必须指定要写入的地址以及要写入的数据。

当一个程序运行时，它会不断访问内存。程序会把自己的各种数据结构存放在内存中，并通过各种指令来访问它们，例如加载（load）、存储（store）以及其他在执行过程中需要访问内存的显式指令。别忘了，程序中的每一条指令本身也同样存放在内存里；因此，每次取指令时，其实也都在访问内存。

让我们看一个程序（图 2.3），它通过调用 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) address pointed to by p: %p\n",
           getpid(), p); // a2
    *p = 0; // a3
    while (1) {
        Spin(1);
        *p = *p + 1;
        printf("(%d) p: %d\n", getpid(), *p); // a4
    }
    return 0;
}

图 2.3：一个访问内存的程序（mem.c）

prompt> ./mem
(2134) address pointed to by p: 0x200000
(2134) p: 1
(2134) p: 2
(2134) p: 3
(2134) p: 4
(2134) p: 5
^C

这个程序做了几件事。首先，它分配了一块内存（代码中的 a1）。然后，它打印出这块内存的地址（a2），接着把数字 0 写入这块新分配内存的第一个位置（a3）。最后，它不断循环：每次先等待一秒，然后把 p 所指向地址中的值加一。每次打印时，它还会输出当前运行程序的 进程标识符（PID）。每个正在运行的进程都有唯一的 PID。

同样，这第一次运行的结果也不算特别有趣。新分配的内存位于地址 0x200000。随着程序运行，它会缓慢地更新这个值，并打印出结果。

现在，我们再次运行这个程序的多个实例，看看会发生什么（图 2.4）。

prompt> ./mem &; ./mem &
[1] 24113
[2] 24114
(24113) address pointed to by p: 0x200000
(24114) address pointed to by p: 0x200000
(24113) p: 1
(24114) p: 1
(24114) p: 2
(24113) p: 2
(24113) p: 3
(24114) p: 3
(24113) p: 4
(24114) p: 4
...

图 2.4：多次运行内存程序

从这个例子中我们可以看到：每个正在运行的程序都在同一个地址（0x200000）处分配了内存，但它们看起来却都能独立地更新 0x200000 处的值！这就好像每个运行中的程序都拥有自己的私有内存，而不是和其他程序共享同一块物理内存一样。5

事实上，这里发生的事情正是操作系统在虚拟化内存。每个进程都会访问它自己的私有 虚拟地址空间（virtual address space）（通常简称为 地址空间），而操作系统会以某种方式把这个地址空间映射到机器的物理内存上。某个运行中的程序所做的内存访问，不会影响其他进程（甚至也不会影响操作系统自身）的地址空间；就这个运行中的程序看来，它似乎独占了整个物理内存。

但真实情况是：物理内存其实是一种共享资源，而它由操作系统统一管理。至于这一切究竟是如何实现的，同样也是本书第一部分——虚拟化——所要讲述的内容。

2.3 并发

本书的另一个核心主题是并发（concurrency）。我们用这个概念性术语来统称这样一类问题：当你需要在同一个程序中同时处理很多事情（也就是并发地处理）时，就会出现这些问题，而且必须认真面对它们。

并发问题最早首先出现在操作系统自身之中。正如你在前面关于虚拟化的例子中看到的那样，操作系统总是在同时处理许多事情：先运行一个进程，再运行另一个，依此类推。而事实证明，这样做会引出一些既深刻又有趣的问题。

不幸的是，并发问题早已不再只局限于操作系统内部。事实上，现代的**多线程程序（multi-threaded programs）**也会表现出同样的问题。下面我们就通过一个多线程程序的例子来说明（见图 2.5）。

虽然你现在可能还不能完全看懂这个例子（我们会在后面关于并发的章节中详细学习它），但它的基本思想其实很简单。主程序通过 Pthread_create() 创建了两个线程。6 你可以把线程（thread）理解为：一个运行在与其他函数同一内存空间中的函数，而且其中可以有不止一个函数在同一时刻处于活动状态。

在这个例子里，每个线程都会从一个名为 worker() 的例程开始执行；而在这个函数中，它所做的事情非常简单：在一个循环里，把共享变量 counter 增加 loops 次。

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

volatile int counter = 0;
int loops;

void *worker(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        counter++;
    }
    return NULL;
}

int
main(int argc, char *argv[])
{
    if (argc != 2) {
        fprintf(stderr, "usage: threads <value>\n");
        exit(1);
    }
    loops = atoi(argv[1]);
    pthread_t p1, p2;
    printf("Initial value: %d\n", counter);

    Pthread_create(&p1, NULL, worker, NULL);
    Pthread_create(&p2, NULL, worker, NULL);
    Pthread_join(p1, NULL);
    Pthread_join(p2, NULL);
    printf("Final value : %d\n", counter);
    return 0;
}

图 2.5：一个多线程程序（threads.c）

下面是我们运行这个程序，并把变量 loops 的输入值设为 1000 时的结果。loops 的值决定了两个工作线程各自在循环中对共享计数器执行多少次加一操作。那么，当程序用 1000 作为 loops 的值运行时，你觉得 counter 的最终值会是多少呢？

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

正如你大概已经猜到的那样，当两个线程都结束之后，计数器的最终值是 2000，因为每个线程都把它加了 1000 次。实际上，当输入值 loops 被设为 N 时，我们自然会期望程序最终输出 2N。

但事情并没有这么简单。让我们把 loops 设成更大的值，再运行同一个程序，看看会发生什么：

prompt> ./thread 100000
Initial value : 0
Final value : 143012
prompt> ./thread 100000
Initial value : 0
Final value : 137298
// 咦？？
// 这又是什么情况？？

在这次运行中，当我们把输入值设为 100000 时，本来应该得到最终值 200000，结果第一次运行却得到了 143012。然后，第二次运行时，我们不仅再次得到了错误的结果，而且这个错误值还和上一次不一样。事实上，如果你用较大的 loops 值反复运行这个程序，你甚至可能会发现：有时候它又会给出正确答案！ 那么，这到底是为什么呢？

归根结底，这种奇怪而反常的结果，与指令是一条一条执行的这一事实有关。不幸的是，上面那个程序里“把共享计数器加一”这一关键操作，实际上需要三条指令才能完成：第一条把计数器的值从内存加载到寄存器中；第二条对它加一；第三条再把结果写回内存。

由于这三条指令并不是**原子地（atomically）**执行的（也就是说，它们不是“一次性不可分割地完成”的），因此就会发生一些奇怪的事情。而这类并发问题，正是本书第二大部分要详细讨论的内容。

问题的关键：如何构建正确的并发程序

当同一个内存空间中有多个线程并发执行时，我们该如何构建一个行为正确的程序？

操作系统需要提供哪些原语（primitives）？硬件又应当提供哪些机制？我们又该如何利用这些原语和机制来解决并发问题？

2.4 持久性

本课程的第三大主题是持久性（persistence）。在系统内存中，数据很容易丢失，因为像 DRAM 这样的设备是以**易失（volatile）**的方式保存数据的；一旦断电，或者系统崩溃，内存中的任何数据都会消失。

因此，我们需要硬件和软件协同工作，来持久地存储数据；这种持久存储对任何系统来说都至关重要，因为用户通常都非常在意自己的数据。

硬件这一侧体现为各种输入/输出设备（input/output devices, I/O devices）；在现代系统中，硬盘（hard drive） 是最常见的长期信息存储介质，不过 固态硬盘（SSD, solid-state drive） 也正在迅速占据这一领域。

而操作系统中通常负责管理磁盘的软件部分，叫做文件系统（file system）；因此，它要负责以可靠且高效的方式，把用户创建的各种文件存储到系统的磁盘上。

与操作系统为 CPU 和内存提供的抽象不同，操作系统并不会为每个应用程序都创建一个私有的、虚拟化的磁盘。相反，它默认用户经常会希望共享文件中的信息。例如，在编写一个 C 程序时，你可能会先用编辑器（比如 Emacs7）创建并编辑一个 C 源文件（例如 emacs -nw main.c）。完成之后，你可能会使用编译器把源代码编译成一个可执行文件（例如 gcc -o main main.c）。等编译完成后，你又会运行这个新的可执行文件（例如 ./main）。

因此，你可以看到文件是如何在不同进程之间被共享的：首先，Emacs 创建了一个文件，它成为编译器的输入；然后，编译器利用这个输入文件，经过许多步骤（想知道细节的话，请去上一门编译原理课），生成一个新的可执行文件；最后，这个可执行文件又被运行起来。于是，一个新的程序就这样诞生了！

为了更好地理解这一点，我们来看一些代码。图 2.6 展示了一个程序，它创建了一个文件（/tmp/file），并在其中写入字符串 "hello world"。

#include <stdio.h>
#include <unistd.h>
#include <assert.h>
#include <fcntl.h>
#include <sys/types.h>

int
main(int argc, char *argv[])
{
    int fd = open("/tmp/file", O_WRONLY | O_CREAT | O_TRUNC, S_IRWXU);
    assert(fd > -1);
    int rc = write(fd, "hello world\n", 13);
    assert(rc == 13);
    close(fd);
    return 0;
}

图 2.6：一个进行 I/O 的程序（io.c）

为了完成这个任务，这个程序向操作系统发出了三次调用。第一次是 open()，用于打开文件并创建它；第二次是 write()，用于向文件写入一些数据；第三次是 close()，简单地关闭文件，从而表明程序不会再继续往里面写数据了。

这些系统调用会被转发到操作系统中称为文件系统的那一部分，由它来处理这些请求，并向用户返回某种错误码。

你可能会好奇：操作系统到底做了什么，才能真正把数据写到磁盘上？我们本来可以演示给你看，不过你得先答应我们把眼睛闭上；因为那个过程可真不怎么赏心悦目。文件系统其实要做相当多的工作：首先，它必须确定这些新数据到底该放在磁盘的什么位置；然后，它还要在自己维护的各种数据结构里追踪这些数据的位置与状态。

要做到这一点，就需要向底层存储设备发出 I/O 请求，要么读取已有的数据结构，要么更新（写入）它们。任何写过**设备驱动程序（device driver）**的人都知道，想让一个设备替你做点事，是一个非常繁琐而细致的过程。8 它要求你对底层设备接口以及其精确定义的语义有非常深入的理解。

幸运的是，操作系统通过系统调用，为访问设备提供了一种标准且简单的方式。因此，操作系统有时也会被看作是一套标准库。

当然，设备究竟是如何被访问的，文件系统又是如何在这些设备之上持久地管理数据的，其中还有很多很多细节。出于性能考虑，大多数文件系统并不会立刻把每次写入都同步落盘，而是会先把写操作延迟一段时间，希望把它们合并成更大的批次一起处理。

为了应对写入过程中系统崩溃的问题，大多数文件系统还会采用某种复杂的写入协议，例如**日志（journaling）**或 写时复制（copy-on-write）；它们会精心安排写入磁盘的顺序，以确保如果在写入过程中发生故障，系统之后仍然能够恢复到一个合理的状态。

为了让各种常见操作都尽可能高效，文件系统还会使用多种不同的数据结构与访问方式，从简单的链表到复杂的 B 树（B-tree） 都会用到。

如果你现在还觉得这些内容有些摸不着头脑，那很好！因为我们会在本书第三大部分——持久性——中更深入地讨论所有这些内容；在那里，我们会先讨论设备与 I/O 的一般概念，然后再详细讨论磁盘、RAID 和文件系统。

问题的关键：如何持久地存储数据

文件系统是操作系统中负责管理持久数据的部分。

为了正确地完成这项任务，需要哪些技术？为了获得高性能，又需要哪些机制与策略？在面对硬件和软件故障时，系统又是如何实现可靠性的？

2.5 设计目标

现在，你对操作系统实际在做什么，已经有了一些概念：它接管诸如 CPU、内存和磁盘这样的物理资源，并将它们虚拟化；它处理与并发相关的复杂而棘手的问题；它还以持久的方式保存文件，从而在长期内保证数据安全。

既然我们想要构建这样一个系统，那么在设计和实现它时，就需要先明确一些目标，以便帮助我们聚焦重点，并在必要时做出合理的权衡；而找到合适的权衡点，正是构建系统的关键之一。

最基本的目标之一，就是构建出某种抽象（abstraction），从而让系统更方便、更易于使用。抽象是计算机科学中几乎一切工作的基础。正是因为有了抽象，我们才能把一个大型程序拆分成一些更小、更容易理解的部分；才能用像 C 这样的高级语言9 编写程序，而不必时时刻刻想着汇编；才能编写汇编代码，而不必去思考逻辑门；也才能用逻辑门构建处理器，而不必过多关心晶体管的细节。

抽象的重要性如此根本，以至于我们有时会忘记它的重要性；但在这本书里，我们不会忽略它。因此，在每一个部分中，我们都会讨论一些随着时间逐渐发展起来的重要抽象，帮助你理解操作系统中的不同组成部分。

设计和实现操作系统的另一个目标，是提供高性能（high performance）；换句话说，就是尽量降低操作系统本身的开销（overhead）。虚拟化和易用性当然很有价值，但也不能不计代价地追求；因此，我们必须努力在不过度增加开销的前提下，提供虚拟化及其他操作系统功能。

这些开销可能以多种形式出现：额外的时间开销（更多的指令执行）以及额外的空间开销（更多的内存占用或磁盘占用）。如果可能的话，我们会寻找能够尽量减少其中一种、或者同时减少两种开销的方案。当然，完美并不总是可以达到的——这一点也是我们在后续内容中会不断看到并且在适当时候学会接受的。

另一个目标，是在应用程序之间、以及操作系统与应用程序之间提供保护（protection）。既然我们希望允许许多程序同时运行，那就必须确保其中某个程序无论是恶意地还是无意中出现了错误行为，都不会伤害到其他程序；我们当然更不希望一个应用程序能够破坏操作系统本身（因为那样会影响系统中所有正在运行的程序）。

保护是操作系统最核心原则之一——隔离（isolation）——的核心所在。把各个进程彼此隔离开，是实现保护的关键，因此它也构成了操作系统许多工作的基础。

操作系统还必须持续不断地运行；一旦它失败，系统上运行的所有应用程序也会随之失败。正因为整个系统都依赖于它，操作系统通常都要努力提供很高程度的可靠性（reliability）。随着操作系统越来越复杂（有时甚至包含数百万行代码），构建一个可靠的操作系统已经成为一项相当困难的挑战——事实上，这个领域中大量仍在持续进行的研究（包括我们自己的一些工作 [BS+09, SS+10]）正是围绕这一问题展开的。

除此之外，还有一些目标也同样重要：在这个越来越强调环保的世界里，能效（energy-efficiency） 很重要；在这个高度网络化的时代，防范恶意应用程序的安全性（security）（本质上其实是保护的延伸）至关重要；随着操作系统运行在越来越小的设备上，移动性（mobility） 也变得越来越重要。

根据系统的具体用途不同，操作系统会有不同的目标，因此实现方式也很可能至少会略有不同。不过，正如我们将会看到的，关于如何构建操作系统的许多基本原则，在各种不同类型的设备上都是适用的。

2.6 一些历史

在结束本章导论之前，让我们先简要回顾一下操作系统是如何发展起来的。和任何由人类构建的系统一样，操作系统中的好想法也是随着时间逐步积累起来的；工程师们在不断实践中逐渐认识到，哪些设计要点是真正重要的。这里，我们会讨论其中一些主要的发展脉络。如果你想看更完整的历史介绍，可以阅读 Brinch Hansen 那本非常出色的操作系统史著作 [BH00]。

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

一开始，操作系统其实并没有做太多事情。基本上，它只是一些常用函数的集合；例如，不必让系统中的每个程序员都自己编写底层 I/O 处理代码，“操作系统”会统一提供这样的 API，从而让开发者的工作变得更轻松。

通常，在这些早期大型机系统上，一次只会运行一个程序，而这一切是由人工操作员控制的。今天你觉得现代操作系统理应完成的许多工作（例如决定作业的运行顺序），当时其实都是由操作员完成的。如果你是个聪明的开发者，你就会对这位操作员态度好一点，这样他也许就会把你的作业挪到队列前面去。

这种计算模式被称为 批处理（batch processing），因为操作员会把一批作业组织起来，然后成“批”地运行。那时的计算机并不是以交互方式使用的，原因很简单：成本太高。如果让一个用户坐在计算机前面亲自使用它，那么大多数时间机器其实都在空等，而这会让机房每小时白白烧掉数十万美元 [BH00]。

超越函数库：保护机制

当操作系统不再只是一个提供常用服务的简单函数库之后，它开始在机器管理中扮演更核心的角色。其中一个重要变化是：人们逐渐意识到，代表操作系统运行的代码是特殊的；它掌控着设备，因此必须与普通应用程序代码区别对待。

为什么呢？不妨想象一下：如果你允许任何应用程序随意读取磁盘上的任意位置，那么“隐私”这件事就根本无从谈起了，因为任何程序都可以读取任何文件。因此，把文件系统实现成一个库（让谁都能直接调用）其实是没有意义的。于是，人们需要别的办法。

正是在这种背景下，系统调用（system call） 的思想被发明了，而 Atlas 计算系统正是这一思想的先驱 [K+61, L78]。这里的思路不再是把操作系统例程做成一个普通函数库（也就是像普通过程调用那样访问），而是通过增加一对特殊的硬件指令以及相应的硬件状态，使得进入操作系统的过程变成一个更正式、受控的过程。

系统调用与普通过程调用的关键区别在于：系统调用会在把控制权转移给操作系统的同时，提高硬件的特权级别（privilege level）。用户应用程序运行在所谓的 用户态（user mode） 中，这意味着硬件会限制应用程序能做的事情；例如，一个运行在用户态的应用程序通常不能主动向磁盘发起 I/O 请求、不能访问任意物理内存页，也不能直接往网络上发送数据包。

当发起系统调用时（通常是通过一条称为 trap 的特殊硬件指令），硬件会把控制权转移到一个预先指定好的 陷阱处理程序（trap handler）——这是操作系统事先设置好的——并同时把特权级提升到 内核态（kernel mode）。在内核态下，操作系统拥有对系统硬件的完整访问权，因此可以执行诸如发起 I/O 请求、为程序分配更多内存之类的操作。

当操作系统完成对请求的处理后，它会通过一条特殊的 return-from-trap 指令把控制权交还给用户程序；这条指令会把处理器恢复到用户态，并同时把控制流返回到应用程序原先中断的位置。

多道程序时代

操作系统真正开始腾飞，是在大型机之后的另一个计算时代：小型机（minicomputer） 时代。Digital Equipment 的 PDP 系列等经典机器让计算机变得便宜得多；因此，不再是一个大型组织只有一台大型机，而是组织内部一个较小的群体也有可能拥有属于自己的计算机。

毫不意外，成本下降带来的一个重要影响，就是开发活动的增加：更多聪明的人接触到了计算机，于是他们也让计算机系统做出了更多有趣而漂亮的事情。

特别地，多道程序设计（multiprogramming） 变得越来越普遍，因为人们希望更充分地利用机器资源。操作系统不再一次只运行一个作业，而是会把多个作业同时装入内存，并在它们之间快速切换，从而提高 CPU 的利用率。

这种切换尤其重要，因为 I/O 设备很慢；如果一个程序正在等待 I/O 完成，而 CPU 还傻等着它，那就是对 CPU 时间的浪费。既然如此，为什么不切换到另一个作业，让它先运行一会儿呢？

为了支持多道程序，以及在 I/O 和中断存在时实现重叠执行，操作系统在概念上沿着多个方向都发生了创新。比如，内存保护（memory protection） 变得非常重要；我们当然不希望一个程序能够访问另一个程序的内存。再比如，如何处理多道程序带来的并发问题，也变得至关重要；在存在中断的情况下，还要确保操作系统本身行为正确，这更是一项巨大挑战。后面的章节中，我们会专门讨论这些问题以及相关主题。

这一时期一个非常重要的实际进展，是 UNIX 操作系统 的诞生。这主要归功于 Bell Labs（没错，就是那家电话公司）的 Ken Thompson（以及 Dennis Ritchie）。UNIX 从不同操作系统中吸收了许多优秀思想（尤其是 Multics [O72]，以及 TENEX [B+72]、Berkeley Time-Sharing System [S+68] 等系统的一些想法），但它把这些思想做得更简单、更易于使用。

很快，这个团队开始向全世界寄送包含 UNIX 源代码的磁带，而拿到代码的人中，许多人又继续参与改进这个系统。关于这一点，参见下面的旁注10。

旁注：UNIX 的重要性

无论怎样强调 UNIX 在操作系统历史上的重要性，都不算夸张。它受到更早系统的影响（尤其是 MIT 那个著名的 Multics 系统），将许多伟大的想法融汇到一起，并构建出了一个既简单又强大的系统。

最初 Bell Labs 的 UNIX 背后，有一个统一的原则：构建小而强大的程序，并让它们能够彼此连接，从而形成更大的工作流。你输入命令的那个 shell，提供了诸如管道（pipe） 这样的原语，使这种“元层级编程（meta-level programming）”成为可能；于是，把多个程序串起来完成一个更大的任务就变得非常容易。

例如，如果你想找出一个文本文件中所有包含单词 foo 的行，然后再统计这样的行一共有多少，你只需要输入：

grep foo file.txt | wc -l

这样你就利用 grep 和 wc（word count）这两个程序完成了任务。

UNIX 环境对程序员和开发者都非常友好，它还为全新的 C 编程语言提供了编译器。让程序员能够轻松地编写自己的程序，并且把它们分享出去，使得 UNIX 变得极其流行。而且，作者愿意把它的副本免费发给任何提出请求的人，这大概也帮了很大忙——这几乎可以看作是一种早期的开源软件形式。

另一个极其重要的因素，是代码本身可获取、可阅读。一个优美而小巧、并且用 C 写成的内核，天然就会吸引其他人去“玩”它，给它增加新的酷炫特性。例如，Berkeley 那群进取心十足的人，在 Bill Joy 的带领下，做出了一个非常出色的发行版（Berkeley Systems Distribution，简称 BSD），其中包括先进的虚拟内存、文件系统和网络子系统。后来，Joy 还共同创办了 Sun Microsystems。

不幸的是，UNIX 的传播后来受到了一些阻碍，因为一些公司开始试图对它主张所有权并从中获利——这是律师介入后常见但令人遗憾的后果。很多公司都推出了自己的 UNIX 变种：Sun Microsystems 的 SunOS、IBM 的 AIX、HP 的 HPUX（也被戏称为“H-Pucks”），以及 SGI 的 IRIX。AT&T / Bell Labs 与这些参与者之间的法律纠纷给 UNIX 笼罩上了一层阴影，许多人开始怀疑它能否继续存活，尤其是在 Windows 出现并占领了大量 PC 市场之后……

现代时代

在小型机之后，出现了另一类新的机器：更便宜、更快、面向大众——也就是我们今天所说的个人计算机（personal computer，PC）。从 Apple 的早期机器（例如 Apple II）到 IBM PC，这一类新机器很快就成为计算领域的主导力量，因为它足够便宜，使得“每张桌子一台机器”成为可能，而不再是“每个工作组共享一台小型机”。

不幸的是，对操作系统而言，PC 的早期阶段某种程度上反而是一大倒退，因为早期这些系统忘记了（或者从来就不知道）小型机时代积累下来的许多经验教训。

例如，像 DOS（Microsoft 的 Disk Operating System）这样的早期操作系统，并不觉得内存保护有多重要；因此，一个恶意的（或者只是写得很糟糕的）应用程序就可以随意覆盖整个内存。早期几代 Mac OS（9 及以前版本）则采用了一种协作式（cooperative） 的作业调度方式；因此，如果某个线程不小心陷入了无限循环，它就可能霸占整个系统，迫使用户只能重启。这个时代的系统缺失了大量关键操作系统特性，真要一一列举，篇幅会长得离谱。

幸运的是，在经历了若干年的“折磨”之后，小型机操作系统中的许多经典特性终于开始回到桌面系统中。例如，Mac OS X / macOS 的核心就是 UNIX，因此它自然具备成熟系统应有的那些特性。Windows 也同样吸收了计算历史中的许多优秀思想，尤其是从 Windows NT 开始，这可以说是 Microsoft 操作系统技术的一次巨大飞跃。

甚至今天的手机所运行的操作系统（例如 Linux），在很多方面都更像 20 世纪 70 年代小型机上运行的系统，而不像 20 世纪 80 年代 PC 上的那些系统（谢天谢地）；看到操作系统发展黄金时代形成的那些优秀思想最终进入现代世界，实在是一件令人欣慰的事。更好的是，这些思想至今仍在不断演进，带来更多功能，也让现代系统对用户和应用程序变得更加友好。

旁注：后来，Linux 出现了

对 UNIX 来说，幸运的是，一位年轻的芬兰黑客 Linus Torvalds 决定自己写一个 UNIX 版本。这个系统大量借鉴了原始 UNIX 背后的原则与思想，但并没有直接使用原有代码，因此也避开了法律上的麻烦。他召集了世界各地许多人的帮助，又利用了当时已经存在的成熟 GNU 工具 [G85]，于是 Linux 诞生了（同时也推动了现代开源软件运动的发展）。

进入互联网时代之后，大多数公司（例如 Google、Amazon、Facebook 等）都选择运行 Linux，因为它免费，而且可以方便地根据自己的需要进行修改；事实上，如果没有这样一个系统，很难想象这些新公司会取得今天这样的成功。

当智能手机成为面向用户的主流平台时，Linux 也凭借 Android 在这一领域站稳了脚跟，原因与之前大体相同。与此同时，Steve Jobs 把基于 UNIX 的 NeXTStep 操作环境带回了 Apple，于是 UNIX 也由此在桌面领域重新流行起来（尽管许多 Apple 用户恐怕根本没有意识到这一点）。

因此，UNIX 直到今天依然活着，而且比以往任何时候都更重要。如果你相信“计算之神”的存在，那么他们确实值得为这一美妙结果被感谢一番。

2.7 小结

至此，我们已经对操作系统有了一个初步介绍。今天的操作系统让计算机系统相对容易使用，而你如今所接触到的几乎所有操作系统，都在不同程度上受到了本书将要讨论的那些发展成果的影响。

不过很遗憾，由于篇幅和时间所限，本书不会覆盖操作系统的所有内容。例如，操作系统中包含大量网络相关代码；这一部分我们留给你去上网络课程时进一步学习。同样，图形设备也非常重要；如果你想在这个方向上拓展知识，可以去上图形学课程。最后，还有一些操作系统教材会花大量篇幅讨论安全（security）；我们当然也会涉及这一主题，但主要限于操作系统必须在运行中的程序之间提供保护，以及赋予用户保护自己文件的能力，而不会深入讨论那些通常应当放到专门安全课程中研究的更深层安全问题。

不过，本书仍然会覆盖许多重要主题，包括 CPU 和内存虚拟化的基础、并发问题，以及通过设备和文件系统实现持久性等内容。

别担心！虽然前面还有很多内容要学，但其中大部分其实都相当有意思；而当你走完整条路时，你会对计算机系统究竟是如何工作的，产生一种全新的认识。

现在，开始干活吧！

参考文献

[BS+09] L. Bairavasundaram、S. Sundararaman、A. Arpaci-Dusseau、R. Arpaci-Dusseau 著，“Tolerating File-System Mistakes with EnvyFS”。USENIX ’09，San Diego, CA，2009 年 6 月。本文很有意思，讨论了如何同时使用多个文件系统，以便在其中任意一个出错时仍能容错。

[BH00] P. Brinch Hansen 著，“The Evolution of Operating Systems”。收录于《Classic Operating Systems: From Batch Processing to Distributed Systems》。Springer-Verlag，New York，2000 年。这篇文章为一套关于历史上重要操作系统的精彩论文集提供了一个很好的引言。

[B+72] D. Bobrow、J. Burchfiel、D. Murphy、R. Tomlinson 著，“TENEX, A Paged Time Sharing System for the PDP-10”。发表于 CACM，第 15 卷第 3 期，1972 年 3 月。TENEX 已经具备了现代操作系统中的许多机制；读一读它，你会发现早在 20 世纪 70 年代初，很多创新就已经出现了。

[B75] F. Brooks 著，《The Mythical Man-Month》。Addison-Wesley，1975 年。软件工程领域的经典著作，非常值得一读。

[BOH10] R. Bryant、D. O’Hallaron 著，《Computer Systems: A Programmer’s Perspective》。Addison-Wesley，2010 年。又一本非常出色的计算机系统导论书籍。它与本书有少量内容重叠——所以如果你愿意，可以跳过那本书最后几章；当然，也可以把它们读完，从另一个角度看看相同主题。毕竟，建立自己知识体系的一种好办法，就是尽可能多地听取不同视角，然后形成你自己的理解和判断。没错，就是要靠思考！

[G85] R. Stallman 著，“The GNU Manifesto”。1985 年。www.gnu.org/gnu/manifesto.html。Linux 之所以能取得巨大成功，一个重要原因无疑是 GNU 计划提供了优秀的编译器 gcc 以及其他相关开源软件。Stallman 在开源理念上极具远见，而这份宣言清晰阐述了他对这一问题的看法。

[K+61] T. Kilburn、D. B. G. Edwards、M. J. Lanigan、F. H. Sumner 著，“One-Level Storage System”。发表于 IRE Transactions on Electronic Computers，1962 年 4 月。Atlas 系统开创了许多你今天在现代系统中仍然能看到的思想。不过，这篇论文本身并不是特别好读。如果你只打算读一篇相关材料，或许可以读下面那篇更偏历史视角的文章 [L78]。

[L78] S. H. Lavington 著，“The Manchester Mark I and Atlas: A Historical Perspective”。发表于 Communications of the ACM，第 21 卷第 1 期，1978 年 1 月。这是一篇关于早期计算机系统发展以及 Atlas 开创性工作的优秀历史文章。当然，你也可以回头去直接读 Atlas 的原始论文；不过这篇文章提供了一个很好的整体概览，并增添了不少历史视角。

[O72] Elliott Organick 著，《The Multics System: An Examination of its Structure》。MIT Press，1972 年。这是一本关于 Multics 的优秀综述。它里面有太多好点子了；但同时，它也是一个设计过度、目标过多、最终并没有真正成功的系统。它是 Fred Brooks 所说“第二个系统效应（second-system effect）”[B75] 的经典例子。

[PP03] Yale N. Patt、Sanjay J. Patel 著，《Introduction to Computing Systems: From Bits and Gates to C and Beyond》。McGraw-Hill，2003 年。这是我们最喜欢的计算机系统导论教材之一。从晶体管一路讲到 C；尤其是前半部分内容，非常精彩。

[RT74] Dennis M. Ritchie、Ken Thompson 著，“The UNIX Time-Sharing System”。发表于 CACM，第 17 卷第 7 期，1974 年 7 月。这是由 UNIX 的创造者亲自写下的一篇极佳综述，记录了 UNIX 在计算世界迅速传播时的面貌。

[S68] Scientific Data Systems 著，“SDS 940 Time-Sharing System”。TECHNICAL MANUAL，SDS 90 11168，1968 年 8 月。没错，我们能找到的最好资料竟然是一份技术手册。但阅读这些老系统文档本身就很有趣，你会发现早在 20 世纪 60 年代末，许多关键思想就已经出现了。Berkeley Time-Sharing System（后来发展为 SDS 系统）背后的重要人物之一是 Butler Lampson；后来，他凭借在系统领域的贡献获得了图灵奖。

[SS+10] S. Sundararaman、S. Subramanian、A. Rajimwale、A. Arpaci-Dusseau、R. Arpaci-Dusseau、M. Swift 著，“Membrane: Operating System Support for Restartable File Systems”。FAST ’10，San Jose, CA，2010 年 2 月。自己写课程讲义的一大好处，就是可以顺便宣传一下自己的研究成果。不过这篇论文本身确实也很有意思——当文件系统因为 bug 崩溃时，Membrane 可以“自动施法”般地把它重启起来，而且不会影响应用程序或系统的其他部分。

作业

本书的大多数章节（并且最终会是所有章节）都会在结尾附带作业部分。完成这些作业非常重要，因为每一道作业都能帮助你——也就是读者——更深入地理解本章介绍的概念。

作业主要有两种类型。第一类是基于**模拟（simulation）**的。所谓计算机系统模拟器，本质上就是一个简单程序：它“假装”去执行真实系统中一些有趣的部分，然后输出某些度量结果，以展示系统的行为方式。比如，一个硬盘模拟器可能会接收一系列请求，模拟这些请求在具有某些性能特征的硬盘上需要多久才能完成服务，然后报告这些请求的平均延迟。

模拟的妙处在于：它能让你比较容易地探索系统行为，而不必真的去运行一个真实系统。事实上，它甚至允许你构造现实世界里根本不存在的系统（例如，一个性能快得不可思议的硬盘），从而观察未来技术可能带来的影响。

当然，模拟也并非没有缺点。就其本质而言，模拟只是对真实系统行为的近似。如果真实世界中某个重要特性被忽略了，那么模拟器得出的结果就可能是错误的。因此，对于模拟结果，你始终都应当保持一定的怀疑态度。归根结底，真正重要的，还是系统在现实世界中的实际表现。

第二类作业则要求你与真实代码打交道。其中有些作业偏重于测量（measurement），有些则要求进行小规模的开发与实验。这两种作业其实都只是你即将进入的更大世界的一点点尝试——也就是在基于 UNIX 的系统上，使用 C 编写系统代码的世界。

事实上，要真正朝这个方向迈进，仅靠这些作业还不够，你还需要做更大规模的项目。因此，除了完成作业之外，我们强烈建议你去做一些项目，以切实巩固你的系统能力。你可以查看这个页面获取一些项目：

https://github.com/remzi-arpacidusseau/ostep-projects

要完成这些作业，你很可能需要一台基于 UNIX 的机器，也就是说，它应该运行 Linux、macOS 或类似系统。机器上还应安装有 C 编译器（例如 gcc）以及 Python。除此之外，你还应当知道如何使用某种真正的代码编辑器来编辑代码。

  1. 当然，现代处理器在底层会做许多古怪甚至有点“吓人”的事情，以便让程序运行得更快，比如同时执行多条指令，甚至让指令乱序发射和完成！不过，这些并不是我们这里关注的重点；我们这里只关心大多数程序所假定的那个简单模型：指令看起来是一条接一条、井然有序、顺序执行的。 ↩

  2. 冯·诺依曼是计算机系统早期的先驱之一。他还在博弈论和原子弹方面做出了开创性工作，并且曾在 NBA 打了六年球。好吧，这几件事里有一件不是真的。 ↩

  3. 操作系统早期还有别的名字，比如 supervisor，甚至叫 master control program。显然，后者听起来有点太过“掌控一切”了（具体可以参考电影《Tron》），所以值得庆幸的是，最后流行起来的是“operating system（操作系统）”这个名字。 ↩

  4. 注意，我们是通过 & 符号来同时运行四个进程的。这样做会在 tcsh shell 中把一个任务放到**后台（background）**运行，这意味着用户可以立刻继续输入下一条命令；在这里，下一条命令恰好又是另一个要运行的程序。命令之间的分号（;）则使我们能够在 tcsh 中一次启动多个程序。如果你使用的是其他 shell（例如 bash），具体行为会稍有不同；详细信息请查阅相应文档。 ↩

  5. 要让前面的那个例子正常工作，你需要确保**地址空间随机化（address-space randomization）**是关闭的。事实证明，随机化可以作为防御某些安全漏洞的一种有效手段。你可以自行进一步了解这一点；尤其是如果你想知道人们是如何通过“栈溢出攻击（stack-smashing attacks）”入侵计算机系统的。当然，我们并不是在鼓励你这么做…… ↩

  6. 严格来说，真实调用应该是小写的 pthread_create()；这里的大写版本是我们自己封装的一个包装函数，它会调用 pthread_create()，并确保返回值表明调用确实成功了。具体细节请查看相关代码。 ↩

  7. 你应该使用 Emacs。如果你在用 vi，那你大概哪里有点不对劲。如果你用的甚至都不算真正的代码编辑器，那情况就更糟了。 ↩

  8. 设备驱动程序（device driver） 是操作系统中的一段代码，它知道如何和某个特定设备打交道。稍后我们还会进一步讨论设备与设备驱动程序。 ↩

  9. 你们当中有些人可能会反对把 C 称为“高级语言”。不过请记住，这是一门操作系统课程；在这里，我们只要不用整天写汇编，就已经很开心了！ ↩

  10. 我们会用像这样的旁注以及其他类似的文本框，来特别提醒你注意一些不太适合放在正文主线中的内容。有时候，我们甚至只是为了讲个笑话才会加它们——毕竟，学习路上为什么不能稍微有点乐子呢？没错，很多笑话确实挺冷的。 ↩