CPU有缓存一致性协议MESI，为何还需要Volatile？

 前言

• 并发编程从操作系统底层工作的整体认识开始
• 深入理解Java内存模型(JMM)及volatile关键字

前面我们从操作系统底层了解了现代计算机结构模型中的CPU指令结构、CPU缓存结构、CPU运行调度以及操作系统内存管理，并且学习了Java内存模型(JMM)和 volatile 关键字的一些特性。本篇来深入理解CPU缓存一致性协议(MESI)，最后来讨论既然CPU有缓存一致性协议(MESI)，为什么JMM还需要volatile关键字?

CPU高速缓存(Cache Memory)

CPU为何要有高速缓存

CPU在摩尔定律的指导下以每18个月翻一番的速度在发展，然而内存和硬盘的发展速度远远不及CPU。这就造成了高性能能的内存和硬盘价格及其昂贵。然而CPU的高度运算需要高速的数据。为了解决这个问题，CPU厂商在CPU中内置了少量的高速缓存以解决I\O速度和CPU运算速度之间的不匹配问题。

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

时间局部性(Temporal Locality)：如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。

比如循环、递归、方法的反复调用等。

空间局部性(Spatial Locality)：如果一个存储器的位置被引用，那么将来他附近的位置也会被引用。

比如顺序执行的代码、连续创建的两个对象、数组等。

带有高速缓存的CPU执行计算的流程

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

目前流行的多级缓存结构

由于CPU的运算速度超越了1级缓存的数据I/O能力，CPU厂商又引入了多级的缓存结构。多级缓存结构示意图如下：

 

多核CPU多级缓存一致性协议MESI

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

MESI 协议缓存状态

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

缓存行(Cache line)：缓存存储数据的单元

注意：对于M 和 E 状态而言是精确的，它们在和该缓存行的真正状态是一致的，而 S 状态可能是非一致的。

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

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

MESI 状态转换

理解该图的前置说明：

1.触发事件 

1.cache分类

• 前提：所有的cache共同缓存了主内存中的某一条数据。
• 本地cache：指当前cpu的cache。
• 触发cache：触发读写事件的cache。
• 其他cache：指既除了以上两种之外的cache。
• 注意：本地的事件触发 本地cache和触发cache为相同。

上图的切换解释：

下图示意了，当一个cache line的调整的状态的时候，另外一个cache line 需要调整的状态。 

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

多核缓存协同操作

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

单核读取

那么执行流程是： CPU A 发出了一条指令，从主内存中读取x。

从主内存通过bus读取到缓存中(远端读取Remote read),这是该 Cache line 修改为 E状态(独享).

双核读取

那么执行流程是：

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

 

修改数据

那么执行流程是：

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

 

同步数据

那么执行流程是：

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

 

缓存行伪共享

什么是伪共享?

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被刷新!

怎么解决伪共享?

Java8中新增了一个注解： @sun.misc.Contended 。加上这个注解的类会自动补齐缓存行，需要注意的是此注解默认是无效的，需要在jvm启动时设置 -XX:-RestrictContended 才会生效。

@sun.misc.Contended 
public final static class VolatileLong { 
    public volatile long value = 0L; 
    //public long p1, p2, p3, p4, p5, p6; 
} 

 MESI优化和他们引入的问题

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

CPU切换状态阻塞解决-存储缓存(Store Bufferes)

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

Store Bufferes

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

Store Bufferes的风险

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

value = 3； 
void exeToCPUA(){ 
  value = 10; 
  isFinsh = true; 
} 
void exeToCPUB(){ 
  if(isFinsh){ 
    //value一定等于10？！ 
    assert value == 10; 
  } 
} 

 试想一下开始执行时，CPU A 保存着 isFinsh 在 E(独享)状态，而 value 并没有保存在它的缓存中。(例如，Invalid)。在这种情况下，value 会比 isFinsh 更迟地抛弃存储缓存。完全有可能 CPU B 读取 isFinsh 的值为true，而value的值不等于10。即isFinsh的赋值在value赋值之前。

这种在可识别的行为中发生的变化称为重排序(reordings)。注意，这不意味着你的指令的位置被恶意(或者好意)地更改。 它只是意味着其他的CPU会读到跟程序中写入的顺序不一样的结果。

硬件内存模型

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

• 对于所有的收到的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; 
} 

 总结

既然CPU有缓存一致性协议(MESI)，为什么JMM还需要volatile关键字?

volatile是java语言层面给出的保证，MSEI协议是多核cpu保证cache一致性的一种方法，中间隔得还很远，我们可以先来做几个假设：

回到远古时候，那个时候cpu只有单核，或者是多核但是保证sequence consistency，当然也无所谓有没有MESI协议了。那这个时候，我们需要java语言层面的volatile的支持吗?

当然是需要的，因为在语言层面编译器和虚拟机为了做性能优化，可能会存在指令重排的可能，而volatile给我们提供了一种能力，我们可以告诉编译器，什么可以重排，什么不可以。

那好，假设更进一步，假设java语言层面不会对指令做任何的优化重排，那在多核cpu的场景下，我们还需要volatile关键字吗?

答案仍然是需要的。因为 MESI只是保证了多核cpu的独占cache之间的一致性，但是cpu的并不是直接把数据写入L1 cache的，中间还可能有store buffer。有些arm和power架构的cpu还可能有load buffer或者invalid queue等等。因此，有MESI协议远远不够。

再接着，让我们再做一个更大胆的假设。假设cpu中这类store buffer/invalid queue等等都不存在了，cpu是数据是直接写入cache的，读取也是直接从cache读的，那还需要volatile关键字吗?

你猜得没错，还需要的。原因就在这个“一致性”上。consistency和coherence都可以被翻译为一致性，但是MSEI协议这里保证的仅仅coherence而不是consistency。那consistency和cohence有什么区别呢?

下面取自wiki的一段话： Coherence deals with maintaining a global order in which writes to a single location or single variable are seen by all processors. Consistency deals with the ordering of operations to multiple locations with respect to all processors.

因此，MESI协议最多只是保证了对于一个变量，在多个核上的读写顺序，对于多个变量而言是没有任何保证的。很遗憾，还是需要volatile～～

好的，到了现在这步，我们再来做最后一个假设，假设cpu写cache都是按照指令顺序fifo写的，那现在可以抛弃volatile了吧?你觉得呢?

那肯定不行啊!因为对于arm和power这个weak consistency的架构的cpu来说，它们只会保证指令之间有比如控制依赖，数据依赖，地址依赖等等依赖关系的指令间提交的先后顺序，而对于完全没有依赖关系的指令，比如x=1;y=2，它们是不会保证执行提交的顺序的，除非你使用了volatile，java把volatile编译成arm和power能够识别的barrier指令，这个时候才是按顺序的。

最后总结，答案就是：还需要～～

参考资料

• [1] http://igoro.com/archive/gallery-of-processor-cache-effects/
• [2] https://en.wikipedia.org/wiki/Sequential_consistency
• [3] https://en.wikipedia.org/wiki/Consistency_model
• [4] Maranget, Luc, Susmit Sarkar, and Peter Sewell. "A tutorial introduction to the ARM and POWER relaxed memory models." Draft available from http://www. cl. cam. ac. uk/~ pes20/ppc-supplemental/test7. pdf (2012).
• [5] https://www.zhihu.com/question/296949412?sort=created

PS：以上代码提交在 Github ：

https://github.com/Niuh-Study/niuh-juc-final.git