Revision | 操作系统（上）

Posted on 2026-04-19 Edited on 2026-06-15 Word count in article: 22k Reading time ≈ 1:21

Abstract. 没学明白，写的东西望之不似人言。

历史和动机
操作系统基本概念
操作系统中的抽象
操作系统中的同步
调度
- 经典策略
- Case Study
内存
I/O
文件系统

历史和动机

历史上的操作系统有四条主要的演化谱系：

Multics - AT&T Unix - BSD Unix - Ultrix, SunOS, NetBSD, …
Mach (micro-kernel) + Unix BSD - NextStep - XNU - Apple OS X, iOS
MINIX - Linux - Android OS, Chrome OS, RedHat, Ubuntu, Fedora, Debian, Suse, …
CP/M - QDOS - MS-DOS - Windows 3.1 - NT - 95 - 98 - 2000 - XP - Vista - 7 - 8 - 9 - 10 - …

操作系统基本概念

操作系统乃是一个特殊层次的软件（Special layer of software），向应用软件提供硬件资源访问（access to hardware resources）。这层软件需要实现以下功能：

复杂硬件设备的易用抽象；
受保护的共享资源访问；
安全性（security）和认证能力（authentication）；
逻辑实体之间的通信机制。

实践中的操作系统，提供的抽象包括文件系统，进程 / 线程，虚拟内存 / 容器，命名系统等；管理的资源包括内存，CPU 和存储等。以上功能的实现涉及到调度、并发控制、事务、安全等概念。总而言之，操作系统将硬件细节抽象给应用，应用程序面向操作系统提供的这个抽象编程，而不是直接面向底层硬件行为。形象地，操作系统扮演以下三个角色：

Illusionist. 提供物理资源的干净、易用的抽象。

进程是一个程序运行的环境，其中仅有 OS 提供的有限的权限。一个进程包含以下要素：地址空间、一个或多个跑在这个地址空间中的线程、以及一些附加的系统状态如打开的文件和套接字等。

“机器的虚拟化”：每个应用程序看到的机器其实是 OS 给它提供的进程抽象，在它自己的进程中运行，面对的接口比裸硬件更加简明。
Referee. 管理保护、隔离和资源共享；

进程的概念要求即便所有的进程本质上都运行在同一套物理硬件之上，进程之间也必须隔离，操作系统也必须和用户进程之间隔离。这就要求操作系统有一定的保护机制。

也是为了在一套物理硬件之上运行多个进程，操作系统必须要合理分配计算资源。实践中操作系统会进行进程切换（Switching Process），来并发地运行所有的进程。
Glue. 提供存储、窗口系统、网络、共享、授权等公共服务。

存储、网络、显示之类的我们熟悉的计算机功能都是通过 OS 提供的 I/O 机制实现的。

一个 OS 的根本任务是把程序跑起来。本质上这涉及到以下任务：

把可执行文件的指令和数据段装到内存中；
创建堆栈；
把控制权交给程序；
给程序提供系统服务；
同时保护 OS 和程序。

此处就涉及到 OS 完成这个流程使用的四个基本概念：

线程. 单一、独立的执行上下文。一个线程包括如下要素：
- 程序计数器：记录这个线程正在运行的指令的地址；
- 寄存器和标志（Flags）：这些寄存器记录了这个线程运行的上下文，如栈指针和数据等。我们称一个线程正在处理器上运行，当这些数据出现在该处理器的寄存器中。注意，寄存器只保存了当前线程的根状态，其余的状态在内存中，可以顺着寄存器记录的信息找到。
- 栈空间。
地址空间（和翻译）. 包含可用的（逻辑）地址，以及这些地址的状态。
- 一个 $i$ 位的处理器有 $2^i$ 个地址。
- 当你向一个地址进行读写时，可能会发生以下事件之一：无事发生 / 正常读写 / 读写被忽略 / 出发 IO / 出发异常。
- 方便起见，地址空间被分成若干个段，包括 Code Segment，Static Data，Heap，Stack 等。我们熟知栈空间向下生张，堆空间向上生长。
进程. 带有有限权限的运行环境。
- 进程由地址空间以及一个或多个线程组成。一个线程拥有自己的地址空间、文件描述符、文件系统上下文等资源；
- 提出进程是为了隔离不同的程序，包括用户程序内部与用户程序和操作系统。
- 保护和效率之间有一个显然的 trade-off：跨进程通信的成本很高。
- 每个应用程序的运行实例可能有多个进程。
双模式 / 保护.
- 硬件需要提供两种模式：内核模式和用户模式。实现上具体包括一个模式位、一些内核态才能使用的特权操作、受控的用户态 / 内核态切换（系统调用、中断、异常）。
- 为了实现进程的保护，核心的机制是地址翻译。最简单的地址翻译方法就是 Base & Bound（指定这个进程的地址空间在大地址空间中的起始位置和大小限制）。这有两种实现方式，就是在线翻译和装载期重定位，这两个东西是在干什么可以顾名思义。

操作系统中的抽象

线程和进程

操作系统有时候必须一次性处理多个事务（Multiple Things at Once，MTAO）。比如以下场景：

网络服务器. 多个连接必须被同时处理；
并行计算. 同时计算以追求更高性能；
带有 UI 的程序. 必须一边计算，一边响应用户；
带有网络和磁盘访存的程序. 以隐藏网络和磁盘访问的巨大延迟。

线程就是用来完成 MTAO 的工具，它是 OS 提供的并发的基本单元（a unit of concurrency）。每个线程表示一个事务。

这里所说的“并发”（Concurrency）意思是多个任务在时间上重叠推进，而“并行”（Parallelism）则是两个任务真的被同时执行。比如说，单核 CPU 上的两个线程可以被并发地执行，但是不是并行。物理上，还需要区分以下几个概念：

Multiprocessing. 有多个 CPU 核心；
Multiprogramming. 多个任务 / 进程共享 CPU；
Multithreading. 一个进程内部有多个线程。

用多线程来屏蔽 I/O 延迟的基本方法如下：一个线程有三种状态：RUNNING（正在运行）、READY（可以被运行，但是没在运行）；BLOCKED（不能被运行）。如果一个线程正在等 I/O，它会被标记成 BLOCKED；当 I/O 结束，他会被标记成 READY 然后等待调度。

当编译了一个程序并且运行它时，将会创建一个运行这个程序的进程。最开始，这个进程里面只有一个主线程。进程运行时，可以发起系统调用来创建新线程。新的线程和主线程共用一个地址空间。

在 C 语言中，有以下几个关键的 API：

int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine)(void*), void *arg);
- thread 指向一个将要记录线程 ID 的变量；
- attr 一些特殊设置，一般置为 NULL 以使用默认设置；
- 后两个参数用来指定线程执行的函数和传入的参数。
- 返回值和常见的系统调用一样（$0$ if success，errno on error）；
void pthread_exit(void *value_ptr)；
- 终止线程，如果有返回值，将通过 value_ptr 这个指针传给那个 join 它的线程。
int pthread_join(pthread_t thread, void **value_ptr);
- 挂起调用它的线程，直到编号为 thread 的线程终止。
- 如果 value_ptr 不是非空，目标线程pthread_exit 的那个参数就会出现在 value_ptr 指向的位置。

在调用 pthread_create 之时，机器层面会发生以下事件：

向正常函数一样压栈和跳转；
库代码将系统调用编号存到 %eax，将参数放到 %ebx 等寄存器；
调用 trap 指令，陷入内核。
内核取参数，完成线程创建；
内核把返回值放在 %eax，然后回到用户态；
库函数从寄存器里面拿到内核的返回值，然后像正常函数一样返回。

一般的多线程程序都采取 Fork-Join 的模式，即主线程创建多个工作线程，然后 Join 这些线程，收集结果。

Remark. 做题的时候需要注意以下要点：

数线程不要漏了主线程；
Join 的顺序取决于主线程怎么写；
线程退出的顺序时不确定的；
如果没有同步好，程序的输出也是不确定的。具体的分析在 ICS 里面见过了太多，这里不赘述。

一个线程的状态（形象地理解就是这个图灵机的 State 和纸带的总和）由以下东西共同构成：

进程内所有线程共享. 代码段，全局数据，堆；I/O 资源如文件描述符和网络连接；
每个线程私有. CPU 寄存器、运行时栈（你创建线程的时候要指定一个函数，众所周知调用函数的时候要往栈里面压参数、临时变量、返回地址之类的东西，这就是逻辑上这个线程的栈的开始位置）。这些私有状态保存在 TCB（Thread Conctrol Block）之中。

虽然逻辑上每个线程都有自己的 CPU，但物理上实际上是所有的线程在 CPU 上交替的执行。实际上，并发的线程之间不确定性主要来源于：

调度器可以以任意顺序运行线程；
调度器可以随时切换线程。

在这种不确定性之下，合作线程（有共享状态的线程，相较于独立线程即没有任何共享状态的线程）的设计就需要仔细地约束。此处涉及到几个关键的概念：

互斥. 一种同步的方式。确保某件事情同一时间只能由一个线程来做。
Critical Section. 互斥的结果：某一段代码只能由一个线程运行。
锁. 一个对象，同一时间只有一个线程持有，用来制造互斥。

称一个操作是原子的，若操作系统保证运行这个操作的时候不会进行调度。一个锁提供两种操作：

Lock.aquire() 等锁被释放，然后持有这个锁；
Lock.release() 释放持有的锁。

在 C 语言中的 API 如下：

int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *attr) 初始化锁；
int pthread_mutex_lock(pthread_mutex_t *mutex); 即 Aquire 操作；
int pthread_mutex_unlock(pthread_mutex_t *mutex); 即 Release 操作。

更广义的锁的实现是信号量（Semaphores），由 Dijkstra 提出。它有两种操作：

P() 或者 down()，挂起线程直到信号量变成正的，然后将其减一；
V() 或者 up()，给信号量加一，然后唤醒一个正在 P 的线程。

这个东西除了可以用来当锁，还可以实现线程间的信息传递。

我们已经反复提及进程是具备有限权限的运行环境。每个进程里面有一个或者多个线程跑在一个地址空间上面，每个进程都有自己的文件描述符和网络连接。当你运行一个可执行文件时，它一定跑在一个进程里面。一个应用程序可能会打开一个或者多个进程来共同完成工作。

不同的进程彼此之间有保护，OS 和进程之间也有保护。在现代操作系统中，任何在内核外运行的东西一定都跑在一个进程之中。

可以用 pid_t fork() 函数创建一个进程，此时这个程序会被分离成父进程和子进程（原来程序的状态会被复制成两份）。这个函数的返回值非常巧妙：

如果错误会返回负数；
如果当前程序是父进程，会返回子进程的 pid。
如果当前程序是子进程，会返回 $0$。

这个函数在写 shell 的时候非常常用。你要在后台运行一个程序，就是 fork 一个子进程，然后调用 execv("filename", args) 函数。execv 不会返回。总的来说可能用到的 API 有：

exit：终止一个进程；
fork：复制当前进程；
exec：改变当前进程中跑的程序；
wait：等一个进程结束。这个 wait 有个参数，传入一个地址，函数会向其中写入子进程的返回值。wait 的返回值是子进程 pid；
kill：发信号，用于进程间通信；
sigaction：设置 signal handler。

Windows 系统的 API 叫做 CreateProcess()。

不要在多线程的进程中调用 fork. 因为 fork 之后只有调用 fork 的那个线程会保留，其他线程会直接消失。

如果其他线程此时持有锁，或者正在修改共享数据结构就炸了。

当然，如果你之后打算 exec 就可以不在意这一点，因为 exec 会重置整个地址空间开始运行新程序。

文件和 I/O

Unix 系统的主旨就是所有东西都是“文件”，此处的所有东西包括但不限于磁盘上的文件、外设、网络、进程间通信。一切操作都是基于 open()，close()，read()，write 这几个系统调用。对于不适合通用接口的设备特定控制，通常用 ioctl()。

POSIX 系指 Portable Operating System Interface。它规范了面向程序员的接口，使得软件能够在类 Unix 系统之间具备可移植性。

所谓的文件，就是一篮子被命名的数据。POSIX 文件就是字节序列。文件里面有一些特殊的数据，记录了文件的大小、所有者、修改时间等。这些数据称为元数据。

文件被组织成层次结构。一个目录里面包含了文件和目录。顺着 /home/ff/pkuos/public_html/index.html 这样的层次命名可以找到唯一的一个文件。

每一个进程都有一个工作目录（current working directory，CWD）。这个东西可以通过系统调用 chdir(const char *path) 来修改。在进程中使用绝对路径 /... 就会忽略 CWD 来找文件，使用相对路径 index.html / ./index.html 之类的东西，就会在 CWD 的基础上去找文件。

接下来的内容里面我们来分层讲文件操作的 API。

最上层的文件 API 将文件视作流，即没有任何格式的比特序列。此处有两个函数用来打开和关闭文件：

FILE *fopen(const char *filename, const char *mode); 这里的 mode 可以是 r, w, a, rb 之类的习见的东西，用来指定操作这个文件的权限。
int fclose(FILE *fp);

已经打开的流可以被一个 FILE * 指针定位。任何一个程序执行时，默认都会打开三个流：stdin, stdout, stderr。而且这三个东西都可以被重定向。比如使用著名的管道算符，运行 cat hello.txt | grep "World!" 之时，cat 的 stdout 就会被定向到 grep 的 stdin。为了在流上读写，常用的 API 有

int fputc(int c, FILE *fp);
int fputs(const char *s, FILE *fp);
int fgetc(FILE *fp);
char *fgets(char *buf, int n, FILE *fp);

size_t fread(void *ptr, size_t size_of_elements, size_t number_of_elements, FILE *a_file);
size_t fwrite(void *ptr, size_t size_of_elements, size_t number_of_elements, FILE *a_file);

int fprintf(FILE *restrict stream, const char *restrict format, ...);
int fscanf(FILE *restrict stream, const char *restrict format, ...);

还有几个以前没见过的操作：

int fseek(FILE *stream, long int offset, int whence); // 更改流位置的指针
// 这里 whence 指示 offset 的作用，可以是： 
// - SEEK_SET（从文件开头往后数）
// - SEEK_END（从文件末尾往前数）
// - SEEK_CUR（从当前位置开始数）
long int ftell(FILE *stream); // 查询当前位置
void rewinf(FILE *stream); // 把流的位置调到最开头

Remark. 在用这些系统检查的时候，一定要检查返回值。

较低层次的文件 I/O 使用的是文件描述符。这些 API 都在 fcntl.h 里面。

int open(const char *filename, int flags, mode_t mode);
int creat(const char *filename, mode_t mode);
int close(int filedes);
ssize_t read(int filedes, void *buffer, size_t maxsize);
ssize_t write(int filedes, const void *buffer, size_t size);
off_t lseek(int filedes, off_t offset, int whence); 

int dup2(int old, int new);
int dup(int old);
int pipe(int pipefd[2]); //  Writes to pipefd[1] can be read from pipefd[0]

这些 API 我们其实已经比较熟悉了，这里不再赘述。在调用这些底层 POSIX I/O 时，注意以下要点：

使用前打开；
注意接口都是面向字节的；
显示关闭文件以释放资源。

另外需要知道读写时，内核都设置有缓冲。read 和 write 都不直接发起磁盘访问，而是在用户空间缓冲区和内核缓冲缓存之间复制数据，此后由内核发起磁盘读写。

至此，一个值得思考的问题是文件的 API 的高低两层有何异同，以及这样做的必要性。

从函数实现上看，read 是一个单纯的系统调用，而 fread 在前面还加了一些用户态的处理。

其次，我们申明一些高层 I/O API 的特性，核心是其包含的用户态缓冲机制。FILE* 里面也包含了一系列别的组件，包括但不限于：

文件描述符；
缓冲区；
文件锁（这是多线程并发使用 FILE 的必要之物）
…

此处需要展开说明一下这个缓冲区。当你调用 fwrite 时，会发生以下事件：

你传入的数组被写到 FILE 的缓冲区；
如果缓冲区满了（或 c 语言标准库中，发生某种事件，比如见到某个字符），就会发生 flush。当然手动调用 fflush() 或者关闭文件 fclose 也会刷新缓冲区。

因此，不 flush 缓冲区可能会引发一系列问题。比如在以下代码中：

char x = 'c';
FILE* f1 = fopen("file.txt", "w");
fwrite("b", sizeof(char), 1, f1);
FILE* f2 = fopen("file.txt", "r");
fread(&x, sizeof(char), 1, f1); // x 可能变成 b，也可能还是 c，取决于有没有发生缓冲区刷新

在写代码的时候，不能包含此等未定义行为。正确的做法是必要时 fflush，以及释放内存和关闭文件描述符之前先 fclose 那个 FILE* 指针。在底层 API 中没有这样的问题，只要 write 完，接下来的 read 就能读到它写的内容。

可以看到，引入高层 API 中的用户态缓冲，固然给程序员带来了一些麻烦，你必须恰当地考虑刷新时机。然而，引入这个机制实乃必要：

提升吞吐量。注意，系统调用比正常函数调用开销更大。
提供更丰富的功能。注意，系统调用为了保证内核实现的简明，没有考虑任何的格式信息，而是完全面向字节。比方说，内核中没有“读一行”这样的操作。这个需要先读进缓冲区然后进行用户态处理来实现。

不要混用高低层次的 I/O API. 我们前面说到了 fread 有缓冲区。调用这个函数时，会从 fd 里面读很多东西到缓冲区里面留待用户态处理。此时，如果你再用 read 读入，就不知道当前你在文件的哪个位置了。

接下来我们详细考察文件描述符里面有什么。

众所周知，每个进程都有一个文件描述符到打开文件描述的映射，叫做文件描述符表。一次成功调用的 open 之后，用户将会拿到一个文件描述符（整数），而内核会创建一条打开文件描述，然后将描述符表的对应指针指向它。一条打开文件描述里面由很多资料，我们最关心的两个是：

文件在磁盘上的位置；
当前我们处于这个文件的哪个位置。

如果调用 fork，文件描述符表会被复制到子进程里面。一个进程 close 掉一个文件描述符，只会减少打开文件描述的一次引用。只要存在一个进程引用这个打开文件描述，它就会存在于内存中。这个特性有以下应用：

（stdout 的复制）如果你 fork() 一个进程，则父子进程的输出会去同一个终端。
（socket 的复制）对于服务器来说，fork 出一个子进程会保留网络连接。

回到 dup 和 dup2 两个底层 API。dup(fd) 就是文件描述符表开一个新项，指向 fd 对应的打开文件描述。dup2(fd1, fd2) 就是让 fd2 指的打开文件描述变成 fd1 指向的那个。

进程间通信（IPC），管道和套接字

同一主机上，乃至不同主机上的不同的进程间时常需要进行通信。此时，一个最简单的方法是，使用一个文件。写者把要传输的内容写在某文件中（文件位于磁盘上），然后读者从中读出。然而，这实际上并不高效，因为：

我们时常需要做 $N$ 个进程之间的点对点通信；
我们有时候只需要瞬时通信，这个文件不需要永久存在。

现代操作系统中的解决方案是，由内核来维护一个存在于内存中的一个长度有限的队列，进程可以通过系统调用来访问这个队列。如果队列长度达到上限时尝试向其中写内容，写者阻塞；若读者尝试读这个队列时队列为空，读者阻塞。

POSIX/Unix PIPE 就是这个方案的一个例子。其 API 为 int pipe(int filds[2]);：创建一个管道，相关的两个套接字会被写入这个数组：向 fileds[1] 写的内容可以在 fileds[0] 中读到。使用 PIPE 做父子进程间通信的方法是先 pipe，然后 fork。此时父子进程都会持有 pipe 的入口和出口的文件描述符。此时，父子进程都可以通过两个描述符向对方发消息和接受对方的消息，从而实现半双工通信。然而实践中不推荐这样做，因为不知道线程的调度何时会发生，队列里面可能会混杂双方的信息。常见的处理是，父进程关闭 fileds[0]，子进程关闭 fileds[1]，实现父进程到子进程的单工通信；反之亦然。

值得一提的是在关闭诸描述符之后，pipe 的行为：

最后一个写口的描述符被关闭之后，pipe 视为成功关闭。此时，任意的 read 都只会收到 EOF；
最后一个读口的描述符被关闭之后，所有的写操作都会触发 SIGPIPE 信号。如果进程不处理这个信号，则 write 失败，错误信息为 EPIPE。

两个进程进行通信之时，应当达成双方如何通信的协议。一个协议包含以下两个要素：

语法. 消息格式和发送顺序；
语义. 消息含义与收发后的动作。

通常用状态机来刻画一个协议。如果通信的两个主体位于两个不同结构的主机上，可能还需要决定如何翻译消息中的数字、字符串的表示，这种翻译在 RPC（远程过程调用）中时常发生，这也属于通信协议的一部分。

通信协议在跨网络的进程间通信中至关重要，而协议具体是怎么实现的都是计算机网络的内容，这里我们只关注操作系统层面的抽象。众所周知，一个 TCP 连接是两个进程之间的双向比特流。可以想象按照此前的进程间通信的范式，这需要内核维护一个临时存储 A 发给 B 的数据的队列，以及一个临时存储 B 发给 A 的数据的队列。为了让这一切看起来和文件读写一样以契合 UNIX 系统的哲学，这些资料都被抽象做套接字（Socket）。

具体地，所谓的套接字是一个网络连接的一个端点的抽象。它包含一个文件描述符和两个队列，向这个描述符里 write 会往写队列里面增加内容；向这个描述符发起 read 会消耗读队列里面的内容。此时 lseek 这个操作就无效了。至于一对建立了连接的套接字的这两个队列如何变化，那是网络协议栈中下层协议的任务。对于 TCP 套接字，程序可以大胆假设连接的可靠性。

当然在计算机网络的层面，“打开一个套接字”还颇须一番工夫。主要是套接字是为了连接服务，不能凭空存在，这里主要是需要解决两个问题：

如何命名我们打开的这个连接，从而知道是在与哪个进程通信；
怎么让这些互不相干的程序知道有人想要与之通信。

在计算机网络课里面我们已经知道了这两个问题的答案，在 IP 协议中，进程的命名包括主机名、IP 地址和端口号；而在常见的 Client-Server 模式中，建立连接（打开一对 socket）的步骤为：

服务器会在熟知端口打开一个特殊的套接字，称为 server socket。服务器不能读写这个 socket，而是只有两种操作，listen（监听某个端口）和 accept（给连接的客户端开一个新的 socket）。
客户端通过 connect 向一个正在监听的套接字发起连接。
经过 connect - accept 之后，客户端的套接字和 accept 新分配的套接字就绑定在一起。

服务器可以通过 fork 或者多线程来并发地服务多个客户。注意如果是多线程，一般地写法是开一个有限大小地线程池，连接来了就从池里抽一个空闲的线程来服务。

操作系统中的同步

我们首先来回顾一下操作系统里面并发是如何实现的。

内核为每一个进程维护了一个 PCB（Process Control Block），其中包含以下资料：

状态（Running / Ready / Blocked / …）；
寄存器（当不是 Ready 状态时，必须要维护寄存器状态）；
一些必要的元数据 （PID，用户，优先级，运行时间等）；
内存信息 （包括地址空间和地址翻译需要的必要资料）

内核中有一个调度器，来给进程分配 CPU、内存、IO 之类的资源。某些中断或者系统调用会触发上下文切换。此时内核会把当前进程的状态存进 PCB 里，然后让调度器拿出另一个进程的 PCB 接着运行。在进程的整个生命周期中，可以有以下五种状态：

New. 新创建的进程 / 线程；
Ready. 该进程可以运行。被调度器调度之后可以转移到 Running；
Running. 该进程正在被 CPU 运行。触发某些中断之后可能进入 Ready，阻塞之后进入 waiting；
Waiting. 该进程正在等待某事件（I/O 或者锁）发生。该事件发生之后转移到 Ready。
Terminated. 调用 exit。

调度器一般都是用队列来维护这些 PCB，如 ready 队列，I/O 队列，睡眠队列之类的东西。系统运行时，PCB 在诸队列之间传递。

此外，回忆在多线程程序中，每个线程的私有信息存在 TCB（Thread Control Block）中，包括栈、寄存器、线程元数据等，而堆、全局变量和代码段都是共享的。当创建一个线程时：

栈指针被初始化到栈上某个位置；
返回 PC 被设置为 &ThreadRoot。
参数寄存器中放入函数指针和指针。

线程真正开始运行的位置是 ThreadRoot 函数，而不是你指定的那个函数。ThreadRoot 还负责维护一些基本信息，切换到用户态和收垃圾，其伪代码为：

ThreadRoot(fcnPRT, fcnArgPtr) {
  DoStartupHouseKeeping();
  UserModeSwitch(); // 进入用户态
  Call fcnPre(fcnArgPtr);
  ThreadFinish();
}

发生线程调度的时候，需要保存旧线程所有必要的状态，然后将新线程的私有状态（寄存器，PC，栈指针）加载到 CPU 中，然后跳转到那个 PC 处执行即可，这比进程上下文切换快得多。以下两种事件可能触发线程调度：

内部事件. 发生 I/O，等锁，或者线程自己调用 yeild()。
外部事件. 该线程被抢占（preempted）。如果写过 lab1 就知道如果来了一个优先级更高的线程，现在执行的线程就会被抢占。此时还需要实现一个定时器，每隔一段时间，强制触发一次调度。

注意并发不是并行。当然，如果 CPU 是多核的，就可以并行地运行多个线程。事实上，现代超标量还可能支持所谓的 HyperThreading，即一个周期发送来自不同的线程的指令。

【Shinjuku：FIXME】

那么，既然有多线程这种缺乏保护的并发，就一定有同步的问题。因为线程调度具有不确定性，调度器可以以任意顺序运行线程，也可以随时切换线程。对于不共享状态的独立线程，这自然没有什么影响。但是对于有共享状态的合作线程，这就是一个重大挑战，需要在设计代码时保证正确性。在此之前，我们摆出几个同步中常见的名词：

原子操作. 某一个操作，这个操作执行过程中不会调度；
同步. 用原子操作来实现线程间合作；
互斥. 保证一个事情同一时间只有一个线程在做；
关键区域. 同一时间只能有一个线程在做的区域；
锁. 实现互斥的关键机制。

锁，以及案例分析

回忆我们之前讲的原子操作的概念。事实上，很多指令（双精度浮点数存储、数组拷贝等）甚至都不是原子的。此外，实践中的大部分关键区域也不是单条指令的。锁就是将这些东西原子化的手段。在一段操作之前 acquire 一个锁，然后在之后 release 掉，这一段操作就会变成原子的。

回忆操作全局数据结构的时候就需要加锁。现在考虑两个程序，一个生产者要往一个队列里面塞东西，一个消费者要处理队列中的东西。此时不能简单地加锁：

Producer(item) {
  acquire(&buf_lock); // 这里锁加载 while 前面也是必要的，不然中途调度就炸了
  while (buffer_full) { /* release(&buf_lock); acquire(&buf_lock); */ }; // 但是这个 while 循环会死锁。
  enqueue(item);
  release(&buf_lock);
} 
Consumer(item) {
  acquire(&buf_lock);
  while (buffer_full) { /* release(&buf_lock); acquire(&buf_lock); */ };
  item = dequeue()
  release(&buf_lock);
  return item;
}

正确操作是取消 while 循环里面的那两个注释。要点是判断条件和数据结构操作都要加锁，数据结构操作和前一次判断必须是原子的。此外有一种替代实现，就是用信号量来替代这个判断条件，方法为：

Producer(item) {
  P(&empty); P(&mutex); enqueue(item); V(&mutex); V(&full);
} 
Consumer() {
  P(&full); P(&mutex); enqueue(item); V(&mutex); V(&empty);
}

信号量初值之类的细节的不再赘述。注意 P 的顺序不能交换，否则容易死锁；而 V 的顺序实际上无所谓。这里假设生产者和消费者有多个，代码也无需做任何修改。

除了生产者 - 消费者问题之外，还有一个经典的问题是 Too Much Milk。这一个案例分析旨在证明实现同步需要 load & store 之外的原子的同步原素。考虑两个人（线程）想要喝牛奶，这两个人都有如下基本的工作模式：

看冰箱里是否有牛奶；
如果没有，出门前往超市；
购买牛奶；
回家，把牛奶放入冰箱。

本质上，我们要保护一个 if (noMilk) buy Milk; 的关键区域。

这里，我们用自然语言描述了这些线程的行为模式，但是记住计算机的调度方式可能不符合人类的直觉，因此最后还是需要脱离生活考虑详细的调度方式。

显然存在一种调度顺序，使得两个人都会去买牛奶。自然，如果有所谓的锁，我们可以直接这么写：

1
2
3

acquire(&lock);
if (!Milk) buy Milk;
release(&milklock);

现在忘记我们有锁的 acquire / release 等操作，假设我们只有习见的 load & store 这两个原素（primitive）。直觉上有一个这样的方案：如果一个人要出门，就在冰箱上贴一张纸条。

if (!Milk) {
  if (!Note) {
    Note = 1;
    buy Milk;
    Note = 0;
  }
}

这个程序的问题是如果在判断条件 !Note 结束之后调度走了，还是会发生 Too Much Milk 的问题。这样确实降低了错误频率，但是本质上还是错的，此等错误最为棘手，自然不是我们想要的解决方案。另一个方案是先贴标签，为此需要两个人贴不同的标签，然后检查对方是不是去买了：

Note_self = 1;
if (!Milk) {
  if (!Note_other) {
    buy Milk;
  }
}
Note_self = 0;

这个程序的问题是如果程序在判断条件 !Note_other 之前调度走了，就不会有人去买东西了，出现另一种调度错误。最终一个可能的的解决方案如下：

// Thread A
Note_A = 1;
while (Note_B) {  }
if (!Milk) buy Milk;
Note_A = 0;

// Thread B
Note_B = 1;
if (!Note_A)
  if (!Milk) buy Milk;
Note_B = 0;

不难确认这样确实没有任何问题。但是工程上已经非常复杂，而且两个地位相等的线程代码不同，扩展到多线程时维护性很差。至此，在我们不知道锁怎么实现的时候，我们已经具备了如下知识：如果只有单独的 if 和赋值操作，很难完成同步。实际上，我们还需要 test&set、compare&swap 之类的原子操作把 if 和赋值绑定起来，才能更灵活地实现同步。

锁的实现，同步原素和管程

现在的问题是怎么实现锁。首先考虑单核处理器，在这上面有一个天然的阻止调度的方法就是关闭中断：

1 2	LockAcquire { disable Ints; } LockRelease { enable Ints; }

这个实现有显而易见的几个问题：

你不能让用户在屏蔽中断的情况下持续运行。如果用户此时开了一个死循环，整个机器就炸了。
这样使得程序过度串行化；
如果关键区域里面有 I/O 或者 sleep 之类的东西就直接炸了。

但这提供了一个启发，就是你可以 Acquire 里面关闭中断。代码为：

Acquire() {
  disable interrupts;
  if (value == 1) {
    Put thread on wait-queue;
    sleep();
  } else {
    value = 1;
  }
  enable interrupts;
} 

Release() {
  disable interrupts;
  if (!queue.empty()) {
    Take thread off wait-queue;
    Place on ready queue;
  } else {
    value = 0;
  }
  enable interrupts;
}

注意调用 Acquire 之后，你需要在恰当的位置打开中断。因为你让当前线程 sleep 之后，就会调度一个新的线程上来顶住。但是这个新的线程必须要能够接收中断，也必须能够被正常唤醒。所以，必须在等锁的程序 sleep 之后因此最终的方案是，由调度器调度出来的下一个线程来关中断。

上面的问题是，关闭中断的方法对于多处理器来说开销很大，因为关闭所有处理器核心的中断需要处理器间通信。因此，硬件一般会提供额外的同步原素，比如说以下几种操作：

test&set (&address) {
  ressult = M[address];
  M[address] = 1;
  return result;
}
swap (&address, register) {
  // trivial.
}
compare&swap(&address, reg1, reg2) {
  if (reg1 == M[address]) {
    M[address] = reg2;
    return success;
  } else {
    return failure;
  }
}

有了这几个原素，最简单的锁就可以写成：

Acquire() {
  while(test&set(value));
} 
Release() {
  value = 0;
}

这个实现逻辑上是正确的，但是它的问题是等锁的程序会一直消耗 CPU 资源。可以想象一个减小消耗的方法是把等锁的程序放进睡眠队列，一个参考实现是用一个这种自旋的 while 循环去代替之前的关闭终端：

Acquire() {
  while(test&set(guard));
  if (value == 1) {
    Put thread on wait-queue;
    sleep() & guard = 0;
  } else {
    value = 1;
    guard = 0;
  }
} 

Release() {
  while(test&set(guard));
  if (!queue.empty()) {
    Take thread off wait-queue;
    Place on ready queue;
  } else {
    value = 0;
  }
  guard = 0;
}

实现并发的一个范式是管程（Monitor）。一个管程包含一个锁以及零或多个条件变量，用于管理对共享数据的并发访问。其中，条件变量（Condition Variable）系指一个队列，其中包含若干个正在等某件事情（这件事情的语义由程序员记忆）的线程。对条件变量中有以下几个操作：

Wait(&lock) 释放锁，然后 sleep；在 sleep 结束之前重新请求锁；
Signal() 唤醒一个 Waiter；
Broadcast() 唤醒所有的 Waiter。

要点是一个线程操作一个条件变量时，必须持有那个锁。

一个利用管程实现的（无限大的）生产者-消费者问题解法如下：

lock buf_lock;
condition buf_CV;
queue queue;

Producer(item) {
  acquire(&buf_lock);
  enqueue(&queue, item);
  cond_signal(&buf_CV);
  release(&buf_lock);
}

Consumer() {
  acquire(&buf_lock);
  while (is_Empty(&queue)) { // ?
    cond_wait(&buf_CV, &buf_lock);
  }
  item = dequeue(&queue);
  release(&buf_lock);
  return item;
}

（？）处使用 while 还是 if 取决于调度器的语义。调度器可以有两种写法：

Hoare Style. signal 之后立即把锁和 CPU 交给等待线程，然后等待线程立刻运行。
Mesa Style. signal 之后继续持有锁，只是把一个等待线程放入 ready queue。当它被从 ready queue 中拿出来之后可能已经不满足那个条件了。

现代操作系统多数使用 Mesa Style。因为你发现正常情况下，尽管 Hoare Style 语义简明，但 Mesa Style 可以比 Hoare Style 少调度几次，而且更好实现。完整版的生产者-消费者问题的管程解法如下：

lock buf_lock;
condition producer_CV;
condition consumer_CV;

Producer(item) {
  acquire(&buf_lock);
  while (buffer_full) { cond_wait(&producer_CV, &buf_lock); }
  enqueue(item);
  cond_signal(&consumer_CV);
  release(&buf_lock);
}

Consumer() {
  acquire(&buf_lock);
  while (is_Empty(&queue)) { cond_wait(&consumer_CV, &buf_lock); }
  item = dequeue(&queue);
  cond_signal(&producer_CV);
  release(&buf_lock);
  return item;
}

建议不要考虑用信号量实现管程得 API，你会发现有很多麻烦得问题。

读者-写者问题

这个是并发编程中一类常见的问题。有两种用户：

读者. 从来不会修改数据库；
写者. 读和写数据库。

正确性要求是：

没有写者时，读者可以访问数据库；
既没有读者又没有写者时，写者可以访问数据库；
你可能会使用很多状态变量。同一时间只有一个线程能够访问状态变量。很显然这里你可能想维护
- 活跃读者数量 AR，等待读者数量 WR，活跃写者数量 AW，等待写者数量 WW；
- 两个条件变量 okToRead 和 okToWrite。

你可以发现这很符合管程的范式。据此可以写出一份写者优先（优先唤醒写者）代码：

Reader() {
  acquire(&lock);
  while ((AW + WW) > 0) {
    WR++;
    cond_wait(&okToRead, &lock);
    WR--;
  }
  AR++;
  release(&lock);
  // read
  acquire(&lock);
  AR--;
  if (AR == 0 && WW > 0)
    cond_signal(&okToWrite);
  release(&lock);
} 

Writer() {
  acquire(&lock);
  while ((AW + AR) > 0) {
    WW++;
    cond_wait(&okToWrite, &lock);
    WW--;
  }
  AW++;
  release(&lock);
  // write
  acquire(&lock);
  AW--;
  if (WW > 0) {
    cond_signal(&okToWrite);
  } else {
    cond_broadcast(&okToRead);
  }
}

Remark. 关于这个代码有以下这些评论：

该策略是写者优先，因此会有读者饥饿。
这个代码做了最大程度的保险，有一些地方可以精简，但是也有代价：
1. 读者退出可以不判断任何东西，因为写者的 while 循环中会判断。代价是你会频繁唤醒写者，效率变低；
2. 读者退出时甚至可以 broadcast 给写者。但是这样大量的写者就会被唤醒然后发现条件不满足，然后继续 sleep（惊群效应），效率更低；
3. 读者和写者甚至可以共用一个条件变量，但是因此此时队首不一定是你想唤醒的东西，此处必须 broadcast，导致效率降低。

最后来说一些语言层面的支持。有一件事情是，你必须确保所有出一个关键区域的路径都有解锁。比如说你依次调用以下东西：

setjmp()，然后调用一个函数；
这个函数请求一个锁，然后调用一个函数；
这个函数调用 longjump；

或者

请求一个锁，触发一个异常，然后释放锁；
触发异常之后不会再回去释放锁。

你就会一直死锁在第二层，然后就炸了。很多语言实现了一些东西来帮你避免这种情况。一方面，你可以用 try ... catch ... 这种语法，在 catch 里面把锁释放了。另一方面：

C++ 里面有个叫做 lock_guard 的东西，以任何路径出了 lock_guard 的作用域自动释放与之关联的那个锁；
Python 里面可以写 with lock:，进入这个代码块自动加锁，以任何路径出了这一个代码块自动释放锁；
Java 有 synchronized 这个修饰函数的关键字，进入这个函数加锁，以任何路径出这个函数释放锁。

调度

回忆线程调度的大体框架状如：

run_new_thread() {
  if (readyThreads(TCBs)) {
    nextTCB = selectThread(TCBs);
    run (nextTCB);
  } else {
    run_idle_thread();
  }
}

那么这些 selectThread 该怎么写，就是调度器要回答的问题。我们首先来刻画一下这个问题的模型，虽然下面似乎全是批话，完全没有形式化的内容。

首先我们假设：

一个用户只跑一个程序；
一个程序只跑一个线程；
程序之间是独立的。

这里的假设很奇怪，主要是为了简化一些现实问题，比如说我在跑一个大实验，你在跑五个小实验，那么谁应该分到更多的机时之类的公平性问题。此外，我们假设一个程序在两个阶段之间交替：

CPU Burst；
I/O Burst。

经验上，CPU Burst 的长度一般比较短。评价标准包括：

最小化完成时间（这里的完成时间就是小学老师说的那种你耽误一分钟就是耽误了所有人一分钟，求所有线程的完成时间的平均值）；
最大化吞吐量（最大化每秒执行的操作数，通过最小化上下文切换开销和合理使用资源等实现）；
公平性；

这三个目标之间直觉上存在一些 Trade-off。

经典策略

最简明的调度策略就是先到先服务 FCFS（First Come，First Services），就是用 FIFO 队列来调度，一直运行到阻塞为止。

这个策略的优缺点十分显然：

优点. 简单，策略开销低；
缺点. 对到达顺序非常敏感，有队头阻塞。

另一个简单的策略叫时间片轮转（RR，Roung Robin）：每个进程运行至多 $q$ 时间单位之后被抢占，然后塞到队尾。显然

$q$ 取无穷大的极限就是 FCFS；
$q$ 越小交错越强。$q$ 越小上下文切换开销越大。

$q$ 给出了一个等待时间 - 吞吐量之间的 trade-off。但因为计算代价的时候有个很垃圾的除法下取整运算，这两件事情都不是单调的：

RR 的平均完成时间并不总优于 FCFS；
$q$ 变小，平均完成时间不一定变小。

一个自然的想法是给每个任务赋一个优先级。严格优先级调度（SPS，Strict Priority Scheduling）就是给每个优先级开个队列，然后从优先级最大的任务里面挑一个运行。如果写过 Lab 就会知道这东西有以下问题：

公平性. 低优先级作业长期得不到 CPU；
优先级反转. 有三个线程优先级分别为 H，M，L，H 等待一个 L 上面的锁，这样高优先级任务的等待时间反而比 M 长。

有各种动态分配优先级的启发式算法，比如说之前写过的所有权捐赠等。

如果我们能预知未来，那么有两种调度策略：

Shortest Time to Completion First（STCF）；
Shortest Remaining Time First（SRTF）；

顾名思义。后者是前者的有抢占版本。用 exchange argument 可以看出这两个是（等待时间方面）最优的贪心。然而很遗憾，如果有很多个小任务和一个大任务，那么大任务会饥饿。下面的手段都是用来近似 SRTF 的。

在策略中我们经常需要动态估计某些量，比如说一个 job 的 CPU Burst 时间。这种估计一般是通过采样和统计手段实现。此处统计手段可以是卡尔曼滤波器，甚至最简单的指数加权平均

$$
\bar\tau_n = \alpha\tau_{n - 1} + (1 - \alpha)\bar\tau_{n - 1}
$$

一个随机近似 SRTF 的手段是给每个 Job 发一定量的 lottery，然后用俄罗斯轮盘赌方法随机抽取。注意，采取这种调度策略时必须：

时间短的 Job 得到的 lottery 多；
每个 Job 必须持有至少一个 lottery 来避免饥饿。

多级反馈队列（Multi-Level Feedback Queue） 是一种启发式策略。我们开若干个队列表示不同的优先级，每个优先级内部是 FCFS 或者 RR，然而：

一个新任务来了，先进入高优先级队列；
若用满时间片，则下调优先级；
若没有超时，上调优先级。

当然这里不同优先级之间的调度策略也可以有选择，比如说硬要先调度最高优先级，或者可以用时间切片法让每个优先级获得某个比例的 CPU 时间。这个策略有一个问题是它可以被攻击，如果直到你用了 MLFQ，那么 CPU 密集的程序可以频繁 I/O 来留在高优先级。

Case Study

【FIXME】

内存

在第二节我们已经讲过，地址空间和翻译乃是操作系统的四个基本成分之一。所谓的地址空间，就是 $2^k$ 个单元的集合。其中，每个单元是一个 $k$ 位的二进制数，代表一个可以访问的地址。

截至目前，我们通过已经解决了“不同的进程和线程需要复用 CPU 的问题”。事实上，进程和线程还需要复用内存。在共享内存时，有以下要点的概念：

保护. 线程不能访问其他进程中的私有内存。
翻译. 如果使用虚拟地址，应当能把虚拟地址翻译成物理地址。如果加入了地址翻译，处理器可以用虚拟地址，硬件可以用物理地址，这样一方面给了程序一个对内存的统一视角，另一方面可以阻止地址相交。
受控的相交. 如果想要进程共享一些块，我们应该能做到这一点。

那么，操作系统对于内存访问起什么作用？如果对于每次内存访问，操作系统都要通过某种中断介入其中，那么效率太低。因此，地址翻译应当交由硬件（MMU，Memory Manage Unit）完成，操作系统只负责解决异常的情况（比如 Page Fault）。

历史上，操作系统对于地址的约束有以下发展阶段：

Uniprogramming. 所有应用跑在同一片物理地址之上，可以访问全部物理地址，没有任何翻译和保护。
Primitive Multiprogramming. 没有地址翻译和保护。不同的应用被划分了相应的地址段。在程序开始运行之时需要现场链接来重定位所有访存地址。在这个阶段一个程序出 Bug 可能导致其他程序甚至操作系统崩溃。
Multiprogramming with Protection. 使用 Base and Bound 方法，每个进程被分配一个 Base 和一个 Bound，只能在这个连续段内访存。除了每次运行前重新链接，这里开始就可以进行初步的地址翻译了（当然这会导致每次访存多算一次加法）。普通的 Base and Bound 有以下问题：
- 碎片问题. 每个进程可能不一样大，那么和堆空间一样，此处会有碎片化问题；
- 不支持稀疏地址空间. 回忆我们的虚拟地址空间被分成 code，data，stack，heap 之类的段，每一段可能用的非常少，但是有向上生长、向下生长导致中间有很多空位。直接 Base and Bound 非常浪费；
- 很难做进程间共享. 比如两个进程想要共享 code 段（这很常见，你 fork 一下立即就会出现这种需求，否则浪费物理空间），对于 Base and Bound 这就很困难。
Segmentation. 解决的方法非常自然，就是把这些段分别分配 Base 和 Bound。一个虚拟地址的格式现在就是 $\mathrm{SegId}:\mathrm{Offset}$，然后 CPU 里面会有一个表，每个表项是 $\mathrm{Base}:\mathrm{Limit}:V/N$，MMU 可以拿着每个 SegID 找到表项，检查是否合法，然后加出物理地址。这样一来
- 我们实现了稀疏地址空间；
- 如果是栈空间和堆空间超过了 Limit，可以增加其大小；
- 通过 V/N 这一位可以实现保护，标记只读和读写等；
- 在上下文切换时，可能不得不把所有内存放到磁盘上去（所谓的交换空间）。

至此，现代的虚拟地址和地址翻译已然初具雏形。

虚拟内存和地址翻译

回忆一个进程的虚拟地址空间定义为：全体它可以访问的地址，以及每个地址的状态。对于一个 32 位的机器，它一共有 $2^{32}$ 个 $32$ 位二进制的地址。

然而，上面提到的 Segmentation 有以下问题：

碎片. 因为你还是要把不同长度的片段塞进物理地址里，所以不可避免地存在内部碎片（段内没完全用完）和外部碎片（段间有很多 gap）；
上下文切换开销大. 这个交换空间的技术开销非常大。

解决的办法是分页（Paging）：把物理地址划分成固定大小的片段。最简单的分页机制可以这样实现：

开一个页表（Page Table）。该表存在于物理内存中，可以通过页表指针（PTP）找到。每个表项包含页基地址和权限位（V 可用性，R 可读性，W 可写性）。
虚拟地址为页编号 + 偏移量。
翻译方式为拿着页编号查页表，拿到页表起始地址。然后做诸多检查（检查 bound 和权限），通过即可拼上偏移量得到物理地址。

在页表里面取相同的页基地址就可以实现共享页。共享页的应用范围如下：

每个进程的“内核区域”具有相同的页表项；
不同进程跑了相同的可执行文件，则代码段可以共享；
用户层系统库也可以共享；
其他根据需要共享的内存。

在上下文切换的时候，需要切换 PTP 和页表大小限制。这种机制通过地址翻译和阻止进程自己修改页表实现了保护。

但是简单页表最大的问题就是页表体积庞大。一般来说页表是 4KB，也就是说 offset 是 12 位。对于 32 位操作系统，虚拟地址的前 20 位就都是 Page ID，页表有 $1048576$ 项；对于 64 位操作系统，页表就有 $4503599627370496$ 项，很明显，这样单是装一个页表都是不可接受的。然而实践中，地址空间里面有用的东西非常稀疏。此处惯用的手法是使用哈希表（称为 Inverted Hash Table）。要么，就是使用动态开点数据结构，体现在具体实现上就是多级页表。此时，无论是几级页表，其表项被叫做 PTE，包含以下两个元素：指向下一级对象（可能是下一级页表基地址，也可能是物理页基地址）的指针，和权限位。

对于一个 32 位系统，虚拟地址由三段拼成：10 位一级页表索引；10 位二级页表索引；12 位偏移量。地址翻译方式如下：

MMU 拿着 PTP 找到一级页表基地址；
根据一级页表索引拿到二级页表基地址；
根据二级页表索引拿到物理页基地址，拼上 offset 完成翻译。

x86_64 使用 48 位虚拟地址，四级页表，每一级页表都是 9 位索引。无论如何，这个迭代查找多级页表的操作，叫做页表树遍历（page table tree traversal），由 MMU（Memory Manage Unit）完成。具体地，MMU 接受指令和具体的地址，然后要么（通过查找 cache 或者内存）返回一个具体的物理帧，要么返回错误。

高速缓存

实践中，如果每次访存都要下沉到主存（通常是 DRAM）则开销巨大。然而，程序的访存一般具有一定的局部性：

时间局部性. 同一个地址经常在短时间内被多次访问；
空间局部性. 短时间内访问的地址通常是连续的。

因此，现代处理器通常进行高速缓存（Caching），在 CPU 内部有一块东西（通常是 SRAM）里面存储了部分近期读取过的内存数据，访问这个单元比查询内存更快。如果你要访问的地址在 Cache 里面，那么你无需继续往下做 DRAM 访问。其效率度量为 Average Access Time：

$$
\mathrm{AAT} = \text{Hit Rate}\times \text{Hit Time} + \text{Miss Rate} \times \text{Miss Time}
$$

如果你要访问的地址不在 Cache 里面，那么称发生了一次缓存不命中（Cache Miss）。缓存不命中有以下来源：

冷不命中. 第一次访问某个 Block；
容量. Cache 空间有限，存不下所有的东西；想要减少这种不命中唯有增大 Cache 大小；
冲突. 即便有时候 Cache 空间有剩余，由于 Cache 的实现方式，可能有多个地址被映射到同一个 Cache 的位置，反复造成驱逐。除了增大 Cache 大小之外，可以增加相联度；
相干. 其他进程修改了内存，导致你 Cache 的东西无效了。

接下来讨论如何实现 Cache。Cache 的基本单元叫做 Block，每个 Block 内部有一些比特。对于每一个虚拟地址，它被分割成以下段：

Block Address. 这一段被进一步分为
- Tag. 标志位，用来判断缓存是否命中；
- Index. 用来索引缓存位置；注意，根据局部性的定义，Index 必须是低位。
Block offset. 顾名思义。

在 ICS 中我们已经学习过最简单的 Cache 叫做直接映射高速缓存。对于 32 位系统，这种高速缓存有以下参数：若块大小为 $2^M$，Cache 有效容量为 $2^N$ 比特，那么地址的前 $32 - N$ 位就是 Tag，最后 $M$ 位是 Block offset，中间是 Cache Index。直接映射高速缓存被组织成 $2^{32 - N - M}$ 行，每一行包含 $2^M$ 个字节的数据，$32 - N$ 位的 Tag，和一位有效位（Valid Bit）。访存时，先拿着 Index 找到对应的行，然后看 Tag 是否匹配以及有效位是不是 1，如果都是，缓存命中。

另一种叫做 $r$ 级组相联高速缓存，与上面的区别是 Cache 被组织成 $2^{32 - N - M}$ 组，每一组有 $M$ 行数据，访存时组里有一个对上就命中。

最极限的情况是全相联高速缓存，它只有一个组。

对于后两种，如果发生了 Cache Miss，你需要知道组里哪一行需要被驱逐。惯用的手法是随机驱逐或者驱逐上次访问时间最远的（LRU）。

现在一个新的问题是，Cache 的索引是虚拟地址还是物理地址？按照这个标准，可以有两种不同的 Pipeline：

Physically-Indexed Caches. Cache 的索引是物理地址。需要先做完翻译，然后交给 Cache，Cache Miss 之后访存；
Virtually-Indexed Caches. Cache 的索引是虚拟地址。CPU 可以拿着虚拟地址去查 Cache，如果未命中再做地址翻译。

前者的好处是任意数据在 Cache 中有唯一的虚拟地址，而且在上下文切换中 Cache 可以不改变，但是 TLB 是一个关键路径。后者则是完全反过来。实践中处理器（比如 x86 处理器）一般都是第一种。

考虑 Caching 的另一个原因是，每次地址翻译都需要查询内存，对于三级页表来说，每一次实际上的 DRAM 访问都伴随两次必要的 DRAM 访问（页表查询）。因此，如果我们的页表可以被装在 Cache 当中，自然访存能获得加速。地址翻译专用的 Cache 叫做 TLB（Translation Lookaside Buffer），它是一个全相联高速缓存，里面存的是近期地址翻译的结果。很明显：

Code 段访问基本上是连续的，局部性非常好；
栈空间访问必然是具有局部性的；
data 段的访问局部性不是很好，但是还是存在。

TLB 自然也可以做成多级的。由于 TLB 是访存的关键路径，它必须非常快。关于 TLB 的效率，直觉上：

如果 TLB 未命中，开销非常大。
Index 必须是 Block Address 的低位，然而 code，data，stack 的这些位基本上都是一样的，所以会持续产生冲突不命中。

基于以上考量，TLB 设计通常遵循以下规范：小（128-512 行）；高连通度（一般是全联通的）。有些时候还会在前面加一个非常小（4-16 个 Entry）的直接缓存高速缓存，称为 TLB 摘要（TLB Slice）来加速全相联的查找。

在现代机器中，通常虚拟地址的 Offset 段完全盖住了物理地址的 index 和 offset 两个字段。这意味着，你在做地址翻译找页基地址的时候，可以同时拿着 index 去查 cache。这样可以并行地做地址翻译和查 cache。这样相当于在虚拟地址高速缓存和物理地址高速缓存之间拉了一条线。

注意上下文切换的时候 TLB 里面的东西就无效了。一般来说有以下解决方案：

上下文切换之后直接把所有行标记成 invalid；这样会造成大量的冷不命中；
在 TLB 的 Tag 里面加上进程 ID；这样需要硬件协同设计。

注意如果地址翻译表发生了变化，比如说一个页面被从内存里丢到了磁盘里，那么你必须马上把 TLB 的对应表项给 invalid 掉，不然后续地址翻译会出问题。

需求分页

如果地址翻译中，发生了异常，那么就会返回 Page Fault。可能的原因包括：PTE 被标记不合法，没有权限，或者缺页。这时候内核会被唤醒来处理错误，对于不合法的问题，一般地保护措施是直接终止执行。但是缺页是必然出现且必须解决的。原因是，现代程序使用的空间通常非常大，然而它不会随时使用全部的空间。比如说，一个统计数据是，一个程序的 90% 的时间都只花在 10% 的代码上（90-10 定律）。那么，你把所有的代码都存在主存里，就很浪费空间了。因此，解决方法是进行需求分页（Demand Paging），简单来说就是将主存视为硬盘的 Cache。所谓的缺页就是“主存不命中”。

这个特殊的 Cache 的结构有以下要点：

块大小是一页的大小（4KB）。
因为地址翻译会帮你找到对应的行，所以可以视为全相联的。
定位 Page 的方式是先查 TLB，查不到就进行地址翻译。
驱逐策略还是随机或者 LRU 之类的，但是有另外的说法，本节最后展开；
如果没有命中，下到磁盘去找；
写策略必须是写回（不然每次都要访问硬盘开销太大）

这里，PTE 的有效位就显得格外重要了。如果一个 PTE 被标记成 valid，那么表示 PTE 指向主存中的一个位置。否则，这表示页面不在主存中，PTE 中的信息可以指示你在磁盘里面找到对应的页面的备份。访问 invalid 的 PTE 之时立即触发页错误，然后操作系统将负责：

选择一个要驱逐的页面（或者一个空页面）。
如果该页面是脏的，要将其写回硬盘。
修改它的 PTE，和对应的 TLB（如果有）。
从磁盘中拉取正在访问的这个页面。
修改当前页面的 PTE。
返回用户态。
修改当前页面的 TLB（因为本次地址翻译的成功时间点在返回用户态之后）。

关于空页面的选取，主要是依靠以下东西：

操作系统维护一个 free list，里面存当前空闲的所有块；
Unix 有一个回收器（reaper），在主存快要满了的时候，写回脏页面并且清除一些很久没有用过的（干净）页面。

磁盘上有一个专门的区域用来保存这些 Page（可以被视为一个文件），称为 swap file。

注意，4 这一步是开销巨大的磁盘访问，OS 要挂起当前线程，执行其他线程。需求分页和虚拟内存协同起来，可以实现以下操作：

扩展堆栈的时候，只需要开一个新的页。
Fork 的时候，可以直接复制页表，PTE 指向父进程的物理地址，但是被标记成 NO-WRITE。发生写操作的时候懒惰地复制页面。
用 MMAP 来实现共享区域，以及随机访问磁盘上的文件。

需求分页的效率用以下的有效访问时间（Effective Access Time）刻画：

$$
\text{EAT} = \text{Hit Rate} \times \text{Hit Time} + \text{Miss Rate}\times \text{Miss Time} = \text{Hit Time} + \text{Miss Rate}\times \text{Miss Penalty}
$$

然后我们来考虑 Paging 的驱除策略。直观上可以想象这几种：

FIFO. 将主存视为一个循环队列。可以想象这东西会把频繁访问的东西扔掉。
RANDOM. 随机驱除。不好分析
MIN. 去掉下一次使用的时间最靠后的。可以证明最优，但是我们没法预测未来。
LRU. 去掉上一次使用时间最早的。根据局部性，最近没有用的东西将来很可能也不会用。因此这是 MIN 的一个近似。

直观展示一个驱除策略的效果，可以画出 Page Faults - Number of Frames 曲线。对于 MIN 和 LRU，可以证明这个曲线都是单调递减的。但是对于 FIFO 则不然，这叫做 Bélády’s anomaly。

实践中，因为主存非常珍贵，我们甚至不希望开很多位来存一个帧上次被访问的时间，或者开一个数据结构来维护这个最小值。对于 LRU 有一个零阶近似的方案是 Clock 算法：

将所有帧顺时针排成一个环，每个帧附加一个叫做 use 的 bit。
顺时针扫描。如果 use 是 $1$，将其改成 $0$；直到遇到空帧或者遇到一个 use 为 $0$ 的帧。

这个策略一方面可以证明均摊 $O(1)$，另一方面确实也近似了 LRU。自然可以想到这个算法的拓展：$N$ 次机会 Clock 算法。每个帧额外配备一个计数器，如果发现 use 为 $1$，则清空 use 和计数器。如果 use 为 $1$，将计数器加一。如果遇到一个计数器为 $N$ 的东西，驱除这个页面。

容易发现 $N$ 越大，堆 LRU 的近似越精确。而算法是均摊 $O(N)$ 的。这里有一个 trade-off。另一个问题是对于脏页面，其写回开销也非常大。因此，实践中对于干净页面和脏页面并不是一视同仁的，而是对于干净页面置 $N = 1$，对于脏页面，$N = 1$ 时写回，$N = 2$ 时驱除。

另一个近似 LRU 的方法是 Second-Chance List 算法。

开两个队列，叫做 Active list（有读写权限）和 SC list（没有权限）；
如果一个页面在 Active list 里，可以直接访问。
否则报 Page Fault。
1. 如果这一页在 SC List 里面，将其弹出并插入 Active List 的头部；
2. 如果这一页不在 SC List 里面，直接插入 Active List 的头部。
3. Active List 大小有限。任意时刻如果它溢出了，弹出队头将其插入队尾。SC List 大小有限，任意时刻如果它移除了，驱除队尾。

这个算法相当于是在 LRU 和 FIFO 之间拉了一条线：如果两队列加起来大小就是 Page 数量，那么这就是 LRU；如果 SC List 大小为 0，这就是 FIFO。

可以额外维护一个 Free List 存所有的空帧来提速。

最后还剩一些遗留问题。

反向页映射. 驱除一页的时候，怎么直到要 invalid 哪个 PTE？在有共享段的时候这更难了。可能的选项是

PTE 链表. 那么开销可能比较大。
基于对象的反向映射. 注意你的每个共享的 Page 通常都是某一个唯一的对象（比如说代码）的部分，因此页表只需要存相对这个对象的位置。而在驱除的时候，你只需要 invalid 这个对象就可以。

进程间的内存分配. 上下文切换时，肯定不需要把一个进程的所有页面全都放进 swap space。在这种情况下，有两种页面置换策略：

全局置换. 一个页面可以驱除任何一个页面，包括别的进程占用的页面；
局部置换. 每个进程被分配了一些页面，它只能驱除自己被分配的页面。此处，分配页面的方法可以有：
- 均匀分配，所有进程分配等量的内存；
- 正比于进程的空间大小；
- 按照优先级分配；
- 根据 Page Fault 率调整。常见的手法是设置一个 Lower bound 和一个 upper bound。如果 page fault 次数超过上界，给它分配更多空间；如果低于下界，减少它的空间。

抖动. 称一个程序正在使用的所有 Page 为 working set。如果剩余空间小于 working set 的大小，则会出现页面在磁盘和内存之间反复跳跃。这种现象称为抖动（Thrashing）。

常见的解决方法是如果发现 working set 大小超过剩余空间，立即挂起进程。

减小冷不命中. 有时候读入是非常线性的。你可能可以预读一堆页面，这需要你写一个程序来跟踪 woking set。

I/O

这一节讲了一堆神秘体系结构，不知道要干什么，此处抄一下 PPT，可能没什么逻辑。我们默认读者熟悉硬盘和 SSD 的结构，课件中对于这两个东西的大量介绍不抄。

很明显，计算机没有 I/O 就没有作用了。然而在 I/O 时，涉及到的设备多种多样。我们希望：

提供不同硬件设备的统一接口；
处理硬件错误和传输错误；
在未知硬件是否会卡住的情况下，管理硬件。

在体系结构课中我们曾经学过，I/O 的实现依靠 I/O 控制器。处理器通过像访问内存一样，读写其中的 I/O 寄存器来访问 I/O 功能。这里，寄存器的编制可以是分开编址（通过特制的 in / out 访问）或者统一编址（寄存器被编进物理地址空间，用 load / store 指令访问）。

现代 I/O 系统的一个重要组成部分是总线。总线是多余两个模块之间传送信息的公共通路，以及附加其上的协议。一般来说，靠近处理器一端带宽高，但是传输模式不灵活；靠经 I/O 子系统段带宽低，但是传输模式灵活。使用总线使得我们用一套线缆维护了 $O(n^2)$ 个设备之间的问题。代价就是每次只有一个事务可以被执行，其他的都必须等待。

关于 I/O，有这样一些参数：

数据颗粒度. 比特（比如键盘） / 块（比如磁盘等）；
访问模式. 序列（比如磁带）/ 随机访问（比如磁盘等）；有些设备需要持续监控（polling），有些在它们需要服务的时候发起中断。关于 polling 和中断，两者的优缺点如下：
- Polling：优点是瞬时开销比处理中断小，但是在长时间或者不可预测的 I/O 操作时多耗费很多周期；
- 中断：可以很好地处理不可预测的事件，但是处理一次中断开销比较大。
传输机制. 程序控制 I/O，或者直接存储器访问方式（DMA）。

为了操作不同的设备，需要的一个关键组件是设备驱动程序。一个设备的驱动程序系指内核中一段和它相关的特定代码，用于与该设备交互。所有的设备驱动程序需要给出统一的 I/O 接口，对于特殊的操作，用 ioctl() 函数完成。驱动程序通常分成两个部分：

Top half. 运行截至系统调用函数的部分。需要实现 open(), close(), read(), write(), ioctl() 之类的接口。这部分将会指示设备开始 I/O，然后可能会让线程陷入睡眠；
Bottom half. 作为中断处理程序的部分。用于获取输入或者传输输出。

那么不同的设备需要实现哪些接口呢？可以按照设备的类型分类：

Block Device. 访问块状数据的设备，如磁盘，磁带，DVD-ROM。需要支持 open(), read()，甚至 write(), seek()。
Character Device. 如键盘，鼠标等，每次只传输一个字节的。需要实现 get(), put()。
Network Devices. 需要实现一众 socket 接口。

在上端确实发起了 I/O 操作之后，这个时间操作系统是否需要等待？这里也需要看接口的类型：

Blocking Interface. 让当前线程 sleep，直到数据准备好；
Non-blocking Interface. 返回非常快，因此直接等到数据传输成功；
Asynchronous Interface. 立即返回 buffer 的地址，在 buffer 被装满或者取走之后内核通知用户。

最后我们来刻画 I/O 的性能。这主要需要看两个量：响应时间或称为延迟（每个操作需要的时间），带宽或吞吐量（某个操作发生，或者比特传输的速率）。回顾 I/O 操作的 pipeline，可以发现对于延迟而言，其主要产因分三部分：来自软件（可以用排队来刻画），来自硬件控制器，和来自 I/O 设备。此处我们主要来分析排队的部分。

首先考虑最简单的确定性情形：所有请求顺次以固定时间间隔到达，用一个固定时间完成。这里只需要看两个参数：服务率 $\mu = 1 / T_s$（其中 $T_s$ 是完成一次服务需要的时间），和到达率 $1 / T_a$（其中 $T_a$ 是到达的时间间隔）。显然，吞吐量关于 $\lambda / \mu$ 呈现出先线性增长后不变的态势。若 $\lambda \leq \mu$，那自然永远不会排队，而若 $\lambda > \mu$，则队列会持续增大。因此排队时延随着时间增长显然会呈现出先不变后线性增长的态势。

实践中，请求总是爆发性地到来的。为了分析这种东西，我们需要排队论。这里我们做两个基本假设：

系统达到平衡态，队列长度没有限制；
两个请求到来之间的时间间隔服从某一无记忆性地随机分布（泊松过程）。

模型中一般考虑以下参数：

$\lambda$：请求到达的平均时间；
$T_{s}$：服务一次请求的平均时间（即 $m$）；其倒数就是服务率 $\mu$，利用率为 $u := \lambda / \mu = \lambda T_s$；
$C$：服务时间的变异系数（$\sigma^2 / m^2$）；

我们希望计算 $T_q$（排队的时间）和平均队列长度 $L_q = \lambda T_q$（根据 Little 定律）。计算表明

$$
T_q = T_s\times \frac 12(1 + C)\times \frac{u}{1 - u}
$$

$C = 1$ 的情况叫做 M/M/I 队列，其他情况叫做 M/G/I 队列。值得一提的是，根据磁盘的特性，如果在磁盘访问这里有了一个这样的队列，除了直接 FIFO 之外，还可以对磁盘访问做如下优化：

SSTF（Shortest Seek Time First）. 在队列中找转圈时间最小的那个来服务。显然，这个策略可能导致饥饿。
SCAN. 开环，把队列分成在当前磁头左边和右边，然后先倒着服务左边，再顺着服务右边。这解决了饥饿，但是和 SSTF 的味道可能不是很一样。
C-SCAN. 让磁盘只往一个方向转。

文件系统

文件系统是操作系统中负责将硬盘的区块接口转换成文件、目录之类的对象的一个层次。它将受限的硬件接口（只是普通的 block 序列）转化成更方便、有用的接口，其提供：

文件命名. 通过名字查找文件，而非 block 的编号；
文件组织. 文件名被组织成树状的目录，文件内容被映射到 block 中；
保护. 访问权限等；
可靠性. 防止文件因为软件崩溃和硬件错误而损坏。

文件的基本实体包含以下两类：

文件. 用户可见的逻辑上的 block 序列；
目录. 用户可见的名字到文件的映射。

从用户的视角看，一个文件是一个持久的数据结构。而从系统的视角来看，文件就是字节序列，至于它以什么样的数据结构形式存在于磁盘上，是无所谓的。在操作系统内部，文件就是一系列 block。一般来说 block 的大小不小于 sector 的大小，为 4KB。

注意，文件操作的一切单元都是 block（这是磁盘读写的单元）。所以即便你只需要写一个字节，也需要拉出整个 block。现代操作系统处理这个事情的手段主要是 buffer。

一个磁盘可以被视为 sector 的一维数组。其中每个 sector 的物理位置都由以下三元组描述：$[sylinder, surface, sector]$。实践中，每个 sector 都有一个整数的逻辑地址。磁盘控制器负责将逻辑地址翻译成物理位置。对操作系统，只提供其逻辑地址（Logical Block Addressing）。

一个文件系统至少要能做到：

你需要知道哪些 block 对应哪些文件（对于一个文件，要知道它存在哪里）；
你需要直到一个目录底下有哪些文件名；
你需要直到哪里有空的 block（写入新的内容时，这一点很重要）。

维护这些东西的必要信息都存在于磁盘上的某处。此外，还需要注意必须考虑磁盘上的东西的持久性。因为磁盘是非易失性存储，所以在关机之后，文件系统必须保持有意义的状态。

文件系统的设计要点

设计文件系统的时候，需要注意以下因素：

尽量优化访存的性能。 多用连续的访问，最小化寻找时间。这一点非常难。
读写前先打开文件。 此时可以检查权限，和寻找文件的位置等；
使用文件时必须确定其大小。
文件需要被组织成目录。
需要仔细分配和释放块。 这其实本质上就是 1 的在线要求。

据此，通常的文件系统的包含以下四个成分：目录（directory），索引结构（index structure），存储区块（storage blocks），空闲空间映射（free space map）。

回忆文件描述符表当中，每个描述符指向一个 OFD。这个 OFD 会告诉你打开的是哪个文件，手段是给出这个文件的文件编号（file number，inumber）。所谓的目录，就是文件名到文件编号的映射。每一个 (file_number, file_name) 二元组，称为一个目录表项（directory entry）。此处，操作系统提供如下的保护：任意进程不允许直接用 read 阅读目录的原始比特序列。它只允许通过 readdir 函数来枚举这个映射中的二元组，这不会暴露目录的原始比特序列。以下几个系统调用用于访问目录：

open, creat, readdir，可以用来打开并遍历目录；
mkdir / rmdir 可以用于给目录添加或者删除 entry；
link / unlink 用来创建链接（可以理解成文件的别名）。

每一个地址空间，都有一个指针，指向它用来解析文件名的目录，称为 current working directory。每个文件自己都在磁盘里面有一个 inode，里面包含这个文件的全部文件描述。每次调用 open，它就会从 cwd 开始（如果是相对路径），找到磁盘上的 inode，然后将其拉到内存中的全局打开文件表里，然后将对应进程的文件描述符表的指针指向它。

Case Study

File Allocation Table. 假设我们现在已经有了一个手段将文件名翻译成 file number。那么拿着这个 file number 怎么找到整个文件呢？FAT 是微软的的系统系统，它主要是这样的一个数据结构，存在磁盘上：

一个大小等于磁盘区块数目的表。
对于每个文件，将其占有的区块按顺序穿成一个链表。
链表的根节点编号就是 file number。
对于空闲区块，用一个 free list 来存。

如果你要格式化一个硬盘，只需要将所有 block 清空，然后把 FAT 每一项都标记成功。快速格式化只需要做后者。

在 FAT 中，目录被组织成一个链表。其中，root 的链表的根节点存在一个良定义的位置，一般是 2 号。

UNIX File System. 文件被组织成一个 inode 的数组，下标就是 file number。inode 主要包含文件的元数据，和一个多层级的树状结构用来找到文件的区块。具体地

文件元数据. 包含文件所属的 User，Group，9 个权限位。
对于小文件，它包含 12 个直接指针，直接指向数据区块；
对于大文件，它包含若干间接指针，间接指针将指向一个全是指针的区块。回忆一个区块大小是 4KB，因此它可以包含 1024 个指针。那么 2 级间接指针可以覆盖 4MB 内存，3 阶可以覆盖 4 GB，依次类推。
倍增决定一个文件有几个直接指针和间接指针，共同构成对整个文件的索引。

后来，Berkeley 的研究人员改进了这个文件系统，提出了 FFS。它的改动主要有：将 inode 的位置重新安排；用 bitmap 存空闲块，而不是 free list；保留 10% 空间；尝试连续编排文件。重新编排 inode 的动机主要是：

所有 inode 都在同一个位置，而且通常是磁盘的外圈轨道。这导致两个问题：磁头故障可能会直接摧毁整个文件系统；inode 离文件太远，在读小文件的时候需要来回转，非常耗时。
创建文件的时候，你通常不知道它有多大，因此难以知道它被放在何处，增加优化难度。

在 FFS 中，磁盘被分割成不同的 block group。其中，目录和其中的文件都被分在同一个 block group，这些文件的 inode 和这个 block group 的 bitmap 也被放在一起。当文件长度变大时，在 bitmap 上查后继然后写这些后继的区块。

对于大目录，我们用 B 树来加速查找。

Windows NTFS（New Technology File System）. 文件数据被组织成一个数据库状的 MFT（Master File Table），其中所有的东西都是 <attribute : value> 对的序列。具体来说，MFT 的一项最大有 1KB，里面包含：

如果是小文件，直接包含文件的数据；
文件的开始 block，大小；
对于更大的文件：指向其他的 MFT 表项的指针。

目录都用 B 树实现。

文件系统的细节

内存映射文件. 传统的 I/O 进行时需要在内存中的 buffer 和地址空间中显式传输数据，这样开销非常大。常见的手段是，将文件直接 mmap 到地址空间中，即虚拟内存上的某些 Page 就直接映射到磁盘上的具体的 Page，加载可执行文件的时候就使用了这种手法。

系统提供了以下接口：mmap(void *addr, size_t len, int prot, int flags, int fd, off_t offset)，用于将某文件从某处开始的东西映射到虚拟内存中 addr 开始的区块，并指定权限。

进程很容易借助一个文件，通过 MMAP 实现区块共享。

缓冲区高速缓存. 内核要修改磁盘，必须把磁盘上的 block 复制到主存，修改之后写回。这个过程通常有一些局部性，因此可以在内存中设置一个缓冲区用于高效访问数据，目录，inode 和 freemap。这个 cache 有以下要点：

完全由操作系统软件实现，和 CPU 中的 Cache 不一样；
置换策略是 LRU。因为我们完全承担得起 LRU 的开销。当然这样有一个弊端就是如果一个应用要扫描整个文件系统，LRU 就会把 cache 里面所有东西驱除，换成一些可能只用这一下的东西。
这个 Cache 的大小是动态决定的，使得文件访问和驱除页面造成的磁盘操作达到平衡。
使用预取策略。
写策略为写回。但是必须定期写回数据，来减小系统崩溃的损失。

几个重要的性质. 文件系统还需要考虑以下几个重要性质：

Availability. 系统能够接受并处理请求的概率。用百分数里面 9 的个数来衡量；
Durability. 文件系统的纠错能力；
Reliability. 系统在规定时间内完成其全部功能的概率；

如何增加系统的 Durability？

在磁盘上，用 Reed-Solomon 纠错码进行纠错。
保证写操作在短时间内可以存货。比如说你可以用所谓的 NVRAM 来做 buffer cache。
备份数据。这里的关键因素是，备份的位置应当尽可能独立（比如说备份在两张盘上，这样一张炸了另一张还能用）。

为备份数据，有一类专门的技术叫做独立磁盘冗余阵列（RAID，Redundant array of Independent Disks）。RAID 的方案分为

RAID 1. 每个盘都被完整的复制到另一个磁盘上。对于这种方案，写操作需要两次同步的写，但是读操作可以并行起来。如果一个磁盘炸了，可以马上换掉坏盘，然后通过另一个来恢复。此时必须确保你随时都有能用的空盘（Hot Spare）。
RAID 5. 假设你有 $N$ 个盘，每个盘有 $M$ 个 block。我们这样存储：
- 先令第 $i \bmod N$ 个磁盘的第 $i \bmod N$ 为第 $i$ 个校验块（这样将所有 block 视为一个 $M\times N$ 的矩阵，每一行都有一个校验块）。
- 然后数据矩阵被从上到下，从左到右地被填入非校验快。
- 第 $i$ 行的校验块存储这一行的数据块的 xor sum。
- 如果一个磁盘炸了，可以拿着其他磁盘和校验块恢复数据。这样改进了 RAID 每次写操作要写两次的问题。
RAID 6. 实践中磁盘很大，可能你在恢复数据的过程中有一个盘又炸了。为此 RAID 使用更复杂的纠错码而不只是奇偶校验，EVENODD 码或者 Reed-Solomon 之类的。

RAID 6 启发我们做一种叫做 Geographic Replication 的操作。比方说，对于 4 个片段的数据，我们用 Reed-Solomon Code 生成 16 个副本，根据经典编码理论的知识，我们知道随便拿着这 16 个中的 4 个都可以拿到完整的数据。因此我们把这些东西分布式地存起来。这样做 durability 非常高，因为你很难销毁 12 个副本，而且非常容易读。但是必须等 16 个东西都在线地时候才能写。

如何增加文件系统的 Reliability？此处还需要解决磁盘断电、系统崩溃这些问题。此时，可能有些正在进行的操作会丢失。RAID 并不能处理这种情况。这些要求一个文件系统能提供类似于可持久化的功能来回滚版本。有一些经典的实现 Reliability 的方法：

Careful Ordering and Recovery. 仔细规定操作磁盘的顺序，保证如果一列操作从中间断了，要能够被检测或者修复。这个看起来不是很本质。
Copy on Write. 写的时候复制一个新的块，对于改动小的块直接复用。这似乎是标准的可持久化套路。

更一般地，实现 Reliability 需要你实现如下概念：一个事务系指一个原子的操作，其将文件系统从一个自洽地状态转移到另一个。如果事务进行途中出现了错误或者与其他事务冲突，都需要回滚，只有成功执行这个事务才被确认（commit）。容易想到的一种实现方法是，开一个日志。一个事务在它被写进日志之后被承认。虽然可能文件系统没有被立即修改，但是数据还在日志里面。课件上说所谓的“Log Structured Filesystem”中一切数据以 log 的形式存在，我并没有理解这句话在说什么。

基于日志的 reliability 的一种实现方法叫做 Journaling。在这种做法中，我们不直接修改磁盘。我们首先把要更新的东西作为事务存进一个 Log（也在磁盘上），前后用 Start 和 Commit 包住。一旦修改被写入 Log，就可以写进文件系统。一个修改一旦成功执行，就删掉 Log 中的表项。此时便有维护文件系统一致性的手段：

如果在写 Journal 的时候断电，那么存在有 start 没有 commit 的事务。我们找到这种东西，直接删掉。
如果在某个操作 apply 的时候断电，那么你可以直接从一个 start 处开始执行到 commit。

可以想象这个 jounaling 开销很大，因为每次写操作都要做两遍。现代操作系统确实做了 journaling，但是只针对文件元数据。

分布式系统. 摆了。