弱内存模型的 CPU 乱序问题检测方法

发表于

摘要： 简述弱内存模型的 CPU 乱序问题背景以及探讨一种适合生产环境中使用的检测方法

转载或者引用本文内容请注明来源及原作者

有些 cpu 为了提高性能，引入了一些优化手段，导致指令实际执行的 “效果” 可能与程序顺序不同，具有这种内存模型的 cpu 通常被称为 ”弱内存模型“。同时，还有另外一些原因可能导致指令乱序的效果：

  • 编译器对指令做重排序
  • cache 一致性优化引入的乱序（可参考 ibm 的文章，看一下 store buffer 和 invalid queue 怎么影响指令执行顺序）
  • 指令多发射，有的流水线的指令由于没有阻塞而先执行，有的被阻塞了后执行从而导致顺序变化

指令乱序的最小约束条件

看起来比较反直觉，毕竟大多数同学写程序时都不会考虑乱序问题，为什么从不出错？

有几点原因，一个是对单线程来说，即便乱序发生了也不会影响程序的执行结果，另一个是在多线程程序中，对临界区加锁和解锁本身就自带了内存屏障语义，所以也不会出错。一般在多线程下写无锁算法时才需要考虑乱序，这个一会分析。

所以首先回答一个关键问题，乱序的边界在哪里？是所有指令都能乱序，还是有一定的约束？

事实上，为了保证程序的正确性，不管是编译器的指令重排序还是 cpu 指令执行乱序或者是 cache 一致性优化引入的乱序，指令的可见性顺序必须满足单线程语义下的正确性。换句话说，在指令执行的每个时间点上对内存的可见性顺序必须和程序顺序保持一致。

例如以下程序：

1
2
3
a = 1;
b = 2;
c = a;

这里 c = a 必须保证此时能看到 a 对应的内存值为 1，这是符合程序顺序的，否则程序结果就错了，所以以上程序不可能执行成这样：

1
2
3
c = a;
a = 1;
b = 2;

而其余保证可见性顺序和程序顺序一致的乱序理论上都是有可能发生的（取决于具体的 cpu 内存模型，但也只可能是子集。这里仅讨论理想情况，如果检测方法能解决理想情况下的乱序问题，那么子集自然不是问题）。

这里用可见性顺序而不是执行顺序去描述，是因为指令的执行过程实际分很多步骤，包括取指、译码、执行、访存、写回等，可能存在有指令取指和译码先进行但等到执行和访存时需要等待其它指令结束的情况，用执行顺序分析会引入太多不必要的概念，徒增分析的复杂度，而内存可见性顺序则抽象了这个问题中最本质的需求。

多线程下的乱序问题

根据上述讨论可以知道，单线程情况下即便有乱序行为发生也不会影响程序的执行结果，所以无需担心。然而，在多线程下仅凭以上的约束就不足以保证程序的正确性了。比如以下程序：

1
2
3
4
5
6
T1:                 T2:
a = 123;
b = true;              
                    if (b == true) {
                        print(a);
                    }

按照程序顺序，print(a) 应该打印出 123，但实际执行结果并不一定。按照上一节的约束条件，T1 的执行顺序可能是：

1
2
b = true;
a = 123;

这并不影响 T1 对其访问的内存的可见性顺序，但问题是，这改变了 T2 对 a 和 b 的可见性顺序，即 print(a) 的时候，看到了 b 为 true，但还没有看到 a 的最新值 123，导致打印出的 a 是旧值。

所以，多线程下乱序会引起问题，本质上是因为不管是编译器还是 cpu，在处理指令时其本身并没有 “线程” 的概念，无法从多线程角度对指令的执行增加新的约束（cpu 做不到我认为是代价太大，也没必要。编译器有一些方案会考虑并自动加内存屏障）。

解决乱序问题

既然编译器和 cpu 都没有线程概念，那需要的 “约束” 条件就要求程序员手工来加了，这就引入了 “内存屏障” （memory barrier）。对上面的程序来说，如果把读写 b 作为同步 a 的手段，想要保证内存可见性顺序须保证两件事：

  1. 从 T1 的角度来看，当 b = true 对外部可见时，a = 123 也必须对外部可见，这个约束叫做 release 语义（通常实现为 write barrier）
  2. 从 T2 的角度来看，当 b = true 可见时，如果 T1 的 b = true 具有 release 语义，那么 happens before b = true 的所有指令的结果对 T2 也必须可见，这种叫做 acquire 语义（通常实现为 read barrier）

加上内存屏障后的代码就一定能保证 print(a) 输出为 123：

1
2
3
4
5
6
7
8
T1:                 T2:
a = 123;
write_barrier();
b = true;              
                    if (b == true) {
                        read_barrier();
                        print(a);
                    }

如果使用 C++11，内存屏障语义会加在 atomic 操作上，使用时注意即可，本质上都是一样的。

如何检测乱序问题

假设给一个大型软件，里面就存在这种乱序问题，如何找出哪里存在问题？

前面几个小节都是背景铺垫，这里才是我想讨论和解决的问题。

TODO