并发学习笔记05-重排序

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

在计算机中，软件技术和硬件技术有一个共同的目标：在不改变程序执行结果的前提下，尽可能提高并行度。

数据依赖

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

这3种情况只要重排序执行顺序，程序的执行结果就会改变。

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

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

as-if-serial语义

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

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

为此，编译器和处理器不会对存在数据依赖关系的操作进行重排序。

单线程程序中，对存在控制依赖的操作重排序，不会改变执行结果（即as-if-serial语义允许对存在控制依赖的操作做重排序操作的原因）。但是在多线程中，对存在控制依赖的操作重排序可能会改变程序的执行结果。

如果两个操作访问同一变量, 且有一个是写操作, 则这两个操作存在数据依赖性.

前序操作是条件语句(if, while…), 则后续操作和前序之间就产生了控制依赖关系.

例：

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做了重排序。重排序在这里破坏了多线程程序的语义。