Java重排序和顺序一致性模型

重排序

重排序是指编译器和处理器为了优化程序性能而对指令序列进行重新排序的一种手段

数据依赖性

  如果两个操作访问同一个变量,且这两个操作中有一个为写操作,此时这两个操作之间就存在数据依赖性.数据依赖分为下列3种类型,如下表所示

上面3种情况,只要重排序两个操作的执行顺序,程序的执行结果就会被改变

  前面提到过,编译器和处理器可能会对操作做重排序.编译器和处理器在重排序时,会遵守数据依赖性,编译器和处理器不会改变存在数据依赖关系的两个操作的执行顺序
  这里所说的数据依赖性仅针对单个处理器中执行的指令序列和单个线程中执行的操作,不同处理器之间和不同线程之间的数据依赖性不被编译器和处理器考虑

as-if-serial语义

  as-if-serial语义的意思是：不管怎么重排序(编译器和处理器为了提高并行度),(单线程)程序的执行结果不能被改变.编译器、runtime和处理器都必须遵守as-if-serial语义
  为了遵守as-if-serial语义,编译器和处理器不会对存在数据依赖关系的操作做重排序,因为这种重排序会改变执行结果.但是,如果操作之间不存在数据依赖关系,这些操作就可能被编译器和处理器重排序.为了具体说明,请看下面计算圆面积的代码示例

1
2
3

double pi = 3.14; // A
double r = 1.0; // B
double area = pi * r * r; // C

上面3个操作的数据依赖关系如下图所示：

1
2
3

graph LR
A-->C
B-->C

  如上图所示,A和C之间存在数据依赖关系,同时B和C之间也存在数据依赖关系.因此在最终执行的指令序列中,C不能被重排序到A和B的前面(C排到A和B的前面,程序的结果将会被改变).但A和B之间没有数据依赖关系,编译器和处理器可以重排序A和B之间的执行顺序
该程序的两种执行顺序:

1. 按程序顺序执行结果: area=3.14

   1 2 3

   graph LR A-->B B-->C

2. 重排序执行结果: area=3.14

   1 2 3

   graph LR B-->A A-->C

     as-if-serial语义把单线程程序保护了起来,遵守as-if-serial语义的编译器、runtime和处理器共同为编写单线程程序的程序员创建了一个幻觉：单线程程序是按程序的顺序来执行的.asif-serial语义使单线程程序员无需担心重排序会干扰他们,也无需担心内存可见性问题

   程序顺序规则

   根据happens-before的程序顺序规则,上面计算圆的面积的示例代码存在3个happensbefore关系:
3. A happens-before B
4. B happens-before C
5. A happens-before C

这里的第3个happens-before关系,是根据happens-before的传递性推导出来的
  这里A happens-before B,但实际执行时B却可以排在A之前执行(看上面的重排序后的执行顺序).如果A happens-before B,JMM并不要求A一定要在B之前执行.JMM仅仅要求前一个操作(执行的结果)对后一个操作可见,且前一个操作按顺序排在第二个操作之前.这里操作A的执行结果不需要对操作B可见;而且重排序操作A和操作B后的执行结果,与操作A和操作B按happens-before顺序执行的结果一致.在这种情况下,JMM会认为这种重排序并不非法(not illegal),JMM允许这种重排序

重排序对多线程的影响

现在让我们来看看,重排序是否会改变多线程程序的执行结果.请看下面的示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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
            ……
        }
    }
}

flag变量是个标记,用来标识变量a是否已被写入.这里假设有两个线程A和B,A首先执行writer()方法,随后B线程接着执行reader()方法.线程B在执行操作4时,能否看到线程A在操作1对共享变量a的写入呢?

答案是：不一定能看到

  由于操作1和操作2没有数据依赖关系,编译器和处理器可以对这两个操作重排序;同样,操作3和操作4没有数据依赖关系,编译器和处理器也可以对这两个操作重排序.让我们先来看看,当操作1和操作2重排序时,可能会产生什么效果?请看下面的程序执行时序图,如下图所示

操作1和操作2做了重排序.程序执行时,线程A首先写标记变量flag,随后线程B读这个变量.由于条件判断为真,线程B将读取变量a.此时,变量a还没有被线程A写入,在这里多线程程序的语义被重排序破坏了
  下面再让我们看看,当操作3和操作4重排序时会产生什么效果(借助这个重排序,可以顺便说明控制依赖性).下面是操作3和操作4重排序后,程序执行的时序图

  在程序中,操作3和操作4存在控制依赖关系.当代码中存在控制依赖性时,会影响指令序列执行的并行度.为此,编译器和处理器会采用猜测(Speculation)执行来克服控制相关性对并行度的影响.以处理器的猜测执行为例,执行线程B的处理器可以提前读取并计算a*a,然后把计算结果临时保存到一个名为重排序缓冲(Reorder Buffer，ROB)的硬件缓存中.当操作3的条件判断为真时,就把该计算结果写入变量i中
  从上图可以看出,猜测执行实质上对操作3和4做了重排序.重排序在这里破坏了多线程程序的语义

  在单线程程序中,对存在控制依赖的操作重排序,不会改变执行结果(这也是as-if-serial语义允许对存在控制依赖的操作做重排序的原因);但在多线程程序中,对存在控制依赖的操作重排序,可能会改变程序的执行结果

顺序一致性

顺序一致性内存模型是一个理论参考模型,在设计的时候,处理器的内存模型和编程语言的内存模型都会以顺序一致性内存模型作为参照

数据竞争与顺序一致性

当程序未正确同步时,就可能会存在数据竞争.Java内存模型规范对数据竞争的定义如下:

1. 在一个线程中写一个变量
2. 在另一个线程读同一个变量
3. 而且写和读没有通过同步来排序

当代码中包含数据竞争时,程序的执行往往产生违反直觉的结果(前面的示例正是如
此).如果一个多线程程序能正确同步,这个程序将是一个没有数据竞争的程序

JMM对正确同步的多线程程序的内存一致性做了如下保证：
  如果程序是正确同步的,程序的执行将具有顺序一致性(Sequentially Consistent)——即程序的执行结果与该程序在顺序一致性内存模型中的执行结果相同.马上我们就会看到,这对于程序员来说是一个极强的保证.这里的同步是指广义上的同步,包括对常用同步原语(synchronized、volatile和final)的正确使用

顺序一致性内存模型

顺序一致性内存模型是一个被计算机科学家理想化了的理论参考模型,它为程序员提供了极强的内存可见性保证.顺序一致性内存模型有两大特性：

1. 一个线程中的所有操作必须按照程序的顺序来执行
2. (不管程序是否同步)所有线程都只能看到一个单一的操作执行顺序.在顺序一致性内存模型中,每个操作都必须原子执行且立刻对所有线程可见

顺序一致性内存模型为程序员提供的视图如下：

  在概念上,顺序一致性模型有一个单一的全局内存,这个内存通过一个左右摆动的开关可以连接到任意一个线程,同时每一个线程必须按照程序的顺序来执行内存读/写操作.从上面的示意图可以看出,在任意时间点最多只能有一个线程可以连接到内存.当多个线程并发执行时,图中的开关装置能把所有线程的所有内存读/写操作串行化(即在顺序一致性模型中,所有操作之间具有全序关系)

为了更好进行理解,下面通过两个示意图来对顺序一致性模型的特性做进一步的说明：
  假设有两个线程A和B并发执行.其中A线程有3个操作,它们在程序中的顺序是：A1→A2→A3.B线程也有3个操作,它们在程序中的顺序是：B1→B2→B3
  假设这两个线程使用监视器锁来正确同步：A线程的3个操作执行后释放监视器锁,随后B线程获取同一个监视器锁.那么程序在顺序一致性模型中的执行效果将如下图所示：

现在我们再假设这两个线程没有做同步,下面是这个未同步程序在顺序一致性模型中的执行示意图：

  未同步程序在顺序一致性模型中虽然整体执行顺序是无序的,但所有线程都只能看到一个一致的整体执行顺序.以上图为例,线程A和B看到的执行顺序都是：B1→A1→A2→B2→A3→B3.之所以能得到这个保证是因为顺序一致性内存模型中的每个操作必须立即对任意线程可见
  但是,在JMM中就没有这个保证.未同步程序在JMM中不但整体的执行顺序是无序的,而且所有线程看到的操作执行顺序也可能不一致.比如,在当前线程把写过的数据缓存在本地内存中,在没有刷新到主内存之前,这个写操作仅对当前线程可见;从其他线程的角度来观察,会认为这个写操作根本没有被当前线程执行.只有当前线程把本地内存中写过的数据刷新到主内存之后,这个写操作才能对其他线程可见.在这种情况下,当前线程和其他线程看到的操作执行顺序将不一致

同步程序的顺序一致性效果

下面对前面的示例程序ReorderExample用锁来同步,看看正确同步的程序如何具有顺序一致性：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class SynchronizedExample {
    int a = 0;
    boolean flag = false;
    
    public synchronized void writer() { // 获取锁
        a = 1;
        flag = true;
    } // 释放锁
    
    public synchronized void reader() { // 获取锁
        if (flag) {
            int i = a;
            ……
        } // 释放锁
    }
}

  在上面示例代码中,假设A线程执行writer()方法后,B线程执行reader()方法.这是一个正确同步的多线程程序.根据JMM规范,该程序的执行结果将与该程序在顺序一致性模型中的执行结果相同.下面是该程序在两个内存模型中的执行时序对比图,如下图所示
  顺序一致性模型中,所有操作完全按程序的顺序串行执行.而在JMM中,临界区内的代码可以重排序(但JMM不允许临界区内的代码”逸出”到临界区之外,那样会破坏监视器的语义).JMM会在退出临界区和进入临界区这两个关键时间点做一些特别处理,使得线程在这两个时间点具有与顺序一致性模型相同的内存视图(具体细节后文会说明).虽然线程A在临界区内做了重排序,但由于监视器互斥执行的特性,这里的线程B根本无法”观察”到线程A在临界区内的重排序.这种重排序既提高了执行效率,又没有改变程序的执行结果

从这里我们可以看到,JMM在具体实现上的基本方针为：在不改变(正确同步的)程序执行结果的前提下,尽可能地为编译器和处理器的优化打开方便之门

未同步程序的执行特性

  对于未同步或未正确同步的多线程程序,JMM只提供最小安全性：线程执行时读取到的值,要么是之前某个线程写入的值,要么是默认值(0，Null，False),JMM保证线程读操作读取到的值不会无中生有(Out Of Thin Air)的冒出来.为了实现最小安全性,JVM在堆上分配对象时,首先会对内存空间进行清零,然后才会在上面分配对象(JVM内部会同步这两个操作).因此,在已清零的内存空间(Pre-zeroed Memory)分配对象时,域的默认初始化已经完成了
  JMM不保证未同步程序的执行结果与该程序在顺序一致性模型中的执行结果一致.因为如果想要保证执行结果一致,JMM需要禁止大量的处理器和编译器的优化,这对程序的执行性能会产生很大的影响.而且未同步程序在顺序一致性模型中执行时,整体是无序的,其执行结果往往无法预知.而且,保证未同步程序在这两个模型中的执行结果一致没什么意义

未同步程序在JMM中的执行时,整体上是无序的,其执行结果无法预知.未同步程序在两个模型中的执行特性有如下几个差异:

1. 顺序一致性模型保证单线程内的操作会按程序的顺序执行,而JMM不保证单线程内的操作会按程序的顺序执行(比如上面正确同步的多线程程序在临界区内的重排序)
2. 顺序一致性模型保证所有线程只能看到一致的操作执行顺序,而JMM不保证所有线程能看到一致的操作执行顺序
3. JMM不保证对64位的long型和double型变量的写操作具有原子性,而顺序一致性模型保证对所有的内存读/写操作都具有原子性