Cache Coherence

​ cache coherence 也就是 cache 一致性问题，首先解释下这个问题为什么会存在。

Cache 存在的必要性

​ 众所周知，CPU 频率远大于内存频率，那么具体大多少呢？可以看这篇文章哦~~《CPU到底有多快？内存：是我的250倍》。我记得是拉跨的 CPU 都能在 1/3 ns 内执行完一条简单指令，而一次访存操作至少要 80 ns。

​ 那么我们听到的什么 DDR4-3200-1600MHZ 是什么意思呢？3200 是指传输速率为 3.2Gbit/s，而 1600MHZ 是指接口总线频率，其工作频率实质只有 400MHZ（接口频率是工作频率的 4 倍了）。如果 2GHZ 的 CPU 算接口频率的话，集成PCI-e 3.0控制器的 CPU，接口频率可是 8 GHz；4.0的则是 16 GHz。除此之外，总线也可能造成瓶颈。

​ 由于 CPU 和内存之间存在着处理能力鸿沟，因此 Cache 就应运而生了（访问 cache 大概在 1ns 吧）。

写 Cache 的两种策略：

  • 直写
  • 写回

直写的逻辑：

1
2
3
4
5
6
7
if(数据不在 Cacheline 中) {
    直接写到内存中去;
}
else {
	写 Cacheline;
    写 内存;
}

写回的逻辑：

1
2
3
4
5
6
7
8
9
10
11
if(数据在 Cacheline 中) {
    直接写 Cache;
}
else {
    if(当前 Cacheline 是脏的) {
        将 Cacheline 中的数据写回到内存;
    }
	从内存中加载数据到 Cacheline;
    写 Cacheline;
}
将 Cacheline 标记为脏;

多核导致的 Cache 不一致现象

现有两个核心 A,B，每个核心有自己独属的 Cache。它们都读取一个共享变量 i，并用写回策略对 i 进行 ++ 操作，整个流程可以用下图表示：

由于它们都在 i = 0 时缓存了 i，并对 i 做 ++ 操作，因此最终将会导致 i = 1 而非 2；原因在于 A 核心执行 i++ 后没有将结果同步到 B 核心缓存的 i 变量上面去，也就是 i 这个共享变量的一致性遭到了破坏。

那么如何解决这个问题呢？最简单的想法就是，最好我修改之前看到的变量已经是最新的了，在我修改之后立马让所有核心看到最新的值。

  • 第一点，某个 CPU 核心里的 Cache 数据更新时，必须要传播到其他核心的 Cache，这个称为写传播（Write Propagation）
  • 第二点，某个 CPU 核心里对数据的操作顺序，必须在其他核心看起来顺序是一样的，这个称为事务的串形化（Transaction Serialization）。

MESI 协议 + 总线嗅探机制 实现 写传播和事务串行化

​ 下图是 CPU Cache 的概览图，Cache 可以分成多个 Cacheline，每个 Cacheline 里有一个 Tag 和一个数据块。其实除此之外，还记录了当前 Cacheline 与物理地址之间的映射。Tag 中有四种标记：

  • M: Modified
  • E: Exclude
  • S: Shared
  • I: Invalid

​ 总线嗅探机制，wiki 解释：Bus snooping or bus sniffing is a scheme by which a coherency controller (snooper) in a cache (a snoopy cache) monitors or snoops the bus transactions, and its goal is to maintain a cache coherency in distributed shared memory systems.

How it works? When specific data is shared by several caches and a processor modifies the value of the shared data, the change must be propagated to all the other caches which have a copy of the data. This change propagation prevents the system from violating cache coherency. The notification of data change can be done by bus snooping. All the snoopers monitor every transaction on a bus. If a transaction modifying a shared cache block appears on a bus, all the snoopers check whether their caches have the same copy of the shared block. If a cache has a copy of the shared block, the corresponding snooper performs an action to ensure cache coherency. The action can be a flush or an invalidation of the cache block. It also involves a change of cache block state depending on the cache coherence protocol.

​ 其实上面的意思是当被多个核心中的 Cache 共享的数据将要发生改变时，这个即将发生改变的通知会通过总线广播到所有核心并被 Cache 中的嗅探器捕捉到，随后做出一系列操作来保证 Cache 一致性。所以这里嗅探器其实会查看自己是否拥有这个共享数据，据推断就是通过 Cacheline 与物理地址之间的映射来做判断的。

​ MESI 协议是 cache 一致性协议中的一种，也比较好理解。它借助 Cacheline 中的 Tag 标记以及 总线嗅探机制实现了一个状态机，从而实现写传播和事务串行化。

​ MESI 每一个标记都是一种状态，那么就有 4 种状态；每一种状态下，嗅探器都可能从总线上嗅探到 4 种通知：local read，local write，remote read，remote write（其实就是 local，remote 和 read，write 的排列组合）。某个核心中共享的 Cacheline 会根据自己所处的状态以及嗅探到的通知来进行状态之间的转换：

参考

  1. 《CPU到底有多快？内存：是我的250倍》
  2. 内存运行速度
  3. 10 张图打开 CPU 缓存一致性的大门