操作系统导论

1. 操作系统介绍

操作系统的目标

• 对硬件进行抽象，使得对它们的调用变得简单易用；（易用）
• 对数据进行持久保存，避免丢失；（存储）
• 对程序进行隔离，避免出现隐私或安全问题；（安全）
• 持久可靠的工作，不轻易发生故障；（可靠）

操作系统的历史

• 库时代：让应用程序可以通过引用库来调用硬件；缺点：应用程序的权限很大，可以无限制的访问所有硬件资源以及其上的数据，缺少安全保护机制；
• 模式时代：引入了系统调用，应用程序只跑在用户模式下，权限受到限制；系统级别的功能通过系统调用 API 来实现，调用后，系统级别的代码跑在内核模式下，拥有最高权限；限制了应用程序能够操作的范围；
• 分时时代：随着 CPU 相对 I/O 设备和存储设备的速度越来越快，为了避免浪费 CPU 资源，引入分时共享，实现多个程序并行的机制；
• 隔离时代：为了避免程序之间相互影响，引入了虚拟内存，以便对内存进行保护；
• 现代：在小型机之后，个人计算机开始兴起，早期的 DOS 和 MacOS 并没有借鉴小型机的操作系统，走了弯路；之后开始进行调整，MacOS 借鉴了 UNIX 的思想，而微软则推出 Windows NT（此处的 NT 表示新技术，new technology），让局面得以改善；UNIX 由于版本官司，导致其发展受到阻碍，之后 Linux 借鉴了其思路，重写了代码，绕开了版权问题，并通过开源快速发展了起来；

2. 抽象：进程

操作系统其实要面临三种角色的使用者，包括个人用户、应用程序开发者、硬件设备生产商等；不同的使用者会使用不同的视角，来看待操作系统提供的功能；

进程简介

进程是一种 CPU 虚拟化技术，实际的物理 CPU 可能只有一个，但是通过分时共享（time sharing）技术，让不同的应用程序轮流使用 CPU，这样在应用程序的眼里，只需要将 CPU 当作自己独自拥有的并进行调用就可以了，简化了应用程序对 CPU 调用的复杂度；

事实上应用程序根本就不发起对 CPU 的调用，而只是按顺序准备好所有的指令，等待着被 CPU 依次执行；看起来就好像 CPU 一直为其工作一样，而不是仅在需要的时候，才通过系统调用来让 CPU 为自己工作；这跟调用其他硬件设备不太一样；因为每一条指令的执行，都是需要 CPU 的，所以其实也算是持续的做 CPU 调用；

进程技术更像是一种执行程序的抽象，即通过创建进程来执行程序，简化了执行程序所要的一系列准备工作；

进程 API

操作系统提供了一些进程的 API 接口，这些接口即可以被用户使用，也可以被应用程序使用；

• 创建进程；
• 销毁进程；
• 等待进程；
• 查询进程状态；
• 暂停/恢复进程；

进程创建细节

当创建一个新进程时，操作系统有一系列的工作需要完成，包括创建新页表、从磁盘加载应用程序的指令到内存、为变量分配内存（栈和堆）完成初始化、更新页表的映射、分配文件描述符、开始执行应用程序的第一条指令等；

进程的状态

一个进程表示一个正在运行中的程序，它有三种状态：运行中、阻塞中、就绪中；当应用程序发起某些耗时较久的 I/O 操作时，进程的状态会被置为阻塞中，直到 I/O 操作完成的事件后，进程的状态将被更新为“就绪”，之后便可以等待调度给 CPU 继续执行余下的指令了；当然，也有可能直接从阻塞状态变成运行状态，取决于事件发生后，在操作系统中设定的调度策略）；

进程其实还有初始、终结等两个状态，它们分别对应进程刚创建时和进程准备退出时的场景；

数据结构

操作系统在本质上也是一个程序，它除了提供接口供其他程序（进程）调用外，还同时维护跟踪着所有其他程序（进程）的状态，以实现在不同进程之间的切换；因此，它需要创建一系列的对象（结构）来保存这些信息；

每个进程都有一些元信息，这些信息以“结构”的形态（C 语言中的一种数据类型，类似对象），存储在内存中；当操作系统切换进程时，进程对象的某些属性将会被更新，以便后续重新运行该进程时，可以从之前停止的地方继续执行余下的指令；

3. 插叙：进程 API

fork() 系统调用

fork 调用会创建一个子进程，子进程会完全拷贝父进程的一切东西，并且是从调用处的指令开始往下执行剩下的代码，而不是从头开始执行所有代码；这个时候系统中有两个一模一样的进程了，区别只在于父进程的 fork 调用，其返回值是子进程的 pid， 而子进程的 fork 调用返回值是 0（如果调用成功的话）；根据这个返回值，我们就可以区分当前是在哪个进程中，并在接下来运行不同的代码；

wait() 系统调用

wait 函数可用来控制当前进程的执行进入阻塞状态，一直等到自己的子进程执行完毕后，再从暂停的地方重新开始执行自己的代码；

exec() 系统调用

fork 让子进程完全拷贝父进程的代码，exec 则可以让新进程运行和原进程完全不一样的东西，并且它并不是通过创建新进程来实现，而是直接在内存中，用被调用的新程序的数据覆盖旧进程的一切数据；如果在 exec() 之后，旧程序还有一部分代码还没有执行的话，则那部分代码就再也没有机会执行了；

为什么这么设计进程 API ？

fork 负责创建子进程，exec 负责用新进程覆盖当前进程，这意味着如果两者配合起来使用，可以实现在运行新进程里面，先跑一段子进程的代码，干一点想干的其他事情；整个过程是先创建新的子进程（复制父进程代码），再覆盖该子进程（用其他新代码），其中最大的重点是在覆盖之前做的相关事情，不会影响到父进程，却又能在覆盖之前，引用父进程的环境和代码，做一些准备工作；

上面的这种工作方式，很适合 shell 想要实现的功能，即在 shell 中调用程序（通过 fork 创建新进程，然后 exec 新程序，并且父进程调用 wait 等待子进程的返回）；

# 重定向的实现原理：shell 在 fork 出子进程后，将子进程的标准输出重定向到 newfile 文件；然后用 exec 调用 wc，接下来 wc 的输出就会进入到文件中了
> wc pc.c > newfile.txt

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>
#include <string.h>
#include <fcntl.h>
// 重定向的实现
int main(int argc, char *argv[])
{
	int rc = fork();
	if (rc < 0) {
		fprintf(stderr, "fork failed\n");
		exit(1);
	} else if (rc == 0) {
         // 可用的文件描述符是从 0 开始计数的，当创建一个进程时，0 一般绑定到标准输出；
         // 通过关闭标准输出，将使得 0 描述符回到可用的状态；
         // 当使用 open 命令打开一个新文件时，它会寻找最小的可用描述符，此时刚好就是 0，因此新文件被绑定到了 0；
         // 完成绑定后，接下来程序中的所有输出，都会被写入文件中；
		close(STDOUT_FILENO);
		open("./p4.output", O_CREAT|O_WRONLY|O_TRUNC, S_IRWXU);

		// now exec "wc"...
		char *myargs[3];
		myargs[0] = strdup("wc");
		myargs[1] = strdup("p3.c");
		myargs[2] = NULL;
		execvp(myargs[0], myargs);
	} else {
        // wait 会返回子进程的 pid；如果当前进程没有子进程，则会返回 -1，表示调用错误；
		int wc = wait(NULL);
	}
	return 0;
}

UNIX shell 中的管道功能也是使用这种方式来实现的；前一个程序的输出，被重定向到管道队列中，然后将下一个程序的输入也重定向到管道队列中，这样就可以实现将上一个程序的输出，无缝的作为下一个程序的输入；其背后使用了 pipe 系统调用；

其他 API

关于如果与进程交互，UNIX 中有一系列丰富的工具，常见的包括：

• ps，查看当前正在运行的进程；
• top，当前各进程的资源占用情况；
• kill，给某个进程发送终止的信号；

4. 机制：受限直接执行

待解决问题：执行程序的时候，不可避免需要将 CPU 运行指令的权力交给程序，但是却要实现两方面的目标，一是交出 CPU 之后，能够再收回来，避免程序永久性占用；二是程序使用 CPU 执行指令的范围应该受到限制，避免程序访问任意资源；最后，在不同的时间将不同的 CPU 交付给不同的程序使用，不可避免要在程序间切换，因此还需要考虑如何减少切换带来的开销，提高性能；

基本技巧：受限直接执行

操作系统执行程序的过程：

• OS：在进程列表中新增一个条目；
• OS：为程序分配内存；
• OS：将程序加载到内存中；
• OS：根据 argc/argv 初始化程序的栈；
• OS：清除寄存器
• OS：将 main 函数的起始地址放入寄存器，以便从该处开始执行指令；
• 程序：执行 main 函数下的指令
• 程序：从 main 函数中返回；
• OS：释放进程的内存；
• OS：将进程从进程列表中删除；

问题1：受限制的操作

程序在执行过程中，不可避免需要使用到一些 I/O 操作，为了避免恶意的程序滥用这些操作，在执行指令时，现代操作系统通过提供用户模式和内核模式两种状态，来区别于程序发起的普通操作和受限操作；

当程序开始执行时，默认是运行在用户模式下的；当程序想执行一些受限制的操作时，需要遵守操作系统的约定，调用操作系统提前写好的函数（即系统调用），并将参数传递给该函数去执行；操作系统的函数会执行在内核模式下，它可以执行任意类型的操作，访问任意类型的资源；当然，也可以对程序想要实现的操作先进行一番审核，确保该操作是有权限的，才继续往下，不然可以直接驳回；

每个函数背后其实是一条或多条的指令；当程序按约定执行操作系统提供的函数时，其实就是在执行这些指令；在这些指令中，有一条 trap 指令，当 CPU 执行到该条指令时，会将当前程序的运行模式，从用户模式切换为内核模式，并将下一条指令的地址，修改到操作系统在虚拟内存空间中的指令的对应地址，这样 CPU 接下来就开始执行操作系统自己在开机后，预先加载到内存中的那些指令；

问：程序能否实现不执行 trap 指令，却实现对用户模式的更改？

答：由于程序被 OS 加载到内存后，一开始默认运行在用户模式下，在此模式下，程序想去修改模式状态的值，应该会被 CPU 拒绝；

问：好奇这个状态值存在哪里？是否存在某个寄存器里面？

答：所有硬件，在 OS 刚启动时，OS 会准备好一份表格，上面备注当出现某个异常时，需要调用的异常处理的指令地址，并把该地址写入硬件的存储器中；当出现某种异常时，硬件根据存储器中记录的地址，从该地址加载指令，开始执行；此时的硬件相当于被写死了，包括 CPU 也是；当程序尝试调用硬件处理某类事情时，硬件只会按写好的地址处取指令来执行，而不会执行程序给出的指令；如果程序尝试非法访问某些资源时，CPU 会报错，例如段错误；

完善后的 OS 执行程序的流程：

• OS：初始化陷阱表，指定当出现某种类型的异常时，需要调用哪些指令来处理；
• OS：将异常处理指令的地址告知 CPU；
• CPU：记住异常处理指令的地址；
• OS：在进程表上添加新条目、为程序分配内存、加载程序到内存中、根据 argv 初始化程序栈、初始化内核栈、从陷阱返回；
• CPU：从内核栈恢复寄存器、切换为用户模式、根据寄存器地址跳转到 main 入口指令；
• 程序：执行 main、调用系统调用、触发陷阱、陷入 OS（将控制权移交给 OS）；
• CPU：将寄存器保存到内核栈（因为后续要为应用程序恢复寄存器状态）、切换为内核模式、跳转到陷阱处理指令；
• OS：执行陷阱处理指令、完成系统调用的工作任务、从陷阱返回；
• CPU：从内核栈恢复寄存器、切换为用户模式、跳转到陷阱之后的指令地址；
• 程序：继续执行余下指令、从 main 中返回、调用 exit 系统调用，触发陷阱，陷入 OS；
• CPU：将寄存器保存到内核栈、切换为内核模式、跳转到陷阱处理指令；
• OS：释放进程的内存、将进程从进程列表中删除；

CPU 的寄存器是供不同的程序轮流使用的，因此如果想要调用另外一个函数 B 做某种运算，其逻辑是当前函数 A 将函数 B 所需要的参数先保存到约定的寄存器中，然后跳转到 B 函数的指令入口地址，开始执行 B 函数；函数 B 的指令会自行到约定的寄存器处查找所需要的参数；

问题2：在进程间切换

问：由于 CPU 是供不同程序轮流使用的，而操作系统本质上也不外乎是另外一个大一点的程序，当 CPU 在执行其他程序的指令时，操作系统如何将控制权拿回来呢？

协作模式

早期的方案是让程序每隔一段时间做一次系统调用，这个系统调用其实啥事也不作，唯一实现的效果是将控制权切换回给操作系统；但这种模式有个漏洞，即程序本身要遵守约定才，如果程序是一个恶意程序，操作系统就被架空了；当然，为了防止程序权力不受限制，在该模式下，如果程序尝试做一下非法的动作时，例如访问本不应该访问的内存，或者计算以 0 的除法，则会触发异常，导致控制权转回给 OS，接下来 OS 可能会将程序杀死；

非协作模式

显然依赖每个程序都会善意的交回控制权是很危险的，因此需要有另外一种机制保证无论如何 CPU 都可以取得控制权；解决办法就是在 CPU 内置一个时钟中断的功能，它会按照提前设置好的时间值，每隔一段时间就触发一次中断异常，然后执行 OS 的异常指令，这样就将 CPU 的执行权交回给 OS 了；除了将异常处理地址写入 CPU 外，启用 CPU 的时间中断功能，也是操作系统在启动时的必做功课之一，这样它才拥有 CPU 控制权的安全保证；

CPU 在触发中断时，需要将当前程序的各种寄存器状态保存下来，以便中断结束后，能够从当前程序的中断继续执行；

保存和恢复上下文

当中断时钟触发中断异常后，CPU 控制权交加给 OS，OS 需要决定接下来运行哪个程序；如果是要切换到其他程序，OS 需要负责保存当前程序的上下文（保存到进程结构中），以便将来再回来执行该程序时，能够从中断处继续；

问题3：并发

当 OS 在处理某个系统调用时，有可能此时发生了一个中断，因此操作系统现在相当于有两个任务要处理了；如何解决并发的问题，不同的操作系统有不同的策略；既可以单纯的禁止和拒绝（代价是当前任务处理过久的话，有可能丢失未处理的那个任务），也可以是引入锁的机制，并发处理（代价是复杂度大大提高）；

当一个 OS 运行的时间越久，由于各种意料之外的情况的存在，它有可能会慢慢累积越来越多的错误，导致出现一些莫明其妙的问题；因此，定期对 OS 进行重启是一种有益的做法；它可以让操作系统恢复到一个初始状态，这个状态得到了更加充分的测试，存在更少的不确定性；

5. 进程调度：介绍

当有多个进程在同时运行的时候，不可避免会出现调度的工作，因此需要制定一个调度的策略，以尽可能提高机器的运行效率；

工作负载假设

为了判断不同调度策略的效率，先从做一些最简单和简化的基本假设，来作为讨论的起始点，这些基本假设包括：

• 所有任务同时到达 CPU
• 每个任务运行相同的时间
• 一旦开始某个任务，就一直运行到任务完毕再退出，中间不切换；
• 所有的工作只涉及 CPU ，不使用其他 I/O 设备
• CPU 已经提前知道每个工作需要运行多少时间；

调度指标

为了比较不同调度策略的好坏，还需要设计一个指标，以便将调度策略的效率进行量化；此处假设使用周转时间作为指标

任务周转时间 = 完成时间 - 到达时间；

此处的到达时间指任务到达 CPU 的时间（可以先假设为零，即假设所有任务同一时间到达 CPU，供 CPU 进行调度）

先进先出策略 FIFO

先进先出策略（First In First Out）的思想很简单，就是先到达的先处理，等处理完了再处理下一个；后到达的先等待；

它的优点是策略的实现很容易很简单；

它的缺点是有可能会增加平均周转时间，因为有可能先到达的任务是一个非常耗时的任务，而后面的任务是小任务，结果导致大量的小任务被迫等待很久以后才能得到处理；

最短任务优先策略 SJF

如果任务同时到达，那么最短任务优先（Shortest Job First）是最优的策略，它可以让平均周转时间最低；但现实的问题是任务常常不会同时到达，这就导致如果先到达的任务是一个大任务，即后续到达的小任务仍然需要被迫等待大任务先执行完成，导致平均周转时间相对先进先出并没有什么变化；

最短完成时间优先策略 STCF

最短完成时间优先（Shortest Time-to-Completion First）的思想是，当有多个任务到达 CPU 时，即使 CPU 当前已经在处理某个任务，CPU 仍然会比较一下所有这些任务（包括处理中的）的剩余工作时间，最少的那个优先处理；

但这个策略有一个问题，即 CPU 需要提前知道任务的剩余完成时间，但显然这也是不太可能的；

新度量指标：响应时间

前面的三个策略都是针对周转时间这个指标来设计的，这在早期的批处理系统是有意义的。在那个年代，开发人员提前将 CPU 要做的工作先准备好，然后一次性的送入 CPU 执行，然后开发人员静静等待结果即可；

但是 PC 后来进入了个人消费者的时代，用户体验也变得越来越重要，因此，响应时间变成了更重要的指标，而不再是周转时间；由于 CPU 处理能力越来越快，分时系统的引入，让 CPU 能够同时处理多个程序；

轮转策略 RR

轮转策略（Round-Robin）的思想，就是将程序的运行时间划分时间中断周期的倍数时间，然后 CPU 在多个任务之间不停的轮转执行，直到某个任务结束退出轮转队列为止；

虽然时间片是中断周期的倍数，但是它并不是越短越好，因为 CPU 切换进程是需要成本的，因此在响应时间和切换时间之间，需要采取一个折中平衡的点；

结合 I/O

轮转策略并没有从总体上降低所有任务的总完成时间，甚至相反，它基本上都大大延长了周转时间，但是它提高了响应时间，让用户体验更好，减少了等待的感觉；但是当任务需要调用 I/O 时，轮转策略的周转时间会有所降低；

无法预知

一般来说，操作系统对进程任务需要多少时间才能完成并不了解的，因此前面提出的策略都不好使，因为它们都要求操作系统有未卜先知的能力；

6.调度：多级反馈队列

现代操作系统使用的是多级反馈队列策略（MLFQ：Multi-Level Feedback Queue）的调度方法，这个方法最早是在 1962 年的时候提出来的；它的目标是兼顾响应时间和周转时间；

基本规则

MLFQ 的基本思想是维护多个不同优先级的队列，每次都优先执行高优先级队列中的任务；如果同一个队列中有多个任务，则在这些任务之间使用轮转策略；一个任务在某个时刻只能处于一个队列中；

接下来的核心是，MLFQ 设计了一套规则，用来观察任务接下来的表现，如果根据规则，某个任务被判断为是一个交互为主的任务（例如频繁放弃 CPU 占用，等待用户的键盘输入），则将调高任务的优先级（即把它从低优先的队列中拉出来，放到高优先级的队列中去）；

在任务刚到达时，系统并不知道它是何种类型的任务，因此默认先将其设为最高优先，如果它短时间内不能完成，则不断降低它的优先级；

• 规则1：如果 A 的优先级大于 B，运行 A；
• 规则2：如果 A 的优先级等于 B，轮转运行 A 和 B；

尝试1：如何改变优先级

• 规则3：任务到达时，先将它放在最高优先级的队列；
• 规则4a：如果任务完整用完分配给它的第一个时间片的话，降低一个优先级（放入另一个队列中）；
• 规则4b：如果任务在用完时间之前主动释放 CPU，则优先级保持不变；

截止目前的规则，只会降低优先级的动作，还没有调高优先级的动作，但是一个任务可能在不同的时间阶段，其表现形式不同，比如一开始是计算密集型的，之后变成了交互密集型的；目前的规则会导致该任务在后期的交互响应很慢，甚至直接饿死了；

另外还要防止一些任务出现欺诈，即它本质上是计算密集型的任务，即故意在时间片快结束前主动释放 CPU ，从而维持其优先级不变，糊弄调度程序；

尝试2：提升优先级

为了避免综合型任务（前期计算密集型，后期交互密集型）被饿死，需要定期关照一下它们，因此引入规则5；

• 规则5：每经过一段时间 S，就把系统中所有任务重新加入到最高优先级的队列；

这个规则引入了一个新问题，即 S 的大小如何设置的问题；如果 S 设置得太大，则任务仍然有可能饿死；如果设置得太小，则交互型任务的响应时间变慢；

尝试3：更好的计时方式

为了避免被一些恶意任务糊弄，调度策略需要改进原来的规则4，从原本的单次计时制，改变为累计时制，即累计该任务在当前队列已经用了多少时间，而不再像原来一样，如果任务主动释放 CPU，就会重新计时；现在不重新计时了，而是不管有无主动释放，或者释放多少次，只计算该任务在当前优先级的队列中，已经占用和消耗了多少分配给它的 CPU 时间；如果该累计时间已经达到配额的上限，就将它的优先级调低；

• 规则4（改进版）：如果任务用完了其在某个优先级队列中的时间配额，就将它降低一个优先级（不管它中间是否主动释放 CPU，以及释放了多少次）；

MLFQ 调优及其他问题

为了更好的提高性能，大多数 MLFQ 的实现都支持给不同的优先级队列设置不同的时间配额，整体原则是优先级越高的队列，时间配额越小，单次执行时间越短，即切换也频繁；而优先级越低的队列，时间配置越大（单次执行时间越久）；

至于每种优先级的具体时间配额应该是多少，以及多长时间提升一次所有任务的优先级，不同的 MLFQ 实现有不同的做法；有些是使用配置表，有些是使用数学公式算法；

有些操作系统有内置的调度策略，但站在用户的层面，该默认策略并一定是用户在运行某个进程时最想要的效果，因此，操作系统一般会提高一些接口，供用户或系统管理员进行调用，用来告知操作系统一些建议，以便操作系统可以基于这些建议，做出更好的调度安排；

7.调度：比例份额

之前的调度策略目标是最小化响应时间和周转时间；但是如果换成另外一个目标，即保证每个任务都可以分配到一定比例的 CPU 时间，则会衍生另外一种类型的调度算法：比例份额调度策略；

比例份额策略有一些非常简单的实现思路，即彩票制；即让每个进程拥有一定数量的彩票，然后从彩票池中随机抽奖，抽出哪个号码，就运行拥有该彩票号码的进程；如果某个进程的优先级比例高，则就给它分配多一点的彩票，这样它就被抽中的概率就是提高；反之则是下降；

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

彩票制的最大亮点是引入了随机性，虽然随机性在短时间内并不能保证概率符合预期，但是只要足够长的时间，就可以无限接近预期；但是随机性最大的好处在于它可以避免出现传统人工算法可能出现的无法覆盖的极端边角情况；

另外一个好处是随机算法实现起来很容易，没有很多复杂的中间状态值需要记录；因此，它运行起来也更快；

虚拟机的内存分配管理也经常使用彩票制来实现；

彩票机制

在原始的彩票调度策略下，为了让操作系统能够更加灵活的应对各种使用场景，额外引入了一些配套的机制来改进原始彩票机制，例如：

• 用户内部的二次分配：假设用户 A 获得系统分配的100 张彩票，而它内部有两个任务要执行，它可以给这两个任务再做一次分配；
• 彩票转让机制：一个进程可以临时的将自己的彩票转给另外一个进程，以促进另外一个进程更快的执行；

实现思路

彩票调度策略实现思路很简单，仅需要一个随机数生成器、一个链表，一个进程结构（保存进程号和它拥有的彩票数）；

当随机数生成出来后，开始遍历链表，判断当前的彩票数，加上之前已经遍历完的彩票数，看是否会大于出奖号码，如果大于，则当前链表节点即是中奖的进程；

为了让遍历更加有效率，最好能够将链表按彩票数从大到小进行排列，这样有助于更快找到中奖号码；

由于彩票算法存在随机性，这意味着当任务的执行时间很短时，彩票算法的分配效率比较糟糕，即并不是公平分配的，而是随机性很大；只有当任务的执行时间很长，需要很多个时间片时，在分配上面就会越发的公平；

如何分配彩票

如何分配彩票这个问题，就彩票机制本身来说，并没有提供任何答案。因为操作系统对于即将要运行的进程是未知的，所以自然也不知道应该分配多少彩票给该进程才算是合理的；

步长调度策略

由于彩票制的随机性，在小样本数时表现不好，因此通过引入步长的概念来减少这种随机性；它的基本思路是先用一个统一的大数，来除各个进程的彩票数，这样就得到该进程如果想要积累到该大数，需要走多少步；例如假设大数是 10000，则拥有 200 张彩票的步长 = 10000 / 200 = 50 个步长；

步长调度策略是每走一步，就累加记录当前任务的累计步长；在下一轮分配的时候，优先考虑分配给累计步长数最小的进程；

虽然步长调度去除了随机性，但是其实现比彩票调度稍微复杂一点点，因为需要引入全局状态，记录每个任务的累计步长是多少；另外步长调度仍然也还没是没有解决彩票调度存在的问题，即初始化状态下，应该给一个任务分配多少彩票；

小结

彩票调度和步长调度并没有在操作系统中得到广泛的采用，其原因即在于未解决初始状态如何分配彩票的问题，但是它们在一些特殊场景中可以使用，例如虚拟机的实现；因为在这些场景中，初始状态分配多少彩票，由用户给出了答案；

8.多处理器的调度

多处理器出现的原因在硬件条件方面的限制，即某个时间点，硬件设计人员无法在不增加太多功耗的情况下，当单核 CPU 实现更快的速度，因此通过在一块芯片上放置多个 CPU 来实现曲线救国；但这也给操作系统和应用程序引入了新的挑战，即如何有效利用多核心的处理器来实现效率的提升；

背景：多处理器架构

由于 CPU 寄存器的速度远远大于内存，因此在二者之间引入了一层高速缓存，来缓解速度差异过大导致的性能瓶颈；但单 CPU 的情况下，这个机制将很好的工作；但是当引入多个 CPU 内核，而这些内核又共享相同的高速缓存时，问题将变得微妙了起来，因为有可能 A 核的缓存被 B 核改动，导致 A 核再次访问缓存中的数据时，已经不存在了，A 核不得不再次到内存中读取。这个即是所谓的缓存一致性问题（持久性存储的场景也会面临缓存一致性问题，凡是使用缓存提高存储效率的场景，估计都不可避免会面临这个问题）；

同步问题

在引入了多 CPU 后，如果一段修改某个数据的代码，被分配到多个 CPU 上并发执行，将带来灾难性的问题，最终的计算数据常常跟预期的不同。这时需要引入互斥锁来保证数据更新操作的原子性才行；

缓存亲和度

某个进程交付给某个 CPU 内核执行后，在该 CPU 的寄存器中将维持很多状态，记录着存储在高速缓存中的数据。此时如果将进程切换交给另外一个 CPU 内核执行，由于新的 CPU 内核的寄存器并不知道原先高速缓存中保存的那些状态数据，因此不得不重新到内存中加载；因此，操作系统在调度进程的时候，最好考虑缓存亲和性，将进程仍交付之前的 CPU 进行处理；

如果多核 CPU 共享一份地址转换表的话，或许可以解决这个问题？

单队列调度

单队列多处理器调度（SQMS：Single Queue Multiprocessor Scheduling）实现起来比较简单，基本复用原来单处理器的调度策略即可，即将所有需要调度的工作，放入一个队列中，当某个 CPU 出现空闲时，就到队列中取走一个任务进行处理；但它的缺点有两个：

• 为了避免多个 CPU 修改同一份数据，需要给数据加锁，但是加锁会带来性能损失；
• 进程可能在不同的 CPU 之间切换，导致失去了缓存亲和性；

多队列调度

多队列多处理器调度（MQMS：Multi-Queue Multiprocessor Scheduling）让每个 CPU 专享一个自己的队列；当一个任务进来后，操作系统根据一定的规则（如随机挑选或者挑选短的队列）将任务放到某个 CPU 的队列中，接下来就跟单处理器的流程一样了；

MQMS 的好处是可以保证亲和性，也无须担心进程在 CPU 之间切换带来的性能开销；但它的缺点是有可能造成资源闲置。即某个 CPU 接到一个大任务导致很忙，而其他 CPU 都是一些小任务，很闲，即所谓的负载不均问题；

负载不均的一个解决办法是定期干预的思路，即当某个 CPU 队列开始变闲时，就将较忙的队列上面的任务迁移一个到较闲的队列中；

这种技术称为“工作窃取”，即闲置的 CPU 每隔一段时间就到繁忙的 CPU 那里窃取一个任务过来；但隔多久去窃取一次是个微妙的设定，因为时间太短太频繁的话，会带来较大的切换性能开销；如果时长太长的话，有可能导致负载不均；

Linux 的多处理器调度

Linux 社区就使用何种调度程序没有达成共识，共有三种常用方案：

• O(1)：多队列，基于优先级调度，类似 MLFQ；
• CFS：多队列，基于比例调度，类似步长调度；
• BFS：单队列，基于比例调度，采用 EEVEF 算法（最早最合适虚拟截止时间优先算法）；

9.抽象：地址空间

早期系统

最早的时候，操作系统没有提供任何内存方面的抽象，内存的头部存储着操作系统的系统（当时 OS 还在库时代），然后从某个地址之后存着程序的代码，内存中也只有一个程序，没有其他程序；

由于计算机很贵，需要很多人共用，而不是每人一台；因此 OS 开始需要支持多程序并行；这个时候的办法是引入磁盘的帮助，当需要切换程序的时候，就先将当前内存中的数据保存在磁盘里，然后加载另外一个程序；

由于磁盘很慢，上面的方法导致用户需要等待很久，接下来进一步的办法是将内存划分成多个段，每个程序使用其中一个段，然后切换程序的时候，不需要再跟磁盘打交道，只需要从这个段跳到另外一个段即可；

段的技术不错，不过它也引入了一个新的问题，即如何保护程序数据，避免被其他程序非法访问；

地址空间

为了解决隔离的问题，操作系统提供了一种虚拟地址空间的约定，在这个约定中，程序拥有巨大的全部内存空间，就像早期系统刚开始时那样，内存中只有一个程序在运行；同时操作系统还引入了地址翻译器，它会将当前进程指令中的虚拟地址，最终翻译为实际的物理地址，然后从该地址中取到数据；

10.插叙：内存操作 API

内存类型

C 程度有两种内存类型，一种是栈内存，它会编译器自动分配和回收；还有一种是堆内存，它由用户自行申请分配和自己回收（因此很容易忘了回收）；

调用函数申请分配堆内存后，函数一般会返回分配好的堆内存的地址，接下来一般需要将这个地址存在在栈中，以便供后续的代码使用；

问：使用 malloc 分配内存时，返回的地址，是在编译期间，由编译器给出的，还是在指令执行期间，由操作系统给出的？

答：猜测可以由编译器给出；执行期间，操作系统分配的是物理内存，返回的是物理地址，并且也只是将物理地址写入到页表当中完成映射而已，并不需要返回给应用程序；理论上编译器管理着整个虚拟地址空间；

malloc() 调用

malloc 用来申请在堆上分配内存

void *malloc(size_t size);
// 使用示例，一般不直接给 malloc 传递 size 字面值，而是通过 sizeof 表达式来获得 size 值，以避免出现错误
double *d = (double *)malloc(sizeof(double));

free() 调用

free 用来释放堆上的内存，只需将指针作为参数传递给它即可；

好奇：为什么 free 只需指针，无须 size_t 参数，即可知道应该回收多大的内存空间？

答：因为在分配该内存块时，在其头部有存储着一些额外的信息，其中一项记录着当前内存块的大小。这意味着实际分配的空间比申请时更大一点点；分配完了后返回的指令实际上并不是指向整个内存块的起始位置，而是在中间，即头部信息之后；

常见错误

忘了分配内存

// 错误示例
char *src = "hello";
char *dst; // 没有分配内存，因此该指针并没有指向堆上的空间，是个空指针
strcpy(dst, src);

// 正确做法
char *src = "hello";
char *dst = (char *) malloc(strlen(src) + 1);
strcpy(dst, src);

没有分配足够的内存

// 错误示例
char *src = "hello";
char *dst = (char *) malloc(strlen(src)); 
// 拷贝字符串时，会在末尾添加结束符，因此长度可能不够，取决于 strlen 返回的值是否包含结束符；
strcpy(dst, src); 
// 缓冲区溢出可能会成为安全漏洞来源

忘记初始化分配的内存

没有初始化的内存，并不意味着里面没有值，里面有时候会有前人留下的值，结果导致读取到的内容造成了程序错误

忘记释放内存

如果没有释放内存，则程序在长时间运行后，由于反复分配内存，最终有可能造成内存溢出；

在用完之前就释放内存

读取的时候很可能会出现预期之外的值；

反复释放内存

反复释放同一块的结果不可预期，通常会导致程序崩溃；

错误地调用 free()

本来想释放 A 指针指向的内存，结果传入了另外一个错误的值做为 free 的参数，结果意外释放了某处的内存，结果有可能导致程序崩溃；

由于手工分配内存很容易造成各种错误隐患，因此一般使用 purify 和 valgrind 等第三方工具来帮忙检查代码中可能存在的错误调用（有点像 lint 的去毛作用）；

底层操作系统支持

malloc 和 free 并不是系统调用，它们是库调用；但是它们本后的实现需要有系统调用，一般是 brk（参数为地址）和 sbrk（参数为增量）；这两个函数用来移动堆顶的指针；

除了 malloc 外，还有一个 mmap 调用可以用来分配内存，它的分配方式跟 malloc 有所不同，是在 swap 交换区中分配一个匿名的内存区域；

其他调用

calloc：分配堆内存后，会将其中的内容置 0；

realloc：分配一个比传入的数组更大的内存，并把数组内容拷贝到其中，再返回新内存的地址；

11.机制：地址转换

CPU 很快，但只有一个，所以它通过分时间段轮流使用的方法来实现共享，为了实现高性能，程序的指令直接送达 CPU 进行处理，操作系统仅在发生系统调用或时钟中断时，才介入处理，以帮忙程序完成一些受限功能或取回硬件的控制权；

内存是存储数据的设备，空间足够大，因此它通过分块使用的方法来实现共享（即空间共享）。在设计内存虚拟化时，也需要考虑高性能、安全可控和简单易用的设计目标；它的实现办法是引入地址转换，即抽象一套足够大的虚拟地址空间，由各个程序专用，这样一来就保证了程序在使用内存时的简单易用和安全可控的目标；之后操作系统通过虚拟地址和物理地址的映射表，来和实际的物理内存打交道，程序则完全不用管。

基址+界限机制

早期的地址转换使用基址加界限的机制（也叫动态重定位）来实现，CPU 里面增加基址和界限两个寄存器，实际的物理地址 = 虚拟物理地址 + 基址，之后再用界限寄存器的值进行核验，避免程序访问的地址越过了允许的边界；

硬件支持

为了实现地址转换，需要硬件提供一些内置功能的支持，包括：

• 区分运行模式：只有在内核模式下，才能运行特权指令；
• 基址&界限寄存器：用来存放相应的值；
• 能够转换地址并校验界限
• 提供修改基址&界限寄存器的指令：以便操作系统可以为每个进程初始化该值；
• 可在硬件中注册异常处理的特权指令的地址：以便操作系统可以告知 CPU，在发生异常后，应该去哪些地址加载异常处理指令；
• 提供异常触发机制：以便在进程试图调用特权指令或者访问越界的内存时，能够触发异常；

操作系统支持

为了实现地址转换，需要操作系统提供一些功能的支持，包括：

• 内存管理：为新进程分配内存、回收已结束进程的内存、更新可用内存表；
• 基址&界限管理：在切换进程时，正确的设置寄存器中的值；
• 异常处理：提供异常处理指令，以便当异常被触发时，CPU 可以进行调用；

虽然基址+界限的地址转换方式实现起来很简单，但是它也有很大的局限性，即对内存的利用效率比较低，每个进程内部都有大量的空闲内存（即所谓的内部碎片）；

原因在于应用程序有大有小，对内存有不同的需求，在操作系统在一开始的时候，并不知道应该给应用程序分配多少内存比较合理；

12.分段

如何解决基址&界限机制下的空间浪费问题？

分段：泛化的基址&界限

虚拟地址空间通常遵守惯例对内容进行分段，至少包括：代码段、堆、栈等三段；这三段占用的空间大小不同，代码段是固定大小的，而堆、栈是动态大小的；因此，为了避免普通基址界限机制下的空间浪费问题，可以做进一步细分，引入多个基址界限，分别用于对应不同的段；当需要对某段内的虚拟地址进行转换时，只要先计算出该地址相对于段起始地址的偏移量，之后加上段基址在映射表中的物理地址，即是它在物理内存中的真实地址（当然，还需要使用界限值检查一下，如果超过了范围，就会引发段错误 segmentation fault）；

接下来的问题是，当 CPU 拿到一个虚拟地址时，如何知道它属于哪个段？因为只有知道属于哪个段，并且知道该段的起始地址，才有办法计算偏移量

如何知道引用哪个段

有两种方式可以用来判断虚拟地址属于哪个段

显式的方法

使用虚拟地址的头两位来判断，例如 00 代表代码段，01 代表堆段，10 代表栈段；虚拟地址拿掉头两位，剩下的即是地址在该段内的偏移量，可以直接和界限比较大小来检验是否越界，并且也可以直接加上基址，获得实际的物理内存地址；

隐式的方法

通过虚拟地址的来源来实现，当地址来源于程序计数器时，意味着这个地址是代码段中的地址；当地址是基于栈指针或者堆指针的偏移量计算出来的时候，意味着这个地址是栈地址或者堆地址；

如何处理栈的反向增长

其实也很简单，当知道了该地址是一个栈地址后，只需要减去栈的起始地址，即可以得到一个负数的偏移量，然后加上基址，即可以得到实际的物理内存地址；

说明栈空间在物理内存中也是反向增长的；

支持共享

不同的进程之间，总是难免会使用到一些相同的数据，例如共享库，如果每个进程都存储一份，显然太浪费空间了。通过引入共享段，可以提高内存的使用效率；

实现办法就是给段地址增加几个位（即保护位），用来标记关于该段是否允许共享、是否可执行等一些额外的信息；如此一来，也给 CPU 增加了一些额外的工作，除了做前述检查虚拟地址是否越界外，还需要检查一下当前指令是否跟标记位有冲突，例如指令尝试向只读的段写入数据，或者尝试运行非执行段中的指令等；

段的颗粒度

按代码、栈、堆的方式进行分段，是一种比较粗颗粒度的分段；在早期有些系统的设计中，曾经尝试过更加细颗粒度的分段，当时的目的是为了让内存的使用更加高效，当然，分段越多，意味着需要硬件的支持才可行。

操作系统支持

虽然分段的方法减少了内存的浪费，提高了使用效率；但是随着进程的不断创建和销毁，物理内存上将存在着越来越来的内存碎片，这些碎片加起来很大，但是它们却是不连续的。这有可能造成明明还有足够多的空闲内存，但却无法满足新建进程的连续性要求。这时候操作系统需要引入一个算法来管理这些碎片，一方面解决如何为新进程找到最合适的空闲内存片段，另一方面负责整理碎片，通过移动已分配内存，让整个内存使用变得紧凑，大部分的非连续碎片能够挨到一起，形成整段的连续内存，从而减少碎片的存在。

管理内存的算法有很多，成百上千，例如最佳匹配、最差匹配、首次匹配等，不过它们只能是尽量减少碎片的产生，暂时还无法完全消除它（因为那意味着要付出其他方面的代价）；

虽然粗颗粒度段的方式部分解决了内存使用效率问题，但其实它并不能完全解决，因为对堆的高效使用，依赖于进程本身在虚拟地址空间中的管理算法。有可能某个进程所用的算法并不高效，导致用的堆空间很多，但其实很稀疏，这无形中就意味着物理空间的浪费

13.空闲空间管理

待解决问题：如何让碎片最小化？

假设

为了方便讨论内存管理算法的实现，先做一些简单的基本假设：

• 已分配内存在生命周期内大小不变；
• 内存分配后就不再被移动；
• 已分配内存是一块连续的区域；

底层机制

分割与合并

当申请分配的内存比某个空闲块小时，内存分配程序就会对空闲块进行分割；

当释放某个已分配的内存块时，内存分配程序会尝试合并，即先检查一下该内存块前后的内存块是否是空闲的，如果是的话，就跟它们合并成一个更大的空闲内存块；

记录已分配空间的大小

当用户在调用 malloc 分配一块新的内存块时，实际分配的大小并不是用户传递的 size_t 参数，而是比它还要大上一点点，因为内存分配程序需要一个额外的头部空间来存储关于当前内存块的一些元信息，例如 size_t 和 magic number；当后续释放该内存块时，这个头部信息将派上用场。它使得用户在调用 free 函数释放内存时，只须传入指针，而无须传入 size；free 会自动根据指针值倒推（减去 header_t）得到真正的起始位置和实际大小；

空闲链表

空闲链表是一种数据结构，它保存着哪些内存块是空闲的信息，每个内存块在链表中用一个 node 节点来表示，多个 node 相互连接就形成了空闲链表；每个 node 有两个属性，一个是 size，保存着当前内存的大小信息；一个是指向下一个 node 的指针值；

由于空闲链表用来管理空闲内存，而它自己又是需要内存存储的，因此它的每个节点信息实际是保存在每个空闲内存块的头部里面；

堆的增长

大多数内存分配程序在开始只是通过系统调用向操作系统申请一块很小的堆，然后随着时间的推进，如果当前已分配的堆确实已经不够用了（做了各种努力之后，例如已经紧凑过了），分配程序会再次发起系统调用，向操作申请更多的堆空间；操作系统在收到请求后，会分配一块空闲的物理内存页，并将该物理内存的地址，映射到进程的虚拟地址空间中；之后进程就有了更大的堆可以使用了；

问：如果进程的堆是分两次单独申请的，如果操作系统前后给的两个物理空闲页是不连续的，接下来在进行地址转换时，要如何处理？

答：操作系统使用一个页表来记录映射关系，在做地址转换时，查询该页表，得到正确的物理地址；

问：此处的分配程序，貌似其实是编译器？因为貌似没必要在程序运行期间，去找一个运行时库来管理已分配的内存？

基本策略

最佳匹配

遍历整个空闲链表，找到和申请大小最接近的空闲内存块；

优点：最佳匹配，空间浪费最小化；

缺点：遍历比较费时，因此分配时间较久；

最差匹配

遍历整个空闲链表，找到最大的块，分割它；

优点：一无是处，只有初衷是好的（它的初衷是想让可用的空闲块尽量的大）；

缺点：遍历费时，碎片还很多；

首次匹配

在找到第一个大小满足要求的块后，就不再往下找了；

优点：快，无须遍历；

缺点：链表头部碎片特别多，后续查找的时间开始变长

下次匹配

比其他策略多维护一个字段，用来记录上次命中后的位置，然后下一次从那里接着往后找；

优点：性能与首次匹配接近，但碎片更平均化，不会集中在头部；

其他方式

分离空闲链表

理论上用户每次申请的内存块的大小是不可预知的。但是由于局部性原理，代码对内存空间的使用不可避免存在某些规律，例如某种大小的内存块被申请的次数最多；因此，可以通过单独增加一个专门维护固定大小的块的链表；只要申请的内存块大小等于某个固定值，就交给这个专门的链表来分配；由于每个内存块的大小都是一样的，而且也无须合并，因此块的分配和释放，都可以在常数时间内完成，效率非常高；同时空间也不怎么浪费；

感觉这里开始有点分页的思想了！

沿着这个思路继续往下开展，可以统计出那些最常用的块的大小，通过增加维护跟该大小一致的链表，来进一步提高内存使用效率；

伙伴系统

伙伴系统将整个内存想象成一个巨大的 2 的 N 次方的空间；每当有一个新的分配请求时，就将空间反复进行二分，直到再次二分便无法满足请求时为止；

它的好处在于，当某个块被释放时，它马上可以检查旁边同等大小的伙伴是否空闲，如果空闲，马上就可以进行合并；合并后以后，再次检查伙伴，以此类推；因此它的合并是非常迅速的；而正因为了合并效率高，使得空间的外部碎片变少；但是内部碎片会多一些（因为不是每个请求都刚好是 2 的幂）；

其他想法

有些策略的空间利用率高，但付出的代价是查找比较慢；为了进一步压榨提升性能，人们不惜通过牺牲简单性引入复杂性来换取性能，包括使用平衡二叉树、伸展树和偏序树等算法；

事实上并不存在一个完美而万能的分配程序，因为计算机被用于处理非常多完全不同类型的任务，每种任务都有其各自的业务特点；当对业务特点了解得越多的时候，才有可能选用越合适的分配策略，以大幅度的提高性能；

14.分页：简介

操作系统有两种管理物理内存的方法：

• 参照虚拟内存的方法，将物理内存进行不同长度的分段；缺点：随着时间的推移，很容易形成碎片化，分配工作变得越来越困难；
• 按固定的长度单位，将物理内存分成 N 个单元（每个单元称为一个页）；优点：内存分配比较简单和灵活，因此每个虚拟空间中的页，刚好也映射物理内存中的一个页（通过页表来实现映射）；

由于内存映射是以页为单位的，因此在进行地理转换时，只需转换头部的页号即可，页内的偏移地址并不需要转换；

页表存储在哪里

页表还是挺大的，例如对于32位的地址空间，每个页设置为 4 KB，因此需要单个页占用了 12 个位，剩下的 20 个位即是页号；每个页面条目假设占用 4 个字节，单个进程的页表大小为 2^20 * 4 字节，相当于 4 MB；

如果操作系统当前运行着 100 个进程，则总共要使用 400 MB 的物理内存空间来保存页表；这么大的存储量，显然无法保存在 CPU 中，因此通常是将其保存在物理内存中；

分页的代价是引入页表，额外消耗了一些存储空间，但换来了简单性和灵活性，也避免了碎片的问题；而在分段的机制中，是不需要页表的；同时分页也牺牲了一点性能，因为现在地址转换工作增加查询页表的环节；

页表中究竟有什么

简化的来看，可以将页表当做一个巨大的数组，以虚拟页号做为索引，来访问其中的元素，元素包含的值除了物理页号外，还有一些额外的位，这些位分别起到不同的控制作用，包括：

• 有效位：表示是否有数据；
• 存在位：表示是否被交换到磁盘；
• 保护位：表示操作权限，例如只读、可写、可执行；
• 参考位：表示是否被频繁访问，如果是，则应该尽量保存在内存中，避免交换到磁盘；
• 脏位：表示页面放到内存中了后，是否有被修改过；
• 其他一些缓存用的位：如 PWT, PCD, PAT, G 等；

分页的性能代价

虽然页表的设计让地址转换变得简单了起来，但是以牺牲部分性能为代价的；因为每一次内存引用，都需要做如下的地址转换计算：

• 从虚拟地址提取虚拟页号；
• 根据页表基址寄存器存储的基址，以虚拟页号为索引，获得物理页号；
• 根据物理页号从物理内存中读取数据；

CPU 每执行一条指令之前，都需要先从内存中读取指令，之后才知道指令要执行的内容；而指令中可能含有从内存中读取数据或者更新数据的操作，此时 CPU 将需要再做一次内存的操作，以便得到数据或者写入数据；

CPU 在程序计数器中存储着下一条指令的地址，在执行指令前，先从该地址将指令加载到 CPU 中，然后解读指令，并进行相关的操作；

除了性能外，分页的另外一个代价是占据较大的物理内存空间；

线性的单级页表确实比较大，但貌似可以通过非线性的多级页表来解决空间占用过大的问题？

15.分页：快速地址转换 TLB

分页固然带来了映射的极大简化，但是如果每执行一条指令，都需要读取物理内存中的页表来作地址转换，这将付出巨大的性能代价，为了弥补这个缺点，一般通过给地址转换器引入缓存来解决，利用局部性原理，减少对物理内存中页表的访问次数，提高地址转换速度；

TLB 的基本算法

在得到一个虚拟地址后，地址转换器先检查缓存中是否已经有映射条目，如果有则缓存命中，马上可以读取缓存，得到物理页号；如果没有，则需要访问一次物理内存中的页表，将条目写入缓存，之后再重新执行转换（第二次执行可以触发缓存命中）

TLB 全称：Translation Lookaside Buffer

单页的尺寸越大，则缓存命中率就会越高；因为最小加载单位是一个页，如果这个页足够大，则接下来要访问的数据，很可能都在这个页中，一般单页的典型大小为 4KB；

如何处理 TLB 未命中

有两种处理办法：

• 硬件办法：由 CPU 自行处理；这种办法会增加 CPU 设计的复杂性，因为 CPU 需要执行一些自己的代码（指令）并知道页表在物理内存中的位置和格式，因此需要设计较为复杂的指令集 CISC；
• 软件办法：由 OS 来处理；这种办法增加了灵活性，OS 可以使用任意数据结构，不像 CPU 一出厂就写死了；另外也让 CPU 的设计变简单了，只需要设计较简单的指令集，即 RISC；

随着 CPU 芯片集成的电路变得越来越大，两种指令集的差异消失了，复杂指令集现在运行起来跟简单指令集一样快；

TLB 的内容

TLB 是缓存，因此也可以看做是一个数组，这些数组的元素是无序的，每一个元素是一条 TLB 记录，记录中保存着某个虚拟地址和物理地址的映射；由于它们是无序的，因此每条记录中需要同时保存虚拟页号 VPN 和物理页号 PFN，不然仅有一堆物理页号则完全不知道它们属于哪个虚拟页号的了；

除了 VPN 和 PFN 外，一条 TLB 记录中还有几个额外的位来存储一些额外的信息，例如：

• 有效位：用来判断当前记录中的映射信息是否有效，这样在切换进程时，只需将有效位全部设置为无效即可，无需删除整条记录；这样就可以避免当前进程使用上一个进程的映射了（重置缓存中所有条目的有效位也是一个不小的工作，因此还有另外一种办法是引入地址空间标识符，来判断当前进程是否匹配）；
• 保护位：用来标记该页的内容的访问权限，例如是只读、可写，还是可执行等；

另外还有一些其他位如地址空间标识符、脏位等；

上下文切换时 TLB 的处理

一种方案是直接重置所有有效位为 0，这种方法可以确保新进程不会访问旧进程的映射，但是它的缺点是性能开销很大；解决的办法是通过引入地址空间标识符（一般是8个位），来代表不同的进程，这样在切换时，就不需要重置了，但是在搜索时，需要增加对这个标识符的判断，只有标识符 和 VPN 都匹配时，才是缓存命中；

TLB 替换策略

有两种可用策略：

• 最小引用策略：即将最近最少使用的 TLB 换出；优点是尽量保持高命中率；缺点是偶尔会出现极端情况；
• 随机策略：随便选择一项换出；不会出现极端情况，但整体命中率有所降低；

实际系统的 TLB 表项

此处是 MIPS R4000 操作系统来举例，在这个操作系统的设计中，使用软件来管理 TLB；因此在遇到缓存没有命中时，需要用到操作系统提供的关于更新 TLB 的一些指令；

该系统单个 TLB 记录有 64 个位，其中：

• 有 19 位用来存 VPN（正常是20位，但因为地址空间有一半被预留给内核，因此实际的用户空间只用 19 位即可表示）；
• 有 24 位用来存 PFN（因为可以支持最大 2^24 的地址空间，约为 64GB 的物理内存）；
• 有 1 个 G 位用来表示当前的记录是否是全局的，如果是的话，则不用检查地址空间标识符；
• 有 8 位用来存储地址空间标识符；
• 有 3 位用来表示一致性；
• 有 1 个 D 位（脏位）用来表示记录是否被改写过；
• 有 1 个 V 位（有效位）用来表示当前记录的内容是否有效；
• 剩下的都是一些暂未使用的位；

MIPS 的 TLB 一般总共有 32 个记录或者 64 个记录；大多数留给用户进程使用，但它有一个寄存器，可以用来设置有多少个记录需要预留给内核使用；在这些预留的记录中的映射，用来保存操作系统自己在某些时刻下要用的代码和数据；

16.分布：较小的表

简单数组结构的单级线性页表带来的一个问题是占用空间过大，因此需要寻找新的办法，例如通过以时间换空间的方法，来解决内存占用过大的问题。

方法一：更大的页

由于地址长度是固定的，因此如果单页变大，则页号的范围变小，因此页表的记录数也随之变少，这样页表就变小了；例如对于 32 位地址，单页设计为 12 位，此时单页的大小为 2^12 字节，约为 4KB，页表条目需要 20 位，因此有 2^20 个条目，每个条目有 4 字节，总共需要 4MB；如果将单页设计为 14 位，大小变成 16 KB，则页表条目只需 2^18 个，少了 4 倍，变成 1MB；

结果看上去不错，占用空间只剩下 1MB 了，而且还提高了缓存命中率；但其实这是以增加单页的内部碎片为代价的，即每次为进程分配内存时，最小单位都是 16KB，但它实际上可能常常用不了这么多，因此造成了很多内部空间浪费；

更大的单页有一个额外的好处是可以提高 TLB 的命中率，减少 TLB 记录数；这对于某些特定的应用，例如数据库管理程序很有必要，因为数据库中的数据是挨在一起的一个整体，而且经常频繁的随机访问，通过大单页，例如单页 4MB，可以有效提高缓存命中率，减轻 TLB 的压力；

方法二：分段+分页

由于虚拟地址空间很大，但实际的进程实际的地址，只占里面很小很小的一部分，因此如果页表为整个虚拟地址空间都提供映射记录，显然绝大部分记录都是空的，存在巨大的空间浪费；所以，可以通过引入分段，为虚拟地址空间中的不同段，提供不同的页表，而不再是一个页表；

由于分段在原先的虚拟内存设计中就已经天然存在，因此可以提前已经存在的段基址寄存器（包括代码段、堆段和栈段），让它们的值指向对应段的页表的物理内存地址，即可以访问每个段各自的页表；

简单的分段其实并不能带来页表占用空间变小的好处，因为每个段也是很大的，关键点在于引入每个段的界限；当一个段拥有界限后，它不再是很大了，而是有限的大（通常都很小）；界限的存在是通过界限寄存器来实现的，通过在界限寄存器中保存一个段大小的值，我们就拥有了有限大小的段；然后页表的记录数，也只需跟段的大小匹配即可，这样页表就变得很小了；

分段+分页的方法其实是要付出一定的性能代价的，因为段的大小是动态可变的，这意味相应段的页表也变成了动态的；因为当原分配给页表的空间不够用时，就需要为页表分配新的空间并迁移它；

方法三：多级页表

虚拟地址空间也是很稀疏的，通过引入页表，让它在物理内存中的存放变得紧凑和灵活了起来；同样的思想也可以运用在页表本身的存储上面，通过引入页目录的结构（作用跟页表类似），页表不再被线性存储，而是映射存储；这个方法的优点是占用的空间大大减少了，只按最小单位（页）来存储，没有浪费；缺点是需要付出一定的性能代价，因为页目录本身也是需要存储在内存中，在得到最终的 PFN 前，需要增加一次或多次物理内存访问（取决于页表分成几级）；

就像内存虚拟化技术一样，多级页表相当于将页表虚拟化了；而且还不只是一级的虚拟化，为了最小化内存占用，还可以丧心病狂的使用多级虚拟化；

方法四：反向页表

反向页表的思路更加极端，在多级页表中，每个进程拥有自己的页表，而反向页表，则是所有进程共用一个页表；该页表的单个页表项中，包括三方面的信息：

• 地址空间标识符：用来记录当前记录属于哪个进程；
• VPN 虚拟页号
• PFN 物理页号

然后使用 HASH 散列表结构来建立映射和存储；类似于以字典键值对的方式来实现映射和转换；优点是极端节省空间；缺点是性能将有所下降，因为随着字典变大，需要进行迁移，分配更大的空间来容纳映射关系；

方法五：交换到磁盘

这个方法倒是一劳永逸的节省空间，但是性能最差；

17.物理内存不足：机制

虽然现在的物理内存相对早期已经大了，但是应用程序运行时所占用的内存也比过去变得更大；当同时运行的应用程序足够多时，不可避免会遇到物理内存不足的情况，此时需要有一个机制，能够将部分物理内存转移到其他存储空间，等需要的时候，再转回来，以避免物理内存不足的窘境；

交换空间

交换空间 swap space 机制是现代系统使用的一种解决方案；通过将部分暂时不用的物理内存页，交换到硬盘中，来缓解内存不足的问题；

进程运行起来后，代码已经被加载到内存；如果此时运行下一个程序时，发现内存不足，此时有两种解决方案，一是将上一个程序的代码转移到交换空间中；另一个是不交换，等后续要用的时候，再重新从硬盘中加载，因为代码本来就是从硬盘中加载过来的；

存在位

为了能够实现交换空间机制，需要在页表中额外安排一个位，用来表示当前条目所代表的物理内存页，是否真的在物理内存中，还是在硬盘上，这个位称为有效位；

当试图访问一个存在位为 0 的物理页时，会触发页错误，然后操作系统会接管并处理这个错误，将数据从硬盘加载到内存中，然后重新执行指令；

页不存在只是页错误的一种，还有其他情况也会触发页错误，例如非法访问；

页错误

当数据存储在物理内存页中的时候，PFN 是有用的，但是如果该页被交换到了硬盘中，则 PFN 就没有用了（失效了），此时只需通过存在位，即可以触发页错误；因此，无效的 PFN 所占用的位，刚好可以用来存储数据在硬盘上面的位置索引；操作系统可以根据该索引，从交换空间中，将数据加载回内存；然后更新页表中的 PTE 条目的 PFN 为最新值，并更新 TLB 记录（硬盘管理 TLB 的系统估计不更新，只有软件管理的才会），之后重试指令；

交换策略

当从硬盘中将页数据交换回物理内存时，有可能物理内存已经是满的，此时需要将部分页换出到硬盘上，如果选择待换出的内存页，需要使用一个好的交换策略，以避免给程序运行带来巨大的性能损失；

页错误处理

当页错误被触发时，操作系统从 PTE 中获得硬盘地址，然后在物理内存中寻找到空闲页，访问硬盘读取页数据，并加载数据到空闲页中，将该空闲页的页号更新到 PTE 中；如果没有找到空闲页，则会触发页交换，将物理内存中已有的部分页面，交换到硬盘上；

什么时候交换

操作系统会设置两条线，一条是低水位警戒线，当物理内存中可用的空闲页低该警戒线时，就会触发页交换守护进程（page daemon 或 swap daemon）；另一条是高水位安全线；交换守护进程的交换工作会一直持续到当前可用的内存页到达安全线后停止下来，然后进入休眠状态，直到下次被唤醒；

由于硬盘的写入速度很慢，交换进程会凑齐足够数据的待交换页后，再一次性交给硬盘处理，从而提高硬盘的访问性能；

18.物理内存不足：策略

当物理内存满了时，选择哪些页面，将它们转移到交换空间，是一个需要好好思考的问题；由于硬盘的访问速度非常慢，因此如有可能，应该尽量避免出现访问硬盘的情况，至少要让概率尽可能小；

理想的替换策略是将未来最不可能用到的页替换出来，这样命中率是最优的，缺点是这个策略基本无法实现；因为在替换的时候，我们无法开启上帝视角，无法判断哪个页是将来最不可能会用到的；

简单策略：FIFO

先进先出是最简单的策略，缺点是命中率比较低；

随机策略：Random

优点：实现简单；

缺点：性能看运气；

基于历史：LRU

LRU 是 Least Recently Used 的缩写，表示最少最近使用；

这个策略利用了程序运行时常常表现出来的局部性特征，即最近访问的数据，也可能在接下来再次被访问；

性能视场景而定

不同的业务场景将决定不同策略的性能表现，虽然 LRU 在多数情况下表现的更好，但它也有一些应付不了的极端情况，此时有可能随机策略反而表现得更好；

LRU 的实现

想要实现 LRU 是有难度的，因为它需要额外记录每个内存页最近被引用的时间，这样才能判断出谁是最少最近使用的；但随着物理内存变大，页表条目变多，通过全局扫描查找最少最近使用条目，将需要付出巨大的时间代价，有可能得不偿失；

近似 LRU

由于完美的 LRU 实现代价很大，因此需要寻找一个近似的替换算法，这样既可以避免性能开销，又可能达到类似的命中率效果；

这类型的近似算法有很多，它们大体的思路也类似，即通过增加一个使用位，来标示当前页是否最近被使用，初始默认所有页的使用位都为 0；使用某个指针寄存器，让它随机批向一个页；当某个页被读写的时候，就将其使用位设置为 1，表示最近该页有过读写的动作；当需要进行页替换时，操作系统通过指针往下遍历每个页，如果某页的使用位为 1，则将其设置为 0，然后继续往下查找，当找到第一个“使用位”非 0 的页时就进行替换；

除了使用遍历查找外，还可以考虑使用随机查找，效果差不多；

考虑脏页

由于与硬盘通信的开销很大，一般会将多个修改后的页进行批量化处理，集中一次性的写入，而不是改一个写一个；因此在替换内存页的时候，有可能会遇到该页暂未写入硬盘的情况；因此，通过增加一个修改位（脏页位）来对已修改未写入的页进行标识，不替换该页，而是尽量替换干净页；

其他读写策略

除了页替换策略外，虚拟内存还同时使用一些其他的策略来提高内存管理的效率，例如：

• 按需读取策略：只在页被指令访问时，才将页从硬盘中加载到内存中；
• 预读取策略：只在有很大把握某个页接下将被访问时，提前将页从硬盘中加载到内存；
• 批量写入策略：集中将多个内存页的修改，一次性写入硬盘，而不是改一个就马上写入；

抖动

当应用程序对某个巨大的数据结构进行计算时，如果该数据结构占用的内存超过了物理内存的可能容量，那么在计算过程中，部分数据将被交换到硬盘中，然后又很快需要被加载回来，同时又换出去一部分，反复循环，导致 CPU 都将时间花费在了触发页错误和加载数据过程中，完全没有办法进行实际的计算，这种情况称为内存的抖动；

19.VAX/VMS 虚拟内存系统

操作系统的部分功能需要硬件的配合，才有可能高效稳定的实现，但是市场上的硬件种类多种多样，而且不同硬件的开发人员水平参差不齐，不可避免存在缺陷，因此操作系统的开发者将不可避免需要解决通用性的问题，即如何让同一个操作系统，在不同的硬件上面，都可以稳定的运行。

操作系统的存储

操作系统本身也需要物理内存来存储自己的代码和数据，它有三种实现方式：

• 直接存储在物理内存中（缺点：无法实现页交换，因为没有虚拟内存这一层）
• 有自己的完整虚拟内存，像是另外一个单独的应用程序（缺点：不方便和应用程序之间的数据通信）
• 做为应用程序的一段分，使用单独的段（内核段）来映射它（目前为大多数系统所采用）

问：好奇是内核否有自己的单独页表，还是与应用程序共用一张页表，因为内核段也有自己的堆，意味着有动态的数据需要存储？如果是共用页表的话，每张页表都有一些重复的项目，有一定的空间浪费；

答：实际上很可能是使用分段+分页的机制，即总共有三对基址寄存器和界限寄存器（总共6个）；内核段有自己的基址和界限寄存器，而且还是每个应用共用的；在进行应用程序切换时，只需要改变 P0 和 P1 寄存器，无须改变 S 寄存器；

页替换

问：在进行页替换的时候，LRU 策略是一种全局的策略，它只会从当前页表的所有条目中，挑出最少最近使用的进行替换，而无视这些页表本身是否占用了过大的内存；因此，需要设计一种机制，对单个进程的可用内存上限进行控制；

FIFO

解决方法是为每个进程设置一个可用内存的上限（由于内存是分页的，相当于有了一个可用的页数上限）；将进程的所有页都放在一个 FIFO 列表中，当列表的长度达到上限时，就基于先进先出的原则，将最早写入的页从 FIFO 列表中清除，并替换到硬盘上的交换空间中；

如果可用上限值比较小，立即执行的 FIFO 策略，将有可能使得进程的性能下降，因为其数据频繁的在内存和硬盘之间交换；为了提高性能，VMS 系统额外增加两个全局的列表，一个用来存放干净的页，一个用来存放脏页；

当某个进程 P 的 FIFO 列表满了时，踢出的页并不会马上被交换到硬盘中，则是先放入干净页或者脏页（取决于脏位的值）的末尾，此时进程 P 的性能并没有受到任何的影响，因为它所有的页仍然在内存中；

当进程 P 执行结束，切换到进程 Q 时，如果进程 Q 需要用到一个空闲页来存储数据时，系统就从干净列表的头部取出一个页，将其替换到硬盘上，然后交给进程 Q 使用；

如果两个全局列表的长度足够大，这种策略的性能将非常接近于 LRU 策略；这个策略本质上利用了局部性的原理，将各个进程要换出的干净页先集中放在一起，然后按时间顺序，先进先出的替换；这样避免了替换最近的页，而是替换最远的；

批量处理

上述增加全局脏页列表的做法，还有另外一个好处，即由于写入硬盘的性能代价比较大，因为可以等到脏列表满了后，再一次性的批量写入，这样就可以尽量减少写入的次数；写入完了后，原来的脏页就变成了干净页了；

VMS 的页表条目中，并没有额外的使用位来标记条目所代表的页，是否最近被引用过；它使用了另外一个巧妙的机制，来达到相同的效果，即使用保护位；初始化的时候，所有条目的保护位先置为不可访问；因为操作系统在访问一个页之前，即判断它的权限，如果可访问，则将保护位设置为只读或可写；这样，当需要进行页替换时，操作系统可以通过查看保护位是否被重置过，如果有，表示最近有被使用；如果没有，表示未被使用；

问：将应用程序从硬盘中加载到内存中的时候，到底发生了什么？

答：操作系统需要做如下事项：

• 在进程表中增加一个条目，并写入一些关于进程的元信息
• 初始化一个新的页表（此处假设是单个线性页表），在进程条目中记录该页表在物理内存中的位置
• 寻找空闲页，将代码和数据载入空闲页中，将空闲页的 PFN 写入页表的相应位置；

惰性技巧

按需置零

因为物理内存是在多个应用程序间共用的，当某个物理内存页被 A 进程释放后，随后该页可能会被进程 B 使用，但此时页上面仍然留有 A 进程的数据，因此需要避免这些数据被 B 访问，这样才能确保安全性；比较土的办法是在该页分配给 B 使用时，就将该页上面的全部数据置 0，这样做可以确保绝对安全，但是性能代价很大，因为有可能 B 只用到该页的一小部分空间，大部分空间并不使用；

通过引入按需置零策略，可以减少性能开销；在分配页给 B 时，操作系统只是先通过保留位将该页标记为按需置零，并不真正的去置零；然后在真的要读写数据时，在检查权限的时候，操作系统顺便检查按需置零位，如果为真，则再做一下置零的工作；

写时复制

当某页数据需要从进程 A 复制到进程 B 时，操作系统一开始并没有直接的复制数据，而只是将该页的物理页号写入进程 B 页表中，这样两个进程不同的 VPN 映射到了相同的 PFN，并在进程 B 中将该页标记为只读；后续如果进程 B 需要对该页进行写入操作，操作系统发现该页为已读，此时才会触发真正分配新页和复制工作；

这个技术在 FORK 的时候特别有用，减少了极大的性能开销；另外在多个进程之间使用共享库时也有用；

20.并发：介绍

通常情况下，进程只面对一个使用者，仅有单一的任务目标，完成一系列指定的操作并得到结果；但是有些情况下，进程可能要面对多个使用者，例如运行在服务器上的进程，为成千上万的访问者提供服务；这些访问者发起的服务请求，对进程来说形成了一种并发的挑战；为了应对这个挑战，引入了线程的概念；

每个线程拥有自己一个独立的栈，不同线程之间的栈不会相互干扰；但它们共用进程的整个地址空间；因此，在切换线程时，并不需要更改页表的寄存器，只需更新程序计数器，以及其它用于存储计算结果的寄存器；

进程切换时，需要保存当前进程的状态，使用进程控制块（Process Control Block，PCB）来保存；

线程切换时，使用原理类似的线程控制块（Thread Control Block，TCB）来保存；

当创建一个线程时，需要传递待执行的例程（即函数）给它，至于这个例程什么时候被 CPU 安排执行，则是不可控的，它有可能比主程序的下一行代码早，也可能比它晚，一切取决于操作系统的调度程序当时心情怎么样。

并发场景

• 修改全局变量：两个线程访问修改彼此共享的变量；
• 依赖：一个线程的执行需要等待另外一个线程的结束；

21.插叙：线程 API

创建与完成

问题：操作系统应该提供哪些创建线程的接口，并当它们简单易用？

在 C 中，可以通过 POSIX 库的 phread_create 函数来创建线程，并通过 phread_join 函数来等待它的返回；

如果每创建一个线程后，马上调用 join 函数等待它的返回，这样完全没有意义，完全实现不了并发，其使用效果跟普通的函数调用没有任何区别；因此重点在于在等于线程返回前，有机会创建更多的线程，这样才有可能实现并发的效果；

有些多线程的 Web 服务器会创建一个主线程，并根据需要创建大量的工作线程；当主线程收到用户的请求后，会将该请求转发给某个刚创建好的工作线程，并且也不需要等待它的返回，这样一来，主线程本身就实现了并发的处理，即它在理论上可以接收并处理海量的请求（具体的数量上限取决于硬件的能力）

锁

当线程需要对共享的全局变量进行修改时，不可能避免需要处理并发的问题；Pthread 库通过引入锁机制来实现；原理也非常简单，先初始化一个锁类型的变量，当需要执行临界代码时（即将改变共享变量的代码），调用 phread_mutex_lock 来尝试获取锁；

• 如果能够得到，就继续往下执行代码，并在执行完毕后调用 pthread_mutex_unlock 函数来释放锁，以便让其他等待中的线程可以获取到锁；
• 如果不能得到，就进入阻塞等待的状态，直到获取到锁为止；

Pthread 库中另外还有其他与锁相关的函数，包括：

• pthread_mutex_trylock：用来尝试获取锁，如果得不到，直接返回失败，不等待；
• pthread_mutex_timelock：用来尝试获取锁，并在给定的时间内等待，如果时间到期后仍然得不到，返回失败；

用途：锁的机制可以用来解决多个线程修改共享的全局变量场景；

条件变量

用途：条件变量可以用来解决线程之间的依赖等待关系；仅靠条件变量性能不够好，结合锁的使用，有助于提高性能，避免等待线程出现自旋；假设有两个线程，其中 B 需要等待 A 的结果；当 B 获取不到锁时，就进入睡眠；如果 B 能够获取到锁，但条件变量未满足，则 B 就释放锁，然后进入睡眠；A 则负责获取锁，并在计算完成后，改变条件变量，然后释放锁，并唤醒 B；

假设某个线程 A 的执行，依赖于另外一个线程 B 的完成，则 B 在完成后，需要释放某种信号，以便 A 可以知悉状态，并开始执行自己的代码；

最简单的办法是引入一个标记变量（或叫状态变量），A 线程定时检查标记变量是否发生了变化，如果已经变化了，就开始执行自己的代码；B 线程负责在完成自己的工作后，改变标记变量的值，以便传递信号通知 A 线程；

但是上述这种方法的性能很不好，因为 A 线程需要循环的检查标记变量，可能在大部分时间内，其检查工作都是无用的；为了解决性能，可以通过引入条件变量和锁变量，利用条件变量的特殊性来降低性能损失；其原理是先调用函数让需要等待的线程 A 进入睡眠状态，然后 B 线程通过改变条件变量来唤醒它；这样 A 线程在等待期间就不需要反复检查前一种方法中的标记变量了；这种方法更加安全的原因在于 A、B 线程通过引入锁保证了执行的先后顺序；

• pthread_mutex_wait(&cond, &lock)：该函数接收一个条件变量和一个锁变量作为参数；当调用该函数时，它会让当前线程 A 进入睡眠状态，并释放锁；
• pthread_mutex_signal(&cond)：在线程 B 中，在获得 &lock 指向的锁后，开始执行自己的代码，并在执行完毕后，调用 pthread_mutex_signal 函数，它会更改 &cond 变量，以便发出信号唤醒处于睡眠状态的 A 线程；之后线程 B 还需要调用 pthread_mutex_unlock 函数释放锁，以便线程 A 在唤醒后可以获得锁

&cond 可以用来唤醒另外一个进程，但为了保险起见，书中的例子还额外引入了一个 ready 变量，来确保 B 线程的代码真正完成了指定的操作，以便防止 A 线程被意外唤醒的情况；相关于有了双保险的机制；

22. 锁

表面上看，锁好像是一个类似状态变量的东西，但其实它是一个结构，里面除了保存状态值外，还保存着当前持有它的线程信息，只是这些信息通常对使用者是隐藏的；

问：锁为程序员提供了一个很方便的实现线程有序并发的工具，但在操作系统和硬件层面，它们需要如何实现锁的机制？

答：需要 CPU 提供一些原子性的指令，这些指令可以用来修改设置变量，从而实现锁的机制；仅由软件实现的锁机制是不可靠的，因为完全不知道 CPU 的时钟中断何时会发生，而一旦发生，将使得处理逻辑失效；

评价锁

锁的实现有多种方案，有三个维度可以用来评价实现方案的优劣：

• 有效性：能够真的实现互斥的效果；
• 公平性：不至于有些等待线程一直无法抢到锁，导致最终饿死了；
• 性能：引入锁之后，性能开销最小化；

方案1：控制中断

之所以会面临并发的问题，在于 CPU 的操作并非原子性的，它通过时钟中断来实现在不同进程或线程之间的切换；因此当线程进入临界区后，如果能够关闭中断，等待当前线程处理完，再恢复中断，就可以实现互斥性；

控制中断的方案实现起来很简单，但是缺点很多，包括：

• 无法规避恶意程序；
• 无法支持多处理器；
• 中断时可能丢失其他程序发出的中断消息；
• 性能太差：因为 CPU 内部要做一系列准备工作；

基于以上这么多的缺点，这种实现方案用得场景非常少；仅在操作系统内部使用，而不是在 CPU 内部使用，即操作系统选择性的在某些时刻暂时屏蔽它自己接收到的中断消息，将手头某个任务全部处理完后，再恢复处理中断队列中的消息；

没有硬件支持，仅通过软件实现的锁很危险，因为完全无法控制时钟中断何时会发生，有可能当前线程 A 正检查完锁可用时，中断了，切换到另外一个线程 B，然后它也发现锁可用；然后设置标记变量为 1；这时中断发生，切换回进程 A ，它接着上次的中断处继续进行，也觉得当前锁自己可用；最终的结果是两个线程同时进入了临界区；锁的互斥性根据没有得到有效实现；因此，必须有硬件的支持，让某些操作指令原子化；

方案2：测试并设置指令

“测试并设置”指令也叫做原子交换（atomic exchange），它的思路是设置一条由 CPU 支持的原子性执行的指令；这条指令会取出旧值，设置新值，并返回旧值；

当有了这条原子性执行的指令后，应用程序就可以基于它们来实现锁；当一个线程暂时取不到锁时，它会陷入自旋等待，直到另外一个线程释放了锁为止；

在 x86 机器上，原子交换指令写成 xchg；

自旋等待的锁有两个缺点：

• 在等待期间，会消耗掉分配给它的完整时钟周期，无谓消耗浪费了很多性能；当线程特别多且为单处理器时，这点尤其明显；
• 自旋机制本身不保证线程不会饿死，线程能否抢到锁，完全看调度器的心情；

方案3：比较并交换指令

“比较并交换”指令也是一条由 CPU 支持的原子性执行的指令，它跟“测试并设置“指令的区别在于多了一个参数，这个参数会传入一个预期值，若旧值和预期值相同，再更新为新值，否则不更新；该指令也同样会返回旧值；

相当于“测试并设置”一定会更新旧值，而“比较并交换“不一定会更新旧值；

方案4：链接加载和条件存储指令

这个方案用到了两条指令，一条用来加载指针指向的值，另外一条会判断该指针地址指向的值是否发生了更新，若没有发生，则将其设置为新值；

通过这两条指令的配合，可以用来实现锁机制；思路是当执行 lock 函数时，先加载标记变量的值，若为1，则自旋等待，因为表示此时有其他线程占用着锁；若为 0，则使用条件存储指令进行抢占；条件存储指令是原子性的，它会判断标记变量的值是否发生过更新，如果没有，意味着还没有其他线程抢占过，则更新它，并获得锁；如发生过更新，表示有线程提前抢占成功，重新开始循环；

方案5：获取并增加指令

这个指令很有意思，它引入了两个标记变量，一个用来表示排队号，一个用来表示当前叫号；跟银行的叫号机工作原理差不多；初始状态下，排号的号码从零开始；第一个线程进来后，取到 n 号，然后排号增加 1，即下一排队号变成了 n + 1 号；取完号后，去窗口看一下当前的叫号，如果刚好是 n 号，则获取锁（开始给它办理业务）；如果不是 n 号，则等候；当线程释放锁时，窗口的服务人员会将叫号增加 1，这样持有该排队号的线程接下来就可以办理业务了；

这个指令有一个特别大的好处，即每个线程都有机会轮上，而且还是先来后到；前后三种方案则无法保证线程什么时候会被安排，靠运气；

避免自旋

显然当一个线程无法获取锁时，一直处于自旋等待是完全没有必要的，纯粹是浪费分配给它的 CPU 时钟周期；如果线程很多的话，就会极大的降低性能，因此有必要当线程进入自旋时，就要求它放弃当前的时间片，切换到其他线程；

方法一是在操作系统层面增加一个能够让出当前调度的系统调用，这样当线程发现自己无法获取锁时，就调用该函数，结束当前的 CPU 时间片；这种方法的性能比自旋好了不少，不过如果线程很多的话，仍然可能产生很高的线程切换成本；

方法二是引入休眠功能，并增加一个队列；当线程无法自己获取锁时，就将自己放到队列中等待，然后进入休眠状态，这样它就不再需要频繁的被切换；当其他线程释放锁时，它就去队列里面找一个线程唤醒它；

结合队列，当一个线程取号后，就查看一下当前叫号，如果不是自己的号，就进入休眠队列，等待被唤醒；当某个线程释放锁时，叫号增加1，然后唤醒队列中对应编号的线程；该线程被唤醒后，检查一下当前叫号，如果是自己，就去尝试获取锁；如果不是自己，重新进入休眠；如果获取不到锁，则意味着有人抢占了，也重新进入休眠；

23.使用锁的并发数据结构

锁的目的是应对并发的场景，但并非所有的并发，都需要使用锁；只有并发场景需要访问修改共享变量时，才需要用锁；这个时候，在设计数据结构的访问修改函数时，需要考虑锁的使用时机和位置，这样才能确保数据的线程安全；但确保线程安全不难，如果要同时兼顾性能，就开始形成一定的挑战了；

并发计数器

计数器是很常见和频繁使用的一种数据结构，某些场景需要在多线程之间共享某个计数器，此时该数据结构将面临线程安全问题；此时会遇到的一个问题是可扩展性，即保证线程安全的情况下，访问性能没有下降，即实现可扩展的计数；

可扩展的计数

单核多线程可以实现并发，但并没有提高性能，只有多核多线程，才通过利用了多核的优势，提高了性能；所谓的可扩展性是指，在引入多核的情况下，原本的锁设计，仍然能够保证对数据结构的访问，能够获得跟单核单线程同样的性能；

它的实现有很多种办法，其中一种叫懒惰计数器，它通过牺牲一点准确性，来保证性能问题；其基本思路是使用全局锁和全局变量来记录全局的计数器，但在每个 CPU 里面，又增加一个局部计数器和局部锁；对于单个 CPU 内部的线程，它只负责当前 CPU 的锁并更新局部的计数器，这样一来没有人跟它竞争，因此它的性能同单核单线程是一样的；然后设定一个阈值，当某个 CPU 的局部计数器值越过这个阈值时，该 CPU 就尝试获取全局锁，将自己的局部计数器值同步写入全局的计数器；

整体来说，当 S 足够大时，这种方法的性能跟单核单线程越接近，但是全局计数器会有一定的延迟；即任意时间点下，获取到的全局计数器值，可能并不是最新的，而是对应于过去的某个时间点；

并发链表

让链表的操作实现线程安全并不复杂，重点是保证在更新链表的关键时刻（即临界区）加锁即可，并在更新完之后，释放锁，避免将加锁的位置提前到内存分配的时候，因为内存分配有可能发生错误，这样会导致锁没有释放；

虽然链表的线程安全容易做到，但是多核多线程下的高性能却是很有挑战，因为链表是一种线性查找的数据结构，它无法提前将任务分段，交给不同的 CPU 并发处理；

并发队列

对于先进先出的队列，需要设置两把锁，一把负责头部，一把负责尾部，它们之间可以实现并发，即在头部删除元素和尾部增加元素并不会发生冲突；

并发散列表

在不考虑改变散列表大小的情况下，散列表的实现只需要基于之前的链表结构即可，每个桶对应一个单独的链表；而每个链表的背后已经是支持线程安全的；这种结构的散列表具有很好的扩展性，因为它实质上是链表间独立的锁，并不会相互影响；

24.条件变量

使用场景

锁只是解决了线程并发访问某个共享变量的问题，但有时候线程之间需要等待某种条件满足后才能继续往下进行，例如当某个线程执行完毕后，另一个线程再开始执行。最简单的解决方案是引入某个条件变量，需等待的线程在它的时间片中，不断的检查这个变量，如果条件满足了，就继续往下执行，如果不满足，就自旋等待。该方案的好处是实现简单，缺点是性能低下，因为自旋需要浪费掉整个时间片；

新的解决办法：除了已有的锁和条件变量后，再引入睡眠和循环检查；线程 A 持有锁后，检查到条件不满足时，就让 A 进入释放锁并进入睡眠；B 线程开始持有锁，做完动作，更新条件变量，发信号唤醒 A，并释放锁；A 被唤醒后，尝试重新取得持有锁后，再次检查条件变量，若满足，开始执行自己余下的动作；

wait() 操作会做四个动作：释放锁、睡眠、被唤醒、获取锁；因此，在执行 wait 之前，当前线程获取锁是必须的，不然有可能长眠不醒了；

signal() 在执行之前也需要先获取持有锁，避免产生竞态条件；

生产者/消费者问题

当有多个生产者线程和多个消费者线程时，如何解决它们之间使用共享缓冲区可能存在冲突的问题？

为了尽可能提高效率，应该避免单次的生产-消费之间的轮换，而应该支持批量多生产和批量多消费，这样可以减少轮换等候的成本；因此，需要引入数组的数据结构，生产者可以依次给每个数组的每个位置写入值，而无须等待消费者是否已经来把值取走了，除非整个数组都写满了；这么做的原因在于，当某个生产者线程释放锁时，抢占到锁的不一定是消费者线程，也有可能是另一个生产者线程，因此该方案可以让它有事可做，而不是放弃它抢到的时间片；

另外还需要引入两个条件变量，分别代表生产者和消费者；当某个生产者线程完成了它自己的工作后，它就同时唤醒一个消费者线程并释放锁；（但释放后并意味着下一个抢到锁的是消费者，也有可能是一个生产者，反之亦然）；

好奇：生产者是先释放锁，再唤醒消费者；还是先唤醒消费者后，再释放锁？

答：从安全的角度来说，貌似应该先释放锁，之后再唤醒消费者；因为如果先唤醒消费者，有可能在释放锁之前，消费者抢占到了时间片，然后尝试获取锁，发现获取不到，然后就重新进入睡眠了；

覆盖条件

覆盖条件的一个例子是多线程的内存分配；内存分配函数检查当前可用堆内存，如果大于待分配值，则进行分配，如果小于，则进入睡眠；内存释放函数在释放某个之前分配的内存后，唤醒睡眠中的内存分配线程；但由于不知道当前释放的内存，是否能够满足哪些待分配线程，它只能将所有睡眠中的分配线程全部唤醒；

不知道为什么这种方案叫做覆盖条件，它真实的本质是不再只唤醒某个线程，而是唤醒所有线程；虽然这种做法会降低性能，因为有些线程唤醒后发现条件仍未满足，然后只好又睡了；

24.信号量

除了锁和条件变量外，信号量是另外一种解决并发问题的方案，这个方案很有趣，感觉它好像自带队列的性质，而且去除了 while 循环；

信号量的定义

信号量（semophore）是一个整数值，并配套两个函数来操作它，它们分别是：

• sem_wait()：也叫 down 或 P 函数，它做两个动作，一是将信号量减1，二是判断减1后的信号量是否为负数，如果是，则让当前线程进入睡眠；
• sem_post()：也叫 up 或 V 函数，它也做两个动作，一是将信号量加1，二是判断有无睡眠中的线程，如有，唤醒其中一个；

当信号量为负数时，该负数值刚好表示当前有多个线程处于睡眠状态中；

#include <semaphore.h>
sem_t s;
sem_init(&s, 0, 1); // 初始化信号量，0 表示该信号量被同一进程的多个线程共享；1 表示初始值为 1；

二值信号量（锁）

问：不知此处为何叫二值信号量，事实上当有多个线程时，信号量的值并不只是在 0 和 1 之间变化，而是有可能会出现负数；

答：被唤醒的线程将直接获得锁，不用再次执行 wait 进行判断（因为之前已经执行过了）；并在执行结束后，对信号量做加1的操作；

当将信号量的初始值设定为 1 时，在临界区的前后调用 sem_wait 和 sem_post 函数的效果，跟上一章的 lock 和 unlock 作用很像，此时信号量发挥的作用跟锁是一样的；

此时信号量扮演的作用非常有趣和巧妙，由于每个线程在进入临界区前，都需要调用 sem_wait 函数尝试获取锁，如果获取不到，就会让自己进入睡眠状态；而当线程从临界区出来的时候，如果有线程在等待，它需要唤醒一个线程，那么这个被唤醒的线程，等同直接获取了锁（此时的信号量有可能依然为负数），而无须做进一步的判断（之前的锁方案有使用 while 进行判断）；

问：如何保证所有的线程都有相同的机会被唤醒，而不会出现某些线程被饿死？

sem_wait(&m);
// critical section here
sem_post(&m);

信号量用作条件变量

当将信号量的初始值设定为 0 时，它可以作为条件变量，用于 A 线程调用 sem_wait 函数等待条件满足时，再继续往下执行，而 B 线程负责调用 sem_post 函数改变条件；

生产者/消费者问题

生产者/消费者问题据说也叫做有界缓冲区问题；原因在于除了缓冲区的 empty/full 判断外，为了避免多个生产者（或消费者）同时进入 get/put 函数，需要对多个生产者之间增加互斥，即每次只能有一个生产者进入 put，或者只有一个消费者进入 get；

此处对 get/put 的互斥锁，不再放在 empty/full 锁的外面，不然由于它的作用域过大，将直接导致死锁情况发生，即某个线程因为 empty 进入睡眠了，但却仍然持有 mutex 锁，导致后续的线程无法获取锁并将其唤醒；避免作用域过大的做法，即为考虑锁的使用界限，因此称为有界缓冲区问题；

读者-写者锁

不同的数据结构，会面临不同的并发状态，例如链表结构，只有写的并发是需要用到锁的，而读的并发则可以不用锁，因此，如果为不同的数据结构设计不同形式的锁，有利于进一步提高性能；

它的思路是设计两个信号量，一个用来控制读，一个用来控制写，并增加一个当前正在读的线程的计数器；第一个读者需要同时获取读锁和写锁，这样可以避免其他线程在它读的时候，进行写的操作；第二个及以后的读者则无须获取写锁；最后一个退出的读者需要负责释放写锁，以便让写者线程可以有机会进行写的操作；

这个方案虽然可以实现读写分离，但是它有两个问题，一个是写者线程有可能被饿死；二是相比普通单锁的方案，由于多增加了一个锁，性能上其实并没有优势；

启示：复杂的方案不一定更好，有时候简单的笨办法反而不错；Hill 定律：大而笨更好；

哲学家就餐问题

这个问题的有趣之外在于，哲学家们是坐成一圈的，所以一个人的左边，是另一个人的右边。因此如果每个哲学家取叉子的顺序一样的话，将有可能造成循环等待的问题，结果便是死锁；为了避免死锁，需要至少让一个哲学家的取叉子顺序跟别人不同，这样就至少会有一个哲学家能够吃上饭了；

如何实现信号量

// 使用锁+条件变量的方式，来实现信号量机制

typedef struct _zemt_t {
    int value;
    pthread_cond_t cond;
    pthread_mutex_t lock;
}

void Zem_init(Zem_t *s, int value) {
    s->value = value;
    Cond_init(&s->cond);
    Mutex_init(&s->lock);
}

void Zem_wait(Zem_t *s) {
    Mutex_lock(&s->lock);
    while(&s->value <= 0) {
        // 进入睡眠前会释放锁；唤醒后会持有锁
        Cont_wait(&s->cond, &s->lock);
    }
    s->value -= 1;
    Mutex_unlock(&s->lock);
}

void Zem_post(Zem_t *s) {
    Mutex_lock(&s->lock);
    s->value += 1;
    Cond_signal(&s->cond);
    Mutex_unlock(&s->lock);
}

使用锁+条件变量也可以实现信号量，因此信号量看上去有点像是锁+条件变量的一种抽象；它既可以用来替代锁，也可以用来替代条件变量，但是，能否替代成功，跟问题场景密切相关，并不是所有的场景都能够替代成功的；因此，使用信号量时要特别的小心，虽然看似简单了，但效果不一定百分百保证，需要进行更加深入的分析和测试，才能够建立信心；

安全起见，使用原始的锁+条件变量方案，或许是更好的做法；

25.常见并发问题

有哪些常见的并发缺陷？如何处理常见的并发缺陷？

有哪些类型的缺陷

一般有非死锁和死锁两类缺陷，前者占多数；

非死锁缺陷

违反原子性缺陷

代码原本预期按原子性来执行，但实际的效果并没有实现原子性，A 线程的部分操作在执行到一半的过程中，可能会因为调度产生中断，某些值被新线程 B 修改，导致调度回 A 线程时，其执行环境已经发生了破坏，导致出错；

解决办法：给需要原子性的操作加锁；

错误顺序缺陷

B 线程在运行过程中可能假定某个值已经由前面的 A 线程完成了初始化，但实际上，由于调度的随机性，有可能这个时候A 线程还未被调度过，初始化并未完成；

解决办法：引入锁+条件变量+状态变量；

绝大部分的非死锁缺陷（约 97%）都是以上两种类型的缺陷；

死锁缺陷

有多个锁，且线程的抢锁顺序不同，导致最终陷入相互等待的境地；

产生的原因

• 复杂系统中，组件之间很可能存在相互依赖，例如虚拟内存需要通过文件系统访问磁盘读取数据到内存，而文件系统又要访问虚拟内存申请一片内存页，存放相应的数据；
• 封装：开发人员一般倾向于模块化实现的细节，但是模块化有时无法跟锁很好的契合，导致出现死锁；

产生死锁的条件

必须同时满足以下四点

• 互斥：对于共享的某个资源，线程对其访问存在互斥性，即一次只有一个线程可以抢到访问资源的锁；
• 持有并等待：线程持有一个资源后，还需要等待抢占其他资源；
• 非抢占：线程已经获得的资源，不会被其线程抢占；
• 循环等待：线程之间存在回路，某个线程持有的资源，刚好是下一个线程想要抢占的；

预防的方法

循环等待

针对循环等待，简单的解决办法就是强制线程对锁的抢占需要按照固定的顺序，比如有两个锁 L1 和 L2，总是先抢 L1，再抢 L2；这样就可以避免两个锁被不同的线程分别持有；

• 全序：锁少的时候用；
• 偏序：锁很多的时候用；

持有并等待

持有并等待的问题根源于等待的资源可能被占用，因此可以通过增加一个全局锁来解决；所有的线程，必须先抢到这个全局锁后，才可以开始抢占剩下的锁，这样就可以避免存在资源在不同线程手上的问题，但这个方案也有一些缺点

• 一是降低了并发性，因为现在所有的线程都得等待同一个锁了；
• 二是不便于封装，据说是因为需要准确的知道需要抢些锁，并提前抢到这些锁（暂时还没有想明白为什么，可能是因为锁需要设置成全局的，无法封装到函数内部里面去）；

非抢占

解决思路就是增加一个 trylock 的判断，当暂时无法抢到下一个资源时，就先放弃已经占有的资源；这种方式肯定不会造成死锁，但有可能陷入活锁的问题；就是大家总是让来让去，最后啥进展也没有；为了避免活锁问题，需要引入一个随机等待时间，即等候一个随机时间后，再开始新的一轮循环，这样可以一定程度的降低活锁概率；

互斥

互斥性是锁的本质，如果不提供互斥性，锁就没有存在的意义了；如果不用锁，则需要通过利用硬件指令的原子性，来实现原子性的操作，例如比较并互换指令（但是感觉它的应用场景貌似有限？）；但是这种方案有可能会带来活锁问题；

通过调度避免死锁

如果我们能够提前知道不同线程可能对锁的需求不同，则只需避免将会有完全重叠锁需求的线程调度到不同 CPU 上同时运行即可；不过这种方案有硬伤，一是它极大的降低了性能；二是我们需要提前知道所有的任务，并知道它们各自需要什么样的锁，这样才可以设计出调度的方案；

示例一：

示例二：

检查和恢复

最后一个不是办法的办法是允许死锁发生，然后定期做一次检查，如果发生停滞了，就做一次重启；很多数据库采用了这个方案；

26.基于事件的并发

基本思路

事件处理程序一开始啥也不做，坐等事件的到来；它轮询事件队列，获取待处理的事件，然后依次处理

while (1) {
    events = getEvents();
    for  (e in events) {
        processEvent (e);
    }
}

select() API 介绍

操作系统提供了一个 select 系统调用函数来实现基于事件循环的并发；它的原理也很简单，该系统调用接收一堆文件描述符的集合和待检查的数量上限；之后操作系统在该数量上限内，依次逐一检查每个文件描述符（包括读、写、错误三类），看某个描述符是否已经进入了就绪的状态；最后，将所有已经处于就绪状态的文件描述符组成一个列表返回；

问：为什么要引入一个上限？

int select (
	int nfds, // 待检查文件描述符数量上限
    fd_set *restrict readfds,  // 读
    fd_set *restrict writefds, // 写
    fd_set *restrict errorfds, // 异常
    struct timeval *restrict timeout  // 检查时间，超时后返回；若为 NULL 则在未找到任何就绪的描述符前先阻塞；若为 0 则马上返回
);

使用 select()

建立一个无限循环，在循环开始时，初始化并准备好一个文件描述符的集合，然后调用 select，将集合送进去检查；如果某个描述符已经进入了就绪状态，select 会对其进行标记；当 select 标记完毕返回完；再依次遍历集合中的每个描述符，看其标记是否改变，若改变，表示该描述符已经就绪，因此可调用相同的函数，对其进行处理；

由于只剩下一个线程在处理事件，因此基于事件的并发处理机制，就暂时不需要锁了，因为不存在线程之间的冲突；不过当 CPU 不止一个时，如果想利用多核 CPU，则有可能会存在冲突；

I/O 异步

如果应用程序发起的操作，仅仅在 CPU 层面就可以完成的话，事件机制是没有任何性能问题的；但是如果某个操作涉及 CPU 之外的操作，例如对 I/O 设备的访问，由于这些设备很慢，将导致 CPU 要等待很长时间才能得到结果，这将导致严重的性能下降，因为 CPU 的时间片大量闲置；仅仅有 select 调用，还不足以让基于事件的机制应付各种业务场景，需要引入一些新的操作系统接口来完善它；

早期操作系统对 I/O 设备发起的请求是同步的，为了支持基于事件的并发，现代操作系统开始提供异步的 IO 请求接口；应用程序调用该接口，发起 IO 请求，但在请求完成之后，操作系统又会马上将控制权返回给应用程序；

当 IO 请求中的动作完成后，此时有两种机制可以通知应用程序：

• 应用程序定期轮询的 IO 请求队列，查看是否有某个请求已经就绪；该方案的缺点是成本过高；
• 请求完成后，发出中断信号给应用程序，应用程序再进行处理；优点：性能好；

状态管理

当一个异步的 IO 请求进入就状态后，应用程序需要知道如何处理该请求的结果，因为应用程序可能在之前已经发起过很多个 IO 异步请求，每一个请求的结果可能需要使用不同的方式进行处理；为了能够让请求结果和处理方式一一对应，一种办法是在发起请求的时候，将相应的结果处理方式，也记录在文件描述符的某个属性中，这样当请求结果返回时，就可以在文件描述符中查找到该属性，获得对应的结果处理办法；

仍然存在的问题

• 无法利用多核CPU：虽然单线程的机制避免了使用锁带来的麻烦，但是单线程无法利用多核的 CPU 来提高性能；如果针对每个 CPU 各开一个线程，则线程之间将不可避免会遇到临界区冲突的问题；
• 部分系统调用非异步：当某个非异步的系统调用发生错误时，例如发生了页错误，由于应用程序是单线程的，此时将导致整个应用程序被阻塞挂起，无法做出响应；
• 可能会累积复杂性：基于事件的代码引入了一些复杂性，随着时间的推移，这些代码的复杂度将逐渐累积，可能会给后续增加代码管理成本；

基于事件的并发机制并不是万能药，或许暂时较为可行的解决方案之一，是将应用程序设计成无状态的，这样就可以充分利用多核的CPU，甚至是多个机器节点；而将有状态的数据，交给其他的应用程序如数据库进行管理；数据库来负责原子性的部分；

27.I/O 设备

问题：I/O 显然是非常重要的，那要如何将 I/O 集成到系统中？常见的机制是什么？如何让其变得高效？

系统架构

不同的设备使用不同速度规格的总线相连，取得成本和速度之间的折中平衡；

标准设备

计算机是由多种设备组合在一起协同工作的，设备与设备之间需要相互配合协作；因此，每个设备都需要定义一套自己的接口和交互协议，以便别人可以调用它提供的功能；而在设备内部，设备需要负责接口所代表的功能的具体实现；实现的办法同样包括拥有自己的微处理器、通用内存、完成特定功能的芯片等；

标准协议

while (STATUS == BUSY)
	; // 轮询等待，直到设备空闲
write data to DATA register // 设备空闲时，向设备DATA寄存器写入数据
write command to COMMAND register // 向设备的 COMMAND 寄存器写入指令，之后设备开始按指令处理数据
while (STATUS == BUSY)
    ; // 轮询等待设备处理完毕
get data or status from register // 处理完毕后，从设备的寄存器读取状态和数据
    

标准协议的交互逻辑还是很简单的，问题在于太过于低效，因为 CPU 要在整个时间片里面不断轮询，浪费了很多无谓的时间；

利用中断减少 CPU 开销

减少 CPU 开销的一个办法是引入中断机制，让设备处理完毕后，可以给 CPU 发一个中断信号，之后 CPU 就可以调用提前映射好的中断处理程序，处理设备计算结果；

中断机制并非在所有情况下都是最好的方案，它比较适用于与计算速度比较慢的设备进行协作的场景中；如果设备的计算速度很快，在收到命令后能够很快给出结果，则中断并没有太大意义，反而增加了切换的成本，此时传统的轮询机制的性能反而更好；

但是有时候并不知道设备的处理速度有多快，一个折中的办法是引入混合模式，即 CPU 在发送完指令给设备后，就尝试轮询一小段时间，如果在该时间内设备仍然未处理完毕，CPU 就切换到其他线程；

网络场景也不适合完全使用中断，因为服务器有可能在短时间内收到大量的请求，如果只用中断机制，将使得 CPU 疲于应付大量的中断信号，而无暇处理真正的请求内容；此时适当配合使用轮询反而效果更好，CPU 可以通过轮询的方式接收一批请求的数据包，然后专心处理它们；处理完之后，再轮询网卡，处理下一批请求的数据包；

另外也可以在设备层面对中断机制进行优化，设备不再是一处理好马上发出中断，而是可以稍等一小段时间，先继续处理一些请求，因为它们有可能也很快可以完成；之后再一次性的发起一次中断；通过将多个中断合并成一个中断，也可以降低中断的性能代价；

问题：当 CPU 收到设备发过来的中断信号后，由于此时 CPU 有可能已经切换到其他线程，CPU 如何知道中断信号是属于哪个线程的？

答：猜测 CPU 并不需要知道，它只要把信号转发给操作系统就好了，由于操作系统负责做好映射表，查询某个设备之前是由哪个线程调用的；此时操作系统负责唤醒该线程；

利用 DMA 更高效的传输数据

当 CPU 在跟设备交互的时候，有一个环节是需要向设备写入或读取数据，这个动作本身也是需要时间的，但是它是非常简单的数据读取或拷贝，并不需要什么计算能力，因此让 CPU 来做这个工作有点屈才和得不偿失；为了避免这个问题，通过引入 DMA（direct memory access）机制，给 CPU 减轻工作压力，让它去处理其他更高价值的工作；

当进入读写数据的环节时，CPU 就发送相关的指令给 DMA，包括数据在内存中的位置，数据的大小，数据的目的地等信息；之后 CPU 开始去做其他的工作，而 DMA 就负责接下来的数据传输工作；

操作系统与设备交互的方法

问：操作系统用什么方式跟设备发生交互？例如从设备读取数据，或者向设备写入数据？

方法一：I/O 指令

CPU 提供了一些 I/O 指令供操作系统调用；当操作系统想要向某个设备写入数据时，就调用该指令，指定设备的某个寄存器（设备存放数据的地方），指定端口号（代表某个特定的目标设备）；CPU 在收到指令后，执行向设备写入数据的操作；

这些 I/O 指令都是特权指令，只有操作系统才有权调用，普通程序无权调用；

方法二：内存映射 I/O

操作系统不直接与设备的寄存器打交道，而是将设备的寄存器映射到虚拟内存地址空间中，用某个虚拟地址代表它；当需要向设备写入数据时，操作系统调用的指令跟平时写入虚拟内存时一样；CPU 在收到该指令后，通过映射表找到实际的设备寄存器地址，然后向设备的寄存器写入数据（内存映射的一个好处是 CPU 不需要单独设计额外的指令集，仅使用原有的指令集就可以了）；

问：映射关系记录在哪里？

答：莫非 CPU 的 TLB 里面有专门的地方用来记录这个东西？

纳入操作系统：设备驱动程序

操作系统由很多个子系统构成，每个子系统都可能与设备打交道，显然让每个子系统都直接去调用设备的交互接口并不是一个好主意，因为当某个设备发生变动时，导致所有子系统都需要做出调整；更好的办法，是让部分模块专门负责与某个特定设备进行交互，由它负责具体的交互实现细节；而系统中的其他模块，只要直接调用该模块提供的接口就好了；（这其实就是简单又强大的抽象分层技术）；

某个具体实现与特定设备进行交互的模块，即是常说的设备驱动程序；

这种架构也有一点缺点，即如果某个比较新款的设备提供了一些市面上不常见的特殊功能，由于通用块接口的开发或者某个系统软件（如文件系统）的开发还没有跟上，暂未实现调用该特殊功能的接口给应用程序，将导致应用程序实际并无法使用到设备提供的最新功能；

此时貌似需要操作系统尽快推出补丁了？

IDE 磁盘驱动程序示例

IDE 硬盘包括以下寄存器：

• 控制寄存器：1个；
• 命令寄存器：8个；
• 状态寄存器：1个；
• 错误寄存器：1个；

驱动程序与设备的交互过程大概如下：

• 等待设备就结绪：通过查看设备的状态寄存器获得是否就绪的信息；
• 写入命令参数：向设备的命令寄存器写入参数：写入的内容包括扇区数、逻辑块地址、磁盘编号（因为同一条 IDE 线支持挂载两个硬盘）；
• 写入命令：向设备的命令寄存器写入命令，以便配合上一步的参数，让磁盘实现具体的操作；
• 数据传送：等待，直到设备的状态寄存器的值再次更新为 READY 和 DRQ 时，向设备的数据寄存器写入数据；
• 中断处理：正常情况下，每个扇区的数据传送结束后，都会触发一次中断，以便调用相应的中断处理程序；
• 错误处理：每次操作后，都检查一下错误寄存器，就触发错误处理程序；

28.磁盘驱动器

问题：现代磁盘驱动器是如何存储数据的？接口是什么？数据是如何安排和访问的？磁盘调度如何提高性能？

基本单位

磁盘驱动器的最小单位是扇区，每个扇区默认为 512 字节；每一次操作都是什么一个扇区的原子性操作，要么全部写入，要么全部没有写入；整个磁盘被划分为 n 个扇区，相当于一个由 n 个元素组成的数组；地址空间（即地址编号范围）由 0 到 n-1 组成；

虽然有些文件系统支持以 4KB 为单位的读取和写入，但实际上在底层仍然是以 512 字节为单位的；这意味着 4KB 的操作并非原子性的，如果在读写过程中发生断电，有可能导致 4KB 的数据只写了一部分；

基本几何形状

由大到小：盘片->表面->磁道->扇区；表面上的磁道很多，几百个磁道加起来也只有一根头发的粗细，因此整个表面拥有成千上万的磁道；由于越外围的磁道，周长越大，因此如何分配跟内围的磁道相同的扇区数的话，显然会造成极大的浪费；因此，一般将表面分成多个区域，相同区域内的磁道，虽然周长不同，但扇区数相同；不同区域的磁盘，扇区数不同，以最大化利用磁盘表面的空间进行数据存储；

缓存机制

寻道时间和旋转延迟是磁盘 I/O 操作中时间成本最高的两个操作；为了降低每次读写数据的时间成本，磁盘通常会引入缓存机制，即并不是精准读取指定扇区的数据，而是将整个磁道多个扇区的数据一起读取出来，放到缓存中；由于局部性原理，接下来这些数据有很大概率被访问，从而避免了第二次的寻道和旋转时间；

I/O 时间

对于随机访问和顺序访问两种场景来说，磁盘性能差距巨大，可能有 200-300 倍左右的差距；随机访问可能才 0.5M/s，而顺序访问可以达到 100M/s；

调度策略

相对于任务调度，磁盘调度有一个好处是可以大概估算完成操作所需要的时间，假设操作系统收到多个磁盘调度的请求，由于可以大致计算每个调度的用时，因此可以使用一些调度策略来提高调度性能；

最短寻道时间优先

操作系统可以根据请求的扇区地址，计算出各个请求与当前位置的远近顺序，优先服务最近的请求，延后服务最远的请求；这样可以避免浪费时间在寻道上面；缺点：有可能导致最远磁道的请求饿死；

电梯扫楼策略

这个策略很像到写字楼发传单的场景，推广人员乘坐电梯，将底层到顶层，将每一层楼扫一遍；扫完之后，如果还有没有新进来的待处理请求，再从最顶层到最底层扫一遍，以此类推；

这个方法的好处是可以避免某些请求饿死，但它仍然不是最优的算法，因为它没有考虑旋转延迟的成本；

最短定位时间优先

这个策略的优点是将旋转延迟的成本也考虑进来了，以最短的寻道时间+旋转时间之和作为调度的顺序；但是理想很丰满，现实很骨感；因为磁盘的规格型号很多，操作系统并不知道所要寻找的扇区在磁盘表面的位置，因此也无法估算出旋转时间；所以，这个策略并不适合操作系统，但适合在磁盘内部来实现；因为每个磁盘生产商在生产磁盘的时候，各项参数是已知的；

双重调度

在早期，磁盘的调度是由操作系统来完成的，但为了取得更好的性能，现在改成了由操作系统和磁盘二者共同完成；操作系统挑选一批自认为不错的请求发给磁盘（例如会合并一些扇区相近的请求），磁盘使用内置的调度程序，以最快的策略处理请求并返回结果；

一般来说，操作系统并不是一收到应用程序的 I/O 请求，就马上将它发给磁盘，而是会稍微等一小段时间，让更多的请求进来后，再开始调度；

29.廉价的冗余磁盘

问：数据除了能够更快的访问外，如何解决可靠性问题，避免意外丢失？

RAID 的全称竟然是 Redundant Array of Inexpensive Disk，翻译一下：廉价的冗余磁盘组；

RAID 的思想很像单独组建一套由多个磁盘、内存、1个或多个处理器组成的计算机系统，这套系统的专职工作即是完成数据的存储和管理；它有如下的优点：

• 增加了可靠性，即使有一个磁盘不工作了，也不会导致数据的丢失；
• 提高了性能，原来的 I/O 请求需要排队逐个处理，现在可以分散给多个磁盘并发处理；

接口和 RAID 内部

RAID 对外暴露的接口跟普通的磁盘完全一样，这就使得它的部署和使用变得没有成本，不需要改动操作系统或应用程序，即可以像使用普通磁盘那样使用 RAID 磁盘；

但实际上 RAID 内部是相当复杂的，它接近等同一个独立的计算机系统，有自己的内存、处理器和磁盘；当它接收到外部的逻辑请求后，对该请求进行换算，映射成物理请求，然后发给磁盘进行处理；

故障模型

RAID 本质上主要还是为了提高可靠性，因此需要对现实世界中可能发生的故障类型进行建模，常见的有如下几种类型的故障：

• 故障-停止：磁盘出现故障，然后不工作了；
• 磁盘损坏
• 扇区错误

如何评估 RAID

RAID 有多种设计实现方案，分别对应满足不同的业务需求，有些侧重可靠性，有些侧重性能，因此一般有三个评估的维度：

• 性能；
• 可靠性
• 容量；

RAID 0级：条带化

条带化的思想是将扇区按顺序轮流放在每个磁盘上，示例如下：

块的大小

以多大的块作为最小的单位，轮流存储在每个磁盘上，是一个设计时需要权衡的问题；块越小，则文件访问的并行性越好；但是同时会增加寻道和旋转成本；因此并不存在最佳方案，完成取决于主要应用在何种业务场景；一般来说，大多数使用 64KB 的块大小；

• 优点：性能好、容量大；
• 缺点：可靠性差，因为任一磁盘故障都将导致数据丢失；

RAID 1级：镜像

镜像的原理是将同一份数据在两个或多个磁盘上各存储一个副本；它的好处是增加了可靠性，即使有一个磁盘发生了故障，也不会导致数据丢失，由于可以并发的读写，因此性能上也没有损失；缺点是损失了容量；

镜像在写入数据的时候，需要同时更新两个或多个磁盘，如果此时其中一个磁盘发生断电，没有写入成功，最后将导致各个磁盘存储的数据不一致；为了解决这个问题，RAID 1 引入了一个小小的非易失性的 RAM，用来预写日志；这样如果万一有某个操作被意外中断没有完成，仍然可以通过日志在后续弥补；

前面说性能没有损失有点错误，实际上性能在不同场景下有些差异：

• 顺序读：N * S / 2
• 顺序写：N * S / 2
• 随机读：N * R
• 随机写：N * R / 2

此处 N 表示磁盘的数量，S 表示顺序，2 表示副本数量，R 表示随机，单位为 M/s

RAID 4级：通过奇偶校验节省空间

由于 RAID 1级非常浪费空间，RAID 4 级准备在这个维度上进行改进；它的思路是在普通磁盘上使用异或算法得到计算结果，并增加一个磁盘用来存储该异或结果；

这样当某个磁盘出错时，可以跟剩余磁盘的位+校验磁盘位，再次异或，得到丢失的位的值；

这个算法很机智，不过 RAID4 最大只能允许一个磁盘出错，如果有2个或多个以上的磁盘出错，就恢复不了了；

各个场景下的性能分析：

• 顺序读：(N - 1) * S
• 顺序写：(N - 1) * S
• 随机读：(N - 1) * R
• 随机写：R / 2，看起来确实很糟糕，因为只有一个校验磁盘，这意味着对任何普通磁盘的写入，都必须汇总到校验盘的读写上面，而它又需要先做一次读，再做一次写，才能完成一个逻辑写入，因此性能下降为单个磁盘的一半；

RAID 5 级：旋转奇偶校验

为了解决 RAID4 在随机小写入场景中性能糟糕的问题，引入了 RAID 5级，它的思路是不再将奇偶位单独存储在一个磁盘上，而是像普通数据一样，加入轮转的队列；根据顺序，依次存放在不同的磁盘上，例如 P0 在编号磁盘4，P1 在磁盘3，P2 在磁盘2，以此类推；

由于奇偶位引入了轮转存储的机制，因此随机小写入的性能会有所提升，达到约 N * R / 4 MB/s；

此处有 4 倍的损失原来在于每个小写入，都将导致两次读取 + 两次写入；

总结：不同的 RAID 方案用以实现不同的目标

• 性能+容量：条带化 RAID0
• 性能+可靠性：镜像 RAID1
• 容量+可靠性：RAID5，牺牲一点点随机写入场景下的性能；

30.插叙：文件和目录

问：操作系统应该如何管理文件和存储设备？需要给应用程序提供哪些API？实现环节有哪些注意事项？

文件和目录

文件和目录是操作系统提供给用户关于管理存储数据的一种抽象；文件和目录都有一个自己的编号（inode号），同时还有一个方便用户阅读识别的名称（名称通常可以由用户任意指定，只要不包含一些限制符号）；目录可以用来组织文件的存储结构；

文件在本质上是一个字节的连续数组，每个字节都可以被单独的读取和写入；操作系统实际上只在磁盘上存储或读取该字节数组，它并不关心里面的内容是什么，内容的解析交由应用程序自己来处理；

文件系统接口

操作系统提供了一些接口（即系统调用），让应用程序能够进行调用以完成对文件的操作；

创建文件

应用程序通过调用 open 接口实现文件的创建，同时传入一些参数，来指定所创建文件的相关要求；

int fd = open('foo', O_CREAT | O_WRONLY | O_TRUNC);
// 其中参数 O_CREAT 表示创建新文件，O_WRONLY 表示仅写入，O_TRUNC 表示如果有同名文件，删除其中的内容；
// 返回值 fd 是一个文件描述符，它相当于一个指向新创建文件的指针，通过它可以实现后续对文件的写入或读取操作；
// fd 是每个进程私有的；不同进程的不同 fd，有可能实际上背后指向的是同一个文件

读写文件：从头开始

基本过程：

• open 某个文件，得到文件描述符；
• read 该文件描述符，并指定缓冲区大小；
• write 将缓冲区内容写到目标位置（另一个文件描述符），例如屏幕（标准输出，它的文件描述符一般是 1）；
• 再次循环 read 和 write，直到文件中没有剩下内容（返回 0）；
• close 文件；

读写文件：从中间开始

lseek 系统调用允许应用程序从文件的中间某个指定位置开始读写操作，并一定非得从头开始；

off_t lseek(int fd, off_t off_set, int whence);
// off_set 表示偏移量, whence 表示偏移的方式，分别有如下几种情况：
// SEEK_SET：从头部开始，偏移 off_set 字节；
// SEEK_CUR：当前位置，偏移 off_set 字节；
// SEEK_END：从尾部开始，偏移 off_set 字节；

用 fsync() 立即写入

正常情况下，当应用程序调用 write 接口将数据写入文件后，操作系统并不是立即去执行这个动作，而是会将待写入数据暂时放在内存缓冲区中，每隔一段固定的时候，再统一向磁盘写一次；这样做的原因是为了提高磁盘的使用性能；

但是有些业务场景需要数据马上写入，例如数据库程序，因此，操作系统有额外提供 fsync() 接口，供应用程序调用；

文件重命名

在 Linux 系统下，mv 接口提供了修改文件名的功能，它背后实质上是调用了 rename 接口；rename 接口有一个特性，即它的操作是原子性的，这样做的目的在于避免奇怪的中间状态，导致数据最后丢失，例如重命名的过程当中突然停电了，如果没有原子性，将导致文件即不是原来的名称，也不是新的名称，最后用户找不到了；

获取文件信息

除了文件内容外，通常还需要保存一些文件本身的相关信息，即所谓的文件元数据（或者叫头部信息），可以通过 stat 或 fstat 接口来查看；文件系统一般将这些信息存储在一个叫做 inode 的数据结构中，通常包含如下信息：

好奇这里面怎么好像没有文件名称的信息？

删除文件

表面上看，删除文件的接口是 rm，但通过 strace 跟踪可以发现它背后实质上调用的是 unlink；

创建目录

创建目录的接口熟悉的老朋友 mkdir；但目录并不能像文件一样被直接写入内容，它的格式在本质上是一堆文件系统元数据，需要使用间接更新的方式（在目录下面创建文件或子目录），来写入一些内容；

这意味着在目录中创建文件或者子目录时，会同时修改目录节点的内容；

目录刚创建的时候，其实含有两个内容条目，一个是引用自身的条目（点目录），一个是引用父级目录的条目（点点目录）；

读取目录

读取目录的接口是也一位老朋友：ls；由于目录本身包含的信息很少，只有文件或子目录名称，以及它们的 inode 编号；这意味着当我们使用 -l 选项让 ls 展示更多信息时，它背后实质上是调用了 stat 来获取每个条目的元数据来得到最终结果；

删除目录

接口为 rmdir，但是由于这个操作可能涉及将目录中的大量文件删除，是个危险动作；因此一般要求目录为空时，才允许执行（其实这个时候也不完全是空的，里面至少还有点和点点两个条目）；

硬链接

link 系统调用可以将一个新文件的名称，链接到某个旧文件名称上；背后的本质其实是让两个文件名称指向同一个 inode 编号；所以文件实质上仍然只有一个，只是名称有了两个；

当我们使用 open 创建一个文件时，操作系统实际上做了两个动作，一个是初始化一个 inode 结构，用来保存文件的元数据；另一个是在目录中增加一个新条目，将某个文件名称，链接到该 inode 结构；

在 inode 结构中有一个引用计数的字段，它用来记录当前有多少个文件名称条目引用到自己，当引用计数为零时，文件系统就会释放存储空间，从而真正的删除文件；

符号链接

符号链接也叫软链接，它出现的目的在于解硬链接存在的一些局限性，例如：

• 不能创建目录的硬链接，因为可能会造成循环引用；
• inode 编号仅在单个文件系统中是唯一的，在不同的文件系统中则不是；而一个操作系统下通常有多个文件系统（每个文件系统对应一个磁盘分区）；

软链接表面上用起来好像跟硬链接一样，但背后有本质性的不同，它实现上并不是为新文件名增加一个引用条目，而是增加一个文件名的映射，即将新文件名映射到旧文件名；因此软链接的大小取于旧文件名有多长，旧文件名越长，则软链接的大小越大；

软链接相当于给旧的文件名起一个新昵称！

由于软链接实际上只是文件路径的映射，因此它并不会改变 inode 中的引用计数，这将导致出现悬空引用，即文件可能已经实质上删除了，但软链接仍然存在；这时如果对它进行访问，就会提示失败，找不到文件；

创建并挂载文件系统

问：什么是文件系统？

答：看上去，文件系统好像是指管理文件的一种方式；文件系统有很多种类型，例如 ext3, ext4, tmpfs, sysfs, NTFS,FAT32, 等；不同类型的文件系统，背后存储和管理数据的方式不同，各有其优缺点；当我们给磁盘进行分区的时候，需要指定使用的格式，其实此时就是在指定文件系统类型；因此一个操作系统中，可能会有多个文件系统类型；但一个磁盘分区只使用一种文件系统类型；

挂载文件系统的接口是 mount，每个文件系统都有自己的根目录，但是通过 mount，可以将各个文件系统统一集成到一个大的目录树项下，而不是多个独立的目录树，这让命名变得统一和方便了起来；

31.文件系统实现

CPU 和内存的虚拟化都需要配合硬件才能够实现，但文件和目录的虚拟化（即文件系统）不同，它是一个纯软件，并不需要硬件的配合；

问：如何构建一个文件系统？磁盘上需要存储什么数据结构？它们需要记录什么？它们如何访问？

实现决策

• 文件系统采用何种数据结构；
• 文件如何被访问；

整体组织

• 先将磁盘按固定大小分成多个块（一般大小为 4KB，块跟扇区有点类似，但一个是在文件系统中虚拟的，一个是在物理磁盘中虚拟的），每个块拥有自己的地址；磁盘变成一个由 n 个块组成的数组；每个块作为最小的存储单位，因此磁盘此时最多可以存储 n 个文件；
• 由于每个文件都有一个 inode 数据结构用来保存文件的元信息；因此磁盘上还需要划分一个区域用来存储 inode 表；每个 inode 条目此处假设固定分配 256 字节的空间；因此一个 4KB 的块，可以存储 16 个 inode 条目；如果磁盘最多可以存放 n 个文件，意味需要 n / 16 个块，用来存放 inode 表；
• 使用位图来标记其映射的 inode 块或者数据块是否空闲，还是已分配；
• 使用一个块（称为超级块）来存储关于当前磁盘上的文件系统的一些元信息，例如 inode 块数量、数据块数量、inode 表的起始位置、文件系统类型等；

问：inode 表一开始就已经固定大小了吗？还是随着存储文件的增多，其大小是动态变化的？

文件组织：inode

对于文件系统来说，它是通过 inode 来标识和管理文件的，只要给它一个 inode 索引号，它就可以通过 inode 表找到该 inode 的相关信息，从而知道文件的具体信息；

问：操作系统如何将路径转化成 inode 索引号？

答：从每级目录的数据块中遍历下一级目录或文件的 inode 编号

只要给定一个 inode 编号，文件系统就可以计算出它在磁盘上的位置（通过起始地址+偏移量计算得到磁盘扇区编号）；

由于磁盘的存储单位是扇区，一般为 512 字节，而此处块的大小为 4KB，二者不同，因此需要做一个换算；

inode 对象中包含有关于文件的一些元数据，包括读写权限、用户名、组名、创建/修改/访问/删除时间、硬链接计数、块数量、磁盘指针等信息；

多级索引

必须考虑的一个现实问题是文件在磁盘上的存储有可能是不连续的，即存储文件的块，有可能并不全部挨到一起；解决该问题有两种方法：

• 间接指针：为每个存储块分配一个指针，如果文件很大，意味着指针将很多，inode 肯定是存放不下了，因此一般在 inode 中存放 12 个直接指针（直接指向数据块），加一个间接指针（指向另外一个专门用于存放指针的块，每个块可以放 1024 个指针，即可以指向 1024 个块，每个块 4KB 的存储空间，1024 * 4KB = 4MB）；该方案的好处是存储位置非常灵活，没有限制，随便组合都行；缺点是对于特别大的文件，需要花很多块用来存放指针；例如 4GB 的文件意味着需要 1024 * 1024 个块，单这些块就需要占去 1MB 的空间（注意：此处已经引入了双重间接指针，即第一级和第二级指针指向的块，都是存储指针，而不是数据）；对于更大的文件，还可以考虑引入三重甚至四重间接指针；
• 范围指针：对于连续的块，用一个头部指针 + 一个长度范围来表示；优点：对于大文件，不再需要那么多的块，比较省空间；

目前大多数文件系统都使用了多重间接指针索引的方式来存储文件，并且在 inode 中包含一定数量的直接指针；之所以这么指针，其原因在于大部分的文件都是一些小文件，因此 12 个左右的直接指针一般就够用了，只有少数大文件，才会用到间接指针；

除了间接指针和范围指针外，还有另外一种存储文件的方式是使用链表，将下一个数据块的地址，存放在当前块的末尾；不过这种设计在应对文件内容的随机访问场景时，力有不逮，性能很差，因为需要完全扫描完整个块，才能得到下一个块的地址；

目录组织

目录的内容是由元组组成的列表，每个元组中包含关于目录中的文件或子目录的基本信息，如 inode 号、元组的长度、文件名称的长度、文件名称；

当目录中的文件很多时，列表将会很长，因此目录也需要存储在数据块中，并且在 inode 表同样会有一条 inode 记录指向该数据块；因此，目录在本质上其实就是一个特殊类型的文件而已；它的类型信息会标记在 inode 记录中；

由于目录的元组列表在数据块中是连续性存储的，当目录中的某个文件被删除时，其对应的元组将被标记为删除（例如将 inode 号标记为 0）；但是其占用的空间仍然存在，只是该空间现在变成可用的了；如果后续有新的文件写入该目录，就可以利用该空间，重新写一条关于新文件的元组记录；

这么说来，目录中的内容条目并不是按顺序存储的，而是无序的；

由于目录的元组以列表方式存储，这意味着它不能快速定位到某个文件对应的元组记录在第几个，需要从头开始扫描；当目录中的文件少的时候还好，如果文件非常多，则会有一点时间成本；

也有其他一些文件系统如 XFS，不是采用元组列表的形式来存储信息，而是采用 B 树的方式，这使得其扫描速度要快得多；

空闲空间管理

管理空闲空间的动作是必须的，因此这样当有新文件需要写入时，才知道将它存放到哪些空闲的数据块上；管理空闲空间的方式有很多种，例如位图、空闲链表（跟内存有点像）、B 树；不同的方式在时间和空间上面各有其优缺点；

为了让数据尽量连续存储，有些文件系统，如 ext2\ext3，在为新文件寻找空闲数据块时，会尽量一次寻找多个（例如 8 个）的连续空闲块，这样有助于后续提高文件的读定性能；

一个块有 4KB，8 个空闲块有 32 KB，一个扇区有 512B，因此 8 个空闲块约等于 64 个扇区；那么问题来了：磁盘在读取扇区数据时，一次性读入多少个扇区到缓存中？

访问路径：读取和写入

读取

当访问某个路径下的文件时，例如 open(“/foo/bar”)，实际发生的动作如下：

• 读取根目录的 inode 内容（在 UNIX 系统中，根目录的 inode 编号固定为 2，因此可以很快根据偏移计算出其磁盘地址）；
• 从根目录的 inode 对象中，得到其指向的数据块地址；（该数据块保存着根目录下的文件或子目录的元组列表）；
• 将根目录的数据块内容读取到内存中，遍历它，找到 foo 的 inode 编号，计算出 foo 的 inode 磁盘地址；
• 从 foo 的 inode 对象中，得到其指向的数据块地址；
• 将 foo 目录数据块内容读取到内存中，遍历它，找到 bar 的 inode 编号，计算出 bar 的 inode 磁盘地址；
• 读取 bar 的 inode 对象内容到内容中，检查读写权是否无误；
• 若无误，返回一个文件描述符，指向该内存地址，完成 open 的调用；

当文件打开后，调用 read() 时，实际发生的动作如下：

• 从 inode 对象中，获取指向的数据块地址；默认从编号为 0 的数据块开始读取（除非调用过 lseek 更改了偏移量）；
• 更新 inode 的最后访问时间字段为当前时间；
• 读取后，更新文件描述符对象中的当前数据块编号，以便下次读取时，可以从上次读取结束后的位置继续；

写入旧文件

将数据写入到磁盘还是涉及挺多动作的，除了跟读取一样，将路径先转换成 inode 外，接下来还涉及：

• 读取数据位图，为新数据分配某个空闲块；
• 更新数据位图，标记该空闲块的状态为“已占用”；
• 读取 inode；
• 添加新的 inode 数据块指针，让其指向刚分配的空闲数据块地址；
• 将数据写入数据块；

创建新文件

以上仅仅是写入数据到一个已存在的文件，如果是创建一个新文件，则涉及的动作还更多一些，包括：

• 读取 inode 位图，寻找空闲 inode；
• 将某个空闲 inode 位标记为已使用；
• 为新文件创建一个 inode 对象，将 inode 对象写入到 inode 表；
• 读取文件所在目录的 inode，找到其指向的数据块；
• 向目录的数据块中增加一条记录，映射新建的文件名和它的 inode 编号；
• 如果目录的数据块已满，则需要分配新的目录数据块，因此还需要读取数据块位图，寻找空闲块，并更新目录的 inode 对象，添加指向新数据块的指针；

缓存和缓冲

由于在读写文件时，有很高的磁盘 I/O 成本，因此，为了提高性能，引入了缓存机制，即在内存中，划分一片区域作为缓存；在首次读取时，将数据放入到缓存中；由于局部性现象的存在，后续的读取，大概率会命中缓存，而无须发生额外的磁盘 I/O；

另外还引入了延迟写入的策略，每隔一段固定的时间，将缓存中的新数据，写入到磁盘上，这种策略有以下几个好处：

• 如果某个块被多次写入，则最后只发生一次 I/O；
• 如果某个块最后被删除了，则完全没有发生 I/O；
• 待写入的数据暂时放在缓存中，意味着后续对该块的读写，可以直接读取缓存，无须通过 I/O 再次访问存储设备；

一般来说，延迟写入的时间间隔为 5-30 秒，但是它有一个缺点，即在写入之前，如果系统崩溃和停机了，待写入的数据将会丢失；有些应用程序对此无法容忍，例如数据库程序，因此它会直接调用 fsync 实现立即写入，避免延迟；

32.局部性和快速文件系统 FFS

早期的 UNIX 系统使用以上结构的文件系统设计，它本质上是将整个磁盘当作一个随机存取的内存来对待（但磁盘跟内存有所不同，内存的随机存取是很快的，但磁盘有寻道成本）；这个设计的好处在于它实现起来非常简单；缺点是随着使用时间的推移，最终将会导致文件的存储变得非常碎片化，从而带来很多的磁盘寻道定位成本（这也是当年为什么会有磁盘碎片整理工具这种东西出现的原因）；

问：如何设计和组织文件系统使用的数据结构，以提高访问性能？以及如何设计分配策略？

FFS：磁盘意识

解决办法也很简单，老式 UNIX 文件系统设计的问题在于将整个磁盘当作随机存取的内存使用，因此，有必要反其道而行之；由于暴露给用户的抽象是文件和目录；目录是让用户组织其文件的一种方式；这意味着用户天然会将相同组别的文件放在同一个目录中，而且由于局部性原理，用户在访问下一个文件的时候，跟上一个文件在相同目录的概率比较大；

接下来 FFS 要做两件事情：

• 将磁盘按柱面分成多个柱面组（很有点类似目录的味道；按柱面的原因在于相同柱面的寻道时间比较短）；
• 每个柱面组内部像是一个小磁盘，由一个超级块副本+两个位图+数据块组成（跟上章的简单文件系统一模一样）；
• 将相同目录下的文件，尽量放在同一个组中，避免跨组；（为了让各个目录尽量分散在所有组中，FFS 在放置新目录时，会特意寻找分配数量少的柱面组）

大文件例外

分组的另一点核心思想在于让各目录尽量平均分配到不同的组中，避免出现目录的存储出现跨组，不然就失去了局部性所能够带来的好处；但对于特别大的文件来说，它有可能会填满整个组并跨到下一个组，这样就破坏了局部性；

解决这个问题的方法之一是将大文件平均分配到各个组中，而不是在单个组中存储；当然，这样不可避免会带来多次的寻道成本，但这里面会有一个折中，即为了实现预期的传输带宽，应该将单组中的块设置为多大；

目前 FFS 的策略简单而粗暴，它将 inode 的 12 个直接指针指向的数据块和 inode 放在同一组，余下的每一个间接块，跟其指向的数据块，单独放在一个组；不同的间接块，放在不同的组（如果块的大小为 4KB 的话，磁盘地址为 32 位 4 个字节的话，则有 1024 个指针，其指向的数据块的总存储容量为 4MB）；

关于 FFS 的其他几件事

子块

当块的大小设置为 4KB 时，有利于提高缓存的命中率，从而提高磁盘的读取性能；但是如果磁盘上大量的文件都只有 2KB 的话，将意味着每个 4KB 的块中，都只有一半的空间得到利用，最终结果将导致磁盘的容量利用率只有预期的一半；解决思路是额外引入另外一种小规格的块（称为子块，sub-block），例如大小为 512B 的块，当某个文件少于 2KB 时，文件系统就为其分配子块；如果后续随着时间推移，文件变大了，则继续为其分配更多的子块，直到其大小达到 4KB 后，再为其分配规格为 4KB 的正常块，并将子块的数据复制过去；当然，这种方法带来了复制的成本，不过由于存在延迟写入的机制，这种复制通常只会发生在内存上，而不是在磁盘上；

磁盘缓存

当块在磁盘上是按编号顺序连续性存储的时候，将会带来一个问题，即当文件系统发出块 0 的请求后，再次发送块 1 的请求时，磁盘已经放置到块 1 的位置了，而磁盘解析请求本身是需要时间的，因此将错过块 1，需要再完整的放置一周后，才能重新定位到块 1；为了解决这个问题，早期的思路是让块在磁盘上进行跳跃布局，这样可以为解析磁盘请求争取到时间；不过跳跃性布局也会带来一个问题，即最多只能得到磁盘一半的带宽，因为块是间隔存储的；后来现代磁盘引入了磁道缓冲区技术，即在其内部增加了单独的缓存，每次将整个磁道的数据读取到缓存中，这样就不需要担心旋转的问题了；

33.崩溃一致性：FSCK 和日志

问：对于某条数据写入请求，磁盘上数据更新操作是有多个步骤的，而不是原子性的，例如需要分别更新位图、inode 记录、数据块等步骤；当在更新过程中，突然机器出现断电或系统崩溃时，文件系统如何让磁盘上的数据保持一致性的状态，而不是部分写入，部分未写入，导致冲突错误？

方案一：FSCK

FSCK，file system check，文件系统检查；思路很简单，当由于断电或操作系统崩溃等错误发生时，文件系统先啥也不做；然后等再次被操作系统挂载并可用之前，做一次检查，修复之前的错误；

FSCK 相当于做了整个磁盘的扫描工作，包括检查超级块、空闲块、inode 状态、inode 链接、重复指针、坏块指针、目录引用等；虽然这种检查方法是有效的，但是性能代价太高昂了，尤其是对于越来越大的磁盘，每次检查将花去几分钟甚至是几小时的时间；实现的目标仅仅某次写入涉及可能存在错误的3个块而已，很不值得；

方案二：日志

思路是在将数据写入磁盘之前，将本次要实现的操作，提前单独写在某个指定的地方，形成日志；这样在遇到崩溃的场景时，就可以从日志中提取原来要实现的操作，并检查这些操作是否按预期完成了，如果没有，就重复执行一遍相关的操作，确保它们完成；

数据日志

当发生文件的写入时，一般会涉及三个块需要更新，包括 inode、位图、数据块；物理日志的方式，是将这三个块的内容完整的写到日志中，并在其前后各包含一个标识开始 TxB 和结束 TxE 的事务块

TxB：Transaction Begin；TxE：Transaction End；

为了应对在日志写入过程中，出现断电或崩溃的场景，需要将日志的写入分成两部分，先写入头部和三个块，完成后，再写入事务的结束块，并将结束块的大小设置为 512 B，因为这个大小的块，磁盘的写入是原子性的；整个过程的顺序如下：

• 日志写入：事务头部块和三个块
• 日志提交：事务的结束块；
• 加检查点：将三个块写入磁盘；

恢复

系统崩溃会在两个时间点下发生：

• 日志提交前：忽略该段日志，数据丢失；
• 日志提交后：重放该段日志，按日志对磁盘再做一次操作，数据未丢失；

批处理日志更新

写日志的动作其实增加了额外的磁盘 I/O，因为除了更新文件和目录的块外，现在又要多一次更新日志块的动作了；为了避免因此带来的性能问题，通常的做法是先将日志数据缓存在内存中，形成一条全局事务，然后每隔一段时间，做一次批处理的更新，而不是每条日志事务单独更新一次磁盘；

如何在批量更新日志时，发生了崩溃，那么日志的内容将会丢失，如果此时有数据正在写入，貌似也会丢失？

循环日志

日志的内容会不断累积，最终超过磁盘容量， 为了避免这个问题，可以通过增加一个日志超级块，加完检查点后，每隔一段时间，将已完成检查点的日志标记为空闲可重用的状态；

元数据日志

物理日志存在两个方法的问题：

• 由于每个数据块需要写入磁盘两次（一次写在日志中，一次写在目标位置中），使得带宽只剩下原来的一半；
• 日志和目标位于不同的磁道，因为带来了额外的寻道时间成本；

解决办法：不将数据块写日志，只将元数据部分的内容写到日志中；（此种机制下，貌似需要先将数据写入数据块，之后再来写日志）

莫非这就是传说中的逻辑日志？

棘手的情况：块复用

删除文件和目录时，将带来一场噩梦！想一想，它会发生什么？

当采用元数据日志的模式时，数据块并没有写入日志，只将元数据写在了日志中；这意味着，与目录有关的更新由于都属于元数据，因此都会写在日志中；当用户在某个目录中添加某个文件时，由于目录的元数据会产生更新，因此，日志中有一条关于该目录更新的日志；

假设之后用户删除了整个目录，并重新创建一个新文件，当采用元数据日志时，日志和该新文件的数据会首先写入磁盘，假设此时写入的位置复用了此前删除的目录的块，然后在日志提交后，系统发生了崩溃；根据原本的协议，系统在恢复后，用户预期应该能够得到崩溃前写入的数据；

但是，此时事情并不能如预期一样发生；因为日志中还有一条关于目录的更新会被重放，而且它发生在创建新文件的日志之前，这意味着在重放时，原本数据块上的新文件数据，将会被覆盖；

有两种办法可以避免该问题：

• 在某条日志被标记为空闲前（即日志对应的操作已顺利完成，日志块将被复用），避免涉及的块的重用；
• 日志引入一种新类型的撤销记录，删除目录使用该记录；当重放时，此种类型的记录不重放；

问题1：当删除一个文件时，会发生什么？当在操作过程中发生崩溃后，会发生什么？

• 更新文件所在目录的数据块，删除文件的映射记录；
• 更新 inode 位图和数据块位图，标记为空闲；

以上几个动作需要打包成一个事务，写到日志中，以便确保操作是原子性的，避免文件系统出现不一致；

问题2：当删除一个目录时，会发生什么？当操作过程中发生崩溃后，会发生什么？

• 扫描目录中所有映射条目，获取每个条目指向的 inode；
• 获取每个文件 inode 指向的数据块指针；
• 将所有文件对应的 inode 位图和数据块位图，标记为空闲；
• 将目录对应的 inode 位图和数据块位图，标记为空闲；
• 更新目录所在的父级目录的 inode 属性和元数据块，删除映射；

由于没有 TxE 块的事务是无效的，因此 TxB 块和元数据块写入日志的请求，和数据块的写入请求可以并行发出，重点是 TxE 块的写入请求需要等待前面三个请求完成后才可以发出；

其他方案

除了 FSCK 和日志外，其他保持文件系统数据一致性的方案：

强制排序

对写入进行强制排序，这样可以避免磁盘出现不一致状态，例如先写数据块，再写 inode；

写时复制

copy-on-write；当发生写入时，不覆盖原文件或目录，而是写到空闲块，写完后更新目录结构，让指针指向新的位置；（如果写失败了，数据会丢失，但旧文件仍然保持一致性；貌似更新目录的操作需要是原子性的，避免更新一半的时候失败了）；

反向指针

在数据块中添加一个指向 inode 的指针；当发生崩溃时，比对 inode 中的数据块指针，和数据块中的 inode 指针是否匹配（问：如何快速知道哪些写入的指针不匹配？）；

事务校验和

不强制事务写入的顺序，而是通过事后计算校验和，来确定是否写入有效，执行成功；（此方法性能不错，但需要磁盘提供新接口；

问：如果在校验之前，系统发生崩溃会怎么样？

答：写入被当作无效，这样文件系统中不会发生一致性问题，但数据将会丢失好像？

34.日志结构文件系统

在读了原始论文后，我终于知道它为什么叫日志结构文件系统了，因为传统的文件是将日志做为一种辅助，临时存储目标数据，以便存储过程中发生崩溃时，可以从日志中恢复目标数据；但 LFS 则直接将目标数据存储在日志中，不再单独额外的存储一份目标数据，所以叫日志结构的文件系统，非常形象；

这样做有一个很大的好处是崩溃恢复非常快，无须做全盘检查，只需检查最后更新的那份日志即可；同时目标数据无形中得到了历史快照，可以任意恢复到某个历史版本（如果还没有被覆盖的话）；

寻道成本

FFS 快速文件系统在日常场景中的性能并不是特别好，因此每做一次文件更新，需要做很多次磁盘 I/O，虽然通过引入缓存，可以缓解这个问题，但这只是将多个 I/O 一次性发给磁盘进行顺序优化，实质上仍然不可避免磁盘内部的寻道成本和旋转成本，因为每个磁盘 I/O 并不是顺序写入；虽然这些写入由于分组的技术，通常在一个柱面组中，但仍然会带来短寻道和旋转延迟的成本；

考虑内存容量和磁盘传输速度在逐年增加，而寻道和旋转成本却进步缓慢，因此如果能够将文件系统改进为顺序写入，随着时间的推移，将获得越来越大的性能优势；

日志结构文件系统，log-structure file system 名称的由来在于它将整个磁盘当做一个循环日志来对待，就像写日志一样，每次新的写入，都写入到尾部，不覆盖旧数据；等日志写满了后，又重头开始写；

顺序写入

解决这个问题的办法有两点：

• 根据磁盘传输速度，设置足够大的缓存，一次性积累足够多的待写入数据；
• 将数据发给磁盘做顺序写入，以获得磁盘最大的带宽速度（一般为峰值速度的 90%）；

以上方案的挑战：

• 顺序写入意味着不现更新和覆盖旧的数据块，而是永远将数据写到新的数据块中；这意味着 inode 的位置将随着每次写入不断的变换位置，需要解决如何定位最新版本的 inode 的问题；（当使用顺序写入的时候，inode 的内容更新同 FFS 并没有什么不同，区别在于将 inode 更新后的内容写入磁盘的时候；LFS 是写入到新的位置，FFS 覆写原来的位置；因此，对于文件原本已有的数据块，仍由 inode 中的原有的指针指向着，没有变化）；

如何定位

由于 inode 的位置不断变化，因此需要有一个地方，保存指向最新版本的 inode 地址；LFS 使用 inode map（映射）来解决这个问题，类似于用 inode 编号和 inode 地址组成的键值对；给定一个 inode 号，根据映射将得到它的磁盘地址；

如果将 inode map 映射存储在某个固定的位置，则该位置在文件发生写入时，将不断避免的出现频繁更新，这样会增加寻道成本；因此将 inode map 也作为顺序写入数据的一部分，放置在 inode 右边；注意：imap 中保存着多个文件的映射信息，而不只是一个文件；

另外随着文件的增多，貌似 imap 的体积也会变得越来越大？怎么对应这个问题？另外是否需要标记已经删除的文件，回收 inode 编号？

虽然 imap 和 inode 一起放置，解决了频繁更新 imap 造成的顺序写入破坏，但是它同样导致 imap 本身也不是不断变化位置的。归根结底，仍然需要有一个持久的数据结构，保存着最新版本的 imap 位置；

检查点区域

解决定位 imap 的方案是引入一个检查点区域（CR，Checkpoint Region），它固定在磁盘的头部，其中保存着每个文件的 imap 地址；

由于随着文件写入时，检查点区域同样会出现频繁更新，因此为了避免由于带来的性能问题，它一般设置为每 30 秒更新一次，两次更新期间的数据先保存在内存中；这样就可以将多次 I/O 变成一次 I/O 了；

问：检查点区域是否存储着多个 imap？还是只有一个？好奇 CR 里面的内容长什么样子

答：CR 里面的内容包括 imap 所有块的地址、段使用表、时间戳、最后一个写入的段的指针；

读取文件

当发生文件读取时，文件系统从检查点区域找到 imap 地址，然后根据地址，将整个 imap 加载到内存中；接下来，根据需要读取的文件的 inode 编号，从 imap 数据中查找到该文件的 inode 地址；根据 inode 地址，加载到文件的元数据，并根据其中的数据块地址，读取到文件中的数据；

处理目录

当在磁盘上面创建一个文件时，不仅有文件数据需要写入磁盘，同时也需要更新目录数据；因此在顺序写入数据的时候，其实也在顺序写入待更新的目录数据，而由于目录的数据都是元数据，因此每次创建或更新文件，都一直在顺序写入目录中的所有内容（相当于目录的位置一直在发生变动）；

问题来了：根目录如何知道旗下各个子目录所在的映射区的位置？莫非映射区中保存着所有的文件和目录的 inode 映射？如果是这样的话，整个映射区就是一个完整的 inode 表；

如果映射块一直存放在内存中的话，那么读取起来的性能还是很快的；

映射区的设计，很好的规避了递归更新问题；每当创建一个文件时，文件所在的目录的 inode 也需要被更新，此时目录的新 inode 会和文件、新映射一起顺序写入磁盘的新位置；新映射中包含着目录 inode 的新位置，但该目录的 inode 编号并没有变，因此并不需要更新其父目录的 inode ；

从 imap -> inode -> 数据块的查找过程如下：

垃圾收集

问题：由于每次更新文件和目录，都是写入新的位置，这不可避免会导致部分旧的数据块失效，变成垃圾块；如果放任不管的话，虽然这些垃圾块并没有指针指向它们，但是它们会在磁盘的空间中形成很多小洞，使用大段连续的空闲空间变得越来越少，从而在未来需要顺序写入的时候，找不到大段的连续空间；同时文件系统也需要额外的机制，来标记这些空闲小洞，负担很大；

解决步骤1：不将磁盘作为一个连续存储空间来处理，而是将其分成很多个段，以段为单位来写入数据；每次需要写入新数据时，即使原来的段没有满，也写到新的段中；这样一来就可以减轻空闲标记的工作（感觉跟内存的分页机制有点像）；

LFS 在清理过程中，如果发现段中的部分数据块仍然是有效的，则会将多个段的有效数据合并复制到一个新的段中，然后将多个旧段回收；

突然发现内存有分段分页机制，磁盘也可以有；内存的分段对应不同数据，磁盘的分段对应不同目录均匀分页、相同目录尽量集中的原则；

解决步骤2：LFS 通过在数据块中增加一个头部，来解决空闲块标记的问题；这个头部包含两个信息，该数据块所属文件的 inode 编号，以及其在文件中的数据块索引号；基于这两样信息，文件系统可以到 imap 中找到当前 inode 块地址，并读取 inode 数据，核对相应索引号的数据块地址，看二者是否匹配；如果匹配，表示该块是活的，仍被 inode 指向；如果不匹配，则表示该块已经失效了，不再被 inode 指向，可以清理了；

LFS 还偷偷的在数据块头部中写入了文件的版本号信息；当文件发生重大变更时，例如被删除时，LFS 会在文件的 inode 中更新其版本号字段；这样后续在核对是否匹配时，如果版本号不同，则可以直接判断数据块失效，无须再核对数据块地址了，节省了一些时间；

清理策略

常见的思路有三种：定期、空闲时、磁盘已满；

崩溃恢复和日志

对于 LFS，最重要的一点是保证 CR 检查点区域的更新是原子性的，只要这点保证了，貌似就不会产生一致性的问题；为了实现 CR 更新的原子性，LFS 的做法是建立两个 CR，分别位于磁盘的头部和尾部，交替更新它们，这样某次更新过程中出现崩溃，仍然有一份旧版本的 CR 可以使用；

在更新 CR 的时候，文件系统会先生成一个时间戳，写入 CR 起始位置，再写 CR 主体，最后再写入 CR 尾部；这样如果更新过程中发生了崩溃，文件系统通过比对头尾的时间戳，如果二者不一致，则表示当前的 CR 是无效的；

问：LFS 需要日志吗？如果需要的话，日志保存在哪里？

答：貌似保存在 CR 中？假设文件系统每 30 秒将数据集中写入磁盘一次，则在写入完成前，如果发生崩溃，如果没有日志，这 30 秒的最新数据将会丢失；如果这个丢失是可以接受的话，则貌似不需要日志也是可以的；

预设前提

LFS 的整个设计是建立在磁盘的寻道成本过高的前提下的，这对于磁盘存储设备来说是成立的，但是对于闪存存储类型的设备来说，情况则有所变化，寻道成本开始变得可以忽略不计了；不过 LFS 的设计倒是提供了一个额外的好处，即文件系统意外获得了快照，出现意外情况下非常方便恢复旧版本文件；

35.数据完整性和保护

问题：当数据写入磁盘后，如果确保当数据从磁盘读取出来时，跟之前写入的数据是一样的？

磁盘故障模式

• 整个磁盘不工作了，stop and fail；
• 某个扇区不工作了，latent sector error；
• 某个块不工作了，block corruption；

整体来说，出现扇区故障和块故障的几率还是不小的：

项目	廉价	昂贵
扇区故障	9.4%	1.4%
块故障	0.5%	0.05%

处理潜在的扇区错误

问题：文件系统应如何处理潜在扇区错误？需要增加什么额外的机制，来处理该类型的错误？

当出现扇区错误时，还是很容易在第一时间发现问题的；因为文件系统尝试读取某个块，但由于该块所在的扇区不工作了，因此不能正常的返回需要的数据，此时文件系统就会发现扇区出现了错误；

接下来只需要使用已有的冗余机制，例如 RAID-1 的镜像备份，或者 RAID-4/5 的校验和，来重建损坏的扇区即可；

对于 RAID-4/5 来说，如果在多个磁盘上出现相同的扇区损坏，则无法重建成功了；

检测块错误：校验和

块错误跟扇区错误不同，它是一种无声的故障，因为当故障发生时，磁盘并不会报错，而只是悄悄的返回了非预期的数据；

问题：需要什么技术来检测无声的错误？如何有效的实现？

常见的校验和函数

异或 XOR

实现：假设最终的校验和是 4 字节的，则将整个块分成多个以 4 字节为单位的段，给每段相同位置的字节做异或计算；

优点：实现起来非常简单；

缺点：如果同个位置有两个字节处理错误，则异或计算的结果会显示正常，导致错误无法被发现；

加法

实现：对整个数据块执行二进制补码的加法，忽略溢出；因此只要有任何一个位或多个位的数据出现变化，整个加法的结果都将不同；

优点：实现简单；

缺点：如果数据出现移位，而不是翻转，则无法检查出错误；

Fletcher 校验和

实现：假设数据块 D 由 d1 至 dn 共 n 个字节组成；有两个校验字节 s1 和 s2，其中

• s1 = s1 + di mod 255
• s2 = s2 + di mod 255

优点：可以检测所有单比特和双比特的错误，以及大部分的突发错误；

缺点：计算稍复杂

循环冗余检验 CRC

CRC 全称：cycle redundancy check；

实现：将数据块 D 视为一个大的二进制数，并将其除以约定的值 k，得到的余数即是 CRC 值；

检验和布局

最终计算出来的检验和，需要在磁盘上安排一个位置来存储它，有两种方法：

磁盘厂商实现

将原本 512 字节的块，实际设置为 520 字节，这样多出来的 8 个字节刚好用来存储校验和；

文件系统实现

单独划分一个 512 字节的块用来存储校验和，每个校验和为 8 字节，因此 512 字节的块可以存储 64 个检验和，刚好对应其后的 64 个连续的数据块；不过这种方法有很大的缺点：即当某个数据块的数据发生改变时，需要同时更新校验和所在的块，增加了寻道、定位等 I/O 成本；

使用校验和

使用方法很简单，在读取某个数据块时，同时读取在磁盘上存储的检验和，并与根据数据块计算出来的校验和进行比较，

• 如果二者一致，就返回数据给用户；
• 如果不一致，如果有冗余机制，尝试进行恢复；如果没有，则报告错误；

错误的写入位置

问题：磁盘在写入数据时，有可能将数据写入到一个错误的地址上

为了应对该类故障，可以在校验和添加物理标识符，例如磁盘序号和块号；

丢失的写入

问题：磁盘报告它成功的将数据写入了，但实际上并没有；

这是一个很蛋疼的问题，当发生此类故障时，前面提到的所有校验机制都将无效，因为块上的旧数据符合上面的任意一条校验规则；一种解决办法是引入写入验证，例如写入后马上读取，但是 I/O 成本很高；

其他方法是在磁盘上的某个位置添加额外的校验和，例如在 inode 和间接块中，存储数据块的检验和，这样如果某个数据块没有成功写入，那么数据块里面的数据是旧的，其校验和跟 inode 中存储的校验和将不一致；

有一种极端情况是连 inode 中的校验和的写入也丢失了，这样就没有办法检验了；不过貌似数据块和 inode 的写入同时丢失是一个小概率事件，当然，任何小概率事件早晚都是有可能发生的；

不定期擦拭

虽然当文件被访问时，检验和将会被核对；但问题是绝大多数的文件在写入后，就很少被访问了；而由于磁盘本身的物理特性，在使用一段时间后，其上面的块可能会自行发生变化，此时将导致检验和出错；随着时间的推移，错误将累积得越来越多，最终导致当发现错误时，恢复工作已经无法进行；

为了避免这个问题，磁盘系统一般会定期对所有数据块进行扫描，以便及时发现错误和修复，保持它们始终是正确干净的状态；

校验和的开销

由于每 4KB 的数据块需要一个 8 字节的校验和，因此整体空间开销在 0.2%，是一个可接受的范围，成本很小；但是计算开销则比较大，因为现在每访问一个数据块，都需要对其做校验和的计算和比对工作；

为了降低 CPU 开销，需要特别优化，将数据块的复制和校验，组合一个单独的简化活动；另外定期的擦净工作一般选择在夜间进行，此时电脑处于低工作荷载的状态中；

36.基于闪存的 SSD

特点与构造

闪存有一个很有意思的特点，它在内部将存储单元分为块和页（块比页大）；当需要写入数据到某个块时，首先需要先将整个块的数据先删除掉，之后才能写入；而且，写入的次数是有上限的；因此，如果对某个页执行频繁的写入操作，将导致其很快老化；

猜测之所以需要先删除，是因为需要让该块处于某种重置后的状态，在该状态下，块可以被放入电子；但是当电子放入后，就会破坏这种状态，导致无法再额外放入或取出电子；如果要写入新数据，则只能将整个块重新初始化；

问：如何构建闪存 SSD？如果应对昂贵的擦除成本？如果重写会缩短磁盘寿命的话，如果构建持久使用的磁盘？

闪存的基本存储原理，是通过存储在晶体管中的电子数量，来判断该比特位所存储的值的；

• 单层：如果电子数量超过某个临界值，则表示 1；反之表示 0；
• 双层：有多个电子数量的临界点，分别表示 00、01、10、11；
• 三层：原理同双层相似，差别在于可以表示 3 个比特位，即 000 ~ 111；

虽然层数越多，单个存储单元的容量越大，单位价格越低，但是性能会下降；单层的单位容量小，但性能最好；

从位到片

显然 SSD 存储器操作的最小单元不可能是比特，而是一个更大的存储单元“页”；SSD 一般由多块存储片构成，每个存储片中有 n 个块；每个块中有 n 个页；

• 块大小：128 ~- 256KB（相当于 32 ~ 64 个页）
• 页大小：512B ~ 4KB；

以块为单位的操作

闪存芯片一般支持三个低级别的操作：

• 读取（页）：给定页编号即可，非常快，没有寻道成本，随机读取和顺序读取的性能几乎相同，约 10 微秒；
• 擦除（块）：将数据写入指定页前，需要将页所在的块上面的数据全面清除，之后才能写入（原因很简单：闪存是以存储单元中的电子量来表示值的，因此需要先将存储单元设置成某个初始化状态，之后才能够正确的放入电子）；擦除的成本比较高，需要约 1 毫秒（跟读取的速度相差 100 倍）；
• 写入（页）：当某个块被擦除后，就可以开始往里面的页写入数据了；写入的时间成本约 100 微秒；

写入过程

根据页号找到所在的块，此时整个块的状态为 VALID（表示其上面的数据可读）；

将块的状态变更为 ERASED（此时块上所有页中的存储单元，都会被置为 1）；

根据页号，将某个页中存储单元的电子量设置为预期的状态（设置成功即表示数据写入成功），写入完成后，该页的状态会从 ERASED 变成 VALID；

问：好奇剩下的三个页仍为 ERASED 状态，那么未来再向它们写入数据时，它们会处于什么样的状态？是否需要重置整个块？

答：貌似剩下的三个页下次可以直接往里面写入数据；只有当需要向已经是 VALID 的存储单元写入数据时，才需要将整个块重置为 ERASED 状态；

性能与可靠性

老化

闪存由于全部是硅晶体管构成的，没有传统磁盘中的机械结构，因此它出现故障的可能要比传统磁盘低一些（例如肯定不会出现磁头撞到盘面的情况）；闪存主要的问题是老化，因为每次向存储单元写入数据时，是往里面放入电子；每次清除其中的电子时，都会有一些残留；随着时间的推移，这些残留会累积；当累积到一定的程度后，就很难用该存储单元的电子数量来区分它当前是处于 0 还是 1 的状态了，这个时候该存储单元便不再可用了；

闪存生产商的数据是单层 SLC 的可擦写次数大约在 10 万次，双层 MLC 大约在 1 万次（但目前还不是非常确定，因为第三方的实验数据发现寿命好像比预想的还要更长一些）；

干扰

另外一个会影响可靠性的点是干扰；当某个存储单元被读取或写入时，有可能会干扰旁边存储单元中的电子数量；当干扰超过某个临界点时，会造成位翻转，导致单元中存储的值不再准确；

从存储片到 SSD

在 SSD 出现之前，传统机械磁盘已经和文件系统形成了成熟的接口，因此 SSD 需要提供向后的兼容性， 以便能够让文件系统无感知的使用 SSD；

为了实现向后的兼容性，SSD 提供了一个中间的翻译层 FTL，Flash Translation Layer；它负责提供跟传统机械磁盘一样的接口，供文件系统调用，并将其翻译成内部指令；

为了提高性能，SSD 一般会将数据并行写在多个闪存存储芯片上（这点跟有多个盘面的机械硬盘其实是一样的）；另外需要降低写放大；

写放大 = FTL 发给闪存芯片的指令数量 / 文件系统发给 FTL 的指令数量

为了提高使用寿命，FTL 需要将数据尽可能均匀的写入到所有存储单元中，避免某些存储单元被写入的更多，导致过早老化；

为了减少写入干扰，FTL 通常会按页的顺序写入数据，从低页写到高页，避免无序写入，减少干扰几率；

实现 FTL 的最简单方式是使用直接映射，但是这会带来非常严重的问题，一是性能问题，因为写入页需要擦除块，因此会需要先复制块中的数据，之后再重新写入，这导致高昂的写入放大；二是寿命问题，文件的元数据不可避免会频繁更新，因此直接映射将导致某些存储单元也频繁更新，很快达到使用寿命的上限；

日志结构的 FTL

文件系统中常用的日志结构刚好非常适合 FTL 的场景，每次更新数据的时候，都不覆盖旧的数据，而是在新的位置写入；

对于文件系统来说，哪些空间是空闲的，是由它自己在管理的，这意味着文件系统有自己的一套块编号系统，该系统与 SSD 内部的页编号并不相同，因此 SSD 内部还需要提供一张映射表，记录文件系统的块，对应自己内部的哪个页；

示例：文件系统的块 100、101、2000、2001，对应内部的页 0、1、2、3；

问题：SSD 需要将映射表存储在哪里？

答：理论上猜测肯定是存储在 SSD 本身的存储单元里；对于日志结构策略来说，整个文件系统 imap 表是不断移动的，即随着数据更新，不断写入到最新的位置；而且单个文件的 inode 也会随着更新，不断在变化位置；数据块也是如此；只有当 inode 和数据块中的数据没有发生改变时，它们的位置才是固定的；

但是以上的分析是站在文件系统的角度，对于 SSD 来说，它还有额外的一个翻译映射层，即需要将文件系统的逻辑块，映射到自己的物理块地址；这个映射表是独立于文件系统的 imap、inode 之外的；它是对 inode 中读取到的指针的再次翻译好像？

没错，而且有些 SSD 内部还有专门的 RAM 内存，用来在运行时加载该映射表，以提高翻译的速度；当然，有些 SSD 的策略是加载到主机的内存里，共享主机的内存，但由于不能无限占用主机的所有内存，肯定会设置一个上限；有可能这个上限小于整个映射表的大小，此时只能加载部分映射表到主机的内存中；由此当发生缓存不命中时，就需要先从闪存中读取未命中的映射数据，加载到内存里；这样的话， 对于主机来说，一条读取数据的指令，其实发生了两条从闪存中加载数据的指令，一次是加载映射表，一次是加载目标数据；

发现 SSD 内部的页表映射机制，跟 CPU 的虚拟内存地址映射是一毛一样的；

日志结构的 FTL 有两个缺点：

• 由于新数据总是写入新位置，而不是覆盖旧数据，这意味着旧位置的数据变成垃圾，需要定期清理，以便能够回收空间；但过度的垃圾回收会增加写放大和降低性能；
• 随着 SSD 容量的变大，SSD 内部需要越来越大的内存，以便能够存储映射表；

垃圾回收

对于任何使用日志结构的系统来说，垃圾回收都将是不可避免的；当 SSD 决定运行垃圾回收时，它可以通过读取页中的块编号，并查询映射表，但相应的块编号指向的页编号是否匹配，如果不匹配，意味着该页已经变成了死页，或者叫垃圾页，可以进行回收；如果块中只有部分页是死页，部分页是活页，那么回收成本很高；因为 SSD 需要先将活页的数据复制出来，并写入到新的页中；为了降低回收成本，更好的办法是优先回收那些全部由死页构成的块，这样就不需要复制和写入数据了；

以上机制的成本仍然不低，因为需要扫描整个 SSD；由于文件系统本身也维护着空闲空间的管理，因此文件系统自己也清楚哪些逻辑块是垃圾块；SSD 可以通过提供一个额外的 trim 接口，让文件系统调用，告知哪些块可以释放，然后直接在 FTL 释放它们即可，少去了扫描的成本；

问：好奇 SSD 内部 FTL 如何管理自己的空闲空间？还是说直接不管理，交给文件系统来处理？万一有的文件系统没有这个功能呢？

映射表尺寸

块映射

块映射是一种直接映射，目的是为了减少页表的大小时，因为如果按页进行直接映射的话，假设一条映射条目（页指针）需要占用 4 比特的空间，对应一个 4KB 的页；那么对于 1TB 的 SSD 来说，将需要 1GB 缓存以存储映射表，显然，这个映射成本太高了；如果换成使用块映射（块指针）的话，可以省下缓存空间，但是付出的代价是降低了性能，因为任何一个页的数据变更，都将导致整个块的迁移重写；

混合映射

为了解决块映射的性能问题，FTL 引入了混合映射；它的策略是使用两个映射表，一个是日志表（负责页映射），一个数据表（负责块映射）；这样既能够得到页映射的性能，又能够得到块映射的空间；

当 FTL 收到文件系统的数据读取指令后，优先到页映射表中查找物理地址，如果找不到，再到块映射表中查询；

貌似优先到页映射表中查找，可以利用上局部性原理的好处；

当 FTL 收到文件系统的数据写入指令后，先将数据写入新的块，然后将新块的地址保存页映射表中；当某个新块中的页都按顺序被写满后，就把该块的地址迁移到块映射表中；

切换合并

块中的页写满后，由原来的页映射切换为块映射；

部分合并

假设出现了只有部分页被重写的情况，则 FTL 需要将未被重写的页，复制一份到新的块中；完成这个动作需要额外的 I/O 操作，因此会导致一定的写放大；

完全合并

假设某个日志块中的四个页，分别写入了四个不同的逻辑块的数据；当需要将它们从日志表迁移到数据表时，就需要做很多动作；需要读取每个逻辑块余下的页的数据，然后新建一个物理块，写入这些数据；同样的操作，每个逻辑块都需要做一遍，共做四遍；

页映射缓存

由于混合映射过于复杂，另外一个解决方案是仍然使用页映射，但为其引入缓存机制（这个机制跟 CPU 中的虚拟内存地址映射缓存一毛一样）；其思路就是使用有效的缓存，来完成映射的工作；由于缓存有限，此时不再能将整个映射表一次加载到缓存中了，只能是部分加载（并且如果满了后，还需要剔除部分不常用的）；由于计算过程中必然存在的局部性，这种机制工作起来能够取得性能和成本的良好平衡；

减缓老化

为了避免某个存储单元由于频繁擦写，导致过快出现老化， FTL 需要尽可能的将写入分摊到所有存储单元中；虽然日志写入策略，能够很好的实现分散化；但是电脑中的部分数据有可能在写入之后，就很被再次改写了，这样导致这些存储单元没有分摊到应尽的责任；为了避免这个问题， FTL 需要定期将这些不活跃的数据，迁移到其他存储单元，以便激活它们，承担更多的写入责任；

看来 FTL 还需要额外承担不时照看那些数据长期不更新的块，不定期把块中的数据迁移到其他写入次数比较多的块，以便可以利用这些数据长期不更新块的使用寿命；

性能和成本

SSD 的随机写入之所以比随机读取性能更好，其原因在于内部 FTL 使用的日志策略；该策略将随机写入在一定程度上转变成了顺序写入；

按理说机械硬盘也存在着相同的现象；

37.分布式系统

分布式系统需要应对诸多方面的挑战，包括机器故障、数据包丢失、网络延迟、安全保障等；

通信常态

不可靠的通信是网络中的常态，少数情况是由于电气原因引起的，多数是由于某个节点的缓冲区不足造成的；由于该节点在单位时间内收到了超过其本身内存可存储的数据包，迫使其必须丢弃一些后到的数据包，因此造成了丢包的现象；

问：既然丢包是网络中的常态，那应如何应对丢包的问题？

答：从通信协议入手；

不可靠的通信层

应对不可靠通信的方法之一是：不管它；因为对于某些应用程序来说，丢失一些数据包问题不大（例如视频类的应用）；或者其内部有其他应对丢包的方法（例如通过校验和确认完整性，当发现丢包时，要求对方重发）；

可靠的通信层

构建可靠的通信涉及到四个动作：

• 确认的动作：acknowledgment，简称 ack；当接收方收到数据包后，发送一条 ack 消息给发送方，让发送方知悉数据包已经安全到达；
• 判断超时的动作：timeout；当发送方在一定的时间内，未收到接收方发回的 ack 消息，则判断数据包在传输的过程中丢失了；
• 重试的动作：当发送方判断数据包丢失后，重新发送一次数据包；
• 编号的动作：如果接收方发送的 ack 消息在路上丢失了，发送方会重新发送数据包；为了让接收方知悉收到了重复的数据包，双方就每次要发送的数据包进行顺序的编号；这样如果接收方收到相同编号的数据包，则只需要发回 ack 消息，而无须额外处理该数据包；

超时时间的设置是一个有意思的点，设得太小的话，发送方要消耗更多的 CPU 和带宽；设得太大的话，发送方提供的服务性能降低；

由于单个服务器经常对应多个客户端，因此有可能某个时间点，服务器会收到很多客户端的请求，导致过载；如果这些客户端都在一个固定的超时间隔后，再次发起重试的请求，将再次导致服务器过载，之后一直不断陷入死循环。为了避免这种情况发生，一般重试的时间间隔采用“指数倒退”的方案，即下一次重试的时间，是上一次的倍数，例如2倍；

分布式共享内存

DSM，Distributed Shared Memory，它的构想是我台机器共享一个大的虚拟地址空间，当访问某个不在本地内存中的数据时，触发页错误，然后由操作系统调用网络通信，访问其他机器上面的数据；

这种分布式方案不是很有实用性，因为本地机器的优点在于 CPU 和快速的内存，现在将内存做成分布式的，反而自断长处了；更好的做法可能是将数据做成分布式的，将数据通过网络分发到多台机器上进行计算，最后再网络汇总各台机器的计算结果即可；

远程过程调用 RPC

RPC，remote procedure call；其思路是像调用本地机器上的函数一样，调用远程机器上的代码并执行它；RPC 系统通常由两部分组成，存根生成器（stub generator）和运行时库（runtime）；

存根生成器

既然是远程调用，不可避免涉及到与远程的机器进行通信，如果每个调用的应用程序，都需要自己处理这些通信的细节，既低效也容易出错。因此，所谓的存根生成器，其实就是对通信动作的抽象，让调用它的应用程序，可以不用关心底层的实现细节，像调用普通函数一样调用 RPC 即可；

好奇存根生成器跟普通的 HTTP 请求有什么本质上的区别？

客户端存根生成器执行的动作：

• 创建缓冲区（申请一段内存空间）；
• 将消息放到缓冲区中：包括调用的函数 ID、函数参数、消息长度等；
• 将消息发送到 RPC 服务器上；
• 等待回复
• 收到回复，解包返回的数据，例如状态码、调用结果等；
• 返回结果给调用者；

服务端的存储生成器执行的动作；

• 解包客户端发过来的消息：提取函数 ID 和参数；
• 调用实际的函数；
• 打包结果，放入回复的缓冲区；
• 发送结果给客户端；

运行时库

运行时库才是真正处理底层的脏活和累活，例如机器路由、传输协议等；它的职责是解决性能和可靠性的问题；

为了提高调用效率，运行时库一般构建在 UDP 协议上，然后将可靠性交给运行时库自己内部来处理；虽然 TCP 协议可以帮忙处理可靠性的问题，但由它处理的层级比较低，并不能取得最好的性能；

其他问题

多久超时

虽然设置了超时机制，但并不是万能的；因为有些远程调用本身确实需要很长的处理时间，如果一刀切的将它们判断为调用失败，并重新发送消息显然是不合适的；此时应该向服务端请求最新状态，如果对方回复仍在处理中，则应该继续保持等待；

超大参数

有时传输的参数可能很大，此时运行时库需要提供消息的分组功能和重组功能；

不同字节序

还有另外一个讨厌的问题是不同的机器可能使用不同字节序，有些使用大端法，有些使用小端法；因此，RPC 通常会在其消息体中明确标识当前消息内容所使用的字节序，以免对方弄错，并根据需要进行转换；

单台机器的故障概率是很小的，但是当一个系统是由几千台机器组成时，故障变成了大概率的事件；因此，如何正确有效的处理故障，则构建分布式系统的首要问题；

38. Sun 的网络文件系统（NFS）

如何构建共享文件系统？要考虑哪些问题？哪些点容易出错？

基本分布式文件系统

通常情况下，应用程序访问本地的文件系统来获取想要的持久性数据，对于分布式文件系统来说，应用程序改成访问客户端文件系统，它提供了一层抽象，接口仍然同普通的文件系统一样，所以对于应用程序来说，是透明无感知的；

开放协议

最早的比较成功的分布式文件系统是 SUN 公司开发的 NFS，它通过制定协议的标准，引导行业人员采用该协议，并可以自行开发自己的 NFS 服务器，而不是限定只能使用 SUN 公司的版本，这种做法使用该协议迅速成为行业的标准；

目标：简单快速的崩溃恢复

对于多客户端单服务器的场景来说，实现快速的崩溃恢复是非常重要的，因为在崩溃期间，客户端完全无法使用文件系统；NFSv2 采取的做法是使用无状态的协议，这使得服务器端无须管理客户端当前的状态，从而最大程度的降低崩溃恢复成本；

无状态与映射

普通文件系统的系统调用是基于有状态的场景来设计的（例如使用文件描述符），如果想在客户端和服务器之间实现无状态的协议，就需要对原始的系统调用做一次封装；它们之间不可以是简单的 RPC，只是传递函数名称和参数，而是应该传递更多更完整的文件信息，包括卷标识、文件 inode 编号等；NFSv2 通过引入文件句柄来实现这一目的，每次通信，客户端都需将文件句柄传递给服务端，用来告知服务器自己想访问的是哪一个文件；

文件句柄：用来唯一标识服务端文件或目录的一种机制；它的思路其实很简单，本来文件系统上的各个文件原本就有唯一标识，现在将这些唯一标识的信息封闭成文件句柄的形式；这样当客户端给出某个文件句柄时，就能定位到某个具体的文件或目录；同时客户端会发送对这些文件的操作名称（即系统调用名称），服务端按要求进行操作即可；

世代号：一个新玩意，用来标识当前客户端读取的文件位置的状态；

虽然服务器端是无状态的，但是客户端的文件系统是有状态的；它会创建本地的文件描述符，来映射服务器返回的文件句柄，并且记录当前文件的位置，之后做为偏移量的参数，包含在请求中，发送给服务端；

客户端文件系统有维护一张映射表，映射每个路径下的文件和目录在服务端的对应句柄；

处理服务器故障

通信故障是网络常态，因此客户端发出的请求有可能在中途丢失，另外服务器端也有可能处于崩溃重启的状态，无法正常响应客户端的请求；客户端通过超时重试的机制，来应对通信故障的场景；

对于大多数的只读操作来说，不管客户端发出几次相同的请求，最终得到的结果都是一样的（即这些操作具有幂等性）；

对于写操作来说，也是幂等的，因为在相同位置多次写入数据，最终得到的结果仍然是相同的；

对于创建目录的操作来说，则没有幂等性，因为如果目录已经存在了，则再次创建会返回失败的消息；

提高性能：缓存

就像本地机器在将数据写入硬盘时，会使用缓存机制实现集中批量写入，以提高性能的做法一样 ，客户端文件系统与服务端之间，也可以引入缓存；让数据的读取和写入的性能更好；

缓存一致性问题

当多个客户端都对同一份文件中的数据进行缓存时，就会出现缓存一致性的问题；因为有可能某个客户端在其缓存中更新了文件数据，但暂时未推送到服务器上面，则此时其他客户端看到的仍然是旧版本的数据；

貌似可以引入类似 git 的文件版本管理机制；

NFS 通过两个机制来解决缓存一致性问题：

• 关闭时刷新：当客户端关闭某个文件后，出现缓存中有一些更新未推送到服务器，则将马上触发推送。以便其他客户端随后登录文件系统时，能够看到最新版本的数据；
• 打开时检查：当客户端访问某个文件时，如果发现本地已经有缓存，此时它会先向服务端发送一个请求，检查服务端的版本是否和本地缓存一致，如果不一致，则不使用缓存，而是从服务器拉取最新的版本；

客户端在检查本地文件缓存是否为最新版本时，需要设置一个检查的时间间隔，避免过于频繁的向服务器发起请求，不然服务端会收到大量的 GETATTR 请求，但实际上在大部分时间内，文件本身并没有什么变化；

服务端缓存的隐藏问题

不止客户端会使用缓存机制，事实上服务器端的内存与硬盘的交互之间，也存在缓存机制，这会带来一个隐含的一致性问题；即如果服务端在收到某个客户端的写入请求后，并没有将数据立即写入持久性设备硬盘，而只是先写在了内存中，并向客户端报告已经成功写入；如果此时服务器发生崩溃，则未写入的数据将会丢失，但是客户端却误会以为已经成功了；

这个问题很棘手，并且不可避免，有两种常见的应对办法：

• 在服务端增加一个有备份电池的内存，这样即使服务端出现断电或崩溃，数据也不会丢失；
• 服务端使用专门为快速写入磁盘而设计的文件系统，以避免普通磁盘在处理立即写入时产生的性能问题；

39.Andrew 文件系统 AFS

AFS 版本1

版本一的设计思路是全文件缓存，即首次打开文件后，就将整个文件下载到本地磁盘，后续的读写操作都在本地运行，调用本地文件系统的接口即可，无需网络通信，性能很好；当文件关闭后，再将修改传输回服务器；

第二次打开文件时，会检查文件的本地版本和服务器版本是否一致，若一致，则直接使用本地副本，不再从服务端拉取；

存在的问题：

• 路径查找成本比较高：每个客户端发送一个请求，服务端都需要按完整的路径进行文件定位，消耗了很多服务器的CPU 时间；
• 类似 NFS，客户端发出很多版本检查的请求，占用了大量服务端的 CPU 和带宽；

AFS 版本2

针对版本1存在的问题，版本2引入了以下的解决方案：

• 反复查询状态问题：引入了回调机制，即文件版本是否变更，不再由客户端发起查询，而是由服务端来通知客户端（貌似这需要保持一个长连接，不然通知不到了）；
• 反复查找路径问题：引入文件标识符（FID，file Identifier，类似 NFS 中的文件句柄）来替代路径名；客户端在查找路径过程中，缓存结果在本地，这样下次查找，可以通过本地缓存找到路径对应的文件标识符，之后发送标识符到服务端即可，避免了服务端反复查找路径的问题（貌似借鉴了 NFS 中文件句柄的机制）；

注意：每次客户端从服务端获取一个文件或者目录时，都会在服务端建立一个回调，以便让文件或目录有变更，服务端可以通知客户端更新；

后来发现服务端的更新通知非常简单粗暴，只是中断回调而已，其他啥事也没有做；当客户端发现回调中断后，就到服务端重新拉取最新的版本；

缓存一致性

更新可见性和缓存过期问题：当客户端关闭一个文件时，如果文件发生了变更，客户端就在第一时间将文件推送到了服务端；之后服务端会中断其他打开该文件客户端的回调；这样其他客户端就在第一时间知道了文件发生了更新，顺带解决了缓存过期问题；

当同一个客户端的不同进程，打开同一份文件时，由于本地缓存的存在，A 进程对文件的更新，对于 B 进程来说是实时可见的，因为它们都是访问的本地缓存，虽然此时服务端的版本可能是旧的，因为本地缓存的更新暂时还没有推送到服务端；

如果两个客户端同时修改一个文件，AFS 执行最后更新者胜出的策略，即以最后一个将更新推送到服务端的版本为准；

崩溃恢复

崩溃有两种情况，一种是客户端崩溃，一种是服务端崩溃；

当客户端崩溃后，其原本和服务端建立的连接将失效，此时如果服务端的文件发生了变更，则服务端将无法通知客户端该变更；因此，客户端在崩溃恢复后，应该将本地的缓存视为可疑，重新和服务端建立连接，并确认版本是否有过期；

当服务端发生崩溃后，由于回调都存储在内存中，因此所有的回调将失效，服务端再也无法主动联系客户端并推送消息了；有两种办法可以解决该问题：

• 客户端定期检查与服务端的连接是否正常，如果发现服务端掉线，则立即将本地所有缓存标记为可疑，之后当访问本地缓存时，就跟服务端确认一下版本；
• 当客户端和服务端再次建立连接后，服务端主动告知客户端其本地缓存应该标记为可疑；

此处碰到的问题，都很像是使用 websocket 进行消息通知时会遇到的问题；

扩展性和性能

优点：

• AFS 受益于在本地磁盘缓存整个文件内容，因此虽然大多数情况下，AFS 和 NFS 的性能差不多，但如果是机器重启后，对文件发起第二次的访问，则 AFS 将胜出，因为 NFS 没有本地磁盘副本，将需要再次通过网络下载文件，导致慢很多；
• AFS 另外一个优点是增加了扩展性，因为减少了很多请求的处理，单台服务器能够支持的客户端数量变得更多了；

缺点：

• 由于 NFS 缓存的是文件中的某个块，而不是整个文件，因此在某些场景下，它的性能将优于 AFS，即对文件中做出局部修改时，此时 NFS 可以只从服务端拉取对应的块即可，然后改写后推送到服务器；此时 AFS 需要先将整个文件从服务端下载下来，占用了很多时间；另外，改写完后，还需要将整个文件再推送回服务端，如果文件很大的话，速度将会很慢；

没有完美的系统，只有根据工作场景选择最匹配的系统；

貌似 AFS 的机制很像 github 的机制；

40.虚拟机管理程序

VMM：virtual machine monitor，虚拟机管理程序（hypervisor），它可以实现在现在的操作系统中，额外添加一层虚拟化；

用途

• 开发人员：方便在同一台机器上，实现不同 OS 下的代码调试和测试；
• 普通用户：方便在同一台机器上，使用不同 OS 下的应用程序；
• 运维人员：提高服务器的硬件资源使用率；

虚拟化 CPU

VMM 的职责需要对安装在其上的虚拟操作系统模拟一切的硬件，包括 CPU、内存、磁盘等；对于普通操作系统，在启动的时候，它会将各种异常处理例程的地址，提前写入到硬件中，以便在发生异常时，硬件可以根据地址，找到异常处理程序来处理异常；对于 VMM 来说，当它启动一个虚拟操作系统时，它需要拦截虚拟操作系统发出的写入异常处理例程的指令，并记录下指令内部的异常处理程序地址；

由于 CPU 本身是受限直接执行的，因此很好奇 VMM 如何让虚拟 OS 在执行到特权指令后，能够陷入到自己的代码，而不是触发错误？猜测此处需要 CPU 的支持才行，即 CPU 必须支持除了内核模式和用户模式外的第三种甚至第四种模式，虚拟 OS 运行在这种模式中，并且在该模式下，虚拟 OS 发出的特权指令，会触发 VMM 已经提前在 CPU 中写好的自己的异常处理，然后接下来陷入 VMM 的代码，由 VMM 接管并处理虚拟 OS 发出的特权指令；

由于 CPU 对于内部程序来说是完全透明的，因此应用程序发出的全部是 CPU 可以直接解读和处理的指令集；当 VMM 监控到应用程序发出了系统调用时（如何实现监控？或许可以考虑让虚拟机的应用程序运行在某种特殊的用户模式下），里面其实包含一个触发异常的指令（正常情况下，执行该指令会陷入系统，即切换到操作系统提前指定的异常处理程序，并切换到内核模式）；当 VMM 发现应用程序发出这种指令时，VMM 就拦截它，并替换成之前记录的虚拟 OS 的异常处理程序的地址；CPU 根据该地址，读取内存中对应的异常处理程序，开始处理应用程序发出的系统调用；

由于虚拟 OS 内部的应用程序也是受限直接执行的，因此当它发出系统调用时，它也应该是要触发 VMM 在 CPU 中提前写入的异常处理程序，让其陷入 VMM 的代码，由 VMM 来接管应用程序发出的系统调用，而不是由陷入主机的 OS 进行处理；

不同虚拟 OS 之间的切换

VMM 有可能同时管理着多个虚拟 OS，当想实现不同的虚拟 OS 之间的切换时，VMM 需要记下每个虚拟 OS 的状态，包括各个寄存器、程序计数器（PC）的值等；切换时，VMM 就把这些值写入到 CPU 中的寄存器和 PC 中，这样就实现切换了；

通过时间分片，CPU 定期陷入到内核模式中，执行 OS 的代码指令；好奇在 VMM 下，由于 VMM 只是一个普通的应用程序，它如何确保分配到足够多的时间片，来运行其中的虚拟 OS 的虚拟应用程序？还是说，这些虚拟的东西加在一起，能够分配到的时间片，只是跟主机上面的应用程序的比例是一样的？

普通 OS 下的应用程序实现系统调用

在普通的 OS 环境中，当应用程序想要执行某个系统调用时，它提前先将各项参数准备好，写入寄存器中，然后执行约定好的特殊指令；CPU 在收到这条特殊指令后，找到之前 OS 给它的该特殊指令的映射地址，写入程序计数器，并更新状态为内核模式，接下来舞台就交给 OS 了；

VMM 必须拦截虚拟 OS 的特权操作

VMM 不可能让虚拟 OS 实现特权操作，因为 VMM 本身也只是一个普通进程，并没有权限去帮忙虚拟 OS 实现任何的特权操作，因此它必须想办法拦截虚拟 OS 发出的各种特权操作，不然如果直接让指令进入 CPU ，会触发异常，并导致程序终止；

问：如何拦截呢？有一个办法是当虚拟 OS 尝试执行特权操作时，就让它陷入 VMM 中；这样 VMM 就有机会记录到特权操作的内容，知道某个虚拟 OS 的异常处理程序，在内存中的地址；有了这个地址后，VMM 之后就可以扮演成一个硬件的角色；

那如何让虚拟 OS 的特权操作能够陷入到 VMM 中呢？暂时想到的一种办法是让虚拟 OS 运行在某种特定的内核模式下，在该模式下的特权操作，会陷入 VMM 中；

VMM 必须拦截虚拟应用程序的系统调用

在普通 OS 下，应用程序的系统调用，会交给 OS 处理；由于 CPU 虚拟化使用的是受限直接执行的技术，因此 VMM 也必须拦截虚拟环境中的应用程序发出的系统调用，不能让它触发 CPU 中的主机 OS 的异常处理程序

问：如果主机的 OS 和虚拟 OS 版本一样的话，说不定也可以，即虽然操作不正确，但结果可能正确？不过这样做貌似很危险，因为虚拟应用程序在主机 OS 和虚拟 OS 的进程表中的代号并不相同，因此应该并不可行；

内存保护

对于虚拟 OS 中的应用程序来说，需要限制其访问虚拟 OS 的数据，但是此时虚拟 OS 本身也是一个普通的应用程序，它的数据并不是存储在内核段中的；有两种办法可以解决这个问题：

• 额外的内核模式：MIPS 硬件提供了额外的管理员模式，可以让虚拟 OS 存放自己的数据，这些数据对普通应用程序不可访问；
• 内存保护：VMM 使用页表保护，让虚拟 OS 的数据仅对 OS 可用，对虚拟应用程序则不可访问；（当虚拟应用程序尝试访问虚拟 OS 的数据时，让其陷入 VMM，然后 VMM 检查地址是否合法）

虚拟化内存

虚拟化方式

问题：VMM 如何虚拟化内存？

答：莫非 VMM 使用基址映射，来帮忙 CPU 找到真正的 虚拟 OS 的指令地址？正确答案是，VMM 需要提供额外的一层映射，将机器内存虚拟化一层物理内存出来，让虚拟 OS 的地址空间和真正的机器内存之间，实现映射；而且，这种实现必须是透明的；

听上去 VMM 还需要扮演类似 TLB 的地址翻译角色；

由于虚拟 OS 可能不止一个，因此 VMM 需要为每个虚拟 OS 维护一张单独的映射表，这张映射表的大小取决于初始化的时候，为虚拟 OS 分配了多少机器内存；然后虚拟 OS 对物理内存的任何写入，都由该映射表转换到对本地机器内存的写入，并在表上记录着映射关系；

问：地址转换的过程是怎么样子的？

地址转换过程

• CPU 执行应用程序（虚拟OS中的）的指令，发现 TLB 缓存未命中，触发陷阱；
• 陷入 VMM 的缓存未命中处理程序；VMM 找到之前保存的虚拟 OS TLB 缓存未命中处理程序的地址；加载该地址中的指令到 CPU 中；
• CPU 执行虚拟 OS 缓存未命中处理程序：从虚拟地址 VA 中提取 VPN 虚拟页号；查找虚拟 OS 中的页表；如果页号存在并有效，取得物理页号 PFN；更新 TLB（特权操作，将触发陷阱）；
• 陷入 VMM 的陷阱处理程序；VMM 将虚拟 OS 提交的 VPN 到 FPN 的映射，转换成 VPN 到 MPN 的映射，更新 TLB；返回虚拟 OS；
• 虚拟 OS 从陷阱返回（非特权指令尝试从陷阱返回，将触发陷阱）；
• 陷入 VMM；从陷阱返回应用程序；
• 继续执行原触发陷阱的指令（指令重试），TLB 命中；

从以上过程可以发现，不管是虚拟 OS 中的应用程序，还是虚拟 OS，它们都是运行在非特权模式下的，因此，当它们尝试执行一些特权指令时，都发触发陷阱，陷入 VMM 的陷阱处理程序；

以上过程是指软件 TLB 的场景，如果是硬件支持的 TLB，则 CPU 将直接和自己内部的 TLB 翻译器打交道，当发生 TLB 未命中时，直接按照页表基址寄存器中的地址，到机器内存中，查找相应的映射，此时 VMM 是没有机会介入的；因此，VMM 必须保存一份影子页表供硬件 TLB 查询，并密切关注虚拟 OS 对页表的所有更改；当发现更新时，第一时间更新影子页表；

当虚拟 OS 中发生缓存未命中时，其成本要大于主机 OS 的缓存未命中；为了降低成本，一种思路是 VMM 在密切关注虚拟 OS 的页表更新时，存一份类似日志的记录，里面记录着 VPN 到 FPN 并到 MPN 的映射；这样当虚拟 OS 发生缓存未命中时，VMM 直接查询自己的日志，看是否有记录到该 VPN 的映射记录，如果有的话，直接返回 MPN；这样可以省去让虚拟 OS 到它的页表查询映射的环节；

信息沟

多个虚拟 OS 的时间片分配

VMM 并不知道虚拟 OS 的内部状态，由于信息差，它们有时候并一定能达到最高性能的配合状态；例如当 VMM 管理多个操作系统时，有些处于空闲状态，没有任务在其中运行；有些处于繁忙的状态，有很多任务在其中运行；此时如果 VMM 为两个操作分配一样的时间片，将不是效率最高的选择；

重复页清零

当 OS 为进程提供某个内存页前，通常会将其置零，以免千万信息泄露；但是对于 VMM 来说，这种置零的动作有可能会发生两次，一次由主机 OS 分配页面给 VMM，一次由虚拟 OS 分配页面给其中的进程；两次置零的操作将增加性能成本；

半虚拟化

半虚拟化：如果操作系统的设计者，知道自己的 OS 将有可能运行在虚拟化的环境中，并因此提前做出相应的设计，以减少信息沟，那么将有可能极大的提高该 OS 在虚拟环境中的运行效率（提高的程度甚至将接近于主机 OS 的运行效率）；

Docker 使用了操作系统层的虚拟化，它并不是一种完整的系统虚拟机，而是将内核共享给多个独立空间中的应用程序；半虚拟化的例子是 Xen 项目；好奇 Xen 如何实现半虚拟化？