每日一句

书中横卧着整个过去的灵魂 —— 卡莱尔

指令重排补充

数据依赖性

如果两个操作访问同一个变量，且这两个操作中有一个为写操作，此时这两个操作之间就存在数据依赖性。数据依赖分下列三种类型：

上面三种情况，重排序两个操作的执行顺序，程序的执行结果将会被改变。前面提到过，编译器和处理器可能会对操作做重排序。编译器和处理器在重排序时，会遵守数据依赖性，编译器和处理器不会改变存在数据依赖关系的两个操作的执行顺序。

注意，这里所说的数据依赖性仅针对单个处理器中执行的指令序列和单个线程中执行的操作，不同处理器之间和不同线程之间的数据依赖性不被编译器和处理器考虑。

总结: 为了提高程序的并发度，从而提高性能！但是对于多线程程序，重排序可能会导致程序执行的结果不是我们需要的结果！因此，在多线程环境下就需要我们通过“volatile，synchronize，锁等方式”作出正确的实现同步，因为单线程遵循 as-if-serial 语义。

as-if-serial 语义

所有的动作都可以为了优化而被重排序，但是必须保证它们重排序后的结果和程序代码本身的应有结果是一致的。Java 编译器、运行时和处理器都会保证 Java 在单线程下遵循 as-if-serial 语义。

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

public class Reordering {    public static void main(String[] args) {        int x, y;        x = 1;        try {            x = 2;            y = 0 / 0;            } catch (Exception e) {        } finally {            System.out.println("x = " + x);        }    }}

答案是 2

原因：为保证 as-if-serial 语义，Java 异常处理机制也会为重排序做一些特殊处理。

例如在下面的代码中，y = 0 / 0 可能会被重排序在 x = 2 之前执行，为了保证最终不致于输出 x = 1 的错误结果，JIT 在重排序时会在 catch 语句中插入错误代偿代码，将 x 赋值为 2，将程序恢复到发生异常时应有的状态。

这种做法的确将异常捕捉的逻辑变得复杂了，但是 JIT 的优化的原则是，尽力优化正常运行下的代码逻辑，哪怕以 catch 块逻辑变得复杂为代价，毕竟，进入 catch 块内是一种“异常”情况的表现。

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

happens-before 规则

JDK5 开始，JSR-133 提出了 happens-before 的概念，通过这个概念来阐述操作之间的内存可见性。如果操作执行的结果需要对另一个操作可见，那么这两个操作之间必须存在 happens-before 关系。这里提到的两个操作既可以是在一个线程之内，也可以是在不同线程之间。

两个操作之间具有 happens-before 关系，并不意味着前一个操作必须要在后一个操作之前执行！happens-before 仅仅要求前一个操作（执行的结果）对后一个操作可见。

happens-before 语法现象

• 对象加锁：对一个监视器锁的解锁，happens-before 于随后对这个监视器锁的加锁。

• volatile 变量：对一个 volatile 域的写，happens-before 于任意后续对这个 volatile 域的读。

在 java 语言中大概有 8 大 happens-before 原则，分别如下：

程序次序规则(Pragram Order Rule)：在一个线程内，按照程序代码顺序，书写在前面的操作先行发生于书写在后面的操作。准确地说应该是控制流顺序而不是程序代码顺序，因为要考虑分支、循环结构。

代码在单线程中执行的结果是有序的。注意是执行结果，因为虚拟机、处理器会对指令进行重排序。虽然重排序了，但是并不会影响程序的执行结果，所以程序最终执行的结果与顺序执行的结果是一致的。

故而这个规则只对单线程有效，在多线程环境下无法保证正确性。

int a = 3; //1int b = a + 3; //2

这里的对 b 的赋值操作会用到变量 a，那么 java 的“单线程 happen-before 原则”就保证 ② 的中的 a 的值一定是 3，因为 ① 书写在②前面, ① 对变量 a 的赋值操作对 ② 一定可见。因为 ② 中有用到 ① 中的变量 a，再加上 java 内存模型提供了“单线程 happen-before 原则”，所以 java 虚拟机不许可操作系统对 ① ② 操作进行指令重排序，即不可能有 ② 在 ① 之前发生，但是对于下面的代码：

int a = 3;int b = 4;

两个语句直接没有依赖关系，所以指令重排序可能发生，即对 b 的赋值可能先于对 a 的赋值。

监视器规则(Monitor Lock Rule)：对某个锁的 unlock 操作先行发生于后面对同一个锁的 lock 操作。这里必须强调的是同一个锁，这里的“后面”是指时间上的先后顺序。也就是说，如果某个锁已经被 lock 了，那么只有它被 unlock 之后，其他线程才能 lock 该锁。表现在代码上，如果是某个同步方法，如果某个线程已经进入了该同步方法，只有当这个线程退出了该同步方法(unlock 操作)，别的线程才可以进入该同步方法。

volatile 变量规则(Volatile Variable Rule)：volatile 变量的写操作先行发生于对这个变量的读操作，这里的“后面”同样是指时间上的先后顺序。也就是说，某个线程对 volatile 变量写入某个值后，能立即被其它线程读取到。

线程启动规则(Thread Start Rule) ：Thread 对象的 start()方法先行发生于此线程的每一个动作。

线程终于规则(Thread Termination Rule) ：线程中的所有操作都先行发生于对此线程的终止检测，我们可以通过 Thread.join()方法结束，Thread.isAlive()的返回值等作段检测到线程已经终止执行。

线程中断规则(Thread Interruption Rule) ：对线程 interrupt()方法的调用先行发生于被中断线程的代码检测到中断事件的发生，可以通过 Thread.interrupted()方法检测是否有中断发生。

对象终结规则(Finalizer Rule)：一个对象初始化完成(构造方法执行完成)先行发生于它的 finalize()方法的开始。

传递性(Transitivity)：如果操作 A 先行发生于操作 B，操作 B 先行发生于操作 C，那就可以得出操作 A 先行发生于操作 C 的结论。

程序次序：不满足，remove(i)与 get(i)在控制流顺序没有先行发生关系；

管程锁定：不满足，remove(i)与 get(i)方法都是 synchronized 修饰，但各自持有不同的锁，不满足管程锁定要求的同一个锁；

volatile 变量：不满足，没有 volatile 修饰变量，无视；

线程启动：不满足，removeThread.start()先与 vector.remove(i)，getThread.start()先于 vector.get(i)，但后两者明显没有关系

线程终止：不满足；线程中断：不满足；

对象终结：不满足，不存在对象终结的关系

传递性：

不满足，加入 size()验证作为参考，假定 A 是 remove()，B 是 size()验证，C 是 get()，B 先于 C，但 A 可能介乎于 BC 之间，也可能在 B 之前。因此不符合传递性。

结论：vector 作为相对线程安全对象，其单个方法带 synchronized 修饰，是相对线程安全的，但 Vector 方法之间不是线程安全的，不能保证多个方法作用下的数据一致性。执行例子 get()会报错：java.lang.ArrayIndexOutOfBoundsException。

时间上的先后顺序”与“先行发生”之间有什么不同：

private int value=0；public void setValue（int value）{    this.value=value；} public int getValue（）{    return value；}

以上显示的是一组再普通不过的 getter/setter 方法，假设存在线程 A 和 B，线程 A 先（时间上的先后）调用了“setValue（1）”，然后线程 B 调用了同一个对象的“getValue（）”，那么线程 B 收到的返回值是什么？

我们依次分析一下先行发生原则中的各项规则，由于两个方法分别由线程 A 和线程 B 调用，不在一个线程中，所以程序次序规则在这里不适用；

由于没有同步块，自然就不会发生 lock 和 unlock 操作，所以管程锁定规则不适用；由于 value 变量没有被 volatile 关键字修饰，所以 volatile 变量规则不适用；

后面的线程启动、 终止、 中断规则和对象终结规则也和这里完全没有关系。 因为没有一个适用的先行发生规则，所以最后一条传递性也无从谈起，因此我们可以判定尽管线程 A 在操作时间上先于线程 B，但是无法确定线程 B 中“getValue（）”方法的返回结果，换句话说，这里面的操作不是线程安全的。

那怎么修复这个问题呢？我们至少有两种比较简单的方案可以选择：要么把 getter/setter 方法都定义为 synchronized 方法，这样就可以套用管程锁定规则；要么把 value 定义为 volatile 变量，由于 setter 方法对 value 的修改不依赖 value 的原值，满足 volatile 关键字使用场景，这样就可以套用 volatile 变量规则来实现先行发生关系。

通过上面的例子，我们可以得出结论：一个操作“时间上的先发生”不代表这个操作会是“先行发生”，那如果一个操作“先行发生”是否就能推导出这个操作必定是“时间上的先发生”呢？很遗憾，这个推论也是不成立的，一个典型的例子就是多次提到的“指令重排序”，演示例子如下代码所示：

//以下操作在同一个线程中执行int i=1；int j=2；

以上代码的两条赋值语句在同一个线程之中，根据程序次序规则，“int i=1”的操作先行发生于“int j=2”，但是“int j=2”的代码完全可能先被处理器执行，这并不影响先行发生原则的正确性，因为我们在这条线程之中没有办法感知到这点。上面两个例子综合起来证明了一个结论：时间先后顺序与先行发生原则之间基本没有太大的关系，所以我们衡量并发安全问题的时候不要受到时间顺序的干扰，一切必须以先行发生原则为准。

内存屏障

处理器都支持一定的内存屏障(memory barrier)或栅栏(fence)来控制重排序和数据在不同的处理器间的可见性。

将 CPU 和内存间的数据存取操作分为 load 和 store。例如，CPU 将数据写回时，会将 store 请求放入 write buffer 中等待 flush 到内存，可以通过插入 barrier 的方式防止这个 store 请求与其他的请求重排序、保证数据的可见性。

可以用一个生活中的例子类比屏障，例如坐地铁的斜坡式电梯时，大家按顺序进入电梯，但是会有一些人从左侧绕过去，这样出电梯时顺序就不相同了，如果有一个人携带了一个大的行李堵住了（屏障），则后面的人就不能绕过去了。

另外这里的 barrier 和 GC 中用到的 write barrier 是不同的概念。

下面是常见处理器允许的重排序类型的列表上面我们说了处理器会发生指令重排,现在来简单的看看常见处理器允许的重排规则,换言之就是处理器可以对那些指令进行顺序调整:

上表单元格中的 “N” 表示处理器不允许两个操作重排序，“Y” 表示允许重排序。从上表我们可以看出：常见的处理器都允许 Store-Load 重排序；常见的处理器都不允许对存在数据依赖的操作做重排序。 x86 拥有相对较强的处理器内存模型，它们仅允许对写-读操作做重排序（因为它们都使用了写缓冲区）。※注 1：上表中的 x86 包括 x64 及 AMD64。=※注 2：由于 ARM 处理器的内存模型与 PowerPC 处理器的内存模型非常类似，本文将忽略它。※注 3：数据依赖性后文会专门说明。

先简单了解两个指令

Store：将处理器缓存的数据刷新到内存中。

Load：将内存存储的数据拷贝到处理器的缓存中。

表格中 Y 表示前后两个操作允许重排,N 则表示不允许重排.与这些规则对应是的禁止重排的内存屏障。

注意：处理器和编译都会遵循数据依赖性,不会改变存在数据依赖关系的两个操作的顺序.所谓的数据依赖性就是如果两个操作访问同一个变量,且这两个操作中有一个是写操作,那么久可以称这两个操作存在数据依赖性.举个简单例子:

a=100;//writeb=a;//read
或者a=100;//writea=2000;//write或者a=b;//readb=12;//write

以上所示的,两个操作之间不能发生重排,这是处理器和编译所必须遵循的.当然这里指的是发生在单个处理器或单个线程中.

内存屏障的分类

几乎所有的处理器都支持一定粗粒度的 barrier 指令，通常叫做 Fence(栅栏、围墙)，能够保证在 fence 之前发起的 load 和 store 指令都能严格的和 fence 之后的 load 和 store 保持有序。通常按照用途会分为下面四种 barrier

StoreLoad Barriers 同时具备其他三个屏障的效果，因此也称之为全能屏障（mfence），是目前大多数处理器所支持的；但是相对其他屏障，该屏障的开销相对昂贵。

内存屏障对性能的影响（Performance Impact of Memory Barriers）

内存屏障阻止了 CPU 执行很多隐藏内存延迟的技术，因此有它们有显著的性能开销，必须考虑。为了达到最大性能，最好对问题建模，这样处理器可以做工作单元，然后让所有必须的内存屏障在工作单元的边界上发生。采用这种方法允许处理器不受限制地优化工作单元。把必须的内存屏障分组是有益的，那样，在第一个之后的 buffer 刷新的开销会小点，因为没有工作需要进行重新填充它。

总结: 通过内存屏障可以禁止特定类型处理器的重排序，从而让程序按我们预想的流程去执行。