C2- CPU缓存一致性原理

一些常识

CPU

• CPU不能直接访问内存（write-back内存模型，也是主流模型），必须通过L1-L3才能访问到内存（具体执行是L3环形总线）;
• CPU访问内存的粒度（write-back模型）——cacheline，是以64字节为一块来访问的，跟os中页的概念类似，为了节约带宽；（原因参考局部性原理）
• L3 cache实际上兼有总线的功能——可以用来传递数据与消息——叫做环形互联——MESI——x86_64的缓存一致性协议就是在这个层面实现；
• 同一个CL在CPU中会有多分拷贝，不同层与不同核都有多个副本；如图中C1会存在在L3-L1每层中，而不同核心因为多线程访问也会有副本；但尽管有这么多副本，他们都代表同一块虚拟内存空间；
• 这篇文章要讨论的缓存一致性协议在X86_64构架下叫做MESI协议。

什么是MESI

• MESI是4个单词的缩写：M-modified（修改的），E-exclusive（独占的），S-shared（共享的）以及I-invalid（失效的）。
• 而对于MESI需要了解的头等大事是：MESI是用来控制CL同步的协议。我们从上图可以看到，在SMP多核多线程访问共享变量的情况下，同一块虚拟内存地址映射的CL会存在在不同CPU core中，那么它们的读写必然会产生同步问题，就跟高级语言中的多线程同步一样。

public class shutDownThread implements Runnable {
    volatile int shutDownRequested;
    volatile int counter;
    public void shutDown(){
        shutDownRequested = true;
    }
    @Override
    public void run() {
        while (!shutDownRequested) {
            System.out.println(counter++);
        }
    }
}


public class Demo01 {
    public static void main(String[] args) throws InterruptedException {
        Thread[] th = new Thread[10];
        shutDownThread t = new shutDownThread();
        for(int i=0;i<=9;i++){
            th[i] = new Thread(t);
            th[i].start();
        }
        Thread.sleep(1000);
        t.shutDown();
    }
}

借用一下这段经典的程序说明下为什么缓存行存在同步问题：

1. Thread1将共享变量counter从内存加载进入core1核心的C1缓存行；
2. 然后Thread2也将counter从内存加载进入core2核心的C1缓存行；
3. Thread1对counter加1，然后将C1写回；此时内存中counter为1；
4. Thread2也对counter加1，接着写回C1，此时内存counter还是1；
5. 而我们想让Thread1与Thread2合作，将counter加到2改怎么做？对，进行同步才行，所以CPU也会有这个同步的问题，事实上只要是对共享变量有多个计算单元进行操作，都会产生同步问题，JVM的锁工作在高层，粒度更粗；而CPU的多核同步机制工作在底层，粒度更小而已机制都是一样的。
6. 多说一点，上面这段代码在有MESI的情况下也不能实现线程同步，原因是counter++这条语句看上去只有一句，但是对于CPU至少有三条：

mov [counter] eax; //加载counter从内存到寄存器（这条mov还会继续分解成操作CL的微指令）
add 1 eax  //+1
mov eax [counter] //写回操作

可见counter++在执行的过程中，可能会被打断（比如时钟中断）造成不可能是原子的。这时，你可能会问MESI的作用是啥？

7. 如果java可以写汇编，只要将counter++改成lock inc [counter]就能立马变成原子操作了，这就是MESI协议在做影响。有兴趣的朋友可以试试看（intel x86 cpu哦)
8. 这里给个C++的实现，没有用到C++的任何锁，但是用汇编调起CPU原子锁来做同步：

#include <iostream>
#include <string>
#include <thread>

const int TC = 4;
int count = 0;
bool flag = true;
void inc_count()
{
    asm("movl   $1, %eax");
    asm("LOCK addl %eax,count(%rip)"); //count是个寄存器相对寻址。lock prefix是CPU原子指令。
}
void testRun()
{
    for(int i=0; i<10000;i++)
    {
        inc_count();
    }
}

int main()
{
    std::thread threads[TC]; // 默认构造线程
    for (int i = 0; i < TC; ++i)
    {
        threads[i] = std::thread(testRun); // move-assign threads
    }

    std::this_thread::sleep_for(std::chrono::seconds(1));
    std::cout << "main thread id:" << std::this_thread::get_id() << std::endl;
    flag = false;
    for (auto &thread : threads)
    {
        thread.join();
    }

    std::cout << "All threads joined!"
              << " count:" << count<<std::endl;
}

下面解释MESI是如何工作的

首先解释下MESI的含义

Modified（M）：更新状态

1. 整个多核系统中最多只有一个CL的状态是M；其他的CL副本都是I状态，此时CL的值跟内存的值不相等；
2. 在变到M之前应该先获取CL的所有权，也就是先必须到E；这个过程是通过总线嗅探机制完成，类似队列的监听，所有core都会通过L3环形总线嗅探来自其他core的同步消息。这个过程简单来说是个共识的过程，如果其他core都同意本core对CL的修改，就会将自己的状态变成I，而发起core的状态变成M；
3. 当发起core更新CL完毕，此时core会发起write back回写到内存，同时发消息给其他core通知它们拉取最新的CL值。最后都更新完毕后会回到S状态；
4. 这里要注意一个细节，就是write back到内存是个漫长的过程，所以采用异步机制回写，提高性能，具体步骤是：将CL回写请求发给store buffer然后就算完成了；然后环形总线处理store buffer，回写到内存。

Exclusive(E) 独占状态

1. 跟M状态一样，整个SMP core中对于某个CL只能有一个副本的状态处于E这个状态；
2. 处于E状态下的CL存储的值跟内存中的值是一样的；
3. 处于E状态的CL是唯一可以转换成M状态的状态；
4. 如果其他core也发起读取这个内存块的值请求，则这个CL副本会通过环形总线同步给其他core，此时所有这个CL的副本状态都变成S；
5. 如果本地core对CL的数据进行更改，则本地的core的状态变成M。同时会发送消息给其他的core，通知它们将这个CL的状态设置成I。

Shared(S) 共享状态

1. S状态下，CL的数据跟内存中的一致；
2. S状态说明CL的所有副本都是S状态，所有CL的数据一致；

Invalid(I)失效状态

1. I状态CL说明本地CL已经已经失效，不能使用，等待更新完毕的通知。

状态机

发布订阅模式

MESI协议的实现很像一个队列服务（其实队列是发布订阅异步模型的基础，不论在互联网分布式系统中还是操作系统中都占有重要的地位，可以说只要有异步模型，就必定会有队列。参考）。

1. core发布的消息（可以简单理解为core发起读、写动作）

• PrRd读本地CL
• PrWr写本地CL
• ack反馈消息。当收到busRd与busWr的反馈消息，可以包含数据。

2. core订阅的消息（通过L3总线嗅探机制，其实就是监听某个其他核心群发的事件消息）

• busRd其他core发布的读请求；
• busWr其他core发布的写请求
• flush更新完毕消息（获得修改权的处于M状态的CL，完成CL更新与完成write-back内存更新发送的消息）

转换场景（简化版，详细版本可以参考wiki的解释）

读取场景

cache miss读取场景

• 如果core发生Cache Miss则会发送busRd消息给其他core，如果其他core有，就发送ack+data的消息完成同步，新的CL状态设置成S;
• 如果其他core都没有这个CL，则CPU从磁盘load进来，设置CL状态为E。

S E M状态下的读取

S E M状态下的读取

• S与E状态下内存的数据跟CL中一致，缓存命中，效率很高，什么消息都不用发；
• M状态也不用发同步消息是因为，新的数据本来就在自己的store buffer中了，所以也可以不去"扰民"。

I状态下的读取

I状态下的读取

• 如果core读取I状态的CL，则一定会发起总线嗅探，发送busRd消息，看看其他core的CL情况；
• 如果收到ack+data则更新自己的CL，说明M状态已经flush完毕，自己可以更新本地的CL了，然后设置状态到S；
• 如果其他core都ack说自己没有这个CL，就从内存load新的值，变成E状态。

更新场景

1.总线发送更改请求

• core1要修改CL必须征得其他core的同意，这是同步的关键。此时core1会发送busWr总线消息去试图征得大家的同意；
• 如果有多个core试图更新CL，也只能有一个core最终获得修改权，也就是进入E独占状态;
• core1必须等到收齐所有其他3个core的ack ok消息以后才能将自己的状态变到E；
• 此时core2，core3，core4的CL状态变成I，也就是CL缓存行失效。此时效果是，如果core2-4还对CL发起PrRd操作，则会pending。

2. 修改完成都是S状态

• core1收齐所有ack ok的消息后，确定只有自己可以修改CL，所以马上发起PrWr的操作，对CL进行修改，此刻CL的状态变成M；
• 修改完毕后，发起flush消息到总线，core2-4收到后，更新自己的副本，并将状态设置为S；
• 同时core1还会将修改后的CL值同步回内存。
• 这就是写操作的步骤了。下面看看两个重要的问题。

Store buffer与Invalidate queues

MESI协议的修改过程有两个性能瓶颈：

1. 发生在修改侧：修改发起core必须发送busWr来跟其他core进行协同共识，这时发起core必须等到所有的ack消息集齐后才能开始动手修改，这就出现了阻塞；
2. 发生在接收侧：当其他core收到busWr消息后，必须要响应ack。这个过程跟队列接收消息很类似，如果此刻core还有其他的消息要处理，这个消息只能排队，如果积压比较严重，就会pending比较长的时间，发生阻塞。
   [图片上传失败...(image-ae81c2-1679042340818)]

• 当出现阻塞要提高响应的性能，通常的做法是用异步代替同步；解决方案是store buffer与invalidate queue；
• 当core1发出busWr的请求后，将等待->同步->flush的任务都委托给store buffer，自己就可以异步地执行下一条指令了；提高了系统的吞吐量；
• 当core2接收到busWr后，不会直接到处理引擎，而是先将消息缓存到invalidate queue里面，紧接着就发送ack给core1，提高吞吐量；此时core2的CL还没有变成I状态，但是等invalidate queue处理完成，最终会变成I，中间会有个延迟。

缺点

• Store buffer：导致数据实际更新时间比数据更新到内存要早；也就是内存数据更新出现了延迟；
• Invalidation queue：core实际感受到数据失效的时间延迟了，也就是数据可见性延迟了。
• 当然，在大部分时间不会有什么问题，只会感觉到系统性能提高了，但是在某些极端情况，比如：多线程，高并发的场景下因为延迟加大，所以就不能忽略了。要修正这个bug又要获得效率就是大名鼎鼎的——内存屏障干的事了。

总结

• MESI是缓存行一致性协议，有了这个协议，多核CPU可以实现核间高速的原子指令与数据共享；
• 理论上一份内存数据只要load到CPU一次，即可通过MESI协议实现多核数据共享，提高了吞吐量；
• 缓存行在高并发、高性能程序设计中影响巨大，后面通过单独章节详细聊聊缓存行的结构与原理；
• Store buffer与Invalidate Queues是MESI协议的副作用——导致内存屏障技术出现的根本原因。后面章节会单独讨论CPU中的原子指令与内存屏障。
• 原子指令是实现高层锁机制的基础，它的性能直接影响到了操作系统与用户程序的性能，在并发激烈或者对性能要求非常苛刻的操作系统中尤其突出。例如著名的spinlock自旋锁的性能问题，x86就因为MESI协议在core的数量不断增大的情况下，通过L3环形互联发送的消息指数增长，而修改单个CL会导致大量的同步消息发布到互联总线，产生了著名的惊群问题，性能也会急剧下降。这直接使得Linux这种非常看重扩展性的操作系统非常不满，RCU这种真正的无锁黑科技正式诞生，成为linux一个重要的子系统。后面在讲述Linux的同步机制章节详细展开讨论。

参考

• wiki——MESI又叫做伊利诺伊同步协议
• 头条专栏：简一说道的《高性能编程必备计算机硬件知识》

补充

重排序

CPU为了提高执行效率与指令的吞吐量，发明了很多黑科技其中指令重排序就是一个，而指令重排序中有一个就是Store buffer与Invalid queue的副作用导致的。

• store buffer会导致当前的store指令（修改CL的指令）延后执行，相当于这条store指令往后挪了；
• invalidation queue会导致读取到老的值，也就是load指令前移了。
  重排序

还有哪些重排序？

• 分支预测
• 编译器重排序
  这里给我们了一个重要的启示：任何优化都是双刃剑，有好的一面就一定有副作用，做工程最重要的工作就是做好平衡，只要平衡得好就是好的产品，不要什么都想要，结果一塌糊涂。
  比如：MESI协议因为有了Store buffer与Invalidation Queue加快了速度，但是在大并发的多线程程序下可能出现指令重排序的bug，造成程序状态紊乱；这时就要开发屏障指令来弥补。但是屏障指令的弥补肯定会抵消掉一部分Store buffer带来的提升。但是这种平衡是可取的，因为多核多线程的目的就是提高CPU的并行能力，这部分的收益足以承担屏障指令带来的损耗，整体来看是个好的设计。
• 同样的道理也可以适用于分支预测与编译器重排序这两种提高性能的方式。
• 好了，完毕！