CPU缓存一致性

存储体系结构

计算机存储分了很多层次，扬长避短，有寄存器、L1 cache、L2 cache、L3 cache、主存（内存）和硬盘等。
缓存工作原理：

cache line（缓存行）是缓存进行管理的最小存储单元，也叫缓存块，每个 cache line 包含 Flag、Tag 和 Data ，通常 Data 大小是 64 字节，但不同型号 CPU 的 Flag 和 Tag 可能不相同。从内存向缓存加载数据是按整个缓存行加载的，一个缓存行和一个相同大小的内存块对应。在图中横向是组(Set)，纵向是路(Way)。每一个元素是缓存行(cache line)。

给定addr定位缓存的方式：
1. 首先找到组号：Set Index = (addr >> 6) % M;(左移6位是因为 Block Offset 占 addr 的低 6 位，Data 为 64 字节)
2. 然后遍历所有的路，找到cache line中的tag和addr中tag相等为止，所有路都没有成功那么缓存没有命中
3. 整个缓存容量 = 组数 × 路数 × 缓存行大小
相关shell命令：
1. lscpu
2. getconf -a| grep CACHE
缓存行替换策略，一般是LRU，可以通过位矩阵实现：

算法：首先初始化行列与缓存相同的矩阵，当访问某一个路对应的缓存行的时候，首先把该路对应的所有行置为1，然后把该路对应的所有列置为0；最近最少使用的缓存行对应的矩阵行中1的个数最少最先被替换出去；

例子里面首先是3，因此D3那一行首先都是1，然后把D3那一列变成0；然后是1，那么就把D1那一行都变成1然后把D1那一列都变成0……

缓存一致性协议

单核时代不存在这个问题，但是到了多核时代，引入了缓存一致性的我呢提，如果一个核心修改了缓存行里面的某一个值，那么需要有一种机制保证其他核心能够观察这个修改；

缓存写

从缓存和内存的更新关系来看，分为：

- 写回（write-back）对缓存的修改不会立刻传播到内存，只有当缓存行被替换时，这些被修改的缓存行才会写回并覆盖内存中过时的数据。
- 写直达（write through）缓存中任何一个字节的修改，都会立刻穿透缓存直接传播到内存，这种比较耗时。

从写缓存时 CPU 之间的更新策略来看，分为：

- 写更新（Write Update）每次缓存写入新的值，该核心必须发起一次总线请求，通知其他核心更新他们缓存中对应的值。
- - 坏处：写更新会占用很多总线带宽；
  - 好处：其他核心能立刻获得最新的值。
- 写无效（Write Invalidate）每次缓存写入新的值，都将其他核心缓存中对应的缓存行置为无效。
- - 坏处：当其他核心再次访问该缓存时，发现缓存行已经失效，必须从内存中重新载入最新的数据；
  - 好处：多次写操作只需发一次总线事件，第一次写已经将其他核心缓存行置为无效，之后的写不必再更新状态，这样可以有效地节省核心间总线带宽。

从写缓存时数据是否被加载来看，分为：

- 写分配（Write Allocate）在写入数据前将数据读入缓存。当缓存块中的数据在未来读写概率较高，也就是程序空间局部性较好时，写分配的效率较好。
- 写不分配（Not Write Allocate）在写入数据时，直接将数据写入内存，并不先将数据块读入缓存。当数据块中的数据在未来使用的概率较低时，写不分配性能较好。

MESI协议

MESI协议是⼀个基于失效的缓存⼀致性协议，是⽀持写回（write-back）缓存的最常⽤协议。

为了解决多个核心之间的数据传播问题，提出了总线嗅探（Bus Snooping）策略。本质上就是把所有的读写请求都通过总线（Bus）广播给所有的核心，然后让各个核心去嗅探这些请求，再根据本地的状态进行响应。

四种状态

已修改Modified (M)：缓存⾏是脏的，与主存的值不同。如果别的CPU内核要读主存这块数据，该缓存⾏必须回写到主存，状态变为共享(S).
独占Exclusive (E)：缓存⾏只在当前缓存中，但是⼲净的，缓存数据等于主存数据。当别的缓存读取它时，状态变为共享；当前写数据时，变为已修改状态。
共享Shared (S)：缓存⾏也存在于其它缓存中且是⼲净的。缓存⾏可以在任意时刻抛弃。
⽆效Invalid (I)：缓存⾏是⽆效的。

这些状态信息实际上存储在缓存行（cache line）的 Flag 里。

事件以及状态机

处理器对缓存的请求:
- PrRd：核心请求从缓存块中读出数据；
- PrWr：核心请求向缓存块写入数据。
总线对缓存的请求:
- BusRd：总线嗅探器收到来自其他核心的读出缓存请求；
- BusRdX：总线嗅探器收到另一核心写⼀个其不拥有的缓存块的请求；
- BusUpgr：总线嗅探器收到另一核心写⼀个其拥有的缓存块的请求；
- Flush：总线嗅探器收到另一核心把一个缓存块写回到主存的请求；
- FlushOpt：总线嗅探器收到一个缓存块被放置在总线以提供给另一核心的请求，和 Flush 类似，但只不过是从缓存到缓存的传输请求。

当前状态	事件	响应
M	PrRd	⽆总线事务⽣成状态保持不变读操作为缓存命中
	PrWr	⽆总线事务⽣成状态保持不变写操作为缓存命中
	BusRd	状态变为共享(S)Shared发出总线FlushOpt信号并发出块的内容，接收者为最初发出BusRd的缓存与主存控制器（回写主存）
	BusRdX	状态变为⽆效(I)Invalid发出总线FlushOpt信号并发出块的内容，接收者为最初发出BusRd的缓存与主存控制器（回写主存）
E	PrRd	⽆总线事务⽣成状态保持不变读操作为缓存命中
	PrWr	⽆总线事务⽣成状态变为已修改(M)Modified向缓存块中写⼊修改后的值
	BusRd	状态变为共享(S)Shared发出总线FlushOpt信号并发出块的内容
	BusRdX	状态变为⽆效发出总线FlushOpt信号并发出块的内容
S	PrRd	⽆总线事务⽣成状态保持不变读操作为缓存命中
	PrWr	发出总线事务BusUpgr信号状态转换为已修改(M)Modified其他缓存看到BusUpgr总线信号，标记其副本为为无效(I)Invalid
	BusRd	状态变为共享(S)Shared可能发出总线FlushOpt信号并发出块的内容（设计时决定那个共享的缓存发出数据）
	BusRdX	状态变为⽆效(I)Invalid可能发出总线FlushOpt信号并发出块的内容（设计时决定那个共享的缓存发出数据）
I	PrRd	给总线发BusRd信号其他处理器看到BusRd，检查⾃⼰是否有有效的数据副本，通知发出请求的缓存如果其他缓存有有效的副本，其中⼀个缓存发出数据，状态变为(S)Shared如果其他缓存都没有有效的副本，从主存获得数据，状态变为(E)Exclusive
	PrWr	给总线发BusRdX信号状态转换为(M)Modified如果其他缓存有有效的副本, 其中⼀个缓存发出数据；否则从主存获得数据如果其他缓存有有效的副本, ⻅到BusRdX信号后⽆效其副本向缓存块中写⼊修改后的值
	BusRd	状态保持不变，信号忽略
	BusRdX/BusUpgr	状态保持不变，信号忽略

内存屏障

编译器和处理器都必须遵守重排序规则。在单处理器的情况下，不需要任何额外的操作便能保持正确的顺序。但是对于多处理器来说，保证一致性通常需要增加内存屏障指令。即使编译器可以优化掉字段的访问（例如因为未使用加载到的值），编译器仍然需要生成内存屏障，就好像字段访问仍然存在一样（可以单独将内存屏障优化掉）。

内存屏障只与内存模型中的高级概念（例如 acquire 和 release）间接相关。内存屏障指令只直接控制 CPU 与其缓存的交互，以及它的写缓冲区（持有等待刷新到内存的数据的存储）和它的用于等待加载或推测执行指令的缓冲。这些影响可能导致缓存、主内存和其他处理器之间的进一步交互。

几乎所有的处理器都至少支持一个粗粒度的屏障指令（通常称为 Fence，也叫全屏障），它保证了严格的有序性：在 Fence 之前的所有读操作（load）和写操作（store）先于在 Fence 之后的所有读操作（load）和写操作（store）执行完。对于任何的处理器来说，这通常都是最耗时的指令之一（它的开销通常接近甚至超过原子操作指令）。大多数处理器还支持更细粒度的屏障指令。

LoadLoad Barrier（读读屏障）

指令 Load1; LoadLoad; Load2 保证了 Load1 先于 Load2 和后续所有的 load 指令加载数据。通常情况下，在执行预测读（speculative loads）或乱序处理（out-of-order processing）的处理器上需要显式的 LoadLoad Barrier。在始终保证读顺序（load ordering）的处理器上，这些屏障相当于无操作（no-ops）。
StoreStore Barrier（写写屏障）

指令 Store1; StoreStore; Store2 保证了 Store1 的数据先于 Store2 及后续 store 指令的数据对其他处理器可见（刷新到内存）。通常情况下，在不保证严格按照顺序从写缓冲区（store buffers）或者缓存（caches）刷新到其他处理器或内存的处理器上，需要使用 StoreStore Barrier。
LoadStore Barrier（读写屏障）

指令 Load1; LoadStore; Store2 保证了 Load1 的加载数据先于 Store2 及后续 store 指令刷新数据到主内存。只有在乱序（out-of-order）处理器上，等待写指令（waiting store instructions）可以绕过读指令（loads）的情况下，才会需要使用 LoadStore 屏障。
StoreLoad Barrier（写读屏障）刷新写缓冲区，最耗时

指令 Store1; StoreLoad; Load2 保证了 Store1 的数据对其他处理器可见（刷新数据到内存）先于 Load2 及后续的 load 指令加载数据。StoreLoad 屏障可以防止后续的读操作错误地使用了 Store1 写的数据，而不是使用来自另一个处理器的更近的对同一位置的写。因此只有需要将对同一个位置的写操作（stores）和随后的读操作（loads）分开时，才严格需要 StoreLoad 屏障。StoreLoad 屏障通常是开销最大的屏障，几乎所有的现代处理器都需要该屏障。之所以开销大，部分原因是它需要禁用绕过缓存（cache）从写缓冲区（Store Buffer）读取数据的机制。这可以通过让缓冲区完全刷新，外加暂停其他操作来实现，这就是 Fence 的效果。一般用 Fence 代替 StoreLoad Barrier ，所以事实上，执行 StoreLoad 指令同时也获得了其他三个屏障的效果，但是通过组合其他屏障通常不能获得与 StoreLoad Barrier 相同的效果。
各处理器支持的内存屏障和原子操作：
另外原文中还有写屏障，读屏障读写屏障等详细说明这里不加赘述
单向屏障：

单向屏障 (half-way barrier) 也是一种内存屏障，但它不是以读写来区分的，而是像单行道一样，只允许单向通行，例如 ARM 中的 stlr 和 ldar 指令就是这样。
- stlr 的全称是 store release register，包括 StoreStore barrier 和 LoadStore barrier（场景少），通常使用 release 语义将寄存器的值写入内存；
- ldar 的全称是 load acquire register，包括 LoadLoad barrier 和 LoadStore barrier（对，你没看错，我没写错），通常使用 acquire 语义从内存中将值加载入寄存器；
- release 语义的内存屏障只不允许其前面的读写向后越过屏障，挡前不挡后；
- acquire 语义的内存屏障只不允许其后面的读写向前越过屏障，挡后不挡前
- StoreLoad barrier 就只能使用 dmb（全屏障）代替了。

参考资料

CPU缓存一致性：从理论到实战

CPU缓存一致性笔记

2022-10-19
阅读笔记