缓存一致性协议介绍

    现代计算机都是多核cpu，cpu需要和内存交互，但内存相对cpu的速度实在太慢，于是cpu和内存之间还有cache层，

每个cpu都有属于自己的cache，cache由cache line组成，每个cache line 64位（根据不同架构，也可能是32位或128位），

每个cache line知道自己对应什么范围的物理内存地址，当cpu需要读取某一个内存地址的值时，它会把内存地址传递给一级cache，

一级cache会检查它是否有这个内存地址对应的cache line。如果没有，它会以cache line为单位从内存加载数据(一次加载整个cache line，

这是基于这样一个假设：内存访问倾向于本地化（localized），如果我们当前需要某个地址的数据，那么很可能我们马上要访问它的邻近地址)。

由于每个cpu独立工作，那就会有一个显著的问题：多个cache与内存之间的数据同步该怎么做？

缓存一致性协议就是要解决这个问题，协议有多种，可以分为两类：“窥探（snooping）”协议和“基于目录的（directory-based）”协议，

本文所讲述的MESI协议属于一种“窥探协议“。

窥探协议的基本思想
     所有cache与内存，cache与cache（是的，cache之间也会有数据传输）之间的传输都发生在一条共享的总线上，而所有的cpu都能看到这条总线，

同一个指令周期中，只有一个cache可以读写内存，所有的内存访问都要经过仲裁（arbitrate）。cahce不但与内存通信时和总线打交道，

而且它会不停地窥探总线上发生的数据交换，跟踪其他cache在做什么。所以当一个cache代表它所属的cpu去读写内存时，

其它cpu都会得到通知，它们以此来使自己的cache保持同步。

MESI协议的工作方式
协议中最重要的内容有两部分：cache line的状态以及消息通知机制。
cache line的状态有4个：

Invalid，表明该cache line已失效，它要么已经不在cache中，要么它的内容已经过时。处于该状态下的cache line等同于它从来没被加载到cache中。

Shared，表明该cache line是内存中某一段数据的拷贝，处于该状态下的cache line只能被cpu读取，不能写入，
因为此时还没有独占。不同cpu的cache line都可以拥有这段内存数据的拷贝。

Exclusive，和 Shared 状态一样，表明该cache line是内存中某一段数据的拷贝。
区别在于，该cache line独占该内存地址，其他处理器的cache line不能同时持有它，
如果其他处理器原本也持有同一cache line，那么它会马上变成“Invalid”状态。

Modified，表明该cache line已经被修改，cache line只有处于Exclusive状态才能被修改。
此外，已修改cache line如果被丢弃或标记为Invalid，那么先要把它的内容回写到内存中。

cpu有读取数据的动作，有独占的动作，有独占后更新数据的动作，有更新数据之后回写内存的动作，
根据”窥探协议“的规范，每个动作都需要通知到其他cpu，于是有以下的消息机制：

Read，cpu发起读取数据请求，请求中包含需要读取的数据地址。


Read Response，作为Read消息的响应，该消息可能是内存响应的，也可能是某cpu响应的(比如该地址在某cpu cache Line中为Modified状态，则该cpu必须返回该地址的最新数据)。


Invalidate，cpu发起”我要独占一个cache line，其他cpu请失效对应的cache line“的消息，消息中包含了内存地址，所有的其它cpu需要将对应cache line置为Invalid状态。


Invalidate ACK，收到Invalidate消息的cpu在将对应cache line置为Invalid后，返回Invalid ACK。


Read Invalidate，相当于Read消息+Invalidate消息，即取得数据并且独占它，将收到一个Read Response和所有其它cpu的Invalidate ACK。


Write back，写回消息，即将状态为Modified的cache line写回到内存，通常在该行将被替换时使用。
现代cpu cache基本都采用”写回(Write Back)”而非”直写(Write Through)”的方式。

初始状态，4个cpu的cache line都为Invalid状态（黑色表示Invalid）。

cpu0发送Read消息，加载0x0的数据，数据从内存返回，cache line状态变为Shared。

cpu3发送Read消息，加载0x0的数据，数据从内存返回，cache line状态变为Shared。

cpu0发送Read消息，加载0x8的数据，导致cache line被替换，由于之前状态为Shared，即与内存中数据一致，可直接覆盖，而无需回写。

cpu2发送Read Invalidate消息，从内存返回最新数据，cpu3返回Invalidate ACK，并将状态变为Invalid，cpu2获得独占权，状态变为Exclusive。

cpu2修改cache line中的数据，cache line状态为Modified，同时内存中0x0的数据过期。

cpu1 对地址0x0的数据执行原子(atomic)递增操作，发出Read Invalidate消息，cpu2将返回Read Response(而不是内存)，
包含最新数据，并返回Invalidate ACK，同时cache line状态变为Invalid。最后cpu1获得独占权，cache line状态变为Modified，
数据为递增后的数据，而内存中的数据仍然为过期状态。

cpu1 加载0x8的数据，此时cache line将被替换，由于之前状态为Modified，因此需要先执行写回操作，此时内存中0x0的数据得以更新。