MESI协议
翻译至https://en.wikipedia.org/wiki/MESI_protocol
EMSI是基于缓存无效化的一致性缓存协议，并且是一种最常见的支持回写式缓存的协议。它也被称为伊利诺伊州协议（由于其在伊利诺伊大学厄本那香槟分校被开发）。回写式缓存和写入式缓存相比可以节约很多的带宽。回写式缓存经常会存在脏状态，而脏状态表明了高数缓存中的数据与主存中的数据不一致。EMSI要求当缓存未命中时并且别的缓存中有该数据，那么缓存和缓存间应该互相传输数据。MESI相对与MSI来说降低了与主存的交互次数，这带来了显著的性能提升。
状态
MESI的四个字母分别代表了四个可以被标记在缓存行上的独立状态。（也就是用2bit来编码）
Modified (M)
当缓存行处于Modified状态时，它表明该缓存行只存在于当前缓存中。并且这个缓存行中的数据是脏数据，也就是说这个缓存行中的数据与主存中的数据不一致。缓存被要求在未来将缓存行的数据写于主存中，但不用立即写入。但如果别的缓存向该缓存请求这个数据，那必须保证该数据写入主存已经完成。当回写回主存完成后，缓存行状态会有Modified变为Shared状态。
Exclusive (E)
当缓存行处于Exclusive状态时，它表明该缓存行只存在于当前缓存中，不过其中的数据与主存中的数据是一致的。当别的缓存向该缓存请求read当前缓存行时，缓存行状态会变成Shared。或者当有write操作时，他会变成Modified状态。
Shared (S)
当缓存行处于Shared状态时，它表明该缓存行可能同时存在与别的缓存中，并且其中的数据与主存中一致。这个缓存行随时可能被丢弃（改变为Invalid状态）。
Invalid (I)
当缓存行处于Invalid 状态时，表明该缓存行是无效的。
对于给定的两个缓存，以下是允许共同存在的状态:
| M | E | S | I | |
|---|---|---|---|---|
| M | ✘ | ✘ | ✘ | ✔ |
| E | ✘ | ✘ | ✘ | ✔ |
| S | ✘ | ✘ | ✘ | ✔ |
| I | ✔ | ✔ | ✔ | ✔ |
当一个缓存中的变量被标记为M状态，那同样拥有这个变量的别的缓存的缓存行会被标记为Invalid。
操作
从一个状态到另一个状态的转变有两个重要影响因素。第一个因素是处理器发出了特殊的读写请求。举个栗子：处理器A的缓存中有变量X，然后这个处理器向自己的缓存发送了对于这个变量的读写请求。第二个影响因素是来自别的处理器的请求，这些处理器缓存中没有这个变量，或者它们想要更新这个变量。这些总线请求被一个名叫Snoopers的监听器监听着。
下面解释不同种类的处理器请求和总线请求
处理器请求包括如下两种：
- PrRd：处理器对缓存中的一个变量发起读请求
- PrWr：处理器对缓存中的一个变量发起写请求
总线请求包括如下五种：
- BusRd：由一个处理器向另一个处理器发出的缓存读请求
- BusRdX：由一个缓存中没有该变量的处理器向另一个处理器发送的缓存写请求
- BusUpgr：由一个缓存中拥有该变量的处理器向另一个处理器发送的缓存写请求
- Flush：有一个处理器将变量写回了主存
- FlushOpt：通知别的处理器修改变量的值（缓存间传值）
如果从主存中获取一个值需要等待的时间比通过缓存间传值等待的时间长，那么我们就可以说缓存间传值可以降低缓存未命中后的读延迟。在多核架构下，一致性主要在二级缓存间保持，但处理器仍然有三级缓存，从三级缓存中获取未命中的变量往往快于从二级缓存。
监控操作：
所有缓存中的变量都拥有四种状态的有限状态机。
对于不同输入的状态转换关系和回复如下表1.1和1.2
| 初始状态 | 操作 | 响应 |
|---|---|---|
| Invalid(I) | PrRd | * 向总线发送BusRd请求 * 别的缓存监听到BusRd请求后检查自己是否有有效的该变量的缓存块，并回复发送请求的缓存 * 状态转换为Shared如果别的缓存有有效的缓存块 * 状态转换为Exclusive，如果所有的缓存都没有有效的该缓存块 *如果别的缓存有有效的缓存块，它们中的一个会发送这个值，否者得从主存中获取 |
| PrWr | * 向总线发送BusRdX请求 * 发出请求的缓存状态变为Modified * 如果别的缓存有这个缓存块，则发送值，否者从主存中获取 * 如果别的缓存有这个缓存块，并且收到了BusRdX请求则将它们的缓存块设为Invalid * 将缓存块的值改为修改值 |
|
| Exclusive(E) | PrRd | * 不发送任何总线请求 * 状态不改变 * 读缓存命中 |
| PrWr | * 不发送任何总线请求 * 状态变为Modified * 写缓存命中 |
|
| Shared(S) | PrRd | * 不发送任何总线请求 * 状态不改变 * 读缓存命中 |
| PrWr | * 向总线发送BusUpgr请求 * 状态改为Modified * 别的缓存收到BusUpgr请求后将他们的缓存块设为Invalid |
|
| Modified(M) | PrRd | * 不发送任何总线请求 * 状态不改变 * 读缓存命中 |
| PrWr | * 不发送任何总线请求 * 状态不改变 * 写缓存命中 |
| 初始状态 | 操作 | 响应 |
|---|---|---|
| Invalid(I) | BusRd | * 无事发生. |
| BusRdX/BusUpgr | * 无事发生 | |
| Exclusive(E) | BusRd | * 状态转化为Shared（） * 向总线发送FlushOpt 请求 |
| BusRdX | * 状态转化为Invalid. * 向总线发送FlushOpt 请求 |
|
| Shared(S) | BusRd | * 无事发生 * 可能向总线发送FlushOpt 请求 (取决与底层设计). |
| BusRdX | * 状态转化为Invalid * 可能向总线发送FlushOpt 请求 (取决与底层设计) |
|
| Modified(M) | BusRd | * 状态转化为Shared * 向总线发送FlushOpt，接受者为BusRd的发送者和主存. |
| BusRdX | * 状态转化为Invalid * 向总线发送FlushOpt，接受者为BusRd的发送者和主存. |
只有写操作发生在Modified或Exclusive状态的缓存行时，才缓存才不需要做额外操作。如果状态为Shared的缓存行被写入，那么首先别的缓存需要无效它们的缓存行。这个由一个叫Request For Ownership (RFO).的广播操作执行。
当一个变量为Modified时，这个缓存必须监听所有别的缓存对于该变量对应主存的读请求，一旦监听到就必须将这个变量写入主存。这个过程可以通过强制让别的缓存等待的方法来完成。当完成了对主存的写入，状态变为Shared。但同样可以直接通知别的缓存这个变量的值，而不写入主存。
当处于Shared状态时，必须监听所有的rfo广播，一旦收到就让缓存中的变量无效。
Modified和Exclusive状态是精确的，当有缓存行处于这个状态就表明，这个变量是这个缓存独有的。而Shared状态时不精确的，当别的缓存丢弃了这个Shared状态的缓存行，那么可能只存在一个缓存行状态为Shared但它不会变为Exclusive。丢弃Shared状态行不会引起别的缓存的注意。
使用Exclusive可以带来性能上的提升，因为修改Exclusive不需要通知别的缓存，而修改Shared状态的缓存行需要告诉别的缓存，并使这些缓存行无效，这是耗时的。（这也是EMSI与MSI协议的区别）
内存屏障
MESI简单直接的实现存在着两个性能问题。1.当向一个Invalid的缓存行写入时，需要从别的缓存获取值，这是很耗时的。2.需要将别的缓存行的该值设置为Invalid这也是耗时的。为了解决这两个问题，我们引入了存储缓冲区和无效化队列。
存储缓冲区
当向一个无效的缓存行写入时会用到储存缓冲区。因为这个写操作最终一定会被执行，因此CPU发送读无效消息（让别的缓存中的该缓存行无效）并且将要写入的值放到存储缓存区中，当这个需要的缓存行写入缓存时，存储缓存区中存储的值将被执行写入。
存储缓存区存在带来的后果是，当一个CPU进行写操作，值不会立即写入缓存中。因此，无论何时CPU读取缓存中的值时，都需要先扫描自己的存储缓冲区，确保缓冲区中是否还有未写入的值。值得注意的时不同CPU之间存储缓冲区时不可见的。
无效化队列
当CPU收到无效请求时，它会将这写无效请求放入无效化队列中。放入队列中的请求会被迅速执行但不是立即执行。所以CPU可以忽略它的缓存块是无效的。CPU不能扫描它的无效队列，这是和存储缓冲区的区别。
可见存储缓冲区带来的是写不同步，而无效化队列则带来读不同步，为了解决这些不同步，我们需要内存屏障。写屏障会刷新我们的存储缓冲区，确保里面所有的写都会被执行到这个CPU的cache上，而读屏障可以保证所有无效化队列里的任务都被执行，确保别的CPU的写对自己可见。
网友评论