模块一：（前置知识）计算机组成原理

01 计算机是什么

“如何把程序写好”这个问题是可计算的吗？

芯片：计算能源

电能供给给芯片，芯片中的一种电子元件晶振（也就是石英晶体）通电后产生震荡，震荡会产生频率稳定的脉冲信号。通常这是一种高频的脉冲信号，每秒可达百万次。然后，我们通过谐振效应发放这个信号，形成方波。再通过电子元件调整这种脉冲的频率，把脉冲信号转换为我们需要的频率，这就形成了驱动芯片工作的时钟信号。这种信号的频率，我们也称作芯片的时钟频率。最后，时钟信号驱动着芯片工作，就像人体的脉搏一样，每一次脉冲到来，都让芯片的状态发生一次变化，用这种方法，最终存储器中的指令被一行行执行。指令被执行，其实就是数据被计算，这就是我说的计算能量。

芯片普及后，不仅给计算机和手机提供支持，它们还被安装到了航天设备、能源设备、医疗设备及通信设备中，甚至小到电灯、微波炉、咖啡机、热水器里面都有了芯片。有了芯片，设备通电后才可以计算，有了计算，这些设备才能够实现更加复杂而精确的功能。

可计算理论：图灵机

公理化体系和不完备性定理

哪些问题可以被计算，哪些不可以被计算，这就是可计算性理论

不可计算问题

无穷

停机问题

计算能力的边界在哪里？

另外解决问题还需要消耗内存，称作空间开销。

问题的分类

世界上有一类问题，无论我们消耗多少时间和空间也无法解决，这类问题就包括“停机问题”，称作不可计算问题

复杂度来衡量，比如：

“求数组第 10 个元素”，计算这种问题，时间开销、空间开销都不会随着问题规模增长，我们记为 O(1)；

“求数组中的最大值”，计算这种问题，时间开销会随着数组规模线性增大，记作 O(N)，N 是问题的规模；

还有像“求一个n*n矩阵的和”，如果n是规模，那么时间开销会随着问题规模的平方增长，我们称作 O(N2)；

当然也有更加复杂的数学模型，比如说O(N3)、O(N4)、O(N100)等

P 问题 vs NP 问题

摩尔定律所说，人类的计算能力每 18～24 个月翻一倍，我们的计算能力在呈指数形式上

这种我们有能力解决的问题，统称为多项式时间（ Polynomial time）问题。我们今天能解决的问题，都是多项式时间的问题，下面记为 P 类型的问题。

还有一类问题复杂度本身也是指数形式的问题，比如 O(2N)的问题。这类型的问题随着规模 N 上升，时间开销的增长速度和人类计算能力增长速度持平甚至更快。因此虽然这类问题可以计算，但是当 N 较大时，因为计算能力不足，最终结果依然无法被解决。

问题如果不能在多项式时间内找到答案，我们记为 NP 问题。

有一部分 NP 问题可以被转化为 P 问题，比如斐波那契数列求第 N 项，可以用缓存、动态规划等方式转化为 O(N) 的问题。但还有更多的 NP 问题，比如一个集合，找出和为零的子集，就没能找到一个合适的转换方法。

02 程序的执行

相比 32 位，64 位的优势是什么？（上）

相比 32 位，64 位的优势是什么？

本质事cpu 计算位宽 32位 4byte 64 8byte

32、64 位指的是操作系统、是软件、还是 CPU？

如果是软件，那么我们的数据库有 32 位和 64 位版本；

如果是操作系统，那么在阿里云上选择 Centos 和 Debian 版本的时候，也会有 32/64 版本；

如果是 CPU，那么有 32 位 CPU，也有 64 位 CPU。

图灵机的构造

第一，它清楚地定义了计算机能力的边界，也就是可计算理论；

第二，它定义了计算机由哪些部分组成，程序又是如何执行的。

图灵机拥有一条无限长的纸带，纸带上是一个格子挨着一个格子，格子中可以写字符，你可以把纸带看作内存，而这些字符可以看作是内存中的数据或者程序。

图灵机有一个读写头，读写头可以读取任意格子上的字符，也可以改写任意格子的字符。

读写头上面的盒子里是一些精密的零件，包括图灵机的存储、控制单元和运算单元。

图灵机如何执行程序

1 首先，我们将“11、15、+” 分别写入纸带上的 3 个格子（现在纸带上的字符串是11、15、 +)，然后将读写头先停在 11 对应的格子上。

2 接下来，图灵机通过读写头读入 11 到它的存储设备中（这个存储设备也叫作图灵机的状态）。图灵机没有说读写头为什么可以识别纸带上的字符，而是假定读写头可以做到这点。

3 然后读写头向右移动一个格，用同样的方法将 15 读入图灵机的状态中。现在图灵机的状态中有两个连续的数字，11 和 15。

4 接下来重复上面的过程，会读到一个+号。下面我详细说一下这个运算流程：

读写头读到一个 + 号 ；

然后将 + 号传输给控制单元 ；

控制单元发现是一个 + 号，所以没有存入状态中。因为 + 号是一个我们预设的控制符（指令），它的作用是加和目前状态。因此，控制单元识别出是控制符，并通知运算单元工作；

运算单元从状态中读入 11、15 并进行计算，将结果 26 存储到状态；

运算单元将结果回传给控制单元；

控制单元将结果传输给读写头。

4 读写头向右移动，将结果 26 写入纸带。

这样，我们就通过图灵机计算出了 11+15 的值。不知道你有没有发现，图灵机构造的这一台机器，主要功能就是读写纸带然后计算；纸带中有数据、也有控制字符（也就是指令），这个设计和我们今天的计算机是一样的。

图灵通过数学证明了，一个问题如果可以拆解成图灵机的可执行步骤，那问题就是可计算的。另一方面，图灵机定义了计算机的组成以及工作原理，但是没有给出具体的实现。

冯诺依曼模型

具体的实现是 1945 年冯诺依曼和其他几位科学家在著名的 101 页报告中提出的。报告遵循了图灵机的设计，并提出用电子元件构造计算机，约定了用二进制进行计算和存储，并且将计算机结构分成以下 5 个部分：

输入设备；

输出设备；

内存；

中央处理器；

总线。

这个模型也被称为冯诺依曼模型，下面我们具体来看看这 5 部分的作用。

内存 在冯诺依曼模型中，程序和数据被存储在一个被称作内存的线性排列存储区域。存储的数据单位是一个二进制位，英文是 bit。最小的存储单位叫作字节，也就是 8 位，英文是 byte，每一个字节都对应一个内存地址。内存地址由 0 开始编号，比如第 1 个地址是 0，第 2 个地址是 1， 然后自增排列，最后一个地址是内存中的字节数减 1。

我们通常说的内存都是随机存取器，也就是读取任何一个地址数据的速度是一样的，写入任何一个地址数据的速度也是一样的。

CPU 冯诺依曼模型中 CPU 负责控制和计算。为了方便计算较大的数值，CPU 每次可以计算多个字节的数据。

如果 CPU 每次可以计算 4 个 byte，那么我们称作 32 位 CPU；

如果 CPU 每次可以计算 8 个 byte，那么我们称作 64 位 CPU。

这里的 32 和 64，称作 CPU 的位宽。

为什么 CPU 要这样设计呢？ 因为一个 byte 最大的表示范围就是 0~255。比如要计算 20000*50，就超出了byte 最大的表示范围了。因此，CPU 需要支持多个 byte 一起计算。当然，CPU 位数越大，可以计算的数值就越大。但是在现实生活中不一定需要计算这么大的数值。比如说 32 位 CPU 能计算的最大整数是 4294967295，这已经非常大了。

控制单元和逻辑运算单元

CPU 中有一个控制单元专门负责控制 CPU 工作；还有逻辑运算单元专门负责计算。具体的工作原理我们在指令部分给大家分析。

寄存器

CPU 要进行计算，比如最简单的加和两个数字时，因为 CPU 离内存太远，所以需要一种离自己近的存储来存储将要被计算的数字。这种存储就是寄存器。寄存器就在 CPU 里，控制单元和逻辑运算单元非常近，因此速度很快。

寄存器中有一部分是可供用户编程用的，比如用来存加和指令的两个参数，是通用寄存器。

还有一部分寄存器有特殊的用途，叫作特殊寄存器。比如程序指针，就是一个特殊寄存器。它存储了 CPU 要执行的下一条指令所在的内存地址。注意，程序指针不是存储了下一条要执行的指令，此时指令还在内存中，程序指针只是存储了下一条指令的地址。

下一条要执行的指令，会从内存读入到另一个特殊的寄存器中，这个寄存器叫作指令寄存器。指令被执行完成之前，指令都存储在这里。

总线

CPU 和内存以及其他设备之间，也需要通信，因此我们用一种特殊的设备进行控制，就是总线。总线分成 3 种：

一种是地址总线，专门用来指定 CPU 将要操作的内存地址。

还有一种是数据总线，用来读写内存中的数据。

当 CPU 需要读写内存的时候，先要通过地址总线来指定内存地址，再通过数据总线来传输数据。

最后一种总线叫作控制总线，用来发送和接收关键信号，比如后面我们会学到的中断信号，还有设备复位、就绪等信号，都是通过控制总线传输。同样的，CPU 需要对这些信号进行响应，这也需要控制总线。

输入、输出设备 输入设备向计算机输入数据，计算机经过计算，将结果通过输出设备向外界传达。如果输入设备、输出设备想要和 CPU 进行交互，比如说用户按键需要 CPU 响应，这时候就需要用到控制总线。

到这里，相信你已经对冯诺依曼模型的构造有了一定的了解。这里我再强调几个问题：

1. 线路位宽问题 第一个问题是，你可能会好奇数据如何通过线路传递。其实是通过操作电压，低电压是 0，高电压是 1。

如果只有一条线路，每次只能传递 1 个信号，因为你必须在 0,1 中选一个。比如你构造高高低低这样的信号，其实就是 1100，相当于你传了一个数字 10 过去。大家注意，这种传递是相当慢的，因为你需要传递 4 次。

这种一个 bit 一个 bit 发送的方式，我们叫作串行。如果希望每次多传一些数据，就需要增加线路，也就是需要并行。

如果只有 1 条地址总线，那每次只能表示 0-1 两种情况，所以只能操作 2 个内存地址；如果有 10 条地址总线，一次就可以表示 210 种情况，也就是可以操作 1024 个内存地址；如果你希望操作 4G 的内存，那么就需要 32 条线，因为 232 是 4G。

到这里，你可能会问，那我串行发送行不行？当然也不是不行，只是速度会很慢，因为每多增加一条线路速度就会翻倍。

1. 64 位和 32 位的计算

32位内存最大是4g

内存大小和CPU 位宽不直接关联

1B=1字节=8bit（比特）。

2^32*1B=2^32B

2^32*1B/2^30=2^2GB=4GB

32位总线可以产生2的32次方个

第二个问题是，CPU 的位宽会对计算造成什么影响？

我们来看一个具体场景：要用 32 位宽的 CPU，加和两个 64 位的数字。

32 位宽的 CPU 控制 40 位宽的地址总线、数据总线工作会非常麻烦，需要双方制定协议。 因此通常 32 位宽 CPU 最多操作 32 位宽的地址总线和数据总线。

因此必须把两个 64 位数字拆成 2 个 32 位数字来计算，这样就需要一个算法，比如用像小时候做加法竖式一样，先加和两个低位的 32 位数字，算出进位，然后加和两个高位的 32 位数字，最后再加上进位。

而 64 位的 CPU 就可以一次读入 64 位的数字，同时 64 位的 CPU 内部的逻辑计算单元，也支持 64 位的数字进行计算。但是你千万不要仅仅因为位宽的区别，就认为 64 位 CPU 性能比 32 位高很多。

要知道大部分应用不需要计算超过 32 位的数字，比如你做一个电商网站，用户的金额通常是 10 万以下的，而 32 位有符号整数，最大可以到 20 亿。所以这样的计算在 32 位还是 64 位中没有什么区别。

还有一点要注意，32 位宽的 CPU 没办法控制超过 32 位的地址总线、数据总线工作。比如说你有一条 40 位的地址总线（其实就是 40 条线），32 位的 CPU 没有办法一次给 40 个信号，因为它最多只有 32 位的寄存器。因此 32 位宽的 CPU 最多操作 232 个内存地址，也就是 4G 内存地址。

03 程序的执行

相比 32 位，64 位的优势是什么？（下）

程序的执行过程

1.首先，CPU 读取 PC 指针指向的指令，将它导入指令寄存器。具体来说，完成读取指令这件事情有 3 个步骤：

步骤 1：CPU 的控制单元操作地址总线指定需要访问的内存地址（简单理解，就是把 PC 指针中的值拷贝到地址总线中）。

步骤 2：CPU 通知内存设备准备数据（内存设备准备好了，就通过数据总线将数据传送给 CPU）。

步骤 3：CPU 收到内存传来的数据后，将这个数据存入指令寄存器。

完成以上 3 步，CPU 成功读取了 PC 指针指向指令，存入了指令寄存器。

完成以上 3 步，CPU 成功读取了 PC 指针指向指令，存入了指令寄存器。

2.然后，CPU 分析指令寄存器中的指令，确定指令的类型和参数。 3.如果是计算类型的指令，那么就交给逻辑运算单元计算；如果是存储类型的指令，那么由控制单元执行。 4.PC 指针自增，并准备获取下一条指令。

比如在 32 位的机器上，指令是 32 位 4 个字节，需要 4 个内存地址存储，因此 PC 指针会自增 4。

内存虽然是一个随机存取器，但是我们通常不会把指令和数据存在一起，这是为了安全起见。具体的原因我会在模块四进程部分展开讲解，欢迎大家在本课时的留言区讨论起来，我会结合你们留言的内容做后续的课程设计。

程序指针也是一个寄存器，64 位的 CPU 会提供 64 位的寄存器，这样就可以使用更多内存地址。特别要说明的是，64 位的寄存器可以寻址的范围非常大，但是也会受到地址总线条数的限制。比如和 64 位 CPU 配套工作的地址总线只有 40 条，那么可以寻址的范围就只有 1T，也就是 240。

从 PC 指针读取指令、到执行、再到下一条指令，构成了一个循环，这个不断循环的过程叫作CPU 的指令周期，下面我们会详细讲解这个概念。

详解 a = 11 + 15 的执行过程

上面我们了解了基本的程序执行过程，接下来我们来看看如果用冯诺依曼模型执行a=11+15是一个怎样的过程。

程序员写的程序a=11+15是字符串，CPU 不能执行字符串，只能执行指令。所以这里需要用到一种特殊的程序——编译器。编译器的核心能力是翻译，它把一种程序翻译成另一种程序语言。

1.编译器通过分析，发现 11 和 15 是数据，因此编译好的程序启动时，会在内存中开辟出一个专门的区域存这样的常数，这个专门用来存储常数的区域，就是数据段，如下图所示：

11 被存储到了地址 0x100；

15 被存储到了地址 0x104；

2.编译器将a=11+15转换成了 4 条指令，程序启动后，这些指令被导入了一个专门用来存储指令的区域，也就是正文段。如上图所示，这 4 条指令被存储到了 0x200-0x20c 的区域中：

0x200 位置的 load 指令将地址 0x100 中的数据 11 导入寄存器 R0；

0x204 位置的 load 指令将地址 0x104 中的数据 15 导入寄存器 R1；

0x208 位置的 add 指令将寄存器 R0 和 R1 中的值相加，存入寄存器 R2；

0x20c 位置的 store 指令将寄存器 R2 中的值存回数据区域中的 0x1108 位置。

3.具体执行的时候，PC 指针先指向 0x200 位置，然后依次执行这 4 条指令。

这里还有几个问题要说明一下：

变量 a 实际上是内存中的一个地址，a 是给程序员的助记符。

为什么 0x200 中代表加载数据到寄存器的指令是 0x8c000100，我们会在下面详细讨论。

不知道细心的同学是否发现，在上面的例子中，我们每次操作 4 个地址，也就是 32 位，这是因为我们在用 32 位宽的 CPU 举例。在 32 位宽的 CPU 中，指令也是 32 位的。但是数据可以小于 32 位，比如可以加和两个 8 位的字节。

关于数据段和正文段的内容，会在模块四进程和线程部分继续讲解。

指令

接下来我会带你具体分析指令的执行过程。

在上面的例子中，load 指令将内存中的数据导入寄存器，我们写成了 16 进制：0x8c000100，拆分成二进制就是：

最左边的 6 位，叫作操作码，英文是 OpCode，100011 代表 load 指令；

中间的 4 位 0000是寄存器的编号，这里代表寄存器 R0；

后面的 22 位代表要读取的地址，也就是 0x100。

所以我们是把操作码、寄存器的编号、要读取的地址合并到了一个 32 位的指令中。

我们再来看一条求加法运算的 add 指令，16 进制表示是 0x08048000，换算成二进制就是：

最左边的 6 位是指令编码，代表指令 add；

紧接着的 4 位 0000 代表寄存器 R0；

然后再接着的 4 位 0001 代表寄存器 R1；

再接着的 4 位 0010 代表寄存器 R2；

最后剩下的 14 位没有被使用。

构造指令的过程，叫作指令的编码，通常由编译器完成；解析指令的过程，叫作指令的解码，由 CPU 完成。由此可见 CPU 内部有一个循环：

首先 CPU 通过 PC 指针读取对应内存地址的指令，我们将这个步骤叫作 Fetch，就是获取的意思。

CPU 对指令进行解码，我们将这个部分叫作 Decode。

CPU 执行指令，我们将这个部分叫作 Execution。

CPU 将结果存回寄存器或者将寄存器存入内存，我们将这个步骤叫作 Store。

上面 4 个步骤，我们叫作 CPU 的指令周期。CPU 的工作就是一个周期接着一个周期，周而复始。

指令的类型

通过上面的例子，你会发现不同类型（不同 OpCode）的指令、参数个数、每个参数的位宽，都不一样。而参数可以是以下这三种类型：

寄存器；

内存地址；

数值（一般是整数和浮点）。

当然，无论是寄存器、内存地址还是数值，它们都是数字。

指令从功能角度来划分，大概有以下 5 类：

I/O 类型的指令，比如处理和内存间数据交换的指令 store/load 等；再比如将一个内存地址的数据转移到另一个内存地址的 mov 指令。

计算类型的指令，最多只能处理两个寄存器，比如加减乘除、位运算、比较大小等。

跳转类型的指令，用处就是修改 PC 指针。比如编程中大家经常会遇到需要条件判断+跳转的逻辑，比如 if-else，swtich-case、函数调用等。

信号类型的指令，比如发送中断的指令 trap。

闲置 CPU 的指令 nop，一般 CPU 都有这样一条指令，执行后 CPU 会空转一个周期。

指令还有一个分法，就是寻址模式，比如同样是求和指令，可能会有 2 个版本：

将两个寄存器的值相加的 add 指令。

将一个寄存器和一个整数相加的 addi 指令。

另外，同样是加载内存中的数据到寄存器的 load 指令也有不同的寻址模式：

比如直接加载一个内存地址中的数据到寄存器的指令la，叫作直接寻址。

直接将一个数值导入寄存器的指令li，叫作寄存器寻址。

将一个寄存器中的数值作为地址，然后再去加载这个地址中数据的指令lw，叫作间接寻址。

因此寻址模式是从指令如何获取数据的角度，对指令的一种分类，目的是给编写指令的人更多选择。

了解了指令的类型后，我再强调几个细节问题：

关于寻址模式和所有的指令，只要你不是嵌入式开发人员，就不需要记忆，理解即可。

不同 CPU 的指令和寄存器名称都不一样，因此这些名称也不需要你记忆。

有几个寄存器在所有 CPU 里名字都一样，比如 PC 指针、指令寄存器等。

指令的执行速度

之前我们提到过 CPU 是用石英晶体产生的脉冲转化为时钟信号驱动的，每一次时钟信号高低电平的转换就是一个周期，我们称为时钟周期。CPU 的主频，说的就是时钟信号的频率。比如一个 1GHz 的 CPU，说的是时钟信号的频率是 1G。

到这里你可能会有疑问：是不是每个时钟周期都可以执行一条指令？其实，不是的，多数指令不能在一个时钟周期完成，通常需要 2 个、4 个、6 个时钟周期。

总结 接下来我们来做一个总结。这节课我们深入讨论了指令和指令的分类。接下来，我们来看一看在 02 课时中留下的问题：64 位和 32 位比较有哪些优势？

还是老规矩，请你先自己思考这个问题的答案，写在留言区，然后再来看我接下来的分析。

【解析】 其实，这个问题需要分类讨论。

如果说的是 64 位宽 CPU，那么有 2 个优势。

优势 1：64 位 CPU 可以执行更大数字的运算，这个优势在普通应用上不明显，但是对于数值计算较多的应用就非常明显。

优势 2：64 位 CPU 可以寻址更大的内存空间

如果 32 位/64 位说的是程序，那么说的是指令是 64 位还是 32 位的。32 位指令在 64 位机器上执行，困难不大，可以兼容。 如果是 64 位指令，在 32 位机器上执行就困难了。因为 32 位指令在 64 位机器执行的时候，需要的是一套兼容机制；但是 64 位指令在 32 位机器上执行，32 位的寄存器都存不下指令的参数。

操作系统也是一种程序，如果是 64 位操作系统，也就是操作系统中程序的指令都是 64 位指令，因此不能安装在 32 位机器上。

思考题 最后再给你出一道思考题：CPU 中有没有求对数的指令？如果没有那么程序如何去计算？

04 构造复杂的程序

将一个递归函数转成非递归函数的通用方法

不支持递归的程序语言如何实现递归程序？

首先，它不是纯粹考概念和死记硬背，求职者在回答问题之前需要进行一定的思考；

其次，这道题目可以继续深挖，比如可以让求职者具体写一个程序，就变成了一道编程题；

最后，这道题目有实战意义，它背后考察的是求职者的编程功底。

为了弄清楚这道题目，你需要对程序有一个更深层次的认识，不仅仅停留在指令的执行层面，而是要灵活使用指令，去实现更加复杂的功能。

for 循环如何被执行

下面是一个求 1 加到 100 的 Java 程序，请你思考如何将它转换为指令：

var i = 1, s = 0;

for(; i <= 100; i++) {

  s+=i;

}

经过思考，如果按照顺序执行上面的程序，则需要很多指令，因为 for 循环可以执行 1 次，也可以执行 100W 次，还可以执行无数次。因此，指令的设计者提供了一种 jump 类型的指令，让你可以在程序间跳跃，比如:

loop:

  jump loop

这就实现了一个无限循环，程序执行到 jumploop 的时候，就会跳回 loop 标签。

用这种方法，我们可以将 for 循环用底层的指令实现：

# var i = 1, s = 0

# 对应 Java 代码，我们首先将 1 和 0 存储到两个地址

# 这两个地址我们用 $i 和 $s 表示

store #1 -> $i // 将数字 1 存入i的地址

store #0 -> $s // 将数字 0 存入 s 的地址

# 接下来循环要开始了，我们在这里预留一个 loop 标签

# loop 是一个自定义标签，它代表指令的相对位置

# 后续我们可以用 jump 指令跳转回这个位置实现循环

loop: # 循环标签



# for ... i <= 100

# 接下来我们开始实现循环控制

# 我们先首先 i <= 100的比较

# 我们先将变量 i 的地址，也就是 $i 导入寄存器 R0

load $i -> R0

# 然后我们用 cmp 比较指令 R0 和数字 100

cmp R0 #100 // 比较 R0 和数字 100

# 注意指令不会有返回值，它会进行计算，然后改变机器的状态（也就是寄存器）

# 比较后，有几个特殊的寄存器会保存比较结果

# 然后我们用 ja（jump above）, 如果比较结果 R0 比 100 大

# 那么我们就跳转到 end 标签，实现循环的跳出

ja end 

nop

# 如果 R0<=100，那么ja end 没有生效，这时我们处理 s+=i

# 首先我们把变量 s 所在地址的数据导入寄存器 R1

load $s -> R1

# 然后我们把寄存器R0和R1加和，把结果存储寄存器 R2

add R0 R1 R2 

# 这时，我们把寄存器 R2 的值存入变量 s 所在的地址

store R2 -> $s

# 刚才我们完成了一次循环

# 我们还需要维护变量 i 的自增

# 现在 i 的值在 R0 中，我们首先将整数 1 叠加到 R0 上

add R0 #1 R0

# 再把 R0 的值存入i所在的内存地址

store R0 -> $i

# 这时我们的循环体已经全部执行完成，我们需要调转回上面 loop 标签所在的位置

# 继续循环

jump loop

nop

end:

1. jump 指令直接操作 PC 指针，但是很多 CPU 会抢先执行下一条指令，因此通常我们在 jump 后面要跟随一条 nop 指令，让 CPU 空转一个周期，避免 jump 下面的指令被执行。是不是到了微观世界，和你所认识的程序还不太一样？
2. 上面我写指令的时候用到了 add/store 这些指令，它们叫作助记符，是帮助你记忆的。整体这段程序，我们就称作汇编程序。
3. 因为不同的机器助记符也不一样，所以你不用太关注我用的是什么汇编语言，也不用去记忆这些指令。当你拿到指定芯片的时候，直接去查阅芯片的说明书就可以了。
4. 虽然不同 CPU 的指令不一样，但也是有行业标准的。现在使用比较多的是 RISC（精简指令集）和 CISC（复杂指令集）。比如目前Inte 和 AMD 家族主要使用 CISC 指令集，ARM 和 MIPS 等主要使用RISC 指令集。

条件控制程序

条件控制程序有两种典型代表，一种是 if-else ，另一种是 switch-case 。 总体来说， if-else 翻译成指令，是比较简单的，你需要用跳转指令和比较指令处理它的跳转逻辑。

当然，它们的使用场景不同，这块我不展开了。在这里我主要想跟你说说，它们的内部实现是不一样的。if-else 是一个自上向下的执行逻辑， switch-case是一种精确匹配算法。比如你有 1000 个 case，如果用 if-else 你需要一个个比较，最坏情况下需要比较 999 次；而如果用 switch-case ，就不需要一个个比较，通过算法就可以直接定位到对应的case 。

举个具体的例子，比如一个根据数字返回星期的程序。如果用if-else，那么你需要这样做：

switch-case 性能更高 在匹配更多时

if(week == 1) {

  return "周一";

} else if(week == 2) {

  return "周二";

}

……
如果用 switch-case 的逻辑，你可能会这样计算：
跳转位置=当前PC + 4*(week * 2 - 1)

函数

了解了循环和条件判断，我们再来看看函数是如何被执行的。函数的执行过程必须深入到底层，也会涉及一种叫作栈的数据结构。

下面是一段 C 程序，传入两个参数，然后返回两个参数的和：

int add(int a, int b){
  return a + b;
}

1. 通过观察，我们发现函数的参数 a,b 本质是内存中的数据，因此需要给它们分配内存地址。
2. 函数返回值也是内存中的数据，也就是返回值也需要分配内存地址。
3. 调用函数其实就是跳转到函数体对应的指令所在的位置，因此函数名可以用一个标签，调用时，就用 jump 指令跟这个标签。

函数进行了a+b的运算，我们可以这样构造指令：

# 首先我们定义一个叫作add的标签
add:
# 然后我们将a和b所在地址中的数据都导入寄存器
load $a -> R0
load $b -> R1
# 然后我们将寄存器求和，并将结果回写到返回地址
add R0 R1 R2
store R2 -> $r

当我们需要调用这个函数的时候，我们就构造下面这样的指令：
jump add

有 2 个问题还没有解决：

1. 参数如何传递给函数？
2. 返回值如何传递给调用者？

为了解决这 2 个问题，我们就需要用到前面提到的一个叫作栈的数据结构。栈的英文是 Stack，意思是码放整齐的一堆东西。首先在调用方，我们将参数传递给栈；然后在函数执行过程中，我们从栈中取出参数。

函数执行过程中，先将执行结果写入栈中，然后在返回前把之前压入的参数出栈，调用方再从栈中取出执行结果。

将参数传递给 Stack 的过程，叫作压栈。取出结果的过程，叫作出栈。栈就好像你书桌上的一摞书，压栈就是把参数放到书上面，出栈就是把顶部的书拿下来。

因为栈中的每个数据大小都一样，所以在函数执行的过程中，我们可以通过参数的个数和参数的序号去计算参数在栈中的位置。

接下来我们来看看函数执行的整体过程：假设要计算 11 和 15 的和，我们首先在内存中开辟一块单独的空间，也就是栈。

就如前面所讲，栈的使用方法是不断往上堆数据，所以需要一个栈指针（Stack Pointer， SP）指向栈顶（也就是下一个可以写入的位置）。每次将数据写入栈时，就把数据写到栈指针指向的位置，然后将 SP 的值增加。

为了提高效率，我们通常会用一个特殊的寄存器来存储栈指针，这个寄存器就叫作 Stack Pointer，在大多数芯片中都有这个特殊的寄存器。一开始，SP 指向 0x100 位置，而 0x100 位置还没有数据。

• 压栈参数11

接下来我们开始传参，我们先将 11 压栈，之所以称作压栈（ Push)，就好像我们把数据 11 堆在内存中一样。模拟压栈的过程是下面两条指令：

store #11 -> $SP // 将11存入SP指向的地址0x100
add SP, 4, SP  // 栈指针增加4（32位机器）

第一条 store 指令将 SP 寄存器指向的内存地址设置为常数 11。

第二条指令将栈指针自增 4。

这里用美元符号代表将 11 存入的是 SP 寄存器指向的内存地址，这是一次间接寻址。存入后，栈指针不是自增 1 而是自增了 4，因为我在这里给你讲解时，用的是一个 32 位宽的 CPU 。如果是 64 位宽的 CPU，那么栈指针就需要自增 8。

压栈完成后，内存变成下图中所示的样子。11 被写入内存，并且栈指针指向了 0x104 位置。

• 压栈参数15

然后我们用同样的方法将参数 15 压栈。

压栈后，11 和 15 都被放入了对应的内存位置，并且栈指针指向了 0x108。

• 将返回值压栈

接下来，我们将返回值压栈。到这里你可能会问，返回值还没有计算呢，怎么就压栈了？其实这相当于一个占位，后面我们会改写这个地址的值。

• 调用函数

当我们完成了上面的压栈后，就开始调用函数，一种简单的做法是用 jump 指令直接跳转到函数的标签，比如：

jump add
这个时候，要加和在栈中的数据 11 和 15，我们可以利用 SP 指针寻找数据。11 距离当前 SP 指针差 3 个位置，15 距离 SP 指针差 2 个位置。这种寻址方式是一种复合的寻址方式，是间接 + 偏移量寻址。

我们可以用下面的代码完成将 11 和 15 导入寄存器的过程：
load $(SP - 12) -> R0
load $(SP - 8) -> R1

然后进行加和，将结果存入 R2。

load R0 R1 R2
最后我们可以再次利用数学关系将结果写入返回值所在的位置
store R2 -> $(SP-4)

上面我们用到了一种间接寻址的方式来进行加和运算，也就是利用 SP 中的地址做加减法操作内存。

经过函数调用的结果如下图所示，运算结果 26 已经被写入了返回值的位置：

• 发现-解决问题

一个好的解决方案，也会面临问题。现在我们就遇到了麻烦：

1. 函数计算完成，这时应该跳转回去。可是我们没有记录函数调用前 PC 指针的位置，因此这里需要改进，我们需要存储函数调用前的 PC 指针方便调用后恢复。
2. 栈不可以被无限使用，11和 15 作为参数，计算出了结果 26，那么它们就可以清空了。如果用调整栈指针的方式去清空，我们就会先清空 26。此时就会出现顺序问题，因此我们需要调整压栈的顺序。

具体顺序你可以看下图。首先，我们将函数参数和返回值换位，这样在清空数据的时候，就会先清空参数，再清空返回值。

然后我们在调用函数前，还需要将返回地址压栈。这样在函数计算完成前，就能跳转回对应的返回地址。翻译成指令，就是下面这样：

## 压栈返回值
add SP, 4  -> SP 

# 计算返回地址
# 我们需要跳转到清理堆栈那行，也就是16行
MOV PC+4*(参数个数*2+1) -> SP

# 压栈参数的程序
……

# 执行函数，计算返回值
call function

# 清理堆栈
add SP, -(参数个数+1)*4， SP

递归函数如何被执行

我们刚刚使用了栈解决了函数的调用问题。但是这个方案究竟合不合理，还需要用更复杂的情况来验证。

如下所示，我们给出一个递归函数，请你判断是否可以用上面的方法执行：

int sum(int n){
  if(n == 1) {return 1;}
  return n + sum(n-1);
}

递归的时候，我们每次执行函数都形成一个如下所示的栈结构：

比如执行 sum(100)，我们就会形成一个复杂的栈，第一次调用 n = 100，第二次递归调用 n = 99：

它们堆在了一起，就形成了一个很大的栈，简化一下就是这样的一个模型，如下所示：

上面程序等价于return 3，接着再触发第 98 次递归的执行，然后是第 97 次，最终触发到第一次函数调用返回结果。

由此可见，栈这种结构同样适合递归的计算。事实上，计算机编程语言就是用这种结构来实现递归函数。

类型（class）如何实现

按照我们之前已经学习到的知识：

• 变量是一个内存地址，所以只需要分配内存就好了；
• 循环控制可以用跳转加判断实现；
• 条件控制也可以用跳转加判断实现，只不过如果是 switch-case 还需要一定的数学计算；
• 函数调用需要压栈参数、返回值和返回地址。

最后，我们来说说类型是如何实现的，也就是很多语言都支持的 class 如何被翻译成指令。其实 class 实现非常简单，首先一个 class 会分成两个部分，一部分是数据（也称作属性），另一部分是函数（也称作方法）。

class 有一个特殊的方法叫作构造函数，它会为 class 分配内存。构造函数执行的时候，开始扫描类型定义中所有的属性和方法。

• 如果遇到属性，就为属性分配内存地址；
• 如果遇到方法，方法本身需要存到正文段（也就是程序所在的内存区域），再将方法的值设置为方法指令所在的内存地址。

当我们调用一个 class 方法的时候，本质上是执行了一个函数，因此和函数调用是一致的：

1. 首先把返回值和返回地址压栈；
2. 然后压栈参数；
3. 最后执行跳转。

这里有一个小问题，有时候 class 的方法会用到this ，这其实并不复杂，你仔细想想， this指针不就是构造函数创建的一个指向 class 实例的地址吗？那么，有一种简单的实现，就是我们可以把 this 作为函数的第一个参数压栈。这样，类型的函数就可以访问类型的成员了，而类型也就可以翻译成指令了。

总结

下面我们做一个简单的总结：

1. 我们写的程序需要翻译成指令才能被执行，在 03 课时中我们提到过，这个翻译工具叫作编译器。
2. 平时你编程做的事情，用机器指令也能做，所以从计算能力上来说它们是等价的，最终这种计算能力又和图灵机是等价的。如果一个语言的能力和图灵机等价，我们就说这个语言是图灵完备的语言。现在市面上的绝大多数语言都是图灵完备的语言，但也有一些不是，比如 HTML、正则表达式和 SQL 等。
3. 我们通过汇编语言构造高级程序；通过高级程序构造自己的业务逻辑，这些都是工程能力的一种体现。

那么通过这节课的学习，你现在可以来回答本节关联的面试题目：一个程序语言如果不支持递归函数的话，该如何实现递归算法？

老规矩，请你先在脑海里思考问题的答案，并把你的思考写在留言区，然后再来看我接下来的分析。

【解析】 思路如下：

• 我们需要用到一个栈（其实用数组就可以）；
• 我们还需要一个栈指针，支持寄存器的编程语言能够直接用寄存器，而不支持直接用寄存器的编程语言，比如 Java，我们可以用一个变量；
• 然后我们可以实现压栈、出栈的操作，并按照上面学习的函数调用方法操作我们的栈。

图灵完备的语言 计算能力

非图灵完备：sql html

思考题

假设你使用的程序语言不支持递归程序，如果要求用栈来模拟下面这个斐波那契求第n项的程序，应该如何转换成等价的基于栈的非递归实现？

int fib(int n) {

 if(n == 1 || n == 2) { return n; }

  return fib(n-1) + fib(n-2)

}

05 存储器分级

L1 Cache 比内存和 SSD 快多少倍？

如果你不知道 L1 Cache，可能会错误地判断内存执行速度。我们写程序，会用寄存器、内存以及硬盘，所以按照墨菲定律，如果这里有一个认知是错误的，那么最终的结果就会产生问题。

时钟周期是由CPU时钟定义的定长时间间隔，是CPU工作的最小时间单位，也称节拍脉冲或T周期。

时钟周期表示了SDRAM所能运行的最高频率。更小的时钟周期就意味着更高的工作频率。对于PC100规格的内存来说，它的运行时钟周期应该不高于10纳秒。纳秒与工作频率之间的转换关系为：1 / 时钟周期 =工作频率。例如，标称10纳秒的PC100内存芯片，其工作频率的表达式就应该是1/ 10 = 100MHZ，这说明此内存芯片的额定工作频率为100MHZ。市场上一些质量优秀的内存通常可以工作在比额定频率高的频率下，这为一些喜欢超频的朋友带来了极大的方便。例如KingMAX的PC100内存，此类内存多采用8纳秒的芯片，相对于其100MHZ的频率来说，频率提高的余地还很大，许多用户都可以让它们工作在133MHZ甚至更高的频率下。能不能超频使用很大程度上反应了内存芯片以及PCB板的质量。不过，仅仅凭借时钟周期来判断内存的速度还是不够的，内存CAS的存取时间和延迟时间也在一定程度上决定了内存的性能。

为什么会有存储器分级策略？

c'pu 寄存器 -内存（L1......内存），硬盘

我们希望存储器是什么样子的”，也就是“我们的需求是什么”？

然后，你要弄清楚，我们的需求有哪些“实现约束”。

从需求上讲，我们希望存储器速度快、体积小、空间大、能耗低、散热好、断电数据不丢失。但在现实中，我们往往无法把所有需求都实现。

下面我们举几个例子，带你深入体会一下，比如：

• 如果一个存储器的体积小，那它存储空间就会受到制约。
• 如果一个存储器电子元件密度很大，那散热就会有问题。因为电子元件都会产生热能，所以电子元件非常集中的 CPU，就需要单独的风扇或者水冷帮助电子元件降温。
• 如果一个存储器离 CPU 较远，那么在传输过程中必然会有延迟，因此传输速度也会下降。

这里你可能会有疑问，因为在大多数人的认知里，光速是很快的，而信号又是以光速传输的。既然光速这么快，那信号的延迟应该很小才对。但事实并不是这样，比如时钟信号是 1GHz 的 CPU，1G 代表 10 个亿，因此时钟信号的一个周期是 1/10 亿秒。而光的速度是 3×10 的 8 次方米每秒，就是 3 亿米每秒。所以在一个周期内，光只能前进 30 厘米

你看！虽然在宏观世界里光速非常快，但是到计算机世界里，光速并没有像我们认知中的那么快。所以即使元件离 CPU 的距离稍微远了一点，运行速度也会下降得非常明显。

那干吗不把内存放到 CPU 里？

如果你这么做的话，除了整个电路散热和体积会出现问题，服务器也没有办法做定制内存了。也就是说 CPU 在出厂时就决定了它的内存大小，如果你想换更大的内存，就要换 CPU，而组装定制化是你非常重要的诉求，这肯定是不能接受的。

此外，在相同价格下，一个存储器的速度越快，那么它的能耗通常越高。能耗越高，发热量越大。

存储器分级策略

既然我们不能用一块存储器来解决所有的需求，那就必须把需求分级。

一种可行的方案，就是根据数据的使用频率使用不同的存储器：高频使用的数据，读写越快越好，因此用最贵的材料，放到离 CPU 最近的位置；使用频率越低的数据，我们放到离 CPU 越远的位置，用越便宜的材料。

具体来说，通常我们把存储器分成这么几个级别：

1. 寄存器；
2. L1-Cache；
3. L2-Cache；
4. L3-Cahce；
5. 内存；
6. 硬盘/SSD。

寄存器（Register）

寄存器紧挨着 CPU 的控制单元和逻辑计算单元，它所使用的材料速度也是最快的。就像我们前面讲到的，存储器的速度越快、能耗越高、产热越大，而且花费也是最贵的，因此数量不能很多。

寄存器的数量通常在几十到几百之间，每个寄存器可以用来存储一定字节（byte）的数据。比如：

• 32 位 CPU 中大多数寄存器可以存储 4 个字节；
• 64 位 CPU 中大多数寄存器可以存储 8 个字节。

寄存机的访问速度非常快，一般要求在半个 CPU 时钟周期内完成读写。比如一条要在 4 个周期内完成的指令，除了读写寄存器，还需要解码指令、控制指令执行和计算。如果寄存器的速度太慢，那 4 个周期就可能无法完成这条指令了。

L1-Cache

L1- 缓存在 CPU 中，相比寄存器，虽然它的位置距离 CPU 核心更远，但造价更低。通常 L1-Cache 大小在几十 Kb 到几百 Kb 不等，读写速度在 2~4 个 CPU 时钟周期。

L1-Cache

L1- 缓存在 CPU 中，相比寄存器，虽然它的位置距离 CPU 核心更远，但造价更低。通常 L1-Cache 大小在几十 Kb 到几百 Kb 不等，读写速度在 2~4 个 CPU 时钟周期。

L2-Cache

L2- 缓存也在 CPU 中，位置比 L1- 缓存距离 CPU 核心更远。它的大小比 L1-Cache 更大，具体大小要看 CPU 型号，有 2M 的，也有更小或者更大的，速度在 10~20 个 CPU 周期。

L3-Cache

L3- 缓存同样在 CPU 中，位置比 L2- 缓存距离 CPU 核心更远。大小通常比 L2-Cache 更大，读写速度在 20~60 个 CPU 周期。L3 缓存大小也是看型号的，比如 i9 CPU 有 512KB L1 Cache；有 2MB L2 Cache； 有16MB L3 Cache。

内存

内存的主要材料是半导体硅，是插在主板上工作的。因为它的位置距离 CPU 有一段距离，所以需要用总线和 CPU 连接。因为内存有了独立的空间，所以体积更大，造价也比上面提到的存储器低得多。现在有的个人电脑上的内存是 16G，但有些服务器的内存可以到几个 T。内存速度大概在 200~300 个 CPU 周期之间。

SSD 和硬盘

SSD 也叫固态硬盘，结构和内存类似，但是它的优点在于断电后数据还在。内存、寄存器、缓存断电后数据就消失了。内存的读写速度比 SSD 大概快 10~1000 倍。以前还有一种物理读写的磁盘，我们也叫作硬盘，它的速度比内存慢 100W 倍左右。因为它的速度太慢，现在已经逐渐被 SSD 替代

当 CPU 需要内存中某个数据的时候，如果寄存器中有这个数据，我们可以直接使用；如果寄存器中没有这个数据，我们就要先查询 L1 缓存；L1 中没有，再查询 L2 缓存；L2 中没有再查询 L3 缓存；L3 中没有，再去内存中拿。

一般用到内存就可以了

缓存条目结构

上面我们介绍了存储器分级结构大概有哪些存储以及它们的特点，接下来还有一些缓存算法和数据结构的设计困难要和你讨论。比如 CPU 想访问一个内存地址，那么如何检查这个数据是否在 L1- 缓存中？换句话说，缓存中的数据结构和算法是怎样的？

无论是缓存，还是内存，它们都是一个线性存储器，也就是数据一个挨着一个的存储。如果我们把内存想象成一个只有 1 列的表格，那么缓存就是一个多列的表格，这个表格中的每一行叫作一个缓存条目。

方案 1

缓存本质上是一个 Key-Value 的存储，它的 Key 是内存地址，值是缓存时刻内存地址中的值。我们先思考一种简单的方案，一个缓存条目设计 2 列：

1. 内存的地址；
2. 缓存的值。

CPU 读取到一个内存地址，我们就增加一个条目。当我们要查询一个内存地址的数据在不在 L1- 缓存中的时候，可以遍历每个条目，看条目中的内存地址是否和查询的内存地址相同。如果相同，我们就取出条目中缓存的值。

这个方法需要遍历缓存中的每个条目，因此计算速度会非常慢，在最坏情况下，算法需要检查所有的条目，所以这不是一个可行的方案。

方案 2

其实很多优秀的方案，往往是从最笨的方案改造而来的。现在我们已经拥有了一个方案，但是这个方案无法快速确定一个内存地址缓存在哪一行。因此我们想要找到一个更好的方法，让我们看到一个内存地址，就能够快速知道它在哪一行。

这里，我们可以用一个数学的方法。比如有 1000 个内存地址，但只有 10 个缓存条目。内存地址的编号是 0、1、2、3，...，999，缓存条目的编号是 0~9。我们思考一个内存编号，比如 701，然后用数学方法把它映射到一个缓存条目，比如 701 整除 10，得到缓存条目 1。

用这种方法，我们每次拿到一个内存地址，都可以快速确定它的缓存条目；然后再比较缓存条目中的第一列内存地址和查询的内存地址是否相同，就可以确定内存地址有没有被缓存。

延伸一下，这里用到了一种类似哈希表的方法：地址 % 10，其实就构成了一个简单的哈希函数。

指令的预读

接下来我们讨论下指令预读的问题。

之前我们学过，CPU 顺序执行内存中的指令，CPU 执行指令的速度是非常快的，一般是 2~6 个 CPU 时钟周期；这节课，我们学习了存储器分级策略，发现内存的读写速度其实是非常慢的，大概有 200~300 个时钟周期。

不知道你发现没有？这也产生了一个非常麻烦的问题：CPU 其实是不能从内存中一条条读取指令再执行的，如果是这样做，那每执行一条指令就需要 200~300 个时钟周期了。

那么，这个问题如何处理呢？

这里我再多说一句，你在做业务开发 RPC 调用的时候，其实也会经常碰到这种情况，远程调用拖慢了整体执行效率，下面我们一起讨论这类问题的解决方案。

一个解决办法就是 CPU 把内存中的指令预读几十条或者上百条到读写速度较快的 L1- 缓存中，因为 L1- 缓存的读写速度只有 2~4 个时钟周期，是可以跟上 CPU 的执行速度的。

这里又产生了另一个问题：如果数据和指令都存储在 L1- 缓存中，如果数据缓存覆盖了指令缓存，就会产生非常严重的后果。因此，L1- 缓存通常会分成两个区域，一个是指令区，一个是数据区。

与此同时，又出现了一个问题，L1- 缓存分成了指令区和数据区，那么 L2/L3 需不需要这样分呢？其实，是不需要的。因为 L2 和 L3，不需要协助处理指令预读的问题。

缓存的命中率

接下来，还有一个重要的问题需要解决。就是 L1/L2/L3 加起来，缓存的命中率有多少？

所谓命中就是指在缓存中找到需要的数据。和命中相反的是穿透，也叫 miss，就是一次读取操作没有从缓存中找到对应的数据。

据统计，L1 缓存的命中率在 80% 左右，L1/L2/L3 加起来的命中率在 95% 左右。因此，CPU 缓存的设计还是相当合理的。只有 5% 的内存读取会穿透到内存，95% 都能读取到缓存。 这也是为什么程序语言逐渐取消了让程序员操作寄存器的语法，因为缓存保证了很高的命中率，多余的优化意义不大，而且很容易出错。

缓存置换问题

最后的一个问题，比如现在 L1- 缓存条目已经存满了，接下来 CPU 又读了内存，需要把一个新的条目存到 L1- 缓存中，既然有一个新的条目要进来，那就有一个旧的条目要出去。所以，这个时候我们就需要用一个算法去计算哪个条目应该被置换出去。这个问题叫作缓存置换问题。有关缓存置换问题，我会在 “21 | 进程的调度：进程调度都有哪些方法？”中和你讨论。

总结

这节课我们讲到了存储器分级策略，讨论了 L1/L2/L3 缓存的工作原理。本课时学习的内容，是所有缓存知识的源头。所有缓存系统的设计，都是存储资源的分级。我们在设计缓存的时候，除了要关心整体架构外，还需要注意细节，比如：

• 条目怎么设计？
• 算法怎么设计？
• 命中率怎么统计？
• 缓存怎么置换等？

现在我们来说一下课前提出的问题：SSD、内存和 L1 Cache 相比速度差多少倍？

还是老规矩，请你先自己思考这个问题的答案，写在留言区，然后再来看我接下来的分析。

【解析】 因为内存比 SSD 快 10~1000 倍，L1 Cache 比内存快 100 倍左右。因此 L1 Cache 比 SSD 快了 1000~100000 倍。所以你有没有发现 SSD 的潜力很大，好的 SSD 已经接近内存了，只不过造价还略高。

这个问题告诉我们，不同的存储器之间性能差距很大，构造存储器分级很有意义，分级的目的是要构造缓存体系。

课后习题

最后，我再给你留一道课后练习题，同样也是一道高频面试题目。

假设有一个二维数组，总共有 1M 个条目，如果我们要遍历这个二维数组，应该逐行遍历还是逐列遍历？

你可以把你的答案、思路或者课后总结写在留言区，这样可以帮助你产生更多的思考，这也是构建知识体系的一部分。经过长期的积累，相信你会得到意想不到的收获。如果你觉得今天的内容对你有所启发，欢迎分享给身边的朋友。期待看到你的思考！

“先列后行”遍历发生的页面交换次数要比“先行后列”多，且cache命中率相对较低。例如对于int b[128][1024];假设内存页大小为4096字节，该数组每行正好占据一个内存页的空间，若按先行后列遍历，外层循环每走一行，内层走过1024个元素正好一页，没发生页面调度，遍历完整个数组页面调度次数最多为128次；若按先列后行，则每遍历一个元素，都发生一次页面调度，因为列上每个元素位于同行内（不同页），遍历整个数组页面调度次数可能达到1024*128次；实际中由于物理内存足够，调度次数会减少很多

二维数组的结构是由多个一维数组构成的，其中这些一维数组都是连续的，所以逐行遍历会将这些连续的地址加载到cache中，缓存命中率大大提高。

加餐 | 练习题详解（一）

练习题详解

01 | 计算机是什么：

“如何把程序写好”这个问题是可计算的吗？

【问题】 可不可以构造一段程序证明停机问题无解?如果可以，请用自己熟悉的语言写出这段程序。

【解析】拿到这道题，我们可以先从问题的抽象入手。

• 判断一段程序是否会停机的方法可以抽象成一个函数。
• 一段程序，也可以抽象成一个函数。

因此，问题可以转换为：存不存在一个通用函数判断另一个函数是否会停止？

接下来，再来构造冲突。 反证法

假设存在一个函数 willStop，它只有一个参数 func，willStop 可以判断任意函数 func 是否会停止：

• 如果会停止，返回 true；
• 如果不会停止返回 false。

willStop 具体如何实现我们无法给出，这里只是做一个假设。

复制代码

func willStop(func){
   //...
}

下面我们构造一组冲突，构造一个叫作wrappedWillStop函数，它调用willStop构造冲突。

复制代码

function wrappedWillStop(){
  if( willStop(wrappedWillStop) ) {
    while(true){}
  } else {
    return
  }
}
wrappedWillStop()

wrapped版本构造冲突方法如下：调用willStop并把自己传进去。如果willStop认为wrapped会停止，那么就执行一个死循环。 如果willStop认为wrapped不会停止，就直接返回。

通过上述的方法，我们就知道willStop这样的函数肯定是无法被实现的；也就是停机问题无解。

03 | 程序的执行：

相比 32 位 64 位的优势是什么？

【问题】 CPU 中有没有求对数的指令？如果没有那么程序如何去计算？

【解析】 CPU 中求一个数字的 2 倍，可以通过左移指令。比如 10 代表数字 2，左移 1 位变成 100 就代表数字 4。CPU 提供了乘法指令，所以如果求一个数字的幂，比如 33，可以拿 3*3 再乘以 3，需要计算 2 次。

但是如果求 3100 次方，就不会去计算 100 次。比如你可以先计算出 325，然后再求 (350)2，就是 3100。所以这样就节省了 1 倍的运算。

我举例主要是想告诉大家，CPU 没有提供很复杂的指令，但是这里有很多算法可以降低我们的时间开销。

然后我们来说说求对数，求对数也是没有指令的。因为对数是指数的逆运算，当然我们可以利用乘法运算一点点尝试。比如计算 log_210，我们可以先尝试 32，再尝试 3.12 等等，一直找到以 2 为底 10 的对数。这其实是个近似算法。

另外，在这个问题上聪明的数学家提出了很多近似算法，提升了计算效率。具体这里比较超纲，面试通常只考到有没有求对数的指令，感兴趣的同学可以学习泰勒级数、牛顿迭代法等。

比如下面这个泰勒级数可以用来求以e为底的对数，可以进行相似运算。

【补充内容】1 位的 CPU 能操作多大的内存空间？

在 03 课时程序的执行中，有个问题我讲的不是很明白，在这里我们再讨论一下。

之前提到过 32 位机器只能操作小于 32 位的地址总线，这里其实讲的不太清晰，历史上出现过 32 位操作 40 位地址总线的情况。

接下来再和你探讨一个极端情况，1 位的 CPU 能操作多大的内存空间。

答案是：无限大。

比如说，地址总线 40 位，说明 CPU 上有 40 个引脚接了地址总线。CPU 只有 1 位，因此操作这 40 个引脚可以分成 40 步。每次设置 1 根引脚的电平是 0 还是 1。所以本身 CPU 多少位和能操作多少位地址总线，没有本质联系。但是如果需要分步操作，效率会低，需要多次操作，不如一次完成来得划算。 因此我们今天的设计通常不拿 32 位 CPU 操作 40 位地址总线，而是用 64 位 CPU 操作。

04 | 构造复杂的程序 :

将一个递归函数转成非递归函数的通用方法？

【问题】 假设你使用的程序语言不支持递归程序，如果要求用栈来模拟下面这个斐波那契求第 n 项的程序，应该如何转换成等价的基于栈的非递归实现？

复制代码

int fib(int n) {

 if(n == 1 || n == 2) { return n; }

  return fib(n-1) + fib(n-2)

【解析】其实这道题目等同于递归的函数如何非递归表达？改写斐波那契数列第 N 项目。

下面是我的一个伪代码，需要实现一个 Stack。

复制代码

fib(n) {
  stack = new Stack();

  // 构造Stack
  // stack中每一项是一个Record
  // Record第一项是数据（参数或者返回值）
  // Record第二项是递归方向(down=1代表向下，up=2代表向上)
  stack.push((n, down));

  // stack中只有一项的时候递归停止
  while(stack.size() > 1) {
    (n, phase) = stack.pop();

    if(phase == down) {
      if(n == 1 || n == 2) {
        stack.push((1, -))
        continue
      }
      stack.push((n-1, down))
      stack.push((n-1, up))
    }
    else {
      last1 = stack.pop()
      last2 = stack.pop()
      stack.push((last1[0] + last2[0], up))
    }
  }
  return stack.pop()[0];
}

05 | 存储器分级 ：

SSD、内存和 L1 Cache 相比速度差多少倍？

【问题】 假设有一个二维数组，总共有 1M 个条目，如果我们要遍历这个二维数组，应该逐行遍历还是逐列遍历？

【解析】 二维数组本质还是 1 维数组。只不过进行了脚标运算。比如说一个 N 行 M 列的数组，第 y 行第 x 列的坐标是： x + y*M。因此当行坐标增加时，内存空间是跳跃的。列坐标增加时，内存空间是连续的。

当 CPU 遍历二维数组的时候，会先从 CPU 缓存中取数据。

关键因素在于现在的 CPU 设计不是每次读取一个内存地址，而是读取每次读取相邻的多个内存地址（内存速度 200～300 CPU 周期，预读提升效率）。所以这相当于机器和人的约定，如果程序员不按照这个约定，就无法利用预读的优势。

另一方面当读取内存地址跳跃较大的时候，会触发内存的页面置换，这个知识在“模块五：内存管理”中学习。

模块二：Linux 指令入门

06 目录结构和文件管理指令

rm / -rf 指令的作用是？

通过模块一的学习，你应该掌握了计算机组成原理的重点知识，到了模块二，我们开始学习 Linux 指令，它是操作系统的前端，学好这部分内容一方面可以帮助你应对工作场景，另一方面可以让你在学习操作系统底层知识前，对 Linux 有一个大概的了解。

我们依然通过一道常见的高频面试题，引出今天的主要内容。面试题如下：请你说说rm / -rf的作用？

什么是 Shell

在我们学习 Linux 指令之前，先来说一下什么是 Shell？Shell 把我们输入的指令，传递给操作系统去执行，所以 Shell 是一个命令行的用户界面。

早期程序员没有图形界面用，就用 Shell。而且图形界面制作成本较高，不能实现所有功能，因此今天的程序员依然在用 Shell。

你平时还经常会看到一个词叫作bash（Bourne Again Shell），它是用 Shell 组成的程序。这里的 Bourne 是一个人名，Steve Bourne 是 bash 的发明者。

我们今天学习的所有指令，不是写死在操作系统中的，而是一个个程序。比如rm指令，你可以用which指令查看它所在的目录。如下图所示，你会发现rm指令在/usr/bin/rm目录中。

如上图所示，ramroll是我的英文名字，ubuntu 是我这台机器的名字。我输入了which rm，然后获得了/usr/bin/rm的结果，最终执行这条指令的是操作系统，连接我和操作系统的程序就是 Shell。

Linux 对文件目录操作的指令就工作在 Shell 上，接下来我们讲讲文件目录操作指令。

Linux 对文件目录的抽象 Linux 对文件进行了一个树状的抽象。/代表根目录，每一节目录也用/分开，所以在上图所展示的/usr/bin/rm中，第一级目录是/根目录，第二级目录是usr目录，第三级是bin目录。最后的rm是一个文件。

路径（path）

像/usr/bin/rm称为可执行文件rm的路径。路径就是一个文件在文件系统中的地址。如果文件系统是树形结构，那么通常一个文件只有一个地址（路径）。

目标文件的绝对路径（Absolute path），也叫作完全路径（full path），是从/开始，接下来每一层都是一级子目录，直到定位到目标文件为止。

如上图所示的例子中，/usr/bin/rm就是一个绝对路径。

工作目录

为了方便你工作，Shell 还抽象出了工作目录。当用户打开 Shell 的时候，Shell 就会给用户安排一个工作目录。因此也就产生了相对路径。

相对路径（Relative path）是以工作目录为基点的路径。比如：

当用户在/usr目录下的时候，rm文件的相对路径就是bin/rm；

如果用户在/usr/bin目录下的时候，rm文件的路径就是./rm或者rm，这里用.代表当前目录；

如果用户在/usr/bin/somedir下，那么rm的相对路径就是../rm，这里用..代表上一级目录。

我们使用cd（change directory）指令切换工作目录，既可以用绝对路径，也可以用相对路径。 这里我要强调几个注意事项：

输入cd，不带任何参数会切换到用户的家目录，Linux 中通常是/home/{用户名}。以我自己为例，我的家目录是/home/ramroll；

输入cd .什么都不会发生，因为.代表当前目录；

输入cd..会回退一级目录，因为..代表上级目录。

利用上面这 3 种能力，你就可以方便的构造相对路径了。

Linux提供了一个指令pwd（Print Working Directory）查看工作目录。下图是我输入pwd的结果。

你可以看到我正在/home/ramroll/Documents目录下工作。

几种常见的文件类型

另一方面，Linux 下的目录也是一种文件；但是文件也不只有目录和可执行文件两种。常见的文件类型有以下 7 种:

普通文件（比如一个文本文件）；

目录文件（目录也是一个特殊的文件，它用来存储文件清单，比如/也是一个文件）；

可执行文件（上面的rm就是一个可执行文件）；

管道文件（我们会在 07 课时讨论管道文件）；

Socket 文件（我们会在模块七网络部分讨论 Socket 文件）；

软链接文件（相当于指向另一个文件所在路径的符号）；

硬链接文件（相当于指向另一个文件的指针，关于软硬链接我们将在模块六文件系统部分讨论）。

你如果使用ls -F就可以看到当前目录下的文件和它的类型。比如下面这种图：

• 结尾的是可执行文件；

= 结尾的是 Socket 文件；

@ 结尾的是软链接；

| 结尾的管道文件；

没有符号结尾的是普通文件；

/ 结尾的是目录。

设备文件

Socket 是网络插座，是客户端和服务器之间同步数据的接口。其实，Linux 不只把 Socket 抽象成了文件，设备基本也都被抽象成了文件。因为设备需要不断和操作系统交换数据。而交换方式只有两种——读和写。所以设备是可以抽象成文件的，因为文件也支持这两种操作。

Linux 把所有的设备都抽象成了文件，比如说打印机、USB、显卡等。这让整体的系统设计变得高度统一。

至此，我们了解了 Linux 对文件目录的抽象，接下来我们看看具体的增删改查指令。

文件的增删改查

增加 创建一个普通文件的方法有很多，最常见的有touch指令。比如下面我们创建了一个 a.txt 文件。

touch指令本来是用来更改文件的时间戳的，但是如果文件不存在touch也会帮助创建一个空文件。

如果你拿到一个指令不知道该怎么用，比如touch，你可以用man touch去获得帮助。man意思是 manual，就是说明书的意思，这里指的是系统的手册。如果你不知道man是什么，也可以使用man man。下图是使用man man的结果：

另外如果我们需要增加一个目录，就需要用到mkdir指令（ make directory），比如我们创建一个hello目录，如下图所示：

查看

创建之后我们可以用ls指令看到这个文件，ls是 list 的缩写。下面是指令 'ls' 的执行结果。

我们看到在当前的目录下有一个a.txt文件，还有一个hello目录。如果你知道当前的工作目录，就可以使用pwd指令。

如果想看到a.txt更完善的信息，还可以使用ls -l。-l是ls指令的可选参数。下图是ls -l的结果，你可以看到a.txt更详细的描述。

如上图所示，我们看到两个ramroll，它们是a.txt所属的用户和所属的用户分组，刚好重名了。Sep 13是日期。 中间有一个0是a.txt的文件大小，目前a.txt中还没有写入内容，因此大小是0。

另外虽然hello是空的目录，但是目录文件 Linux 上来就分配了4096字节的空间。这是因为目录内需要保存很多文件的描述信息。

删除 如果我们想要删除a.txt可以用rm a.txt；如我们要删除hello目录，可以用rm hello。rm是 remove 的缩写。

但是当我们输入rm hello的时候，会提示hello是一个目录，不可以删除。因此我们需要增加一个可选项，比如-r即 recursive（递归）。目录是一个递归结构，所以需要用递归删除。最后，你会发现rm hello -r删除了hello目录。

接下来我们尝试在 hello 目录下新增一个文件，比如相对路径是hello/world/os.txt。需要先创建 hello/world 目录。这种情况会用到mkdir的-p参数，这个参数控制mkdir当发现目标目录的父级目录不存在的时候会递归的创建。以下是我们的执行结果：

修改 如果需要修改一个文件，可以使用nano或者vi编辑器。类似的工具还有很多，但是nano和vi一般是linux自带的。

这里我不展开讲解了，你可以自己去尝试。在尝试的过程中如果遇到什么问题，可以写在留言区，我会逐一为你解答。

查阅文件内容

在了解了文件的增删改查操作后，下面我们来学习查阅文件内容。我们知道，Linux 下查阅文件内容，可以根据不同场景选择不同的指令。

当文件较小时，比如一个配置文件，想要快速浏览这个文件，可以用cat指令。下面 cat 指令帮助我们快速查看/etc/hosts文件。cat指令将文件连接到标准输出流并打印到屏幕上。

标准输出流（Standard Output）也是一种文件，进程可以将要输出的内容写入标准输出流文件，这样就可以在屏幕中打印。

如果用cat查看大文件，比如一个线上的日志文件，因为动辄有几个 G，控制台打印出所有的内容就要非常久，而且刷屏显示看不到东西。

而且如果在线上进行查看大文件的操作，会带来不必要的麻烦：

首先因为我们需要把文件拷贝到输入输出流，这需要花费很长时间，这个过程会占用机器资源；

其次，本身文件会读取到内存中，这时内存被大量占用，很危险，这可能导致其他应用内存不足。因此我们需要一些不用加载整个文件，就能查看文件内容的指令。

more

more可以帮助我们读取文件，但不需要读取整个文件到内存中。本身more的定位是一个阅读过滤器，比如你在more里除了可以向下翻页，还可以输入一段文本进行搜索。

如上图所示，我在more查看一个 nginx 日志后，先输入一个/，然后输入192.168看到的结果。more帮我找到了192.168所在的位置，然后又帮我定位到了这个位置。整个过程 more 指令只读取我们需要的部分到内存中。

less

less是一个和more功能差不多的工具，打开man能够看到less的介绍上写着自己是more的反义词（opposite of more）。这样你可以看出linux生态其实也是很自由的一个生态，在这里创造工具也可以按照自己的喜好写文档。less支持向上翻页，这个功能more是做不到的。所以现在less用得更多一些。

head/tail

head和tail是一组，它们用来读取一个文件的头部 N 行或者尾部 N 行。比如一个线上的大日志文件，当线上出了 bug，服务暂停的时候，我们就可以用tail -n 1000去查看最后的 1000 行日志文件，寻找导致服务异常的原因。

另一个比较重要的用法是，如果你想看一个实时的nginx日志，可以使用tail -f 文件名，这样你会看到用户的请求不断进来。查一下man，你会发现-f是 follow 的意思，就是文件追加的内容会跟随输出到标准输出流。

grep

有时候你需要查看一个指定ip的nginx日志，或者查看一段时间内的nginx日志。如果不想用less和more进入文件中去查看，就可以用grep命令。Linux 的文件命名风格都很短，所以也影响了很多人，比如之前我看到过一个大牛的程序，变量名从来不超过 5 个字母，而且都有意义。

grep 这个词，我们分成三段来看，是 g|re|p。

g 就是 global，全局；

re 就是 regular expression，正则表达式；

p 就是 pattern，模式。

所以这个指令的作用是通过正则表达式全局搜索一个文件找到匹配的模式。我觉得这种命名真的很牛，软件命名也是一个世纪难题，grep这个名字不但发音不错，而且很有含义，又避免了名字过长，方便记忆。

下面我们举两个例子看看 grep 的用法：

例 1：查找 ip 地址

我们可以通过grep命令定位某个ip地址的用户都做了什么事情，如下图所示：

例 2：查找时间段的日志

我们可以通过 grep 命令查找某个时间段内用户都做了什么事情。如下图所示，你可以看到在某个 5 分钟内所有用户的访问情况。

查找文件

用户经常还会有一种诉求，就是查找文件。

之前我们使用过一个which指令，这个指令可以查询一个指令文件所在的位置，比如which grep会，你会看到grep指令被安装的位置是/usr/bin。但是我们还需要一个更加通用的指令查找文件，也就是 find 指令。

find

find 指令帮助我们在文件系统中查找文件。 比如我们如果想要查找所有.txt 扩展名的文件，可以使用find / -iname "*.txt"，-iname这个参数是用来匹配查找的，i 字母代表忽略大小写，这里也可以用-name替代。输入这条指令，你会看到不断查找文件，如下图所示：

总结

这节课我们学习了很多指令，不知道你记住了多少？最后，我们再一起复习一下。

pwd指令查看工作目录。

cd指令切换工作目录。

which指令查找一个执行文件所在的路径。

ls显示文件信息。

rm删除文件。

touch修改一个文件的时间戳，如果文件不存在会触发创建文件。

vi和nano可以用来编辑文件。

cat查看完成的文件适合小型文件。

more``less查看一个文件但是只读取用户看到的内容到内存，因此消耗资源较少，适合在服务器上看日志。

head``tail可以用来看文件的头和尾。

grep指令搜索文件内容。

find指令全局查找文件。

在这里，我再强调一个指令，即man指令，它是所有指令的手册，所以你一定要多多运用，熟练掌握。另外，一个指令通常有非常多的参数，但都需要用man指令去仔细研究。

那么通过这节课的学习，你现在可以来回答本节关联的面试题目：rm / -rf的作用是？

老规矩，请你先在脑海里先思考你的答案，并把你的思考写在留言区，然后再来看我接下来的分析。

【解析】

/是文件系统根目录；

rm是删除指令；

-r是 recursive（递归）；

-f是 force（强制），遇到只读文件也不提示，直接删除。

所以rm -rf /就是删除整个文件系统上的所有文件，而且不用给用户提示。

课后习题 最后再给你出一道查资料的面试题，搜索文件系统中所有以包含std字符串且以.h扩展名结尾的文件。

你可以把你的答案、思路或者课后总结写在留言区，这样可以帮助你产生更多的思考，这也是构建知识体系的一部分。经过长期的积累，相信你会得到意想不到的收获。如果你觉得今天的内容对你有所启发，欢迎分享给身边的朋友。期待看到你的思考！

find / -iname “std.h”

07 进程、重定向和管道指令

xargs 指令的作用是？

xargs指令的作用是什么？

进程

为了弄清楚这节课程的内容，也就是管道，我们先来讨论一下进程。

我们知道，应用的可执行文件是放在文件系统里，把可执行文件启动，就会在操作系统里（具体来说是内存中）形成一个应用的副本，这个副本就是进程。

插一个小知识，以后你再遇到面试题：什么是进程？

可以回答：进程是应用的执行副本；而不要回答进程是操作系统分配资源的最小单位。前者是定义，后者是作用。

ps

如果你要看当前的进程，可以用ps指令。p 代表 processes，也就是进程；s 代表 snapshot，也就是快照。所谓快照，就是像拍照一样。

如上图所示，我启动了两个进程，ps和bash。ps 就是我刚刚启动的，被ps自己捕捉到了；bash是因为我开了这个控制台，执行的shell是bash。

当然操作系统也不可能只有这么几个进程，这是因为不带任何参数的ps指令显示的是同一个电传打字机（TTY上）的进程。TTY 这个概念是一个历史的概念，过去用来传递信息，现在已经被传真、邮件、微信等取代。

操作系统上的 TTY 是一个输入输出终端的概念，比如用户打开 bash，操作系统就为用户分配了一个输入输出终端。没有加任何参数的ps只显示在同一个 TTY 的进程。

如果想看到所有的进程，可以用ps -e，-e没有特殊含义，只是为了和-A区分开。我们通常不直接用ps -e而是用ps -ef，这是因为-f可以带上更多的描述字段，如下图所示：

UID 指进程的所有者；

PID 是进程的唯一标识；

PPID 是进程的父进程 ID；

C 是 CPU 的利用率（就是 CPU 占用）；

STIME 是开始时间；

TTY 是进程所在的 TTY，如果没有 TTY 就是 ？号；

TIME；

CMD 是进程启动时的命令，如果不是一个 Shell 命令，而是用方括号括起来，那就是系统进程或者内核过程。

另外一个用得比较多的是ps aux，它和ps -ef能力差不多，但是是 BSD 风格的。就是加州伯克利分校研发的 Unix 分支版本的衍生风格，这种风格其实不太好描述，我截了一张图，你可以体会一下：

在 BSD 风格中有些字段的叫法和含义变了，如果你感兴趣，可以作为课后延伸学习的内容。

top

另外还有一个和ps能力差不多，但是显示的不是快照而是实时更新数据的top指令。因为自带的top显示的内容有点少， 所以我喜欢用一个叫作htop的指令，具体的安装全方法我会在 10 | 软件的安装： 编译安装和包管理器安装有什么优势和劣势？中给你介绍。先看一下使用效果，如下图所示：

管道（Pipeline）

现在你已经掌握了一点点进程的基础，下面我们来学习管道，管道（Pipeline）的作用是在命令和命令之间，传递数据。比如说一个命令的结果，就可以作为另一个命令的输入。我们了解了进程，所以这里说的命令就是进程。更准确地说，管道在进程间传递数据。

输入输出流

每个进程拥有自己的标准输入流、标准输出流、标准错误流。

这几个标准流说起来很复杂，但其实都是文件。

标准输入流（用 0 表示）可以作为进程执行的上下文（进程执行可以从输入流中获取数据）。

标准输出流（用 1 表示）中写入的结果会被打印到屏幕上。

如果进程在执行过程中发生异常，那么异常信息会被记录到标准错误流（用 2 表示）中。

重定向

我们执行一个指令，比如ls -l，结果会写入标准输出流，进而被打印。这时可以用重定向符将结果重定向到一个文件，比如说ls -l > out，这样out文件就会有ls -l的结果；而屏幕上也不会再打印ls -l的结果。

具体来说>符号叫作覆盖重定向；>>叫作追加重定向。>每次都会把目标文件覆盖，>>会在目标文件中追加。比如你每次启动一个程序日志都写入/var/log/somelogfile中，可以这样操作，如下所示：

start.sh >> /var/log/somelogfile

经过这样的操作后，每次执行程序日志就不会被覆盖了。

另外还有一种情况，比如我们输入

ls1 > out

结果并不会存入out文件，因为ls1指令是不存在的。结果会输出到标准错误流中，仍然在屏幕上。这里我们可以把标准错误流也重定向到标准输出流，然后再重定向到文件。

ls1 &> out
这个写法等价于：

复制代码
ls1 > out 2>&1

相当于把ls1的标准输出流重定向到out，因为ls1 > out出错了，所以标准错误流被定向到了标准输出流。&代表一种引用关系，具体代表的是ls1 >out的标准输出流。

管道的作用和分类

有了进程和重定向的知识，接下来我们梳理下管道的作用。管道（Pipeline）将一个进程的输出流定向到另一个进程的输入流，就像水管一样，作用就是把这两个文件接起来。如果一个进程输出了一个字符 X，那么另一个进程就会获得 X 这个输入。

管道和重定向很像，但是管道是一个连接一个进行计算，重定向是将一个文件的内容定向到另一个文件，这二者经常会结合使用。

Linux 中的管道也是文件，有两种类型的管道：

匿名管道（Unnamed Pipeline），这种管道也在文件系统中，但是它只是一个存储节点，不属于任何一个目录。说白了，就是没有路径。

命名管道（Named Pipeline），这种管道就是一个文件，有自己的路径。

FIFO

管道具有 FIFO（First In First Out），FIFO 和排队场景一样，先排到的先获得。所以先流入管道文件的数据，也会先流出去传递给管道下游的进程。

使用场景分析

接下来我们以多个场景举例帮助你深入学习管道

排序 比如我们用ls，希望按照文件名排序倒序，可以使用匿名管道，将ls的结果传递给sort指令去排序。你看，这样ls的开发者就不用关心排序问题了。

去重

另一个比较常见的场景是去重，比如有一个字典文件，里面都是词语。如下所示：

Apple
Banana
Apple
Banana
……

如果我们想要去重可以使用uniq指令，uniq指令能够找到文件中相邻的重复行，然后去重。但是我们上面的文件重复行是交替的，所以不可以直接用uniq，因此可以先sort这个文件，然后利用管道将sort的结果重定向到uniq指令。指令如下：

筛选 有时候我们想根据正则模式筛选对应的内容。比如说我们想找到项目文件下所有文件名中含有Spring的文件。就可以利用grep指令，操作如下：

find ./ | grep Spring

find ./递归列出当前目录下所有目录中的文件。grep从find的输出流中找出含有Spring关键字的行。

如果我们希望包含Spring但不包含MyBatis就可以这样操作：

find ./ | grep Spring | grep -v MyBatis

grep -v是匹配不包含 MyBatis 的结果。

数行数

还有一个比较常见的场景是数行数。比如你写了一个 Java 文件想知道里面有多少行，就可以使用wc -l指令，如下所示：

但是如果你想知道当前目录下有多少个文件，可以用ls | wc -l，如下所示：

接下来请你思考一个问题：我们如何知道当前java的项目目录下有多少行代码？

提示一下。你可以使用下面这个指令：

复制代码

find -i ".java" ./ | wc -l

快去自己动手写一写吧，你在尝试的过程中如果遇到什么问题，也可以写在留言区，我会逐一为你解答。

中间结果

管道一个接着一个，是一个计算逻辑。有时候我们想要把中间的结果保存下来，这就需要用到tee指令。tee指令从标准输入流中读取数据到标准输出流。

这时候，你可能会问： 老师， 这不是什么都没做吗？

别急，tee还有一个能力，就是自己利用这个过程把输入流中读取到的数据存到文件中。比如下面这条指令：

复制代码

find ./ -i "*.java" | tee JavaList | grep Spring

这句指令的意思是从当前目录中找到所有含有 Spring 关键字的 Java 文件。tee 本身不影响指令的执行，但是 tee 会把 find 指令的结果保存到 JavaList 文件中。

tee这个执行就像英文字母中的 T 一样，连通管道两端，下面又开了口。这个开口，在函数式编程里面叫作副作用。

xargs

上面我们学习的内容难度，已经由小学 1 年级攀升到了小学 6 年级，最后我们来看看初中难度的xargs指令。

xargs指令从标准数据流中构造并执行一行行的指令。xargs从输入流获取字符串，然后利用空白、换行符等切割字符串，在这些字符串的基础上构造指令，最后一行行执行这些指令。

举个例子，如果我们重命名当前目录下的所有 .a 的文件，想在这些文件前面加一个前缀prefix_。比如说x.a文件需要重命名成prefix_x.a，我们就可以用xargs指令构造模块化的指令。

现在我们有x.ay.az.a三个文件，如下图所示：

然后使用下图中的指令构造我们需要的指令：

我们用ls找到所有的文件；

-I参数是查找替换符，这里我们用GG替代ls找到的结果；-I GG后面的字符串 GG 会被替换为x.a``x.b或x.z；

echo是一个在命令行打印字符串的指令。使用echo主要是为了安全，帮助我们检查指令是否有错误。

我们用xargs构造了 3 条指令。这里我再多讲一个词，叫作样板代码。如果你没有用xargs指令，而是用一条条mv指令去敲，这样就构成了样板代码。

最后去掉 echo，就是我们想要的结果，如下所示：

管道文件

上面我们花了较长的一段时间讨论匿名管道，用|就可以创造和使用。匿名管道也是利用了文件系统的能力，是一种文件结构。当你学到模块六文件系统的内容，会知道匿名管道拥有一个自己的inode，但不属于任何一个文件夹。

还有一种管道叫作命名管道（Named Pipeline）。命名管道是要挂到文件夹中的，因此需要创建。用mkfifo指令可以创建一个命名管道，下面我们来创建一个叫作pipe1的命名管道，如下图所示：

命名管道和匿名管道能力类似，可以连接一个输出流到另一个输入流，也是 First In First Out。

当执行cat pipe1的时候，你可以观察到，当前的终端处于等待状态。因为我们cat pipe1的时候pipe1中没有内容。

如果这个时候我们再找一个终端去写一点东西到pipe中，比如说:

echo "XXX" > pipe1

这个时候，cat pipe1就会返回，并打印出xxx，如下所示：

我们可以像上图那样演示这段程序，在cat pipe1后面增加了一个&符号。这个&符号代表指令在后台执行，不会阻塞用户继续输入。然后我们通过echo指令往pipe1中写入东西，接着就会看到xxx被打印出来。

总结 这节课我们为了学习管道，先简单接触了进程的概念，然后学习了重定向。之后我们学习了匿名管道的应用场景，匿名管道帮助我们把 Linux 指令串联起来形成很强的计算能力。特别是xargs指令支持模板化的生成指令，拓展了指令的能力。最后我们还学习了命名管道，命名管道让我们可以真实拿到一个管道文件，让多个程序之间可以方便地进行通信。

那么通过这节课的学习，你现在可以来回答本节关联的面试题目：xargs 的作用了吗？

老规矩，请你先在脑海里构思下给面试官的表述，并把你的思考写在留言区，然后再来看我接下来的分析。

【解析】 xargs 将标准输入流中的字符串分割成一条条子字符串，然后再按照我们自己想要的方式构建成一条条指令，大大拓展了 Linux 指令的能力。

比如我们可以用来按照某种特定的方式逐个处理一个目录下所有的文件；根据一个 IP 地址列表逐个 ping 这些 IP，收集到每个 IP 地址的延迟等。

思考题 最后我再给你出一道高中难度的指令题目。请问下面这段 Shell 程序的作用是什么？

复制代码 mkfifo pipe1 mkfifo pipe2 echo -n run | cat - pipe1 > pipe2 & cat pipe1 你可以把你的答案、思路或者课后总结写在留言区，这样可以帮助你产生更多的思考，这也是构建知识体系的一部分。经过长期的积累，相信你会得到意想不到的收获。如果你觉得今天的内容对你有所启发，欢迎分享给身边的朋友。期待看到你的思考！

小编有话说： 今天老师带你认识了面试中经常被问到的 Linux 指令，还初步讲解了进程的概念，但关于 Linux 的进阶知识以及最最让人头疼的网络知识，我们无法在一篇文章内讲完。想要了解更多知识，深入到真实互联网项目中学习实战技巧，也可以点击此处，即可跳转至《Java 就业急训营》介绍页面。

08 用户和权限管理指令

请简述 Linux 权限划分的原则？

我看到过这样一道面试题：请简述 Linux 权限划分的原则？

这种类型的面试题也是我比较喜欢的一种题目，因为它考察的不仅是一个具体的指令，还考察了候选人技术层面的认知。

如果你对 Linux 权限有较深的认知和理解，那么完全可以通过查资料去完成具体指令的执行。更重要的是，认知清晰的程序员可以把 Linux 权限管理的知识迁移到其他的系统设计中。而且我认为，能够对某个技术形成认知的人， 同样也会热爱思考，善于总结，这样的程序员是所有团队梦寐以求的。

因此，这次我们就把这道面试题作为引子，开启今天的学习。

权限抽象

一个完整的权限管理体系，要有合理的抽象。这里就包括对用户、进程、文件、内存、系统调用等抽象。下面我将带你一一了解。

首先，我们先来说说用户和组。Linux 是一个多用户平台，允许多个用户同时登录系统工作。Linux 将用户抽象成了账户，账户可以登录系统，比如通过输入登录名 + 密码的方式登录；也可以通过证书的方式登录。

但为了方便分配每个用户的权限，Linux 还支持组 （Group）账户。组账户是多个账户的集合，组可以为成员们分配某一类权限。每个用户可以在多个组，这样就可以利用组给用户快速分配权限。

组：权限的备份

组的概念有点像微信群。一个用户可以在多个群中。比如某个组中分配了 10 个目录的权限，那么新建用户的时候可以将这个用户增加到这个组中，这样新增的用户就不必再去一个个目录分配权限。

而每一个微信群都有一个群主，Root 账户也叫作超级管理员，就相当于微信群主，它对系统有着完全的掌控。一个超级管理员可以使用系统提供的全部能力。

此外，Linux 还对文件进行了权限抽象（注意目录也是一种文件）。Linux 中一个文件可以设置下面 3 种权限：

读权限（r）：控制读取文件。

写权限（w）：控制写入文件。

执行权限（x）：控制将文件执行，比如脚本、应用程序等。

然后每个文件又可以从 3 个维度去配置上述的 3 种权限：

用户维度。每个文件可以所属 1 个用户，用户维度配置的 rwx 在用户维度生效；

组维度。每个文件可以所属 1 个分组，组维度配置的 rwx 在组维度生效；

全部用户维度。设置对所有用户的权限。

因此 Linux 中文件的权限可以用 9 个字符，3 组rwx描述：第一组是用户权限，第二组是组权限，第三组是所有用户的权限。然后用-代表没有权限。比如rwxrwxrwx代表所有维度可以读写执行。rw--wxr-x代表用户维度不可以执行，组维度不可以读取，所有用户维度不可以写入。

通常情况下，如果用ls -l查看一个文件的权限，会有 10 个字符，这是因为第一个字符代表的是文件类型。我们在 06 课时讲解“几种常见的文件类型”时提到过，有管道文件、目录文件、链接文件等等。-代表普通文件、d代表目录、p代表管道。

学习了这套机制之后，请你跟着我的节奏一起思考以下 4 个问题。

文件被创建后，初始的权限如何设置？

需要全部用户都可以执行的指令，比如ls，它们的权限如何分配？

给一个文本文件分配了可执行权限会怎么样？

可不可以多个用户都登录root，然后只用root账户？

你可以把以上 4 个问题作为本课时的小测验，把你的思考或者答案写在留言区，然后再来看我接下来的分析。

问题一：初始权限问题

一个文件创建后，文件的所属用户会被设置成创建文件的用户。谁创建谁拥有，这个逻辑很顺理成章。但是文件的组又是如何分配的呢？

这里 Linux 想到了一个很好的办法，就是为每个用户创建一个同名分组。

比如说zhang这个账户创建时，会创建一个叫作zhang的分组。zhang登录之后，工作分组就会默认使用它的同名分组zhang。如果zhang想要切换工作分组，可以使用newgrp指令切换到另一个工作分组。因此，被创建文件所属的分组是当时用户所在的工作分组，如果没有特别设置，那么就属于用户所在的同名分组。

再说下文件的权限如何？文件被创建后的权限通常是：

rw-rw-r--

也就是用户、组维度不可以执行，所有用户可读。

问题二：公共执行文件的权限

前面提到过可以用which指令查看ls指令所在的目录，我们发现在/usr/bin中。然后用ls -l查看ls的权限，可以看到下图所示：

第一个-代表这是一个普通文件，后面的 rwx 代表用户维度可读写和执行；第二个r-x代表组维度不可以写；第三个r-x代表所有用户可以读和执行。后面的两个root，第一个是所属用户，第二个是所属分组。

到这里你可能会有一个疑问：如果一个文件设置为不可读，但是可以执行，那么结果会怎样？

答案当然是不可以执行，无法读取文件内容自然不可以执行。

问题三：执行文件

在 Linux 中，如果一个文件可以被执行，则可以直接通过输入文件路径（相对路径或绝对路径）的方式执行。如果想执行一个不可以执行的文件，Linux 则会报错。

当用户输入一个文件名，如果没有指定完整路径，Linux 就会在一部分目录中查找这个文件。你可以通过echo $PATH看到 Linux 会在哪些目录中查找可执行文件，PATH是 Linux 的环境变量，关于环境变量，我将在 “12 | 高级技巧之集群部署中”和你详细讨论。

问题四：可不可以都 root

最后一个问题是，可不可以都root？

答案当然是不行！这里先给你留个悬念，具体原因我们会在本课时最后来讨论。

到这里，用户和组相关权限就介绍完了。接下来说说内核和系统调用权限。 内核是操作系统连接硬件、提供最核心能力的程序。今天我们先简单了解一下，关于内核的详细知识，会在“14 |用户态和内核态：用户态线程和内核态线程有什么区别？”中介绍。

内核提供操作硬件、磁盘、内存分页、进程等最核心的能力，并拥有直接操作全部内存的权限，因此内核不能把自己的全部能力都提供给用户，而且也不能允许用户通过shell指令进行系统调用。Linux 下内核把部分进程需要的系统调用以 C 语言 API 的形式提供出来。部分系统调用会有权限检查，比如说设置系统时间的系统调用。

以上我们看到了 Linux 对系统权限的抽象。接下来我们再说说权限架构的思想。

权限架构思想

优秀的权限架构主要目标是让系统安全、稳定且用户、程序之间相互制约、相互隔离。这要求权限系统中的权限划分足够清晰，分配权限的成本足够低。

因此，优秀的架构，应该遵循最小权限原则（Least Privilege)。权限设计需要保证系统的安全和稳定。比如：每一个成员拥有的权限应该足够的小，每一段特权程序执行的过程应该足够的短。对于安全级别较高的时候，还需要成员权限互相牵制。比如金融领域通常登录线上数据库需要两次登录，也就是需要两个密码，分别掌握在两个角色手中。这样即便一个成员出了问题，也可以保证整个系统安全。

同样的，每个程序也应该减少权限，比如说只拥有少量的目录读写权限，只可以进行少量的系统调用。

权限划分

此外，权限架构思想还应遵循一个原则，权限划分边界应该足够清晰，尽量做到相互隔离。Linux 提供了用户和分组。当然 Linux 没有强迫你如何划分权限，这是为了应对更多的场景。通常我们服务器上重要的应用，会由不同的账户执行。比如说 Nginx、Web 服务器、数据库不会执行在一个账户下。现在随着容器化技术的发展，我们甚至希望每个应用独享一个虚拟的空间，就好像运行在一个单独的操作系统中一样，让它们互相不用干扰。

到这里，你可能会问：为什么不用 root 账户执行程序？ 下面我们就来说说 root 的危害。

举个例子，你有一个 Mysql 进程执行在 root（最大权限）账户上，如果有黑客攻破了你的 Mysql 服务，获得了在 Mysql 上执行 Sql 的权限，那么，你的整个系统就都暴露在黑客眼前了。这会导致非常严重的后果。

黑客可以利用 Mysql 的 Copy From Prgram 指令为所欲为，比如先备份你的关键文件，然后再删除他们，并要挟你通过指定账户打款。如果执行最小权限原则，那么黑客即便攻破我们的 Mysql 服务，他也只能获得最小的权限。当然，黑客拿到 Mysql 权限也是非常可怕的，但是相比拿到所有权限，这个损失就小多了。

分级保护

因为内核可以直接操作内存和 CPU，因此非常危险。驱动程序可以直接控制摄像头、显示屏等核心设备，也需要采取安全措施，比如防止恶意应用开启摄像头盗用隐私。通常操作系统都采取一种环状的保护模式。

如上图所示，内核在最里面，也就是 Ring 0。 应用在最外面也就是Ring 3。驱动在中间，也就是 Ring 1 和 Ring 2。对于相邻的两个 Ring，内层 Ring 会拥有较高的权限，可以改变外层的 Ring；而外层的 Ring 想要使用内层 Ring 的资源时，会有专门的程序（或者硬件）进行保护。

比如说一个 Ring3 的应用需要使用内核，就需要发送一个系统调用给内核。这个系统调用会由内核进行验证，比如验证用户有没有足够的权限，以及这个行为是否安全等等。

权限包围（Privilege Bracking）

之前我们讨论过，当 Mysql 跑在 root 权限时，如果 Mysql 被攻破，整个机器就被攻破了。因此我们所有应用都不要跑在 root 上。如果所有应用都跑在普通账户下，那么就会有临时提升权限的场景。比如说安装程序可能需要临时拥有管理员权限，将应用装到/usr/bin目录下。

Linux 提供了权限包围的能力。比如一个应用，临时需要高级权限，可以利用交互界面（比如让用户输入 root 账户密码）验证身份，然后执行需要高级权限的操作，然后马上恢复到普通权限工作。这样做可以减少应用在高级权限的时间，并做到专权专用，防止被恶意程序利用。

用户分组指令

上面我们讨论了 Linux 权限的架构，接下来我们学习一些具体的指令。

查看

如果想查看当前用户的分组可以使用groups指令。

上面指令列出当前用户的所有分组。第一个是同名的主要分组，后面从adm开始是次级分组。

我先给你介绍两个分组，其他分组你可以去查资料：

• adm 分组用于系统监控，比如/var/log中的部分日志就是 adm 分组。
• sudo 分组用户可以通过 sudo 指令提升权限。

如果想查看当前用户，可以使用id指令，如下所示：

• uid 是用户 id；
• gid 是组 id；
• groups 后面是每个分组和分组的 id。

如果想查看所有的用户，可以直接看/etc/passwd。

/etc/passwd这个文件存储了所有的用户信息，如下图所示：

创建用户&设置密码

创建用户用useradd指令。

sudo useradd foo

sudo 原意是 superuser do，后来演变成用另一个用户的身份去执行某个指令。如果没有指定需要 sudo 的用户，就像上面那样，就是以超级管理员的身份。因为 useradd 需要管理员身份。这句话执行后，会进行权限提升，并弹出输入管理员密码的输入界面。

passwd foo

创建分组

创建分组用groupadd指令。下面指令创建一个叫作hello的分组。

sudo groupadd hello

为用户增加次级分组

组分成主要分组（Primary Group）和次级分组（Secondary Group）。主要分组只有 1 个，次级分组可以有多个。如果想为用户添加一个次级分组，可以用usermod指令。下面指令将用户foo添加到sudo分组，从而foo拥有了sudo的权限。

sudo usermod -a -G sudo foo

代表append，-G代表一个次级分组的清单， 最后一个foo是账户名

修改用户主要分组

修改主要分组还是使用usermod指令。只不过参数是小写的-g。

sudo usermod -g somegroup foo

文件权限管理指令

接下来我们学习文件管理相关的指令。

查看

我们可以用ls -l查看文件的权限，相关内容在本课时前面已经介绍过了。

修改文件权限

可以用chmod修改文件权限，chmod（ change file mode bits），也就是我们之前学习的 rwx，只不过 rwx 在 Linux 中是用三个连在一起的二进制位来表示。

# 设置foo可以执行

chmod +x ./foo

# 不允许foo执行

chmod -x ./foo

# 也可以同时设置多个权限

chmod +rwx ./foo

因为rwx在 Linux 中用相邻的 3 个位来表示。比如说111代表rwx，101代表r-x。而rwx总共有三组，分别是用户权限、组权限和全部用户权限。也就是可以用1111111119 个 1 代表rwxrwxrwx。又因为11110 进制是 7，因此当需要一次性设置用户权限、组权限和所有用户权限的时候，我们经常用数字表示。

# 设置rwxrwxrwx (111111111 -> 777)
chmod 777 ./foo
# 设置rw-rw-rw-(110110110 -> 666)
chmod 666 ./foo

修改文件所属用户

有时候我们需要修改文件所属用户，这个时候会使用chown指令。 下面指令修改foo文件所属的用户为bar。

chown bar ./foo

还有一些情况下，我们需要同时修改文件所属的用户和分组，比如我们想修改foo的分组位g，用户为u，可以使用：

chown g.u ./foo

总结

这节课我们学习 Linux 的权限管理的抽象和架构思想。Linux 对用户、组、文件、系统调用等都进行了完善的抽象。之后，我们讨论了最小权限原则。最后我们对用户分组管理和文件权限管理两部分重要的指令进行了系统学习。

那么通过这节课的学习，你现在可以来回答本节关联的面试题目：请简述 Linux 权限划分的原则？

老规矩，请你先在脑海里构思下给面试官的表述，并把你的思考写在留言区，然后再来看我接下来的分析。

【解析】 Linux 遵循最小权限原则。

1. 每个用户掌握的权限应该足够小，每个组掌握的权限也足够小。实际生产过程中，最好管理员权限可以拆分，互相牵制防止问题。
2. 每个应用应当尽可能小的使用权限。最理想的是每个应用单独占用一个容器（比如 Docker），这样就不存在互相影响的问题。即便应用被攻破，也无法攻破 Docker 的保护层。
3. 尽可能少的root。如果一个用户需要root能力，那么应当进行权限包围——马上提升权限（比如 sudo），处理后马上释放权限。
4. 系统层面实现权限分级保护，将系统的权限分成一个个 Ring，外层 Ring 调用内层 Ring 时需要内层 Ring 进行权限校验。

思考题

最后再给你留一道实战问题，希望你在课下自己尝试一下。如果一个目录是只读权限，那么这个目录下面的文件还可写吗？

你可以把你的答案、思路或者课后总结写在留言区，这样可以帮助你产生更多的思考，这也是构建知识体系的一部分。经过长期的积累，相信你会得到意想不到的收获。如果你觉得今天的内容对你有所启发，欢迎分享给身边的朋友。期待看到你的思考！

09 Linux 中的网络指令

如何查看一个域名有哪些 NS 记录？

我看到过一道关于 Linux 指令的面试题：如何查看一个域名有哪些 NS 记录？

这类题目是根据一个场景，考察一件具体的事情如何处理。虽然你可以通过查资料找到解决方案，但是，这类问题在面试中还是有必要穿插一下，用于确定求职者技能是否熟练、经验是否丰富。特别是计算机网络相关的指令，平时在远程操作、开发、联调、Debug 线上问题的时候，会经常用到。

Linux 中提供了不少网络相关的指令，因为网络指令比较分散，本课时会从下面几个维度给你介绍，帮助你梳理常用的网络指令：

• 远程操作；
• 查看本地网络状态；
• 网络测试；
• DNS 查询；
• HTTP。

这块知识从体系上属于 Linux 指令，同时也关联了很多计算机网络的知识，比如说 TCP/IP 协议、UDP 协议，我会在“模块七”为你简要介绍。

远程操作指令

远程操作指令用得最多的是ssh，ssh指令允许远程登录到目标计算机并进行远程操作和管理。还有一个比较常用的远程指令是scp，scp帮助我们远程传送文件。

ssh（Secure Shell）

有一种场景需要远程登录一个 Linux 系统，这时我们会用到ssh指令。比如你想远程登录一台机器，可以使用ssh user@ip的方式，如下图所示：

上图中，我在使用ssh指令从机器u1登录我的另一台虚拟机u2。这里u1和u2对应着 IP 地址，是我在/etc/hosts中设置的，如下图所示：

/etc/hosts这个文件可以设置 IP 地址对应的域名。我这里是一个小集群，总共有两台机器，因此我设置了方便记忆和操作的名字。

scp

另一种场景是我需要拷贝一个文件到远程，这时可以使用scp指令，如下图，我使用scp指令将本地计算机的一个文件拷贝到了 ubuntu 虚拟机用户的家目录中。

比如从u1拷贝家目录下的文件a.txt到u2。家目录有一个简写，就是用~。具体指令见下图：

输入 scp 指令之后会弹出一个提示，要求输入密码，系统验证通过后文件会被成功拷贝。

查看本地网络状态

如果你想要了解本地的网络状态，比较常用的网络指令是ifconfig和netstat。

ifconfig

当你想知道本地ip以及本地有哪些网络接口时，就可以使用ifconfig指令。你可以把一个网络接口理解成一个网卡，有时候虚拟机会装虚拟网卡，虚拟网卡是用软件模拟的网卡。

比如：VMware 为每个虚拟机创造一个虚拟网卡，通过虚拟网卡接入虚拟网络。当然物理机也可以接入虚拟网络，它可以通过虚拟网络向虚拟机的虚拟网卡上发送信息。

下图是我的 ubuntu 虚拟机用 ifconfig 查看网络接口信息。

可以看到我的这台 ubuntu 虚拟机一共有 2 个网卡，ens33 和 lo。lo是本地回路（local lookback），发送给lo就相当于发送给本机。ens33是一块连接着真实网络的虚拟网卡。

netstat

另一个查看网络状态的场景是想看目前本机的网络使用情况，这个时候可以用netstat。

默认行为

不传任何参数的netstat帮助查询所有的本地 socket，下图是netstat | less的结果。

如上图，我们看到的是 socket 文件。socket 是网络插槽被抽象成了文件，负责在客户端、服务器之间收发数据。当客户端和服务端发生连接时，客户端和服务端会同时各自生成一个 socket 文件，用于管理这个连接。这里，可以用wc -l数一下有多少个socket。

你可以看到一共有 615 个 socket 文件，因为有很多 socket 在解决进程间的通信。就是将两个进程一个想象成客户端，一个想象成服务端。并不是真的有 600 多个连接着互联网的请求。

查看 TCP 连接

如果想看有哪些 TCP 连接，可以使用netstat -t。比如下面我通过netstat -t看tcp协议的网络情况：

这里没有找到连接中的tcp，因为我们这台虚拟机当时没有发生任何的网络连接。因此我们尝试从机器u2（另一台机器）ssh 登录进u1，再看一次：

如上图所示，可以看到有一个 TCP 连接了。

查看端口占用

还有一种非常常见的情形，我们想知道某个端口是哪个应用在占用。如下图所示：

这里我们看到 22 端口被 sshd，也就是远程登录模块被占用了。-n是将一些特殊的端口号用数字显示，-t是指看 TCP 协议，-l是只显示连接中的连接，-p是显示程序名称。

网络测试

当我们需要测试网络延迟、测试服务是否可用时，可能会用到ping和telnet指令。

ping

想知道本机到某个网站的网络延迟，就可以使用ping指令。如下图所示：

ping一个网站需要使用 ICMP 协议。因此你可以在上图中看到 icmp 序号。 这里的时间time是往返一次的时间。ttl叫作 time to live，是封包的生存时间。就是说，一个封包从发出就开始倒计时，如果途中超过 128ms，这个包就会被丢弃。如果包被丢弃，就会被算进丢包率。

另外ping还可以帮助我们看到一个网址的 IP 地址。 通过网址获得 IP 地址的过程叫作 DNS Lookup（DNS 查询）。ping利用了 DNS 查询，但是没有显示全部的 DNS 查询结果

telnet

有时候我们想知道本机到某个 IP + 端口的网络是否通畅，也就是想知道对方服务器是否在这个端口上提供了服务。这个时候可以用telnet指令。 如下图所示：

elnet 执行后会进入一个交互式的界面，比如这个时候，我们输入下图中的文字就可以发送 HTTP 请求了。如果你对 HTTP 协议还不太了解，建议自学一下 HTTP 协议。

如上图所示，第 5 行的GET 和第 6 行的HOST是我输入的。 拉勾网返回了一个 301 永久跳转。这是因为拉勾网尝试把http协议链接重定向到https。

DNS 查询

我们排查网络故障时想要进行一次 DNS Lookup，想知道一个网址 DNS 的解析过程。这个时候有多个指令可以用。

host

host 就是一个 DNS 查询工具。比如我们查询拉勾网的 DNS，如下图所示：

我们看到拉勾网 www.lagou.com 是一个别名，它的原名是 lgmain 开头的一个域名，这说明拉勾网有可能在用 CDN 分发主页（关于 CDN，）。

上图中，可以找到 3 个域名对应的 IP 地址。

如果想追查某种类型的记录，可以使用host -t。比如下图我们追查拉勾的 AAAA 记录，因为拉勾网还没有部署 IPv6，所以没有找到。

dig

dig指令也是一个做 DNS 查询的。不过dig指令显示的内容更详细。下图是dig拉勾网的结果

从结果可以看到www.lagou.com 有一个别名，用 CNAME 记录定义 lgmain 开头的一个域名，然后有 3 条 A 记录，通常这种情况是为了均衡负载或者分发内容。

HTTP 相关

最后我们来说说http协议相关的指令。

curl

如果要在命令行请求一个网页，或者请求一个接口，可以用curl指令。curl支持很多种协议，比如 LDAP、SMTP、FTP、HTTP 等。

我们可以直接使用 curl 请求一个网址，获取资源，比如我用 curl 直接获取了拉勾网的主页，如下图所示：

如果只想看 HTTP 返回头，可以使用curl -I。

另外curl还可以执行 POST 请求，比如下面这个语句：

curl -d '{"x" : 1}' -H "Content-Type: application/json" -X POST http://localhost:3000/api

curl在向localhost:3000发送 POST 请求。-d后面跟着要发送的数据， -X后面是用到的 HTTP 方法，-H是指定自定义的请求头。

总结

这节课我们学习了不少网络相关的 Linux 指令，这些指令是将来开发和调试的强大工具。这里再给你复习一下这些指令：

• 远程登录的 ssh 指令；
• 远程拷贝文件的 scp 指令；
• 查看网络接口的 ifconfig 指令；
• 查看网络状态的 netstat 指令；
• 测试网络延迟的 ping 指令；
• 可以交互式调试和服务端的 telnet 指令；
• 两个 DNS 查询指令 host 和 dig；
• 可以发送各种请求包括 HTTPS 的 curl 指令。

那么通过这节课的学习，你现在可以来回答本节关联的面试题目：如何查看一个域名有哪些 NS 记录了吗？

老规矩，请你先在脑海里构思下给面试官的表述，并把你的思考写在留言区，然后再来看我接下来的分析。

【解析】 host 指令提供了一个-t参数指定需要查找的记录类型。我们可以使用host -t ns {网址}。另外 dig 也提供了同样的能力。如果你感兴趣，还可以使用man对系统进行操作。

思考题

最后我再给你出一道需要查资料的思考题目：如何查看正在 TIME_WAIT 状态的连接数量？

你可以把你的答案、思路或者课后总结写在留言区，这样可以帮助你产生更多的思考，这也是构建知识体系的一部分。经过长期的积累，相信你会得到意想不到的收获。如果你觉得今天的内容对你有所启发，欢迎分享给身边的朋友。期待看到你的思考！

09 | Linux 中的网络指令：如何查看一个域名有哪些 NS 记录？

10:04

重学操作系统

10 软件的安装

编译安装和包管理器安装有什么优势和劣势？

今天给你带来的面试题是：编译安装和包管理器安装有什么优势和劣势？为了搞清楚这个问题，就引出了今天的话题，在 Linux 上如何安装程序。

在 Linux 上安装程序大概有 2 种思路：

1. 直接编译源代码；
2. 使用包管理器。

受开源运动影响，Linux 上很多软件都可以拿到源代码，这也是 Linux 能取得成功的一个重要原因。接下来我们先尝试用包管理器安装应用，然后再用一个实战的例子，教你如何编译安装nginx。

包管理器使用

Linux 下的应用程序多数以软件包的形式发布，用户拿到对应的包之后，使用包管理器进行安装。说到包管理器，就要提到dpkg和rpm。

我们先说说包。 Linux 下两大主流的包就是rpm和dpkg。

dpkg（debian package），是linux一个主流的社区分支开发出来的。社区就是开源社区，有很多世界顶级的程序员会在社区贡献代码，比如 github。一般衍生于debian的 Linux 版本都支持dpkg，比如ubuntu。

rpm（redhatpackage manager）。在正式讲解之前，我们先来聊聊 RedHat 这家公司。

RedHat 是一个做 Linux 的公司，你可以把它理解成一家“保险公司”。 很多公司购买红帽的服务，是为了给自己的业务上一个保险。以防万一哪天公司内部搞不定 Linux 底层，或者底层有 Bug，再或者底层不适合当下的业务发展，需要修改等问题，红帽的工程师都可以帮企业解决。

再比如，RedHat 收购了JBoss，把 JBoss 改名为 WildFly。 像 WildFly 这种工具更多是面向企业级，比如没有大量研发团队的企业会更倾向使用成熟的技术。RedHat 公司也有自己的 Linux，就叫作 RedHat。RedHat 系比较重要的 Linux 有 RedHat/Fedora 等。

无论是dpkg还是rpm都抽象了自己的包格式，就是以.dpkg或者.rpm结尾的文件。

dpkg和rpm也都提供了类似的能力：

• 查询是否已经安装了某个软件包；
• 查询目前安装了什么软件包；
• 给定一个软件包，进行安装；
• 删除一个安装好的软件包。

关于dpkg和rpm的具体用法，你可以用man进行学习。接下来我们聊聊yum和apt。

自动依赖管理

Linux 是一个开源生态，因此工具非常多。工具在给用户使用之前，需要先打成dpkg或者rpm包。 有的时候一个包会依赖很多其他的包，而dpkg和rpm不会对这种情况进行管理，有时候为了装一个包需要先装十几个依赖的包，过程非常艰辛！因此现在多数情况都在用yum和apt。

yum

你可能会说，我不用yum也不用apt，我只用docker。首先给你一个连击 666，然后我还是要告诉你，如果你做docker镜像，那么还是要用到yum和apt，因此还是有必要学一下。

yum的全名是 Yellodog Updator，Modified。 看名字就知道它是基于Yellodog Updator这款软件修改而来的一个工具。yum是 Python 开发的，提供的是rpm包，因此只有redhat系的 Linux，比如 Fedora，Centos 支持yum。yum的主要能力就是帮你解决下载和依赖两个问题。

下载之所以是问题，是因为 Linux 生态非常庞大，有时候用户不知道该去哪里下载一款工具。比如用户想安装vim，只需要输入sudo yum install vim就可以安装了。yum的服务器收集了很多linux软件，因此yum会帮助用户找到vim的包。

另一方面，yum帮助用户解决了很多依赖，比如用户安装一个软件依赖了 10 个其他的软件，yum会把这 11 个软件一次性的装好。

关于yum的具体用法，你可以使用man工具进行学习。

apt

接下来我们来重点说说apt，然后再一起尝试使用。因为我这次是用ubuntuLinux 给你教学，所以我以 apt 为例子，yum 的用法是差不多的，你可以自己 man 一下。

apt全名是 Advanced Packaging Tools，是一个debian及其衍生 Linux 系统下的包管理器。由于advanced（先进）是相对于dpkg而言的，因此它也能够提供和yum类似的下载和依赖管理能力。比如在没有vim的机器上，我们可以用下面的指令安装vim。如下图所示：

然后用dpkg指令查看 vim 的状态是ii。第一个i代表期望状态是已安装，第二个i代表实际状态是已安装。

下面我们卸载vim，再通过dpkg查看，如下图所示：

我们看到 vim 的状态从ii变成了rc，r是期望删除，c是实际上还有配置文件遗留。 如果我们想彻底删除配置文件，可以使用apt purge，就是彻底清除的意思，如下图所示：

再使用dpkg -l时，vim已经清除了。

期待结果是u就是 unkonw（未知）说明已经没有了。实际结果是n，就是 not-installed（未安装）。

如果想查询mysql相关的包，可以使用apt serach mysql，这样会看到很多和mysql相关的包，如下图所示：

如果我们想精确查找一个叫作mysql-server的包，可以用apt list。

这里我们找到了mysql-server包。

另外有时候国内的apt服务器速度比较慢，你可以尝试使用阿里云的镜像服务器。具体可参考我下面的操作：

cat /etc/apt/sources.list

--以下是文件内容--

deb http://mirrors.aliyun.com/ubuntu/ focal main restricted universe multiverse

deb http://mirrors.aliyun.com/ubuntu/ focal-security main restricted universe multiverse

deb http://mirrors.aliyun.com/ubuntu/ focal-updates main restricted universe multiverse

deb http://mirrors.aliyun.com/ubuntu/ focal-proposed main restricted universe multiverse

deb http://mirrors.aliyun.com/ubuntu/ focal-backports main restricted universe multiverse

deb-src http://mirrors.aliyun.com/ubuntu/ focal main restricted universe multiverse

deb-src http://mirrors.aliyun.com/ubuntu/ focal-security main restricted universe multiverse

deb-src http://mirrors.aliyun.com/ubuntu/ focal-updates main restricted universe multiverse

deb-src http://mirrors.aliyun.com/ubuntu/ focal-proposed main restricted universe multiverse

deb-src http://mirrors.aliyun.com/ubuntu/ focal-backports main restricted universe multiverse

镜像地址可以通过/etc/apt/sources.list配置，注意focal是我用的ubuntu版本，你可以使用sudo lsb_release查看自己的 Ubuntu 版本。如果你想用我上面给出的内容覆盖你的sources.list，只需把版本号改成你自己的。注意，每个ubuntu版本都有自己的代号。

通过上面的学习，相信你已经逐渐了解了包管理器的基本概念和使用。如果你是centos或者fedora，需要自己man一下yum。

编译安装 Nginx

接下来我们说说编译安装 Nginx（发音是 engine X），是一个家喻户晓的 Web 服务器。 它的发明者是俄国的伊戈尔·赛索耶夫。赛索耶夫 2002 年开始写 Nginx，主要目的是解决同一个互联网节点同时进入大量并发请求的问题。注意，大量并发请求不是大量 QPS 的意思，QPS 是吞吐量大，需要快速响应，而高并发时则需要合理安排任务调度。

后来塞索耶夫成立了 Nginx 公司， 2018 年估值到达到 4.3 亿美金。现在基本上国内大厂的 Web 服务器都是基于 Nginx，只不过进行了特殊的修改，比如淘宝用 Tengine。

下面我们再来看看源码安装，在 Linux 上获取nginx源码，可以去搜索 Nginx 官方网站，一般都会提供源码包。

如上图所示，可以看到 nginx-1.18.0 的网址是：http://nginx.org/download/nginx-1.19.2.tar.gz。然后我们用 wget 去下载这个包。 wget 是 GNU 项目下的下载工具，GNU 是早期unix项目的一个变种。linux下很多工具都是从unix继承来的，这就是开源的好处，很多工具不用再次开发了。你可能很难想象windows下的命令工具可以在linux下用，但是linux下的工具却可以在任何系统中用。 因此，linux下面的工具发展速度很快，如今已成为最受欢迎的服务器操作系统。

当然也有同学的机器上没有wget，那么你可以用apt安装一下。

第一步：下载源码。我们使用wget下载nginx源码包：

可以像我这样使用cd先切换到家目录。

• 第二步：解压。我们解压下载好的nginx源码包。

用ls发现包已经存在了，然后使用tar命令解压。

tar是用来打包和解压用的。之所以叫作tar是有一些历史原因：t代表tape（磁带）；ar是 archive（档案）。因为早期的存储介质很小，人们习惯把文件打包然后存储到磁带上，那时候unix用的命令就是tar。因为linux是个开源生态，所以就沿袭下来继续使用tar。

-x代表 extract（提取）。-z代表gzip，也就是解压gz类型的文件。-v代表 verbose（显示细节），如果你不输入-v，就不会打印解压过程了。-f代表 file，这里指的是要操作文件，而不是磁带。 所以tar解压通常带有x和f，打包通常是c就是 create 的意思。

• 第三步：配置和解决依赖。解压完，我们进入nginx的目录看一看。 如下图所示：

可以看到一个叫作configure的文件是绿色的，也就是可执行文件。然后我们执行 configure 文件进行配置，这个配置文件来自一款叫作autoconf的工具，也是 GNU 项目下的，说白了就是bash（Bourne Shell）下的安装打包工具（就是个安装程序）。这个安装程序支持很多配置，你可以用./configure --help看到所有的配置项，如下图所示：

这里有几个非常重要的配置项，叫作prefix。prefix配置项决定了软件的安装目录。如果不配置这个配置项，就会使用默认的安装目录。sbin-path决定了nginx的可执行文件的位置。conf-path决定了nginx配置文件的位置。我们都使用默认，然后执行./configure，如下图所示：

autoconf进行依赖检查的时候，报了一个错误，cc 没有找到。这是因为机器上没有安装gcc工具，gcc 是家喻户晓的工具套件，全名是 GNU Compiler Collection——里面涵盖了包括 c/c++ 在内的多门语言的编译器。

我们用包管理器，安装gcc，如下图所示。安装gcc通常是安装build-essential这个包。

安装完成之后，再执行./configure，如下图所示：

我们看到配置程序开始执行。但是最终报了一个错误，如下图所示：

报错的内容是，nginx的HTTP rewrite模块，需要PCRE库。 PCRE 是perl语言的兼容正则表达式库。perl语言一直以支持原生正则表达式，而受到广大编程爱好者的喜爱。我曾经看到过一个 IBM 的朋友用perl加上wget就实现了一个简单的爬虫。接下来，我们开始安装PCRE。

一般这种依赖库，会叫pcre-dev或者libpcre。用apt查询了一下，然后grep。

我们看到有pcre2也有pcre3。这个时候可以考虑试试pcre3。

安装完成之后再试试./configure，提示还需要zlib。然后我们用类似的方法解决zlib依赖。

zlib包的名字叫zlib1g不太好找，需要查资料才能确定是这个名字。

我们再尝试配置，终于配置成功了。

• 第四步：编译和安装。

通常配置完之后，我们输入make && sudo make install进行编译和安装。make是linux下面一个强大的构建工具。autoconf也就是./configure会在当前目录下生成一个 MakeFile 文件。make会根据MakeFile文件编译整个项目。编译完成后，能够形成和当前操作系统以及 CPU 指令集兼容的二进制可执行文件。然后再用make install安装。&&符号代表执行完make再去执行make installl。

你可以看到编译是个非常慢的活。等待了差不多 1 分钟，终于结束了。nginx被安装到了/usr/local/nginx中，如果需要让nginx全局执行，可以设置一个软连接到/usr/local/bin，具体如下：

ln -sf /usr/local/nginx/sbin/nginx /usr/local/sbin/nginx

为什么会有编译安装？

学完整个编译安装 Ngnix 过程后，你可能会问，为什么会有编译安装这么复杂的事情。

原来使用 C/C++ 写的程序存在一个交叉编译的问题。就是写一次程序，在很多个平台执行。而不同指令集的 CPU 指令，还有操作系统的可执行文件格式是不同的。因此，这里有非常多的现实问题需要解决。一般是由操作系统的提供方，比如 RedHat 来牵头解决这些问题。你可以用apt等工具提供给用户已经编译好的包。apt会自动根据用户的平台类型选择不同的包。

但如果某个包没有在平台侧注册，也没有提供某个 Linux 平台的软件包，我们就需要回退到编译安装，通过源代码直接在某个平台安装。

总结

这节课我们学习了在 Linux 上安装软件，简要介绍了dpkg和rpm，然后介绍了能够解决依赖和帮助用户下载的yum和apt。重点带你使用了apt，在这个过程中看到了强大的包管理机制，今天的maven、npm、pip都继承了这样一个特性。最后我们还尝试了一件高难度的事情，就是编译安装nginx。

那么通过这节课的学习，你现在可以来回答本节关联的面试题目：编译安装和包管理安装有什么优势和劣势了吗？

老规矩，请你先在脑海里构思下给面试官的表述，并把你的思考写在留言区，然后再来看我接下来的分析。

【解析】 包管理安装很方便，但是有两点劣势。

第一点是需要提前将包编译好，因此有一个发布的过程，如果某个包没有发布版本，或者在某个平台上找不到对应的发布版本，就需要编译安装。

第二点就是如果一个软件的定制程度很高，可能会在编译阶段传入参数，比如利用configure传入配置参数，这种时候就需要编译安装。

思考题

最后我再给你出一道思考题：如果你在编译安装 MySQL 时，发现找不到 libcrypt.so，应该如何处理？

你可以把你的答案、思路或者课后总结写在留言区，这样可以帮助你产生更多的思考，这也是构建知识体系的一部分。经过长期的积累，相信你会得到意想不到的收获。如果你觉得今天的内容对你有所启发，欢迎分享给身边的朋友。期待看到你的思考！

加到/usr/lib路径下安装libcrypt.so，将libcrypt.so添加到链接路径

11 | 高级技巧之日志分析：

利用 Linux 指令分析 Web 日志

著名的黑客、自由软件运动的先驱理查德.斯托曼说过，“编程不是科学，编程是手艺”。可见，要想真正搞好编程，除了学习理论知识，还需要在实际的工作场景中进行反复的锤炼。

所以今天我们将结合实际的工作场景，带你利用 Linux 指令分析 Web 日志，这其中包含很多小技巧，掌握了本课时的内容，将对你将来分析线上日志、了解用户行为和查找问题有非常大地帮助。

本课时将用到一个大概有 5W 多条记录的nginx日志文件，你可以在 GitHub上下载。 下面就请你和我一起，通过分析这个nginx日志文件，去锤炼我们的手艺。

第一步：能不能这样做？

当我们想要分析一个线上文件的时候，首先要思考，能不能这样做？ 这里你可以先用htop指令看一下当前的负载。如果你的机器上没有htop，可以考虑用yum或者apt去安装。

如上图所示，我的机器上 8 个 CPU 都是 0 负载，2G的内存用了一半多，还有富余。 我们用wget将目标文件下载到本地（如果你没有 wget，可以用yum或者apt安装）。

wget 某网址（自己替代）

然后我们用ls查看文件大小。发现这只是一个 7M 的文件，因此对线上的影响可以忽略不计。如果文件太大，建议你用scp指令将文件拷贝到闲置服务器再分析。下图中我使用了--block-size让ls以M为单位显示文件大小。

确定了当前机器的CPU和内存允许我进行分析后，我们就可以开始第二步操作了。

第二步：LESS 日志文件

在分析日志前，给你提个醒，记得要less一下，看看日志里面的内容。之前我们说过，尽量使用less这种不需要读取全部文件的指令，因为在线上执行cat是一件非常危险的事情，这可能导致线上服务器资源不足。

如上图所示，我们看到nginx的access_log每一行都是一次用户的访问，从左到右依次是：

• IP 地址；
• 时间；
• HTTP 请求的方法、路径和协议版本、返回的状态码；
• User Agent。

第三步：PV 分析

PV（Page View），用户每访问一个页面就是一次Page View。对于nginx的acess_log来说，分析 PV 非常简单，我们直接使用wc -l就可以看到整体的PV。 请求量

如上图所示：我们看到了一共有 51462 条 PV。

第四步：PV 分组

通常一个日志中可能有几天的 PV，为了得到更加直观的数据，有时候需要按天进行分组。为了简化这个问题，我们先来看看日志中都有哪些天的日志。

使用awk '{print $4}' access.log | less可以看到如下结果。awk是一个处理文本的领域专有语言。这里就牵扯到领域专有语言这个概念，英文是Domain Specific Language。领域专有语言，就是为了处理某个领域专门设计的语言。比如awk是用来分析处理文本的DSL，html是专门用来描述网页的DSL，SQL是专门用来查询数据的DSL……大家还可以根据自己的业务设计某种针对业务的DSL。

你可以看到我们用$4代表文本的第 4 列，也就是时间所在的这一列，如下图所示：

我们想要按天统计，可以利用 awk提供的字符串截取的能力。

上图中，我们使用awk的substr函数，数字2代表从第 2 个字符开始，数字11代表截取 11 个字符。

接下来我们就可以分组统计每天的日志条数了。

上图中，使用sort进行排序，然后使用uniq -c进行统计。你可以看到从 2015 年 5 月 17 号一直到 6 月 4 号的日志，还可以看到每天的 PV 量大概是在 2000~3000 之间。

第五步：分析 UV

接下来我们分析 UV。UV（Uniq Visitor），也就是统计访问人数。通常确定用户的身份是一个复杂的事情，但是我们可以用 IP 访问来近似统计 UV。

上图中，我们使用 awk 去打印$1也就是第一列，接着sort排序，然后用uniq去重，最后用wc -l查看条数。 这样我们就知道日志文件中一共有2660个 IP，也就是2660个 UV。

第六步：分组分析 UV

接下来我们尝试按天分组分析每天的 UV 情况。这个情况比较复杂，需要较多的指令，我们先创建一个叫作sum.sh的bash脚本文件，写入如下内容：

#!/usr/bin/bash

awk '{print substr($4, 2, 11) " " $1}' access.log |\

    sort | uniq |\

    awk '{uv[$1]++;next}END{for (ip in uv) print ip, uv[ip]}'

awk '{print substr($4, 2, 11) " " $1}' access.log |\

    sort | uniq |\

    awk ' { uv[$1]++} END { for (date in uv) print date, uv[date]}'

    # 构建字典 值自增 迭代字典 打印字典key value

具体分析如下。

• 文件首部我们使用#!，表示我们将使用后面的/usr/bin/bash执行这个文件。
• 第一次awk我们将第 4 列的日期和第 1 列的ip地址拼接在一起。
• 下面的sort是把整个文件进行一次字典序排序，相当于先根据日期排序，再根据 IP 排序。
• 接下来我们用uniq去重，日期 +IP 相同的行就只保留一个。
• 最后的awk我们再根据第 1 列的时间和第 2 列的 IP 进行统计。

awk本身是逐行进行处理的。因此我们的next关键字是提醒awk跳转到下一行输入。 对每一行输入，awk会根据第 1 列的字符串（也就是日期）进行累加。之后的END关键字代表一个触发器，就是 END 后面用 {} 括起来的语句会在所有输入都处理完之后执行——当所有输入都执行完，结果被累加到uv中后，通过foreach遍历uv中所有的key，去打印ip和ip对应的数量。

编写完上面的脚本之后，我们保存退出编辑器。接着执行chmod +x ./sum.sh，给sum.sh增加执行权限。然后我们可以像下图这样执行，获得结果：

如上图，IP地址已经按天进行统计好了。

总结

今天我们结合一个简单的实战场景——Web 日志分析与统计练习了之前学过的指令，提高熟练程度。此外，我们还一起学习了新知识——功能强大的awk文本处理语言。在实战中，我们对一个nginx的access_log进行了简单的数据分析，直观地获得了这个网站的访问情况。

我们在日常的工作中会遇到各种各样的日志，除了 nginx 的日志，还有应用日志、前端日志、监控日志等等。你都可以利用今天学习的方法，去做数据分析，然后从中得出结论。

思考题

接下来我给你出 2 个场景思考题，帮助你继续练习使用 Linux 指令。

1. 根据今天的 access_log 分析出有哪些终端访问了这个网站，并给出分组统计结果。
2. 根据今天的 access_log 分析出访问量 Top 前三的网页。

你可以把你的答案、思路或者课后总结写在留言区，这样可以帮助你产生更多的思考，这也是构建知识体系的一部分。经过长期的积累，相信你会得到意想不到的收获。如果你觉得今天的内容对你有所启发，欢迎分享给身边的朋友。期待看到你的思考！

12 | 高级技巧之集群部署：

利用 Linux 指令同时在多台机器部署程序

Linux 指令是由很多顶级程序员共同设计的，彼此独立，又互成一体，专注、高效。

通过前面的学习，相信你已经掌握了一些基础指令的使用方法，今天我们继续挑战一个更复杂的问题——用 Linux 指令管理一个集群。这属于 Linux 指令的高级技巧，所谓高级技巧并不是我们要学习更多的指令，而是要把之前所学的指令进行排列组合。

通过把简单的指令组合起来，分层组织成最终的多个脚本文件，解决一个复杂的工程问题：在成百上千的集群中安装一个 Java 环境。接下来，请你带着这个目标，开启今天的学习。

第一步：搭建学习用的集群

第一步我们先搭建一个学习用的集群。这里简化一下模型。我在自己的电脑上装一个ubuntu桌面版的虚拟机，然后再装两个ubuntu服务器版的虚拟机。

相对于桌面版，服务器版对资源的消耗会少很多。我将教学材料中桌面版的ubuntu命名为u1，两个用来被管理的服务器版ubuntu叫作v1和v2。

用桌面版的原因是：我喜欢ubuntu漂亮的开源字体，这样会让我在给你准备素材的时候拥有一个好心情。如果你对此感兴趣，可以搜索ubuntu mono，尝试把这个字体安装到自己的文本编辑器中。不过我还是觉得在ubuntu中敲代码更有感觉。

注意，我在这里只用了 3 台服务器，但是接下来我们要写的脚本是可以在很多台服务器之间复用的。

第二步：循环遍历 IP 列表

你可以想象一个局域网中有很多服务器需要管理，它们彼此之间网络互通，我们通过一台主服务器对它们进行操作，即通过u1操作v1和v2。

在主服务器上我们维护一个ip地址的列表，保存成一个文件，如下图所示：

目前iplist中只有两项，但是如果我们有足够的机器，可以在里面放成百上千项。接下来，请你思考shell如何遍历这些ip？

你可以先尝试实现一个最简单的程序，从文件iplist中读出这些ip并尝试用for循环遍历这些ip，具体程序如下：

#!/usr/bin/bash

readarray -t ips < iplist

for ip in ${ips[@]}

do

    echo $ip

done

首行的#!叫作 Shebang。Linux 的程序加载器会分析 Shebang 的内容，决定执行脚本的程序。这里我们希望用bash来执行这段程序，因为我们用到的 readarray 指令是bash 4.0后才增加的能力。

readarray指令将 iplist 文件中的每一行读取到变量ips中。ips是一个数组，可以用echo ${ips[@]}打印其中全部的内容：@代表取数组中的全部内容；$符号是一个求值符号。不带$的话，ips[@]会被认为是一个字符串，而不是表达式。

for循环遍历数组中的每个ip地址，echo把地址打印到屏幕上。

如果用shell执行上面的程序会报错，因为readarray是bash 4.0后支持的能力，因此我们用chomd为foreach.sh增加执行权限，然后直接利用shebang的能力用bash执行，如下图所示：

第三步：创建集群管理账户

为了方便集群管理，通常使用统一的用户名管理集群。这个账号在所有的集群中都需要保持命名一致。比如这个集群账号的名字就叫作lagou。

接下来我们探索一下如何创建这个账户lagou，如下图所示：

上面我们创建了lagou账号，然后把lagou加入sudo分组。这样lagou就有了sudo成为root的能力，如下图所示：

接下来，我们设置lagou用户的初始化shell是bash，如下图所示：

这个时候如果使用命令su lagou，可以切换到lagou账号，但是你会发现命令行没有了颜色。因此我们可以将原来用户下面的.bashrc文件拷贝到/home/lagou目录下，如下图所示：

这样，我们就把一些自己平时用的设置拷贝了过去，包括终端颜色的设置。.bashrc是启动bash的时候会默认执行的一个脚本文件。

接下来，我们编辑一下/etc/sudoers文件，增加一行lagou ALL=(ALL) NOPASSWD:ALL表示lagou账号 sudo 时可以免去密码输入环节，如下图所示：

我们可以把上面的完整过程整理成指令文件，create_lagou.sh：

sudo useradd -m -d /home/lagou lagou

sudo passwd lagou

sudo usermod -G sudo lagou

sudo usermod --shell /bin/bash lagou

sudo cp ~/.bashrc /home/lagou/

sudo chown lagou.lagou /home/lagou/.bashrc

sduo sh -c 'echo "lagou ALL=(ALL)  NOPASSWD:ALL">>/etc/sudoers'

你可以删除用户lagou，并清理/etc/sudoers文件最后一行。用指令userdel lagou删除账户，然后执行create_lagou.sh重新创建回lagou账户。如果发现结果一致，就代表create_lagou.sh功能没有问题。

最后我们想在v1``v2上都执行create_logou.sh这个脚本。但是你不要忘记，我们的目标是让程序在成百上千台机器上传播，因此还需要一个脚本将create_lagou.sh拷贝到需要执行的机器上去。

这里，可以对foreach.sh稍做修改，然后分发create_lagou.sh文件。

foreach.sh

#!/usr/bin/bash

readarray -t ips < iplist



for ip in ${ips[@]}

do

    scp ~/remote/create_lagou.sh ramroll@$ip:~/create_lagou.sh

done

这里，我们在循环中用scp进行文件拷贝，然后分别去每台机器上执行create_lagou.sh。

如果你的机器非常多，上述过程会变得非常烦琐。你可以先带着这个问题学习下面的Step 4，然后再返回来重新思考这个问题，当然你也可以远程执行脚本。另外，还有一个叫作sshpass的工具，可以帮你把密码传递给要远程执行的指令，如果你对这块内容感兴趣，可以自己研究下这个工具。

第四步： 打通集群权限

接下来我们需要打通从主服务器到v1和v2的权限。当然也可以每次都用ssh输入用户名密码的方式登录，但这并不是长久之计。 如果我们有成百上千台服务器，输入用户名密码就成为一件繁重的工作。

这时候，你可以考虑利用主服务器的公钥在各个服务器间登录，避免输入密码。接下来我们聊聊具体的操作步骤：

首先，需要在u1上用ssh-keygen生成一个公私钥对，然后把公钥写入需要管理的每一台机器的authorized_keys文件中。如下图所示：我们使用ssh-keygen在主服务器u1中生成公私钥对。

然后使用mkdir -p创建~/.ssh目录，-p的优势是当目录不存在时，才需要创建，且不会报错。~代表当前家目录。 如果文件和目录名前面带有一个.，就代表该文件或目录是一个需要隐藏的文件。平时用ls的时候，并不会查看到该文件，通常这种文件拥有特别的含义，比如~/.ssh目录下是对ssh的配置。

我们用cd切换到.ssh目录，然后执行ssh-keygen。这样会在~/.ssh目录中生成两个文件，id_rsa.pub公钥文件和is_rsa私钥文件。 如下图所示：

可以看到id_rsa.pub文件中是加密的字符串，我们可以把这些字符串拷贝到其他机器对应用户的~/.ssh/authorized_keys文件中，当ssh登录其他机器的时候，就不用重新输入密码了。 这个传播公钥的能力，可以用一个shell脚本执行，这里我用transfer_key.sh实现。

我们修改一下foreach.sh，并写一个transfer_key.sh配合foreach.sh的工作。transfer_key.sh内容如下：

foreach.sh

#!/usr/bin/bash

readarray -t ips < iplist

for ip in ${ips[@]}

do

    sh ./transfer_key.sh $ip

done

tranfer_key.sh

ip=$1

pubkey=$(cat ~/.ssh/id_rsa.pub)

echo "execute on .. $ip"

ssh lagou@$ip " 

mkdir -p ~/.ssh

echo $pubkey  >> ~/.ssh/authorized_keys

chmod 700 ~/.ssh

chmod 600 ~/.ssh/authorized_keys

"

在foreach.sh中我们执行 transfer_key.sh，并且将 IP 地址通过参数传递过去。在 transfer_key.sh 中，用$1读出 IP 地址参数， 再将公钥写入变量pubkey，然后登录到对应的服务器，执行多行指令。用mkdir指令检查.ssh目录，如不存在就创建这个目录。最后我们将公钥追加写入目标机器的~/.ssh/authorized_keys中。

chmod 700和chmod 600是因为某些特定的linux版本需要.ssh的目录为可读写执行，authorized_keys文件的权限为只可读写。而为了保证安全性，组用户、所有用户都不可以访问这个文件。

此前，我们执行foreach.sh需要输入两次密码。完成上述操作后，我们再登录这两台服务器就不需要输入密码了。

接下来，我们尝试一下免密登录，如下图所示：

可以发现，我们登录任何一台机器，都不再需要输入用户名和密码了。

第五步：单机安装 Java 环境

在远程部署 Java 环境之前，我们先单机完成以下 Java 环境的安装，用来收集需要执行的脚本。

在ubuntu上安装java环境可以直接用apt。

我们通过下面几个步骤脚本配置 Java 环境：

sudo apt install openjdk-11-jdk

经过一番等待我们已经安装好了java，然后执行下面的脚本确认java安装。

which java

java --version

根据最小权限原则，执行 Java 程序我们考虑再创建一个用户ujava。

sudo useradd -m -d /opt/ujava ujava

sudo usermod --shell /bin/bash lagou

这个用户可以不设置密码，因为我们不会真的登录到这个用户下去做任何事情。接下来我们为用户配置 Java 环境变量，如下图所示：

通过两次 ls 追查，可以发现java可执行文件软连接到/etc/alternatives/java然后再次软连接到/usr/lib/jvm/java-11-openjdk-amd64下。

这样我们就可以通过下面的语句设置 JAVA_HOME 环境变量了。

export JAVA_HOME=/usr/lib/jvm/java-11-openjdk-amd64/

Linux 的环境变量就好比全局可见的数据，这里我们使用 export 设置JAVA_HOME环境变量的指向。如果你想看所有的环境变量的指向，可以使用env指令。

其中有一个环境变量比较重要，就是PATH。

如上图，我们可以使用shell查看PATH的值，PATH中用:分割，每一个目录都是linux查找执行文件的目录。当用户在命令行输入一个命令，Linux 就会在PATH中寻找对应的执行文件。

当然我们不希望JAVA_HOME配置后重启一次电脑就消失，因此可以把这个环境变量加入ujava用户的profile中。这样只要发生用户登录，就有这个环境变量。

sudo sh -c 'echo "export JAVA_HOME=/usr/lib/jvm/java-11-openjdk-amd64/" >> /opt/ujava/.bash_profile'

将JAVA_HOME加入bash_profile，这样后续远程执行java指令时就可以使用JAVA_HOME环境变量了。

最后，我们将上面所有的指令整理起来，形成一个install_java.sh。

sudo apt -y install openjdk-11-jdk

sudo useradd -m -d /opt/ujava ujava

sudo usermod --shell /bin/bash ujava

sudo sh -c 'echo "export JAVA_HOME=/usr/lib/jvm/java-11-openjdk-amd64/" >> /opt/ujava/.bash_profile'

apt后面增了一个-y是为了让执行过程不弹出确认提示。

第六步：远程安装 Java 环境

终于到了远程安装 Java 环境这一步，我们又需要用到foreach.sh。为了避免每次修改，你可以考虑允许foreach.sh带一个文件参数，指定需要远程执行的脚本。

foreach.sh

#!/usr/bin/bash

readarray -t ips < iplist



script=$1

for ip in ${ips[@]}

do

    ssh $ip 'bash -s' < $script

done

改写后的foreach会读取第一个执行参数作为远程执行的脚本文件。 而bash -s会提示使用标准输入流作为命令的输入；< $script负责将脚本文件内容重定向到远程bash的标准输入流。

然后我们执行foreach.sh install_java.sh，机器等待 1 分钟左右，在执行结束后，可以用下面这个脚本检测两个机器中的安装情况。

check.sh

sudo -u ujava -i /bin/bash -c 'echo $JAVA_HOME'

sudo -u ujava -i java --version

check.sh中我们切换到ujava用户去检查JAVA_HOME环境变量和 Java 版本。执行的结果如下图所示：

总结

这节课我们所讲的场景是自动化运维的一些皮毛。通过这样的场景练习，我们复习了很多之前学过的 Linux 指令。在尝试用脚本文件构建一个又一个小工具的过程中，可以发现复用很重要。

在工作中，优秀的工程师，总是善于积累和复用，而shell脚本就是积累和复用的利器。如果你第一次安装java环境，可以把今天的安装脚本保存在自己的笔记本中，下次再安装就能自动化完成了。除了积累和总结，另一个非常重要的就是你要尝试自己去查资料，包括使用man工具熟悉各种指令的使用方法，用搜索引擎查阅资料等。

课后练习题

最后我再给你出一道需要查阅资料的题目：~/.bashrc ~/.bash_profile, ~/.profile 和 /etc/profile 的区别是什么？

/etc/profile:此文件为系统的每个用户设置环境信息,当用户第一次登录时,该文件被执行.并从/etc/profile.d目录的配置文件中搜集shell的设置.所以如果你有对/etc/profile有修改的话必须得重启你的修改才会生效，此修改对每个用户都生效。可以通过命令source /etc/profile立即生效

/etc/bashrc或 /etc/bash.bashrc:为每一个运行bash shell的用户执行此文件.当bash shell被打开时,该文件被读取.如果你想对所有的使用bash的用户修改某个配置并在以后打开的bash都生效的话可以修改这个文件， 修改这个文件不用重启，重新打开一个bash即可生效。

~/.bash_profile或～/.profile :每个用户都可使用该文件输入专用于当前用户使用的shell信息,当用户登录时,该文件仅仅执行一次!默认情况下,他设置一些环境变量,执行用户的.bashrc文件.

此文件类似于/etc/profile，也是需要需要重启才会生效，/etc/profile对所有用户生效，~/.bash_profile只对当前用户生效。

加餐 | 练习题详解（二）

练习题详解

06 | 目录结构和文件管理指令：rm / -rf 指令的作用是？

【问题】 搜索文件系统中所有以包含 std字符串且以.h扩展名结尾的文件。

【解析】 这道题目比较简单，大家也比较活跃，我自己只写了一种方法，没想到留言中有挺多不错的方案，那我们一起来看下。

下面是我的方案，你学完模块二的内容后，应该知道查看全部文件需要sudo，以管理员身份：

复制代码

sudo find / -name "*std*.h"

我在留言中看到有的同学用的是-iname，这样也是可以的，只是忽略了大小写。

也可以结合 grep 语句， 用管道实现，比如:

复制代码

sudo find / -name "*.h" |grep std

07 | 进程、重定向和管道指令：xargs 指令的作用是？

【问题】 请问下面这段 Shell 程序的作用是什么？

复制代码

mkfifo pipe1
mkfifo pipe2
echo -n run | cat - pipe1 > pipe2 &
cat < pipe2 > pipe1

【解析】 这个题目是我在网上看到的一个比较有趣的问题。

前 2 行代码创建了两个管道文件。

从第 3 行开始，代码变得复杂。echo -n run就是向输出流中写入一个run字符串（不带回车，所以用-n）。通过管道，将这个结果传递给了cat。cat是 concatenate 的缩写，意思是把文件粘在一起。

• 当cat用>重定向输出到一个管道文件时，如果没有其他进程从管道文件中读取内容，cat会阻塞。
• 当cat用<读取一个管道内容时，如果管道中没有输入，也会阻塞。

从这个角度来看，总共有 3 次重定向：

• 将-也就是输入流的内容和pipe1内容合并重定向到pipe2；
• 将pipe2内容重定向到cat；
• 将cat的内容重定向到pipe1。

仔细观察下路径：pipe1->pipe2->pipe1，构成了一个循环。 这样导致管道pipe1管道pipe2中总是有数据（没有数据的时间太短）。于是，就构成了一个无限循环。我们打开执行这个程序后，可以用htop查看当前的 CPU 使用情况，会发现 CPU 占用率很高。

08 | 用户和权限管理指令： 请简述 Linux 权限划分的原则？

【问题】 如果一个目录是只读权限，那么这个目录下面的文件还可写吗？

【解析】 这类问题，你一定要去尝试，观察现象再得到结果。

你可以看到上图中，foo 目录不可读了，下面的foo/bar文件还可以写。 即便它不可写了，下面的foo/bar文件还是可以写。

但是想要创建新文件就会出现报错，因为创建新文件也需要改目录文件。这个例子说明 Linux 中的文件内容并没有存在目录中，目录中却有文件清单。

09 | Linux 中的网络指令：如何查看一个域名有哪些 NS 记录？

【问题】 如何查看正在 TIME_WAIT 状态的连接数量？

【解析】 注意，这里有个小坑，就是 netstat 会有两行表头，这两行可以用 tail 过滤掉，下面tail -n +3就是告诉你 tail 从第 3 行开始显示。-a代表显示所有的 socket。

复制代码

netstat -a | tail -n +3  | wc -l

10 | 软件的安装： 编译安装和包管理器安装有什么优势和劣势？

【问题】 如果你在编译安装 MySQL 时，发现找不到libcrypt.so ，应该如何处理？

【解析】 遇到这类问题，首先应该去查资料。 比如查 StackOverflow，搜索关键词：libcrypt.so not found，或者带上自己的操作系统ubuntu。下图是关于 Stackoverflow 的一个解答：

在这里我再多说两句，程序员成长最需要的是学习时间，如果在这前面加一个形容词，那就是大量的学习时间；而程序员最需要掌握的技能就是搜索和学习知识的能力。如果你看到今天的这篇内容，说明已经学完了《重学操作系统》专栏两个模块的知识，希望你可以坚持下去！

11 | 高级技巧之日志分析：利用 Linux 指令分析 Web 日志

【问题 1 】 根据今天的 access_log 分析出有哪些终端访问了这个网站，并给出分组统计结果。

【解析】access_log中有Debian和Ubuntu等等。我们可以利用下面的指令看到，第 12 列是终端，如下图所示：

我们还可以使用sort和uniq查看有哪些终端，如下图所示：

最后需要写一个脚本，进行统计：

复制代码

cat nginx_logs.txt |\
awk '{tms[$12]++;next}END{for (t in tms) print t, tms[t]}'

结果如下：

【问题 2】 根据今天的 access_log 分析出访问量 Top 前三的网页。

如果不需要 Substring 等复杂的处理，也可以使用sort和uniq的组合。如下图所示：

12 | 高级技巧之集群部署：利用 Linux 指令同时在多台机器部署程序

【问题】~/.bashrc ~/.bash_profile, ~/.profile 和 /etc/profile 的区别是什么？

【解析】 执行一个 shell 的时候分成login shell和non-login shell。顾名思义我们使用了sudo``su切换到某个用户身份执行 shell，也就是login shell。还有 ssh 远程执行指令也是 login shell，也就是伴随登录的意思——login shell 会触发很多文件执行，路径如下：

如果以当前用户身份正常执行一个 shell，比如说./a.sh，就是一个non-login的模式。 这时候不会触发上述的完整逻辑。

另外shell还有另一种分法，就是interactive和non-interactive。interactive 是交互式的意思，当用户打开一个终端命令行工具后，会进入一个输入命令得到结果的交互界面，这个时候，就是interactive shell。

baserc文件通常只在interactive模式下才会执行，这是因为~/.bashrc文件中通常有这样的语句，如下图所示：

这个语句通过$-看到当前shell的执行环境，如下图所示：

带 i 字符的就是interactive，没有带i字符就不是。

因此， 如果你需要通过 ssh 远程 shell 执行一个文件，你就不是在 interactive 模式下，bashrc 不会触发。但是因为登录的原因，login shell 都会触发，也就是说 profile 文件依然会执行。

总结

这个模块我们学习了 Linux 指令。我带大家入了个门，也和你一起感受了一次 Linux 指令的博大精深。Linux 虽然没有上下五千年的历史，但每次使用，依然让我感受到了它浓郁的历史气息，悠久的文化传承，自由的创造精神。希望这块知识可以陪伴大家，鼓励你成为优秀的程序员。虽然我们已经学了几十个指令，但还是沧海一粟。后续就需要你多查资料，多用man手册，继续深造了。

好的，Linux 指令部分就告一段落。下一节课，我们将开启操作系统核心知识学习，请和我一起来学习“模块三：操作系统基础知识”吧。

加餐 | 练习题详解（二）

00:19

重学操作系统

模块三：操作系统基础知识

13 | 操作系统内核：

Linux 内核和 Windows 内核有什么区别？

Windows 和 Linux 是当今两款最主流的服务器操作系统产品，都拥有广泛的用户和信徒。Windows 通过强大的商业运作，驱动了大量优秀人才加盟到它的开发团队中；Linux 通过社区产品的魅力吸引着世界上大量的顶级程序员为它贡献源代码、解答问题。两者在服务器市场上竞争激烈，不分伯仲，但也存在互相扶持的关系。

我觉得，两个操作系统各有千秋。每次学习两个操作系统的技术知识，都让我切实地感受到编程真的是一门艺术，而学习编程就像是在探索艺术。

今天我们继续从一道面试题目“ Linux 内核和 Windows 内核有什么区别？”入手，去了解这两个操作系统内核的设计，帮助你学习操作系统中最核心的一个概念——内核，并希望这些知识可以伴随你日后的每个系统设计。

什么是内核？

说到操作系统，就必须说内核。内核是操作系统中应用连接硬件设备的桥梁。

内核的能力

对于一个现代的操作系统来说，它的内核至少应该提供以下 4 种基本能力：

• 管理进程、线程（决定哪个进程、线程使用 CPU）；
• 管理内存（决定内存用来做什么）；
• 连接硬件设备（为进程、和设备间提供通信能力）；
• 提供系统调用（接收进程发送来的系统调用）。

操作系统分层

从上面 4 种能力来看操作系统和内核之间的关系，通常可以把操作系统分成 3 层，最底层的硬件设备抽象、中间的内核和最上层的应用。

内核是如何工作的？

为了帮助你理解什么是内核，请你先思考一个问题：进程和内核的关系，是不是像浏览器请求服务端服务？你可以先自己思考，然后在留言区写下你此时此刻对这个问题的认知，等学完“模块三”再反过头来回顾这个知识，相信你定会产生新的理解。

接下来，我们先一起分析一下这个问题。

内核权限非常高，它可以管理进程、可以直接访问所有的内存，因此确实需要和进程之间有一定的隔离。这个隔离用类似请求/响应的模型，非常符合常理。

但不同的是在浏览器、服务端模型中，浏览器和服务端是用不同的机器在执行，因此不需要共享一个 CPU。但是在进程调用内核的过程中，这里是存在资源共享的。

• 比如，一个机器有 4 个 CPU，不可能让内核用一个 CPU，其他进程用剩下的 CPU。这样太浪费资源了。
• 再比如，进程向内核请求 100M 的内存，内核把 100M 的数据传回去。 这个模型不可行，因为传输太慢了。

所以，这里多数操作系统的设计都遵循一个原则：进程向内核发起一个请求，然后将 CPU 执行权限让出给内核。内核接手 CPU 执行权限，然后完成请求，再转让出 CPU 执行权限给调用进程。

关于这块知识，我们会在“ 14 |户态和内核态：用户态线程和内核态线程有什么区别？”中详细讨论。

Linux 的设计

Linux 操作系统第一版是1991 年林纳斯托·瓦兹（一个芬兰的小伙子，当时 22 岁）用 C 语音写的。 写完之后他在网络上发布了 Linux 内核的源代码。又经过了 3 年的努力，在 1994 年发布了完整的核心 Version 1.0。

说到 Linux 内核设计，这里有很多有意思的名词。大多数听起来复杂、专业，但是理解起来其实很简单。接下来我们一一讨论。

• Multitask and SMP（Symmetric multiprocessing）

MultiTask 指多任务，Linux 是一个多任务的操作系统。多任务就是多个任务可以同时执行，这里的“同时”并不是要求并发，而是在一段时间内可以执行多个任务。当然 Linux 支持并发。

SMP 指对称多处理。其实是说 Linux 下每个处理器的地位是相等的，内存对多个处理器来说是共享的，每个处理器都可以访问完整的内存和硬件资源。 这个特点决定了在 Linux 上不会存在一个特定的处理器处理用户程序或者内核程序，它们可以被分配到任何一个处理器上执行。

• ELF（Executable and Linkable Format）

这个名词翻译过来叫作可执行文件链接格式。这是一种从 Unix 继承而来的可执行文件的存储格式。我们可以看到 ELF 中把文件分成了一个个分段（Segment），每个段都有自己的作用。如果想要深入了解这块知识，会涉及部分编译原理的知识，如果你感兴趣可以去网上多查些资料或者去留言区我们一起讨论。

• Monolithic Kernel

这个名词翻译过来就是宏内核，宏内核反义词就是 Microkernel ，微内核的意思。Linux 是宏内核架构，这说明 Linux 的内核是一个完整的可执行程序，且内核用最高权限来运行。宏内核的特点就是有很多程序会打包在内核中，比如，文件系统、驱动、内存管理等。当然这并不是说，每次安装驱动都需要重新编译内核，现在 Linux 也可以动态加载内核模块。所以哪些模块在内核层，哪些模块在用户层，这是一种系统层的拆分，并不是很强的物理隔离。

与宏内核对应，接下来说说微内核，内核只保留最基本的能力。比如进程调度、虚拟内存、中断。多数应用，甚至包括驱动程序、文件系统，是在用户空间管理的。

学到这里，你可能会问：在内核层和在用户层有什么区别吗？

感觉分层其实差不多。 我这里说一个很大的区别，比如说驱动程序是需要频繁调用底层能力的，如果在内核中，性能肯定会好很多。对于微内核设计，驱动在内核外，驱动和硬件设备交互就需要频繁做内核态的切换。

当然微内核也有它的好处，比如说微内核体积更小、可移植性更强。不过我认为，随着计算能力、存储技术越来越发达，体积小、安装快已经不能算是一个很大的优势了。现在更重要的是如何有效利用硬件设备的性能。

之所以这么思考，也可能因为我是带着现代的目光回望当时人们对内核的评判，事实上，当时 Linux 团队也因此争论过很长一段时间。 但是我觉得历史往往是螺旋上升的，说不定将来性能发展到了一个新的阶段，像微内核的灵活性、可以提供强大的抽象能力这样的特点，又重新受到人们的重视。

还有一种就是混合类型内核。 混合类型的特点就是架构像微内核，内核中会有一个最小版本的内核，其他功能会在这个能力上搭建。但是实现的时候，是用宏内核的方式实现的，就是内核被做成了一个完整的程序，大部分功能都包含在内核中。就是在宏内核之内有抽象出了一个微内核。

上面我们大体介绍了内核几个重要的特性，有关进程、内存、虚拟化等特性，我们会在后面几个模块中逐步讨论。

Window 设计

接下来我们说说 Windows 的设计，Windows 和 Linux 的设计有很大程度的相似性。Windows也有内核，它的内核是 C/C++ 写的。准确地说，Windows 有两个内核版本。一个是早期的Windows 9x 内核，早期的 Win95, Win98 都是这个内核。我们今天用的 Windows 7, Windows 10 是另一个内核，叫作 Windows NT。NT 指的是 New Technology。接下来我们讨论的都是 NT 版本的内核。

下面我找到一张 Windows 内核架构的图片给你一个直观感受。

Windows 同样支持 Multitask 和 SMP（对称多处理）。Windows 的内核设计属于混合类型。你可以看到内核中有一个 Microkernel 模块。而整个内核实现又像宏内核一样，含有的能力非常多，是一个完整的整体。

Windows 下也有自己的可执行文件格式，这个格式叫作 Portable Executable（PE），也就是可移植执行文件，扩展名通常是.exe、.dll、.sys等。

PE 文件的结构和 ELF 结构有很多相通的地方，我找到了一张图片帮助你更直观地理解。 因为这部分知识涉及编译原理，我这里就不详细介绍了，感兴趣同学可以在留言区和大家一起讨论，或者查阅更多资料。

Windows 还有很多独特的能力，比如 Hyper-V 虚拟化技术，有关虚拟化技术我们将在“模块八：虚拟化和其他”中详细讲解。

总结

这一讲我们学习了内核的基础知识，包括内核的作用、整体架构以及 3 种内核类型（宏内核、微内核和混合类型内核）。内核很小（微内核）方便移植，因为体积小、安装快；内核大（宏内核），方便优化性能，毕竟内核更了解计算机中的资源。我们还学习了操作系统对执行文件的抽象，但是没有很深入讨论，内核部分有很多知识是需要在后面的几个模块中体现的，比如进程、文件、内存相关的能力等。

那么通过这一讲的学习，你现在可以来回答本节关联的面试题目：Linux 内核和 Windows 内核有什么区别？

老规矩，请你先在脑海里构思下给面试官的表述，并把你的思考写在留言区，然后再来看我接下来的分析。

【解析】 Windows 有两个内核，最新的是 NT 内核，目前主流的 Windows 产品都是 NT 内核。NT 内核和 Linux 内核非常相似，没有太大的结构化差异。

从整体设计上来看，Linux 是宏内核，NT 内核属于混合型内核。和微内核不同，宏内核和混合类型内核从实现上来看是一个完整的程序。只不过混合类型内核内部也抽象出了微内核的概念，从内核内部看混合型内核的架构更像微内核。

另外 NT 内核和 Linux 内核还存在着许多其他的差异，比如：

• Linux 内核是一个开源的内核；
• 它们支持的可执行文件格式不同；
• 它们用到的虚拟化技术不同。

关于这块知识就不展开说了， 我们会在后续的“进程、内存、虚拟化”等模块中仔细讨论。

思考题

最后我再给你出一道需要查资料的思考题：Unix 和 Macintosh 内核属于哪种类型？

你可以把你的答案、思路或者课后总结写在留言区，这样可以帮助你产生更多的思考，这也是构建知识体系的一部分。经过长期的积累，相信你会得到意想不到的收获。如果你觉得今天的内容对你有所启发，欢迎分享给身边的朋友。期待看到你的思考！

14 | 用户态和内核态：

用户态线程和内核态线程有什么区别？

这节课给你带来了一道非常经典的面试题目：用户态线程和内核态线程有什么区别？

这是一个组合型的问题，由很多小问题组装而成，比如：

• 用户态和内核态是什么？
• 用户级线程和内核级线程是一个怎样的对应关系？
• 内核响应系统调用是一个怎样的过程？

而且这个问题还关联到了我们后面要学习的多线程、I/O 模型、网络优化等。 所以这是一道很不错的面试题目，它不是简单考某个概念，而是通过让求职者比较两种东西，从而考察你对知识整体的认知和理解。

今天就请你顺着这个问题，深入学习内核的工作机制，和我一起去理解用户态和内核态。

什么是用户态和内核态

Kernel 运行在超级权限模式（Supervisor Mode）下，所以拥有很高的权限。按照权限管理的原则，多数应用程序应该运行在最小权限下。因此，很多操作系统，将内存分成了两个区域：

• 内核空间（Kernal Space），这个空间只有内核程序可以访问；
• 用户空间（User Space），这部分内存专门给应用程序使用。

用户态和内核态

用户空间中的代码被限制了只能使用一个局部的内存空间，我们说这些程序在用户态（User Mode） 执行。内核空间中的代码可以访问所有内存，我们称这些程序在内核态（Kernal Mode） 执行。

系统调用过程

如果用户态程序需要执行系统调用，就需要切换到内核态执行。下面我们来讲讲这个过程的原理。

如上图所示：内核程序执行在内核态（Kernal Mode），用户程序执行在用户态（User Mode）。当发生系统调用时，用户态的程序发起系统调用。因为系统调用中牵扯特权指令，用户态程序权限不足，因此会中断执行，也就是 Trap（Trap 是一种中断）。

发生中断后，当前 CPU 执行的程序会中断，跳转到中断处理程序。内核程序开始执行，也就是开始处理系统调用。内核处理完成后，主动触发 Trap，这样会再次发生中断，切换回用户态工作。关于中断，我们将在“15 课时”进行详细讨论。

线程模型

上面我们学习了用户态和内核态，接下来我们从进程和线程的角度进一步思考本课时开头抛出的问题。

进程和线程

一个应用程序启动后会在内存中创建一个执行副本，这就是进程。Linux 的内核是一个 Monolithic Kernel（宏内核），因此可以看作一个进程。也就是开机的时候，磁盘的内核镜像被导入内存作为一个执行副本，成为内核进程。

进程可以分成用户态进程和内核态进程两类。用户态进程通常是应用程序的副本，内核态进程就是内核本身的进程。如果用户态进程需要申请资源，比如内存，可以通过系统调用向内核申请。

那么用户态进程如果要执行程序，是否也要向内核申请呢？

一个应用程序启动后会在内存中创建一个执行副本，这就是进程。Linux 的内核是一个 Monolithic Kernel（宏内核），因此可以看作一个进程。也就是开机的时候，磁盘的内核镜像被导入内存作为一个执行副本，成为内核进程。

进程可以分成用户态进程和内核态进程两类。用户态进程通常是应用程序的副本，内核态进程就是内核本身的进程。如果用户态进程需要申请资源，比如内存，可以通过系统调用向内核申请。

那么用户态进程如果要执行程序，是否也要向内核申请呢？

程序在现代操作系统中并不是以进程为单位在执行，而是以一种轻量级进程（Light Weighted Process），也称作线程（Thread）的形式执行。

一个进程可以拥有多个线程。进程创建的时候，一般会有一个主线程随着进程创建而创建。

如果进程想要创造更多的线程，就需要思考一件事情，这个线程创建在用户态还是内核态。

你可能会问，难道不是用户态的进程创建用户态的线程，内核态的进程创建内核态的线程吗？

其实不是，进程可以通过 API 创建用户态的线程，也可以通过系统调用创建内核态的线程，接下来我们说说用户态的线程和内核态的线程。

用户态线程

用户态线程也称作用户级线程（User Level Thread）。操作系统内核并不知道它的存在，它完全是在用户空间中创建。

用户级线程有很多优势，比如。

• 管理开销小：创建、销毁不需要系统调用。
• 切换成本低：用户空间程序可以自己维护，不需要走操作系统调度。

但是这种线程也有很多的缺点。

• 与内核协作成本高：比如这种线程完全是用户空间程序在管理，当它进行 I/O 的时候，无法利用到内核的优势，需要频繁进行用户态到内核态的切换。
• 线程间协作成本高：设想两个线程需要通信，通信需要 I/O，I/O 需要系统调用，因此用户态线程需要支付额外的系统调用成本。
• 无法利用多核优势：比如操作系统调度的仍然是这个线程所属的进程，所以无论每次一个进程有多少用户态的线程，都只能并发执行一个线程，因此一个进程的多个线程无法利用多核的优势。
• 操作系统无法针对线程调度进行优化：当一个进程的一个用户态线程阻塞（Block）了，操作系统无法及时发现和处理阻塞问题，它不会更换执行其他线程，从而造成资源浪费。

内核态线程

内核态线程也称作内核级线程（Kernel Level Thread）。这种线程执行在内核态，可以通过系统调用创造一个内核级线程。

内核级线程有很多优势。

• 可以利用多核 CPU 优势：内核拥有较高权限，因此可以在多个 CPU 核心上执行内核线程。
• 操作系统级优化：内核中的线程操作 I/O 不需要进行系统调用；一个内核线程阻塞了，可以立即让另一个执行。

当然内核线程也有一些缺点。

• 创建成本高：创建的时候需要系统调用，也就是切换到内核态。
• 扩展性差：由一个内核程序管理，不可能数量太多。
• 切换成本较高：切换的时候，也同样存在需要内核操作，需要切换内核态。

用户态线程和内核态线程之间的映射关系

线程简单理解，就是要执行一段程序。程序不会自发的执行，需要操作系统进行调度。我们思考这样一个问题，如果有一个用户态的进程，它下面有多个线程。如果这个进程想要执行下面的某一个线程，应该如何做呢？

这时，比较常见的一种方式，就是将需要执行的程序，让一个内核线程去执行。毕竟，内核线程是真正的线程。因为它会分配到 CPU 的执行资源。

如果一个进程所有的线程都要自己调度，相当于在进程的主线程中实现分时算法调度每一个线程，也就是所有线程都用操作系统分配给主线程的时间片段执行。这种做法，相当于操作系统调度进程的主线程；进程的主线程进行二级调度，调度自己内部的线程。

这样操作劣势非常明显，比如无法利用多核优势，每个线程调度分配到的时间较少，而且这种线程在阻塞场景下会直接交出整个进程的执行权限。

由此可见，用户态线程创建成本低，问题明显，不可以利用多核。内核态线程，创建成本高，可以利用多核，切换速度慢。因此通常我们会在内核中预先创建一些线程，并反复利用这些线程。这样，用户态线程和内核态线程之间就构成了下面 4 种可能的关系：

多对一（Many to One）

用户态进程中的多线程复用一个内核态线程。这样，极大地减少了创建内核态线程的成本，但是线程不可以并发。因此，这种模型现在基本上用的很少。我再多说一句，这里你可能会有疑问，比如：用户态线程怎么用内核态线程执行程序？

程序是存储在内存中的指令，用户态线程是可以准备好程序让内核态线程执行的。后面的几种方式也是利用这样的方法。

一对一（One to One）

该模型为每个用户态的线程分配一个单独的内核态线程，在这种情况下，每个用户态都需要通过系统调用创建一个绑定的内核线程，并附加在上面执行。 这种模型允许所有线程并发执行，能够充分利用多核优势，Windows NT 内核采取的就是这种模型。但是因为线程较多，对内核调度的压力会明显增加。

多对多（Many To Many）

这种模式下会为 n 个用户态线程分配 m 个内核态线程。m 通常可以小于 n。一种可行的策略是将 m 设置为核数。这种多对多的关系，减少了内核线程，同时也保证了多核心并发。Linux 目前采用的就是该模型。

两层设计（Two Level）

这种模型混合了多对多和一对一的特点。多数用户态线程和内核线程是 n 对 m 的关系，少量用户线程可以指定成 1 对 1 的关系。

上图所展现的是一个非常经典的设计。

我们这节课讲解的问题、考虑到的情况以及解决方法，将为你今后解决实际工作场景中的问题打下坚实的基础。比如处理并发问题、I/O 性能瓶颈、思考数据库连接池的配置等，要想完美地解决问题，就必须掌握这些模型，了解问题的本质上才能更好地思考问题衍生出来的问题。

总结

这节课我们学习了用户态和内核态，然后我们简单学习了进程和线程的基础知识。这部分知识会在“模块四：进程和线程”中以更细粒度进行详细讲解。等你完成模块四的学习后，可以再返回来看这一节的内容，相信会有更深入的理解。

最后，我们还讨论了用户线程和内核线程的映射关系，这是一种非常经典的设计和思考方式。关于这个场景我们讨论了 1 对 1、1 对多以及多对 1，两层模型 4 种方法。日后你在处理线程池对接；远程 RPC 调用；消息队列时，还会反复用到今天的方法。

那么通过这节课的学习，你现在是否可以来回答本节关联的面试题目？用户态线程和内核态线程的区别？

老规矩，请你先在脑海里构思下给面试官的表述，并把你的思考写在留言区，然后再来看我接下来的分析。

【解析】 用户态线程工作在用户空间，内核态线程工作在内核空间。用户态线程调度完全由进程负责，通常就是由进程的主线程负责。相当于进程主线程的延展，使用的是操作系统分配给进程主线程的时间片段。内核线程由内核维护，由操作系统调度。

用户态线程无法跨核心，一个进程的多个用户态线程不能并发，阻塞一个用户态线程会导致进程的主线程阻塞，直接交出执行权限。这些都是用户态线程的劣势。内核线程可以独立执行，操作系统会分配时间片段。因此内核态线程更完整，也称作轻量级进程。内核态线程创建成本高，切换成本高，创建太多还会给调度算法增加压力，因此不会太多。

实际操作中，往往结合两者优势，将用户态线程附着在内核态线程中执行。

思考题

最后我再给你出一道需要查资料的思考题：JVM的线程是用户态线程还是内核态线程？

你可以把你的答案、思路或者课后总结写在留言区，这样可以帮助你产生更多的思考，这也是构建知识体系的一部分。经过长期的积累，相信你会得到意想不到的收获。如果你觉得今天的内容对你有所启发，欢迎分享给身边的朋友。期待看到你的思考！

15 | 中断和中断向量：

Java/js 等语言为什么可以捕获到键盘输入？

本课时我们依然以一道面试题为引开启今天的学习。请你思考：Java/JS 等语言为什么可以捕获到键盘的输入？

其实面试是一个寻找同类的过程，在阿里叫作“闻味道”——用键盘输入是程序员每天必做的事情，如果你对每天发生的事情背后的技术原理保持好奇心和兴趣，并且愿意花时间去探索和学习，这就是技术潜力强的表现。相反，如果你只对马上能为自己创造价值的事情感兴趣，不愿意通过探索和思考的方式，去理解普遍存在的世界，长此以往就会导致知识储备不足。

我想通过本课时讲解一种特别的学习技巧，可以说是“填鸭式学习”的反义词，叫作“探索式学习”。我看网上也叫作“破案式学习”，学习过程像攻破一个谜题，或者分析一个案件，并不是从结论开始，然后一层层学习理论；而是通过找到一个目标，一层层挖掘需要的知识、理论，一点点去思考解决方案，最终达到提升解决问题能力的目的。

接下来，请你和我一起化身成一名计算机科学家，假设明天就要生产机器了，但是为 Java/JS 等语言提供键盘输入支持模块的操作系统今天还没有完成，现在还有一节课的时间，那么我们应该如何去做呢？

探索过程：如何设计响应键盘的整个链路？

当你拿到一个问题时，需要冷静下来思考和探索解决方案。你可以查资料、看视频或者咨询专家，但是在这之前，你先要进行一定的思考和梳理，有的问题可以直接找到答案，有的问题却需要继续深挖寻找其背后的理论支撑。

问题 1：我们的目标是什么?

我们的目标是在 Java/JS 中实现按键响应程序。这种实现有点像 Switch-Case 语句——根据不同的按键执行不同的程序，比如按下回车键可以换行，按下左右键可以移动光标。

问题 2：按键怎么抽象？

键盘上一般不超过 100 个键。因此我们可以考虑用一个 Byte 的数据来描述用户按下了什么键。按键有两个操作，一个是按下、一个是释放，这是两个不同的操作。对于一个 8 位的字节，可以考虑用最高位的 1 来描述按下还是释放的状态，然后后面的 7 位（0~127）描述具体按了哪个键。这样我们只要确定了用户按键/释放的顺序，对我们的系统来说，就不会有歧义。

问题 3：如何处理按键？使用操作系统处理还是让每个程序自己实现？

处理按键是一个通用程序，可以考虑由操作系统先进行一部分处理，比如：

• 用户按下了回车键，先由操作系统进行统一的封装，再把按键的编码转换为字符串Enter方便各种程序使用。

• 处理组合键这种操作，由操作系统先一步进行计算比较好。因为底层只知道按键、释放，组合键必须结合时间因素判断。

你可以把下面这种情况看作是一个Ctrl + C组合键，这种行为可以由操作系统进行统一处理，如下所示：

按下 Ctrl

按下 C

释放 Ctrl

释放 C

问题 4：程序用什么模型响应按键？

当一个 Java 或者 JS 写的应用程序想要响应按键时，应该考虑消息模型。因为如果程序不停地扫描按键，会给整个系统带来很大的负担。比如程序写一个while循环去扫描有没有按键，开销会很大。 如果程序在操作系统端注册一个响应按键的函数，每次只有真的触发按键时才执行这个函数，这样就能减少开销了。

问题 5：处理用户按键，需不需要打断正在执行的程序？

从用户体验上讲，按键应该是一个高优先级的操作，比如用户按 Ctrl+C 或者 Esc 的时候，可能是因为用户想要打断当前执行的程序。即便是用户只想要输入，也应该尽可能地集中资源给到用户，因为我们不希望用户感觉到延迟。

如果需要考虑到程序随时会被中断，去响应其他更高优先级的情况，那么从程序执行的底层就应该支持这个行为，而且最好从硬件层面去支持，这样速度最快。 这就引出了本课时的主角——中断。具体如何处理，见下面我们关于中断部分的分析。

问题 6：操作系统如何知道用户按了哪个键？

这里有一个和问题 5 类似的问题。操作系统是不断主动触发读取键盘按键，还是每次键盘按键到来的时候都触发一段属于操作系统的程序呢？

显然，后者更节省效率。

那么谁能随时随地中断操作系统的程序？ 谁有这个权限？是管理员账号吗？ 当然不是，拥有这么高权限的应该是机器本身。

我们思考下这个模型，用户每次按键，触发一个 CPU 的能力，这个能力会中断正在执行的程序，去处理按键。那 CPU 内部是不是应该有处理按键的程序呢？这肯定不行，因为我们希望 CPU 就是用来做计算的，如果 CPU 内部有自带的程序，会把问题复杂化。这在软件设计中，叫作耦合。CPU 的工作就是专注高效的执行指令。

因此，每次按键，必须有一个机制通知 CPU。我们可以考虑用总线去通知 CPU，也就是主板在通知 CPU。

那么 CPU 接收到通知后，如何通知操作系统呢？CPU 只能中断正在执行的程序，然后切换到另一个需要执行的程序。说白了就是改变 PC 指针，CPU 只有这一种办法切换执行的程序。这里请你思考，是不是只有这一种方法：CPU 中断当前执行的程序，然后去执行另一个程序，才能改变 PC 指针？

接下来我们进一步思考，CPU 怎么知道 PC 指针应该设置为多少呢？是不是 CPU 知道操作系统响应按键的程序位置呢？

答案当然是不知道。

因此，我们只能控制 CPU 跳转到一个固定的位置。比如说 CPU 一收到主板的信息（某个按键被触发），CPU 就马上中断当前执行的程序，将 PC 指针设置为 0。也就是 PC 指针下一步会从内存地址 0 中读取下一条指令。当然这只是我们的一个思路，具体还需要进一步考虑。而操作系统要做的就是在这之前往内存地址 0 中写一条指令，比如说让 PC 指针跳转到自己处理按键程序的位置。

讲到这里，我们总结一下，CPU 要做的就是一看到中断，就改变 PC 指针（相当于中断正在执行的程序），而 PC 改变成多少，可以根据不同的类型来判断，比如按键就到 0。操作系统就要向这些具体的位置写入指令，当中断发生时，接管程序的控制权，也就是让 PC 指针指向操作系统处理按键的程序。

上面这个模型和实际情况还有出入，但是我们已经开始逐渐完善了。

问题 7：主板如何知道键盘被按下?

经过一层一层地深挖“如何设计响应键盘的整个链路？”这个问题，目前操作系统已经能接管按键，接下来，我们还需要思考主板如何知道有按键，并且通知 CPU。

你可以把键盘按键看作按下了某个开关，我们需要一个芯片将按键信息转换成具体按键的值。比如用户按下 A 键，A 键在第几行、第几列，可以看作一个电学信号。接着我们需要芯片把这个电学信号转化为具体的一个数字（一个 Byte）。转化完成后，主板就可以接收到这个数字（按键码），然后将数字写入自己的一个寄存器中，并通知 CPU。

为了方便 CPU 计算，CPU 接收到主板通知后，按键码会被存到一个寄存器里，这样方便处理按键的程序执行。

通过对以上 7 个问题的思考和分析，我们已经有了一个粗浅的设计，接下来就要开始整理思路了。

思路的整理：中断的设计

整体设计分成了 3 层，第一层是硬件设计、第二层是操作系统设计、第三层是程序语言的设计。

按键码的收集，是键盘芯片和主板的能力。主板知道有新的按键后，通知 CPU，CPU 要中断当前执行的程序，将 PC 指针跳转到一个固定的位置，我们称为一次中断（interrupt）。

考虑到系统中会出现各种各样的事件，我们需要根据中断类型来判断PC 指针跳转的位置，中断类型不同，PC 指针跳转的位置也可能会不同。比如按键程序、打印机就绪程序、系统异常等都需要中断，包括在“14 课时”我们学习的系统调用，也需要中断正在执行的程序，切换到内核态执行内核程序。

因此我们需要把不同的中断类型进行分类，这个类型叫作中断识别码。比如按键，我们可以考虑用编号 16，数字 16 就是按键中断类型的识别码。不同类型的中断发生时，CPU 需要知道 PC 指针该跳转到哪个地址，这个地址，称为中断向量（Interupt Vector）。

你可以考虑这样的实现：当编号 16 的中断发生时，32 位机器的 PC 指针直接跳转到内存地址 16*4 的内存位置。如果设计最多有 255 个中断，编号就是从 0~255，刚好需要 1K 的内存地址存储中断向量——这个 1K 的空间，称为中断向量表。

因此 CPU 接收到中断后，CPU 根据中断类型操作 PC 指针，找到中断向量。操作系统必须在这之前，修改中断向量，插入一条指令。比如操作系统在这里写一条Jump指令，将 PC 指针再次跳转到自己处理对应中断类型的程序。

操作系统接管之后，以按键程序为例，操作系统会进行一些处理，包括下面的几件事情：

1. 将按键放入一个队列，保存下来。这是因为，操作系统不能保证及时处理所有的按键，比如当按键过快时，需要先存储下来，再分时慢慢处理。
2. 计算组合键。可以利用按下、释放之间的时间关系。
3. 经过一定计算将按键抽象成消息（事件结构或对象）。
4. 提供 API 给应用程序，让应用程序可以监听操作系统处理后的消息。
5. 分发按键消息给监听按键的程序。

所以程序在语言层面，比如像 Java/Node.js 这种拥有虚拟机的语言，只需要对接操作系统 API 就可以了。

中断的类型

接下来我们一起讨论下中断的分类方法：

• 按照中断的触发方分成同步中断和异步中断；
• 根据中断是否强制触发分成可屏蔽中断和不可屏蔽中断。

中断可以由 CPU 指令直接触发，这种主动触发的中断，叫作同步中断。同步中断有几种情况。

• 之前我们学习的系统调用，需要从用户态切换内核态，这种情况需要程序触发一个中断，叫作陷阱（Trap），中断触发后需要继续执行系统调用。
• 还有一种同步中断情况是错误（Fault），通常是因为检测到某种错误，需要触发一个中断，中断响应结束后，会重新执行触发错误的地方，比如后面我们要学习的缺页中断。
• 最后还有一种情况是程序的异常，这种情况和 Trap 类似，用于实现程序抛出的异常。

另一部分中断不是由 CPU 直接触发，是因为需要响应外部的通知，比如响应键盘、鼠标等设备而触发的中断。这种中断我们称为异步中断。

CPU 通常都支持设置一个中断屏蔽位（一个寄存器），设置为 1 之后 CPU 暂时就不再响应中断。对于键盘鼠标输入，比如陷阱、错误、异常等情况，会被临时屏蔽。但是对于一些特别重要的中断，比如 CPU 故障导致的掉电中断，还是会正常触发。可以被屏蔽的中断我们称为可屏蔽中断，多数中断都是可屏蔽中断。

所以这里我们讲了两种分类方法，一种是同步中断和异步中断。另一种是可屏蔽中断和不可屏蔽中断。

总结

这节课我们通过探索式学习讨论了中断的设计。 通过一个问题，Java/JS 如何响应键盘按键，引出了 7 个问题的思考。通过探索这些问题，我们最终找到 了答案，完成了一次从硬件、内核到应用的完整设计。我想说的是，学习不是最终目的，长远来看我更希望你在学习的过程中得到成长，通过学习技能锻炼自己解决问题的能力。

那么通过这节课的学习，你现在可以来回答本节关联的面试题目：Java/Js 等语言为什么可以捕获到键盘输入？

老规矩，请你先在脑海里构思下给面试官的表述，并把你的思考写在留言区，然后再来看我接下来的分析。

【解析】 为了捕获到键盘输入，硬件层面需要把按键抽象成中断，中断 CPU 执行。CPU 根据中断类型找到对应的中断向量。操作系统预置了中断向量，因此发生中断后操作系统接管了程序。操作系统实现了基本解析按键的算法，将按键抽象成键盘事件，并且提供了队列存储多个按键，还提供了监听按键的 API。因此应用程序，比如 Java/Node.js 虚拟机，就可以通过调用操作系统的 API 使用键盘事件。

思考题

最后我再给你出一道需要查资料的思考题：操作系统可以处理键盘按键可以理解，那么我们开机的时候也可以使用键盘，但是那时候操作系统还没有载入内存，这个怎么解释？

你可以把你的答案、思路或者课后总结写在留言区，这样可以帮助你产生更多的思考，这也是构建知识体系的一部分。经过长期的积累，相信你会得到意想不到的收获。如果你觉得今天的内容对你有所启发，欢迎分享给身边的朋友。期待看到你的思考！

16 | Win/Mac/Unix/Linux 的区别和联系：

为什么 Debian 漏洞排名第一还这么多人用？

在我的印象中 Windows 才是最容易被攻击的操作系统，没想到 2020 年美国 NIST 的报告中， Debian 竟然是过去 20 年中漏洞最多的操作系统。Debain 以 3067 个漏洞稳居第一，第二名是 Android，第三名是 Linux Kernel。那么为什么 Debian 漏洞数会排在第一位呢？

NIST的数据报告：软件漏洞排名

今天我们就以这个问题为引，带你了解更多的操作系统。这就要追溯到 20 世纪操作系统蓬勃发展的年代。那是一个惊艳绝伦的时代，一个个天才黑客，一场场激烈的商战，一次次震撼的产品发布会——每个人都想改变世界，都在积极的抓住时机，把握时代赋予的机会。我们今天的工程师文化——一种最纯粹的、崇尚知识，崇尚创造的文化，也是传承于此。

本课时作为内核部分的最后一课，我会带你了解一些操作系统的历史，希望通过这种方式，把这种文化传承下去，让你更有信心去挑战未来的变化。当然，你也可以把本课时当作一个选学的内容，不会影响你继续学习我后面的课程。

IBM

话不多说，我们正式开始。1880 年美国进行了一次人口普查，涉及5000 多万人。因为缺少技术手段，总共用了 7 年半时间才完成。后来霍尔列斯发明了一种穿孔制表机，大大改善了这种情况，而后他还给这种机器申请了专利。

1896 年，霍尔列斯成立了 CRT 公司，也就是 IBM 的前身。后来霍尔列斯经营不善，遇到困难，中间有金融家，军火商都参与过 CRT 的经营，却没能使得情况好转。

直到 1914 年托马斯·约翰·沃森（老沃森）加盟CRT，帮助霍尔列斯管理 CRT，情况才逐渐好转。老沃森是一个销售出身，很懂得建立销售团队的文化，所以才能逐渐把 CRT 的业务做起来，成为 CRT 的实际掌控者。在 1924 年 CRT 正式更名为 IBM，开启了沃森的时代。

IBM（International Business Machines Corporation）一开始是卖机器的。后来沃森的儿子，也就是小沃森后来逐渐接管了 IBM。小沃森对蓬勃发展的计算机产业非常感兴趣，同时也很看好计算机市场。但也正因如此，沃森父子间发生了一场冲突。老沃森的著名论断也是出自这场冲突：世界上对计算机有需求的人不会超过 5 个。于是我们都成了这幸运的 5 个人之一。

所以 IBM 真正开始做计算机是 1949 年小沃森逐渐掌权后。1954 年，IBM 推出了世界上第一个拥有操作系统的商用计算机——IBM 704，并且在 1956 年时独占了计算机市场的 70% 的份额。

你可能会问，之前的计算机没有操作系统吗？

我以第一台可编程通用计算机 ENIAC 为例，ENIAC 虽然支持循环、分支判断语句，但是只支持写机器语言。ENIAC 的程序通常需要先写在纸上，然后再由专业的工程师输入到计算机中。 对于 ENIAC 来说执行的是一个个作业，就是每次把输入的程序执行完。

上图中的画面正是一位程序员通过操作面板在写程序。 那个时候写程序就是接线和使用操作面板开关，和今天我们所说的“写程序”还是有很大区别的。

所以在 IBM 704 之前，除了实验室产品外，正式投入使用的计算机都是没有操作系统的。但当时 IBM 704 的操作系统是美国通用移动公司帮助研发的 GM-NAA I/O 系统，而非 IBM 自研。IBM 一直没有重视操作系统的研发能力，这也为后来 IBM 使用微软的操作系统，以及进军个人 电脑 市场的失败埋下了伏笔。

大型机操作系统

1975 年前，还没有个人电脑，主要是银行、政府、保险公司这些企业在购买计算机。因为比较强调数据吞吐量，也就是单位时间能够处理的业务数量，因此计算机也被称作大型机。

早期的大型机厂商往往会为每个大型机写一个操作系统。后来 1964 年 IBM 自研了 OS/360 操作系统，在这个操作系统之上 IBM 推出了 System/360 大型机，然后在 1965~1978 年间，IBM 以 System/360 的代号陆陆续续推出了多款机器。开发 System/360 大型机的过程也被称为 IBM 的一次世纪豪赌，雇用了 6W 员工，新建了 5 个工厂。这么大力度的投资背后是小沃森的支持，几乎是把 IBM 的家底掏空转型去做计算机了。 IBM 这家公司喜欢押注，而且一次比一次大——2019 年 IBM 以 340 亿美金收购红帽，可能是 IBM 想在云计算和操作系统市场发力。

IBM 投入了大量人力物力在 System/360 上，也推进了 OS/360 的开发。当时 IBM 还自研了磁盘技术，IBM 自己叫作 DASD（Direct access storage devices）。

从上图中你可以看到，IBM 自研的磁盘，非常类似今天硬盘的结构的。当时支持磁盘的操作系统往往叫作 DOS（Disk Operating System）。还有一些是支持磁带的操作系统，叫作 TOS（Tape Operating System）。所以 OS/360 早期叫作 BOS/360，就是 Basic Operating System，后来分成了 DOS/360 和 TOS/360。现在我们不再根据硬件的不同来区分系统了，而是通过驱动程序驱动硬件工作，对硬件的支持更像是插件一样。

为了支持大型机的工作，IBM 在1957 年还推出了 Fortran（Formula Translation）语言。这是一门非常适合数值计算的语言，目的是更好地支持业务逻辑处理。计算机、语言、操作系统，这应该是早期计算机的三要素。把这三个环节做好，就能占领市场。

那个时代的操作系统是作业式的，相当于处理一个个任务，核心是一个任务的调度器。它会先一个任务处理，完成后再处理另一个任务，当时 IBM 还没有想过要开发分时操作系统，也就是多个任务轮流调度的模型。直到 Unix 系统的前身 Multics 出现，IBM 为了应对时代变化推出了 TSS/360（T 代表 Time Sharing）。

和大型机相比，还有一个名词是超级计算机。超级计算机是指拥有其他计算机无法比拟的计算性能的计算机，目前超算每秒可以达到万亿次计算。通常处理业务，不需要超算。超算的作用还是处理科学问题。比如淘宝某次双 11 当天的订单数量是 10 亿量级，单从计算量上说，这并不是很大。如果单纯计算订单状态，恐怕一台手机足矣。但是双 11 期间最恐怖的是 I/O，加上解决大量事务带来的压力，还要同时保证一致性、可用性、分区容错性带来的系统性工作量。

如果企业没有能力像阿里巴巴一样建立一个分布式集群，同时雇佣大量顶级程序员，就可以直接购买大型机，这样做是相对比较划算的。大型机的主要目标就是为了集中式处理 I/O 和作业提供响应巨大的吞吐量的能力。目前还没有几个企业拥有阿里巴巴处理交易的能力。因此 IBM 的大型机一直拥有非常大的市场。

比如 IBM 的 z15 大型机，每天可以处理 1 万亿笔订单，内部可以部署 240 万个 Linux 容器。今天的银行交易、航班处理、政府的税务基本都还是大型机在管理。大型机价格也是相对较贵的，一台机器算上硬件、软件和维护费用，一年间花费上亿也是很正常的事情。

Unix

IBM 是一家商业驱动的公司，至今已经 100 多年历史。因为 IBM 喜欢用蓝色，大家经常戏称它是 Big Blue（蓝巨人）。IBM 的巨头们有魄力押注，看准了计算机时代的来临，雇用了 60000 员工，开了 5 个工厂，几乎把全部积累的财富都投入到了大型机市场，让 IBM 有了 90% 的大型机市场。商业驱动公司的弱点，就是对驱动技术发展缺少真正的热爱，更多还是商业利益的追逐。

1964 年贝尔实验室、MIT 和通用电子公司合作开发了 Multics 操作系统，用在了 GE 645 大型机上。GE 开头就是 Generic Electric，通用电气公司，这家公司当时也有想过生产大型机。当时总共有 8 家公司生产大型机，因为做不过 IBM，被戏称为白雪公主和 7 个小矮人。Multics 提出了不少新的概念，比如：

• 分时（Time Sharing）；
• “08 课时”学习过的环形保护模型；
• 区分不同级别的权限；

后来 IBM 逐渐对 Multics 引起了重视， 推出 TSS/360 系统，这只是做出防御性部署的一个举措。但是同在贝尔实验室 Multics 项目组的丹尼斯·里奇（C 语言的作者）和肯·汤普逊却看到了希望。他们都是 30 岁不到，正是意气风发的时候。两个人对程序设计、操作系统都有着浓厚的兴趣，特别是肯·汤普逊，之前已经做过大量的操作系统开发，还写过游戏，他们都觉得 Multics 设计太过于复杂了。再加上 Multics 没取得商业成功，贝尔实验室叫停了这个项目后，两个人就开始合作写 Unix。Unix 这个名字一方面参考 Multics，另一方面参考了 Uniplexed，它是 Multiplexed 的反义词，含义有点像统一和简化。

Unix 早期开放了源代码，可以说是现代操作系统的奠基之作——支持多任务、多用户，还支持分级安全策略。拥有内核、内存管理、文件系统、正则表达式、开发工具、可执行文件格式、命令行工具等等。可以说，到今天 Unix 不再代表某种操作系统，而是一套统一的，大家都认可的架构标准。

因为开源的原因，Unix 的版本非常复杂。具体你可以看下面这张大图。

绿色的是开源版本，黄色的是混合版本，红色的是闭源版本。这里面有大型机使用的版本，有给工作站使用的版本，也有个人电脑版本。比如 Mac OS、SunOS、Solaris 都有用于个人电脑和工作站；HP-UX 还用作过大型机操作系统。另外，Linux 系统虽然不是 Unix，但是参考了 Unix 的设计，并且遵照 Unix 的规范，它从 Unix 中继承过去不少好用的工具，这种我们称为 Unix-like 操作系统。

个人电脑革命

从大型机兴起后，就陆续有人开始做个人电脑。但是第一台真正火了的个人电脑，是 1975 年 MITS 公司推出的 Altair 8800。

里面有套餐可选，套餐价是 $439。MITS 的创始人 ED Roberts，和投资人承诺可以卖出去 800 台，没想到第一个月就卖出了 1000 台。对于一台没有显示器、没有键盘，硬件是组装的也不是自有品牌的电脑，它的购买者更多的是个人电脑爱好者们。用户可以通过上面的开关进行编程，然后执行简单的程序，通过观察信号灯看到输出。所以，市场对个人电脑的需求，是普遍存在的，哪怕是好奇心，大家也愿意为之买单。比尔·盖茨也买了这台机器，我们后面再说。

Altair 8800 出品半年后，做个人电脑的公司就如雨后春笋一样出现了。IBM 当然也嗅到了商机。

1976 年 21 岁的乔布斯在一次聚会中说服了 26 岁的沃兹尼亚克一起设计 Apple I 电脑。 沃兹尼亚克大二的时候，做过一台组装电脑，在这次聚会上，他的梦想被乔布斯点燃了，当晚就做了 Apple I 的设计图。1976 年 6 月份，Apple I 电脑就生产出了 200 台，最终卖出去 20 多台。 当时 Apple I 只提供一块板，不提供键盘、显示器等设备。这样的电脑竟然有销量，在今天仍然是不可想象的。

Apple I 在商业上的发展不太成功，但是 1977 年，乔布斯又说服了投资人，投资生产 Apple II。结果当年就让乔布斯身价上百万，两年后就让他身价过亿。

你可以看到 Apple II 就已经是一个完整的机器了。一开始 Apple II 是苹果自研的操作系统，并带有沃兹尼亚克写的简单的 BASIC 语言解释器。1978 年 Apple 公司花了 13000 美金采购了一家小公司的操作系统，这家小公司负责给苹果开发系统，也就是后来的 Apple DOS 操作系统。这家公司还为 Apple DOS 增加了文件浏览器。

1980s 初， 蓝巨人 IBM 感受到了来自 Apple 的压力。如果个人市场完全被抢占，这对于一家专做商业系统的巨头影响会非常大。因此 IBM 成立了一个特别行动小组，代号 Project Chess，目标就是一年要做出一台能够上市的 PC。但是这次 IBM 没有豪赌，只是组织了一个 150 人的团队。因此，他们决定从硬件到软件都使用其他厂商的，当时的说法叫作开放平台。

IBM 没有个人电脑上可用的操作系统，因此找到了当时一家做操作系统和个人电脑的厂商，Digital Research 公司。Digital Research 的 CP/M 操作系统已经受到了市场的认可，但是这家公司的创始人竟然拒绝了蓝巨人的提议，态度也不是很友好。这导致 Digital Research 直接错过了登顶的机会。蓝巨人无奈之下，就找到了只有 22 岁的比尔·盖茨。

盖茨 22 岁的时候和好朋友艾伦创了微软公司。他其实也购买了 Altair 8800（就是本课时前面我们提到的第一台卖火的机器），但是他们目的是和 Altair 的制造商 MITS 公司搞好关系。最终盖茨成功说服了 MITS 公司雇佣艾伦，在 Altair 中提供 BASIC 解释器。BASIC 这门语言 1964 年就存在了，但是盖茨和艾伦是第一个把它迁移到 PC 领域的。IBM 看上了盖茨的团队，加上 Digital Research 拒绝了自己，有点生气，就找到了盖茨。

盖茨非常重视这次机会。但是这里有个问题，微软当时手上是没有操作系统的，他们连夜搞定了一个方案，就是去购买另一家公司的 86-DOS 操作系统，然后承诺 IBM 自己团队负责修改和维护。微软花了 50000 美金买了 86-DOS 的使用权，允许修改和再发布。然后微软再将 86-DOS 授权给 IBM。这里面有非常多有趣的故事，如果你感兴趣可以去查资料了解更多的内容。

最后，Project Chess 小组在 1 年内，成功完成了使命，做出了 IBM 个人电脑，看上去非常像 APPLE II。名字就叫 Personal Computer， 就是我们今天说的 PC。86-DOS 也改成了 PC DOS，IBM 的加入又给 PC 市场带了一波节奏，让更多的人了解到了个人电脑。

微软也跟着水涨船高，每销售 1 台 PC，微软虽然拿不到利润，但保留了 PC DOS 的版权。而且拿到 IBM 的合同，为 IBM 开发核心系统，这也使得微软的地位大涨。盖茨相信马上就会有其他厂商开始和 IBM 竞争，会需要 PC DOS，而微软只需要专心做好操作系统就足够了。

其实没有用多久， 1982 年康柏公司花了几个月时间，雇用了 100 多个工程师，逆向工程了 IBM PC，然后就推出了兼容 IBM PC 的电脑，价格稍微便宜一点。然后整个产业沸腾了，各种各样的商家都进来逆向 IBM PC。整个产业陷入了价格战，每过半年人们可以花更少的钱，拿到配置更高的机器。这个时候微软就在背后卖操作系统，也就是 PC DOS 的保真版，MS-DOS。直到 10 年后，微软正式和 IBM 决裂。

微软第一个视窗操作系统是 1985 年，然后又被 IBM 要求开发它的竞品 OS/2。需要同时推进两个系统，所以微软不是很开心，但是又不能得罪蓝巨人。IBM 也不是很舒服，但是又不得不依赖微软。这个情况一直持续到 1995 年左右，Windows 95 发布的时候，微软还使用 MS-DOS 作为操作系统核心，到了 2001 年 Windows XP 发布的时候，就切换到了 Windows NT 内核。就这样，微软成功发展壮大，并逃离蓝巨人的掌控，成为世界上最大的操作系统公司。

Linux

微软的崛起伴随着个人电脑的崛起。但是推动操作系统技术发展，还有另一条线，就是以开源力量为主导的 Unix 线。Unix 出现后，随着一些商业公司逐渐加入，部分公司开始不愿意再公开源代码，而是公开销售修改过的 Unix，这引起了很多黑客的不满。其中比较著名的有理查德·斯托曼和林纳斯。

大黑客理查德·斯托曼有一次觉得打印机有一部分功能不方便，想要修改，却被施乐公司拒绝提供打印机驱动的源代码，导致了一些茅盾。再加上自己工作的 AI 实验室的成员被商业公司挖走了，他认为商业阻碍了技术进步。于是开始到处呼吁软件应该是自由的、开源的，人们应该拿到源代码进行修改和再发布。

1985 年理查德·斯托曼发布了 GNU 项目，本身 GNU 是一个左递归，就是 GNU = GNU's not Unix。GNU 整体来说还是基于 Unix 生态，但在斯托曼的领导下开发了大量的优质工具，比如 gcc 和 emacs 等。但是斯托曼一直为 GNU 没有自己的操作系统而苦恼。

结果 1991 年 GNU 项目迎来了转机，年仅 21 岁的林纳斯·托瓦兹在网络上发布了一个开源的操作系统，就是 Linux。林纳斯的经历和斯托曼有点类似，所以林纳斯会议听斯托曼讲座，让他有种热血沸腾的感觉。林纳斯不满意 MS-DOS 不开源，但是作为学生党，刚刚学完了 Andy 的《操作系统：设计与实现》，本来一开始没有想过要写 Linux。最后是因为 Unix 的商用版本太贵了买不起，才开始写 Linux。

斯托曼也觉得 GNU 不能没有操作系统，就统称为 GNU/Linux，并且利用自己的影响力帮助林纳斯推广 Linux。这样就慢慢吸引了世界上一批顶级的黑客，一起来写 Linux。后来 Linux 慢慢成长壮大，成为一块主流的服务器操作系统。当然 Linux 后来也衍生了大量的版本，下图是不同版本的 Linux 的分布。

数据取自 W3Techs.com 2020

Ubuntu 源自 Debian，有着非常漂亮的桌面体验，我就是使用 Ubuntu 开发程序。 Ubuntu 后面有商业公司 Canonical 的支持，也有社区的支持。Centos 源自 Red Hat 公司的企业版 Linux（RHEL），商用版本的各种硬件、软件支持通常会好一些，因此目前国内互联网企业的运维都偏向使用 CentosOS。第三名的 Debian 是 Ubuntu 的源头，是一个完全由自由软件精神驱动的社区产品，提供了大量的自由软件。当然也有人批评 Debian 太过于松散，发行周期太长，漏洞修复周期长等等。

Android

乔布斯的苹果电脑最终没有卖过微软的操作系统。但是苹果手机就独占了世界上 2/3 的手机利润。苹果手机取得成功后，各大厂商都开始做智能手机。然后 Google 收购了 Android 公司，复刻了微软成功道路。Android 是基于 Linux 改造的。Android 之所以能成功有这么几个原因：

• Android 是免费的，因此手机厂商不需要为使用 Android 支付额外的费用，而 Google 可以利用 Google 的移动服务变现，据统计 Google Play 应用商店 + Google 搜索服务 + Google 地图三项一年的营收就可以到 188 亿美金；
• Android 是开源生态，各大厂商可以基于 Android 修改；
• Android 系统基于 Linux 稳定性很好，崩溃率很低；
• 最后就是应用生态，用 Android 技术开发 App 可以在各大手机品牌通用。

个人认为还有一个重要原因是比尔·盖茨把微软做大之后，就不再参与微软事物了，醉心于改变人类的事业，所以智能手机、操作系统才有苹果和 Google 的机会。

总结

本课时我主要给你介绍了操作系统的历史。

• IBM 靠一次豪赌，抓住了大型机的市场，至今仍在盈利。
• 苹果靠个人电脑起家，通过智能手机成为商业巨头。
• 微软靠 IBM 的扶持起家，在个人电脑兴起的浪潮中抓住了机会，成为最大的 PC 操作系统厂商。
• 最后 Google 开源 Android，成为移动端操作系统的王者。

在这几十年的浪潮中，商业竞争风起云涌，但是学术界和黑客们也创造了以自由软件运动为核心的社区文化，操作系统经历了百家争鸣的时代和残酷的淘汰，大浪淘沙，剩下了 Windows 和 Unix 系。Unix 系操作系统包括 Unix、 Linux、Mac OS 和 Android。

那么通过这节课的学习，你现在可以尝试来回答本节关联的面试题目：为什么 Debian 漏洞排名第一还这么多人用？

【解析】 首先你要明白漏洞是无可避免的。这是因为软件设计是一个不可计算的问题。因为无法计算，发现漏洞往往需要反复使用软件，或者利用工具扫描看到现象，或者阅读源代码才能找到代码问题……

那么什么软件漏洞多呢？

假设开发人员的水平差不多，那么开源软件漏洞一定更多。开放源代码后，可以接触到的源码群体庞大，作为技术资料分析的场景也更庞大，大量开发者讨论和分析设计，技术交流频繁，漏洞往往发现更快。这样你就可以理解为什么 Debian/Android 和 Linux Kernel 位居漏洞排名前三了。

在 Linux 发行版中，Ubuntu 和 Debian 共享着大量代码，Ubuntu+Debian 市场份额占到 60%，开发群体遍布世界各地，因此 Debian 会被发现其中本来存在着大量的漏洞。Android 同样是开源软件中的佼佼者，开发者依然是一个庞大的群体，因此 Android 漏洞也很多。

Linux Kernel 代码量级相对 Debian、Android 小，但是有更多的人在用 Linux Kernel 源码，因此漏洞多。而 Windows，因为是闭源产品，所以漏洞反而不容易被发现。

思考题

最后我再给你出一道需要查资料的思考题：林纳斯 21 岁写出 Linux，那么开发一个操作系统的难度到底大不大？

你可以把你的答案、思路或者课后总结写在留言区，这样可以帮助你产生更多的思考，这也是构建知识体系的一部分。经过长期的积累，相信你会得到意想不到的收获。如果你觉得今天的内容对你有所启发，欢迎分享给身边的朋友。期待看到你的思考！

加餐 | 练习题详解（三）

练习题详解

13 | 操作系统内核：Linux 内核和 Windows 内核有什么区别？

【问题】 Unix 和 Mac OS 内核属于哪种类型？

【解析】 Unix 和 Linux 非常类似，也是宏内核。Mac OS 用的是 XNU 内核， XNU 是一种混合型内核。为了帮助你理解，我找了一张 Mac OS 的内核架构图。 如下图所示，可以看到内部是一个叫作 XNU 的宏内核。XNU 是 X is not Unix 的意思， 是一个受 Unix 影响很大的内核。

Mac OS 内核架构图

14 | 用户态和内核态：用户态线程和内核态线程有什么区别？

【问题】 JVM 的线程是用户态线程还是内核态线程？

【解析】 JVM 自己本身有一个线程模型。在 JDK 1.1 的时候，JVM 自己管理用户级线程。这样做缺点非常明显，操作系统只调度内核级线程，用户级线程相当于基于操作系统分配到进程主线程的时间片，再次拆分，因此无法利用多核特性。

为了解决这个问题，后来 Java 改用线程映射模型，因此，需要操作系统支持。在 Windows 上是 1 对 1 的模型，在 Linux 上是 n 对 m 的模型。顺便说一句，Linux 的PThreadAPI 创建的是用户级线程，如果 Linux 要创建内核级线程有KThreadAPI。映射关系是操作系统自动完成的，用户不需要管。

15 | 中断和中断向量：Java/JS 等语言为什么可以捕获到键盘输入？

【问题】 操作系统可以处理键盘按键，这很好理解，但是在开机的时候系统还没有载入内存，为什么可以使用键盘呢？这个怎么解释？

【解析】 主板的一块 ROM 上往往还有一个简化版的操作系统，叫 BIOS（Basic Input/Ouput System）。在 OS 还没有接管计算机前，先由 BIOS 管理机器，并协助加载 OS 到内存。早期的 OS 还会利用 BIOS 的能力，现代的 OS 接管后，就会替换掉 BIOS 的中断向量。

16 | Win/Mac/Unix/Linux 的区别和联系：为什么 Debian 漏洞排名第一还这么多人用？

【问题】 林纳斯 21 岁写出 Linux，那么开发一个操作系统的难度到底大不大？

【解析】 毫无疑问能在 21 岁就写出 Linux 的人定是天赋异禀，林纳斯是参照一个 Minix 系统写的 Linux 内核。如果你对此感兴趣，可以参考这个 1991 年的源代码。

写一个操作系统本身并不是非常困难。需要了解一些基础的数据结构与算法，硬件设备工作原理。关键是要有参照，比如核心部分可以参考前人的内核。

但是随着硬件、软件技术发展了这么多年，如果想再写一个大家能够接受的内核，是一件非常困难的事情。内核的能力在上升，硬件的种类在上升，所以 Android 和很多后来的操作系统都是拿 Linux 改装。

总结

操作系统中的程序，除去内核部分，剩下绝大多数都可以称为应用。应用是千变万化的，内核是统一而稳定的。操作系统分成 3 层：应用层、内核层、硬件层。因此，内核是连接应用和硬件的桥梁。

内核需要公平的对待每个 CPU，于是有了用户态和内核态的切换；为了实现切换，需要中断；为了保护内存资源，需要划分用户态和内核态；为了更好地使用计算资源，需要划分线程——而线程需要操作系统内核调度。本模块所讲的内容，还只是对内核理解的冰山一角，后面我们还会从多线程、内存管理、文件系统、虚拟化的角度，重新审视内核的设计。

最后，我再跟你分享一下我自己的一点小小心得：在给你讲解操作系统的过程中，我仿佛也回到了 20 世纪 70 年代那个风起云涌的时代。在整理操作系统、编程语言、个人电脑领域的大黑客、发明家、企业家们的故事时，我发现这些程序员，强大的不仅仅是技术和创造力，更多的还是对时机的把握。我觉得从这个角度来看，除了要提升自身的技术能力，你也要重视人文知识的学习，这可以帮助你在以后的工作中做得更好。

好的，操作系统基本概念部分就告一段落。接下来，我们将开始多线程并发相关学习，请和我一起来学习“模块四：进程和线程”吧。

模块四：进程和线程

17 | 进程和线程：

进程的开销比线程大在了哪里？

不知你在面试中是否遇到过这样的问题，题目很短，看似简单，但在回答时又感觉有点吃力？比如下面这两个问题：

• 进程内部都有哪些数据？
• 为什么创建进程的成本很高？

这样的问题确实不好回答，除非你真正理解了进程和线程的原理，否则很容易掉入面试大坑。本讲，我将带你一起探究问题背后的原理，围绕面试题展开理论与实践知识的学习。通过本讲的学习，希望你可以真正理解进程和线程原理，从容应对面试。

进程和线程

进程（Process），顾名思义就是正在执行的应用程序，是软件的执行副本。而线程是轻量级的进程。

进程是分配资源的基础单位。而线程很长一段时间被称作轻量级进程（Light Weighted Process），是程序执行的基本单位。

在计算机刚刚诞生的年代，程序员拿着一个写好程序的闪存卡，插到机器里，然后电能推动芯片计算，芯片每次从闪存卡中读出一条指令，执行后接着读取下一条指令。闪存中的所有指令执行结束后，计算机就关机。

早期的 ENIAC

一开始，这种单任务的模型，在那个时代叫作作业（Job），当时计算机的设计就是希望可以多处理作业。图形界面出现后，人们开始利用计算机进行办公、购物、聊天、打游戏等，因此一台机器正在执行的程序会被随时切来切去。于是人们想到，设计进程和线程来解决这个问题。

每一种应用，比如游戏，执行后是一个进程。但是游戏内部需要图形渲染、需要网络、需要响应用户操作，这些行为不可以互相阻塞，必须同时进行，这样就设计成线程。

资源分配问题

设计进程和线程，操作系统需要思考分配资源。最重要的 3 种资源是：计算资源（CPU）、内存资源和文件资源。早期的 OS 设计中没有线程，3 种资源都分配给进程，多个进程通过分时技术交替执行，进程之间通过管道技术等进行通信。

但是这样做的话，设计者们发现用户（程序员），一个应用往往需要开多个进程，因为应用总是有很多必须要并行做的事情。并行并不是说绝对的同时，而是说需要让这些事情看上去是同时进行的——比如图形渲染和响应用户输入。于是设计者们想到了，进程下面，需要一种程序的执行单位，仅仅被分配 CPU 资源，这就是线程。

轻量级进程

线程设计出来后，因为只被分配了计算资源（CPU），因此被称为轻量级进程。被分配的方式，就是由操作系统调度线程。操作系统创建一个进程后，进程的入口程序被分配到了一个主线程执行，这样看上去操作系统是在调度进程，其实是调度进程中的线程。

这种被操作系统直接调度的线程，我们也成为内核级线程。另外，有的程序语言或者应用，用户（程序员）自己还实现了线程。相当于操作系统调度主线程，主线程的程序用算法实现子线程，这种情况我们称为用户级线程。Linux 的 PThread API 就是用户级线程，KThread API 则是内核级线程。

分时和调度

因为通常机器中 CPU 核心数量少（从几个到几十个）、进程&线程数量很多（从几十到几百甚至更多），你可以类比为发动机少，而机器多，因此进程们在操作系统中只能排着队一个个执行。每个进程在执行时都会获得操作系统分配的一个时间片段，如果超出这个时间，就会轮到下一个进程（线程）执行。再强调一下，现代操作系统都是直接调度线程，不会调度进程。

分配时间片段

如下图所示，进程 1 需要 2 个时间片段，进程 2 只有 1 个时间片段，进程 3 需要 3 个时间片段。因此当进程 1 执行到一半时，会先挂起，然后进程 2 开始执行；进程 2 一次可以执行完，然后进程 3 开始执行，不过进程 3 一次执行不完，在执行了 1 个时间片段后，进程 1 开始执行；就这样如此周而复始。这个就是分时技术。

下面这张图更加直观一些，进程 P1 先执行一个时间片段，然后进程 P2 开始执行一个时间片段， 然后进程 P3，然后进程 P4……

注意，上面的两张图是以进程为单位演示，如果换成线程，操作系统依旧是这么处理。

进程和线程的状态

一个进程（线程）运行的过程，会经历以下 3 个状态：

• 进程（线程）创建后，就开始排队，此时它会处在“就绪”（Ready）状态；
• 当轮到该进程（线程）执行时，会变成“运行”（Running）状态；
• 当一个进程（线程）将操作系统分配的时间片段用完后，会回到“就绪”（Ready）状态。

我这里一直用进程(线程）是因为旧的操作系统调度进程，没有线程；现代操作系统调度线程。

有时候一个进程（线程）会等待磁盘读取数据，或者等待打印机响应，此时进程自己会进入“阻塞”（Block）状态。

因为这时计算机的响应不能马上给出来，而是需要等待磁盘、打印机处理完成后，通过中断通知 CPU，然后 CPU 再执行一小段中断控制程序，将控制权转给操作系统，操作系统再将原来阻塞的进程（线程）置为“就绪”（Ready）状态重新排队。

而且，一旦一个进程（线程）进入阻塞状态，这个进程（线程）此时就没有事情做了，但又不能让它重新排队（因为需要等待中断），所以进程（线程）中需要增加一个“阻塞”（Block）状态。

注意，因为一个处于“就绪”（Ready）的进程（线程）还在排队，所以进程（线程）内的程序无法执行，也就是不会触发读取磁盘数据的操作，这时，“就绪”（Ready）状态无法变成阻塞的状态，因此下图中没有从就绪到阻塞的箭头。

而处于“阻塞”（Block）状态的进程（线程）如果收到磁盘读取完的数据，它又需要重新排队，所以它也不能直接回到“运行”（Running）状态，因此下图中没有从阻塞态到运行态的箭头。

进程和线程的设计

接下来我们思考几个核心的设计约束：

1. 进程和线程在内存中如何表示？需要哪些字段？
2. 进程代表的是一个个应用，需要彼此隔离，这个隔离方案如何设计？
3. 操作系统调度线程，线程间不断切换，这种情况如何实现？
4. 需要支持多 CPU 核心的环境，针对这种情况如何设计？

接下来我们来讨论下这4个问题。

进程和线程的表示

可以这样设计，在内存中设计两张表，一张是进程表、一张是线程表。

进程表记录进程在内存中的存放位置、PID 是多少、当前是什么状态、内存分配了多大、属于哪个用户等，这就有了进程表。如果没有这张表，进程就会丢失，操作系统不知道自己有哪些进程。这张表可以考虑直接放到内核中。

细分的话，进程表需要这几类信息。

• 描述信息：这部分是描述进程的唯一识别号，也就是 PID，包括进程的名称、所属的用户等。
• 资源信息：这部分用于记录进程拥有的资源，比如进程和虚拟内存如何映射、拥有哪些文件、在使用哪些 I/O 设备等，当然 I/O 设备也是文件。
• 内存布局：操作系统也约定了进程如何使用内存。如下图所示，描述了一个进程大致内存分成几个区域，以及每个区域用来做什么。 每个区域我们叫作一个段。

操作系统还需要一张表来管理线程，这就是线程表。线程也需要 ID， 可以叫作 ThreadID。然后线程需要记录自己的执行状态（阻塞、运行、就绪）、优先级、程序计数器以及所有寄存器的值等等。线程需要记录程序计数器和寄存器的值，是因为多个线程需要共用一个 CPU，线程经常会来回切换，因此需要在内存中保存寄存器和 PC 指针的值。

用户级线程和内核级线程存在映射关系，因此可以考虑在内核中维护一张内核级线程的表，包括上面说的字段。

如果考虑到这种映射关系，比如 n-m 的多对多映射，可以将线程信息还是存在进程中，每次执行的时候才使用内核级线程。相当于内核中有个线程池，等待用户空间去使用。每次用户级线程把程序计数器等传递过去，执行结束后，内核线程不销毁，等待下一个任务。这里其实有很多灵活的实现，总体来说，创建进程开销大、成本高；创建线程开销小，成本低。

隔离方案

操作系统中运行了大量进程，为了不让它们互相干扰，可以考虑为它们分配彼此完全隔离的内存区域，即便进程内部程序读取了相同地址，而实际的物理地址也不会相同。这就好比 A 小区的 10 号楼 808 和 B 小区的 10 号楼 808 不是一套房子，这种方法叫作地址空间，我们将在“21 讲”的页表部分讨论“地址空间”的详细内容。

所以在正常情况下进程 A 无法访问进程 B 的内存，除非进程 A 找到了某个操作系统的漏洞，恶意操作了进程 B 的内存，或者利用我们在“21 讲”讲到的“进程间通信”的手段。

对于一个进程的多个线程来说，可以考虑共享进程分配到的内存资源，这样线程就只需要被分配执行资源。

进程（线程）切换

进程（线程）在操作系统中是不断切换的，现代操作系统中只有线程的切换。 每次切换需要先保存当前寄存器的值的内存，注意 PC 指针也是一种寄存器。当恢复执行的时候，就需要从内存中读出所有的寄存器，恢复之前的状态，然后执行。

上面讲到的内容，我们可以概括为以下 5 个步骤：

1. 当操作系统发现一个进程（线程）需要被切换的时候，直接控制 PC 指针跳转是非常危险的事情，所以操作系统需要发送一个“中断”信号给 CPU，停下正在执行的进程（线程）。
2. 当 CPU 收到中断信号后，正在执行的进程（线程）会立即停止。注意，因为进程（线程）马上被停止，它还来不及保存自己的状态，所以后续操作系统必须完成这件事情。
3. 操作系统接管中断后，趁寄存器数据还没有被破坏，必须马上执行一小段非常底层的程序（通常是汇编编写），帮助寄存器保存之前进程（线程）的状态。
4. 操作系统保存好进程状态后，执行调度程序，决定下一个要被执行的进程（线程）。
5. 最后，操作系统执行下一个进程（线程）。

当然，一个进程（线程）被选择执行后，它会继续完成之前被中断时的任务，这需要操作系统来执行一小段底层的程序帮助进程（线程）恢复状态。

一种可能的算法就是通过栈这种数据结构。进程（线程）中断后，操作系统负责压栈关键数据（比如寄存器）。恢复执行时，操作系统负责出栈和恢复寄存器的值。

多核处理

在多核系统中我们上面所讲的设计原则依然成立，只不过动力变多了，可以并行执行的进程（线程）。通常情况下，CPU 有几个核，就可以并行执行几个进程（线程）。这里强调一个概念，我们通常说的并发，英文是 concurrent，指的在一段时间内几个任务看上去在同时执行（不要求多核）；而并行，英文是 parallel，任务必须绝对的同时执行（要求多核）。

比如一个 4 核的 CPU 就好像拥有 4 条流水线，可以并行执行 4 个任务。一个进程的多个线程执行过程则会产生竞争条件，这块我们会在“19 讲”锁和信号量部分给你介绍。因为操作系统提供了保存、恢复进程状态的能力，使得进程（线程）也可以在多个核心之间切换。

创建进程（线程）的 API

用户想要创建一个进程，最直接的方法就是从命令行执行一个程序，或者双击打开一个应用。但对于程序员而言，显然需要更好的设计。

站在设计者的角度，你可以这样思考：首先，应该有 API 打开应用，比如可以通过函数打开某个应用；另一方面，如果程序员希望执行完一段代价昂贵的初始化过程后，将当前程序的状态复制好几份，变成一个个单独执行的进程，那么操作系统提供了 fork 指令。

也就是说，每次 fork 会多创造一个克隆的进程，这个克隆的进程，所有状态都和原来的进程一样，但是会有自己的地址空间。如果要创造 2 个克隆进程，就要 fork 两次。

你可能会问：那如果我就是想启动一个新的程序呢？

我在上文说过：操作系统提供了启动新程序的 API。

你可能还会问：如果我就是想用一个新进程执行一小段程序，比如说每次服务端收到客户端的请求时，我都想用一个进程去处理这个请求。

如果是这种情况，我建议你不要单独启动进程，而是使用线程。因为进程的创建成本实在太高了，因此不建议用来做这样的事情：要创建条目、要分配内存，特别是还要在内存中形成一个个段，分成不同的区域。所以通常，我们更倾向于多创建线程。

不同程序语言会自己提供创建线程的 API，比如 Java 有 Thread 类；go 有 go-routine（注意不是协程，是线程）。

总结

本讲我们学习了进程和线程的基本概念。了解了操作系统如何调度进程（线程）和分时算法的基本概念，然后了解进程（线程）的 3 种基本状态。线程也被称作轻量级进程，由操作系统直接调度的，是内核级线程。我们还学习了线程切换保存、恢复状态的过程。

我们发现进程和线程是操作系统为了分配资源设计的两个概念，进程承接存储资源，线程承接计算资源。而进程包含线程，这样就可以做到进程间内存隔离。这是一个非常巧妙的设计，概念清晰，思路明确，你以后做架构的时候可以多参考这样的设计。 如果只有进程，或者只有线程，都不能如此简单的解决我们遇到的问题。

那么通过这节课的学习，你现在可以来回答本节关联的面试题目：进程的开销比线程大在了哪里？

【解析】 Linux 中创建一个进程自然会创建一个线程，也就是主线程。创建进程需要为进程划分出一块完整的内存空间，有大量的初始化操作，比如要把内存分段（堆栈、正文区等）。创建线程则简单得多，只需要确定 PC 指针和寄存器的值，并且给线程分配一个栈用于执行程序，同一个进程的多个线程间可以复用堆栈。因此，创建进程比创建线程慢，而且进程的内存开销更大。

思考题

最后我再给你出一道思考题。考虑下面的程序：

fork()

fork()

fork()

print("Hello World\n")

请问这个程序执行后， 输出结果 Hello World 会被打印几次？

18 | 锁、信号量和分布式锁：

如何控制同一时间只有 2 个线程运行？

锁是一个面试的热门话题，有乐观锁、悲观锁、重入锁、公平锁、分布式锁。有很多和锁相关的数据结构，比如说阻塞队列。还有一些关联的一些工具，比如说 Semaphore、Monitor 等。这些知识点可以关联很多的面试题目，比如：

• 锁是如何实现的？
• 如何控制同一时间只有 2 个线程运行？
• 如何实现分布式锁？

面试官通过这类题目考查你的这部分知识，就知道你对并发的理解是停留在表面，还是可以深入原理，去设计高并发的数据结构。这一讲我将帮你把锁类问题一网打尽。

原子操作

要想弄清楚锁，就要弄清楚锁的实现，实现锁需要底层提供的原子操作，因此我们先来学习下原子操作。

原子操作就是操作不可分。在多线程环境，一个原子操作的执行过程无法被中断。那么你可以思考下，具体原子操作的一个示例。

比如i++就不是一个原子操作，因为它是 3 个原子操作组合而成的：

1. 读取 i 的值；
2. 计算 i+1；
3. 写入新的值。

像这样的操作，在多线程 + 多核环境会造成竞争条件。

竞争条件

竞争条件就是说多个线程对一个资源（内存地址）的读写存在竞争，在这种条件下，最后这个资源的值不可预测，而是取决于竞争时具体的执行顺序。

举个例子，比如两个线程并发执行i++。那么可以有下面这个操作顺序，假设执行前i=0：

虽然上面的程序执行了两次i++，但最终i的值为 1。

i++这段程序访问了共享资源，也就是变量i，这种访问共享资源的程序片段我们称为临界区。在临界区，程序片段会访问共享资源，造成竞争条件，也就是共享资源的值最终取决于程序执行的时序，因此这个值不是确定的。

竞争条件是一件非常糟糕的事情，你可以把上面的程序想象成两个自动提款机。如果用户同时操作两个自动提款机，用户的余额就可能会被算错。

解决竞争条件

解决竞争条件有很多方案，一种方案就是不要让程序同时进入临界区，这个方案叫作互斥。还有一些方案旨在避免竞争条件，比如 ThreadLocal、 cas 指令以及 “19 讲”中我们要学习的乐观锁。

避免临界区

不让程序同时进入临界区这个方案比较简单，核心就是我们给每个线程一个变量i，比如利用 ThreadLocal，这样线程之间就不存在竞争关系了。这样做优点很明显，缺点就是并不是所有的情况都允许你这样做。有一些资源是需要共享的，比如一个聊天室，如果每次用户请求都有一个单独的线程在处理，不可能为每个请求（线程）都维护一份聊天记录。

cas 指令

先查再操作结果滞后了操作失败

另一个方案是利用 CPU 的指令，让i++成为一个原子操作。 很多 CPU 都提供 Compare And Swap 指令。这个指令的作用是更新一个内存地址的值，比如把i更新为i+1，但是这个指令明确要求使用者必须确定知道内存地址中的值是多少。比如一个线程想把i从100更新到101，线程必须明确地知道现在i是 100，否则就会更新失败。

cas 可以用下面这个函数表示：

cas(&oldValue, expectedValue, targetValue)

这里我用的是伪代码，用&符号代表这里取内存地址。注意 cas 是 CPU 提供的原子操作。因此上面的比较和设置值的过程，是原子的，也就是不可分。

比如想用 cas 更新i的值，而且知道i是 100，想更新成101。那么就可以这样做：

cas(&i, 100, 101)

如果在这个过程中，有其他线程把i更新为101，这次调用会返回 false，否则返回 true。

所以i++程序可以等价的修改为：

// i++等价程序

cas(&i, i, i+1)

上面的程序执行时，其实是 3 条指令：

读取i

计算i+1

cas操作：比较期望值i和i的真实值的值是否相等，如果是，更新目标值

假设i=0，考虑两个线程分别执行一次这个程序，尝试构造竞争条件：

你可以看到通过这种方式，cas 解决了一部分问题，找到了竞争条件，并返回了 false。但是还是无法计算出正确的结果。因为最后一次 cas 失败了。

如果要完全解决可以考虑这样去实现：

while(!cas(&i, i, i+1)){

// 什么都不做

}

如果 cas 返回 false，那么会尝试再读一次 i 的值，直到 cas 成功。

tas 指令

还有一个方案是 tas 指令，有的 CPU 没有提供 cas（大部分服务器是提供的），提供一种 Test-And-Set 指令（tas）。tas 指令的目标是设置一个内存地址的值为 1，它的工作原理和 cas 相似。首先比较内存地址的数据和 1 的值，如果内存地址是 0，那么把这个地址置 1。如果是 1，那么失败。

所以你可以把 tas 看作一个特殊版的cas，可以这样来理解：

> >

tas(&lock) {

return cas(&lock, 0, 1)

}

锁

锁（lock），目标是实现抢占（preempt）。就是只让给定数量的线程进入临界区。锁可以用tas或者cas来实现。

举个例子：如果希望同时只能有一个线程执行i++，伪代码可以这么写：

enter();

i++;

leave();

可以考虑用cas实现enter和leave函数，代码如下：

int lock = 0;

enter(){

  while( !cas(&lock, 0, 1) ) {

    // 什么也不做

  }

}

leave(){

  lock = 0;

}

多个线程竞争一个整数的 lock 变量，0 代表目前没有线程进入临界区，1 代表目前有线程进入临界区。利用cas原子指令我们可以对临界区进行管理。如果一个线程利用 cas 将 lock 设置为 1，那么另一个线程就会一直执行cas操作，直到锁被释放。

语言级锁的实现

上面解决竞争条件的时候，我们用到了锁。 相比 cas，锁是一种简单直观的模型。总体来说，cas 更底层，用 cas 解决问题优化空间更大。但是用锁解决问题，代码更容易写——进入临界区之前 lock，出去就 unlock。 从上面这段代码可以看出，为了定义锁，我们需要用到一个整型。如果实现得好，可以考虑这个整数由语言级定义。

比如考虑让用户传递一个变量过去：

int lock = 0;

enter(&lock);

//临界区代码

leave(&lock);

自旋锁

while 语句 c'pu 不断消耗的锁，空转

上面我们已经用过自旋锁了，这是之前的代码：

enter(){

  while( !cas(&lock, 0, 1) ) {

    // 什么也不做

  }

}

这段代码不断在 CPU 中执行指令，直到锁被其他线程释放。这种情况线程不会主动释放资源，我们称为自旋锁。自旋锁的优点就是不会主动发生 Context Switch，也就是线程切换，因为线程切换比较消耗时间。自旋锁缺点也非常明显，比较消耗 CPU 资源。如果自旋锁一直拿不到锁，会一直执行。

wait 操作

你可以考虑实现一个 wait 操作，主动触发 Context Switch。这样就解决了 CPU 消耗的问题。但是触发 Context Switch 也是比较消耗成本的事情，那么有没有更好的方法呢？

enter(){

  while( !cas(&lock, 0, 1) ) {

    // sleep(1000ms);

    wait();

  }

}

你可以看下上面的代码，这里有一个更好的方法：就是 cas 失败后，马上调用sleep方法让线程休眠一段时间。但是这样，可能会出现锁已经好了，但是还需要多休眠一小段时间的情况，影响计算效率。

另一个方案，就是用wait方法，等待一个信号——直到另一个线程调用notify方法，通知这个线程结束休眠。但是这种情况——wait 和 notify 的模型要如何实现呢？

生产者消费者模型

一个合理的实现就是生产者消费者模型。 wait 是一个生产者，将当前线程挂到一个等待队列上，并休眠。notify 是一个消费者，从等待队列中取出一个线程，并重新排队。

如果使用这个模型，那么我们之前简单用enter和leave来封装加锁和解锁的模式，就需要变化。我们需要把enter``leave``wait``notify的逻辑都封装起来，不让用户感知到它们的存在。

比如 Java 语言，Java 为每个对象增加了一个 Object Header 区域，里面一个锁的位（bit），锁并不需要一个 32 位整数，一个 bit 足够。下面的代码用户使用 synchronized 关键字让临界区访问互斥。

synchronized(obj){// enter

  // 临界区代码

} // leave

synchronized 关键字的内部实现，用到了封装好的底层代码——Monitor 对象。每个 Java 对象都关联了一个 Monitor 对象。Monitor 封装了对锁的操作，比如 enter、leave 的调用，这样简化了 Java 程序员的心智负担，你只需要调用 synchronized 关键字。

另外，Monitor 实现了生产者、消费者模型。

• 如果一个线程拿到锁，那么这个线程继续执行；
• 如果一个线程竞争锁失败，Montior 就调用 wait 方法触发生产者的逻辑，把线程加入等待集合；
• 如果一个线程执行完成，Monitor 就调用一次 notify 方法恢复一个等待的线程。

这样，Monitor 除了提供了互斥，还提供了线程间的通信，避免了使用自旋锁，还简化了程序设计。

信号量

互斥的一个广义版 两个互斥线程有逻辑的实现

接下来介绍一个叫作信号量的方法，你可以把它看作是互斥的一个广义版。我们考虑一种更加广义的锁，这里请你思考如何同时允许 N 个线程进入临界区呢？

我们先考虑实现一个基础的版本，用一个整数变量lock来记录进入临界区线程的数量。

int lock = 0;

enter(){

  while(lock++ > 2) { }

}

leave(){

  lock--;

}

上面的代码具有一定的欺骗性，没有考虑到竞争条件，执行的时候会出问题，可能会有超过2个线程同时进入临界区。

下面优化一下，作为一个考虑了竞争条件的版本：

up(&lock){

  while(!cas(&lock, lock, lock+1)) { }

}

down(&lock){

  while(!cas(&lock, lock, lock - 1) || lock == 0){}

}

为了简化模型，我们重新设计了两个原子操作up和down。up将lock增 1，down将lock减 1。当 lock 为 0 时，如果还在down那么会自旋。考虑用多个线程同时执行下面这段程序：

int lock = 2;

down(&lock);

// 临界区

up(&lock);

如果只有一个线程在临界区，那么lock等于 1，第 2 个线程还可以进入。 如果两个线程在临界区，第 3 个线程尝试down的时候，会陷入自旋锁。当然我们也可以用其他方式来替代自旋锁，比如让线程休眠。

当lock初始值为 1 的时候，这个模型就是实现互斥（mutex）。如果 lock 大于 1，那么就是同时允许多个线程进入临界区。这种方法，我们称为信号量（semaphore）。

信号量实现生产者消费者模型 信号量可以用来实现生产者消费者模型。下面我们通过一段代码实现生产者消费者：

int empty = N; // 当前空位置数量

int mutex = 1; // 锁

int full = 0; // 当前的等待的线程数

wait(){

  down(&empty);

  down(&mutex);

  insert(); 

  up(&mutex);

  up(&full);



}

notify(){

  down(&full);

  down(&mutex);

  remove(); 

  up(&mutex);

  up(&empty)

}

insert(){

  wait_queue.add(currentThread);

  yield();

}

remove(){

  thread = wait_queue.dequeue();

  thread.resume();

}

代码中 wait 是生产者，notify 是消费者。 每次wait操作减少一个空位置数量，empty-1；增加一个等待的线程，full+1。每次notify操作增加一个空位置，empty+1，减少一个等待线程，full-1。

insert和remove方法是互斥的操作，需要用另一个 mutex 锁来保证。insert方法将当前线程加入等待队列，并且调用 yield 方法，交出当前线程的控制权，当前线程休眠。remove方法从等待队列中取出一个线程，并且调用resume进行恢复。以上， 就构成了一个简单的生产者消费者模型

死锁问题

另外就是在并行的时候，如果两个线程互相等待对方获得的锁，就会发生死锁。你可以把死锁理解成一个环状的依赖关系。比如：

int lock1 = 0;

int lock2 = 0;

// 线程1

enter(&lock1);

enter(&lock2);

leave(&lock1);

leave(&lock2);

// 线程2

enter(&lock2);

enter(&lock1);

leave(&lock1);

leave(&lock2)
上面的程序，如果是按照下面这个顺序执行，就会死锁：
线程1： enter(&lock1);

线程2： enter(&lock2);

线程1： enter(&lock2)

线程2:  enter(&lock1)

// 死锁发生，线程1、2陷入等待

上面程序线程 1 获得了lock1，线程 2 获得了lock2。接下来线程 1 尝试获得lock2，线程 2 尝试获得lock1，于是两个线程都陷入了等待。这个等待永远都不会结束，我们称之为死锁。

关于死锁如何解决，我们会在“21 | 哲学家就餐问题：什么情况下会触发饥饿和死锁？”讨论。这里我先讲一种最简单的解决方案，你可以尝试让两个线程对锁的操作顺序相同，这样就可以避免死锁问题。

分布式环境的锁

最后，我们留一点时间给分布式锁。我们之前讨论了非常多的实现，是基于多个线程访问临界区。现在要考虑一个更庞大的模型，我们有 100 个容器，每一个里面有一个为用户减少积分的服务。

简化下模型，假设积分存在 Redis 中。当然数据库中也有，但是我们只考虑 Redis。使用 Redis，我们目标是给数据库减负。

假设这个接口可以看作 3 个原子操作：

1 从 Redis 读出当前库存；

2 计算库存 -1；

3 更新 Redis 库存。

和i++类似，很明显，当用户并发的访问这个接口，是会发生竞争条件的。 因为程序已经不是在同一台机器上执行了，解决方案就是分布式锁。实现锁，我们需要原子操作。

在单机多线程并发的场景下，原子操作由 CPU 指令提供，比如 cas 和 tas 指令。那么在分布式环境下，原子操作由谁提供呢？

有很多工具都可以提供分布式的原子操作，比如 Redis 的 setnx 指令，Zookeeper 的节点操作等等。作为操作系统课程，这部分我不再做进一步的讲解。这里是从多线程的处理方式，引出分布式的处理方式，通过两个类比，帮助你提高。如果你感兴趣，可以自己查阅更多的分布式锁的资料。

总结 那么通过这节课的学习，你现在可以尝试来回答本讲关联的面试题目：如何控制同一时间只有 2 个线程运行？

老规矩，请你先在脑海里构思下给面试官的表述，并把你的思考写在留言区，然后再来看我接下来的分析。

【解析】 同时控制两个线程进入临界区，一种方式可以考虑用信号量（semaphore）。

另一种方式是考虑生产者、消费者模型。想要进入临界区的线程先在一个等待队列中等待，然后由消费者每次消费两个。这种实现方式，类似于实现一个线程池，所以也可以考虑实现一个 ThreadPool 类，然后再实现一个调度器类，最后实现一个每次选择两个线程执行的调度算法。

思考题 最后我再给你出一道需要查资料的思考题：如果考虑到 CPU 缓存的存在，会对上面我们讨论的算法有什么影响？

你可以把你的答案、思路或者课后总结写在留言区，这样可以帮助你产生更多的思考，这也是构建知识体系的一部分。经过长期的积累，相信你会得到意想不到的收获。如果你觉得今天的内容对你有所启发，欢迎分享给身边的朋友。期待看到你的思考！

19 | 乐观锁、区块链：除了上锁还有哪些并发控制方法？

这一讲我带来的面试题是：除了上锁还有哪些并发控制方法？

上面这道面试题是在“有哪些并发控制方法？”这个问题的基础上加了一个限制条件。

在我面试候选人的过程中，“上锁”是我听到过回答频次最多的答案，也就是说大多数程序员都可以想到这个并发控制方法。因此，是否能回答出上锁以外的方法，是检验程序员能力的一个分水岭，其实锁以外还有大量优秀的方法。

你掌握的方法越多，那么在解决实际问题的时候，思路就越多。即使你没有做过高并发场景的设计，但是如果脑海中有大量优秀的方法可以使用，那么公司也会考虑培养你，将高并发场景交给你去解决。今天我们就以这道面试题为引，一起探讨下“锁以外的并发控制方法”。

悲观锁/乐观锁

悲观锁： 实际上锁的所有锁

乐观锁：版本控制，假锁

说到并发场景，设计系统的目的往往是达到同步（Synchronized）的状态，同步就是大家最终对数据的理解达成了一致。

同步的一种方式，就是让临界区互斥。 这种方式，每次只有一个线程可以进入临界区。比如多个人修改一篇文章，这意味着必须等一个人编辑完，另一个人才能编辑。但是从实际问题出发，如果多个人编辑的不是文章的同一部分，是可以同时编辑的。因此，让临界区互斥的方法（对临界区上锁），具有强烈的排他性，对修改持保守态度，我们称为悲观锁（Pressimistic Lock）。

通常意义上，我们说上锁，就是悲观锁，比如说 MySQL 的表锁、行锁、Java 的锁，本质是互斥（mutex）。

和悲观锁（PressimisticLock）持相反意见的，是乐观锁（Optimistic Lock）。你每天都用的，基于乐观锁的应用就是版本控制工具 Git。Git 允许大家一起编辑，将结果先存在本地，然后都可以向远程仓库提交，如果没有版本冲突，就可以提交上去。这就是一种典型的乐观锁的场景，或者称为基于版本控制的场景。

Git 的类比

比如现在代码仓库的版本是 100。Bob 和 Alice 把版本 100 拷贝到本地，Bob 在本地写到了 106 版本，Alice 在本地写到 108 版本。那么如果 Alice 先提交，代码仓库的版本就到了 108。 Bob 再提交的时候，发现版本已经不是 100 了，就需要把最新的代码 fetch 到本地，然后合并冲突，再尝试提交一个更新的版本，比如 110。

这种方式非常类似cas指令的形式，就是每次更新的发起方，需要明确地知道想从多少版本更新到多少版本。以 Git 为例，可以写出cas的伪代码：

cas(&version, 100, 108); // 成功

cas(&version, 100, 106); // 失败，因为version是108

上面代码第二次cas操作时因为版本变了，更新失败，这就是一个乐观锁——Alice 和 Bob 可以同时写，先更新的人被采纳，后更新的人负责解决冲突。

购物车的类比

再举个例子，比如说要实现一个购物车。用户可能在移动端、PC 端之间切换，比如他用一会手机累了，然后换成用电脑，当他用电脑累了，再换回手机。

在移动端和 PC 端，用户都在操作购物车。 比如在移动端上，用户增加了商品 A；然后用户打开 PC 端，增加了商品 B；然后用户又换回了移动端，想增加商品 C。

这种时候，如果用悲观锁，用户登录移动端后，一种方案就是把 PC 端下线——当然这个方案显然不合理。 合理的方案是给购物车一个版本号，假设是 MySQL 表，那么购物车表中就会多一个版本字段。这样当用户操作购物车的时候，检查一下当前购物车的版本号是不是最新的，如果是最新的，那么就正常操作。如果不是最新的，就提示用户购物车在其他地方已被更新，需要刷新。

去中心化方案：区块链的类比

继续类比，我们可以思考一个更加有趣的方案。在传统的架构中，我们之所以害怕并发，是因为中心化。比如说 DNS 系统，如果全球所有的 DNS 查询都执行一个集群，这个吞吐量是非常恐怖的，因此 DNS 系统用了一个分级缓存的策略。

但是交易数据分布的时候，比如下单、支付、修改库存，如果用分布式处理，就牵扯到分布式锁（分布式事务）。那么，有没有一个去中心化的方案，让业务不需要集中处理呢？比如说双 11 期间你在淘宝上买东西，可不可以直接和商家下单，而不用通过淘宝的中心系统呢？——如果可以，这也就相当于实现了同步，或者说去掉了高并发的同步。

解决最基本的信用问题

考虑购买所有的网购产品，下单不再走中心化的平台。比如阿里、拼多多、 京东、抖音……这些平台用户都不走平台的中心系统下单，而是用户直接和商家签订合同。这个技术现在已经实现了，叫作电子合同。

举例：Alice（A）向苹果店 B 购买了一个 iPhone。那么双方签订电子合同，合同内容 C 是：

from=A, to=B, price=10000, signature=alice的签名

from=B, to=A, object=iphone, signature=苹果店的签名

上面两条记录，第 1 条是说 A 同意给 B 转 10000 块钱；第 2 条记录说，B 同意给 A 一个 iPhone。如果 A 收了 iPhone 不给 B 打款，B 可以拿着这个电子合同去法院告 A。因为用 A 的签名，可以确定是 Alice 签署了这份协议。同理，如果苹果店不给 Alice iPhone，Alice 可以去法院告苹果店，因为 Alice 可以用苹果店的签名证明合同是真的。

解决货币和库存的问题

有了上面的例子，最基本的信用问题解决了。接下来，你可能会问，Alice 怎么证明自己有足够的钱买 iPhone？苹果店怎么证明有足够的 iPhone？

比如在某个对公开放的节点中，记录了：

account=alice, money=10000

account=bob, iphone=100

…… 以及很多其他的数据

我们假设这里的钱可能是 Alice 用某种手段放进来的。或者我们再简化这个模型，比如全世界所有人的钱，都在这个系统里，这样我们就不用关心钱从哪里来这个问题了。如果是比特币，钱是需要挖矿的

如图，这个结构也叫作区块链。每个 Block 下面可以存一些数据，每个 Block 知道上一个节点是谁。每个 Block 有上一个节点的摘要签名。也就是说，如果 Block 10 是 Block 11 的上一个节点，那么 Block 11 会知道 Block 10 的存在，且用 Block 11 中 Block 10 的摘要签名，可以证明 Block 10 的数据没有被篡改过。

区块链构成了一个基于历史版本的事实链，前一个版本是后一个版本的历史。Alice 的钱和苹果店的 iPhone 数量，包括全世界所有人的钱，都在这些 Block 里。

购买转账的过程

下面请你思考，Alice 购买了 iPhone，需要提交两条新数据到上面的区块链。

from=A, to=B, price=10000, signature=alice的签名

from=B, to=A, object=iphone, signature=苹果店的签名

那么我们可以在末端节点上再增加一个区块，代表这次交易，如下图：

比如，Alice 先在本地完成这件事情，本地的区块链就会像上图那样。 假设有一个中心化的服务器，专门接收这些区块数据，Alice 接下来就可以把数据提交到中心化的服务器，苹果店从中心化服务器上看到这条信息，认为交易被 Alice 执行了，就准备发货。

如果世界上有很多人同时在这个末端节点上写新的 Block。那么可以考虑由一个可信任的中心服务帮助合并新增的区块数据。就好像多个人同时编辑了一篇文章，发生了冲突，那就可以考虑由一个人整合大家需要修改和新增的内容，避免同时操作产生混乱。

解决欺诈问题

正常情况下，所有记录都可以直接合并。但是比如Alice在一家店购买了 1 个 iPhone，在另外一家店购买了 2 个 iPhone，这个时候 Alice 的钱就不够付款了。 或者说 Alice 想用 20000 块买 3 个 iPhone，她还想骗一个。

那么 Alice 最终就需要写这样的记录：

from=A, to=B, price=10000, signature=alice的签名

from=B, to=A, object=iphone, signature=一个苹果店的签名

from=A, to=B1, price=20000, signature=alice的签名

from=B1, to=A, object=iphonex2, signature=另一个苹果店的签名

无论 Alice 以什么顺序写入这些记录，她的钱都是不够的，因为她只有 20000 的余额。 这样简单地就解决了欺诈问题。

如果 Alice 想要修改自己的余额，那么 Alice 怎么做呢？

Alice 需要新增一个末端的节点，比如她在末端节点上将自己的余额修改为 999999。那么 Alice 的余额，就和之前 Block 中记录的冲突了。简单一查，就知道 Alice 在欺诈。如果 Alice 想要修改之前的某个节点的数据，这个节点的摘要签名就会发生变化了， 那么后面所有的节点就失效了。

比如 Alice 修改了 Block 9 的数据，并把整个区块链拷贝给 Bob。Bob 通过验证签名，就知道 Alice 在骗人。如果 Alice 修改了所有 Block 9 以后的 Block，相当于修改了完整的一个链条，且修改了所有的签名。Bob 只需要核对其中几个版本和其他人，或者和中心服务的签名的区别就知道 Alice 在欺诈。

刚才有一个设计，就是有一个中心平台供 Bob 下载。如果中心平台修改了数据。那么 Bob 会马上发现存在本地的和自己相关的数据与中心平台不一致。这样 Bob 就会联合其他用户一起抵制中心平台。

所以结论是，区块链一旦写入就不能修改，这样可以防止很多欺诈行为。

解决并发问题

假设全球有几十亿人都在下单。那么每次下单，需要创建新的一个 Block。这种情况，会导致最后面的 Block，开很多分支。

这个时候你会发现，这里有同步问题对不对？ 最傻的方案就是用锁解决，比如用一个集中式的办法，去接收所有的请求，这样就又回到中心化的设计。

还有一个高明的办法，就是允许商家开分支。 用户和苹果店订合同，苹果店独立做一个分支，把用户的合同连起来。

这样苹果店自己先维护自己的 Block-Chain，等待合适的时机，再去合并到主分支上。 如果有合同合并不进去，比如余额不足，那再作废这个合同（不发货了）。

这里请你思考这样一种处理方式：如果全世界每天有 1000 亿笔订单要处理，那么可以先拆分成 100 个区域，每个区域是 10W 家店。这样最终每家店的平均并发量在 10000 单。 然后可以考虑每过多长时间，比如 10s，进行一次逐级合并。

这样，整体每个节点的压力就不是很大了。

总结

在这一讲，我们主要学习了一些比锁更加有趣的处理方式， 其实还有很多方式，你可以去思考。并发问题也不仅仅是要解决并发问题，并发还伴随着一致性、可用性、欺诈及吞吐量等。一名优秀的架构师是需要储备多个维度的知识，所以还是我常常跟你强调的，知识在于积累，绝非朝夕之功。

另外，我想告诉你的是，其实大厂并不是只招收处理过并发场景的工程师。作为一名资深面试官，我愿意给任何人机会，前提是你的方案打动了我。而设计方案的能力，是可以学习的。你要多思考，多查资料，多整理总结，这样久而久之，就有公司愿意让你做架构了。

那么通过这节课的学习，你现在可以尝试来回答本节关联的面试题目：除了上锁还有哪些并发控制方法？

【解析】 这个问题比较发散，这一讲我们介绍了基于乐观锁的版本控制，还介绍了区块链技术。另外还有一个名词，并不属于操作系统课程范畴，我也简单给你介绍下。处理并发还可以考虑 Lock-Free 数据结构。比如 Lock-Free 队列，是基于 cas 指令实现的，允许多个线程使用这个队列。再比如 ThreadLocal，让每个线程访问不同的资源，旨在用空间换时间，也是避免锁的一种方案。

思考题

最后我再给你出一道需要查资料的思考题：举例各 2 个悲观锁和乐观锁的应用场景？

你可以把你的答案、思路或者课后总结写在留言区，这样可以帮助你产生更多的思考，这也是构建知识体系的一部分。经过长期的积累，相信你会得到意想不到的收获。如果你觉得今天的内容对你有所启发，欢迎分享给身边的朋友。期待看到你的思考！

20 | 线程的调度：线程调度都有哪些方法？

这一讲我带来的面试题目是：线程调度都有哪些方法？

所谓调度，是一个制定计划的过程，放在线程调度背景下，就是操作系统如何决定未来执行哪些线程？

这类型的题目考察的并不是一个死的概念，面试官会通过你的回答考量你对知识进行加工和理解的能力。这有点类似于设计技术方案，要对知识进行系统化、结构化地思考和分类。就这道题目而言，可以抓两条主线，第一条是形形色色调度场景怎么来的？第二条是每个调度算法是如何工作的？

先到先服务

早期的操作系统是一个个处理作业（Job），比如很多保险业务，每处理一个称为一个作业（Job）。处理作业最容易想到的就是先到先服务（First Come First Service，FCFS），也就是先到的作业先被计算，后到的作业，排队进行。

这里需要用到一个叫作队列的数据结构，具有先入先出（First In First Out，FIFO）性质。先进入队列的作业，先处理，因此从公平性来说，这个算法非常朴素。另外，一个作业完全完成才会进入下一个作业，作业之间不会发生切换，从吞吐量上说，是最优的——因为没有额外开销。

但是这样对于等待作业的用户来说，是有问题的。比如一笔需要用时 1 天的作业 ，如果等待了 10 分钟，用户是可以接受的；一个用时 10 分钟的作业，用户等待一天就要投诉了。 因此如果用时 1 天的作业先到，用时 10 分钟的任务后到，应该优先处理用时少的，也就是短作业优先（Shortest Job First，SJF）。

短作业优先

通常会同时考虑到来顺序和作业预估时间的长短，比如下面的到来顺序和预估时间：

这样就会优先考虑第一个到来预估时间为 3 分钟的任务。 我们还可以从另外一个角度来审视短作业优先的优势，就是平均等待时间。

平均等待时间 = 总等待时间/任务数

上面例子中，如果按照 3,3,10 的顺序处理，平均等待时间是：(0 + 3 + 6) / 3 = 3 分钟。 如果按照 10,3,3 的顺序来处理，就是( 0+10+13 )/ 3 = 7.66 分钟。

平均等待时间和用户满意度是成反比的，等待时间越长，用户越不满意，因此在大多数情况下，应该优先处理用时少的，从而降低平均等待时长。

采用 FCFS 和 SJF 后，还有一些问题没有解决。

1. 紧急任务如何插队？比如老板安排的任务。
2. 等待太久的任务如何插队？比如用户等太久可能会投诉。
3. 先执行的大任务导致后面来的小任务没有执行如何处理？比如先处理了一个 1 天才能完成的任务，工作半天后才发现预估时间 1 分钟的任务也到来了。

为了解决上面的问题，我们设计了两种方案， 一种是优先级队列（PriorityQueue），另一种是抢占（Preemption）。

优先级队列（PriorityQueue）

刚才提到老板安排的任务需要紧急插队，那么下一个作业是不是应该安排给老板？毫无疑问肯定是这样！那么如何控制这种优先级顺序呢？一种方法是用优先级队列。优先级队列可以给队列中每个元素一个优先级，优先级越高的任务就会被先执行。

优先级队列的一种实现方法就是用到了堆（Heap）这种数据结构，更最简单的实现方法，就是每次扫描一遍整个队列找到优先级最高的任务。也就是说，堆（Heap）可以帮助你在 O(1) 的时间复杂度内查找到最大优先级的元素。

比如老板的任务，就给一个更高的优先级。 而对于普通任务，可以在等待时间（W） 和预估执行时间（P） 中，找一个数学关系来描述。比如：优先级 = W/P。W 越大，或者 P 越小，就越排在前面。 当然还可以有很多其他的数学方法，利用对数计算，或者某种特别的分段函数。

这样，关于紧急任务如何插队？等待太久的任务如何插队？这两个问题我们都解决了，接下来我们来看先执行的大任务导致后面来的小任务没有执行的情况如何处理？

抢占

为了解决这个问题，我们需要用到抢占（Preemption）。

抢占就是把执行能力分时，分成时间片段。 让每个任务都执行一个时间片段。如果在时间片段内，任务完成，那么就调度下一个任务。如果任务没有执行完成，则中断任务，让任务重新排队，调度下一个任务。

拥有了抢占的能力，再结合之前我们提到的优先级队列能力，这就构成了一个基本的线程调度模型。线程相对于操作系统是排队到来的，操作系统为每个到来的线程分配一个优先级，然后把它们放入一个优先级队列中，优先级最高的线程下一个执行。

每个线程执行一个时间片段，然后每次执行完一个线程就执行一段调度程序。

图中用红色代表调度程序，其他颜色代表被调度线程的时间片段。调度程序可以考虑实现为一个单线程模型，这样不需要考虑竞争条件。

上面这个模型已经是一个非常优秀的方案了，但是还有一些问题可以进一步处理得更好。

1. 如果一个线程优先级非常高，其实没必要再抢占，因为无论如何调度，下一个时间片段还是给它。那么这种情况如何实现？
2. 如果希望实现最短作业优先的抢占，就必须知道每个线程的执行时间，而这个时间是不可预估的，那么这种情况又应该如何处理？

为了解决上面两个问题，我们可以考虑引入多级队列模型。

多级队列模型

多级队列，就是多个队列执行调度。 我们先考虑最简单的两级模型，如图：

上图中设计了两个优先级不同的队列，从下到上优先级上升，上层队列调度紧急任务，下层队列调度普通任务。只要上层队列有任务，下层队列就会让出执行权限。

• 低优先级队列可以考虑抢占 + 优先级队列的方式实现，这样每次执行一个时间片段就可以判断一下高优先级的队列中是否有任务。
• 高优先级队列可以考虑用非抢占（每个任务执行完才执行下一个）+ 优先级队列实现，这样紧急任务优先级有个区分。如果遇到十万火急的情况，就可以优先处理这个任务。

上面这个模型虽然解决了任务间的优先级问题，但是还是没有解决短任务先行的问题。可以考虑再增加一些队列，让级别更多。比如下图这个模型：

紧急任务仍然走高优队列，非抢占执行。普通任务先放到优先级仅次于高优任务的队列中，并且只分配很小的时间片；如果没有执行完成，说明任务不是很短，就将任务下调一层。下面一层，最低优先级的队列中时间片很大，长任务就有更大的时间片可以用。通过这种方式，短任务会在更高优先级的队列中执行完成，长任务优先级会下调，也就类似实现了最短作业优先的问题。

实际操作中，可以有 n 层，一层层把大任务筛选出来。 最长的任务，放到最闲的时间去执行。要知道，大部分时间 CPU 不是满负荷的。

总结

那么通过这一讲的学习，你现在可以尝试来回答本节关联的面试题目：线程调度都有哪些方法？

【解析】 回答这个问题你要把握主线，千万不要教科书般的回答：任务调度分成抢占和非抢占的，抢占的可以轮流执行，也可以用优先级队列执行；非抢占可以先到先服务，也可以最短任务优先。

上面这种回答可以用来过普通的程序员岗位，但是面试官其实更希望听到你的见解，这是初中级开发人员与高级开发人员之间的差异。

比如你告诉面试官：非抢占的先到先服务的模型是最朴素的，公平性和吞吐量可以保证。但是因为希望减少用户的平均等待时间，操作系统往往需要实现抢占。操作系统实现抢占，仍然希望有优先级，希望有最短任务优先。

但是这里有个困难，操作系统无法预判每个任务的预估执行时间，就需要使用分级队列。最高优先级的任务可以考虑非抢占的优先级队列。 其他任务放到分级队列模型中执行，从最高优先级时间片段最小向最低优先级时间片段最大逐渐沉淀。这样就同时保证了小任务先行和高优任务最先执行。

以上的回答，并不是一种简单的概括，还包含了你对问题的理解和认知。在面试时，正确性并不是唯一的考量指标，面试官更看重候选人的思维能力。这也是为什么很多人面试问题都答上来了，仍然没有拿到 offer 的原因。如果面试目标是正确性，为什么不让你开卷考试呢？ 上维基百科看不是更正确吗？

思考题

最后我再给你出一道需要查资料的思考题：用你最熟悉的语言模拟分级队列调度的模型？

你可以把你的答案、思路或者课后总结写在留言区，这样可以帮助你产生更多的思考，这也是构建知识体系的一部分。经过长期的积累，相信你会得到意想不到的收获。如果你觉得今天的内容对你有所启发，欢迎分享给身边的朋友。期待看到你的思考

21 | 哲学家就餐问题：什么情况下会触发饥饿和死锁？

22 | 进程间通信： 进程间通信都有哪些方法？

23 | 分析服务的特性：我的服务应该开多少个进程、多少个线程？

加餐 | 练习题详解（四）

模块五：内存管理

24 | 虚拟内存 ：一个程序最多能使用多少内存？

25 | 内存管理单元： 什么情况下使用大内存分页？

26 | 缓存置换算法： LRU 用什么数据结构实现更合理？

27 | 内存回收上篇：如何解决内存的循环引用问题？

28 | 内存回收下篇：三色标记-清除算法是怎么回事？

加餐 | 练习题详解（五）

模块六：文件系统

29 | Linux 下的各个目录有什么作用？

30 | 文件系统的底层实现：FAT、NTFS 和 Ext3 有什么区别？

31 | 数据库文件系统实例：MySQL 中 B 树和 B+ 树有什么区别？

32 | HDFS 介绍：分布式文件系统是怎么回事？

加餐 | 练习题详解（六）

模块七：网络安全

33 | 互联网协议群（TCP/IP）：多路复用是怎么回事？

34 | UDP 协议：UDP 和 TCP 相比快在哪里？

35 | Linux 的 I/O 模式：select/poll/epoll 有什么区别？

36 | 公私钥体系和网络安全：什么是中间人攻击？

加餐 | 练习题详解（七）

模块八：虚拟化和其他

37 | 虚拟化技术介绍：VMware 和 Docker 的区别？

38 | 容器编排技术：如何利用 K8s 和 Docker Swarm 管理微服务？

39 | Linux 架构优秀在哪里?

40 | 商业操作系统：电商操作系统是不是一个噱头？

加餐 | 练习题详解（八）