多核程序设计——缓存一致性协议MESI

MESI协议

    在MP系统中，每个CPU都有自己独立的cache，缓存之间的一致性很很容易受到破坏的，所以缓存一致性协议就应运而生了。MESI是一种使用非常广泛的缓存一致性协议。

    MESI存在”modified”,”exclusive”,”shared”和”invalid”四种状态，协议可以在一个指定的缓存中应用这四种状态。因此，协议在每一个缓存行中维护一个两位的状态”tag”，这个”tag”附着在缓存行的物理地址或者数据后。

• 处于“ modified” 状态的缓存行是由于相应的 CPU 最近进行了内存存储。并且相应的内存确保没有在其他 CPU 的缓存中出现。下边的图有一些误导嫌疑，可以把“叉”看做是invalid状态。这些图是《大话处理器》作者的图，这里直接偷过来了。

• “exclusive”状态非常类似于“ modified” 状态，唯一的例外是缓存行还没有被相应的 CPU 修改，这表示缓存行中的数据及内存中的数据都是最新的。
  
• 处于“ shared” 状态的缓存行可能被复制到至少一个其他 CPU 缓存中，这样在没有得到其他 CPU 的许可时，不能向缓存行存储数据。
  
• 处于“ invalid” 状态的行是空的，换句话说，它没有保存任何有效数据。

MESI消息

     根据几幅图来看，MESI协议的各个状态是非常容易理解的。但事实上，MESI协议的核心却是MESI消息和状态转移。《Is parallel programming hard, …》中是把消息和状态转移分开讲的，我觉得不是特别直观，所以我把这两个混在一起了。如果CPUs在单个共享总线上，MESI协议一般有以下这些消息。

• Read：当CPU在自己的cache中没有发现需要的物理地址，就会发送一条“READ”消息，该消息包括缓存行需要读的物理地址。

• Read Response: 顾名思义，”Read Response”消息是回复“Read”消息的。“Read Response”消息是由内存或者其他CPU缓存提供的。如果其他缓存请求一个处于“modified”状态的数据，则本地缓存必须提供“Read Response”消息。这个很容易理解，别的CPU在请求本地缓存中的数据，而这份数据还没有刷新到内存，所以必须告诉其他CPU该数据的最新值。接收到”Read Response”消息后，该数据的缓存状态就由”invalid”变成了”share”或者”exclusive”，这取决于”Read Response”的提供者是内存还是其他CPU缓存。

• Invalidate：“ invalidate” 消息包含要使无效的缓存行的物理地址。其他的缓存必须从它们的缓存中移除相应的数据并且响应此消息。当CPU要对一个变量进行写操作，而此变量处于只读状态(share)，就需要发送“invalid”消息。由于一个变量被多个CPU缓存，所以单个CPU的改写会造成缓存不一致，所以在写之前必须告诉其他CPU你们缓存的值马上就要过时了。接受到”invalidate”消息的CPU就会把本地缓存中的对应数据无效掉。

• Invalidate Acknowledge：一个接收到“invalidate”消息的 CPU必须在移除指定数据后响应一个“invalidate acknowledge”消息。这个消息就是告诉“invalidate”消息的提供者“我已经知道你要更改这个数据了，我放弃使用自己缓存中的拷贝！”

• Read Invalidate：”read invalidate”消息包含要缓存行读取的物理地址。同时指示其他缓存移除数据。因此，它包含一个”read”和一个”invalidate”。“read invalidate”也需要“read response”以及”invalidate acknowledge”消息集。
       “Read Invalidate”消息的发送时机有两个：第一个是CPU对一个数据进行原子读写操作，但是该数据没有在本地CPU的缓存中，在其他CPU缓存中可能有该数据的拷贝。所以它需要发送一条“Read Invalidate”消息，它不仅需要读取该数据的最新值，还要无效掉其他的CPU缓存(它马上就要改写该数据)。

• Writeback：“writeback”消息包含要回写到内存的地址和数据。这个消息允许缓存在必要时换出“modified”状态的数据以腾出空间。消息的发送时机是，CPU把本地缓存中的数据刷新到内存中，而该数据是share状态(只读)，它需要告诉其他CPU”我不再使用这些缓存数据了”

MESI状态转移

有了前面的学习，MESI的状态转移也就不难理解了。MESI协议的状态转移图如下：

其中，a-l是状态转移路径。关于全部状态转移路径，我不准备详细记录了，《Is parallel programming hard…》中有详细的描述。这里我记录几条自己觉得不容易理解的。

• Transition(e)：这条路径从”share”状态通往”Modified”装态。这种状态转移的发生时机是CPU执行一条原子读写指令(如test_and_set或者exchg)。其实从本质上说，是不存在一条从S直接到M的状态转移的。原子读写指令的微指令逻辑依然是先读后写，写之前需要invalid其他的CPU缓存，所以先还是从S到E，然后开始改写，状态从E转移到M。但是，原子读写指令与load+store的区别在于它是原子性的，不能被分割，整个指令执行过程是事务性的，必须一次完成。因此，MESI协议中才会有这样一条状态转移。

• Transition(h)：h是从S到E的一条状态转移路径。该状态转移发生的时机有两个。第一个是：CPU马上要对一个数据进行写入操作，它首先要先invalidate其他的CPU缓存，所以它进入了E状态(其他CPU缓存中都不存在该数据)。另一个时机是接收到其他全部共享某数据的CPU发送的writeback消息，也即是说本地缓存是唯一缓存了，所它就是exclusive了。需要强调的东西是——要改写某数据，要先”拥有”它，即处于S状态其实是无法改写该数据的。

  在《深入理解并行编程V1.0》中，我觉得对Transition(h)部分的翻译是有误的。同时我也已经发现了不少其他错误，在以后的博文中会陆续写出来。

  Blog: intheworld