从硬件缓存模型到Java内存模型原理浅析

参考Google的这个问题what is a store buffer?
一、硬件方面的问题
1、背景
在现代系统的CPU中，所有的内存访问都是通过层层缓存进行的。CPU的读/写（以及指令）单元正常情况下甚至都不能直接与内存进行访问，这是物理结构决定的。CPU和缓存进行通信，而缓存才能与内存进行通信。处理器保证从系统内存中读取或者写入一个字节是原子的，但是复杂的内存操作处理器是不能保证其原子性的，比如跨总线操作、跨多个缓存行和跨页表的访问。但是处理器提供了总线锁定和缓存锁定两个机制来保证复杂内存操作的原子性。
硬件缓存模型如下图所示：
解释：具体这些会在MESI协议里面讲，先有个概念
（1） CPU就是CPU
（2）Store Bufferes存储缓存
（3）Cache 就是代表高速缓存
（4）Invalidate Queues 无效队列
（5）Memory 内存

2、问题与解决
问题：如果有多个CPU，每个CPU都有自己的缓存，其中一个修改了缓存，会发生什么？答案是什么也不会发生。我们希望拥有多组缓存的时候，需要它们保持同步。或者说，系统的内存在各个CPU之间无法做到与生俱来的同步，我们实际上是需要一个大家都能遵守的方法来达到同步的目的。接下来看带来的问题与解决方案。
（1）原子性问题
我们以一个原子操作的i++为例，来讲解这个问题。
如果多个处理器同时对共享变量i进行读该写操作，那么共享变量就会被多个处理器就行同时操作，这样的读写该操作就不是原子的，操作完成之后共享变量的值会和期望的不一致。如果i=1,我们CPU0进行i++操作，CPU1进行i++操作，我们期望结果是3，但是有可能结果是2。
原因可能是多个处理器同时从各自的缓存中读取变量i，分别进行i++，操作，然后分别写入系统。这就不是原子的了，读改写被分开了。所以要解决这个问题就必须保证CPU0进行读改写时，CPU1不行进行读改写操作。
通过总线锁来保证原子性
所谓处理器总线锁就是使用处理器提供的一个LOCK#信号，当一个处理器总线上输出此信号时，其它处理器的请求将被阻塞住，那么该处理器可以独占共享内存。
通过缓存锁定来保证原子性
总线锁定把CPU和内存之间的通信锁住了，这使得锁定期间，其它处理器不能操作其它内存地址的数据，所以总线锁的开销比较大，所以就引进了缓存锁定来代替总线锁定来进行优化。
所谓“缓存锁定”是指内存区域如果被缓存在处理器的缓存中，那么当它执行锁操作会写内存时，处理器不需要再总线上加锁，而是修改内存地址，并允许处理器的缓存一致性协议“来保证操作的原子性，因为缓存一致性协议会阻止同时修改由两个以上处理器缓存区的内存区域数据，当其它处理器回写已被修改的缓存行数据实，会使其它缓存行无效。
缓存一致性协议（MESI）大多数支持
结合硬件缓存模型图来讲解：

• 失效（Invalid）缓存段，要么已经不在缓存中，要么它的内容已经过时。为了达到缓存的目的，这种状态的段将会被忽略。一旦缓存段被标记为失败，那效果就等同于它从来没被加载到缓存中。
• 共享（Shared）缓存段，它是和主内存内容保持一致的一份拷贝，在这种状态下的缓存段只能被读取，不能被写入。多组缓存可以同时拥有针对同一内存地址的共享缓存段，这就是名称的由来。
• 独占（Exclusive）缓存段，也是和主内存内容保持一致的一份拷贝。区别在于，如果一个处理器持有了某个E状态的缓存段，那其他处理器就不能同时拥有它，所以叫”独占“。这意味着，如果其他处理器原来也持有同一段换成段，那么它会马上变成”失败“状态。

• 已修改（Modified）缓存段，属于脏段，它们已经被所属的处理器修改了。如果一个段处于已修改状态，那么它在其他处理器缓存中的拷贝马上会变成失效状态，这个规律和E状态一样。此外，已修改缓存段如果被丢弃或标记为失败，那么先要把它的内容回写到内存中-这和回写模式下常规的脏段处理方。
  状态转换时需要发送的消息：

• Read消息
  该消息包含读的物理地址，一般用于加载数据。
• Read Respionse消息
  该消息包含前面Read消息所请求的数据，可以由其他CPU缓存或者内存发出。
• Invalidate消息
  该消息包含无效的物理地址，由某个CPU缓存发出，所有接收到消息的缓存需要移除对应的数据项（置无效）。
• Invalidate Acknowledge消息
  在接收到Invalidate消息并移除对应数据后，相应的CPU缓存需要发送此消息。
• Read Invalidate消息
  该消息包含读的物理地址，同时让其他CPU缓存移除对应数据。该消息可以接收到一个Read Response消息和一系列Invalidate Acknowledge消息。
• Writeback消息
  该消息包含物理地址和需要被会写内存的数据，这个消息允许缓存为存放其他数据清除该数据所占的空间，否则该数据不能被移除。
  状态转换

我们发现上面的状态转换只有当缓存段处于E或M状态时，处理器才能去写它，也就是说只有这两种状态下，处理器是独占这个缓存段的。当处理器想写某个缓存段时，如果它没有独占权，它必须先发送一条“我要独占权”的请求给总线，这会通知其他处理器，把它们拥有的同一缓存段的拷贝失效（如果它们有的话）。只有在获得独占权后，处理器才能开始修改数据——并且此时，这个处理器知道，这个缓存段只有一份拷贝，在我自己的缓存里，所以不会有任何冲突。反之，如果有其他处理器想读取这个缓存段（我们马上能知道，因为我们一直在窥探总线），独占或已修改的缓存段必须先回到“共享”状态。如果是已修改的缓存段，那么还要先把内容回写到内存中。
MESI协议的问题(性能)
我们来分析一个例子，如下代码示例：

int a = 5;
public void  add () {
        a = a + 2;
}

假如现在有三个CPU，每个CPU都有a的缓存，状态为S，现在CPU1要去修改a,我们要做些什么操作了，首先要申请总线，独占这一缓存，获取成功后，给CPU2、CPU3发生Invalidate消息，使CPU2、CPU3的缓存失效，然后CPU2、CPU3是本缓存失效后，回复确认Invalidate Acknowledge消息，然后CPU1，才能去修改缓存，然后而这个过程中CPU1啥都不能干，这就浪费了CPU的性能，所以硬件就提供了写优化策略。
Store Bufferes和Invalidate Queues
Store Bufferes 缓存存储，当处理器需要把修改写入缓存时，然后在写入内存这个过程时，我们处理器不需要等待了。只需要把指数据写入Store Bufferes，然后发生Invalidate消息给其它CPU，然后本CPU就可以去执行其它指令了，等到我们都收所有回复确认Invalidate Acknowledge消息，在把Store Bufferes消息写回缓存修改状态为（M），如果有其它CPU来读，就会刷新到内存，状态变为S。Store Bufferes 的作用是让 CPU 需要写的时候仅仅将其操作交给 Store Buffere，然后继续执行下去，Store Bufferes 在某个时刻就会完成一系列的同步行为。
Invalidate Queues 无效队列，这么理解吧我们在修改数据时，需要使其它处理器数据失效，这其实也是一系列的写操作，如果我们这些消息都交给Store Bufferes处理，Store Bufferes速度快，但是容量很小，所以就设计出了Invalidate Queues，当别的CPU收到Invalidate消息时，把这个操作加入无效队列，然后快速返回Invalidate Acknowledge消息，让发起者做后续操作，然后Invalidate并不是马上处理，而只是加入了队列，也就是说其实不是立刻让本CPU的缓存数据失效，而是等CPU处理无效队列里的无效消息时。
（2）可见性问题（Store Bufferes和Invalidate Queues产生）
Store Bufferes和Invalidate Queues问题；问题分析，我们发现Store Bufferes的写入缓存和Invalidate Queues的处理失效，都是最终一致性的表现，这在单核操作时可能没什么问题，如果是多核操作（其实就是Java的并发）那么数据修改的可见性就是不确定的。
代码分析：两个CPU同时操作（）
我么假设此时numone的状态为共享（S），flag状态为E，
我们假设CPU1中的执行update方法，CPU2执行test方法。
现在CPU1需要修改numone，由于numone为共享状态，所以缓存和内存一致，所以我们获取总线，通知其它CPU缓存的numone变为无效（I），然后CPU1把numone的8加入Store Bufferes里面，就去执行其它指令了，CPU1执行修改flag，因为flag为E，所以直接修改，写入缓存。CPU2，执行test方法，由于CPU1修改了flag所以需要刷新到内存，然后CPU2去从内存中读取flag，CPU1和CPU2状态变为S，此时CPU2可能收到无效消息，加入无效队列，然后我们打印numone,结果是多少了，不确定，因为CPU1 何时把numone刷新至内存，CPU2何时执行无效消息，这都是不确定的，所以我们打印的numone可能是8或者0。
其实也可以理解为CPU指令的重排序，CPU1flag的写入发生在了numone的前面，导致CPU2打印时不确定这个值是否写入；CPU2的读取numone可能发生在了无效命令前面。

public class StoreBufferesQuestion {

    private int  numone = 0;
    private Boolean  flag = false;

    public void update() {
        numone = 8;
        flag = true;        
    }

    public void test() {
        while (flag) {
            // numone 是多少？
            System.out.println(numone);
        }
    }
}

Store Bufferes和Invalidate Queues问题解决：硬件 level 上很难揣度软件上这种前后数据依赖关系，因此往往无法通过某种手段自动的避免这种问题，因而只有通过软件的手段表示（对应也需要硬件提供某种指令来支持这种语义），这个就是 Memory Barrier（内存屏障）。
Store Memory Barrier(a.k.a. ST, SMB, smp_wmb)是一条告诉处理器在执行这之后的指令之前，应用所有已经在存储缓存（store buffer）中的保存的指令。
Load Memory Barrier (a.k.a. LD, RMB, smp_rmb)是一条告诉处理器在执行任何的加载前，先应用所有已经在失效队列中的失效操作的指令。
再看下如下代码：
这样就保证了可见性。

public class StoreBufferesQuestion {

    private int  numone = 0;
    private Boolean  flag = false;

    public void update() {
        numone = 8;
        Store Memory Barrier指令；刷新Store Bufferes
        flag = true;        
    }

    public void test() {
        while (flag) {
            // numone 是多少？
            Load Memory Barrier指令；执行时效消息
            System.out.println(numone);
        }
    }
}

总结
我们看到硬件为了解决原子性，使用了总线锁和缓存锁，缓存锁是基于缓存一致性协议实现的。缓存一致性协议带来了指令执行顺序问题，影响了多核处理器之间的可见性。因为硬件无法知道我们这些软件数据在执行时的指令顺序，所以硬件就制定了这样一套硬件规则来满足硬件需求，提供Memory Barrier来解决方案来应对软件可能发生的问题，具体需要我们软件自己去实现。
二、软件层面的问题（JAVA）
我们在编写并发程序时，也会出现问题原子性问题、可见性问题。
Java如何实现原子操作
在Java中可以通过锁和循环CAS的方式实现原子操作。
CAS是英文单词CompareAndSwap的缩写，中文意思是：比较并替换。CAS需要有3个操作数：内存地址V，旧的预期值A，即将要更新的目标值B。从Java 1.5开始，JDK并发包提供了一些类支持原子操作。
CAS实现原子操作存在的问题
1）ABA问题。因为CAS需要在操作值得时候，检查值没有变化，如果没有发生变化则更新，但是一个值原来是A，变成了B，由变成了A，那么使用CAS允许检查时会发现它的值没有发生变化，但是实际却发生了变化。ABA问题的解决思路就是使用版本号，每次变量更新的时候版本号加1，那么A-B-A就会变成1A-2B-3A.从Java1.5开始,JDK的atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法作用是首先检查当前引用是否等于预期引用，并且检查当前标志是否等于预期标志，如果全部相等，则以原子方式将引用和该标志的值设置为给定的更新值。
2）循环时间长开销大。自旋CAS如果长时间不成功，会给CPU带来非常大的执行开销。
3）只能保证一个共享变量的原子操作。
使用锁机制来实现原子性：锁机制保证了只有获得锁的线程才能够操作锁定的内存区域。JVM内部实现了很多种锁机制。
可见性问题
Java线程之间的通信对程序员完全透明，内存可见性问题很容易困扰Java程序员。
Java内存模型的抽象结构
在Java中，所有实例域、静态域和数组元素都存在堆内存中，堆内存在线程之间共享。局部变量，方法定义参数和异常处理器参数不会再线程之间共享，他们不会存在内存可见性问题，也不受内存模型的影响。
Java线程之间的通信由Java内存模型控制，JMM决定一个线程对共享变量的写入何时对另一个线程可见。从抽象的角度来看，JMM定义了线程和主内存之间的抽象关系：线程之间的共享变量存储在主内存中，每个线程都有一个私有的本地内存，本地内存中存储了该线程读/写共享变量的副本。本地内存是JMM的一个抽象概念，并不真实存在。它涵盖了缓存、写缓存区、寄存器以及其他的硬件和编译优化。如下图所示。

线程之间的通信：如下图所示
1）线程A把本地内存A中更新过的共享变量刷新到主内存中去。
2）线程B到主内存中去读取线程A 已更新过的共享变量。

影响可见性的因素（重排序）
在执行程序时，为了提高性能，编译器和处理器常常会对指令做重排序。分为3中类型。
1）编译器重排序。编译器在不改变单线程语义的前提下，可以重新安排语句的执行顺序。
2）指令级并行的重排序。现代处理器采用了指令并行技术。如果不存在数据依赖性，处理器可以改变语句对应机器指令的执行顺序。
3）内存系统的重排序。由于处理器使用缓存和读/写缓冲区，这使得加载和存储操作看上去可能是乱序执行。（处理器的重排序）
从Java源代码到最终的指令序列，会经历下面三种排序，如下图所示：

重排序的规则；as-if-serial语义：不管怎么重排序，单线程程序的执行结果不能被改变。编译和处理器都必须遵循as-if-serial语义。但是如果操作之间没有数据依赖关系，这些操作就可以被重排序。
对于处理器的(内存和指令)重排序，JMM的处理器重排序规则会要求Java编译器生成指令时，插入特定类型的内存屏障指令。JMM把内存屏障分为4类：

happens-before(JMM可见性的保证)
JSR-133使用happens-before的概念来指定连个操作之间的执行顺序。由于这两个操作可以在一个线程之内，也可以在不同线程之间。因此，JMM可以通过happens-before关系向程序员提供跨线程的内存可见性。
happens-before关系定义
（1）如果一个操作happens-before另一个操作，那么第一个操作的执行结果将对第二个操作可见，而且第一个操作的执行顺序排在第二个操作前面。这是JMM对程序员的保证。
（2）两个操作之间存在happens-before关系，并不意味着Java平台的具体实现必须要按照happens-before的指向顺序来执行。如果重排序之后的执行结果，与按happens-before关系的执行结果一致，这种重排序并不非法（也就是说，JMM允许这种重排序）。这是JMM对重排序指定的规则，只要不改变程序的执行结果（单线程和正确同步的线程），怎么优化都行。
happens-before规则（满足规则即满足可见性）
1）程序顺序规则：一个线程中的每个操作，happens-before与该线程中的任意后续操作。
2）监视器锁规则：对一个锁的解锁，happens-before与随后对这个锁的加锁。
3）volatile变量规则：对一个volatile域的写，happens-before于任意后续对这个volatile域的读。
4）传递性：如果A happens-before B，且B happens-before C，那么A happens-before C。
5）start()规则：如果线程A 执行操作ThreadB.start()(线程B启动)，那么A线程的ThreadB.start()操作happens-before于线程B中的任意操作。
6）join规则：如果线程A执行操作ThreadB.join()并成功返回，那么线程B中的任意操作happens-before于线程A从ThreadB.join()操作成功的返回。
总结：Java提供了锁和CAS来保证原子性操作，通过JMM的规则来禁止一些重排序，通过JMM的happens-before规则来保证内存的可见性。我们可以看到规则里面有一些关键字，volatile（通过内存屏障）、锁保证了可见性，我们在下面的章节详解---------------------------以下是个人理解：我们结合硬件缓存模型来看，其实JMM是对处理器缓存模型的一种实现，硬件实现了最终缓存在一致性的方案，并提供了强一致性缓存的解决方案（内存屏障的指令），JMM实现了这个方案，在我们需要的时候（插入内存屏障）提供强大的可见性保证，不需要时遵循硬件的优化策略（可以进行指令重排序优化，提高执行性能）。