什么是缓存一致性问题 ：单核心与多核

• 纵向：Cache 与内存的一致性问题： 在修改 Cache 数据后，如何同步回内存？
• 横向：多核心 Cache 的一致性问题： 在一个核心修改 Cache 数据后，如何同步给其他核心 Cache？

Cache与内存的一致性问题：缓存写策略

缓存写策略是解决Cache与内存一致性问题的方案

参考之前的文章: Cache原理有设计

多核心Cache的一致性问题：缓存一致性协议与实现方式

多核一致性的问题引入

• 1、Core 1 和 Core 2 读取了同一个内存块的数据，在两个 Core 都缓存了一份内存块的副本。此时，Cache 和内存块是一致的；
• 2、Core 1 执行内存写入操作：
  • 2.1 在写直达策略中，新数据会直接写回内存，此时，Cache 和内存块一致。但由于之前 Core 2 已经读过这块数据，所以 Core 2 缓存的数据还是旧的。此时，Core 1 和 Core 2 不一致；
  • 2.2 在写回策略中，新数据会延迟写回内存，此时 Cache 和内存块不一致。不管 Core 2 之前有没有读过这块数据，Core 2 的数据都是旧的。此时，Core 1 和 Core 2 不一致。
• 3、由于 Core 2 无法感知到 Core 1 的写入操作，如果继续使用过时的数据，就会出现逻辑问题。

多核一致性需要解决的问题：写传播与事务串行化

• 特性 1 - 写传播（Write Propagation）： 每个 CPU 核心的写入操作，需要传播到其他 CPU 核心；
• 特性 2 - 事务串行化（Transaction Serialization）： 各个 CPU 核心所有写入操作的顺序，在所有 CPU 核心看起来是一致。

写广播+事务串行化才能解决一致性，比如CPU0和CPU1对同一个数据都进行了修改，写传播可以保证两次修改可以传播到其他CPU，但是只有事务串行化才能保证即使事务传送到不同核心的顺序不一致也可以保证数据一致。

总线嗅探or目录（写传播方案） + 总线仲裁（事务串行化方案）

嗅探

嗅探（Snooping）作为缓存一致性的最早的主流实现方式，依赖于两个事实：其一，总线作为广播介质，能够把请求变为全局（global）可见，即所有缓存都能同时看到总线上出现了哪个请求；其二，所有的一级缓存和二级缓存都同时密切地监视（嗅探）总线上出现的请求，各自独立并且正确地改变对应缓存行的状态。嗅探的具体工作原理将结合VI协议介绍。

目录

目录（Directory）是缓存一致性的另一种常用的实现方式，依赖于二级缓存来记录缓存行在一级缓存中的分享情况。在以目录方式实现的一致性协议中，任何缓存一致性请求都需要先造访二级缓存中的目录。目录的好处是以点对点的数据传输，取代了嗅探中的全局广播：这一性质在系统的计算核心数量较多时尤为重要。

目录式缓存一致性协议就是通过在全局共享目录中记录每个缓存行在不同核上的状态，确保对于缓存行的修改互斥且能够及时对所有核可见，从而保证了缓存的一致性

总线仲裁

总线的独占性要求同一时刻最多只有一个主模块占用总线，天然地会将所有核心对内存的读写操作串行化。如果多个核心同时发起总线事务，此时总线仲裁单元会对竞争做出仲裁，未获胜的事务只能等待获胜的事务处理完成后才能执行。

什么是缓存一致性协议

多个处理器核心对于同一个缓存行的操作，需要遵循一定的规则，以不同的顺序来完成。而这个规则就是缓存一致性协议（Cache Coherence Protocol）。当一个系统拥有了缓存一致性，它的所有私有缓存就会表现得和一个大的共享缓存一样，即不存在缓存一致性问题。本节将先介绍嗅探和目录的基本概念，然后介绍各种缓存一致性协议。

缓存一致性协议有多种实现方案，包括目录式缓存一致性（Directory-based Cache Coherence）与嗅探式缓存一致性（Snoop-based Cache Co-herence）。缓存一致性是由硬件保证的，其对于上层系统软件是透明的。

MSI协议 （目录+总线仲裁）

基本思想

缓存行的状态可以是独占修改（Modified）、共享（Shared）以及失效（Invalid）

每条缓存行都对应了该目录中的一个目录项，其包含两项内容：用于记录是否有处理器已经修改过这个缓存行的 Dirty Bit （1 表示被修改，0 表示未修改），以及用于记录缓存行的拥有者的 Bit Vector（拥有者对应位被置为 1，其余置为 0）。全局目录、高速缓存与内存三者均通过高速内部互联总线相连。目录式缓存一致性协议就是通过在全局共享目录中记录每个缓存行在不同核上的状态，确保对于缓存行的修改互斥且能够及时对所有核可见，从而保证了缓存的一致性。

状态与事件

1. 独占修改：这个状态代表着当前缓存行在全局只有本地高速缓存中这一份拷贝。因此当前的核心独占该缓存行，可以直接进行读/写操作，不会触发缓存行的状态变化。
2. 共享。这个状态代表当前缓存行在全局可能存在多份拷贝，且本地的拷贝是有效的。因此当前核心可以直接读该缓存行。如果需要写该缓存行，则当前核心需要查找全局共享目录，找到所有拥有该缓存行拷贝的核心，并通知这些核心将缓存行状态转换为失效。之后再设置目录中该项的 DirtyBit 为 1，更新拥有者的 Bit Vector。最后，将本地的缓存行状态转换为独占修改，方能对缓存行进行写操作。
3. 失效。这个状态代表当前缓存行本地的拷贝失效，当前核心不能直接读/写该缓存行。如果需要读缓存行，则应当在目录找到拥有该缓存行的核心，向其索要该缓存行的数据，同时通知该核心将该缓存行状态改为共享。之后更新目录中的 Dirty Bit 为 0，并更新拥有者的 Bit Vector。最后，在本核心中将拿到的缓存行设置为共享之后，方能读取该缓存行。如果需要写该缓存行，则需要通过目录找到所有拥有缓存行的核心，通知它们将该缓存行状态都改为失效。之后才能拿到该缓存行的数据，并更新目录中的状态。最后，将本地的缓存行状态设置为独占修改后，方能写该缓存行。

上面三种情况均为需要访问的缓存行已经在私有高速缓存中。而若需要访问的缓存行不在私有高速缓存中时，该核心将查看全局共享目录，检查该缓存行是否在其他核心上。如果其他核心拥有该缓存的拷贝，则处理流程同缓存行为失效一致。如果其他核心上也没有，则该次访问为缓存不命中（Cache Miss）。此时需要从内存中获取该缓存行，放到本地的高速缓存，同时更新全局的共享目录。而该缓存行状态将根据操作类型为读或写，设置该缓存行状态为共享或独占修改。

MESI协议 （嗅探+总线仲裁）

基本原理

MESI协议是⼀个基于失效的缓存⼀致性协议，是⽀持写回（write-back） 缓存的最常⽤协议。也称作伊利诺伊协议 (Illinois protocol，因为是在伊利诺伊⼤学厄巴纳-⾹槟分校被发明的)。

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

状态

• 已修改Modified (M)：表明 Cache 块被修改过，但未同步回内存；
• 独占Exclusive (E)：表明 Cache 块被当前核心独占，而其它核心的同一个 Cache 块会失效；
• 共享Shared (S)：表明 Cache 块被多个核心持有且都是有效的；
• 无效Invalid (I)：表明 Cache 块的数据是过时的。 这些状态信息实际上存储在缓存行（cache line）的 Flag 里。

在 “独占” 和 “共享” 状态下，Cache 块的数据是 “清” 的，任何读取操作可以直接使用 Cache 数据；

在 “已失效” 和 “已修改” 状态下，Cache 块的数据是 “脏” 的，它们和内存的数据都可能不一致。在读取或写入 “已失效” 数据时，需要先将其它核心 “已修改” 的数据写回内存，再从内存读取；

在 “共享” 和 “已失效” 状态，核心没有获得 Cache 块的独占权（锁）。在修改数据时不能直接修改，而是要先向所有核心广播 RFO（Request For Ownership）请求 ，将其它核心的 Cache 置为 “已失效”，等到获得回应 ACK 后才算获得 Cache 块的独占权。这个独占权这有点类似于开发语言层面的锁概念，在修改资源之前，需要先获取资源的锁；

在 “已修改” 和 “独占” 状态下，核心已经获得了 Cache 块的独占权（锁）。在修改数据时不需要向总线发送广播，能够减轻总线的通信压力。

MESI有两个重要的思想：

• 关键 1 - 阻止同时有多个核心修改的共享数据： 当一个 CPU 核心要求修改数据时，会先广播 RFO 请求获得 Cache 块的所有权，并将其它 CPU 核心中对应的 Cache 块置为已失效状态；
• 关键 2 - 延迟回写： 只有在需要的时候才将数据写回内存，当一个 CPU 核心要求访问已失效状态的 Cache 块时，会先要求其它核心先将数据写回内存，再从内存读取。

事件

• 处理器对缓存的请求:

  • PrRd：核心请求从缓存块中读出数据；
  • PrWr：核心请求向缓存块写入数据。

• 总线对缓存的请求:

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

状态变化

详解讲解

各家 CPU 厂商没有都完全按照 MESI 实现缓存一致性协议，导致 MESI 有很多变种，例 如：Intel 采用的 MESIF 和 AMD 采用的 MOESI，ARM 大部分采用的是 MESI，少部分使 用的是 MOESI 。

MESIF（INTEL）

MESIF 是一个缓存一致性和记忆连贯协议，该协议由五个状态组成：已修改（M），互斥 （E），共享（S），无效（I）和转发（F）。

M，E，S 和 I 状态与 MESI 协议一致。F 状态是 S 状态的一种特殊形式，当系统中有多个 S 时，必须选取一个转换为 F，只有 F 状态的负责应答。通常是最后持有该副本的转换为F，注意 F 是干净的数据。 该协议由 Intel 的 快速通道互联 QPI（QuickPath Interconnect）技术引入，其主要目的是解决“基于点到点互联的非一致性内存访问（Non-uniform memory access，NUMA）处理器系统”的缓存一致性问题，而不是“基于共享总线的一致性内存访问（Uniform Memory Access， UMA）处理 器系统”的缓存一致性问题。

缓存一致性的优化：写缓冲区和失效队列

MESI 协议保证了 Cache 的一致性，但完全地遵循协议会影响性能。因此，现代的 CPU 会在增加写缓冲区和失效队列将 MESI 协议的请求异步化，以提高并行度：

• 写缓冲区（Store Buffer）

由于在写入操作之前，CPU 核心 1 需要先广播 RFO 请求获得独占权，在其它核心回应 ACK 之前，当前核心只能空等待，这对 CPU 资源是一种浪费。因此，现代 CPU 会采用 “写缓冲区” 机制：写入指令放到写缓冲区后并发送 RFO 请求后，CPU 就可以去执行其它任务，等收到 ACK 后再将写入操作写到 Cache 上。

• 失效队列（Invalidation Queue）

由于其他核心在收到 RFO 请求时，需要及时回应 ACK。但如果核心很忙不能及时回复，就会造成发送 RFO 请求的核心在等待 ACK。因此，现代 CPU 会采用 “失效队列” 机制：先把其它核心发过来的 RFO 请求放到失效队列，然后直接返回 ACK，等当前核心处理完任务后再去处理失效队列中的失效请求。

事实上，写缓冲区和失效队列破坏了 Cache 的一致性。 举个例子：初始状态变量 a 和变量 b 都是 0，现在 Core1 和 Core2 分别执行这两段指令，最终 x 和 y 的结果是什么？

1
2
3
4
5
6
7

//core1
a = 1 ;
x = b ;

//core2
b = 2 ;
y = a ;

我们知道在未同步的情况下，这段程序可能会有多种执行顺序。不管怎么执行，只要 2 号指令是在 1 号指令后执行的，至少 x 或 y 至少一个有值。但是在写缓冲区和失效队列的影响下，程序还有以意料之外的方式执行：

可以看到：从内存的视角看，直到 Core1 执行 A3 来刷新写缓冲区，写操作 A1 才算真正执行了。虽然 Core 的执行顺序是 A1 → A2 → B1 → B2，但内存看到的顺序却是 A2 → B1 → B2 → A1，变量 a 写入没有同步给对变量 a 的读取，Cache 的一致性被破坏了。

[1] 浅谈多核系统的缓存一致性协议与非均一缓存访问

[2] 《操作系统 原理与设计》陈海波

[3] MESI协议

[4] 12 张图看懂 CPU 缓存一致性与 MESI 协议，真的一致吗？

[5] MESI动态展示

[6] 带你了解缓存一致性协议 MESI