Java 并发编程（三）：MESI、内存屏障

CPU Cache

我们知道计算机三大核心组件： CPU 、内存和硬盘，其中 CPU 的处理速度是最快的， CPU 的处理速度远远大于将数据从硬盘加载进来的速度，所以就导致 CPU 大部分都是空闲处于等待从硬盘加载数据这个流程上。然后就引入了内存， CPU 从内存读取速度得到很大提升，然而依然存在很大瓶颈，为了提升 CPU 处理效率，生产厂商就在 CPU 上引入缓存 Cache 。

MESI协议

为了提升 CPU 性能 CPU 厂商引入 CPU Cache 概念，但是会带来一个问题：缓存一致性。 L1、L2 都位于 CPU 核内部， CPU 可能存在多个核，它们之间缓存可能就会存在一致性问题。

CPU Cache 会带来缓存一致性问题，那怎么去解决这个问题呢？有几种解决方案，其中比较通用的各种厂商通常都会支持的一种方案就是 MESI 协议，该协议就是用来解决 CPU Cache 之间缓存共享数据的一致性。

MESI 是由四个单词首字母简写来的，这四个单词是用来描述 cache line 在 CPU Cache 中的四种不同状态：

• Modified
  cache line
  CPU
  

• Exclusive
  cache line
  CPU
  

• Shared
  cache line
  CPU
  

• Invalid
  cache line
  CPU
  CPU
  

cache line是CPU Cache管理数据最小单元，即CPU Cache和内存之间交换数据最小单位就是cache line，如果需要将某个变量加载到CPU中，会把该变量所处的cache line都统一一起加载进来，所以这里就引入了伪共享概念，即修改cache line中的一个变量导致处于该cache line中的其它变量也一起失效。

多处理器时，单个 CPU 对缓存中数据进行了改动，需要通知其它 CPU ，也就是意味着， CPU 处理要控制自己读写操作，还需要监听其它CPU发出的通知，从而保证最终一致。

状态之间相互转换详细说明如下：

举个例子说明下，现在有个 cache line 位于 CPU0 和 CPU1 中，所以，这个 cache line 状态是 Shared 共享态，现在 CPU0 需要对 cache line 中的一个变量进行修改，大致流程如下：

• S
  invalidate
  CPU1
  

• CPU1
  invalidate
  CPU1
  cache line
  I
  ack
  CPU0
  

• CPU0
  ack
  cache line
  cache line
  M
  

• CPU
  CPU0
  M
  cache line
  CPU
  cache line
  S
  

store-buffer

上面分析了如何通过 MESI 协议解决 CPU Cache 的一致性问题，但是却存在性能问题。如红色框框标记这个区间内， CPU0 是一直处于等待状态的，现在计算机 CPU 核数都比较多，可能要等所有的 CPU 核都返回 ack 确认消息后才能继续工作，造成 CPU0 资源被白白的浪费。

如何去解决 MESI 带来的 CPU 性能问题呢？这时候 store-buffer 就出场了。 store-buffer 是处于 CPU 核中的另一个缓存，当存在修改时，把修改直接放到 store-buffer 中， store-buffer 后台异步方式发送 invalidate 通知到其它 CPU 以及处理 ack 确认等工作，这样 CPU 就可以不用傻傻等待了。

还以刚才场景为例， CPU0 修改 cache line 后，直接丢给 store-buffer ，让 store-buffer 处理后续和其它 CPU 同步问题，自己可以接着干下面工作， store-buffer 采用异步方式发送 invalidate 通知和处理 ack ，这样 CPU0 就不会存在长时间阻塞问题，提示了 CPU 性能。

内存屏障

store-buffer 的引入虽然提升了 CPU 的性能，但是却引入了一个很大问题：数据不一致。 CPU0 中的 cache line 被修改后直接丢给 store-buffer ， store-buffer 是异步处理方式，这时 CPU0 继续处理后续工作，其它 CPU 的 cache line 由于还没有来得及通知可能还是旧数据，这就出现数据不一致问题。

比如下面代码可能存在这样一种场景：

• CPU0
  cpu0()
  value
  10
  value
  S
  CPU1
  

• CPU0
  value
  store-buffer
  isFinish = true
  isFinish
  CPU0
  E
  M
  

• CPU1
  while(!isFinish)
  CPU1
  isFinish
  CPU0
  CPU0
  isFinish
  CPU1
  isFinish
  true
  assert value == 10
  CPU0
  value
  10
  CPU0
  store-buffer
  CPU1
  value
  3
  

上面分析场景来看： 明明 cpu0() 方法中先执行 value=10 赋值，再去执行的 isFinish=true 赋值，但是在 cpu1() 方法中读取到了 isFinish 最新值， value 却读到的是旧值。 给人一种指令重排假象，这种就是伪指令重排，表面上像是发生了指令重排，实质上并没有进行指令重排，而是由于 CPU 缓存不一致造成的。

那怎么去解决这个问题呢？这里就引入了内存屏障。

在 cpu0() 方法中两个语句中间插入一个内存屏障指令 smp_mb (伪代码)，该指令作用就是保住 CPU0 的 store-buffer 中任务都同步完成后才能执行后续操作，也就保证 CPU0 上发生的修改对其它 CPU 都是可见的，然后再去执行后面语句。所以，这样就保证了 CPU1 中读取到 isFinish 最新值时， value 也一定是最新值，从而解决了上面所说的问题。

invalidate-queues

内存屏障就是把 store-buffer 由异步执行变成同步执行的过程， store-buffer 进行同步是个相当耗时的过程，需要发送 invalidate 通知到所有关联的 CPU 上，然后 CPU 接收到通知进行处理，处理完成后反馈 ack ，等获取到所有 CPU 反馈回来的 ack 才能继续向下执行。为了对内存屏障进行优化，又引入了 invalidate queues (失效队列)概念。

如上图， store-buffer 将 invalidate 通知发送到其它 cpu ，其它 cpu 接收到 invalidate 通知后放入到 invalidate queues 后直接反馈 ack ，因为处理 invalidate 也是比较耗时的工作，通过 invalidate queues 引入，缩短了 store-buffer 同步的时间。

读屏障、写屏障、全屏障

还是刚才那个场景，引入 invalidate queues 后，需要在 cpu0() 和 cpu1() 两个方法中都插入一条内存屏障才能实现之前效果。

CPU0 其实只需要把 store-buffer 同步出去即可，保证在 cpu0() 方法中的修改及时对其它 CPU 可见，插入内存屏障导致 CPU0 同时也会把 invalidate queues 处理掉，这是没有必要的一步；另一点， CPU1 为了实现数据可见性，只需要把 invalidate queues 处理完就可以获取到 value 最新值，执行 assert value == 10 判断就没有问题了，插入内存屏障导致 store-buffer 中任务被处理同样是没必要的一步。

所以，对内存屏障进行优化，细分出三种类型：

• 写屏障：主要用来保证 store-buffer 中的任务都被处理完成，才能继续后续操作，避免因指令重排导致的后续的写操作提前到这个写操作之前；
• 读屏障：主要用于保证 invalidate queues 中的任务都被处理完成，才能继续后续操作；
• 全屏障：同时保证 store-buffer 和 invalidate queues 中的任务都被处理完成才能继续后续操作；

所以，对上述代码优化后就是如下情形，只需要在 cpu0 方法中插入写屏障， cpu1 方法中插入读屏障即可。