硬件结构——(4) CPU 缓存⼀致性

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

CPU Cache由多个Cache Line组成，CPU Line(缓存块) 是CPU从内存读取数据 的基本单位，CPU Line由各种 标志+数据块 组成。

对数据的操作 除了读操作，还有写操作。数据写入Cache后，内存与Cache相对应的数据将会不同，之后肯定需要 将Cache中的数据 同步到内存中。

问题：何时将Cache中的数据 写回到内存呢？

下面介绍两种 关于写入数据的方法：

1. 写直达
2. 写回

(1) 写直达：

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

写入前会先判断 数据是否已经在CPU Cache中：

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

虽然写直达 直观、简单，但也存在个问题。无论数据在不在Cache中，每次写操作都会写回到内存，这样的写操作 将会花费⼤量的时间，性能也会受到很大的影响。

(2) 写回：

写直达由于每次写操作 都会把数据写回到内存，从而影响性能。于是为了 减少数据写回内存的频率，就出现了写回的方法。
在写回机制中，当发生写操作时，新的数据仅仅被写入Cache Block中，只有当修改过的Cache Block被替换时 才需要写到内存中。从而减少了 数据写回内存的频率，进而提高了 系统的性能。

• 当发生写操作时，如果数据对应的Block 已经在CPU Cache中，则将数据更新到 CPU Cache中的该Cache Block中，同时标记CPU Cache中的 该Cache Block为脏(Dirty)。这个脏的标记代表 此时CPU Cache中的该Cache Block中的数据被修改过 (此时Cache Block中的数据 和在内存中对应的数据 是不⼀致的)，这种情况"先不急着"将数据写到内存中。
• 当发生写操作时，如果数据所对应的Cache Block中存放的是 别的内存地址的数据 (即要写数据对应的Block 不在CPU Cache中)，则检查该Cache Block中的数据 有没有被标记为脏。(1) 如果被标记为脏，就要先将这个Cache Block中的数据 写回到内存 (在覆盖写 被标记为脏的Block 的时候，必须该Block中的数据 写回到内存)，然后再将当前要写入的数据 写入该Cache Block中，同时也将该Cache Block 标记为脏；(2) 如果没有被标记为脏，则直接将数据写入 该Cache Block中，同时也将该Cache Block 标记为脏。

由上可知，将数据写入到Cache时，只有在 缓存不命中(即要写数据对应的Block 不在CPU Cache中) 且数据对应在CPU Cache中的Cache Block标记为脏 的情况下，才会将数据写到内存中；在缓存命中的情况下，则只需将数据 写入对应Cache Block，再将该Cache Block 标记为脏。
优点：如果大量的写操作都能够命中缓存，那么大多数情况下 CPU都不需要读写内存，所以写回的性能 相比写直达更高。

现代CPU都是多核的，因为 L1/L2 Cache 是多个核心各自独有的，也因此带来了 多核心的缓存⼀致性 的问题。如果不能保证 缓存的⼀致性，就可能造成错误。
问题：缓存⼀致性的问题 具体是怎样发生的？

举例：下面将以 ⼀个含有两个核心的CPU 作为例子。假设 A号核心和B号核心 同时运行两个线程，都操作共同的变量 i (初始值为0)。

A号核心执行了 i++后，先将值为1的执行结果 写入到L1/L2 Cache中，然后将L1/L2 Cache中对应的Block 标记为脏。（此时数据还没有 被同步到内存中的。根据写回策略，只有在A号核心中的该Cache Block 要被替换时，数据才会被写入到内存中。
如果此时B号核心 从内存读取 变量i 的值，则将会读到错误的值，因为之前A号核心更新 变量i 的值 还未写入到内存中，所以内存中的 变量i 的值依然是0。

这就是所谓的 缓存⼀致性问题，此时 A号核心和B号核心的缓存中的变量i 是不一致的，从而将导致错误的执行结果。

要解决这⼀问题，就需要⼀种机制，来同步两个不同核心中的缓存数据。首先需要保证 做到以下两点：

1. 某个CPU核心中的 Cache数据更新时，必须要传播到 其他核心的Cache，这个过程称为写传播；
2. 某个CPU核心中对数据的操作顺序 必须在其他核心看来 顺序是⼀样的，这个过程称为事务的串形化。

(1) 写传播 容易理解，当某个核心在Cache中 更新数据时，需要将更新后的数据 同步到其他核心的Cache中。
(2) 事务的串形化，我们举个例⼦来理解它。
举例：假设有⼀个 含有4个核心的CPU，这4个核心都操作 共同的变量 i (初始值为0)。A号核心先将 变量i 的值变为100，与此同时，B号核心把 变量i 的值变为200。这两个对 变量i 的修改，都会"传播"到 C和D号核心。

可能出现的问题：如果C号核心先收到 A号核心更新数据的事件，再收到B号核心更新数据的事件，因此C号核心看到的 变量i 是先变成100，后变成200。而如果D号核心 收到的事件是反过来的，则D号核心看到的 变量i 是先变成200，再变成100。虽然做到了写传播，但是各个核心的Cache中的数据 依旧是不一致的。

因此，还需要保证 C号核心和D号核心 都能看到 相同顺序的数据变化。（比如：变量i 都是先变成100，再变成200，这样的过程就是 事务的串形化）

实现事务的串形化，需要做到两点：

1. CPU核心对Cache中的数据 的操作，需要同步给 其他CPU核心。
2. 引入 "锁" 的概念。如果两个CPU核心中 有包含相同数据的Cache，那么对于这个Cache中的数据 的更新，只有在拿到"锁"的情况下 才能进行。

写传播的原则就是，当某个CPU核心更新了 Cache中的数据后，就要把该事件 广播通知到其它核心。最常见的实现方式是 总线嗅探。
举例：当A号CPU核心 修改了L1 Cache中的 变量i 的值后，通过总线将这个事件 广播通知给其它所有的CPU核心，每个CPU核心都会监听 总线上的⼴播事件，并检查是否有相同的数据 在自己的L1 Cache中，因为B、C、D号CPU核心的L1 Cache中 也有该数据，所以也需要将该数据 更新到自己的L1 Cache中。

• 优点：总线嗅探方法很简单， CPU只需要每时每刻 监听总线上的⼀切活动。
• 缺点：因为不管别的核心的Cache 是否缓存相同的数据，每次更新数据 都需要发出⼀个广播事件，这无疑会 加重总线的负载。另外，总线嗅探只是保证了 某个CPU核心的Cache更新数据的这个事件 能被其它CPU核心知道，但是并不能保证 事务的串形化。

于是，有⼀个协议基于总线嗅探机制 实现了事务的串形化，也使用了状态机机制 来降低总线带宽的压力，最终做到了 CPU缓存⼀致性，这个协议就是 MESI 协议。

4. MESI 协议

MESI协议 也是4个状态单词的开头字母的缩写 (这四个状态用来标记 Cache Line的四个不同的状态)，分别是：

1. Modified - 已修改
2. Exclusive - 独占
3. Shared - 共享
4. Invalidated - 已失效

• 已修改状态 就是前面提到的 "脏"标记，表示该Cache Block上的数据 已经被更新过，但还未写到内存中。
• 已失效状态 表示该Cache Block中的数据 已经失效了，不可以读取该状态的数据。

独占状态 和 共享状态 都表示Cache Block中的数据是干净的。也就是说，此时Cache Block中的数据 和内存中的数据是⼀致的。
独占状态 和 共享状态 的差别在于：

• 独占状态时：数据只存储在 ⼀个CPU核心的Cache中，而其它CPU核心的Cache中 没有该数据。此时，如果要向独占的Cache中写数据，就可以直接自由地写入，而不需要通知其它CPU核心 (因为独有这个数据，所以就不存在 缓存⼀致性的问题)。另外，在独占状态下的数据，如果有其它核心从内存读取相同的数据 到各自的Cache ，那么此时 独占状态下的数据 就会变成共享状态。
• 共享状态时：相同的数据存储在 多个CPU核心的Cache中。所以当我们要 更新Cache中的数据时，不能直接修改，而是要先向所有其他CPU核心 广播⼀个请求，要求先将其他CPU核心的Cache中 对应的Cache Line标记为无效状态，然后再更新 当前Cache中的数据。

举个具体的例子来观察 这四个状态的转换：

(1) 当A号CPU核心 从内存读取 变量i 的值时，数据被缓存到 A号CPU核心自己的Cache中，因为此时其他CPU核心的Cache 没有缓存该数据，所以标记Cache Line的状态为 独占状态，此时其Cache中的数据与内存 是⼀致的。
(2) 然后B号CPU核心 也从内存中读取了 变量i 的值，此时会发送消息 给其它CPU核心，由于A号CPU核心 已经缓存了该数据，所以会把数据返回给 B号CPU核心。在这个时候，A核心和B核心 缓存了相同的数据，Cache Line的状态也因此变为 共享状态，并且其Cache中的数据 与内存中的数据是⼀致的。
(3) 当A号CPU核心 要修改Cache中的 变量i 的值时，发现数据对应的 Cache Line的状态为共享状态，则要向其它所有的CPU核心 广播⼀个请求，要求先把其他核心的Cache中 对应的Cache Line标记为 无效状态，然后A号CPU核心 才更新Cache中的数据，同时标记Cache Line为 已修改状态，此时Cache中的数据 与内存中的数据是不⼀致的。
(4) 如果A号CPU核心 继续修改Cache中 变量i 的值，由于此时的Cache Line是 已修改状态，因此不需要给其他CPU核心 发送消息，直接更新数据即可。
(5) 如果A号CPU核心的Cache中的 变量i 对应的Cache Line要被替换，发现Cache Line状态是 已修改状态，就会在替换前 先将数据同步到内存。

可以发现，当Cache Line状态为 已修改状态 或 独占状态 时，更新其数据 不需要发送⼴播 给其它CPU核心，因此⼀定程度上 减小了总线带宽的压⼒。

整个MESI的状态 可以用⼀个有限状态机 来表示它的状态变迁。（对于不同状态 触发的事件操作，可能来自本地CPU核心 发出的广播事件，也可能来自其他CPU核心 发出的广播事件）

 MESI协议的四种状态之间的 状态转移过程 汇总到如下表格：