无惧并行——从内存一致性模型到C++11内存模型

发表于 分类于 本文字数： 7.7k 阅读时长 ≈ 7 分钟

壊れかけの世界 崩れそうで目眩
这个支离破碎的世界 宛如即将崩溃般 头晕目眩

空っぽな体で 歪な視界
以空洞的身躯 容纳扭曲的视界

ゾクリと脈を打つ 命の線
不断跳动的脉搏 生命线

ナイフでなぞって 伸ばしてしまえたら
若是用小刀顺着线 向前沿伸的话

ねえ、誰か教えて 月が見えるなら
请问 谁来告诉我 若能看到那盏明月

消さないで まだ消さないで
请不要再消去 现在还未消去之物

消えないで まだ消えないで
请不要再消逝 如今还未消逝之人
——游戏《月姬 -A piece of blue glass moon-》主题曲《生命线》歌词

题图：不确定的旅程——盐田千春

Intro-操作系统课程上的内存模型不存在了

让我们先来看一段代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
volatile int x,y;
barrier sync_point(3),do_point(3);
void T1(){
  while (1){
    x = 1;
    printf("%d ",y);
    sync_point.arrive_and_wait();
    do_point.arrive_and_wait();
  }
}
void T2(){
  while (1){
    y = 1;
    printf("%d ",x);
    sync_point.arrive_and_wait();
    do_point.arrive_and_wait();
  }
}
int main(){
  thread t1(T1),t2(T2);
  while (cout){
    sync_point.arrive_and_wait();
    printf("\n");
    x=0;
    y=0;
    do_point.arrive_and_wait();
  }
}

其中sync_point和do_point是 C++20 引入的同步原语，在本程序中的表现在于必须三个线程都到达了sync_point和do_point才能继续运行，否则会一直阻塞直到有三个线程到达。之后会继续进行这样的操作。

按照操作系统课上的理解，这个程序只可能一直输出0 1/1 0/1 1，不可能出现0 0，因为有输出就代表x或y置 1，接下来输出时就不会输出 0。但是在我的两台机器上发生了诡异的现象（z3475laptop-Ryzen 4800H,u0_a251-Snapdragon 865）

这是因为操作系统课是基于是单核心处理器讲的，用多线程是为了解决 IO 阻塞导致 CPU 空转/CPU 资源管理等问题。到了现代多核心处理器，线程可以分派到不同核心上运行，每个核心内部都有 cache，cache 之间的同步造成的不一致性远比课上介绍的要复杂得多。

CPU 的内存一致性模型

一致性模型分为以下几种

顺序一致性（Sequential Consistency）

就是上述操作系统课程上介绍到的内存模型。

用上述的例子可以很清楚的鉴定一个 CPU 的内存一致性模型是否为顺序一致性的。

x86 完全存储定序 TSO(Total Store Order)

x86 CPU 使用的内存模型，其写操作有缓冲区，为定序的；读操作的结果和内存中的数据是一致的。写操作可能延迟应用到内存，但是一定是顺序应用的，但一旦应用到内存，所有处理器读的结果都是这个最新的值。

鉴定一个 CPU 是否是 TSO 的，可以使用连续写和多个核心交错读的方法。

  1. Test1
1
2
3
4
x = y = 0
Thread0/CPU0    Thread1/CPU1
x = 1           r0 = x
y = 1           r1 = y

其(r0,r1)一共可能出现的情况为(0,0),(1,0),(1,1)。

  1. Test2
1
2
3
Thread0/CPU0   Thread1/CPU1   Thread2/CPU2   Thread3/CPU3
x = 1          y = 1          r0 = x         r0 = y
                              r1 = y         r1 = x

就不可能出现 CPU2 为(1,0) CPU3 为(1,0)；

x86 CPU 为了实现内存一致性提供了三个内存屏障指令和 lock 前缀。

lfence阻止其前面的读操作重排到其后面，阻止其后面的读操作重排到其前面（一般情况下没有作用，除非使用绕过了缓存机制的指令，如 str 系列指令）

sfence阻止其前面的写操作重排到其后面，阻止其后面的写操作重排到其前面

mfence为上述两者的综合

lock 前缀保证了指令翻译成了一堆微指令的原子性，比如可以 LOCK inc r8，这样 r8 就会正常加一。

那么我们就可以凭借这些指令来构建顺序一致性的程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
volatile int x,y;
barrier sync_point(3),do_point(3);
#define mfence() __asm volatile ("mfence" ::: "memory");
void T1(){
  while (1){
  x = 1;
  mfence();
  printf("%d ",y);
  sync_point.arrive_and_wait();
  do_point.arrive_and_wait();
  }
}
void T2(){
  while (1){
  y = 1;
  mfence();
  printf("%d ",x);
  sync_point.arrive_and_wait();
  do_point.arrive_and_wait();
  }
}
int main(){
  thread t1(T1),t2(T2);
  while (cout){
    usleep(1);
    sync_point.arrive_and_wait();
    printf("\n");
    x=0;
    y=0;
    do_point.arrive_and_wait();
  }
}

ARM/POWER 宽松内存模型(Relaxed Memory Model)

ARM/POWER 使用的内存模型，其特点为所有读写均可重排，所有核心都有自己的全局内存副本。写读操作均操作自己的那份内存副本。核间同步机制保证了最低限度的一致性——即当多个核心写一个内存区域时，对于其他核心来说不可能出现数据回滚的情况。

1
2
3
4
5
6
7
8
9
10
11
Litmus Test: Coherence
Can this program see r1 = 1, r2 = 2, r3 = 2, r4 = 1?
(Can Thread 3 see x = 1 before x = 2 while Thread 4 sees the reverse?)

Thread 1    Thread 2    Thread 3    Thread 4
x = 1       x = 2       r1 = x      r3 = x
                        r2 = x      r4 = x

On sequentially consistent hardware: no.
On x86 (or other TSO): no.
On ARM/POWER: no.

以上所有不可能发生的情况在宽松内存模型中都可能发生。

构建软件内存模型

Adve 和 Hill 提出了一种同步模型，他们称之为 data-race-free（DRF）。这个模型假设硬件的内存同步操作与普通内存的读写分开。普通内存的读写可以在同步操作之间重新排序，但它们不能跨越同步操作进行移动。(也就是说，同步操作也是重新排序的屏障）。) 如果在所有理想化的顺序一致的执行中，不同线程对同一位置的任何两个普通内存访问要么都是读，要么被同步操作分开，迫使一个在另一个之前发生，那么这个程序被称为 Data-Race-Free。（译者注：即要么全是读，要么读写、写写是分离的）

现在我们介绍到的所有的内存模型都满足 DRF 的要求。

Adve 和 Hill 给出了一个证明，即硬件如果 “通过 Data-Race-Free 进行了弱排序”，这意味着它执行 Data-Race-Free 的程序就像通过了顺序一致的排序一样。

这意味着我们使用恰当的同步原语就可以使程序变成顺序一致内存模型的程序。

C++11 标准中的内存模型/同步原语

迈向 C++ 11，为了满足日益增长的多线程编程需求。在不破坏之前的“没有多线程的世界”的老 C++ 代码情况下。C++ 11 额外定义了 std::atomic 来保护基本类型。对 std::atomic 额外定义一些要求规定 std::atomic 操作原子性、可见性和重排的规则。因此 std::atomic 操作不止定义了原子性，还定义了std::atomic 操作在本线程中的指令重排顺序和“可见性”——修改对本线程/其他线程的影响。

默认的 std::atomic 已经使用最强的内存顺序(seq_cst)了，需要更细致的控制以实现更强的性能需要用户指定内存顺序（memory_order）。

释放消费顺序的规范正在修订中，而且暂时不鼓励使用 memory_order_consume (C++17)

作为例子，本节将会改造验证 x86 TSO 的代码使其符合顺序一致性模型的结果。当然对于其他平台也是一样。

std::memory_order

memory_order 应用环境 重排效果 可见性影响
relaxed ALL 无 无
consume
acquire 有此内存顺序的加载操作，在其影响的内存位置进行获得操作 当前线程中读或写不能被重排到此加载前 其他释放同一原子变量的线程的所有写入，能为当前线程所见。
release 有此内存顺序的存储操作进行释放操作 当前线程中的读或写不能被重排到此存储后 当前线程的所有写入，可见于获得该同一原子变量的其他线程
acq_rel 带此内存顺序的读修改写操作既是获得操作又是释放操作 当前线程的读或写内存不能被重排到此存储前或后 所有释放同一原子变量的线程的写入可见于修改之前，而且修改可见于其他获得同一原子变量的线程。
seq_cst 有此内存顺序的加载操作进行获得操作，存储操作进行释放操作，而读修改写操作进行获得操作和释放操作 存在一个单独全序 其中所有线程以同一顺序观测到所有修改

重排效果指导编译器如何编排指令，重排效果和可见性指导编译器如何插入平台特定的同步指令。

其中acquire、release、acq_rel均需要形成 release-acquire 对才能确保一个线程写的数据成功被另一个线程读。

relaxed无需操作。

对于 x86，seq_cst、acq_rel、acquire、release的一种最坏的实现方案下是直接插入mfence、mfence、lfence、sfence指令。当然这也是性能最差的方案，不过最能保证的seq_cst一定会产生跟mfence一样的效果。

std::atomic

std::memory_order 应用到 std::atomic 主要影响的重排和可见性。 std::atomic 默认是 seq_cst 内存顺序，如果不考虑性能直接用就可以达到和顺序一致性一样的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
atomic<int> x,y;
barrier sync_point(3),do_point(3);
void T1(){
  while (1){
  x.store(1);
  printf("%d ",y.load());
  sync_point.arrive_and_wait();
  do_point.arrive_and_wait();
  }
}
void T2(){
  while (1){
  y.store(1,rel);
  printf("%d ",x.load());
  sync_point.arrive_and_wait();
  do_point.arrive_and_wait();
  }
}
int main(){
  thread t1(T1),t2(T2);
  while (cout){
    sync_point.arrive_and_wait();
    printf("\n");
    x.store(0);
    y.store(0);
    do_point.arrive_and_wait();
  }
}

当然还可以用 release-acquire 实现，结果一样达到和顺序一致性一样的结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
atomic<int> x,y;
barrier sync_point(3),do_point(3);
auto rel = memory_order_release;
auto acq = memory_order_acquire;
void T1(){
  while (1){
  x.store(1,rel);
  printf("%d ",y.load(acq));
  sync_point.arrive_and_wait();
  do_point.arrive_and_wait();
  }
}
void T2(){
  while (1){
  y.store(1,rel);
  printf("%d ",x.load(acq));
  sync_point.arrive_and_wait();
  do_point.arrive_and_wait();
  }
}
int main(){
  thread t1(T1),t2(T2);
  while (cout){
    sync_point.arrive_and_wait();
    printf("\n");
    x.store(0,rel);
    y.store(0,rel);
    do_point.arrive_and_wait();
  }
}

std::atomic_thread_fence

即内存屏障，套对应 memory_order 就可以。一般直接用 seq_cst 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
volatile int x,y;
barrier sync_point(3),do_point(3);
void T1(){
  while (1){
  x = 1;
  atomic_thread_fence(memory_order::seq_cst);
  printf("%d ",y);
  sync_point.arrive_and_wait();
  do_point.arrive_and_wait();
  }
}
void T2(){
  while (1){
  y = 1;
  atomic_thread_fence(memory_order::seq_cst);
  printf("%d ",x);
  sync_point.arrive_and_wait();
  do_point.arrive_and_wait();
  }
}
int main(){
  thread t1(T1),t2(T2);
  while (cout){
    sync_point.arrive_and_wait();
    printf("\n");
    x=0;
    y=0;
    do_point.arrive_and_wait();
  }
}

你也可以用 rel-acq 对来替代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
volatile int x,y;
barrier sync_point(3),do_point(3);
auto rel = memory_order_release;
auto acq = memory_order_acquire;
void T1(){
  while (1){
  x = 1;
  atomic_thread_fence(rel);
  atomic_thread_fence(acq);
  printf("%d ",y);
  sync_point.arrive_and_wait();
  do_point.arrive_and_wait();
  }
}
void T2(){
  while (1){
  y = 1;
  atomic_thread_fence(rel);
  atomic_thread_fence(acq);
  printf("%d ",x);
  sync_point.arrive_and_wait();
  do_point.arrive_and_wait();
  }
}
int main(){
  thread t1(T1),t2(T2);
  while (cout){
    sync_point.arrive_and_wait();
    printf("\n");
    x=0;
    y=0;
    do_point.arrive_and_wait();
  }
}

std::mutex等

有关资料跟 Java 一样非常简单易懂这里就不谈了。

benchmark

编译运行计时命令，表格内是 total 秒数（图一乐）

1
2
g++ "$i.cpp" -o "$i" -std=c++20
sudo nice -20 zsh -c "time zsh -c \"./$i | head -n 100000 > /dev/null\""
std::atomic seq_cst std::atomic rel-acq std::memory_thread_fence seq_cst std::memory_thread_fence rel-acq
-O0 1.278s 1.238s 1.610s 1.618s
-O2 1.247s 0.971s 1.024s 1.300s

Reference

多处理器编程：从入门到放弃 (线程库、现代处理器架构、宽松内存模型) [南京大学 2023 操作系统-P5] (蒋炎岩)

【译文】硬件内存模型

【译文】编程语言内存模型

cppreference/atomic/memory_order