Yinjun Zhu's Blog
首页 归档 标签 分类
Yinjun Zhu's Blog

目录

内存一致性模型（一）

 收录于 编程语言
 Created on   约 3517 字   预计阅读 8 分钟 

问题起源

在多核处理器上进行多线程并行编程，所有程序员都需要面对的一个问题是 how threads see things in order，即内存单元上发生的变化是按什么样的顺序被其它相关线程给观察到的。由此引申出内存一致性模型（memory consistency models），简称内存模型。

内存模型用来定义多个并行线程如何观察他们的共享内存的状态。它是硬件系统和软件开发之间的某种约定，硬件许诺只有某些顺序的执行是可能发生的，软件开发过程中只要按照约定的规则去写程序，那么相关的内存结果就是一致的、可预测的。

内存模型对于多核上的并行编程之所以重要，是因为在多核处理上开发的程序，实际运行的方式，和代码展示的、或者说程序员直觉上的感知，是不同的，甚至是反直觉的。深层次的原因在于，现代 CPU 架构上采用的多层 cache、流水线、多发射、乱序执行、分支预测等优化技术，使得实际执行的机器指令，和原先的程序，不存在顺序对应关系。

对内存模型有较好的了解和运用，不仅可以使多线程程序更安全更健壮，而且可以大大提高程序的运行效率。以至于说内存一致性模型是： “The cause of, and solution to, all your multicore performance problems.”

 

分类

内存一致性模型，按大类来分，有以下几类：

  • 强一致性模型，包括：严格一致性、顺序一致性（sequential consistency）、因果一致性、处理器一致性、缓存一致性等。
  • 弱一致性模型，包括：弱序一致性、发布一致性、本地一致性等。
  • 介于强和弱之间的宽松一致性模型，包括：total store ordering, partial store ordering 等。

本系列文章将选取一些最常见的模型做介绍。

 

先看一个例子

前面说了，内存模型是多个线程如何观察内存世界的。先来看一个简单的例子，假设 a 和 b 是两个共享变量，初始化为 0，thread 1 和 thread 2 分别执行下面两段代码：

1
2
3

// thread 1
a = 1;		// (1)
print(b)	// (2)

1
2
3

// thread 2
b = 1		// (3)
print(a)	// (4)

为了描述代码的执行顺序，在注释部分添加了数字。

我们可以先看看可能的执行顺序。显然，有两种顺序是完全可能发生的：

  • 1 -> 2 -> 3 -> 4：即 thread 1 先执行，完了之后 thread 2 再执行。这种情况下，变量 a 的修改，对于其它线程（thread 2）是可观察到的，或者说可见的，所以打印结果是 a = 1, b = 0;
  • 3 -> 4 -> 1 -> 2：同上，thread 2 先执行，再执行 thread 1，结果是 a = 0, b = 1。

还可能有其它结果吗？大部分童鞋，可能已经猜到了：

  • 1 -> 3 -> 2 -> 4：thread 1 先执行语句 1，然后另一个线程在语句 2 执行前，抢先执行，这种情况下，结果是 a = 1, b = 1;
  • 1 -> 3 -> 4 -> 2：和上面一样，结果是 a = 1, b = 1;
  • 其它类似的顺序：结果都是 a = 1, b = 1;

 

直觉感知

上面的例子，有没有可能结果是 a = 0, b = 0 ？直觉上，我们觉得不可能。但是正如文章开头说的，很多时候，实际结果和直觉感知是不同的，稍后我会讲。我们先来看看为什么直觉上结果不可能是 a = 0, b = 0。

如果结果中 b = 0，那么（2）一定在（3）之前执行（happen before）。而（1）在（2）之前执行，（4）在（3）之后执行，所以推导出（1）一定在（4）之前执行。这种情况下，（1）已经将 a 设为 1 了，所以输出中 a 不可能为 0。

同理，如果结果中 a = 0，那么（4）一定在（1）之前执行，可以推导出（3）一定在（2）之前执行，所以 b 不可能为 0。

所以，直觉上，输出结果中，a 和 b 不可能同时为 0。

 

顺序一致性模型

上述的例子告诉我们，在直觉感知上，这两个线程的执行结果，可能是以下任意一种：

  • a = 1，b = 0；
  • a = 0，b = 1；
  • a = 1，b = 1；

这种符合直觉感知的内存模型，其实就是顺序一致性（sequential consistency）模型。顺序一致性模型属于强一致性模型的一种。

硬件架构设计师和编程语言的设计者们相信，这种模型中的规则是符合程序员的直觉的。一方面，多个并行执行的线程要同时操作（读写）内存，它们的操作必须有先后顺序，不可能在“同一个时间点”操作；另一方面，直觉上，这些操作的执行顺序是按照程序代码展示的顺序（program order）发生的，即操作的执行顺序和我们看到的代码的顺序是一致的。两个规则构成了顺序一致性的本质。

需要注意的是，顺序一致性并没有告诉我们哪个线程或者哪个语句先执行，它只是告诉我们指令是按某种顺序在执行。

通过顺序一致性的定义，我们可以说，上述的代码在顺序一致性模型下，输出结果不可能是 a = 0, b = 0。

文章开头说过，内存一致性模型是硬件系统和软件开发之间的某种约定，对于顺序一致性模型，这个约定就好比是：

  • 硬件架构师承诺：“我设计的架构，会通过优化技术乱序执行指令，但我保证对于内存操作，它的发生顺序一定是和你在代码中定义的顺序一致的。“
  • 软件开发工程师：”好的，我按照这个约定设计我的代码。”

 

当有多个连续的写操作时，顺序一致性还保证了连贯性，即：其它线程看到的写操作的顺序，和实际写操作发生的顺序，是一致的。它并不是指定写发生的顺序，而是说每个线程看到的顺序结果是相同的。

 

顺序一致性模型下，最大的问题就是执行效率慢。所有内存操作指令，必须线性执行，同一时刻只能执行一个内存操作指令。更糟糕的是，我们必须等待当前内存操作指令执行完，才能继续执行下一条指令，在当前指令的结果对所有其它线程可见之前，无法执行任何其它指令。

 

宽松模型

顺序一致性模型中，保证指令执行顺序和代码一致，然而在大部分程序中，其实这往往是不必要的。回到前面的例子中，对于 thread 1，它的两个语句分别是（1）写入变量 a 和（2）打印变量 b。没有任何理由说，（2）必须等（1）完成后才执行。它们属于对两个不同变量的操作，不会相互干扰，所以完全可以并行执行。

在顺序一致性模型下，（2）必须在（1）完成后才执行，这个代价是很大的。因为（1）是一个写入操作，现代 CPU 架构中，由于多层 cache 设计，写入操作相当昂贵。CPU 需要将变量 a 写入多核共享的 L3 cache，这个操作要花费 90 个指令周期。

宽松模型在强一致性模型和弱一致性模型之间，通过打破一些强一致性模型中的规则，换取执行性能的大幅改善。

Total store ordering 模型

与其我们等待（1）的执行结果完全可见，不如先将它存放在 core 的 store buffer 中。于是，前面的例子，执行时变成了这样：

/2020/memory_model_1/1.png

这样，语句（2）可以在 a 存放到 store buffer 之后，就立即执行，无需等到写入到 L3 cache 后才执行。由于 store buffer 是 on-core 的，它的访问速度比 L1 cache 还快。在未来的某个时刻，多层 cache 的架构会将写入 store buffer 中的变量同步到其它 cache 中，使得所有线程都可以观察到它的变化。这种利用 store buffer 的机制，帮助我们实现了延迟隐藏（latency hide），即写入操作和其他操作并行，从而感受不到写入操作的延迟。

store buffer 的优点在于提高执行效率的同时，保留了单线程的行为。比如，考虑下面这个单线程代码：

1
2

a = 1
print(a)

打印语句需要知道 a 的最新值，但此时 a 还没有被写入内存，它的新值 1 被存放在 store buffer 中。如果打印语句执行时尝试从内存获取 a，拿到的就是旧值。然而，由于这两行代码在同一个 CPU core 上执行，打印语句将会先尝试检查 store buffer，当它发现 store buffer 中有一个变量的写入，而这个变量就是它要读取的 a，它就会直接使用 store buffer 中的值。因此，在单线程中，store buffer 在改善性能的同时，不会改变程序原有的逻辑。

使用 store buffer 的内存模型，称为 total store ordering (TSO)。TSO 模型保留了顺序一致性模型的大部分约定，除了允许使用 store buffer。这些 store buffer 隐藏了写入延迟，使得执行速度获得巨大提升。

store buffer 虽然带来性能的改善，但问题也很明显：因为 TSO 允许顺序一致性模型所不允许的行为，所以在采用 TSO 模型的硬件上跑的程序，会产生意想不到的结果。

让我们再回头看看一开始的例子。这次是在有 store buffer、采用 TSO 模型的硬件上跑。假设我们先执行了（1）和（3），这两个变量的修改都被写入了 store buffer 中，而不是内存中：

/2020/memory_model_1/2.png

接下来，在 core 1 上执行（2），即读取变量 b 并打印。此时，core 1 先尝试观察它自己的 store buffer，没有发现变量 b，于是它尝试从内存区域读取 b，读取的结果是 0。接着执行语句（4），同理，core 2 从内存中读取 a，结果也是 0。在未来的某一时刻，每个 core 上的 store buffer 被同步到内存中。

可以看到，在 TSO 模型下，程序的执行结果可能为 a = 0, b = 0，这个结果在顺序一致性模型中是不可能发生的。所以，多核上的开发并行程序，store buffer 会产生程序员无法预料的行为。

那既然 TSO 模型可能产生反直觉的结果，那么有没有什么架构采纳了这种优化机制呢？答案是所有！所有的现代 CPU 架构都采用了 store buffer，所以所有的硬件采用的内存模型至少和 TSO 一样。尤其是，最常用的 X86 架构，采用了和 TSO 模型非常接近的内存模型。这意味着，在现代 CPU 多核架构上写多线程程序，对会面对 TSO 内存模型带来的问题，好在主流的高级语言，较新版（如 C++11）都加入了相关的同步机制，使得只需在代码层面少许改动，就可以避免 TSO 模型带来的结果无法预料问题。

 

参考

http://15418.courses.cs.cmu.edu/spring2015/lecture/consistency/slide_001

https://courses.cs.washington.edu/courses/cse451/15au/notes/l17-mcm-slides.pdf

https://www.cs.utexas.edu/~bornholt/post/memory-models.html

- 全文完 -

相关文章

「 您的赞赏是激励我创作和分享的最大动力! 」

 C/C++, 并发, 并行, 操作系统, 多线程
返回 | 主页