0x01. 概述
1. 缓存一致性 (Cache Coherence)
硬件层面的问题，指的是由于多核计算机中有多套缓存，各个缓存之间的数据不一致性问题。一致性如何理解，我觉得 CMU 的一位老师说得不错：All processors see the same view of memory at the same time。缓存一致性协议，如MESI解决是多个缓存副本之间的数据的一致性问题，这些协议可能十分复杂，可能有数十种状态。
2. MESI
MESI协议是一个基于失效的缓存一致性协议，是支持回写（write-back）缓存的最常用协议。因为是在伊利诺伊大学厄巴纳-香槟分校被发明的，所以也被称作伊利诺伊协议 (Illinois protocol）。与写通过（write through）缓存相比，回写缓冲能节约大量带宽。总是有“脏”（dirty）状态表示缓存中的数据与主存中不同。MESI协议要求在缓存不命中（miss）且数据块在另一个缓存时，允许缓存到缓存的数据复制。
0x02. 状态
MESI 存在modified、exclusive、shared和invalid四种状态，协议可以在一个指定的缓存中应用这四种状态。因此，协议在每一个缓存行中维护一个两位的状态tag， 附着在缓存行的物理地址或者数据后。
- modified：处于该状态的缓存行中的数据被当前CPU独占，不在其他CPU缓存中，且为最新的与主存不同的数据，因为数据已经更新，所以
脏位为1，缓存最终有责任将数据写回到内存，并且也应当为其他缓存提供数据，必须在当前缓存缓存其他数据之前完成这些事情。该缓存行写回主存后，状态变为shared。 - exclusive：非常类似于
modified状态，唯一的区别是缓存行的数据还没有被相应的 CPU 修改，这表示缓存行中的数据及内存中的数据都是最新的，所以缓存行的脏位是0。但是，由于 CPU 独占该缓存行，所以能够在任何时刻将数据保存到该行，而不考虑其他 CPU。也就是说，由于内存中的值是最新的，该行可以被直接丢弃而不用回写到内存，也可以为其他缓存提供数据。 - shared：处于该状态的缓存行可能被复制到至少一个其他 CPU 缓存中，这样在没有得到其他 CPU 的许可时，不能向缓存行存储数据。由于
exclusive状态下，内存中的值是最新的，因此可以不用向内存回写值而直接丢弃缓存中的值，或者向其他 CPU 提供值。 - invalid：处于该状态的行是空的，换句话说，它没有保存任何有效数据。当新数据进入缓存时，它替换一个处于
invalid状态的缓存行。这个方法是比较好的，因为替换其他状态的缓存行将引起大量的缓存缺失。
对于任意给定的缓存对，给定缓存行的允许状态如下:
如当一个缓存中的某个块被标记为M（modified）时，其他缓存中的块副本只能被标记为I（Invalid）。
0x03. 协议消息
- Read：该消息包含缓存行需读的物理地址。
- Read Response：该消息包含较早前的
read消息的数据。这个read response消息可能由内存或者其他缓存提供。例如，如果一个缓存请求一个处于modified状态的数据，则缓存必须提供read response消息。 - Invalidate：包含要使无效的缓存行的物理地址。其他的缓存必须从它们的缓存中移除相应的数据并且响应此消息。
- Invalidate Acknowledge：一个接收到
invalidate消息的 CPU 必须在移除指定数据后响应一个invalidate acknowledge消息。 - Read Invalidate：该消息包含要缓存行读取的物理地址。同时指示其他缓存移除数据。因此，它包含一个
read和一个invalidate。read invalidate也需要read response以及invalidate acknowledge消息集。英文亦称read with intend to modify，可理解为读其他缓存的数据，并试图修改当前缓存数据，然后指示其他缓存的数据无效化。 - Writeback：该消息包含要回写到内存的地址和数据。(并且也许会通过窥探器请求检查其他 CPUs 的缓存)。这个消息允许缓存在必要时换出
modified状态的数据以腾出空间。
0x04. 状态转换
一个指定缓存行的状态变化及协议消息发送及接收如下图所示，四个状态共12条转移路径：
本缓存行起始态为modified：缓存行内容为当前缓存所独有的，而且已被修改。
| 标号 | 最终状态 | 描述 |
|---|---|---|
| a | exclusive | 缓存行被写回内存，但是CPU将它保留在缓存中，并进一步保留修改它的权利。此转换需要writeback消息。 |
| c | invalid | CPU 接收到一条read invalidate消息，表示相应的缓存行数据已经在其他CPU缓存中被修改。CPU必须使其本地副本无效，然后响应read response和invalidate acknowledge消息，两者都将发送数据给请求方，表示本 CPU 不再具有本地副本。 |
| f | shared | 其他一些 CPU 读取缓存行，数据由本 CPU 缓存提供，本 CPU 缓存保留只读副本，也可能将其写入内存。此转换由接收read消息开始，本 CPU 使用包含所请求数据的read response消息进行响应。 |
本缓存行起始态为exclusive：缓存内容不存在于其他缓存中，被当前缓存独占，可在不咨询其他缓存的情况下覆盖它。
| 标号 | 最终状态 | 描述 |
|---|---|---|
| b | modified | 本 CPU 将数据写入它已经具有独占访问权的缓存行。此转换不需要发送或接收任何消息。 |
| g | shared | 其他一些 CPU 读取本缓存行中的数据，并且数据是从本 CPU 的缓存或者内存中提供的。在这两种情况下，本 CPU 都保留只读副本。此转换开始于接收到一个read消息，并且本 CPU 响应了一个read response消息。 |
| i | invalid | 其他的 CPU 进行了一个原子读写操作，相应的缓存行被本 CPU 独有。本 CPU 将缓存行变成无效状态。此转换开始于接收到read invalidate消息，并且本 CPU 响应一个read response消息以及一个invalidate acknowledge消息。 |
本缓存行起始态为shared：当前缓存行中的内容在至少一个其他 CPU 缓存中存在副本，即内容被共享。
| 标号 | 最终状态 | 描述 |
|---|---|---|
| e | modified | 本 CPU 进行一个原子读写操作，相应的数据在缓存中是只读的。它必须发送一个invalidate消息，并等待其他 CPU 响应invalidate acknowledge消息集以完成此转换。 |
| h | exclusive | 当前 CPU 将要写入一些数据到缓存行，于是发送一个invalidate消息。直到它接收到所有invalidate acknowledge消息后，CPU 才完成转换。或者其他 CPUs 通过writeback消息将缓存行的数据换出。这样，当前 CPU 就是最后一个缓存该数据的 CPU，自然顺理成章地独占数据。 |
| l | invalid | 其他 CPU 存储一个数据到缓存行，但是由于该缓存行数据也被保存在其他 CPU 缓存中（比如当前CPU的高速缓存），所以它处于只读状态。此转换开始于接收到一个invalidate消息，当前 CPU 响应一个invalidate acknowledge消息。 |
本缓存行起始态为invalid：缓存行的内容无效，或者说缓存行数据块为空，valid状态为0。
| 标号 | 最终状态 | 描述 |
|---|---|---|
| d | modified | CPU 进行一个原子读写操作，相应的数据没有在它的缓存中。它发送一个read invalidate消息，通过read response接收数据。一旦它接收到一个完整的invalidate acknowledge响应集合，CPU 就完成此转换。 |
| j | exclusive | 本 CPU 保存一个数据到缓存行，但是数据还没有在它的缓存行中。因此发送一个read invalidate消息。直到它接收到read response消息以及所有invalidate acknowledge消息后，它才完成转换。 |
| k | shared | 本 CPU 装载一个数据，但是数据还没有在缓存行中。CPU 发送一个read消息，当它接收到相应相应的read response消息后完成转换。 |
0x05. 例子
最初，数据储存在内存的地址 0中。它在一个 4CPU 的系统中的几个直接映射的单行缓存中移动。下表展示了数据流，第一列是操作顺序，第二行表示执行操作的 CPU，第三行表示执行的操作，接下来是四个 CPU 的缓存行状态（MESI 状态在内存地址后面）。最后两列表示相应的内存内容是否是最新的（V为最新， I不是最新）。
- 最初，CPU 缓存行处于
invalid状态，数据在内存中。 - 当
CPU 0从地址 0装载数据，CPU 0中相应的的缓存行进入shared状态，并且内存中的数据是有效的。 CPU 3也从地址 0装载数据，这样其中相应的的缓存行也处于shared状态，并且内存中的数据仍然有效。- 接下来
CPU 0装载其他缓存行 (地址 8)，通过使无效操作强制将地址 0的数据换出缓存，原缓存行中的数据被换成地址 8的数据。 CPU 2装载地址 0的数据，但是该 CPU 发现它将很快就会存储数据，因此它使用一个read invalidate消息以获得一个独享副本。CPU 3缓存中的数据变成无效（但是内存中的数据仍然是有效的）。- 按下来
CPU 2开始预期的存储操作，并将状态改变为modified。内存中的数据将不再是最新的。 CPU 1开始一个原子自增操作，使用一个read invalidate操作从CPU 2的缓存中窥探数据并使之无效，这样CPU 1的缓存变成modified状态（内存中的数据仍然是过期的）。- 最后，
CPU 1从地址 8读取数据，使用一个writeback消息将地址 0数据回写到内存。
0x06. 参考
- 维基百科: MESI协议
- 维基百科: Cache coherence
- Paul E. McKenney: Is Parallel Programming Hard, And, If So, What Can You Do About It?
- 《深入理解并行编程》（第1版，Paul E Mckenney著，谢宝友、鲁阳译，电子工业出版社）
- Computer Architecture - Cache Coherence Protocols (Sundararaman Nakshatra)