概述
MESI（也称伊利诺斯协议）是一种广泛使用的支持 write-back 策略的缓存一致性协议。
MESI 状态
我们假设 CPU 中共有 $k$ 个核； CPU 中每个 cacheline 使用 $4$ 种状态进行标记：
| 状态 | 介绍 | 所有核中该状态的个数 |
|---|---|---|
| MODIFIED | 实际上是 exclusive dirty，说明该核的缓存数据被修改了，且并未写入到更低一层存储中；当某个核的缓存处于该状态时，其余核的对应 cacheline 均为 INVALID | 1 |
| EXCLUSIVE | 实际上是 exclusive clean，说明该核的缓存刚从更低一层存储中读取到了最新的数据；当某个核的缓存处于该状态时，其余核的对应 cacheline 均为 INVALID | 1 |
| SHARED | 实际上是 shared clean，说明多个核的缓存从更低一层存储中读到的数据都是最新的，处于该状态的核的数量一定 $\geq 2$，其余核的对应 cacheline 均为 INVALID | $\geq 2$ |
| INVALID | 说明该核的 cacheline 无效 |
状态切换
我们以四个核为例，用四元组如 $(M, I, I, I)$ 表示四个核的 cacheline 状态，假设只操作第一个核的 cacheline：
执行读操作
- $(M,I,I,I)$ 执行读，状态仍为 $(M, I, I, I)$；
- $(E,I,I,I)$ 执行读，状态仍为 $(E, I, I, I)$；
- $(S,S,I,I)$ 执行读，状态仍为 $(S, S, I, I)$；
- $(I,M,I,I)$ 执行读，将第二个核的 cacheline 的数值 $val$ 写入内存，然后更新第一个核的 cacheline 的值为 $val$，状态切换为 $(S,S,I,I)$；
- $(I,E,I,I)$ 执行读，更新第一个核的 cacheline 为第二个核的数值 $val$，状态切换为 $(S,S,I,I)$；
- $(I,S,S,I)$ 执行读，更新第一个核的 cacheline 为第二个或第三个核的数值 $val$，状态切换为 $(S,S,S,I)$；
- $(I,I,I,I)$ 执行读，从内存中读取对应的地址的数值 $*addr$ 到 cacheline，状态切换为 $(E, I, I, I)$；
执行写操作
- $(M,I,I,I)$ 执行写，状态仍为 $(M, I, I, I)$；
- $(E,I,I,I)$ 执行写，状态变为 $(M, I, I, I)$；
- $(S,S,I,I)$ 执行写，将其他所有状态为 $S$ 的 cacheline 的状态全都设置为 $I$，状态变为 $(M, I, I, I)$；
- $(I,M,I,I)$ 执行写，将第二个核的 cacheline 的数值 $val$ 写入内存（为了防止 ABA 问题），状态变为 $I$，然后更新第一个核的 cacheline 的值为 $val$，再更新值为待写入的值 $write_value$，状态切换为 $(M,I,I,I)$；
- $(I,E,I,I)$ 执行写，更新第一个核的 cacheline 为第二个核的数值 $val$，将第二个核的状态设为 $I$，状态切换为 $(M,I,I,I)$；
- $(M,S,S,I)$ 执行写，更新第一个核的 cacheline 为状态是 $S$ 的 cacheline 的数值 $val$，并将这些状态为 $S$ 的 cacheline 的状态设为 $I$，状态切换为 $(M,I,I,I)$；
- $(I,I,I,I)$ 执行写，将 $write_val$ 写到 cacheline 中，状态切换为 $(E, I, I, I)$；