并发编程-CPU缓存一致性协议MESI

一、CPU高速缓存

CPU的高度运算需要高速的数据。CPU厂商在CPU中内置了少量的高速缓存以解决I\O速度和CPU运算速度之间的不匹配问题。

1.局部性原理

在CPU访问存储设备时，无论是存取数据或存取指令，都趋于聚集在一片连续的区域中，称为局部性原理。

• 时间局部性（Temporal Locality）：如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。
  比如循环、递归、方法的反复调用等。
• 空间局部性（Spatial Locality）：如果一个存储器的位置被引用，那么将来他附近的位置也会被引用。
  比如顺序执行的代码、连续创建的两个对象、数组等。

2.CPU执行计算的流程

image.png

• 程序以及数据被加载到主内存
• 指令和数据被加载到CPU的高速缓存
• CPU执行指令，把结果写到高速缓存
• 高速缓存中的数据写回主内存

3.多级缓存结构

由于CPU的运算速度超越了1级缓存的数据I\O能力，CPU厂商引入了多级的缓存结构。

image.png

多核CPU的情况下有多个一级缓存，如何保证缓存内部数据的一致,不让系统数据混乱。引出了一个一致性的协议MESI。

二、MESI协议缓存状态

MESI 是指4种状态的首字母。每个Cache line有4个状态，可用2个bit表示，它们分别是：

状态	描述	监听任务
M 修改 (Modified)	该Cache line有效，数据被修改了，和内存中的数据不一致，数据只存在于本Cache中。	缓存行必须时刻监听所有试图读该缓存行相对主存的操作，这种操作必须在缓存将该缓存行写回主存并将状态变成S（共享）状态之前被延迟执行
E 独享、互斥 (Exclusive)	该Cache line有效，数据和内存中的数据一致，数据只存在于本Cache中。	缓存行也必须监听其它缓存读主存中该缓存行的操作，一旦有这种操作，该缓存行需要变成S（共享）状态。
S 共享 (Shared)	该Cache line有效，数据和内存中的数据一致，数据存在于很多Cache中。	缓存行也必须监听其它缓存使该缓存行无效或者独享该缓存行的请求，并将该缓存行变成无效（Invalid）。
I无效 (Invalid)	该Cache line无效。	无

缓存行（Cache line）:缓存存储数据的单元。

对于M和E状态而言总是精确的，他们在和该缓存行的真正状态是一致的，而S状态可能是非一致的。如果一个缓存将处于S状态的缓存行作废了，而另一个缓存实际上可能已经独享了该缓存行，但是该缓存却不会将该缓存行升为E状态，这是因为其它缓存不会广播他们作废掉该缓存行的通知，同样由于缓存并没有保存该缓存行的copy的数量，因此（即使有这种通知）也没有办法确定自己是否已经独享了该缓存行。

E状态是一种投机性的优化：如果一个CPU想修改一个处于S状态的缓存行，总线事务需要将所有该缓存行的copy变成invalid状态，而修改E状态的缓存不需要使用总线事务。

三、MESI状态转换

MESI状态转换.png

1.触发事件

触发事件	描述
本地读取（Local read）	本地cache读取本地cache数据
本地写入（Local write）	本地cache写入本地cache数据
远端读取（Remote read）	其他cache读取本地cache数据
远端写入（Remote write）	其他cache写入本地cache数据

2.cache分类

前提：所有的cache共同缓存了主内存中的某一条数据。

• 本地cache：当前cpu的cache。
• 触发cache：触发读写事件的cache。
• 其他cache：除了以上两种之外的cache。

image.png

当一个cache line的调整的状态的时候，另外一个cache line 需要调整的状态：

	M	E	S	I
M	❌	❌	❌	✅
E	❌	❌	❌	✅
S	❌	❌	✅	✅
I	✅	✅	✅	✅

假设cache 1 中有一个变量x = 0的cache line 处于S状态(共享)。
那么其他拥有x变量的cache 2、cache 3等x的cache line调整为S状态（共享）或者调整为 I 状态（无效）。

四、多核缓存协同操作

image.png

假设有三个CPU 1、2、3，对应三个缓存分别是cache a、b、 c。在主内存中定义了x的引用值为0。

1.读取数据

读取数据.png
单核读取执行流程：

• CPU 1发出了一条指令，从主内存中读取x。
• 从主内存通过bus读取到缓存中（远端读取Remote read）,这时该Cache line修改为E状态（独享）.

双核读取执行流程：

• CPU 1发出了一条指令，从主内存中读取x。
• CPU 1从主内存通过bus读取到 cache a中并将该cache line 设置为E状态。
• CPU 2发出了一条指令，从主内存中读取x。
• CPU 2试图从主内存中读取x时，CPU 1检测到了地址冲突。这时CPU 1对相关数据做出响应。此时x 存储于cache a和cache b中，x在chche a和cache b中都被设置为S状态(共享)。

2.修改数据

修改数据.png

• CPU 1计算完成后发指令需要修改x.
• CPU 1 将x设置为M状态（修改）并通知缓存了x的CPU 2, CPU 2将本地cache b中的x设置为I状态(无效)
• CPU 1对x进行赋值。

3.同步数据

同步数据.png

• CPU 2 发出了要读取x的指令。
• CPU 2 通知CPU1，CPU1将修改后的数据同步到主内存时cache a 修改为E（独享）
• CPU 1同步CPU2的x,将cache a和同步后cache b中的x设置为S状态（共享）。

五、缓存行伪共享

1.定义

CPU缓存系统中是以缓存行（cache line）为单位存储的。目前主流的CPU Cache 的 Cache Line 大小都是64Bytes。在多线程情况下，如果需要修改“共享同一个缓存行的变量”，就会无意中影响彼此的性能，这就是伪共享（False Sharing）。

有2个long 型变量 a 、b，如果有t1在访问a，t2在访问b，而a与b刚好在同一个cache line中，此时t1先修改a，将导致b被刷新。

2.解决伪共享

自动补齐缓存行：

• 前后加八个long型字段补齐缓存行
• 使用@sun.misc.Contended自动补齐缓存行

注意：此注解默认无效，需要在jvm启动时设置 -XX:-RestrictContended 才会生效。

六、MESI优化

缓存的一致性消息传递是要时间的，其切换时会产生延迟。当一个缓存被切换状态时其他缓存收到消息完成各自的切换并且发出回应消息这么一长串的时间中CPU都会等待所有缓存响应完成。可能出现的阻塞都会导致各种各样的性能问题和稳定性问题。

1.CPU切换状态阻塞解决-存储缓存（Store Bufferes）

需要修改本地缓存中的一条信息，那么必须将I（无效）状态通知到其他拥有该缓存数据的CPU缓存中，并且等待确认。等待确认的过程会阻塞处理器，这会降低处理器的性能。因为这个等待远远比一个指令的执行时间长的多。

为了避免这种CPU运算能力的浪费，Store Bufferes被引入使用。处理器把它想要写入到主存的值写到缓存，然后继续去处理其他事情。当所有失效确认（Invalidate Acknowledge）都接收到时，数据才会最终被提交。

2.Store Bufferes的风险

• 处理器会尝试从存储缓存（Store buffer）中读取值，但它还没有进行提交。这个的解决方案称为Store Forwarding，它使得加载的时候，如果存储缓存中存在，则进行返回。
• 保存什么时候会完成没有任何保证。

七、硬件内存模型

执行失效不是一个简单的操作，它需要处理器去处理。另外，存储缓存（Store Buffers）并不是无穷大的，所以处理器有时需要等待失效确认的返回。这两个操作都会使得性能大幅降低。为了应付这种情况，引入了失效队列。

约定如下：

• 对于所有收到的Invalidate请求，Invalidate Acknowlege消息必须立刻发送
• Invalidate并不真正执行，而是被放在一个特殊的队列中，在方便的时候才会去执行。
• 处理器不会发送任何消息给所处理的缓存条目，直到它处理Invalidate。

即便是这样处理器已然不知道什么时候优化是允许的，而什么时候并不允许。所以处理器将这个任务丢给了写代码的人。这就是内存屏障（Memory Barriers）：

• 写屏障 Store Memory Barrier(a.k.a. ST, SMB, smp_wmb)是一条告诉处理器在执行这之后的指令之前，应用所有已经在存储缓存（store buffer）中的保存的指令。
• 读屏障Load Memory Barrier (a.k.a. LD, RMB, smp_rmb)是一条告诉处理器在执行任何的加载前，先应用所有已经在失效队列中的失效操作的指令。

void executedOnCpu0() {
    value = 10;
    //在更新数据之前必须将所有存储缓存（store buffer）中的指令执行完毕。
    storeMemoryBarrier();
    finished = true;
}
void executedOnCpu1() {
    while(!finished);
    //在读取之前将所有失效队列中关于该数据的指令执行完毕。
    loadMemoryBarrier();
    assert value == 10;
}