高并发编程-重排序

定义

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

---

数据依赖性

如果两个操作访问同一个变量，且这两个操作中有一个为写操作，此时这两个操作之间就存在数据依赖性.

名称	代码	说明
写后读	a=1;b=a;	写一个变量后，再读这个位置
写后写	a=1;a=2	写一个变量后，再写这个变量
读后写	a=b;b=1;	读一个变量后，再写这个变量

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

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

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

---

as-if-serial语义

as-if-serial语义的意思是：不管怎么重排序（编译器和处理器为了提高并行度），（单线程）程序的执行结果不能被改变。

编译器、runtime和处理器都必须遵守as-if-serial语义。

为了遵守as-if-serial语义，编译器和处理器不会对存在数据依赖关系的操作做重排序，因为这种重排序会改变执行结果。

但是，如果操作之间不存在数据依赖关系，这些操作就可能被编译器和处理器重排序。

举个例子 ： 计算圆面积

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

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

A和C之间存在数据依赖关系，同时B和C之间也存在数据依赖关系。因此最终执行的指令序列中，C不能被重排序到A和B的前面（C排到A和B的前面，程序的结果将会被改变）。

但A和B之间没有数据依赖关系，编译器和处理器可以重排序A和B之间的执行顺序。

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

---

程序顺序规则

根据happens-before的程序顺序规则，上面计算圆的面积的示例代码存在3个happens-before关系。

1）A　happens-before B。
2）B　happens-before C。
3）A　happens-before C。

这里的第3个happens-before关系，是根据happens-before的传递性推导出来的。

---

重排序对多线程的影响

我们来看看，重排序是否会改变多线程程序的执行结果。 请看下面的示例代码

public class AsIfSerial {

    private int a = 0;
    private boolean flag = false;

    public void wirte() {
        a = 1;    //  操作1
        flag = true;//  操作2
        System.out.println(Thread.currentThread().getName() + " 更新后 a=" + a + " , flag=" + flag);

    }


    public void read() {
        System.out.println(Thread.currentThread().getName() + "  读取值 a=" + a + " , flag=" + flag);
        if (flag) {  //  操作3 
            int i = a * a; //  操作4
            System.out.println(Thread.currentThread().getName() + "  执行结果:" + i);
        }
    }
   }

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语义允许对存在控制依赖的操作做重排序的原因）；但在多线程程序中，对存在控制依赖的操作重排序，可能会改变程序的执行结果。

咋改呢 ？ 加 volatile

package com.artisan.test;


public class AsIfSerial {

    // 共享变量： 实例域 （同一个对象的）
    private volatile int a = 0;
    // 共享变量： 实例域（同一个对象的）
    private volatile boolean flag = false;

    public void wirte() {
        a = 1;
        flag = true;
        System.out.println(Thread.currentThread().getName() + " 更新后 a=" + a + " , flag=" + flag);

    }


    public void read() {
        System.out.println(Thread.currentThread().getName() + "  读取值 a=" + a + " , flag=" + flag);
        if (flag) {
            int i = a * a;
            System.out.println(Thread.currentThread().getName() + "  执行结果:" + i);
        }
    }

    public static void main(String[] args) throws InterruptedException {

        // 实例化出来一个对象
        AsIfSerial asIfSerial = new AsIfSerial();

        new Thread(() -> {
            asIfSerial.wirte();
        }, "WRITE").start();

        // sleep一下 确保 WRITE线程先启动
        Thread.sleep(500);

        new Thread(() -> {
            asIfSerial.read();
        }, "READ").start();

    }

}

---