内存屏障

内存屏障

  现代计算机大多数采用多核处理器或多处理器以提高性能,同时每个处理器通常存在一层或多层高速缓存,这将会更进一步加快对数据的访问。但是这也带来了新的挑战,即同一数据在不同处理器之间并不保证一致。所以为了保证数据的可见性,内存屏障应运而生。它能够刷新或使本地处理器高速缓存失效,以便查看其他处理器进行的写入的最新值或使该处理器的写入对其他处理器可见。而Java内存模型用于屏蔽不同硬件所带来的内存访问差异,以实现程序在不同平台能保证一致的并发效果。那么在并发环境下如何正确的使用内存屏障成为了首要问题。

硬件内存架构

Java内存模型是对硬件内存模型的抽象,因此理解它需要一些硬件基础知识。这里主要介绍 处理器的存储器结构处理器的高速缓存与缓存一致性

随机访问存储器(RAM)

随机访问存储器(RAM),是用于和CPU交换数据的内部存储器。根据存储单元的工作原理不同可以分为两类:

  • 动态的存储器(DRAM)
  • 静态的存储器(SRAM)

SRAM比DRAM更快,但也更贵,因此SRAM主要作为高速缓存存储器(Cache,如CPU的L1,L2),而DRAM则作为计算机主存。而我们常说的内存指的就是是计算机的主内存DRAM。

总线(Bus)

总线是一组并行的导线,能携带地址,数据和控制信号,用于计算机各种功能部件(CPU,DRAM,I/O设备等)之间传送信息。根据传输的信息种类,计算机的总线可以划分为数据总线、地址总线和控制总线。CPU则是通过数据总线与内存交换数据的(即通信)

  CPU和主存(DRAM)之间的数据传送称为总线事务,读事务代表从主存传送数据到CPU,写事务代表从CPU传送数据到主存。

它们同个两条总线连接起来,一条是系统总线(连接CPU和I/O桥接器),一条是内存总线(连接I/O桥接器和DRAM),其中I/O桥接器会将系统总线的电子信号翻译成内存总线的电子信号。

  • 读事务(movq A, %rax):

    • 首先CPU将地址A放到系统总线并通过I/O桥传递到内存总线
    • 接着DRAM感受到内存总线的地址信号并读取地址,并将其对应的数据写回内存总线通过I/O桥传递到系统总线
    • 最后CPU感觉到系统总线的数据并读取数据复制到寄存器中完成读事务。

  • 写事务(movq %rax, A):

    • 首先CPU将地址A放到系统总线,DRAM从内存总线读出地址,并等到数据到达
    • 接着,CPU将寄存器中的%rax放到系统总线
    • 最后,DRAM从内存总线读出数据,并存储到DRAM中

存储器层次结构

以一个经典的存储器层次结构举例,所有现代计算机系统都是采用用这种结构

从上至下,存储设备的速度变得更慢,容量更大。顶层是最快的寄存器,CPU可以在一个时钟周期内访问,接下来是L1-L3缓存(它们用的就是之前所说的SRAM),然后就是计算机主存(DRAM),再往下就是磁盘等等。

而Inter Core i7中的高速缓存如下:

Intel Core i7处理器的的每个CPU芯片有4个核。每个核有自己私有的L1,L2高速缓存,所有的核共享L3统一高速缓存。

高速缓存的读和写

略过把内存地址映射到快速缓存块的内容(这里不需要相关知识),高速缓存的读分为缓存命中和缓存不命中。

  • 对于缓存命中,即当程序需要读取K+1层的某个数据时,当前K层的缓存已经存在,那么直接读取数据
  • 而对于缓存不命中,即K层没有存储数据,那么将从K+1层缓存读取数据,同时如果K层的缓存已经满了,可能需要覆盖现存的块。如通过LRU算法替换被访问时间距现在最远的块。

而对于高速缓存的写则有两种方案

  • 直写(write through) + 非写分配(not write allocate):

    • 直写:写命中时(即要写一个已经缓存的数据),同时写入缓存以及主内存

    • 非写分配:写不命中时,不将写入位置读入缓存,直接将数据写入主内存

  • 回写(write back) + 写分配(write allocate):

    • 回写:写命中时,只写入缓存,只在数据被替换出缓存时才会将数据写到主内存

    • 写分配:写不命中时,将写入位置读入缓存,然后以写命中的方式进行写入(即回写)

有些(大多数是比较老的)CPU只使用直写模式,有些只使用回写模式,还有一些,一级缓存使用直写而二级缓存使用回写。这样做虽然在一级和二级缓存之间产生了不必要的数据流量,但二级缓存和更低级缓存或内存之间依然保留了回写的优势。对于直写(write through),它需要一个写缓冲区(write buffer)将高速缓存写入的数据保存的主内存中

  写缓冲区的作用类似于异步处理来提高性能,比如当CPU的写入速度比缓存响应的还快时则减少了等待的时间,大大提高性能;同时它还能聚合多个写入到同一个缓存块从而减少下一级缓存的流量

缓存一致性

如果系统只有一个CPU核在工作,那么一些都没有问题。而如果一个CPU有多个核,且每个核都有自己的缓存,那么就会遇到问题:如果某个CPU缓存段中对应的内存内容被另外一个CPU改了,它无法感知到。而对于回写模式,写指令甚至会在执行过后很久才会真正写到DRAM中,这就造成了多组缓存不一致的问题。

   注意,这个问题的原因不在于多核而在于多组缓存。假如多个CPU核共用一组缓存,是不会存在这个问题的

为了保证缓存一致性,MESI协议就出现了。MESI是四种缓存段状态的首字母缩写,任何多核系统中的缓存段都处于只有四种状态:失效(Invalid)缓存段,共享(Shared)缓存段,独占(Exclusive)缓存段,已修改(Modified)缓存段。

  • 失效(Invalid)缓存段: 要么已经不在缓存中,要么它的内容已经过时。为了达到缓存的目的,这种状态的段将会被忽略。一旦缓存段被标记为失效,那效果就等同于它从来没被加载到缓存中。
  • 共享(Shared)缓存段,它是和主内存内容保持一致的一份拷贝,在这种状态下的缓存段只能被读取,不能被写入。多组缓存可以同时拥有针对同一内存地址的共享缓存段,这就是名称的由来。
  • 独占(Exclusive)缓存段,和S状态一样,也是和主内存内容保持一致的一份拷贝。区别在于,如果一个处理器持有了某个E状态的缓存段,那其他处理器就不能同时持有它,所以叫“独占”。这意味着,如果其他处理器原本也持有同一缓存段,那么它会马上变成“失效”状态。
  • 已修改(Modified)缓存段,属于脏段,它们已经被所属的处理器修改了。如果一个段处于已修改状态,那么它在其他处理器缓存中的拷贝马上会变成失效状态,这个规律和E状态一样。此外,已修改缓存段如果被丢弃或标记为失效,那么先要把它的内容回写到内存中——这和回写模式下常规的脏段处理方式一样。

该协议保证:只有当缓存段处于E或M状态时处理器才能去修改它,也就是说只有这两种状态下,处理器是独占这个缓存段的。当处理器想写某个缓存段时,如果它没有独占权,它必须先发送一条“我要独占权”的请求给总线,这会通知其他处理器,把它们拥有的同一缓存段的拷贝失效。

而如果有其他处理器想读取这个缓存段,独占或已修改的缓存段必须先回到“共享”状态。如果是已修改的缓存段,那么还要先把内容回写到内存中。

也就是说,MESI保证一旦某个缓存段被回写修改后(M状态),任意缓存级别的所有缓存段的内容和它对应的内存内容一致

写缓冲区和失效队列

缓存一致性已经能够保证对单个地址的读写的内存上的完整一致性,但是同步等待其他处理器指令返回影响了处理性能。因此在寄存器和L1缓存之间会有读写缓冲区(LoadBuffer, StoreBuffer),合称排序缓冲(Memoryordering Buffers ,MOB )。它们使得CPU异步处理读写指令,即当前处理器不需要等待其他处理器的失效确认(Invalidate Acknowlege)返回,会直接处理接下去的指令。 比如

  • 写指令:对于已处于E(独占)状态的缓存行,CPU会直接写入缓存行;而对于其他需要切换回E状态的情况,则首先向其他处理器发出失效指令,接着把要写入到主存的值写到StoreBuffer,然后处理接下去指令。而StoreBuffer中的数据则等待失效确认(Invalidate Acknowlege)返回后统一刷新到内存。
  • 读指令:对于处于S(共享)状态的缓存行命中时,CPU会直接读取缓存完成读指令;而对于其他状态需要切回S状态的情况,则会放入LoadBuffer中等待确认后处理

但是这会导致一个严重的问题:

  即使读写指令本身是按照顺序执行的,但最终仍然存在指令重排序

比如按顺序执行A, B两个写指令,A写指令所在缓存行处于S状态,B写指令所在缓存行处于E状态,那么B会比A先完成写入操作;又或者按顺序执行C, D两个读指令,C读指令所在缓存行处于I状态,D读指令所在缓存行处于S状态,那么D会比C先完成读取操作。

同时处理器执行失效也不是一个简单的操作,它需要占用处理器的时间,如果接受的invalidate请求过多,cpu处理速度就跟不上,因此又出现了失效队列(invalidate queue),它保证:

  • 对于所有的收到的Invalidate请求,Invalidate Acknowlege消息必须立刻发送返回
  • Invalidate并不真正执行,而是被放在一个失效队列中,在方便的时候才会去执行。【当然,这里必须不能太慢。也就是说,cpu实际上给出了一个承诺,如果一个invalidatge请求在invalidate queue中,那么对于这个请求相关的cacheline,在该请求被处理完成前,cpu不会再发送任何与该cacheline相关的MESI消息。 】

同样这也会导致一个严重的问题:

  读取的时候有可能会读到过时的数据

比如CPU0执行写指令,它向CPU1发出失效指令,然后CPU1立刻返回失效确认,但实际上并未真正执行失效操作。这时CPU0则更新了缓存行,造成了不同处理器直接的数据不一致。

所以我们现在可以总结下目前遇到的问题:

  • 乱序处理器在满足As-if-Serial特性的基础下,本身就不会严格按照程序的顺序向缓存发送内存操作指令,导致指令重排序。
  • Java运行时环境的JIT编译器指令重排序
  • 由于store buffer和invalidate queue导致的内存可见性问题(即内存重排序)

  As-if-serial 语义的意思指:不管怎么重排序(编译器和处理器为了提高并行度),(单线程)程序的执行结果不能被改变。编译器,runtime 和处理器都必须遵守 as-if-serial 语义。比如:

1
2
3
double pi  = 3.14;    // A
double r = 1.0; // B
double area = pi r r; // C

这里例子中,A和B可以重排序,但是A和C,B和C不行,因为它们存在数据依赖关系。但需要注意的是,控制依赖仍然会存在重排序,比如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class ReorderExample {
int a = 0;
boolean flag = false;

public void writer() {
a = 1; //1
flag = true; //2
}

Public void reader() {
if (flag) { //3
int i = a * a; //4
……
}
}
}

看起来3和4存在控制依赖关系,不应该重排序,而实际上,编译器和处理器会采用猜测(Speculation)执行来克服控制相关性对并行度的影响。这里3和4操作可能会被重排序为:

1
2
3
4
5
6
7
// 先把计算结果临时保存到一个名为重排序缓冲(reorder buffer ROB)的硬件缓存中
temp = a * a;

if(flag){
// 当flag为真后再赋值进去
int i = temp
}

那么它们会导致什么问题呢?我们以两个典型的案例来让问题显形:

  • CPUB依赖于CPUA发出的信号来执行逻辑

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    DRAM: x = 0; y = false;

    CPUA:
    x = 1;
    y = true;

    CPUB:
    if(y){
    assert x = 1;
    }

    这个案例有可能会出现CPUB断言错误的情况,可能原因有以下几种

    • 由于指令重排序,CPUA的两个写入指令重排序,导致CPUB读取到y=true时,x=0
    • 虽然指令未重排序,但由于store buffer的存在导致CPUA对x=1的指令写入主内存不及时使得y=true先被写入内存,那么CPUB就有可能读到老数据
    • 虽然指令未重排序,但由于invalidate queue的存在导致虽然Invalidate Acknowlege返回后使得store buffer的数据已经回写到主存,但是由于失效消息未处理导致CPUB的缓存行仍有效,读到了老数据。
  • CPUA,CPUB互相读取对方的写入

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    DRAM:
    x, y, r1, r2 = 0

    CPUA:
    x = 1;
    r1 = y;

    CPUB:
    y = 1;
    r2 = x;

    和上述类似同样的原因,这个案例有可能会出现 r1 = r2 = 0 的情况。

为了解决上述案例产生的问题,内存屏障诞生 =͟͟͞͞( •̀д•́)

内存屏障

JDK1.7根据store/load指令的先后顺序将内存屏障分为以下四种:

  • LoadLoad 屏障

    • 防止LoadLoad屏障前后的读指令的指令重排序
    • 处理器以阻塞的方式先处理失效队列的消息,防止读取到老数据
  • StoreStore 屏障

    • 防止StoreStore屏障前后的写指令的指令重排序
    • 处理器以阻塞的方式将当前存储缓存(store buffer)的值写回主存
  • LoadStore 屏障

    • 防止LoadStore屏障前的读指令和屏障后的写指令的指令重排序
    • 处理器以阻塞的方式先处理失效队列的消息,防止读取到老数据

    在JVM中,实际上它和LoadLoad屏障作用是相同的,底层都是调用 acquire() 方法

  • StoreLoad 屏障

    • 防止StoreLoad屏障前后的所有读写指令的指令重排序
    • 处理器以阻塞的方式将当前存储缓存(store buffer)的值写回主存
    • 处理器以阻塞的方式先处理失效队列的消息,防止读取到老数据

    该屏障同时具备另三种屏障的作用,因此开销也最大。

它们并不是真正意义上的内存屏障,只是一种抽象的概念。在不同硬件中,内存屏障会有不同的实现。比如x86的64位CPU提供了mfence, lfence, sfence指令来提供内存屏障,而x86的32位CPU则不提供mfence、lfence、sfence三条汇编指令的支持。因此Linux内核定义smp_mb, smp_rmb,smp_wmb三种内存屏障来处理不同处理器架构(比如对于X86-64直接使用上述指令,而对于X86-32则通过lock前缀来实现)

案例重现

了解了内存屏障的作用后,我们重新再来分析之前的两个案例

  • CPUB依赖于CPUA发出的信号来执行逻辑

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    DRAM: x = 0; y = false;

    CPUA:

    x = 1;

    StoreStore()

    y = true;

    CPUB:

    if(y){

    LoadLoad()

    assert x = 1;

    }

    我们在CPUA和CPUB的程序中分别插入StoreStore屏障和LoadLoad屏障。它们能保证以下三点:

    • CPUA的写写指令,CPUB的读读指令不能重排序
    • CPUA写入x变量的值后保证将store buffer缓存的数据写回主内存。即写入x到主内存一定先于y
    • CPUB在读取到y的值后保证先处理invalidate queue的失效消息,即读取到y会重新从主内存获取最新的x的值

    那么这就保证一个顺序链:x写入到主存 < y写入到主存 < y从主存读取数据 < x从主存读取数据。也就意味值:一旦CPUB读取到 y=true,x的值总是等于1

  • CPUA,CPUB互相读取对方的写入

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    DRAM:
    x, y, r1, r2 = 0

    CPUA:
    x = 1;

    StoreLoad();

    r1 = y;

    CPUB:
    y = 1;

    StoreLoad();

    r2 = x;

    我们在CPUA和CPUB的程序中都插入了StoreLoad屏障。它们能保证以下三点:

    • CPUA和CPUB均不会对写入x和读取y两个操作重排序

    • CPUA和CPUB写入值后保证将store buffer缓存的数据写回主内存

    • CPUA和CPUB读取值之前保证先处理invalidate queue,即总是读到主内存的最新数据

    那么我们可以推导出,当任一处理器执行到读取指令时,必定已经写入了当前值到主存且重新从主存读取数据,那么 r1 = r2 = 0 的情况也是不可能的了。

      该案例必须使用StoreLoad屏障。因为CPUA的读的值依赖于CPUB的写,而CPUB的读的值也依赖于CPUA的写,那么就需要同时保证写的及时性和读的正确性了。而每个处理器同时插入两条屏障(LoadLoad屏障,StoreStore屏障)也是不行的,因为它们都不能保证读写指令的重排序。

volatile小解

JMM通过内存屏障实现了volatile的内存语义,这里简单的讨论它的两点特性

  volatile如何保证读取能读取到最新值?

仅从CPU层面来看,单个变量能够保证最终一致性的,即总能在一定时间内读取到最新值,因此不会存在读不到最新值的情况。但由于java的JIT即时编译器的存在,会使得生成的汇编指令总是从寄存器暂存的数据获取值(甚至直接将值定义为常量),因此会有即使变量在主存更新了依然无法读取到变量的最新值的情况。

  寄存器不同于高速缓存,CPU大多只能与寄存器交互(有些也可以和L1缓存交互,这里的高速缓存指的是无法直接交互的缓存),高速缓存的存在是因为CPU和主存交互太慢,需要缓存来提供性能。那么如果CPU始终从寄存器的暂存数据中读取,即使缓存是最终一致的,也会永远都不到最新值。

而volatile的读基于C++的volatile实现:

1
inline jint OrderAccess::load_acquire(volatile jint* p) { return *p; }

它是一种编译器屏障,会禁止编译器优化,生成的加载指令不能从寄存器取值,而是总是从内存中加载(虽然由于高速缓存的存在,实际上总是从缓存加载),而因为缓存是最终一致的,因此可以保证可见性。

  volatile如何保证写入最新值?

volatile变量在写入后会插入StoreLoad屏障(lock前缀的效果同StoreLoad屏障),即

1
__asm__ volatile ("lock; addl $0,0(%%rsp)" : : : "cc", "memory");

这样就保证了每次写入都会到主内存。

  • volatile写之前会插入StoreStore,防止和之前的任何写指令重排序

  • volatile读之后会插入LoadLoad,LoadStore屏障,保证不和之后的读写指令重排序

至于原因,可以参考之前的两个案例。实际上通过volatile关键字就能保证上述两个案例的并发正确性

Final小解

JMM同样通过内存屏障在一些情景下实现final的内存语义,这里也简单的讨论下

  • 初始读取共享对象与初始读取该共享对象的final成员变量之间不能重排序

    1
    2
    3
    x = sharedRef; 
    ... ;
    i = x.finalField;

    当存在数据依赖关系时,编译器本身不会对它们重排序。但确实有一些处理器会对这种情况进行重排序,因此特别制定了这一规则

  • 如果在构造函数中有一条final字段的store指令,同时这个字段是一个引用,那么它将不能与构造函数外后续可以让持有这个final字段的对象被其他线程访问的指令重排。…代表构建方法边界

    1
    2
    3
    x.finalField = v; ... ; sharedRef = x;

    v.afield = 1; x.finalField = v; ... ; sharedRef = x;

    JMM为了满足final的这种特殊规则,实际上就是加了一个StoreStore屏障

    1
    x.finalField = v; ... ; StoreStore() sharedRef = x;

参考链接

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×