图解操作系统

在 1945 年冯诺依曼和其他计算机科学家们提出了计算机具体实现的报告，其遵循了图灵机的设计，
而且还提出用电子元件构造计算机，并约定了用二进制进行计算和存储。

最重要的是定义计算机基本结构为 5 个部分，分别是 运算器、控制器、存储器、输入设备、输出设备，这 5 个部分也被称为 冯诺依曼模型。

运算器、控制器是在中央处理器里的，存储器就我们常见的内存，输入输出设备则是计算机外接的设备，比如键盘就是输入设备，显示器就是输出设备。

存储单元和输入输出设备要与中央处理器打交道的话，离不开 总线。所以，它们之间的关系如下图：

接下来，分别介绍内存、中央处理器、总线、输入输出设备。

我们的程序和数据都是存储在内存，存储的区域是线性的。

在计算机数据存储中，存储数据的基本单位是 字节（byte），1 字节等于 8 位（8 bit）。每一个字节都对应一个内存地址。

内存的地址是从 0 开始编号的，然后自增排列，最后一个地址为内存总字节数 - 1，
这种结构好似我们程序里的数组，所以内存读写任何一个数据的速度都是一样的。

中央处理器也就是我们常说的 CPU，32 位和 64 位 CPU 最主要区别在于 一次能计算多少字节数据：

• 32 位 CPU 一次可以计算 4 个字节；
• 64 位 CPU 一次可以计算 8 个字节；

这里的 32 位和 64 位，通常称为 CPU 的位宽。

之所以 CPU 要这样设计，是为了能计算更大的数值，如果是 8 位的 CPU，那么一次只能计算 1 个字节 0~255 范围内的数值，
这样就无法一次完成计算 10000 * 500 ，于是为了能一次计算大数的运算，CPU 需要支持多个 byte 一起计算，所以 CPU
位宽越大，可以计算的数值就越大，比如说 32 位 CPU 能计算的最大整数是 4294967295。

CPU 内部还有一些组件，常见的有 寄存器、控制单元和逻辑运算单元 等。其中：

• 控制单元负责控制 CPU 工作；
• 逻辑运算单元负责计算；
• 而寄存器可以分为多种类，每种寄存器的功能又不尽相同。

CPU 中的寄存器主要作用是存储计算时的数据，你可能好奇为什么有了内存还需要寄存器？原因很简单，
因为内存离 CPU 太远了，而 寄存器就在 CPU 里，还紧挨着控制单元和逻辑运算单元，自然 计算时速度会很快。

常见的寄存器种类：

• 通用寄存器，用来存放需要进行运算的数据，比如需要进行加和运算的两个数据。
• 程序计数器，用来存储 CPU 要执行下一条指令「所在的内存地址」，注意不是存储了
  下一条要执行的指令，此时指令还在内存中，程序计数器只是存储了下一条指令「的地址」。
• 指令寄存器，用来存放当前正在执行的指令，也就是指令本身，指令被执行完成之前，指令都存储在这里。

总线是用于 CPU 和内存以及其他设备之间的通信，总线可分为 3 种：

• 地址总线，用于指定 CPU 将要操作的内存地址；
• 数据总线，用于读写内存的数据；
• 控制总线，用于发送和接收信号，比如中断、设备复位等信号，CPU 收到信号后自然进行响应，这时也需要控制总线；

当 CPU 要读写内存数据的时候，一般需要通过下面这三个总线：

• 首先要通过「地址总线」来指定内存的地址；
• 然后通过「控制总线」控制是读或写命令；
• 最后通过「数据总线」来传输数据；

输入设备向计算机输入数据，计算机经过计算后，把数据输出给输出设备。

如果输入设备是键盘，按下按键时是需要和 CPU 进行交互的，这时就需要用到控制总线了。

知道了基本的程序执行过程后，接下来用 a = 1 + 2 的作为例子，进一步分析该程序在冯诺伊曼模型的执行过程。

CPU 是不认识 a = 1 + 2 这个字符串，这些字符串只是方便我们程序员认识，要想这段程序能跑起来，
还需要把整个程序翻译成 汇编语言 的程序，这个过程称为编译成汇编代码。

针对汇编代码，我们还需要用汇编器翻译成机器码，这些机器码由 0 和 1 组成的机器语言，
这一条条机器码，就是一条条的 计算机指令，这个才是 CPU 能够真正认识的东西。

下面来看看 a = 1 + 2 在 32 位 CPU 的执行过程。

程序编译过程中，编译器通过分析代码，发现 1 和 2 是数据，于是程序运行时，内存会有个
专门的区域来存放这些数据，这个区域就是「数据段」。如下图，数据 1 和 2 的区域位置：

• 数据 1 被存放到 0x200 位置；
• 数据 2 被存放到 0x204 位置；

注意，数据和指令是分开区域存放的，存放指令区域的地方称为「正文段」。

编译器会把 a = 1 + 2 翻译成 4 条指令，存放到正文段中。如图，这 4 条指令被存放到了 0x100 ~ 0x10c 的区域中：

• 0x100 的内容是 load 指令将 0x200 地址中的数据 1 装入到寄存器 R0；
• 0x104 的内容是 load 指令将 0x204 地址中的数据 2 装入到寄存器 R1；
• 0x108 的内容是 add 指令将寄存器 R0 和 R1 的数据相加，并把结果存放到寄存器 R2；
• 0x10c 的内容是 store 指令将寄存器 R2 中的数据存回数据段中的 0x208 地址中，这个地址也就是变量 a 内存中的地址；

编译完成后，具体执行程序的时候，程序计数器会被设置为 0x100 地址，然后依次执行这 4 条指令。

上面的例子中，由于是在 32 位 CPU 执行的，因此一条指令是占 32 位大小，所以你会发现每条指令间隔 4 个字节。

而数据的大小是根据你在程序中指定的变量类型，比如 int 类型的数据则占 4 个字节，char 类型的数据则占 1 个字节。

上面的例子中，图中指令的内容我写的是简易的汇编代码，目的是为了方便理解指令的具体内容，事实上指令
的内容是一串二进制数字的机器码，每条指令都有对应的机器码，CPU 通过解析机器码来知道指令的内容。

不同的 CPU 有不同的指令集，也就是对应着不同的汇编语言和不同的机器码，接下来选用最简单的 MIPS 指集，
来看看机器码是如何生成的，这样也能明白二进制的机器码的具体含义。

MIPS 的指令是一个 32 位的整数，高 6 位代表着操作码，表示这条指令是一条什么样的指令，
剩下的 26 位不同指令类型所表示的内容也就不相同，主要有三种类型 R、I 和 J。

一起具体看看这三种类型的含义：

• R 指令，用在算术和逻辑操作，里面有读取和写入数据的寄存器地址。如果是逻辑位移操作，后面还有位移操作的「位移量」，
  而最后的「功能码」则是再前面的操作码不够的时候，扩展操作码来表示对应的具体指令的；
• I 指令，用在数据传输、条件分支等。这个类型的指令，就没有了位移量和功能码，也没有了第三个寄存器，
  而是把这三部分直接合并成了一个地址值或一个常数；
• J 指令，用在跳转，高 6 位之外的 26 位都是一个跳转后的地址；

接下来，我们把前面例子的这条指令：「add 指令将寄存器 R0 和 R1 的数据相加，并把结果放入到 R2」，翻译成机器码。

加和运算 add 指令是属于 R 指令类型：

• add 对应的 MIPS 指令里操作码是 000000，以及最末尾的功能码是 100000，
  这些数值都是固定的，查一下 MIPS 指令集的手册就能知道的；
• rs 代表第一个寄存器 R0 的编号，即 00000；
• rt 代表第二个寄存器 R1 的编号，即 00001；
• rd 代表目标的临时寄存器 R2 的编号，即 00010；
• 因为不是位移操作，所以位移量是 00000

把上面这些数字拼在一起就是一条 32 位的 MIPS 加法指令了，那么用 16 进制表示的机器码则是 0x00011020。

编译器在编译程序的时候，会构造指令，这个过程叫做指令的编码。CPU 执行程序的时候，就会解析指令，这个过程叫作指令的解码。

现代大多数 CPU 都使用来流水线的方式来执行指令，所谓的流水线就是把一个任务拆分成多个小任务，
于是一条指令通常分为 4 个阶段，称为 4 级流水线，如下图：

四个阶段的具体含义：

• CPU 通过程序计数器读取对应内存地址的指令，这个部分称为 Fetch（取得指令）；
• CPU 对指令进行解码，这个部分称为 Decode（指令译码）；
• CPU 执行指令，这个部分称为 Execution（执行指令）；
• CPU 将计算结果存回寄存器或者将寄存器的值存入内存，这个部分称为 Store（数据回写）；

上面这 4 个阶段，我们称为 指令周期（Instrution Cycle），CPU 的工作就是一个周期接着一个周期，周而复始。

事实上，不同的阶段其实是由计算机中的不同组件完成的：

• 取指令的阶段，我们的指令是存放在 存储器 里的，实际上，通过程序计数器和指令寄存器取出指令的过程，是由 控制器 操作的；
• 指令的译码过程，也是由 控制器 进行的；
• 指令执行的过程，无论是进行算术操作、逻辑操作，还是进行数据传输、条件分支操作，都是由 算术逻辑单元 操作的，
  也就是由 运算器 处理的。但是如果是一个简单的无条件地址跳转，则是直接在 控制器 里面完成的，不需要用到运算器。

指令从功能角度划分，可以分为 5 大类：

• 数据传输类型的指令，比如 store/load 是寄存器与内存间数据传输的指令，mov 是将一个内存地址的数据移动到另一个内存地址的指令；
• 运算类型的指令，比如加减乘除、位运算、比较大小等等，它们最多只能处理两个寄存器中的数据；
• 跳转类型的指令，通过修改程序计数器的值来达到跳转执行指令的过程，比如编程中常见的 if-else、switch-case、函数调用等。
• 信号类型的指令，比如发生中断的指令 trap；
• 闲置类型的指令，比如指令 nop，执行后 CPU 会空转一个周期；

介绍

如何让程序跑的更快？

我们想象中一个场景，大学期末准备考试了，你前去图书馆临时抱佛脚。那么，在看书的时候，我们的大脑会思考问题，
也会记忆知识点，另外我们通常也会把常用的书放在自己的桌子上，当我们要找一本不常用的书，则会去图书馆的书架找。

就是这么一个小小的场景，已经把计算机的存储结构基本都涵盖了。

我们可以把 CPU 比喻成我们的大脑，大脑正在思考的东西，就好比 CPU 中的 寄存器，处理速度是最快的，
但是能存储的数据也是最少的，毕竟我们也不能一下同时思考太多的事情，除非你练过。

我们大脑中的记忆，就好比 CPU Cache，中文称为 CPU 高速缓存，处理速度相比寄存器慢了一点，但是能存储的数据也稍微多了一些。

CPU Cache 通常会分为 L1、L2、L3 三层，其中 L1 Cache 通常分成「数据缓存」和「指令缓存」，L1 是距离 CPU 最近的，
因此它比 L2、L3 的读写速度都快、存储空间都小。我们大脑中短期记忆，就好比 L1 Cache，而长期记忆就好比 L2/L3 Cache。

寄存器和 CPU Cache 都是在 CPU 内部，跟 CPU 挨着很近，因此它们的读写速度都相当的快，但是能存储的数据很少，毕竟 CPU 就这么丁点大。

知道 CPU 内部的存储器的层次分布，我们放眼看看 CPU 外部的存储器。

当我们大脑记忆中没有资料的时候，可以从书桌或书架上拿书来阅读，那我们桌子上的书，就好比 内存，我们虽然可以一伸手就可以拿到，但读写速度
肯定远慢于寄存器，那图书馆书架上的书，就好比 硬盘，能存储的数据非常大，但是读写速度相比内存差好几个数量级，更别说跟寄存器的差距了。

我们从图书馆书架取书，把书放到桌子上，再阅读书，我们大脑就会记忆知识点，然后再经过大脑思考，这一系列过程
相当于，数据从硬盘加载到内存，再从内存加载到 CPU 的寄存器和 Cache 中，然后再通过 CPU 进行处理和计算。

对于存储器，它的速度越快、能耗会越高、而且材料的成本也是越贵的，以至于速度快的存储器的容量都比较小。

CPU 里的寄存器和 Cache，是整个计算机存储器中价格最贵的，虽然存储空间很小，但是读写速度是极快的，
而相对比较便宜的内存和硬盘，速度肯定比不上 CPU 内部的存储器，但是能弥补存储空间的不足。

存储器通常可以分为这么几个级别：

• 寄存器；
• CPU Cache；
• L1-Cache；
• L2-Cache；
• L3-Cahce；
• 内存；
• SSD/HDD 硬盘

最靠近 CPU 的控制单元和逻辑计算单元的存储器，就是寄存器了，它使用的材料速度也是最快的，因此价格也是最贵的，那么数量不能很多。

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

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

寄存器的访问速度非常快，一般要求在半个 CPU 时钟周期内完成读写，CPU 时钟周期跟 CPU 主频息息相关，
比如 2 GHz 主频的 CPU，那么它的时钟周期就是 1/2G，也就是 0.5ns（纳秒）。

CPU 处理一条指令的时候，除了读写寄存器，还需要解码指令、控制指令执行和计算。
如果寄存器的速度太慢，则会拉长指令的处理周期，从而给用户电脑「很慢」的感觉。

CPU Cache 用的是一种叫 SRAM（Static Random-Access Memory，静态随机存储器） 的芯片。

SRAM 之所以叫「静态」存储器，是因为只要有电，数据就可以保持存在，而一旦断电，数据就会丢失了。

在 SRAM 里面，一个 bit 的数据，通常需要 6 个晶体管，所以 SRAM 的存储密度不高，同样的物理空间下，
能存储的数据是有限的，不过也因为 SRAM 的电路简单，所以访问速度非常快。

CPU 的高速缓存，通常可以分为 L1、L2、L3 这样的三层高速缓存，也称为一级缓存、二级缓存、三级缓存。

L1 高速缓存

L2 高速缓存

L3 高速缓存

内存用的芯片和 CPU Cache 有所不同，它使用的是一种叫作 DRAM （Dynamic Random Access Memory，动态随机存取存储器） 的芯片。

相比 SRAM，DRAM 的密度更高，功耗更低，有更大的容量，而且造价比 SRAM 芯片便宜很多。

DRAM 存储一个 bit 数据，只需要一个晶体管和一个电容就能存储，但是因为数据会被存储在电容里，电容会不断漏电，所以需要「定时刷新」
电容，才能保证数据不会被丢失，这就是 DRAM 之所以被称为「动态」存储器的原因，只有不断刷新，数据才能被存储起来。

DRAM 的数据访问电路和刷新电路都比 SRAM 更复杂，所以访问的速度会更慢，内存速度大概在 200~300 个 时钟周期之间。

SSD（Solid-state disk） 就是我们常说的固体硬盘，结构和内存类似，但是它相比内存的优点是断电后数据
还是存在的，而内存、寄存器、高速缓存断电后数据都会丢失。内存的读写速度比 SSD 大概快 10~1000 倍。

当然，还有一款传统的硬盘，也就是机械硬盘（Hard Disk Drive, HDD），它是通过物理
读写的方式来访问数据的，因此它访问速度是非常慢的，它的速度比内存慢 10W 倍左右。

由于 SSD 的价格快接近机械硬盘了，因此机械硬盘已经逐渐被 SSD 替代了。

我们知道 CPU 访问内存的速度，比访问 CPU Cache 的速度慢了 100 多倍，所以如果 CPU 所要操作的数据在 CPU Cache 中的话，这样将会
带来很大的性能提升。访问的数据在 CPU Cache 中的话，意味着 缓存命中，缓存命中率越高的话，代码的性能就会越好，CPU 也就跑的越快。

于是，「如何写出让 CPU 跑得更快的代码？」这个问题，可以改成「如何写出 CPU 缓存命中率高的代码？」。

在前面我也提到， L1 Cache 通常分为「数据缓存」和「指令缓存」，这是因为 CPU 会分别处理数据和指令，
比如 1+1=2 这个运算，+ 就是指令，会被放在「指令缓存」中，而输入数字 1 则会被放在「数据缓存」里。

因此，我们要分开来看「数据缓存」和「指令缓存」的缓存命中率。

假设要遍历二维数组，有以下两种形式，虽然代码执行结果是一样，但你觉得哪种形式效率最高呢？为什么高呢？

经过测试，形式一 array[i][j] 执行时间比形式二 array[j][i] 快好几倍。

之所以有这么大的差距，是因为二维数组 array 所占用的内存是连续的，比如长度 N 的值是 2 的话，那么内存中的数组元素的布局顺序是这样的：

形式一用 array[i][j] 访问数组元素的顺序，正是和内存中数组元素存放的顺序一致。当 CPU 访问 array[0][0] 时，由于该数据
不在 Cache 中，于是会「顺序」把跟随其后的 3 个元素从内存中加载到 CPU Cache，这样当 CPU 访问后面的 3 个数组元素时，
就能在 CPU Cache 中成功地找到数据，这意味着缓存命中率很高，缓存命中的数据不需要访问内存，这便大大提高了代码的性能。

而如果用形式二的 array[j][i] 来访问，则访问的顺序就是：

你可以看到，访问的方式跳跃式的，而不是顺序的，那么如果 N 的数值很大，那么操作 array[j][i] 时，是没办法把 array[j+1][i] 
也读入到 CPU Cache 中的，既然 array[j+1][i] 没有读取到 CPU Cache，那么就需要从内存读取该数据元素了。很明显，这种
不连续性、跳跃式访问数据元素的方式，可能不能充分利用到了 CPU Cache 的特性，从而代码的性能不高。

那访问 array[0][0] 元素时，CPU 具体会一次从内存中加载多少元素到 CPU Cache 呢？这个问题，在前面我们也提到过，这跟 CPU Cache Line 
有关，它表示 CPU Cache 一次性能加载数据的大小，可以在 Linux 里通过 coherency_line_size 配置查看 它的大小，通常是 64 个字节。

也就是说，当 CPU 访问内存数据时，如果数据不在 CPU Cache 中，则会一次性会连续加载 64 字节大小的数据到 CPU Cache，
那么当访问 array[0][0] 时，由于该元素不足 64 字节，于是就会往后顺序读取 array[0][0]~array[0][15] 到 CPU Cache 中。
顺序访问的 array[i][j] 因为利用了这一特点，所以就会比跳跃式访问的 array[j][i] 要快。

因此，遇到这种遍历数组的情况时，按照内存布局顺序访问，将可以有效的利用 CPU Cache 带来的好处，这样我们代码的性能就会得到很大的提升，

提升数据的缓存命中率的方式，是按照内存布局顺序访问，那针对指令的缓存该如何提升呢？

我们以一个例子来看看，有一个元素为 0 到 100 之间随机数字组成的一维数组：

接下来，对这个数组做两个操作：

• 第一个操作，循环遍历数组，把小于 50 的数组元素置为 0；
• 第二个操作，将数组排序；

那么问题来了，你觉得先遍历再排序速度快，还是先排序再遍历速度快呢？

在回答这个问题之前，我们先了解 CPU 的 分支预测器。对于 if 条件语句，意味着此时至少可以选择跳转到两段不同的指令执行，
也就是 if 还是 else 中的指令。那么，如果分支预测可以预测到接下来要执行 if 里的指令，还是 else 指令的话，就可以「提前」
把这些指令放在指令缓存中，这样 CPU 可以直接从 Cache 读取到指令，于是执行速度就会很快。

当数组中的元素是随机的，分支预测就无法有效工作，而当数组元素都是是顺序的，
分支预测器会动态地根据历史命中数据对未来进行预测，这样命中率就会很高。

因此，先排序再遍历速度会更快，这是因为排序之后，数字是从小到大的，那么前几次循环命中 if < 50 的次数会比较多，
于是分支预测就会缓存 if 里的 array[i] = 0 指令到 Cache 中，后续 CPU 执行该指令就只需要从 Cache 读取就好了。

如果你肯定代码中的 if 中的表达式判断为 true 的概率比较高，我们可以使用显示分支预测工具，比如在 C/C++ 语言中编译器提供
了 likely 和 unlikely 这两种宏，如果 if 条件为 ture 的概率大，则可以用 likely 宏把 if 里的表达式包裹起来，反之用 unlikely 宏。

实际上，CPU 自身的动态分支预测已经是比较准的了，所以只有当非常确信 CPU 预测的不准，且能够知道实际的概率情况时，才建议使用这两种宏。

在单核 CPU，虽然只能执行一个线程，但是操作系统给每个线程分配了一个时间片，时间片用完了，
就调度下一个线程，于是各个线程就按时间片交替地占用 CPU，从宏观上看起来各个线程同时在执行。

而现代 CPU 都是多核心的，线程可能在不同 CPU 核心来回切换执行，这对 CPU Cache 不是有利的，虽然 L3 Cache 是多核心之间共享的，
但是 L1 和 L2 Cache 都是每个核心独有的，如果一个线程在不同核心来回切换，各个核心的缓存命中率就会受到影响，相反如果线程都在
同一个核心上执行，那么其数据的 L1 和 L2 Cache 的缓存命中率可以得到有效提高，缓存命中率高就意味着 CPU 可以减少访问内存的频率。

当有多个同时执行「计算密集型」的线程，为了防止因为切换到不同的核心，而导致缓存命中率下降的问题，
我们可以把 线程绑定在某一个 CPU 核心上，这样性能可以得到非常可观的提升。

在 Linux 上提供了 sched_setaffinity 方法，来实现将线程绑定到某个 CPU 核心这一功能。

随着时间的推移，CPU 和内存的访问性能相差越来越大，于是就在 CPU 内部嵌入了 CPU Cache（高速缓存），
CPU Cache 离 CPU 核心相当近，因此它的访问速度是很快的，于是它 充当了 CPU 与内存之间的缓存角色。

CPU Cache 通常分为三级缓存：L1 Cache、L2 Cache、L3 Cache，级别越低的离 CPU 核心越近，访问速度也快，但是存储
容量相对就会越小。其中，在多核心的 CPU 里，每个核心都有各自的 L1/L2 Cache，而 L3 Cache 是所有核心共享使用的。

我们先简单了解下 CPU Cache 的结构，CPU Cache 是由很多个 Cache Line 组成的，CPU Line 是 CPU 从内存读取
数据的基本单位，而 CPU Line 是由各种标志（Tag）+ 数据块（Data Block）组成，你可以在下图清晰的看到：

我们当然期望 CPU 读取数据的时候，都是尽可能地从 CPU Cache 中读取，而不是每一次都要从内存中获取数据。
所以，身为程序员，我们要尽可能写出缓存命中率高的代码，这样就有效提高程序的性能。

事实上，数据不光是只有读操作，还有写操作，那么如果数据写入 Cache 之后，内存与 Cache 相对应的数据将会不同，
这种情况下 Cache 和内存数据都不一致了，于是我们肯定是要把 Cache 中的数据同步到内存里的。

问题来了，那在什么时机才把 Cache 中的数据写回到内存呢？为了应对这个问题，下面介绍两种针对写入数据的方法：

• 写直达（Write Through）
• 写回（Write Back）

保持内存与 Cache 一致性最简单的方式是，把数据同时写入内存和 Cache 中，这种方法称为 写直达（Write Through）。

在这个方法里，写入前会先判断数据是否已经在 CPU Cache 里面了：

• 如果数据已经在 Cache 里面，先将数据更新到 Cache 里面，再写入到内存里面；
• 如果数据没有在 Cache 里面，就直接把数据更新到内存里面。

写直达法很直观，也很简单，但是问题明显，无论数据在不在 Cache 里面，每次写操作都会写回到内存，
这样写操作将会花费大量的时间，无疑 性能会受到很大的影响。

既然写直达由于每次写操作都会把数据写回到内存，而导致影响性能，于是为了要减少数据写回内存的频率，就出现了 写回（Write Back）的方法。

在写回机制中，当发生写操作时，新的数据仅仅被写入 Cache Block 里，只有当修改过的 Cache Block「被替换」
时才需要写到内存中，减少了数据写回内存的频率，这样便可以提高系统的性能。

那具体如何做到的呢？下面来详细说一下：

• 如果当发生写操作时，数据已经在 CPU Cache 里，则把数据更新到 CPU Cache 里，同时标记 CPU Cache 里的这个 Cache Block 为脏（Dirty）的，
  这个脏的标记代表这个时候，我们 CPU Cache 里面的这个 Cache Block 的数据和内存是不一致的，这种情况是不用把数据写到内存里的；
  
  
• 如果当发生写操作时，数据所对应的 Cache Block 里存放的是「别的内存地址的数据」，就要检查这个 Cache Block 里的数据有没有被标记为脏的：

     （1）如果是脏的话，我们就要把这个 Cache Block 里的数据写回到内存，然后再把当前要写入的数据，先从内存读入
              到 Cache Block 里（注意，这一步不是没用的，具体为什么要这一步，可以看这个「回答 (opens new window)」），
              然后再把当前要写入的数据写入到 Cache Block，最后也把它标记为脏的；
     （2）如果不是脏的话，把当前要写入的数据先从内存读入到 Cache Block 里，接着将数据写入到这个 Cache Block 里，
              然后再把这个 Cache Block 标记为脏的就好了。

可以发现写回这个方法，在把数据写入到 Cache 的时候，只有在缓存不命中，同时数据对应的 Cache 中的 Cache Block 为脏标记的情况下，
才会将数据写到内存中，而在缓存命中的情况下，则在写入后 Cache 后，只需把该数据对应的 Cache Block 标记为脏即可，而不用写到内存里。

这样的好处是，如果我们大量的操作都能够命中缓存，那么大部分时间里 CPU 都不需要读写内存，自然性能相比写直达会高很多。

为什么缓存没命中时，还要定位 Cache Block？这是因为此时是要判断数据即将写入到 Cache block 里的位置，
是否被「其他数据」占用了此位置，如果这个「其他数据」是脏数据，那么就要帮忙把它写回到内存。

CPU 缓存与内存使用「写回」机制的流程图如下，左半部分就是读操作的流程，右半部分就是写操作的流程，也就是我们上面讲的内容。

先来认识 CPU 的架构，只有理解了 CPU 的 架构，才能更好地理解 CPU 是如何读写数据的，对于现代 CPU 的架构图如下：

可以看到，一个 CPU 里通常会有多个 CPU 核心，比如上图中的 1 号和 2 号 CPU 核心，并且每个 CPU 核心都有自己的 L1 Cache 和 L2 Cache，
而 L1 Cache 通常分为 dCache（数据缓存） 和 iCache（指令缓存），L3 Cache 则是多个核心共享的，这就是 CPU 典型的缓存层次。

上面提到的都是 CPU 内部的 Cache，放眼外部的话，还会有内存和硬盘，这些存储设备共同构成了金字塔存储层次。如下图所示：

从上图也可以看到，从上往下，存储设备的容量会越大，而访问速度会越慢。至于每个存储设备的访问延时，你可以看下图的表格：

你可以看到， CPU 访问 L1 Cache 速度比访问内存快 100 倍，这就是为什么 CPU 里会有 L1~L3 Cache 的原因，
目的就是把 Cache 作为 CPU 与内存之间的缓存层，以减少对内存的访问频率。

CPU 从内存中读取数据到 Cache 的时候，并不是一个字节一个字节读取，而是一块一块的方式来读取数据的，
这一块一块的数据被称为 CPU Cache Line（缓存块），所以 CPU Cache Line 是 CPU 从内存读取数据到 Cache 的单位。

至于 CPU Cache Line 大小，在 Linux 系统可以用下面的方式查看到，你可以看我服务器的 
L1 Cache Line 大小是 64 字节，也就意味着 L1 Cache 一次载入数据的大小是 64 字节。

那么对数组的加载， CPU 就会加载数组里面连续的多个数据到 Cache 里，因此我们应该按照物理内存地址分布的顺序去访问元素，
这样访问数组元素的时候，Cache 命中率就会很高，于是就能减少从内存读取数据的频率， 从而可提高程序的性能。

但是，在我们不使用数组，而是使用单独的变量的时候，则会有 Cache 伪共享的问题，Cache 伪共享问题上是一个性能杀手，我们应该要规避它。

接下来，就来看看 Cache 伪共享是什么？又如何避免这个问题？

现在假设有一个双核心的 CPU，这两个 CPU 核心并行运行着两个不同的线程，它们同时从内存中读取两个不同的数据，分别是类型为 long 的变量 A 和 B，这个两个数据的地址在物理内存上是连续的，如果 Cahce Line 的大小是 64 字节，并且变量 A 在 Cahce Line 的开头位置，那么这两个数据是位于同一个 
Cache Line 中，又因为 CPU Cache Line 是 CPU 从内存读取数据到 Cache 的单位，所以这两个数据会被同时读入到了两个 CPU 核心中各自 Cache 中。

我们来思考一个问题，如果这两个不同核心的线程分别修改不同的数据，比如 1 号 CPU 核心
的线程只修改了 变量 A，或 2 号 CPU 核心的线程的线程只修改了变量 B，会发生什么呢？

现在我们结合保证多核缓存一致的 MESI 协议，来说明这一整个的过程。

①. 最开始变量 A 和 B 都还不在 Cache 里面，假设 1 号核心绑定了线程 A，2 号核心绑定了线程 B，线程 A 只会读写变量 A，线程 B 只会读写变量 B。

②. 1 号核心读取变量 A，由于 CPU 从内存读取数据到 Cache 的单位是 Cache Line，也正好变量 A 和 变量 B 的数据
归属于同一个 Cache Line，所以 A 和 B 的数据都会被加载到 Cache，并将此 Cache Line 标记为「独占」状态。

③. 接着，2 号核心开始从内存里读取变量 B，同样的也是读取 Cache Line 大小的数据到 Cache 中，此 Cache Line 
中的数据也包含了变量 A 和 变量 B，此时 1 号和 2 号核心的 Cache Line 状态变为「共享」状态。

④. 1 号核心需要修改变量 A，发现此 Cache Line 的状态是「共享」状态，所以先需要通过总线发送消息给 2 号核心，通知 2 号核心|
把 Cache 中对应的 Cache Line 标记为「已失效」状态，然后 1 号核心对应的 Cache Line 状态变成「已修改」状态，并且修改变量 A。

⑤. 之后，2 号核心需要修改变量 B，此时 2 号核心的 Cache 中对应的 Cache Line 是已失效状态，另外由于 1 号核心的 Cache 
也有此相同的数据，且状态为「已修改」状态，所以要先把 1 号核心的 Cache 对应的 Cache Line 写回到内存，然后 2 号核心再
从内存读取 Cache Line 大小的数据到 Cache 中，最后把变量 B 修改到 2 号核心的 Cache 中，并将状态标记为「已修改」状态。

所以，可以发现 如果 1 号和 2 号 CPU 核心这样持续交替的分别修改变量 A 和 B，就会 重复 ④ 和 ⑤ 这两个步骤，
Cache 并没有起到缓存的效果，虽然 变量 A 和 B 之间其实并没有任何的关系，但是因为同时归属于一个 Cache Line ，
这个 Cache Line 中的任意数据被修改后，都会相互影响，从而出现 ④ 和 ⑤ 这两个步骤。

因此，这种因为 多个线程同时读写同一个 Cache Line 的不同变量时，而导致 CPU Cache 失效的现象称为伪共享（False Sharing）。

因此，对于多个线程共享的热点数据，即经常会修改的数据，应该避免这些数据刚好在同一个 Cache Line 中，否则就会出现为伪共享的问题。

接下来，看看在实际项目中是用什么方式来避免伪共享的问题的。

在 Linux 内核中存在 __cacheline_aligned_in_smp 宏定义，是用于解决伪共享的问题。

从上面的宏定义，我们可以看到：

• 如果在多核（MP）系统里，该宏定义是 __cacheline_aligned，也就是 Cache Line 的大小；
• 而如果在单核系统里，该宏定义是空的；

因此，针对在同一个 Cache Line 中的共享的数据，如果在多核之间竞争比较严重，为了
防止伪共享现象的发生，可以采用上面的宏定义使得变量在 Cache Line 里是对齐的。

举个例子，有下面这个结构体：

结构体里的两个成员变量 a 和 b 在物理内存地址上是连续的，于是它们可能会位于同一个 Cache Line 中，如下图：

所以，为了防止前面提到的 Cache 伪共享问题，我们可以使用上面介绍的宏定义，将 b 的地址设置为 Cache Line 对齐地址，如下：

这样 a 和 b 变量就不会在同一个 Cache Line 中了，如下图：

所以，避免 Cache 伪共享实际上是用空间换时间的思想，浪费一部分 Cache 空间，从而换来性能的提升。

我们再来看一个应用层面的规避方案，有一个 Java 并发框架 Disruptor 使用「字节填充 + 继承」的方式，来避免伪共享的问题。

Disruptor 中有一个 RingBuffer 类会经常被多个线程使用，代码如下：

你可能会觉得 RingBufferPad 类里 7 个 long 类型的名字很奇怪，但事实上，它们虽然看起来毫无作用，但却对性能的提升起到了至关重要的作用。

我们都知道，CPU Cache 从内存读取数据的单位是 CPU Cache Line，一般 64 位 CPU 的 CPU Cache Line 
的大小是 64 个字节，一个 long 类型的数据是 8 个字节，所以 CPU 一下会加载 8 个 long 类型的数据。

根据 JVM 对象继承关系中父类成员和子类成员，内存地址是连续排列布局的，因此 RingBufferPad 中的 7 个 long 类型数据作为 Cache Line 前置
填充，而 RingBuffer 中的 7 个 long 类型数据则作为 Cache Line 后置填充，这 14 个 long 变量没有任何实际用途，更不会对它们进行读写操作。

另外，RingBufferFelds 里面定义的这些变量都是 final 修饰的，意味着第一次加载之后不会再修改， 又 由于「前后」
各填充了 7 个不会被读写的 long 类型变量，所以无论怎么加载 Cache Line，这整个 Cache Line 里都没有会发生更新
操作的数据，于是只要数据被频繁地读取访问，就自然没有数据被换出 Cache 的可能，也因此不会产生伪共享的问题。

了解完 CPU 读取数据的过程后，我们再来看看 CPU 是根据什么来选择当前要执行的线程。

在 Linux 内核中，进程和线程都是用 task_struct 结构体表示的，区别在于线程的 task_struct 结构体里部分资源是共享了
进程已创建的资源，比如内存地址空间、代码段、文件描述符等，所以 Linux 中的线程也被称为轻量级进程，因为线程的 
task_struct 相比进程的 task_struct 承载的 资源比较少，因此以「轻」得名。

一般来说，没有创建线程的进程，是只有单个执行流，它被称为是主线程。如果想让进程处理更多的事情，
可以创建多个线程分别去处理，但不管怎么样，它们对应到内核里都是 task_struct。

所以，Linux 内核里的调度器，调度的对象就是 task_struct，接下来我们就把这个数据结构统称为 任务。

在 Linux 系统中，根据任务的优先级以及响应要求，主要分为两种，其中优先级的数值越小，优先级越高：

• 实时任务，对系统的响应时间要求很高，也就是要尽可能快的执行实时任务，优先级在 0~99 范围内的就算实时任务；
• 普通任务，响应时间没有很高的要求，优先级在 100~139 范围内都是普通任务级别；

由于任务有优先级之分，Linux 系统为了保障高优先级的任务能够尽可能早的被执行，于是分为了这几种调度类，如下图：

Deadline 和 Realtime 这两个调度类，都是应用于 实时任务 的，这两个调度类的调度策略合起来共有这三种，它们的作用如下：

• SCHED_DEADLINE：是按照 deadline 进行调度的，距离当前时间点最近的 deadline 的任务会被优先调度；
• SCHED_FIFO：对于相同优先级的任务，按先来先服务的原则，但是优先级更高的任务，可以抢占低优先级的
  任务，也就是优先级高的可以「插队」；
• SCHED_RR：对于相同优先级的任务，轮流着运行，每个任务都有一定的时间片，当用完时间片的任务会被放到
  队列尾部，以保证相同优先级任务的公平性，但是高优先级的任务依然可以抢占低优先级的任务；

而 Fair 调度类是应用于普通任务，都是由 CFS 调度器管理的，分为两种调度策略：

• SCHED_NORMAL：普通任务使用的调度策略；
• SCHED_BATCH：后台任务的调度策略，不和终端进行交互，
  因此在不影响其他需要交互的任务，可以适当降低它的优先级。

我们平日里遇到的基本都是普通任务，对于普通任务来说，公平性最重要，在 Linux 里面，
实现了一个基于 CFS 的调度算法，也就是 完全公平调度（Completely Fair Scheduling）。

这个算法的理念是想让分配给每个任务的 CPU 时间是一样，于是它为每个任务安排一个虚拟运行时间 vruntime，
如果一个任务在运行，其运行的越久，该任务的 vruntime 自然就会越大，而没有被运行的任务，vruntime 不变。

那么，在 CFS 算法调度的时候，会优先选择 vruntime 少的任务，以保证每个任务的公平性。

这就好比，让你把一桶的奶茶平均分到 10 杯奶茶杯里，你看着哪杯奶茶少，就多倒一些；哪个多了，
就先不倒，这样经过多轮操作，虽然不能保证每杯奶茶完全一样多，但至少是公平的。

当然，上面提到的例子没有考虑到优先级的问题，虽然是普通任务，但是普通任务之间还是有优先级区分的，所以在计算
虚拟运行时间 vruntime 还要考虑普通任务的 权重值，注意权重值并不是优先级的值，内核中会有一个 nice 级别与权重值
的转换表，nice 级别越低的权重值就越大，至于 nice 值是什么，我们后面会提到。 于是就有了以下这个公式：

你可以不用管 NICE_0_LOAD 是什么，你就认为它是一个常量。那么在「同样的实际运行时间」里，高权重任务
的 vruntime 比低权重任务的 vruntime 少，你可能会奇怪为什么是少？你还记得 CFS 调度吗，它是会优先选择 
vruntime 少的任务进行调度，所以高权重的任务会被优先调度，于是高权重的获得的实际运行时间自然就多了。

一个系统通常都会运行着很多任务，多任务的数量基本都是远超 CPU 核心数量，因此这时候就需要 排队。

事实上，每个 CPU 都有自己的 运行队列（Run Queue, rq），用于描述在此 CPU 上所运行的所有进程，其
队列包含三个运行队列，Deadline 运行队列 dl_rq、实时任务运行队列 rt_rq 和 CFS 运行队列 cfs_rq，其中 
cfs_rq 是用红黑树来描述的，按 vruntime 大小来排序的，最左侧的叶子节点，就是下次会被调度的任务。

PS：下图中的 csf_rq 应该是 cfs_rq。

这几种调度类是有优先级的，优先级 如下：Deadline > Realtime > Fair，这意味着 Linux 选择下一个任务执行的时候，会按照此优先级顺序进行
选择，也就是说先从 dl_rq 里选择任务，然后从 rt_rq 里选择任务，最后从 cfs_rq 里选择任务。因此，实时任务总是会比普通任务优先被执行。

如果我们启动任务的时候，没有特意去指定优先级的话，默认情况下都是普通任务，普通任务的调度类是 Fair，由 
CFS 调度器来进行管理。CFS 调度器的目的是实现任务运行的公平性，也就是保障每个任务的运行的时间是差不多的。

如果你想让某个普通任务有更多的执行时间，可以调整任务的 nice 值，从而让优先级高一些的任务执行更多时间。nice 的
值能设置的范围是 -20～19， 值越低，表明优先级越高，因此 -20 是最高优先级，19 则是最低优先级，默认优先级是 0。

是不是觉得 nice 值的范围很诡异？事实上，nice 值并不是表示优先级，而是表示优先级的修正数值，它与优先级（priority）的关系是这样的：
priority(new) = priority(old) + nice。内核中，priority 的范围是 0~139，值越低，优先级越高，其中前面的 0~99 范围是提供给实时任务
使用的，而 nice 值是映射到 100~139，这个范围是提供给普通任务用的，因此 nice 值调整的是普通任务的优先级。

在前面我们提到了，权重值与 nice 值的关系的，nice 值越低，权重值就越大，计算出来的 vruntime 就会越少，
由于 CFS 算法调度 的时候，就会优先选择 vruntime 少的任务进行执行，所以 nice 值越低，任务的优先级就越高。

我们可以在启动任务的时候，可以指定 nice 的值，比如将 mysqld 以 -3 优先级：

如果想修改已经运行中的任务的优先级，则可以使用 renice 来调整 nice 值：

nice 调整的是普通任务的优先级，所以不管怎么缩小 nice 值，任务永远都是普通任务，如果某些任务
要求实时性比较高，那么你可以考虑改变任务的优先级以及调度策略，使得它变成实时任务，比如：

Linux 的开山始祖是来自一位名叫 Linus Torvalds 的芬兰小伙子，他在 1991 年用 C 语言写出了第一版的 Linux 操作系统，那年他 22 岁。

完成第一版 Linux 后，Linus Torvalds 就在网络上发布了 Linux 内核的源代码，每个人都可以免费下载和使用。

Linux 内核设计的理念主要有这几个点：

• MultiTask，多任务
• SMP，对称多处理
• ELF，可执行文件链接格式
• Monolithic Kernel，宏内核

MultiTask 的意思是 多任务，代表着 Linux 是一个多任务的操作系统。

多任务意味着可以有多个任务 同时 执行，这里的「同时」可以是 并发或并行：

• 对于单核 CPU 时，可以让每个任务执行一小段时间，时间到就切换另外一个任务，
  从宏观角度看，一段时间内执行了多个任务，这被称为并发。
• 对于多核 CPU 时，多个任务可以同时被不同核心的 CPU 同时执行，这被称为并行。

SMP 的意思是 对称多处理，代表着每个 CPU 的地位是相等的，对资源的使用权限也是相同的，
多个 CPU 共享同一个内存，每个 CPU 都可以访问完整的内存和硬件资源。

这个特点决定了 Linux 操作系统不会有某个 CPU 单独服务应用程序或内核程序，
而是每个程序都可以被分配到任意一个 CPU 上被执行。

ELF 的意思是 可执行文件链接格式，它是 Linux 操作系统中可执行文件的存储格式，你可以从下图看到它的结构：

ELF 把文件分成了一个个分段，每一个段都有自己的作用，具体每个段的作用这里我就不详细说明了，
感兴趣的同学可以去看《程序员的自我修养——链接、装载和库》这本书。

另外，ELF 文件有两种索引，Program header table 中记录了「运行时」所需的段，
而 Section header table 记录了二进制文件中各个「段的首地址」。

那 ELF 文件怎么生成的呢？

我们编写的代码，首先通过「编译器」编译成汇编代码，接着通过「汇编器」变成目标代码，也就是目标文件，
最后通过「链接器」把多个目标文件以及调用的各种函数库链接起来，形成一个可执行文件，也就是 ELF 文件。

那 ELF 文件是怎么被执行的呢？

执行 ELF 文件的时候，会通过「装载器」把 ELF 文件装载到内存里，CPU 读取内存中的指令和数据，于是程序就被执行起来了。

Monolithic Kernel 的意思是 宏内核，Linux 内核架构就是宏内核，意味着 Linux 的内核是一个完整的可执行程序，且拥有最高的权限。

宏内核的特征是系统内核的所有模块，比如进程调度、内存管理、文件系统、设备驱动等，都运行在内核态。

不过，Linux 也实现了动态加载内核模块的功能，例如大部分设备驱动是以可加载模块的形式存在的，
与内核其他模块解藕，让驱动开发和驱动加载更为方便、灵活。

与宏内核相反的是 微内核，微内核架构的内核只保留最基本的能力，比如进程调度、虚拟机内存、中断等，把一些应用放到了用户空间，比如驱动程序、
文件系统等。这样服务与服务之间是隔离的，单个服务出现故障或者完全攻击，也不会导致整个操作系统挂掉，提高了操作系统的稳定性和可靠性。

微内核内核功能少，可移植性高，相比宏内核有一点不好的地方在于，由于驱动程序不在内核中，而且驱动程序一般会频繁调用底层
能力的，于是驱动和硬件设备交互就需要频繁切换到内核态，这样会带来性能损耗。华为的鸿蒙操作系统的内核架构就是微内核。

还有一种内核叫 混合类型内核，它的架构有点像微内核，内核里面会有一个最小版本的内核，然后其他模块会在这个基础上搭建，然后
实现的时候会跟宏内核类似，也就是把整个内核做成一个完整的程序，大部分服务都在内核中，这就像是宏内核的方式包裹着一个微内核。

我们来看看这样一个例子。假设有 1G 的物理内存，用户执行了多个程序，其中：

• 游戏占用了 512MB 内存
• 浏览器占用了 128MB 内存
• 音乐占用了 256 MB 内存。

这个时候，如果我们关闭了浏览器，则空闲内存还有 1024 - 512 - 256 = 256MB。

如果这个 256MB 不是连续的，被分成了两段 128 MB 内存，这就会导致没有空间再打开一个 200MB 的程序。

内存分段会出现内存碎片吗？

内存碎片主要分为，内部内存碎片和外部内存碎片。

内存分段管理可以做到 段根据实际需求分配内存，所以有多少需求就分配多大的段，所以 不会出现内部内存碎片。

但是由于每个段的长度不固定，所以 多个段未必能恰好使用所有的内存空间，会产生了
多个不连续的小物理内存，导致新的程序无法被装载，所以 会出现外部内存碎片 的问题。

解决「外部内存碎片」的问题就是 内存交换。

可以把音乐程序占用的那 256MB 内存写到硬盘上，然后再从硬盘上读回来到内存里。不过再读回的时候，我们不能装载回原来的位置，
而是紧紧跟着那已经被占用了的 512MB 内存后面。这样就能空缺出连续的 256MB 空间，于是新的 200MB 程序就可以装载进来。

这个内存交换空间，在 Linux 系统里，也就是我们常看到的 Swap 空间，这块空间是从硬盘划分出来的，用于 内存与硬盘的空间交换。

对于多进程的系统来说，用分段的方式，外部内存碎片是很容易产生的，产生了外部内存碎片，那不得不重新 Swap 内存区域，这个过程会产生性能瓶颈。

因为硬盘的访问速度要比内存慢太多了，每一次内存交换，我们都需要把一大段连续的内存数据写到硬盘上。

所以，如果内存交换的时候，交换的是一个占内存空间很大的程序，这样整个机器都会显得卡顿。

为了解决内存分段的「外部内存碎片和内存交换效率低」的问题，就出现了内存分页。

分段的好处就是能产生连续的内存空间，但是会出现「外部内存碎片和内存交换的空间太大」的问题。

要解决这些问题，那么就要想出能少出现一些内存碎片的办法。另外，当需要进行内存交换的时候，让需要
交换写入或者从磁盘装载的数据更少一点，这样就可以解决问题了。这个办法，也就是 内存分页（Paging）。

分页是把整个虚拟和物理内存空间切成一段段固定尺寸的大小。这样一个连续并且
尺寸固定的内存空间，我们叫页（Page）。在 Linux 下，每一页的大小为 4KB。

虚拟地址与物理地址之间通过 页表 来映射，如下图：

页表是存储在内存里的，内存管理单元 （MMU）就做 将虚拟内存地址转换成物理地址 的工作。

而 当进程访问的虚拟地址在页表中查不到时，系统会产生一个 缺页异常，进入系统
内核空间分配物理内存、更新进程页表，最后再返回用户空间，恢复进程的运行。

分页是怎么解决分段的「外部内存碎片和内存交换效率低」的问题？

分页机制下，虚拟地址和物理地址是如何映射的？

简单的分页有什么缺陷吗？

要解决上面的问题，就需要采用一种叫作 多级页表（Multi-Level Page Table）的解决方案。

在前面我们知道了，对于单页表的实现方式，在 32 位和页大小 4KB 的环境下，一个进程的页表需要装下 100 
多万个「页表项」，并且每个页表项是占用 4 字节大小的，于是相当于每个页表需占用 4MB 大小的空间。

我们把这个 100 多万个「页表项」的单级页表再分页，将页表（一级页表）分为 1024 个页表（二级页表），
每个表（二级页表）中包含 1024 个「页表项」，形成二级分页。如下图所示：

你可能会问，分了二级表，映射 4GB 地址空间就需要 4KB（一级页表）+ 4MB（二级页表）的内存，这样占用空间不是更大了吗？

当然如果 4GB 的虚拟地址全部都映射到了物理内存上的话，二级分页占用空间确实是更大了，但是，我们往往不会为一个进程分配那么多内存。

其实我们应该换个角度来看问题，还记得计算机组成原理里面无处不在的 局部性原理 么？

每个进程都有 4GB 的虚拟地址空间，而显然对于大多数程序来说，其使用到的空间远未达到 4GB，因为会存在部分对应的页表项都是空的，根本没有分配，对于已分配的页表项，如果存在最近一定时间未访问的页表，在物理内存紧张的情况下，操作系统会将页面换出到硬盘，也就是说不会占用物理内存。

如果使用了二级分页，一级页表就可以覆盖整个 4GB 虚拟地址空间，但 如果某个一级页表的页表项没有被用到，也就不需要创建这个页表项
对应的二级页表了，即可以在需要时才创建二级页表。做个简单的计算，假设只有 20% 的一级页表项被用到了，那么 页表占用的内存空间 就
只有 4KB（一级页表） + 20% * 4MB（二级页表）= 0.804MB，这对比单级页表的 4MB 是不是一个巨大的节约？

那么为什么不分级的页表就做不到这样节约内存呢？

我们从页表的性质来看，保存在内存中的页表承担的职责是将虚拟地址翻译成物理地址。假如虚拟地址在页表中找不到对应的页表项，
计算机系统就不能工作了。所以 页表一定要覆盖全部虚拟地址空间，不分级的页表就需要有 100 多万个页表项来映射，而二级分页则
只需要 1024 个页表项（此时一级页表覆盖到了全部虚拟地址空间，二级页表在需要时创建）。

我们把二级分页再推广到多级页表，就会发现页表占用的内存空间更少了，这一切都要归功于对局部性原理的充分应用。

对于 64 位的系统，两级分页肯定不够了，就变成了四级目录，分别是：

• 全局页目录项 PGD（Page Global Directory）；
• 上层页目录项 PUD（Page Upper Directory）；
• 中间页目录项 PMD（Page Middle Directory）；
• 页表项 PTE（Page Table Entry）；

多级页表虽然解决了空间上的问题，但是虚拟地址到物理地址的转换就多了几道转换的工序，
这显然就降低了这俩地址转换的速度，也就是带来了时间上的开销。

程序是有局部性的，即在一段时间内，整个程序的执行仅限于程序中的某一部分。
相应地，执行所访问的存储空间也局限于某个内存区域。

我们就可以利用这一特性，把最常访问的几个页表项存储到访问速度更快的硬件，于是计算机科学家们就在 CPU 芯片中，加入了一个专门存放
程序最常访问的页表项的 Cache，这个 Cache 就是 TLB（Translation Lookaside Buffer） ，通常称为 页表缓存、转址旁路缓存、快表 等。

在 CPU 芯片里面，封装了内存管理单元 MMU（Memory Management Unit）芯片，它用来完成地址转换和 TLB 的访问与交互。

有了 TLB 后，那么 CPU 在寻址时，会先查 TLB，如果没找到，才会继续查常规的页表。

TLB 的命中率其实是很高的，因为程序最常访问的页就那么几个。

早期 Intel 的处理器从 80286 开始使用的是段式内存管理。但是很快发现，光有段式内存管理而没有页式内存管理是不够的，
这会使它的 X86 系列会失去市场的竞争力。因此，在不久以后的 80386 中就实现了页式内存管理。也就是说，80386 除了
完成并完善从 80286 开始的段式内存管理的同时还实现了页式内存管理。

但是这个 80386 的页式内存管理设计时，没有绕开段式内存管理，而是建立在段式内存管理的基础上，
这就意味着，页式内存管理的作用是在由段式内存管理所映射而成的地址上再加上一层地址映射。

由于此时由段式内存管理映射而成的地址不再是“物理地址”了，Intel 就称之为“线性地址”（也称虚拟地址）。
于是，段式内存管理先将逻辑地址映射成线性地址，然后再由页式内存管理将线性地址映射成物理地址。

这里说明下逻辑地址和线性地址：

• 程序所使用的地址，通常是没被段式内存管理映射的地址，称为逻辑地址；
• 通过段式内存管理映射的地址，称为线性地址，也叫虚拟地址；

逻辑地址是「段式内存管理」转换前的地址，线性地址则是「页式内存管理」转换前的地址。

Linux 内存主要采用的是页式内存管理，但同时也不可避免地涉及了段机制。

这主要是上面 Intel 处理器发展历史导致的，因为 Intel X86 CPU 一律对程序中使用的地址先进行段式映射，
然后才能进行页式映射。既然 CPU 的硬件结构是这样，Linux 内核也只好服从 Intel 的选择。

但是事实上，Linux 内核所采取的办法是使段式映射的过程实际上不起什么作用。也就是说“上有政策，下有对策”，若惹不起就躲着走。

Linux 系统中的每个段都是从 0 地址开始的整个 4GB 虚拟空间（32 位环境下），也就是所有的段的起始地址都是一样的。
这意味着，Linux 系统中的代码，包括操作系统本身的代码和应用程序代码，所面对的地址空间都是线性地址空间（虚拟地址），
这种做法相当于屏蔽了处理器中的逻辑地址概念，段只被用于访问控制和内存保护。

在 Linux 操作系统中，虚拟地址空间的内部又被分为 内核空间和用户空间 两部分，不同
位数的系统，地址空间的范围也不同。比如最常见的 32 位和 64 位系统，如下所示：

通过这里可以看出：

• 32 位系统的内核空间占用 1G，位于最高处，剩下的 3G 是用户空间；
• 64 位系统的内核空间和用户空间都是 128T，分别占据整个内存空间的最高和最低处，剩下的中间部分是未定义的。

再来说说，内核空间与用户空间的区别：

• 进程在用户态时，只能访问用户空间内存；
• 只有进入内核态后，才可以访问内核空间的内存；

虽然每个进程都各自有独立的虚拟内存，但是 每个虚拟内存中的内核地址，其实关联的
都是相同的物理内存。这样，进程切换到内核态后，就可以很方便地访问内核空间内存。

接下来，进一步了解虚拟空间的划分情况，用户空间和内核空间划分的方式是不同的，内核空间的分布情况就不多说了。

我们看看用户空间分布的情况，以 32 位系统为例，我画了一张图来表示它们的关系：

通过这张图你可以看到，用户空间内存，从低到高分别是 6 种不同的内存段：

• 代码段，包括二进制可执行代码；
• 数据段，包括已初始化的静态常量和全局变量；
• BSS 段，包括未初始化的静态变量和全局变量；
• 堆段，包括动态分配的内存，从低地址开始向上增长；
• 文件映射段，包括动态库、共享内存等，从低地址开始向上增长（跟硬件和内核版本有关）；
• 栈段，包括局部变量和函数调用的上下文等。栈的大小是固定的，一般是 8 MB。当然系统也提供了参数，以便我们自定义大小；

上图中的内存布局可以看到，代码段下面还有一段内存空间的（灰色部分），这一块区域是「保留区」，之所以要有保留区是因为在
大多数的系统里，我们认为比较小数值的地址不是一个合法地址，例如，我们通常在 C 的代码里会将无效的指针赋值为 NULL。因此，
这里会出现一段不可访问的内存保留区，防止程序因此出现 bug，导致读或写了一些小内存地址的数据，而使得程序跑飞。

在这 7 个内存段中，堆和文件映射段的内存是动态分配的。比如使用 C 标准库的 malloc() 或者 mmap() ，就可以分别在堆和文件映射段动态分配内存。

在前面我们知道了回收内存有两种方式：

• 一种是后台内存回收，也就是唤醒 kswapd 内核线程，这种方式是异步回收的，不会阻塞进程。
• 一种是直接内存回收，这种方式是同步回收的，会阻塞进程，这样就会造成很长时间的延迟，
  以及系统的 CPU 利用率会升高，最终引起系统负荷飙高。

可被回收的内存类型有文件页和匿名页：

• 文件页的回收：对于干净页是直接释放内存，这个操作不会影响性能，而对于脏页会先
  写回到磁盘再释放内存，这个操作会发生磁盘 I/O 的，这个操作是会影响系统性能的。
• 匿名页的回收：如果开启了 Swap 机制，那么 Swap 机制会将不常访问的匿名页换出
  到磁盘中，下次访问时，再从磁盘换入到内存中，这个操作是会影响系统性能的。

可以看到，回收内存的操作基本都会发生磁盘 I/O 的，如果回收内存的操作很频繁，意味
着磁盘 I/O 次数会很多，这个过程势必会影响系统的性能，整个系统给人的感觉就是很卡。

下面针对回收内存导致的性能影响，说说常见的解决方式。

从文件页和匿名页的回收操作来看，文件页的回收操作对系统的影响相比匿名页的回收操作会少一点，因为
文件页对于干净页回收是不会发生磁盘 I/O 的，而匿名页的 Swap 换入换出这两个操作都会发生磁盘 I/O。

Linux 提供了一个 /proc/sys/vm/swappiness 选项，用来调整文件页和匿名页的回收倾向。

swappiness 的范围是 0-100：

• 数值越大，越积极使用 Swap，也就是更倾向于回收匿名页；
• 数值越小，越消极使用 Swap，也就是更倾向于回收文件页。

一般建议 swappiness 设置为 0（默认值是 60），这样在回收内存的时候，会更倾向于文件页的回收，但是并不代表不会回收匿名页。

如何查看系统的直接内存回收和后台内存回收的指标？

我们可以使用 sar -B 1 命令来观察：

图中红色框住的就是后台内存回收和直接内存回收的指标，它们分别表示：

• pgscank/s : kswapd(后台回收线程) 每秒扫描的 page 个数。
• pgscand/s: 应用程序在内存申请过程中每秒直接扫描的 page 个数。
• pgsteal/s: 扫描的 page 中每秒被回收的个数（pgscank+pgscand）。

如果系统时不时发生抖动，并且在抖动的时间段里如果通过 sar -B 观察到 pgscand 数值很大，那大概率是因为「直接内存回收」导致的。

针对这个问题，解决的办法就是，可以通过尽早的触发「后台内存回收」来避免应用程序进行直接内存回收。

什么条件下才能触发 kswapd 内核线程回收内存呢？

内核定义了三个内存阈值（watermark，也称为水位），用来衡量当前剩余内存（pages_free）是否充裕或者紧张，分别是：

• 页最小阈值（pages_min）；
• 页低阈值（pages_low）；
• 页高阈值（pages_high）；

这三个内存阈值会划分为四种内存使用情况，如下图：

kswapd 会定期扫描内存的使用情况，根据剩余内存（pages_free）的情况来进行内存回收的工作。

• 图中绿色部分：如果剩余内存（pages_free）大于 页高阈值（pages_high），说明剩余内存是充足的；

• 图中蓝色部分：如果剩余内存（pages_free）在页高阈值（pages_high）和页低阈值（pages_low）之间，
  说明内存有一定压力，但还可以满足应用程序申请内存的请求；

• 图中橙色部分：如果剩余内存（pages_free）在页低阈值（pages_low）和页最小阈值（pages_min）之间，
  说明内存压力比较大，剩余内存不多了。这时 kswapd0 会执行内存回收，直到剩余内存大于高阈值（pages_high）
  为止。虽然会触发内存回收，但是不会阻塞应用程序，因为两者关系是异步的。

• 图中红色部分：如果剩余内存（pages_free）小于页最小阈值（pages_min），说明用户可用内存都耗尽了，
  此时就会 触发直接内存回收，这时应用程序就会被阻塞，因为两者关系是同步的。

可以看到，当剩余内存页（pages_free）小于页低阈值（pages_low），就会触发 kswapd 进行
后台回收，然后 kswapd 会一直回收到剩余内存页（pages_free）大于页高阈值（pages_high）。

也就是说 kswapd 的活动空间只有 pages_low 与 pages_min 之间的这段区域，如果剩余
内存低于了 pages_min 会触发直接内存回收，高于了 pages_high 又不会唤醒 kswapd。

页低阈值（pages_low）可以通过内核选项 /proc/sys/vm/min_free_kbytes （该参数代表系统所保留空闲内存的最低限）来间接设置。

min_free_kbytes 虽然设置的是页最小阈值（pages_min），但是页高阈值（pages_high）和页低阈值（pages_low）
都是根据页最小阈值（pages_min）计算生成的，它们之间的计算关系如下：

如果系统时不时发生抖动，并且通过 sar -B 观察到 pgscand 数值很大，那大概率是因为直接内存回收导致的，
这时可以增大 min_free_kbytes 这个配置选项来及早地触发后台回收，然后继续观察 pgscand 是否会降为 0。

增大了 min_free_kbytes 配置后，这会使得系统预留过多的空闲内存，从而在一定程度上降低了应用程序可使用的内存量，这在一定程度上
浪费了内存。极端情况下设置 min_free_kbytes 接近实际物理内存大小时，留给应用程序的内存就会太少而可能会频繁地导致 OOM 的发生。

所以在调整 min_free_kbytes 之前，需要先思考一下，应用程序更加关注什么，如果关注延迟
那就适当地增大 min_free_kbytes，如果关注内存的使用量那就适当地调小 min_free_kbytes。

什么是 NUMA 架构？

再说 NUMA 架构前，先给大家说说 SMP 架构，这两个架构都是针对 CPU 的。

SMP 指的是一种 多个 CPU 处理器共享资源的电脑硬件架构，也就是说每个 CPU 地位平等，它们共享相同的物理资源，包括总线、内存、IO、
操作系统等。每个 CPU 访问内存所用时间都是相同的，因此，这种系统也被称为一致存储访问结构（UMA，Uniform Memory Access）。

随着 CPU 处理器核数的增多，多个 CPU 都通过一个总线访问内存，这样总线的带宽压力会越来越大，
同时每个 CPU 可用带宽会减少，这也就是 SMP 架构的问题。

为了解决 SMP 架构的问题，就研制出了 NUMA 结构，即非一致存储访问结构（Non-uniform memory access，NUMA）。

NUMA 架构将每个 CPU 进行了分组，每一组 CPU 用 Node 来表示，一个 Node 可能包含多个 CPU 。

每个 Node 有自己独立的资源，包括内存、IO 等，每个 Node 之间可以通过互联模块总线（QPI）进行通信，所以，也就意味
着每个 Node 上的 CPU 都可以访问到整个系统中的所有内存。但是，访问远端 Node 的内存比访问本地内存要耗时很多。

NUMA 架构跟回收内存有什么关系？

在 NUMA 架构下，当某个 Node 内存不足时，系统可以从其他 Node 寻找空闲内存，也可以从本地内存中回收内存。

具体选哪种模式，可以通过 /proc/sys/vm/zone_reclaim_mode 来控制。它支持以下几个选项：

• 0 （默认值）：在回收本地内存之前，在其他 Node 寻找空闲内存；
• 1：只回收本地内存；
• 2：只回收本地内存，在本地回收内存时，可以将文件页中的脏页写回硬盘，以回收内存。
• 4：只回收本地内存，在本地回收内存时，可以用 swap 方式回收内存。

在使用 NUMA 架构的服务器，如果系统出现还有一半内存的时候，却发现系统频繁触发「直接内存回收」，导致了影响了系统性能，那么大概率
是因为 zone_reclaim_mode 没有设置为 0 ，导致当本地内存不足的时候，只选择回收本地内存的方式，而不去使用其他 Node 的空闲内存。

虽然说访问远端 Node 的内存比访问本地内存要耗时很多，但是相比内存回收的危害而言，访问
远端 Node 的内存带来的性能影响还是比较小的。因此，zone_reclaim_mode 一般建议设置为 0。

因为 32 位操作系统，进程最多只能申请 3 GB 大小的虚拟内存空间，所以进程申请 8GB 内存的话，
在申请虚拟内存阶段就会失败（我手上没有 32 位操作系统测试，我估计失败的原因是 OOM）。

64 位操作系统，进程可以使用 128 TB 大小的虚拟内存空间，所以进程申请 8GB 内存是没问题的，
因为进程申请内存是申请虚拟内存，只要不读写这个虚拟内存，操作系统就不会分配物理内存。

我们可以简单做个测试，我的服务器是 64 位操作系统，但是物理内存只有 2 GB：

现在，我在机器上，连续申请 4 次 1 GB 内存，也就是一共申请了 4 GB 内存，
注意下面代码只是单纯分配了虚拟内存，并没有使用该虚拟内存：

然后运行这个代码，可以看到，我的物理内存虽然只有 2GB，但是程序正常分配了 4GB 大小的虚拟内存：

我们可以通过下面这条命令查看进程（test）的虚拟内存大小：

• 其中，VSZ 就代表进程使用的虚拟内存大小，RSS 代表进程使用的物理内存大小。
  可以看到，VSZ 大小为 4198540，也就是 4GB 的虚拟内存。

前面讨论在 32 位/64 位操作系统环境下，申请的虚拟内存超过物理内存后会怎么样？

• 在 32 位操作系统，因为进程最大只能申请 3 GB 大小的虚拟内存，所以直接申请 8G 内存，会申请失败。
• 在 64 位操作系统，因为进程最大只能申请 128 TB 大小的虚拟内存，即使物理内存只有 4GB，申请 8G 内存也是没问题，因为申请的内存是虚拟内存。

程序申请的虚拟内存，如果没有被使用，它是不会占用物理空间的。当访问这块虚拟内存后，操作系统才会进行物理内存分配。

如果申请物理内存大小超过了空闲物理内存大小，就要看操作系统有没有开启 Swap 机制：

• 如果没有开启 Swap 机制，程序就会直接 OOM；
• 如果有开启 Swap 机制，程序可以正常运行。

什么是 Swap 机制？

Swap 换入换出的是什么类型的内存？

我的服务器是 64 位操作系统，但是物理内存只有 2 GB，而且没有 Swap 分区：

我们改一下前面的代码，使得在申请完 4GB 虚拟内存后，通过 memset 函数访问这个虚拟内存，看看在没有 Swap 分区的情况下，会发生什么？

运行结果：

可以看到，在访问第 2 块虚拟内存（每一块虚拟内存是 1 GB）的时候，因为超过了机器的物理内存（2GB），进程（test）被操作系统杀掉了。

通过查看 message 系统日志，可以发现该进程是被操作系统 OOM killer 机制杀掉了，
日志里报错了 Out of memory，也就是发生 OOM（内存溢出错误）。

内存溢出(Out Of Memory，简称OOM)是指应用系统中存在无法回收的内存或使用的内存过多，
最终使得程序运行要用到的内存大于能提供的最大内存。此时程序就运行不了，系统会提示内存溢出。

我用我的 mac book pro 笔记本做测试，我的笔记本是 64 位操作系统，物理内存是 8 GB， 目前 Swap 分区大小为 1 GB（注意这个大小不是固定
不变的，Swap 分区总大小是会动态变化的，当没有使用 Swap 分区时，Swap 分区总大小是 0；当使用了 Swap 分区，Swap 分区总大小会增加至 
1 GB；当 Swap 分区已使用的大小超过 1 GB 时；Swap 分区总大小就会增加到至 2 GB；当 Swap 分区已使用的大小超过 2 GB 时；Swap 分区总
大小就增加至 3GB，如此往复。这个估计是 macos 自己实现的，Linux 的分区则是固定大小的，Swap 分区不会根据使用情况而自动增长）。

为了方便观察磁盘 I/O 情况，我们改进一下前面的代码，分配完 32 GB虚拟内存后（笔记本物理内存是 8 GB），
通过一个 while 循环频繁访问虚拟内存，代码如下：

运行结果如下：

可以看到，在有 Swap 分区的情况下，即使笔记本物理内存是 8 GB，申请并使用 32 GB 内存是没问题，程序正常运行了，并没有发生 OOM。

从下图可以看到，进程的内存显示 32 GB（这个不要理解为占用的物理内存，理解为已被访问
的虚拟内存大小，也就是在物理内存呆过的内存大小），系统已使用的 Swap 分区达到 2.3 GB。

此时我的笔记本电脑的磁盘开始出现“沙沙”的声音，通过查看磁盘的 I/O 情况，可以看到磁盘 I/O 达到了一个峰值，非常高：

那么有了 Swap 分区，是不是意味着进程可以使用的内存是无上限的？

在应用程序读取文件的数据的时候，Linux 操作系统是会对读取的文件数据进行缓存的，会缓存在文件系统中的 Page Cache（如下图中的页缓存）。

Page Cache 属于内存空间里的数据，由于内存访问比磁盘访问快很多，在下一次访问相同的数据就不需要通过磁盘 I/O 了，命中缓存就直接返回数据即可。

因此，Page Cache 起到了加速访问数据的作用。

MySQL 的数据是存储在磁盘里的，为了提升数据库的读写性能，Innodb 存储引擎
设计了一个 缓冲池（Buffer Pool），Buffer Pool 属于内存空间里的数据。

有了缓冲池后：

• 当读取数据时，如果数据存在于 Buffer Pool 中，客户端就会直接读取 Buffer Pool 中的数据，否则再去磁盘中读取。
• 当修改数据时，首先是修改 Buffer Pool 中数据所在的页，然后将其页设置为脏页，最后由后台线程将脏页写入到磁盘。

Linux 操作系统为基于 Page Cache 的读缓存机制提供 预读机制，一个例子是：

• 应用程序只想读取磁盘上文件 A 的 offset 为 0-3KB 范围内的数据，由于磁盘的基本读写单位为 block（4KB），
  于是操作系统至少会读 0-4KB 的内容，这恰好可以在一个 page 中装下。
• 但是操作系统出于 空间局部性原理（靠近当前被访问数据的数据，在未来很大概率会被访问到），会选择将磁盘块 
  offset [4KB,8KB)、[8KB,12KB) 以及 [12KB,16KB) 都加载到内存，于是额外在内存中申请了 3 个 page；

下图代表了操作系统的预读机制：

上图中，应用程序利用 read 系统调动读取 4KB 数据，实际上内核使用预读机制（ReadaHead） 
机制完成了 16KB 数据的读取，也就是通过一次磁盘顺序读将多个 Page 数据装入 Page Cache。

这样下次读取 4KB 数据后面的数据的时候，就不用从磁盘读取了，直接在 Page Cache 即可命中数据。
因此，预读机制带来的好处就是 减少了 磁盘 I/O 次数，提高系统磁盘 I/O 吞吐量。

MySQL Innodb 存储引擎的 Buffer Pool 也有类似的预读机制，MySQL 从磁盘加载页时，会提前把它相邻的页一并加载进来，目的是为了减少磁盘 IO。

如果这些 被提前加载进来的页，并没有被访问，相当于这个预读工作是白做了，这个就是 预读失效。

如果使用传统的 LRU 算法，就会把「预读页」放到 LRU 链表头部，而当内存空间不够的时候，还需要把末尾的页淘汰掉。

如果这些「预读页」如果一直不会被访问到，就会出现一个很奇怪的问题，不会被访问的预读页却
占用了 LRU 链表前排的位置，而末尾淘汰的页，可能是热点数据，这样就大大降低了缓存命中率 。

我们不能因为害怕预读失效，而将预读机制去掉，大部分情况下，空间局部性原理还是成立的。

要避免预读失效带来影响，最好就是 让预读页停留在内存里的时间要尽可能的短，让真正被访问
的页才移动到 LRU 链表的头部，从而保证真正被读取的热数据留在内存里的时间尽可能长。

那到底怎么才能避免呢？

Linux 操作系统和 MySQL Innodb 通过改进传统 LRU 链表来避免预读失效带来的影响，具体的改进分别如下：

• Linux 操作系统实现两个了 LRU 链表：活跃 LRU 链表（active_list）和非活跃 LRU 链表（inactive_list）；
• MySQL 的 Innodb 存储引擎是在一个 LRU 链表上划分来 2 个区域：young 区域 和 old 区域。

这两个改进方式，设计思想都是类似的，都是将数据分为了冷数据和热数据，然后分别进行 LRU 算法。
不再像传统的 LRU 算法那样，所有数据都只用一个 LRU 算法管理。

接下来，具体聊聊 Linux 和 MySQL 是如何避免预读失效带来的影响？

Linux 是如何避免预读失效带来的影响？

MySQL 是如何避免预读失效带来的影响？

虽然 Linux （实现两个 LRU 链表）和 MySQL （划分两个区域）通过改进传统的 LRU 数据结构，避免了预读失效带来的影响。

但是如果还是使用「只要数据被访问一次，就将数据加入到活跃 LRU 链表头部（或者 young 区域）」这种方式的话，那么 还存在缓存污染的问题。

当我们在批量读取数据的时候，由于数据被访问了一次，这些大量数据都会被加入到「活跃 LRU 链表」里，然后之前缓存在活跃 LRU 链表（或者 young 
区域）里的热点数据全部都被淘汰了，如果这些大量的数据在很长一段时间都不会被访问的话，那么整个活跃 LRU 链表（或者 young 区域）就被污染了。

缓存污染带来的影响就是很致命的，等这些热数据又被再次访问的时候，由于缓存未命中，就会产生大量的磁盘 I/O，系统性能就会急剧下降。

我以 MySQL 举例子，Linux 发生缓存污染的现象也是类似。

当某一个 SQL 语句 扫描了大量的数据 时，在 Buffer Pool 空间比较有限的情况下，可能会将 Buffer Pool 里的所有页都替换出去，导致
大量热数据被淘汰了，等这些热数据又被再次访问的时候，由于缓存未命中，就会产生大量的磁盘 I/O，MySQL 性能就会急剧下降。

注意， 缓存污染并不只是查询语句查询出了大量的数据才出现的问题，即使查询出来的结果集很小，也会造成缓存污染。

比如，在一个数据量非常大的表，执行了这条语句：

可能这个查询出来的结果就几条记录，但是由于这条语句会发生索引失效，所以这个查询过程是 全表扫描 的，接着会发生如下的过程：

• 从磁盘读到的页加入到 LRU 链表的 old 区域头部；
• 当从页里读取行记录时，也就是页被访问的时候，就要将该页放到 young 区域头部；
• 接下来拿行记录的 name 字段和字符串 xiaolin 进行模糊匹配，如果符合条件，就加入到结果集里；
• 如此往复，直到扫描完表中的所有记录。

经过这一番折腾，由于这条 SQL 语句访问的页非常多，每访问一个页，都会将其加入 young 区域头部，那么 原本 young 区域的热点数据都会被
替换掉，导致缓存命中率下降。那些在批量扫描时被加入到 young 区域的页，如果在很长一段时间都不会再被访问的话，就污染了 young 区域。

举个例子，假设需要批量扫描：21，22，23，24，25 这五个页，这些页都会被逐一访问（读取页里的记录）。

在批量访问这些页的时候，会被逐一插入到 young 区域头部。

可以看到，原本在 young 区域的 6 和 7 号页都被淘汰了，而批量扫描的页基本占满了 young 区域，
如果这些页在很长一段时间都不会被访问，那么就对 young 区域造成了污染。

如果 6 和 7 号页是热点数据，那么在被淘汰后，后续有 SQL 再次读取 6 和 7 号页时，由于
缓存未命中，就要从磁盘中读取了，降低了 MySQL 的性能，这就是缓存污染带来的影响。

前面的 LRU 算法只要数据被访问一次，就将数据加入活跃 LRU 链表（或者 young 区域），这种 LRU 算法进入活跃 LRU 
链表的门槛太低了！正式因为门槛太低，才导致在发生缓存污染的时候，很容就将原本在活跃 LRU 链表里的热点数据淘汰了。

所以，只要我们提高进入到活跃 LRU 链表（或者 young 区域）的门槛，就能
有效地保证活跃 LRU 链表（或者 young 区域）里的热点数据不会被轻易替换掉。

Linux 操作系统和 MySQL Innodb 存储引擎分别是这样提高门槛的：

• Linux 操作系统：在内存页被访问 第二次 的时候，才将页从 inactive list 升级到 active list 里。
  
  
• MySQL Innodb：在内存页被访问 第二次 的时候，并不会马上将该页从 old 区域升级到 young 区域，
  因为还要 进行停留在 old 区域的时间判断：

          · 如果第二次的访问时间与第一次访问的时间 在 1 秒内（默认值），那么该页就 不会 被从 old 区域升级到 young 区域；
          · 如果第二次的访问时间与第一次访问的时间 超过 1 秒，那么该页就 会 从 old 区域升级到 young 区域；

提高了进入活跃 LRU 链表（或者 young 区域）的门槛后，就很好了避免缓存污染带来的影响。

在批量读取数据时候，如果这些大量数据只会被访问一次，那么它们就不会进入到活跃 LRU 链表（或者 young 区域），
也就不会把热点数据淘汰，只会待在非活跃 LRU 链表（或者 old 区域）中，后续很快也会被淘汰。

我们编写的代码只是一个存储在硬盘的静态文件，通过编译后就会生成二进制可执行文件，当我们运行这个可执行文件后，
它会被装载到内存中，接着 CPU 会执行程序中的每一条指令，那么这个 运行中的程序，就被称为「进程」（Process）。

现在我们考虑有一个会读取硬盘文件数据的程序被执行了，那么当运行到读取文件的指令时，就会去从硬盘读取数据，
但是硬盘的读写速度是非常慢的，那么在这个时候，如果 CPU 傻傻的等硬盘返回数据的话，那 CPU 的利用率是非常低的。

做个类比，你去煮开水时，你会傻傻的等水壶烧开吗？很明显，小孩也不会傻等。我们可以在水壶烧开之前
去做其他事情。当水壶烧开了，我们自然就会听到“嘀嘀嘀”的声音，于是再把烧开的水倒入到水杯里就好了。

所以，当进程要从硬盘读取数据时，CPU 不需要阻塞等待数据的返回，而是去执行另外的进程。
当硬盘数据返回时，CPU 会收到个 中断，于是 CPU 再继续运行这个进程。

这种 多个程序、交替执行 的思想，就有 CPU 管理多个进程的初步想法。

对于一个支持多进程的系统，CPU 会从一个进程快速切换至另一个进程，其间每个进程各运行几十或几百个毫秒。

虽然单核的 CPU 在某一个瞬间，只能运行一个进程。但在 1 秒钟期间，
它可能会运行多个进程，这样就产生 并行的错觉，实际上这是 并发。

并发和并行有什么区别？

进程与程序的关系的类比

在上面，我们知道了进程有着「运行 - 暂停 - 运行」的活动规律。一般说来，一个进程
并不是自始至终连续不停地运行的，它与并发执行中的其他进程的执行是相互制约的。

它有时处于运行状态，有时又由于某种原因而暂停运行处于等待状态，当使它暂停的原因消失后，它又进入准备运行状态。

所以，在一个进程的 活动期间 至少具备三种基本状态，即 运行状态、就绪状态、阻塞状态：

• 运行状态（Running）：该时刻进程占用 CPU；
• 就绪状态（Ready）：可运行，由于其他进程处于运行状态而暂时停止运行；
• 阻塞状态（Blocked）：该进程正在等待某一事件发生（如等待输入/输出操作的完成）
  而暂时停止运行，这时，即使给它CPU控制权，它也无法运行；

当然，进程还有 另外两个基本状态：

• 创建状态（new）：进程正在被创建时的状态；
• 结束状态（Exit）：进程正在从系统中消失时的状态；

于是，一个完整的进程状态的变迁如下图：

再来详细说明一下进程的状态变迁：

• NULL -> 创建状态：一个新进程被创建时的第一个状态；
• 创建状态 -> 就绪状态：当进程被创建完成并初始化后，一切就绪准备运行时，变为就绪状态，这个过程是很快的；
• 就绪态 -> 运行状态：处于就绪状态的进程被操作系统的进程调度器选中后，就分配给 CPU 正式运行该进程；
• 运行状态 -> 结束状态：当进程已经运行完成或出错时，会被操作系统作结束状态处理；
• 运行状态 -> 就绪状态：处于运行状态的进程在运行过程中，由于分配给它的运行时间片用完，
  操作系统会把该进程变为就绪态，接着从就绪态选中另外一个进程运行；
• 运行状态 -> 阻塞状态：当进程请求某个事件且必须等待时，例如请求 I/O 事件；
• 阻塞状态 -> 就绪状态：当进程要等待的事件完成时，它从阻塞状态变到就绪状态；

如果有大量处于阻塞状态的进程，进程可能会占用着物理内存空间，显然不是我们所希望的，
毕竟物理内存空间是有限的，被阻塞状态的进程占用着物理内存就一种浪费物理内存的行为。

所以，在虚拟内存管理的操作系统中，通常会把阻塞状态的进程的物理内存空间换出到硬盘，
等需要再次运行的时候，再从硬盘换入到物理内存。

那么，就需要一个新的状态，来描述进程没有占用实际的物理内存空间的情况，这个状态就是挂起状态。
这跟阻塞状态是不一样，阻塞状态是等待某个事件的返回。

另外，挂起状态可以分为两种：

• 阻塞挂起状态：进程在外存（硬盘）并等待某个事件的出现；
• 就绪挂起状态：进程在外存（硬盘），但只要进入内存，即刻立刻运行；

这两种挂起状态加上前面的五种状态，就变成了七种状态变迁（留给我的颜色不多了），见如下图：

导致进程挂起的原因不只是因为进程所使用的内存空间不在物理内存，还包括如下情况：

• 通过 sleep 让进程间歇性挂起，其工作原理是设置一个定时器，到期后唤醒进程。
• 用户希望挂起一个程序的执行，比如在 Linux 中用 Ctrl+Z 挂起进程；

在操作系统中，是用 进程控制块（process control block，PCB）数据结构来描述进程的。

PCB 是进程存在的唯一标识，这意味着一个进程的存在，必然会有一个 PCB，如果进程消失了，那么 PCB 也会随之消失。

PCB 具体包含什么信息呢？

每个 PCB 是如何组织的呢？

我们熟知了进程的状态变迁和进程的数据结构 PCB 后，再来看看进程的 创建、终止、阻塞、唤醒 的过程，这些过程也就是进程的控制。

1、创建进程

2、终止进程

3、阻塞进程

4、唤醒进程

各个进程之间是共享 CPU 资源的，在不同的时候进程之间需要切换，让不同的进程
可以在 CPU 执行，那么这个一个进程切换到另一个进程运行，称为进程的上下文切换。

在详细说进程上下文切换前，我们先来看看 CPU 上下文切换

进程的上下文切换到底是切换什么呢？

发生进程上下文切换有哪些场景？

我们举个例子，假设你要编写一个视频播放器软件，那么该软件功能的核心模块有三个：

• 从视频文件当中读取数据；
• 对读取的数据进行解压缩；
• 把解压缩后的视频数据播放出来；

对于单进程的实现方式，我想大家都会是以下这个方式：

对于单进程的这种方式，存在以下问题：

• 播放出来的画面和声音会不连贯，因为当 CPU 能力不够强的时候，Read 
  的时候可能进程就等在这了，这样就会导致等半天才进行数据解压和播放；
• 各个函数之间不是并发执行，影响资源的使用效率；

那改进成多进程的方式：

对于多进程的这种方式，依然会存在问题：

• 进程之间如何通信，共享数据？
• 维护进程的系统开销较大，如创建进程时，分配资源、建立 PCB；
  终止进程时，回收资源、撤销 PCB；进程切换时，保存当前进程的状态信息；

那到底如何解决呢？需要有一种新的实体，满足以下特性：

• 实体之间可以并发运行；
• 实体之间共享相同的地址空间；

这个新的实体，就是 线程（Thread），线程之间可以并发运行且共享相同的地址空间。

线程是进程当中的一条执行流程。

同一个进程内多个线程之间可以共享代码段、数据段、打开的文件等资源，但每个
线程各自都有一套独立的寄存器和栈，这样可以确保线程的控制流是相对独立的。

线程的优缺点？

线程与进程的比较如下：

• 进程是资源（包括内存、打开的文件等）分配的单位，而线程是 CPU 调度的单位；
• 进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈；
• 线程同样具有就绪、阻塞、执行三种基本状态，同样具有状态之间的转换关系；
• 线程能减少并发执行的时间和空间开销；

对于，线程相比进程能减少开销，体现在：

• 线程的创建时间比进程快，因为进程在创建的过程中，还需要资源管理信息，比如内存管理信息、
  文件管理信息，而线程在创建的过程中，不会涉及这些资源管理信息，而是共享它们；
• 线程的终止时间比进程快，因为线程释放的资源相比进程少很多；
• 同一个进程内的线程切换比进程切换快，因为线程具有相同的地址空间（虚拟内存共享），这意味着同一个进程的线程都具有同一个
  页表，那么在切换的时候不需要切换页表。而对于进程之间的切换，切换的时候要把页表给切换掉，而页表的切换过程开销是比较大的；
• 由于同一进程的各线程间共享内存和文件资源，那么在线程之间数据传递的时候，就不需要经过内核了，这就使得线程之间的数据交互效率更高了；

所以，不管是时间效率，还是空间效率线程比进程都要高。

在前面我们知道了，线程与进程最大的区别在于：线程是调度的基本单位，而进程则是资源拥有的基本单位。

所以，所谓操作系统的任务调度，实际上的调度对象是线程，而进程只是给线程提供了虚拟内存、全局变量等资源。

对于线程和进程，我们可以这么理解：

• 当进程只有一个线程时，可以认为进程就等于线程；
• 当进程拥有多个线程时，这些线程会共享相同的虚拟内存和全局变量等资源，这些资源在上下文切换时是不需要修改的；

另外，线程也有自己的私有数据，比如栈和寄存器等，这些在上下文切换时也是需要保存的。

线程上下文切换的是什么？

主要有三种线程的实现方式：

• 用户线程（User Thread）：在用户空间实现的线程，不是由内核管理的线程，是由用户态的线程库来完成线程的管理；
• 内核线程（Kernel Thread）：在内核中实现的线程，是由内核管理的线程；
• 轻量级进程（LightWeight Process）：在内核中来支持用户线程；

那么，这还需要考虑一个问题，用户线程和内核线程的对应关系。

首先，第一种关系是多对一的关系，也就是多个用户线程对应同一个内核线程：

第二种是一对一的关系，也就是一个用户线程对应一个内核线程：

第三种是多对多的关系，也就是多个用户线程对应到多个内核线程：

用户线程如何理解？存在什么优势和缺陷？

那内核线程如何理解？存在什么优势和缺陷？

最后的轻量级进程如何理解？

进程都希望自己能够占用 CPU 进行工作，那么这涉及到前面说过的进程上下文切换。

一旦操作系统把进程切换到运行状态，也就意味着该进程占用着 CPU 在执行，但是当操作系统
把进程切换到其他状态时，那就不能在 CPU 中执行了，于是操作系统会选择下一个要运行的进程。

选择一个进程运行这一功能是在操作系统中完成的，通常称为 调度程序（scheduler）。

那到底什么时候调度进程，或以什么原则来调度进程呢？

在进程的生命周期中，当进程从一个运行状态到另外一状态变化或者从某一状态转变到运行态的时候，其实会触发一次调度。

比如，以下状态的变化都会触发操作系统的调度：

• 就绪态 -> 运行态：当进程被创建时，会进入到就绪队列，操作系统会从就绪队列选择一个进程运行；
• 运行态 -> 阻塞态：当进程发生 I/O 事件而阻塞时，操作系统必须选择另外一个进程运行；
• 运行态 -> 结束态：当进程退出结束后，操作系统得从就绪队列选择另外一个进程运行；

因为，这些状态变化的时候，操作系统需要考虑是否要让新的进程给 CPU 运行，或者是否让当前进程从 CPU 上退出来而换另一个进程运行。

另外，如果硬件时钟提供某个频率的周期性中断，那么可以根据如何处理时钟中断 ，把调度算法分为两类：

• 非抢占式调度算法 挑选一个进程，然后让该进程运行直到被阻塞，或者直到该进程退出，才会调用另外一个进程，也就是说不会理时钟中断这个事情。
• 抢占式调度算法 挑选一个进程，然后让该进程只运行某段时间，如果在该时段结束时，该进程仍然在运行时，则会把它挂起，接着调度程序从就绪队列
  挑选另外一个进程。这种抢占式调度处理，需要在时间间隔的末端发生时钟中断，以便把 CPU 控制返回给调度程序进行调度，也就是常说的时间片机制。

原则一：如果运行的程序，发生了 I/O 事件的请求，那 CPU 使用率必然会很低，因为此时进程在阻塞等待硬盘的数据返回。这样的过程，势必会造成 
CPU 突然的空闲。所以，为了提高 CPU 利用率，在这种发送 I/O 事件致使 CPU 空闲的情况下，调度程序需要从就绪队列中选择一个进程来运行。

原则二：有的程序执行某个任务花费的时间会比较长，如果这个程序一直占用着 CPU，会造成系统吞吐量（CPU 在单位时间内完成的进程数量）
的降低。所以，要提高系统的吞吐率，调度程序要权衡长任务和短任务进程的运行完成数量。

原则三：从进程开始到结束的过程中，实际上是包含两个时间，分别是进程运行时间和进程等待时间，这两个时间总和就称为周转时间。进程
的周转时间越小越好，如果进程的等待时间很长而运行时间很短，那周转时间就很长，这不是我们所期望的，调度程序应该避免这种情况发生。

原则四：处于就绪队列的进程，也不能等太久，当然希望这个等待的时间越短越好，这样可以使得
进程更快的在 CPU 中执行。所以，就绪队列中进程的等待时间也是调度程序所需要考虑的原则。

原则五：对于鼠标、键盘这种交互式比较强的应用，我们当然希望它的响应时间越快越好，否则
就会影响用户体验了。所以，对于交互式比较强的应用，响应时间也是调度程序需要考虑的原则。

针对上面的五种调度原则，总结成如下：

• CPU 利用率：调度程序应确保 CPU 是始终匆忙的状态，这可提高 CPU 的利用率；
• 系统吞吐量：吞吐量表示的是单位时间内 CPU 完成进程的数量，长作业的进程会
  占用较长的 CPU 资源，因此会降低吞吐量，相反，短作业的进程会提升系统吞吐量；
• 周转时间：周转时间是进程运行+阻塞时间+等待时间的总和，一个进程的周转时间越小越好；
• 等待时间：这个等待时间不是阻塞状态的时间，而是进程处于就绪队列的时间，等待的时间越长，用户越不满意；
• 响应时间：用户提交请求到系统第一次产生响应所花费的时间，在交互式系统中，响应时间是衡量调度算法好坏的主要标准。

说白了，这么多调度原则，目的就是要使得进程要「快」。

匿名管道的创建，需要通过下面这个系统调用：

这里表示创建一个匿名管道，并返回了两个描述符，一个是管道的读取端描述符 fd[0]，另一个是管道的写入端描述符 fd[1]。
注意，这个匿名管道是特殊的文件，只存在于内存，不存于文件系统中。

其实，所谓的管道，就是内核里面的一串缓存。从管道的一段写入的数据，实际上是缓存在内核中的，
另一端读取，也就是从内核中读取这段数据。另外，管道传输的数据是无格式的流且大小受限。

看到这，你可能会有疑问了，这两个描述符都是在一个进程里面，并没有起到进程间通信的作用，怎么样才能使得管道是跨过两个进程的呢？

我们可以使用 fork 创建子进程，创建的子进程会复制父进程的文件描述符，这样就做到了两个进程各有
两个「 fd[0] 与 fd[1]」，两个进程就可以通过各自的 fd 写入和读取 同一个管道文件 实现跨进程通信了。

管道只能一端写入，另一端读出，所以上面这种模式容易造成混乱，因为父进程和
子进程都可以同时写入，也都可以读出。那么，为了避免这种情况，通常的做法是：

• 父进程关闭读取的 fd[0]，只保留写入的 fd[1]；
• 子进程关闭写入的 fd[1]，只保留读取的 fd[0]；

所以说如果需要双向通信，则应该创建两个管道。

到这里，我们仅仅解析了使用管道进行父进程与子进程之间的通信，但是在我们 shell 里面并不是这样的。

在 shell 里面执行 A | B命令的时候，A 进程和 B 进程都是 shell 创建出来的子进程，
A 和 B 之间不存在父子关系，它俩的父进程都是 shell。

所以说，在 shell 里通过「 | 」匿名管道将多个命令连接在一起，实际上也就是创建了多个子进程，那么在我们
编写 shell 脚本时，能使用一个管道搞定的事情，就不要多用一个管道，这样可以减少创建子进程的系统开销。

我们可以得知，对于匿名管道，它的通信范围是存在父子关系的进程。因为管道没有实体，
也就是没有管道文件，只能通过 fork 来复制父进程 fd 文件描述符，来达到通信的目的。

另外，对于命名管道，它可以在不相关的进程间也能相互通信。因为命令管道，提前创建
了一个类型为管道的设备文件，在进程里只要使用这个设备文件，就可以相互通信。

不管是匿名管道还是命名管道，进程写入的数据都是缓存在内核中，另一个进程读取数据时候
自然也是从内核中获取，同时通信数据都遵循 先进先出原则，不支持 lseek 之类的文件定位操作。

• 服务端和客户端初始化 socket，得到文件描述符；
• 服务端调用 bind，将绑定在 IP 地址和端口;
• 服务端调用 listen，进行监听；
• 服务端调用 accept，等待客户端连接；
• 客户端调用 connect，向服务器端的地址和端口发起连接请求；
• 服务端 accept 返回用于传输的 socket 的文件描述符；
• 客户端调用 write 写入数据；服务端调用 read 读取数据；
• 客户端断开连接时，会调用 close，那么服务端 read 读取数据的时候，
  就会读取到了 EOF，待处理完数据后，服务端调用 close，表示连接关闭。

这里需要注意的是，服务端调用 accept 时，连接成功了会返回一个已完成连接的 socket，后续用来传输数据。

所以，监听的 socket 和真正用来传送数据的 socket，是「两个」 socket，一个叫作 监听 socket，一个叫作 已完成连接 socket。

成功连接建立之后，双方开始通过 read 和 write 函数来读写数据，就像往一个文件流里面写东西一样。

UDP 是没有连接的，所以不需要三次握手，也就不需要像 TCP 调用 listen 和 connect，
但是 UDP 的交互仍然需要 IP 地址和端口号，因此也需要 bind。

对于 UDP 来说，不需要要维护连接，那么也就没有所谓的发送方和接收方，甚至都不存在客户端和
服务端的概念，只要有一个 socket 多台机器就可以任意通信，因此每一个 UDP 的 socket 都需要 bind。

另外，每次通信时，调用 sendto 和 recvfrom，都要传入目标主机的 IP 地址和端口。

本地 socket 被用于在 同一台主机上进程间通信 的场景：

• 本地 socket 的编程接口和 IPv4 、IPv6 套接字编程接口是一致的，可以支持「字节流」和「数据报」两种协议；
• 本地 socket 的实现效率大大高于 IPv4 和 IPv6 的字节流、数据报 socket 实现；

对于本地字节流 socket，其 socket 类型是 AF_LOCAL 和 SOCK_STREAM。

对于本地数据报 socket，其 socket 类型是 AF_LOCAL 和 SOCK_DGRAM。

本地字节流 socket 和 本地数据报 socket 在 bind 的时候，不像 TCP 和 UDP 要绑定 IP 地址和端口，
而是 绑定一个本地文件，这也就是它们之间的最大区别。

在单核 CPU 系统里，为了实现多个程序同时运行的假象，操作系统通常以时间片调度的方式，让每个进程执行每次
执行一个时间片，时间片用完了，就切换下一个进程运行，由于这个时间片的时间很短，于是就造成了「并发」的现象。

另外，操作系统也为每个进程创建巨大、私有的虚拟内存的假象，这种地址空间的抽象让每个程序
好像拥有自己的内存，而实际上操作系统在背后秘密地让多个地址空间「复用」物理内存或者磁盘。

如果一个程序只有一个执行流程，也代表它是单线程的。当然一个程序可以有多个执行流程，
也就是所谓的多线程程序，线程是调度的基本单位，进程则是资源分配的基本单位。

所以，线程之间是可以共享进程的资源，比如代码段、堆空间、数据段、打开的文件等资源，但每个线程都有自己独立的栈空间。

那么问题就来了，多个线程如果竞争共享资源，如果不采取有效的措施，则会造成共享数据的混乱。

我们做个小实验，创建两个线程，它们分别对共享变量 i 自增 1 执行 10000 次，如下代码：

按理来说，i 变量最后的值应该是 20000，但很不幸，并不是如此。我们对上面的程序执行一下：

运行了两次，发现出现了 i 值的结果是 15173，也会出现 20000 的 i 值结果。

每次运行不但会产生错误，而且得到不同的结果。在计算机里是不能容忍的，虽然是小概率出现的错误，
但是小概率事件它一定是会发生的，「墨菲定律」大家都懂吧。

为什么会发生这种情况？

上面展示的情况称为 竞争条件（race condition），当多线程相互竞争操作共享变量时，由于运气不好，即在执行过程中发生了上下文切换，
我们得到了错误的结果。事实上，每次运行都可能得到不同的结果，因此输出的结果存在 不确定性（indeterminate）。

由于多线程执行操作共享变量的这段代码可能会导致竞争状态，因此我们将此段代码称为 
临界区（critical section），它是访问共享资源的代码片段，一定不能给多线程同时执行。

我们希望这段代码是 互斥（mutualexclusion）的，也就说 保证一个线程在临界区执行时，
其他线程应该被阻止进入临界区，说白了，就是这段代码执行过程中，最多只能出现一个线程。

另外，说一下互斥也并不是只针对多线程。在多进程竞争共享资源的时候，也同样是可以使用互斥的方式来避免资源竞争造成的资源混乱。

互斥解决了并发进程/线程对临界区的使用问题。这种基于临界区控制的交互作用是比较简单的，只要一个
进程/线程进入了临界区，其他试图想进入临界区的进程/线程都会被阻塞着，直到第一个进程/线程离开了临界区。

我们都知道在多线程里，每个线程并不一定是顺序执行的，它们基本是以各自独立的、不可
预知的速度向前推进，但有时候我们又希望多个线程能密切合作，以实现一个共同的任务。

例子，线程 1 是负责读入数据的，而线程 2 是负责处理数据的，这两个线程是相互合作、相互依赖的。线程 2 在没有收到线程 1 的
唤醒通知时，就会一直阻塞等待，当线程 1 读完数据需要把数据传给线程 2 时，线程 1 会唤醒线程 2，并把数据交给线程 2 处理。

所谓 同步，就是 并发进程/线程在一些关键点上可能需要互相等待与互通消息，这种 相互制约的等待与互通信息称为进程/线程同步。

举个生活的同步例子，你肚子饿了想要吃饭，你叫妈妈早点做菜，妈妈听到后就开始做菜，但是在妈妈
没有做完饭之前，你必须阻塞等待，等妈妈做完饭后，自然会通知你，接着你吃饭的事情就可以进行了。

注意，同步与互斥是两种不同的概念：

• 同步就好比：「操作 A 应在操作 B 之前执行」，「操作 C 必须在操作 A 和操作 B 都完成之后才能执行」等；
• 互斥就好比：「操作 A 和操作 B 不能在同一时刻执行」；

在进程/线程并发执行的过程中，进程/线程之间存在协作的关系，例如有互斥、同步的关系。

为了实现进程/线程间正确的协作，操作系统必须提供实现进程协作的措施和方法，主要的方法有两种：

• 锁：加锁、解锁操作；
• 信号量：P、V 操作；

这两个都可以方便地实现进程/线程互斥，而信号量比锁的功能更强一些，它还可以方便地实现进程/线程同步。

使用加锁操作和解锁操作可以解决并发线程/进程的互斥问题。

任何想进入临界区的线程，必须先执行加锁操作。若加锁操作顺利通过，则线程可进入临界区；
在完成对临界资源的访问后再执行解锁操作，以释放该临界资源。

根据锁的实现不同，可以分为「忙等待锁」和「无忙等待锁」。

先来看看「忙等待锁」的实现

再来看看「无等待锁」的实现

信号量是操作系统提供的一种协调共享资源访问的方法。

通常 信号量表示资源的数量，对应的变量是一个整型（sem）变量。

另外，还有 两个原子操作的系统调用函数来控制信号量的，分别是：

• P 操作：将 sem 减 1，相减后，如果 sem < 0，则进程/线程进入阻塞等待，否则继续，表明 P 操作可能会阻塞；
• V 操作：将 sem 加 1，相加后，如果 sem <= 0，唤醒一个等待中的进程/线程，表明 V 操作不会阻塞；

举个例子，如果 sem = 1，有三个线程进行了 P 操作：

• 第一个线程 P 操作后，sem = 0；
• 第二个线程 P 操作后，sem = -1；
• 第三个线程 P 操作后，sem = -2；
  
  

这时，第一个线程执行 V 操作后， sem 是 -1，因为 sem <= 0，所以要唤醒第二或第三个线程。

P 操作是用在进入临界区之前，V 操作是用在离开临界区之后，这两个操作是必须成对出现的。

操作系统是如何实现 PV 操作的呢？

PV 操作如何使用的呢？

生产者-消费者问题描述：

• 生产者 在生成数据后，放在一个缓冲区中；
• 消费者 从缓冲区取出数据处理；
• 任何时刻，只能有一个 生产者或消费者可以访问缓冲区；

我们对问题分析可以得出：

• 任何时刻只能有一个线程操作缓冲区，说明操作缓冲区是临界代码，需要互斥；
• 缓冲区空时，消费者必须等待生产者生成数据；缓冲区满时，生产者必须等待消费者取出数据。说明生产者和消费者 需要同步。

那么我们需要三个信号量，分别是：

• 互斥信号量 mutex：用于互斥访问缓冲区，初始化值为 1；
• 资源信号量 fullBuffers：用于消费者询问缓冲区是否有数据，有数据则读取数据，初始化值为 0（表明缓冲区一开始为空）；
• 资源信号量 emptyBuffers：用于生产者询问缓冲区是否有空位，有空位则生成数据，初始化值为 n （缓冲区大小）；

具体的实现代码：

如果消费者线程一开始执行 P(fullBuffers)，由于信号量 fullBuffers 初始值为 0，
则此时 fullBuffers 的值从 0 变为 -1，说明缓冲区里没有数据，消费者只能等待。

接着，轮到生产者执行 P(emptyBuffers)，表示减少 1 个空槽，如果当前没有其他生产者线程在临界区执行代码，那么该生产者线程就可以把数据放到
缓冲区，放完后，执行 V(fullBuffers) ，信号量 fullBuffers 从 -1 变成 0，表明有「消费者」线程正在阻塞等待数据，于是阻塞等待的消费者线程会被唤醒。

当初我在校招的时候，面试官也问过「哲学家就餐」这道题目，我当时听的一脸懵逼，
无论面试官怎么讲述这个问题，我也始终没听懂，就莫名其妙的说这个问题会「死锁」。

当然，我这回答槽透了，所以当场 game over，残酷又悲惨故事，就不多说了，反正当时菜就是菜。

先来看看哲学家就餐的问题描述：

• 5 个老大哥哲学家，闲着没事做，围绕着一张圆桌吃面；
• 巧就巧在，这个桌子只有 5 支叉子，每两个哲学家之间放一支叉子；
• 哲学家围在一起先思考，思考中途饿了就会想进餐；
• 奇葩的是，这些哲学家要两支叉子才愿意吃面，也就是需要拿到左右两边的叉子才进餐；
• 吃完后，会把两支叉子放回原处，继续思考；

那么问题来了，如何保证哲学家们的动作有序进行，而不会出现有人永远拿不到叉子呢？

方案一

方案二

方案三

方案四

前面的「哲学家进餐问题」对于互斥访问有限的竞争问题（如 I/O 设备）一类的建模过程十分有用。

另外，还有个著名的问题是「读者-写者」，它为数据库访问建立了一个模型。

读者只会读取数据，不会修改数据，而写者即可以读也可以修改数据。

读者-写者的问题描述：

• 「读-读」允许：同一时刻，允许多个读者同时读
• 「读-写」互斥：没有写者时读者才能读，没有读者时写者才能写
• 「写-写」互斥：没有其他写者时，写者才能写

接下来，提出几个解决方案来分析分析。

方案一

方案二

方案三

在多线程编程中，我们为了防止多线程竞争共享资源而导致数据错乱，都会在操作共享资源之前加上互斥锁，
只有成功获得到锁的线程，才能操作共享资源，获取不到锁的线程就只能等待，直到锁被释放。

那么，当两个线程为了保护两个不同的共享资源而使用了两个互斥锁，那么这两个互斥锁应用不当的时候，可能会造成 两个
线程都在等待对方释放锁，在没有外力的作用下，这些线程会一直相互等待，就没办法继续运行，这种情况就是发生了 死锁。

举个例子，小林拿了小美房间的钥匙，而小林在自己的房间里，小美拿了小林房间的钥匙，而小美也在自己的房间里。
如果小林要从自己的房间里出去，必须拿到小美手中的钥匙，但是小美要出去，又必须拿到小林手中的钥匙，这就形成了死锁。

死锁只有同时满足以下四个条件才会发生：

• 互斥条件；
• 持有并等待条件；
• 不可剥夺条件；
• 环路等待条件；

互斥条件是指 多个线程不能同时使用同一个资源。

比如下图，如果线程 A 已经持有的资源，不能再同时被线程 B 持有，如果线程 B 
请求获取线程 A 已经占用的资源，那线程 B 只能等待，直到线程 A 释放了资源。

持有并等待条件是指，当线程 A 已经持有了资源 1，又想申请资源 2，而资源 2 已经被线程 C 持有了，
所以线程 A 就会处于等待状态，但是 线程 A 在等待资源 2 的同时并不会释放自己已经持有的资源 1。

不可剥夺条件是指，当线程已经持有了资源 ，在自己使用完之前不能被其他线程获取，
线程 B 如果也想使用此资源，则只能在线程 A 使用完并释放后才能获取。

环路等待条件指的是，在死锁发生的时候，两个线程获取资源的顺序构成了环形链。

比如，线程 A 已经持有资源 2，而想请求资源 1， 线程 B 已经获取了资源 1，
而想请求资源 2，这就形成资源请求等待的环形图。

读取磁盘数据的时候，之所以要发生上下文切换，这是因为用户空间没有权限操作磁盘或网卡，内核的权限最高，这些操作设备
的过程都需要交由操作系统内核来完成，所以一般要通过内核去完成某些任务的时候，就需要使用操作系统提供的系统调用函数。

而一次系统调用必然会发生 2 次上下文切换：首先从用户态切换到内核态，当内核执行完任务后，再切换回用户态交由进程代码执行。

所以，要想减少上下文切换到次数，就要减少系统调用的次数。

在前面我们知道了，传统的文件传输方式会历经 4 次数据拷贝，而且这里面，「从内核的读缓冲区
拷贝到用户的缓冲区里，再从用户的缓冲区里拷贝到 socket 的缓冲区里」，这个过程是没有必要的。

因为文件传输的应用场景中，在用户空间我们并不会对数据「再加工」，
所以数据实际上可以不用搬运到用户空间，因此 用户的缓冲区是没有必要存在的。

在前面我们知道，read() 系统调用的过程中会把内核缓冲区的数据拷贝到用户的缓冲区里，
于是为了减少这一步开销，我们可以用 mmap() 替换 read() 系统调用函数。

mmap() 系统调用函数会直接把内核缓冲区里的数据「映射」到用户空间，这样，操作系统内核与用户空间就不需要再进行任何的数据拷贝操作。

• 应用进程调用了 mmap() 后，DMA 会把磁盘的数据拷贝到内核的缓冲区里。接着，应用进程跟操作系统内核「共享」这个缓冲区；
• 应用进程再调用 write()，操作系统直接将内核缓冲区的数据拷贝到 socket 缓冲区中，这一切都发生在内核态，由 CPU 来搬运数据；
• 最后，把内核的 socket 缓冲区里的数据，拷贝到网卡的缓冲区里，这个过程是由 DMA 搬运的。

我们可以得知，通过使用 mmap() 来代替 read()， 可以减少一次数据拷贝的过程。

但这还不是最理想的零拷贝，因为仍然需要通过 CPU 把内核缓冲区的数据拷贝到 socket 缓冲区里，
而且仍然需要 4 次上下文切换，因为系统调用还是 2 次。

在 Linux 内核版本 2.1 中，提供了一个专门发送文件的系统调用函数 sendfile()，函数形式如下：

它的前两个参数分别是目的端和源端的文件描述符，后面两个参数是源端的偏移量和复制数据的长度，返回值是实际复制数据的长度。

首先，它可以 替代前面的 read() 和 write() 这两个系统调用，这样就可以减少一次系统调用，也就减少了 2 次上下文切换的开销。

其次，该系统调用，可以直接把内核缓冲区里的数据拷贝到 socket 缓冲区里，不再拷贝到用户态。

这样就只有 2 次上下文切换，和 3 次数据拷贝。如下图：

但是这还不是真正的零拷贝技术，如果网卡支持 SG-DMA（The Scatter-Gather Direct Memory Access）技术
（和普通的 DMA 有所不同），我们可以进一步减少通过 CPU 把内核缓冲区里的数据拷贝到 socket 缓冲区的过程。

你可以在你的 Linux 系统通过下面这个命令，查看网卡是否支持 scatter-gather 特性：

于是，从 Linux 内核 2.4 版本开始起，对于支持网卡支持 SG-DMA 技术的情况下， sendfile() 系统调用的过程发生了点变化，具体过程如下：

• 第一步，通过 DMA 将磁盘上的数据拷贝到内核缓冲区里；
• 第二步，缓冲区描述符和数据长度传到 socket 缓冲区，这样网卡的 SG-DMA 控制器就可以直接将内核缓存中的数据拷贝
  到网卡的缓冲区里，此过程不需要将数据从操作系统内核缓冲区拷贝到 socket 缓冲区中，这样就减少了一次数据拷贝；

所以，这个过程之中，只进行了 2 次数据拷贝，如下图：

这就是所谓的 零拷贝（Zero-copy）技术，因为我们没有在内存层面去拷贝数据，
也就是说全程没有通过 CPU 来搬运数据，所有的数据都是通过 DMA 来进行传输。

零拷贝技术的文件传输方式相比传统文件传输的方式，减少了 2 次上下文切换和数据拷贝次数，只需要 2 次上下文切换
和数据拷贝次数，就可以完成文件的传输，而且 2 次的数据拷贝过程，都不需要通过 CPU，2 次都是由 DMA 来搬运。

所以，总体来看，零拷贝技术可以把文件传输的性能提高至少一倍以上。

事实上，Kafka 这个开源项目，就利用了「零拷贝」技术，从而大幅提升了 I/O 的吞吐率，这也是 Kafka 在处理海量数据为什么这么快的原因之一。

如果你追溯 Kafka 文件传输的代码，你会发现，最终它调用了 Java NIO 库里的 transferTo 方法：

如果 Linux 系统支持 sendfile() 系统调用，那么 transferTo() 实际上最后就会使用到 sendfile() 系统调用函数。

曾经有大佬专门写过程序测试过，在同样的硬件条件下，传统文件传输和零拷拷贝文件传输的性能差异，
你可以看到下面这张测试数据图，使用了零拷贝能够缩短 65% 的时间，大幅度提升了机器传输数据的吞吐量。

另外，Nginx 也支持零拷贝技术，一般默认是开启零拷贝技术，这样有利于提高文件传输的效率，是否开启零拷贝技术的配置如下：

sendfile 配置的具体意思:

• 设置为 on 表示，使用零拷贝技术来传输文件：sendfile ，这样只需要 2 次上下文切换，和 2 次数据拷贝。
• 设置为 off 表示，使用传统的文件传输技术：read + write，这时就需要 4 次上下文切换，和 4 次数据拷贝。

当然，要使用 sendfile，Linux 内核版本必须要 2.1 以上的版本。

先复习下 epoll 的用法。如下的代码中，先用 epoll_create 创建一个 epoll 对象 epfd，
再通过 epoll_ctl 将需要监视的 socket 添加到 epfd 中，最后调用 epoll_wait 等待数据。

epoll 通过两个方面，很好解决了 select/poll 的问题。

第一点 ：epoll 在内核里使用 红黑树来跟踪进程所有待检测的文件描述字，把需要监控的 socket 通过 epoll_ctl() 函数加入内核中
的红黑树里，红黑树是个高效的数据结构，增删改一般时间复杂度是 O(logn)。而 select/poll 内核里没有类似 epoll 红黑树这种
保存所有待检测的 socket 的数据结构，所以 select/poll 每次操作时都传入整个 socket 集合给内核，而 epoll 因为在内核维护了
红黑树，可以保存所有待检测的 socket ，所以只需要传入一个待检测的 socket，减少了内核和用户空间大量的数据拷贝和内存分配。

第二点 ：epoll 使用 事件驱动 的机制，内核里 维护了一个链表来记录就绪事件，当某个 socket 有事件发生时，
通过 回调函数，内核会将其加入到这个就绪事件列表中，当用户调用 epoll_wait() 函数时，只会返回有事件发生
的文件描述符的个数，不需要像 select/poll 那样轮询扫描整个 socket 集合，大大提高了检测的效率。

从下图你可以看到 epoll 相关的接口作用：

epoll 的方式即使监听的 Socket 数量越多的时候，效率不会大幅度降低，能够同时监听的 Socket 的数目也
非常的多了，上限就为系统定义的进程打开的最大文件描述符个数。因而，epoll 被称为解决 C10K 问题的利器。

插个题外话，网上文章不少说，epoll_wait 返回时，对于就绪的事件，epoll 使用的是
共享内存的方式，即用户态和内核态都指向了就绪链表，所以就避免了内存拷贝消耗。

这是错的！看过 epoll 内核源码的都知道，压根就没有使用共享内存这个玩意。你可以从下面这份代码看到， 
epoll_wait 实现的内核代码中调用了 __put_user 函数，这个函数就是将数据从内核拷贝到用户空间。

epoll 支持两种事件触发模式，分别是 边缘触发（edge-triggered，ET）和水平触发（level-triggered，LT）。

这两个术语还挺抽象的，其实它们的区别还是很好理解的。

• 使用边缘触发模式时，当被监控的 Socket 描述符上有可读事件发生时，服务器端只会从 epoll_wait 中苏醒一次，即使
  进程没有调用 read 函数从内核读取数据，也依然只苏醒一次，因此我们程序要保证一次性将内核缓冲区的数据读取完；
• 使用水平触发模式时，当被监控的 Socket 上有可读事件发生时，服务器端不断地从 epoll_wait 中苏醒，
  直到内核缓冲区数据被 read 函数读完才结束，目的是告诉我们有数据需要读取；

举个例子，你的快递被放到了一个快递箱里，如果快递箱只会通过短信通知你一次，即使你一直没有去取，它也不会再发送第二条短信提醒你，这个
方式就是边缘触发；如果快递箱发现你的快递没有被取出，它就会不停地发短信通知你，直到你取出了快递，它才消停，这个就是水平触发的方式。

这就是两者的区别：

• 水平触发的意思是只要满足事件的条件，比如内核中有数据需要读，就一直不断地把这个事件传递给用户；
• 而边缘触发的意思是只有第一次满足条件的时候才触发，之后就不会再传递同样的事件了。

如果使用水平触发模式，当内核通知文件描述符可读写时，接下来还可以继续去检测它的状态，
看它是否依然可读或可写。所以在收到通知后，没必要一次执行尽可能多的读写操作。

如果使用边缘触发模式，I/O 事件发生时只会通知一次，而且我们不知道到底能读写多少数据，所以在收到通知后应尽可能地读写数据，
以免错失读写的机会。因此，我们会 循环 从文件描述符读写数据，那么如果文件描述符是阻塞的，没有数据可读写时，进程会阻塞在
读写函数那里，程序就没办法继续往下执行。所以，边缘触发模式一般和非阻塞 I/O 搭配使用，程序会一直执行 I/O 操作，直到系统
调用（如 read 和 write）返回错误，错误类型为 EAGAIN 或 EWOULDBLOCK。

一般来说，边缘触发的效率比水平触发的效率要高，因为边缘触发可以减少 epoll_wait 
的系统调用次数，系统调用也是有一定的开销的的，毕竟也存在上下文的切换。

select/poll 只有水平触发模式，epoll 默认的触发模式是水平触发，但是可以根据应用场景设置为边缘触发模式。

另外，使用 I/O 多路复用时，最好搭配非阻塞 I/O 一起使用，Linux 手册关于 select 的内容中有如下说明：

我谷歌翻译的结果：

简单点理解，就是 多路复用 API 返回的事件并不一定可读写的，如果使用阻塞 I/O， 那么在
调用 read/write 时则会发生程序阻塞，因此最好搭配非阻塞 I/O，以便应对极少数的特殊情况。

一般来说，C 语言实现的是「单 Reactor 单进程」的方案，因为 C 语编写完的程序，运行后就是一个独立的进程，不需要在进程中再创建线程。

而 Java 语言实现的是「单 Reactor 单线程」的方案，因为 Java 程序是跑在 Java 虚拟机
这个进程上面的，虚拟机中有很多线程，我们写的 Java 程序只是其中的一个线程而已。

我们来看看「单 Reactor 单进程」的方案示意图：

可以看到进程里有 Reactor、Acceptor、Handler 这三个对象：

• Reactor 对象的作用是监听和分发事件；
• Acceptor 对象的作用是获取连接；
• Handler 对象的作用是处理业务；

对象里的 select、accept、read、send 是系统调用函数，dispatch 和 「业务处理」是需要完成的操作，其中 dispatch 是分发事件操作。

接下来，介绍下「单 Reactor 单进程」这个方案：

• Reactor 对象通过 select （IO 多路复用接口） 监听事件，收到事件后通过 dispatch 
  进行分发，具体分发给 Acceptor 对象还是 Handler 对象，还要看收到的事件类型；
• 如果是连接建立的事件，则交由 Acceptor 对象进行处理，Acceptor 对象会通过 
  accept 方法 获取连接，并创建一个 Handler 对象来处理后续的响应事件；
• 如果不是连接建立事件， 则交由当前连接对应的 Handler 对象来进行响应；
• Handler 对象通过 read -> 业务处理 -> send 的流程来完成完整的业务流程。

单 Reactor 单进程的方案因为全部工作都在同一个进程内完成，所以实现起来比较简单，不需要考虑进程间通信，也不用担心多进程竞争。

但是，这种方案存在 2 个缺点：

• 第一个缺点，因为只有一个进程，无法充分利用 多核 CPU 的性能；
• 第二个缺点，Handler 对象在业务处理时，整个进程是无法处理其他
  连接的事件的，如果业务处理耗时比较长，那么就造成响应的延迟；

所以，单 Reactor 单进程的方案 不适用计算机密集型的场景，只适用于业务处理非常快速的场景。

Redis 是由 C 语言实现的，在 Redis 6.0 版本之前采用的正是「单 Reactor 单进程」的方案，因为 Redis 业务处理
主要是在内存中完成，操作的速度是很快的，性能瓶颈不在 CPU 上，所以 Redis 对于命令的处理是单进程的方案。

如果要克服「单 Reactor 单线程 / 进程」方案的缺点，那么就需要引入多线程 / 多进程，这样就产生了 单 Reactor 多线程 / 多进程 的方案。

闻其名不如看其图，先来看看「单 Reactor 多线程」方案的示意图如下：

详细说一下这个方案：

• Reactor 对象通过 select （IO 多路复用接口） 监听事件，收到事件后通过 dispatch 进行分发，
  具体分发给 Acceptor 对象还是 Handler 对象，还要看收到的事件类型；
• 如果是连接建立的事件，则交由 Acceptor 对象进行处理，Acceptor 对象会通过 accept 方法 
  获取连接，并创建一个 Handler 对象来处理后续的响应事件；
• 如果不是连接建立事件， 则交由当前连接对应的 Handler 对象来进行响应；
  
  

上面的三个步骤和单 Reactor 单线程方案是一样的，接下来的步骤就开始不一样了：

• Handler 对象不再负责业务处理，只负责数据的接收和发送，Handler 对象通过 read 读取
  到数据后，会将数据发给子线程里的 Processor 对象进行业务处理；
• 子线程里的 Processor 对象就进行业务处理，处理完后，将结果发给主线程中的 Handler 对象，
  接着由 Handler 通过 send 方法将响应结果发送给 client；

单 Reator 多线程的方案优势在于 能够充分利用多核 CPU 的性能，那既然引入多线程，那么自然就带来了多线程竞争资源的问题。

例如，子线程完成业务处理后，要把结果传递给主线程的 Handler 进行发送，这里涉及共享数据的竞争。

要避免多线程由于竞争共享资源而导致数据错乱的问题，就需要在操作共享资源前加上互斥锁，以保证任意
时间里只有一个线程在操作共享资源，待该线程操作完释放互斥锁后，其他线程才有机会操作共享数据。

聊完单 Reactor 多线程的方案，接着来看看单 Reactor 多进程的方案。

事实上，单 Reactor 多进程相比单 Reactor 多线程实现起来很麻烦，主要因为要考虑
子进程 <-> 父进程的双向通信，并且父进程还得知道子进程要将数据发送给哪个客户端。

而 多线程间可以共享数据，虽然要额外 考虑并发问题，但是这远比进程间通信的复杂度低得多，
因此实际应用中也看不到单 Reactor 多进程的模式。

另外，「单 Reactor」的模式还有个问题，因为一个 Reactor 对象承担所有事件的监听和
响应，而且只在主线程中运行，在面对瞬间高并发的场景时，容易成为性能的瓶颈的地方。

要解决「单 Reactor」的问题，就是将「单 Reactor」实现成「多 Reactor」，这样就产生了第 多 Reactor 多进程 / 线程 的方案。

老规矩，闻其名不如看其图。多 Reactor 多进程 / 线程方案的示意图如下（以线程为例）：

方案详细说明如下：

• 主线程中的 MainReactor 对象通过 select 监控连接建立事件，收到事件后通过 Acceptor 
  对象中的 accept 获取连接，将新的连接分配给某个子线程；
• 子线程中的 SubReactor 对象将 MainReactor 对象分配的连接加入 select 继续进行监听，
  并创建一个 Handler 用于处理连接的响应事件。
• 如果有新的事件发生时，SubReactor 对象会调用当前连接对应的 Handler 对象来进行响应。
• Handler 对象通过 read -> 业务处理 -> send 的流程来完成完整的业务流程。

多 Reactor 多线程的方案虽然看起来复杂的，但是实际实现时比单 Reactor 多线程的方案要简单的多，原因如下：

• 主线程和子线程分工明确，主线程只负责接收新连接，子线程负责完成后续的业务处理。
• 主线程和子线程的交互很简单，主线程只需要把新连接传给子线程，子线程无须返回数据，
  直接就可以在子线程将处理结果发送给客户端。

大名鼎鼎的两个开源软件 Netty 和 Memcache 都采用了「多 Reactor 多线程」的方案。

采用了「多 Reactor 多进程」方案的开源软件是 Nginx，不过方案与标准的多 Reactor 多进程有些差异。

具体差异表现在主进程中仅仅用来初始化 socket，并没有创建 mainReactor 来 accept 连接，而是由子进程的 Reactor 来 accept 连接，通过锁来
控制一次只有一个子进程进行 accept（防止出现惊群现象），子进程 accept 新连接后就放到自己的 Reactor 进行处理，不会再分配给其他子进程。