转载自:http://fromwiz.com/share/s/27gDU_1XA17w2yWIUS2AA_om1qpX2f2z94RJ2ycv6S2PHuwD

1.背景

在阅读java中volatile的关键词语义时,发现很多书中都使用了重排序这个词来描述,同时又讲到了线程工作内存和主存等等相关知识。但是只用那些书的抽象定义进行理解时总是感觉什么地方说不通,最后发现,是那些书中使用的抽象屏蔽了一些对读者的知识点,反而导致了理解上的困难。因此有了这篇文章。没有任何虚构的理解抽象,从硬件的角度来理解什么是内存屏障,以及内存屏障如何让volatile工作。最后说明了在多线程中,如何使用volatile来提升性能。

2.存储结构

在计算机之中,存在着多级的存储结构。这是为了适应不同硬件速度带来的差异。底层是主存(也就是内存),容量最大,速度最慢;中间是cpu的缓存(现代cpu都有多级缓存结构,级别越高速度越慢,但是可以将多级缓存看成是一个整体),容量较小,但是速度很快;最上层是cpu自身的store buffer和Invalidate Queues,速度最快,容量非常少。其中主存和cpu缓存的数据视图对于每一个cpu都是相同的,也就是说在这个级别上,每个cpu都看到了相同的数据,而store buffer和Invalidate Queues是每一个cpu私有的。这就导致了一系列的编程问题,下文会详细展开。

2.1CPU缓存

Cpu为了平衡自身处理速度过快和主存读写速度过慢这个问题,使用了缓存来存储处理中的热点数据。cpu需要处理数据的时候(包含读取和写出),都是直接向缓存发出读写指令。如果数据不在缓存中,则会从主存中读取数据到缓存中,再做对应的处理。需要注意的是,cpu读取数据到缓存中,是固定长度的读取。也就是说cpu缓存是一行一行的载入数据进来。因为也称之为cpu缓存行,即cacheline。而缓存中的数据,也会在合适的时候回写到主存当中(这个时机可以抽象的认为是由cpu自行决定的)。
现在的cpu都是多核cpu,为了在处理数据的时候保持缓存有效性,因此一个cpu需要数据而且该数据不在自身的cache中的时候,会同时向其他的cpu缓存和主存求取。如果其他的cpu缓存中有数据,则使用该数据,这样就保证了不会使用到主存中的错误的尚未更新的旧数据。
而各个cpu的内部缓存依靠MESI缓存一致性协议来进行协调。以此保证各个Cpu看到的内容是一致的。

在MESI协议中,每个Cache line有4个状态,可用2个bit表示,它们分别是:

状态 描述
M(Modified) 这行数据有效,数据被修改了,和内存中的数据不一致,数据只存在于本Cache中。
E(Exclusive) 这行数据有效,数据和内存中的数据一致,数据只存在于本Cache中。
S(Shared) 这行数据有效,数据和内存中的数据一致,数据存在于很多Cache中。
I(Invalid) 这行数据无效

2.2 Store buffer

如果一个Cpu要写出一个数据,但是此时这个数据不在自己的cacheline中,因为cpu要向其他的cpu缓存发出read invalidate消息。等待其他的cpu返回read response和invalidate ack消息后,将数据写入这个cacheline。这里就存在着时间的浪费,因为不管其他的cpu返回的是什么数据,本cpu都是要将它覆盖的。而在等待的这段时间,cpu无事可干,只能空转。为了让cpu不至于空闲,因为设计了store buffer组件。store buffer是每个cpu独享的写入缓存空间,用于存储对cacheline的写入,而且速度比cacheline高一个数量级,但是容量非常少。
但是store buffer会产生在单核上的读写不一致问题。下面是模拟

a = 1;
b = a+1;
assert b==2;

假设a不在本cpu的cacheline中。在其他cpu的cacheline中,值为0.会有如下的步骤

序号 操作内容
1 发现a的地址不在本cpu的cacheline中,向其他的cpu发送read invalidate消息
2 将数据写入store buffer中
3 收到其他cpu响应的read response和invalidate ack消息
4 执行b=a+1,因为a这个时候已经在cacheline中,读取到值为0,加1后为1,写入到b中
5 执行assert b==2 失败,因为b是1
6 store buffer中的值刷新到a的cacheline中,修改a的值为1,但是已经太晚了

为了避免这个问题,所以对于store buffer的设计中增加一个策略叫做store forwarding。就是说cpu在读取数据的时候会先查看store buffer,如果store buffer中有数据,直接用store buffer中的。这样,也就避免了使用错误数据的问题了。
store forwarding可以解决在单线程中的数据不一致问题,但是store buffer所带来的复杂性远不止如此。在多线程环境下,会有其他的问题。下面是模拟代码

public void set(){
  a=1;
  b=1;
}
public void print(){
 while(b==0)
 ;
 assert a==1;
}

假设a和b的值都是0,其中b在cpu0中,a在cpu1中。cpu0执行set方法,cpu1执行print方法。

序号 cpu0的步骤(执行set) cpu1的步骤(执行print)
1 想写入a=1,但是由于a不在自身的cacheline中,向cpu1发送read invalidate消息 执行while(b==0),由于b不在自身的cacheline中,向cpu0发送read消息
2 向store buffer中写入a=1 等待cpu0响应的read response消息
3 b在自身的cacheline中,并且此时状态为M或者E,写入b=1 等待cpu0响应的read response消息
4 收到cpu1的read请求,将b=1的值用read response消息传递,同时将b所在的cacheline修改状态为s 等待cpu0响应的read response消息
5 等待cpu1的read response和invalidate ack消息 收到cpu0的read response消息,将b置为1,因此程序跳出循环
6 等待cpu1的read response和invalidate ack消息 因为a在自身的cacheline中,所以读取后进行比对。assert a==1失败。因为此时a在自身cacheline中的值还是0,而且该cacheline尚未失效
7 等待cpu1的read response和invalidate ack消息 收到cpu0发送的read invalidate消息,将a所在的cacheline设置为无效,但是 为时已晚,错误的判断结果已经产生了
8 收到cpu1响应的read response和invalidate ack消息,将store buffer中的值写入cacheline中

通过上面的例子可以看到,在多核系统中,store buffer的存在让程序的结果与我们的预期不相符合。上面的程序中,由于store buffer的存在,所以在cacheline中的操作顺序实际上先b=1然后a=1。就好像操作被重排序一样(重排序这个词在很多文章中都有,但是定义不详,不好理解。实际上直接理解store buffer会简单很多)。为了解决这样的问题,cpu提供了一些操作指令,来帮助我们避免这样的问题。这样的指令就是内存屏障(英文fence,也翻译叫做栅栏)。来看下面的代码

public void set(){
  a=1;
  smp_mb();
  b=1;
}
public void print(){
 while(b==0)
 ;
 assert a==1;
}

smb_mb()就是内存屏障指令,英文memory barries。它的作用,是在后续的store动作之前,将sotre buffer中的内容刷新到cacheline。这个操作的效果是让本地的cacheline的操作顺序和代码的顺序一致,也就是让其他cpu观察到的该cpu的cacheline操作顺序被分为smp_mb()之前和之后。要达到这个目的有两种方式

  1. 遇到smp_mb()指令时,暂停cpu执行,将当前的store_buffer全部刷新到cacheline中,完成后cpu继续执行
  2. 遇到smp_mb()指令时,cpu继续执行,但是所有后续的store操作都进入到了store buffer中,直到store buffer之前的内容都被刷新到cacheline,即使此时需要store的内容的cacheline是M或者E状态,也只能先写入store buffer中。这样的策略,既可以提升cpu效率,也保证了正确性。当之前store buffer的内容被刷新到cacheline完成后,后面新增加的内容也会有合适的时机刷新到cacheline。把store buffer想象成一个FIFO的队列就可以了。

下面来看,当有了smp_mb()之后,程序的执行情况。所有的初始假设与上面相同。

序号 cpu0的步骤(执行set) cpu1的步骤(执行print)
1 想写入a=1,但是由于a不在自身的cacheline中,向cpu1发送read invalidate消息 执行while(b==0),由于b不在自身的cacheline中,向cpu0发送read消息
2 向store buffer中写入a=1 等待cpu0响应的read response消息
3 遇到smp_mb(),等待直到可以将store buffer中的内容刷新到cacheline 等待cpu0响应的read response消息
4 等待直到可以将store buffer中的内容刷新到cacheline 收到cpu0发来的read invalidate消息,发送a=0的值,同时将自身a所在的cacheline修改为invalidate状态
5 收到cpu1响应的read response和invalidate ack消息,将a=0的值设置到cacheline,随后store buffer中a=1的值刷新到cacheline,设置cacheline状态为M 等待cpu0响应的read response消息
6 由于b就在自身的cacheline中,并且状态为M或者E,设置值为b=1 等待cpu0响应的read response消息
7 收到cpu1的read请求,将b=1的值传递回去,同时设置该cacheline状态为s 等待cpu0响应的read response消息
8 收到cpu0的read response信息,将b设置为1,程序跳出循环
9 由于a所在的cacheline被设置为invalidate,因此向cpu0发送read请求
10 收到cpu1的read请求,以a=1响应,并且将自身的cacheline状态修改为s 等待cpu0的read response响应
11 收到read response请求,将a设置为1,执行程序判断,结果为真

可以看到,在有了内存屏障之后,程序的真实结果就和我们的预期结果相同了。

2.3 invalidate queue

使用了store buffer后,cpu的store性能会提升很多。然后store buffer的容量是很小的(越快的东西,成本就越高,一定就越小),cpu以中等的频率填充store buffer。如果不幸发生比较多的cache miss,那么很快store buffer就被填满了,cpu只能等待。又或者程序中调用了smp_mb()指令,这样后续的操作都只能进入store buffer,而不管相关cacheline是否处于M或者E状态。
store buffer很容易满的原因是因为收到其他cpu的invalidate ack的速度太慢。而cpu发送invalidate ack的速度太慢是因为cpu要等到将对应的cacheline设置为invalidate后才能发送invalidate ack。有的时候太多invalidate请求,cpu的处理速度就跟不上。为了加速这个流程,硬件设计者设计了invaldate queue来加速这个过程。收到的invalidate请求先放入invalidate queue,然后之后立刻响应invalidate ack消息。而cpu可以在随后慢慢的处理这些invalidate消息。当然,这里必须不能太慢。也就是说,cpu实际上给出了一个承诺,如果一个invalidatge请求在invalidate queue中,那么对于这个请求相关的cacheline,在该请求被处理完成前,cpu不会再发送任何与该cacheline相关的MESI消息。在有了store buffer和invalidate queue后,cpu的处理速度又可以更高。下面是结构图。

但是在引入了invalidate queue又会导致另外一个问题。下面先来看代码

public void set(){
  a=1;
  smp_mb();
  b=1;
}
public void print(){
 while(b==0)
 ;
 assert a==1;
}

代码与上面的例子相同,但是初始条件不同了。这次a同时存在于cpu0和cpu1之中,状态为s。b是cpu0独享,状态为E或者M。

序号 cpu0的步骤(执行set) cpu1的步骤(执行print)
1 想写入a=1,但是由于a的状态是s,向cpu1发送invalidate消息 执行while(b==0),由于b不在自身的cacheline中,向cpu0发送read消息
2 向store buffer中写入a=1 收到cpu0的invalidate消息,放入invalidate queue,响应invalidate ack消息。
3 遇到smp_mb(),等待直到可以将store buffer中的内容刷新到cacheline。 立刻收到cpu0的invalidate ack,将store buffer中的a=1写入到cacheline,并且修改状态为M 等待cpu0响应的read response消息
4 由于b就在自己的cacheline中,写入b=1,修改状态为M 等待cpu0响应的read response消息
5 收到cpu1响应的read请求,将b=1作为响应回传,同时将cacheline的状态修改为s。 等待cpu0响应的read response消息
6 收到read response,将b=1写入cacheline,程序跳出循环
7 由于a所在的cacheline还未失效,load值,进行比对,assert失败
8 cpu处理invalidate queue的消息,将a所在的cacheline设置为invalidate,但是已经太晚了

上面的例子,看起来就好像第一个一样,仍然是b=1先生效,a=1后生效。导致了cpu1执行的错误。就好像内存操作”重排序”一样(个人不太喜欢内存操作重排序这个术语,因为实际上并不是重新排序的问题,而是是否可见的问题。但是用重排序这样的词语,反而不好理解。但是很多书都是用是了这个词语,大家可以有自己的理解。但是还是推荐不要理会这些作者的抽象概念,直接了解核心)。其实这个问题的触发,就是因为invalidate queue没有在需要被处理的时候处理完成,造成了原本早该失效的cacheline仍然被cpu认为是有效,出现了错误的结果。那么只要让内存屏障增加一个让invalidate queue全部处理完成的功能即可。
硬件的设计者也是这么考虑的,请看下面的代码

public void set(){
  a=1;
  smp_mb();
  b=1;
}
public void print(){
 while(b==0)
 ;
 smp_mb();
 assert a==1;
}

a同时存在于cpu0和cpu1之中,状态为s。b是cpu0独享,状态为E或者M。

序号 cpu0的步骤(执行set) cpu1的步骤(执行print)
1 想写入a=1,但是由于a的状态是s,向cpu1发送invalidate消息 执行while(b==0),由于b不在自身的cacheline中,向cpu0发送read消息
2 向store buffer中写入a=1 收到cpu0的invalidate消息,放入invalidate queue,响应invalidate ack消息。
3 遇到smp_mb(),等待直到可以将store buffer中的内容刷新到cacheline。 立刻收到cpu0的invalidate ack,将store buffer中的a=1写入到cacheline,并且修改状态为M 等待cpu0响应的read response消息
4 由于b就在自己的cacheline中,写入b=1,修改状态为M 等待cpu0响应的read response消息
5 收到cpu1响应的read请求,将b=1作为响应回传,同时将cacheline的状态修改为s。 等待cpu0响应的read response消息
6 收到read response,将b=1写入cacheline,程序跳出循环
7 遇见smp_mb(),让cpu将invalidate queue中的消息全部处理完后,才能继续向下执行。此时将a所在的cacheline设置为invalidate
8 由于a所在的cacheline已经无效,向cpu0发送read消息
9 收到read请求,以a=1发送响应 收到cpu0发送的响应,以a=1写入cacheline,执行assert a==1.判断成功

可以看到,由于内存屏障的加入,程序正确了。

2.4 内存屏障

通过上面的解释和例子,可以看出,内存屏障是是因为有了store buffer和invalidate queue之后,被用来解决可见性问题(也就是在cacheline上的操作重排序问题)。内存屏障具备两方面的作用

  1. 强制cpu将store buffer中的内容写入到cacheline中
  2. 强制cpu将invalidate queue中的请求处理完毕

但是有些时候,我们只需要其中一个功能即可,所以硬件设计者们就将功能细化,分别是

  • 读屏障: 强制cpu将invalidate queue中的请求处理完毕。也被称之为smp_rmb
  • 写屏障: 强制cpu将store buffer中的内容写入到cacheline中或者将该指令之后的写操作写入store buffer直到之前的内容被写入cacheline.也被称之为smp_wmb
  • 读写屏障: 强制刷新store buffer中的内容到cacheline,强制cpu处理完invalidate queue中的内容。也被称之为smp_mb

3. JMM内存模型

在上面描述中可以看到硬件为我们提供了很多的额外指令来保证程序的正确性。但是也带来了复杂性。JMM为了方便我们理解和使用,提供了一些抽象概念的内存屏障。注意,下文开始讨论的内存屏障都是指的是JMM的抽象内存屏障,它并不代表实际的cpu操作指令,而是代表一种效果。

LoadLoad Barriers
该屏障保证了在屏障前的读取操作效果先于屏障后的读取操作效果发生。在各个不同平台上会插入的编译指令不相同,可能的一种做法是插入也被称之为smp_rmb指令,强制处理完成当前的invalidate queue中的内容
StoreStore Barriers
该屏障保证了在屏障前的写操作效果先于屏障后的写操作效果发生。可能的做法是使用smp_wmb指令,而且是使用该指令中,将后续写入数据先写入到store buffer的那种处理方式。因为这种方式消耗比较小
LoadStore Barriers
该屏障保证了屏障前的读操作效果先于屏障后的写操作效果发生。
StoreLoad Barriers
该屏障保证了屏障前的写操作效果先于屏障后的读操作效果发生。该屏障兼具上面三者的功能,是开销最大的一种屏障。可能的做法就是插入一个smp_mb指令来完成。

3.1 内存屏障在volatile关键中的使用

内存屏障在很多地方使用,这里主要说下对于volatile关键字,内存屏障的使用方式。

在每个volatile写操作的前面插入一个StoreStore屏障。
在每个volatile写操作的后面插入一个StoreLoad屏障。
在每个volatile读操作的后面插入一个LoadLoad屏障。
在每个volatile读操作的后面插入一个LoadStore屏障。
上面的内存屏障方式主要是规定了在处理器级别的一些重排序要求。而JMM本身,对于volatile变量在编译器级别的重排序也制定了相关的规则。可以用下面的图来表示

3.2 Happen-before

JMM为了简化对编程复杂的理解,使用了HB来表达不同操作之间的可见性。HB关系在不同的书籍中有不同的表达。这里推荐一种比较好理解的。

A Happen before B,说明A操作的效果先于B操作的效果发生。这种偏序关系在单线程中是没有什么作用的,因为单线程中,执行效果要求和代码顺序一致。但是在多线程中,其可见性作用就非常明显了。举个例子,在线程1中进行进行a,b操作,操作存在hb关系。那么当线程2观察到b操作的效果时,必然也能观察到a操作的效果,因为a操作Happen before b操作。
在java中,存在HB关系的操作一共有8种,如下。

程序次序法则,如果A一定在B之前发生,则happen before
监视器法则,对一个监视器的解锁一定发生在后续对同一监视器加锁之前
Volatie变量法则:写volatile变量一定发生在后续对它的读之前
线程启动法则:Thread.start一定发生在线程中的动作前
线程终结法则:线程中的任何动作一定发生在线程终结之前(其他线程检测到这个线程已经终止,从Thread.join调用成功返回,Thread.isAlive()返回false)
中断法则:一个线程调用另一个线程的interrupt一定发生在另一线程发现中断之前。
终结法则:一个对象的构造函数结束一定发生在对象的finalizer之前
传递性:A发生在B之前,B发生在C之前,A一定发生在C之前。
使用HB关系,在多线程开发时就可以尽量少的避免使用锁,而是直接利用hb关系和volatile关键字来达到信息传递并且可见的目的。
比如很常见的一个线程处理一些数据并且修改标识位后,另外的线程检测到标识位发生改变,就接手后续的流程。此时如何保证前一个线程对数据做出的更改后一个线程全部可见呢。先来看下面的代码例子

class VolatileExample {
    int a = 0;
    volatile boolean flag = false;
    public void writer() {
        a = 1;     //1
        flag = true;    //2
    }
    public void reader() {
        while(flag==false); //3
        int i=a; //4
    }
}

有两个不同的线程分别执行writer和reader方法,根据Hb规则,有如下的顺序执行图。

这样的顺序,i读取到的a的值就是最新的,也即是1.