17.5 重排样例

列表 17-4 展示了一个内存重排给我们带来麻烦的场景。两个线程交错执行其线程上运行的代码。

Listing 17-4.mem_reorder_sample.c

int x = 0;
int y = 0;

void thread1(void) {
    x = 1;
    print(y);
}

void thread2(void) {
    y = 1;
    print(x);
}

两个线程间共享变量 x 和变量 y。其中一个线程向 x 写一个值然后读取 y 。另一个线程执行差不多的动作，不过把 x 和 y 的操作顺序互换。

我们主要关注 load 和 store 这两种内存访问方法。例子里的代码为了简略，把其它的行为都省略掉了。

由于这些指令是完全独立的(分别操作的是不同的数据)，所以每个线程内的操作在线程内都是可以在不影响可观察行为的前提下，进行重排序的，这样就给了我们四种组合：store + load 或 load + store 两两组合。编译器可以按自己的想法进行组合。每一种组合方式下都可能会有六种可能的执行顺序。这些执行顺序表示了线程彼此之间是如何向前执行的。

下面我们以 1 和 2 来表示两个线程的执行情况，如果第一个线程执行了一步，那就写 1，否则就写 2 表示第二个线程执行了一条指令。

1.1-1-2-2

2.1-2-1-2

3.2-1-1-2

4.2-1-2-1

5.2-2-1-1

6.1-2-2-1

例如，1-1-2-2 表示第一个线程执行了两步操作，然后第二个线程执行两步。每一个序列都会对应四种不同的场景。例如，序列 1-2-1-2 实际的流程可能有几种流程，见表 17-1:

Table 17-1.Possible Instruction Execution Sequences If Processes Take Turns as 1-2-1-2

如果我们反复观察每次执行顺序的可能结果，总共会有 24 种情况(有一些情况结果等价)。如你所见，即使是这么小的一个例子，就已经有这么多种可能的情况了。

不过我们也不需要关心所有可能的执行顺序；我们只要关心每一个变量 load 和 store 的相对顺序即可。在表 17-1 中出现的多种情况中，一个值的 load 结果只取决于之前是否有过 store 操作。

如果没有重排这回事的话，可能的情况就很有限了：两个 load 指令之前一定会有一个 store，因为我们的源代码就是这么写的；即使是换一种调度指令也依然不能改变这种事实。不过由于重排始终存在，有时候我们还是会得到一些有趣的结果，如果两个线程的指令都被重排了的话，我们会遇到类似列表 17-5 的场景。

Listing 17-5.mem_reorder_sample_happened.c

int x = 0;
int y = 0;

void thread1(void) {
    print(y);
    x = 1;
}

void thread2(void) {
    print(x);
    y = 1;
}

如果重排策略是 1-2-*-*(* 表示两个线程随意)，那么相当于先执行 load x 和 load y，这样就都会打印 0 了。

编译器把这些操作重排是完全有可能的。不过即使我们将重排控制的很好，或者完全关闭重排，CPU 层面也还是可能会发生同样形式的重排。

这个例子演示了这种程序的极度不可预测性。之后我们会研究怎么限制编译器和 CPU 进行这种重排；同时会提供一个演示硬件层面重排的例子。