什么是并发 Part 2：缓存一致性
目录
本文中会出现 ARM64 汇编代码。
如果对文中使用的语法有不理解的地方，可以在Aarch64 汇编速览一文中查找对应的解释。
引言
首先我们来看一段 C 代码：
int max_index(int *list, int len) {
int result = -1;
int max = 0;
for (int i = 0; i < len; i++) {
if (result < 0 || list[i] > max) {
max = list[i];
result = i;
}
}
return result;
}
这段代码不过是找出数组中最大元素所在索引位置的函数，没有什么特别的。
现在我们来看 gcc 编译器对这个函数的汇编形式的输出：
max_index:
.LFB0:
.cfi_startproc // 上下文环境保存
sub sp, sp, #32
.cfi_def_cfa_offset 32
str x0, [sp, 8] // sp[8] -> int *list;
str w1, [sp, 4] // sp[4] -> int len;
mov w0, -1 // sp[20] -> int result = -1;
str w0, [sp, 20] //
str wzr, [sp, 24] // sp[24] -> int max = 0;
str wzr, [sp, 28] // sp[28] -> int i = 0;
b .L2 // goto .L2
.L5:
ldr w0, [sp, 20] // if (sp[20] < 0) {
cmp w0, 0 // goto .L3
blt .L3 // }
ldrsw x0, [sp, 28] // if (sp[8][sp[28]] > sp[24]) {
lsl x0, x0, 2 // goto .L4
ldr x1, [sp, 8] // }
add x0, x1, x0 //
ldr w0, [x0] //
ldr w1, [sp, 24] //
cmp w1, w0 //
bge .L4 //
.L3:
ldrsw x0, [sp, 28] // sp[24] = sp[8][sp[28]]
lsl x0, x0, 2 //
ldr x1, [sp, 8] //
add x0, x1, x0 //
ldr w0, [x0] //
str w0, [sp, 24] //
ldr w0, [sp, 28] // sp[20] = sp[28];
str w0, [sp, 20] //
.L4:
ldr w0, [sp, 28] //
add w0, w0, 1 // sp[28]++;
str w0, [sp, 28] //
.L2:
ldr w1, [sp, 28] // if (sp[28] < sp[4]) {
ldr w0, [sp, 4] // goto .L5
cmp w1, w0 //
blt .L5 // }
ldr w0, [sp, 20] // return result;
add sp, sp, 32 // 上下文环境恢复
.cfi_def_cfa_offset 0
ret
.cfi_endproc
看到笔者手写的反编译 C 注释，读者可能会对如此多的 sp 数组的下标引用感到奇怪。
即使这些下标引用全都对应的是局部变量访问，在反汇编的函数入口
处也写出了各个索引所对应的局部变量名，但是笔者仍然选择使用 sp 索引来指代这些变量。
读者在反汇编代码中遇到的阅读困难，正是这段代码在 CPU 上执行时会遇到的困难——大家
可能已经注意到了在汇编代码中多到不自然的大量 str 与 ldr 指令。
局部变量在被引用后被立即通过内存写入指令写回到了栈上；而局部变量在被使用时，一
次又一次地被从栈上读取出来。
即使 CPU 上空闲的寄存器数量远远超过了这个函数执行所需要的局部变量数量，编译器仍然 选择了使用内存完成所有局部变量读写。
接下来我们再看这个函数使用 O1 优化标记进行编译的结果：
max_index:
.LFB11:
.cfi_startproc
mov x3, x0
cmp w1, 0
ble .L6
sxtw x2, w1
mov x1, 0
mov w4, 0
mov w0, -1
b .L5
.L3:
mov w0, w1
ldr w4, [x3, x1, lsl 2]
.L4:
add x1, x1, 1
cmp x1, x2
beq .L1
.L5:
tbnz w0, #31, .L3
ldr w5, [x3, x1, lsl 2]
cmp w5, w4
ble .L4
b .L3
.L6:
mov w0, -1
.L1:
ret
.cfi_endproc
这一次，即使我不提供反汇编注释读者也能发现，输出结果中一次 sp 访问也没有，str 与
ldr 指令也是一条都没有。这说明 gcc 的汇编器是清楚这个函数是可以在无内存操作
的情况下执行完的。
编译器的优化总是采用最保守策略——如果不能证明一种优化在所有情况下都能产出正确的效果， 那这种优化就不会被采用。换言之，未优化版本的输出里，那些频繁的内存操作在某些情况 下是必要的，所以必须将这部分行为作为编译器的默认输出模式在未优化的编译结果中输出。
只有到了开启优化后，对代码进行语义上的分析，才能确定这些栈内存访问是否可以去掉。
本文的目的，是介绍这些看似冗余的内存访问操作背后，所对应的机制。
缓存一致性
为了加快 CPU 的计算效率，现代的设计会给 CPU 加上数据缓存区域。当 CPU 需要进行内存 中的数据的访问时，就会先在缓存中寻找是否已经存有该地址所对应的数据块。如果有，就 直接使用缓存中的数据；如果没有，就会从内存中加载数据到缓存中，这样下一次再需要 访问这个数据时，就暂时不需要再访问内存了。
缓存的读写速度，要比内存快得多，但是为了保持这样的优势，缓存的储存大小做不大。 因此现在的多核 CPU 中，为每个核心安排了一个独立缓存，而不是使用一个大缓存在所有核心间 共享。
但是这也带来了一个问题——各个核心专属缓存中的数据，其它核心是无法读取到的，必须要 提供一种机制来让核心各自的成果在多个核心之间流动。
缓存一致性的要求如下：
- 一个核向某一地址写入数据后，如果没有其它核向该地址写入过数据，那么该核对此地址 进行读取操作时，必须要读取到该核最近一次写入的数据。
- 在核 1 向内存中写入数据足够长时间后，核 2 对该地址进行读操作，并且这一组了写、 读之间该地址上没有发生过别的写入操作，那么核 2 应该读取到核 1 写入的内容。
- 所有核心对同一地址上发生过的写入操作的顺序感知应该是一致的。
前两条要求很容易理解，第三条要求在任务并发执行时也非常重要。我们来看下面的例子：
void task_a(int *lock) {
*lock = 1; // 步骤 a1
while (*lock != 1) { // 步骤 a2
;
}
*lock = 1; // 步骤 a3
}
void task_b(int *lock) {
*lock = 0; // 步骤 b1
while (*lock != 0) { // 步骤 b2
;
}
*lock = 0; // 步骤 b3
}
现在 task_a 与 task_b 使用同一个整数指针进行调用，并且在不同的核心上同时运行。
设想步骤 a1 与 b1 都很快完成了对核心缓存上数据的写入，并开始向内存中同步数据。
结果 task_b 因为接收到 task_a 的通知比自身进行数据写入更晚，就认为 *lock
的最终取值应该是 1；而 task_a 也因为同样的理由认为 *lock 的值应该是 0。最终 task_a
与 task_b 都在等待对方解除锁定，程序陷入完全挂起状态。
只要能保证两个核心上对于内存写入操作的排序是一致的，就不会出现这样的问题。
基于嗅探的写入更新
嗅探指的是 CPU 核心监听内存总线上的写入指令发生，每当发生写入操作时，就触发缓存 中的某些操作。
在这一种缓存一致性保持方案中，每当一个核心对内存进行写入时，其它核心的缓存中如果 有包含目标地址的块，就从内存中加载新写入的数据对旧缓存块进行更新。
写入更新作为一种缓存同步协议，对内存总线通信的压力太大了。为了减少频繁的数据写入 操作在内存总线上成为瓶颈限制 CPU 效率，作出以下两点优化：
- 为了减少写操作触发的更新操作数量，各个核心应该采用懒惰更新的形式写入内存。给 缓存中的每个数据条目添加脏标，一个内存地址被修改过后，对应条目脏标就改为 1。当被 标脏的数据块要被从缓存块中移除时，处理器就将该块中的数据写入到内存后再移除。
缓存条目中有脏标的核心，在嗅探到其它核心要对标脏的内存地址进行读操作时，该核心 直接在总线上返回缓存中的数据，只有这一核心上的数据才代表了该内存地址的最近状态。 2. 一个内存地址经常是不需要被多个核心同时访问的，能够确定只在一个核上出现的数据 即使发生变化也不会触发其它核的缓存更新，也就不需要占用内存总线进行广播。
给各个缓存条目添加分享标记，每当核心监听到其它核的内存读、写时，如果操作目标地址 在自身缓存中有对应条目，就通知进行操作的核心。双方同时将该地址对应的缓存条目标记为 共享条目。当核心对被共享的条目所对应的地址进行写入操作时，就需要在内存总线上通过 广播通知其它核心进行更新。
如果在访问一个内存地址时，没有其它核心示意该地址出现在自身的缓存中，则说明该 地址被当前核心独占。对该地址进行的读写操作只需要发生在当前核心的缓存上，不需要 通过内存总线对外广播。
基于嗅探的缓存作废
缓存作废，指的是当一个核心上发生对地址 A 的写入操作时，其它所有核心检测到该写入 操作，就将自身缓存中对应地址 A 的条目标记为过期。当核心尝试读取地址 A 的数据，而 对应的缓存条目已过期时，核心就放弃缓存条目，重新从内存中加载对应数据。
在这一方案中，我们仍然可以采用在写入更新操作中使用过的优化，给所有的缓存条目添加 上脏标与分享标记。
核心只有在对已经被标记为共享地址的缓存条目进行修改时，才需要通知其它核心将旧缓存作废； 核心将修改过的缓存条目标记为脏但不直接写入内存，在嗅探其它核心要读取该地址时，就 取消真实的内存操作，直接从缓存中将数据返回给发起请求的核。
在这种方案中，缓存有 3 种基本的数据状态：
I- Invalid，内存地址在缓存中没有对应的条目，或者地址对应的条目已经过期。M- Modified，缓存条目在当前核心上发生了修改。S- Shared，该条目对应的内存地址在其它核心上也存在。
所有的条目的状态均是从 I 开始的。
当核心第一次将数据条目移入到缓存时，如果是进行写操作，条目被标记为 M 状态；如果
是进行读取操作，条目就被标记为 S 状态。
在 M 状态下，如果监听到内存总线上发生了对该地址新的写操作，该核心就必须将其它
核心的写入操作延后，先将自己缓存中的数据写入到内存中，再进行其它核心的写操作。
经过这样的操作后，M 状态变成 I 状态。
并且 M 状态的条目要被从缓存中移除时，需要先将其内容写入到内存中。
当总线上发生了针对一个 M 状态条目的读取操作时，持有 M 状态条目的核心就在总线
上将数据分享出去。M 状态条目所在核心与发起读取操作的核心，共同将该条目标记为
S 状态。
在此过程中，由于 M 状态被去除，持有 M 状态条目的核心应当对条目进行一次内存
写入，以确保内存与缓存对“没有修改”的状态认知是一致的。
在所有状态中，只有 M 状态能够在其它核心进行读操作时向外提供自身缓存里的数据。
这一点是会引起一个问题。
当核心 2 发起读取，核心 1 对外提供了自己 M 状态的缓存条目后，核心 1、2 的条目
一同进入 S 状态后，如果核心 3 要进行读操作就没有核心能够给核心 3 提供缓存中的
数据了，核心 3 只能从内存中获取数据。这很显然会引起效率的降低。
为此，可以添加一个新状态：O - Owned，表示该地址在多个核心上有缓存条目，但是当前
核心负责进行该条目的分发。
当一个 M 状态的条目在别的核心上出现了读取请求时，M 状态的条目就变为 O 状态。
而发起读取请求的核心上，这一条目的状态是 S。原本在 M 转变为 S 操作时需要
进行的内存写入操作，可以延迟到 O 状态条目被从缓存中移除时进行。
和使用写入更新协议时一样，很多数据并没有在多个核心中分享。大多数时候，对数据进行修改时
是不需要对外进行广播的。为此，新添加一个状态 E - Exclusive，表示数据是被单个核独占，
在对这样的条目进行修改时不需要对外广播缓存作废信息。
对 I 状态的条目对应的地址进行读取时，如果没有其它核心提供该数据，那么条目进入到
缓存中后，就标记为 E 状态。
对 E 状态的条目进行读操作不改变其状态，对其进行写操作则直接将其改变为 M 状态。
当有其它核心需要读取该地址的数据时，E 条目就可以通过总线共享给其它核心，并且
数据的授受双方都将条目变更为 S 状态。
写入更新协议相比，写入作废协议在多个核心轮流进行读、写操作时，对总线通信的使用较 少；写入更新协议在多个核心，一方负责提供数据，另一方负责读取数据时，对总线通信 的使用较少。
但是有一个决定性的差别导致了写入更新协议很少被使用。
在一个进程执行时，其线程调度是不会保证同一线程总在某一个核心上执行的。如果一个 线程在核心 1 上执行一段时间，经过休眠后重新在核心 2 上恢复执行，那么它在新的执行 流程中触发的缓存更新写入，很有可能都是自己在核心 1 上遗留的旧缓存条目的更新。 这样的操作既没有正面作用，还会占用内存总线影响其它的核心访问内存。
所以在现在大多数的硬件上，都是采用缓存作废机制。
基于目录的同步
基于嗅探的缓存一致性协议里，内存总线将会是一个瓶颈。当 CPU 的核心数量过多时，CPU 能够进行的内存操作数量就会渐渐超过总线最大承载量，多核的优势就无法发挥出来。
基于目录的缓存同步是通过分散缓存状态的管理硬件，以及使用点对点通信替代广播来提高 CPU 的内存操作吞量。
和缓存中的条目一样，一个目录管理的也是一个内存地址段。缓存中的一个条目，就对应 目录中的一个条目。
每个目录与所有核心之间都有直接的连接。当核心需要对内存进行访问时，首先确定的是目 标地址处于哪一个目录的管辖之下，随后将访问请求发送给对应的目录。对应的目录将进行 实际的数据操作，并将必要的结果返回给请求发起方。
当目录在进行数据操作时，只会与缓存中出现了受影响地址的核心进行沟通。在目录的 每一个条目中，都记录以下两种信息：
- 该条目所对应的缓存条目是否已被修改。
- 所有核心中，有哪些核心缓存中包含有该条目所对应的数据块。
比如在一个有 8 核心的系统上，目录条目 0b0 0100 1000 可以用于表示：
- 该条目对应的数据块在缓存中没有被修改过，因为最高位是 0。
- 该条目对应的数据块，被第 2、第 5 核心共享，这是
0100 1000中两个 1 位对应的 核心。
在缓存侧，仍然采用缓存作废协议，使用 MOESI 状态来管理缓存块。
下面是使用目录进行同步管理的一个简短的例子（从不同核心发起的去往不同目录的请求是 可以同时进行的）：
sequenceDiagram
participant 核心 1
participant 核心 2
participant 核心 3
participant 目录 1
participant 目录 2
participant 内存
核心 1->>目录 1: 读取 0x1000
核心 2->>目录 2: 读取 0x2000
目录 1->>内存: 获取 0x1000 所在块的数据
目录 2->>内存: 获取 0x2000 所在块的数据
目录 1->>核心 1: 以 E 状态发送 0x1000 所在块的数据
目录 1->>目录 1: 记录核心 1 持有 0x1000 所在的块
目录 2->>核心 2: 以 E 状态发送 0x2000 所在块的数据
目录 2->>目录 2: 记录核心 2 持有 0x1000 所在的块
核心 3->>目录 2: 读取 0x2000
目录 2->>核心 2: 获取 0x2000 的数据块，通知需要修改该缓存块状态为 S
核心 2->>目录 2: 返回数据
目录 2->>核心 3: 以 S 状态发送 0x2000 所在块的数据
核心 1->>目录 2: 向 0x2000 写入数据
目录 2->>目录 2: 发现核心 2 与核心 3 持有 0x2000 所在块对应的缓存
目录 2->>核心 2: 要求将 0x2000 所在块标记为 I 状态
目录 2->>核心 3: 要求将 0x2000 所在块标记为 I 状态
核心 2->>目录 2: 完成修改
核心 3->>目录 2: 完成修改
目录 2->>目录 2: 将 0x2000 对应的条目标脏
目录 2->>核心 1: 以 M 状态返回 0x2000 所在块完成写入操作后的数据
尾声
在 CPU 中，不同核心之间为了保持数据的互通需要确立特定的机制，用来将核心私有的缓存 中储存的数据同步到所有核心都可以访问到的空间中。
回应引言中给出的代码样例，所有将函数局域变量写入到内存中的行为，保证了所有的核心 都可以通过内存访问到完全相同的数据。在优化版本的代码中，编译器确认了这些变量并 没有在线程中进行共享，便将所有的内存访问都改换成了核心私有的寄存器的访问。
通过感知其它核心的读写操作，一个核心可以主动从自己的缓存中取出数据，提供给其它核心 来减少真正需要对内存进行访问的次数。
通过给缓存中不同的数据块添加状态标记，我们可以识别一个数据块是否需要在被替换时 将其数据返写到内存；是否需要在修改该数据块时，对其它核心进行通知；让单线程运行 的程序在对数据进行修改时，无需承担广播修改行为的负担。
通过将嗅探替换为分布式的、记录各个数据块在核心中分布方式的目录，来去除协议对总线 代宽的强要求，提高系统中整体的数据访问吞吐量。
而以上提到的这些协议，不仅仅可以用于 CPU 的缓存管理，还可以推广到分布式的数据系统 中不同主机间的数据交流与管理。
本次关于缓存一致性处理的介绍就到此结束。