理解c++内存一致性模型

发表于 更新于 阅读次数： 本文字数： 19k 阅读时长 ≈ 17 分钟

我对内存屏障以及C++11引入的memory order一直处于一知半解的状态

知道有这么个东西，知道一部分原理，不知道什么场合去用它，一直以来我的多线程工具库里面只有锁，条件变量和原子变量三板斧，错过了很多更细粒度的优化机会。

在ChatGPT的帮助下，终于从头到尾理解了它的底层原理和应用场景

本文属于拾人牙慧的总结，将看到的一些资料整理出来，本文的大纲如下：

  • 缓存一致性

    从cpu缓存开始，引出多核cpu的缓存一致性(Cache Coherence)问题

    为了解决这个问题，发明了MESI协议，但是这个协议性能还不够好，因此引入了Store Buffer和Invalidate Queue来提高性能

  • 内存一致性

    Store Buffer，Invalidate Queue再加上编译器指令乱序和cpu指令乱序，导致了内存一致性(Memory Consistency)无法得到满足

    使用各种内存屏障来解决这些问题

  • C++的memory order

    为了简化和细化内存屏障，C++11引入了memory order

缓存一致性(Cache Conherence)

缓存一致性主要关注单个内存位置的行为。缓存一致性要求在一个多核系统中，处理器对特定内存位置的读写操作满足一定的一致性条件。

例如，当一个处理器对某个内存位置进行修改时，其他处理器能够观察到这个修改。其目标是确保每个处理器看到的内存位置值是一致的。

本节从cpu结构说起，介绍为了实现缓存一致性做了哪些工作

cpu结构

以下是Intel Skylake系统的结构图，其中包含了类似于4级缓存的eDRAM。在Broadwell架构中，eDRAM曾被设计成4级缓存，但在Skylake架构中，它已经不再只是4级缓存，而被英特尔定义为内存端缓存。

在Skylake的设计中，所有内存访问甚至包括通过PCIe总线进行的DMA访问，都可以被eDRAM缓存。

虽然eDRAM在这里被提及，但它并不是讨论的重点。它只被用来示例硬件发展的趋势，即缓存的级别正在不断增加。

现代的CPU Cache通常分为三层，分别叫L1，L2，L3 Cache, 其中L1，L2 Cache为每个CPU核特有，L3为所有CPU核共有，L1还分为缓存指令的i-cache(只读)和缓存程序数据的d-cache，L2，L3 Cache则不区分指令和程序数据，称为统一缓存(unified cache)

Cpu读取内存的某个地址数据时，会优先查看缓存，因此需要有一种方法可以将内存地址映射到多个缓存地址

映射方法分为全相连映射，直接映射，组相连映射

组相连映射是前两者的折中，已经完全替代了前两者（这部分内容不是重点，可以参见本文附录：内存到缓存映射）

L1缓存通常采用8路组相连映射，L2缓存采用16路组相连映射，L3缓存则可能采用更高阶数的组相连映射（如64路）

在讨论多核缓存一致性问题前，首先考虑在单核下cpu读写缓存的工作方式

  • 读

    需要读取的内存地址，通过映射寻找缓存行，找不到再访问内存

  • 写

    相对读，写则复杂多了

    写分为写回（Write back）和写通（Write through）

    访问缓存时失效后分为按写分配（Write allocate）和不按写分配（No-write allocate）

    这部分也不是重点，可以参见附录：写缓存策略

    在写通+不按写分配的策略下写入是最简单的：

    需要写入的内存地址，通过映射寻找缓存行

    命中：写入缓存+内存

    失效：写入内存

考虑写时写通+不按写分配的策略，由于L1和L2缓存对其他cpu是不可见的，当一个cpu更新自己的缓存数据时，其他cpu看不到

因此需要写传播：CPU需要将每个修改动作都通过总线进行广播，并实时监听总线上的消息

多核系统在这种情况下性能急剧下降，因此发明了缓存一致性协议（MESI）来优化这个问题

缓存一致性协议（MESI）

MESI是以下四个状态的简称:

  • M(modified)

    该行刚被 CPU 改过，并且保证不会出现在其它CPU的Cache Line中。即CPU是该行的所有者。CPU持有该行的唯一正确参照。

  • E(exclusive)

    和M类似，但是未被修改，即和内存是一致的，CPU可直接对该行执行修改(修改之后为modified状态)。

  • S(shared)

    该行内容至少被一个其它CPU共享，因此该CPU不能直接修改该行。而需要先与其它CPU协商。

  • I(invalid)

    该行为无效行，即为空行，前面提到Cache策略会优先填充Invalid行。

MESI是一个设计精密的状态机

当前状态 事件 状态流转规则
I（已失效） Local Read 由于当前缓存行失效，需要重新从内存中读取数据：
• 其他CPU中没有该数据，直接从内存中读取数据，并将缓存行状态置为E
• 其他CPU中存在该数据，且对应缓存行状态为M
要先将其他CPU中数据写回到内存中后再读取内存数据，并将缓存行状态置为S
• 其他CPU中存在该数据，且对应缓存行状态为S或E，从内存中读取数据，并将缓存行状态置为S
Local Write 由于当前缓存行失效，需要重新从内存中读取数据：
• 其他CPU中没有该数据，直接从内存中读取数据，修改数据后将缓存行状态置为M
• 其他CPU中存在该数据，且对应缓存行状态为M，要先将其他CPU中数据写回到内存中
并将缓存行状态置为I，然后本地再读取内存数据，修改数据后将缓存行状置为M
• 其他CPU中存在该数据，且对应缓存行状态为S或E，
本地CPU从内存中读取数据并将缓存行状态置为M，同时其他CPU将缓存行状态置为I
Remote Read 本地数据已失效，其他CPU读写操作不会再引起状态变化
Remote Write 本地数据已失效，其他CPU读写操作不会再引起状态变化
E（独占） Local Read 状态不变
Local Write 状态变为M
Remote Read 其他CPU访问数据，不再独占，状态变为S
Remote Write 数据被其他CPU修改，本地缓存数据失效，状态变为I
S（共享） Local Read 状态不变
Local Write 本地状态变为M，其他CPU中缓存该数据的缓存行状态变为I
Remote Read 状态不变
Remote Write 数据被其他CPU修改，本地缓存数据失效，状态变为I
M（已修改） Local Read 状态不变
Local Write 状态不变
Remote Read 其他CPU需要访问最新数据，需要将数据写入内存中，状态变为S
Remote Write 其他CPU需要访问最新数据，需要将数据写入内存中，由于其他CPU获取数据后又修改了数据，因此状态变为I

状态机显然是难以理解的，因此举例说明一个双核系统（核心A和核心B）采用MESI协议来维护缓存一致性

在这个例子中，我们将展示在两个核心上同时访问共享数据时，MESI协议是如何工作的。

内存中有一个数据块X，初始时两个核心的缓存都没有这个数据块。现在让我们分析以下操作顺序：

  1. 核心A读取数据块X：
  • 因为X不在核心A的缓存中，发生缓存未命中，核心A将发送读请求至内存或者其他的缓存。
  • 数据块X被加载到核心A的缓存，并将其状态标记为Shared（S）。
  1. 核心B读取数据块X：
  • 同样，因为X不在核心B的缓存中，发生缓存未命中，核心B发送读请求。
  • 数据块X被加载到核心B的缓存，将其状态标记为Shared（S），并通知核心A，X仍处于共享状态。

现在两个核心的缓存都有数据块X，状态都为Shared（S）。

  1. 核心A需修改数据块X：
  • 因为数据块X的状态为Shared（S），核心A需要先获取独占权限。核心A向总线发送Invalidate请求，表示要修改数据。
  • 此时核心B监听到Invalidate请求，它将使本地缓存中的数据块X无效（Invalid），并回复发送Invalidate ack的确认。
  • 核心A收到Invalidate ack，将本地缓存中数据块X的状态更新为Modified（M）。然后，核心A修改数据块X。
  1. 核心B再次读取数据块X：
  • 由于核心B的本地缓存中数据块X为Invalid（I）状态，发生缓存未命中。核心B将发送读请求。
  • 核心A监听到该请求，检测到数据块X在其本地缓存中为Modified（M）状态。核心A将把最新的数据写回内存，并更新本地缓存中数据块X的状态为Shared（S）。同时，确认核心B的请求。
  • 核心B收到确认，加载数据块X到本地缓存，并将状态设置为Shared（S）。

经过这一系列操作，MESI协议确保了在双核系统中共享数据的一致性。在整个过程中，核心间通过监听总线请求，并对本地缓存状态做相应调整，实现了缓存一致性。

这里有一个很棒的网站可以模拟多核Cpu读写时MESI的状态转换MESIHelp，出色的动画效果很适合用来理解MESI

可以看到，MESI协议的一个变量在多个CPU中共享时，每次写操作都要先发一个 invalidate 消息广播，再等其他 CPU 将缓存行设置为无效后返回 invalidate ack 才能进行缓存数据修改，这样性能太差了

因此引入了Store Buffer和Invalidate Queue来提高写性能

Store Buffer

在CPU和Cache之间引入了Store Buffer，写操作时无需立即向其他CPU发送 invalidate 消息

而是先写入Store Buffer中，然后立刻返回执行其他操作，由 Store Buffer异步执行发送广播消息，等到接收到其他cpu的响应后再将数据从Store Buffer移到Cache

当写入Store Buffer的数据A还移到Cache之前，如果需要读取数据A的值，显然不能读取Cache，因此引入了Store Forwarding来读取最新的Store Buffer数据

Store Forwarding和本文主题无关，了解概念即可，后续都不会提到他

Invalidate Queue

由于Store Buffer的容量有限，如果Store Buffer发送Invalidate消息后，接收到消息的CPU处于忙碌状态无法及时响应Invalidate ack，Store Buffer很快就会写满。

因此引入了Invalidate Queue，CPU在消息被放入队列后立即确认Invalidate消息，而无需等待相关Cache行实际失效

当然，在准备发送数据B的Invalidate消息时，CPU必须先查看它的Invalidate Queue。

如果Invalidate Queue存在未处理的数据B的Invalidate消息，CPU必须等待处理完毕才可以发送。

只有遇到False Sharing之类的争用激烈场景时，性能才会出现明显下降，这部分也不是本文重点，略过

小结

可以看到，从多核cpu结构开始，MESI，Store Buffer，Invalidate Queue都是一步一步不得不发展出来的设计

Store Buffer和Invalidate Queue相当于Invalidate消息的读队列和写队列

通过异步队列来提高性能是计算机科学中的常见手法，通过这种方式也很容易设计各种各样的过载保护方式

但是这显然会带来乱序问题，实际上就是cpu结构优化到了极限

只能通过和程序员合作的方式，在一定的情况下乱序执行指令来进一步提高性能

这就是下一部分的内容，程序员需要了解的内存一致性

内存一致性(Memory Consistency)

内存一致性关注整个内存系统的全局行为。内存一致性主要涉及处理器对内存的访问顺序和更新顺序。

内存一致性定义了处理器之间允许的内存访问顺序，为程序员提供一个简化的内存访问模型。

例如，顺序一致性（Sequential Consistency）要求所有处理器上的操作按照一个全局顺序进行，使得它们在时间上有一个一致的顺序。

本节从内存乱序原因说起，随后介绍用于解决内存乱序的内存屏障类型，并简单介绍几个内存一致性模型

内存乱序原因

处理器和编译器有一个核心的设计规则，叫做As-If rule:

Allows any and all code transformations that do not change the observable behavior of the program.

As-If rule表示在不改变程序可观察行为的前提下，编译器和处理器可以自由地对指令进行优化和重新排序。

编译器乱序

1
2
3
4
5
int A, B;
void test() {
  A = B + 1;
  B = 0;
}

不打开编译器的优化,把它编译成汇编,我们可以看到,B的赋值在A的后面,和原程序的顺序一样

1
2
3
4
5
$ gcc -S -masm=intel test.c
	mov	eax, DWORD PTR B[rip]
	add	eax, 1
	mov	DWORD PTR A[rip], eax
	mov	DWORD PTR B[rip], 0

用O2打开优化:

1
2
3
4
5
$ gcc -O2 -S -masm=intel test.c	
	mov	eax, DWORD PTR B[rip]
	mov	DWORD PTR B[rip], 0
	add	eax, 1
	mov	DWORD PTR A[rip], eax

这次编译器把B的赋值提到A的前面。

这就是编译器的As-If rule

解决办法
显式的Compiler Barrier
1
2
3
4
5
6
int A, B;
void test() {
  A = B + 1;
  asm volatile("" ::: "memory");
  B = 0;
}

用O2打开优化，可以看到乱序已经恢复

1
2
3
4
5
$ gcc -S -O2  -masm=intel test.c
	mov	eax, DWORD PTR B[rip]
	add	eax, 1
	mov	DWORD PTR A[rip], eax
	mov	DWORD PTR B[rip], 0
隐式的Compiler Barrier

非inline函数通常被视为隐式的Compiler Barrier，这是因为编译器需要保留函数调用的语义，并确保跨函数调用的指令不发生重排序

而另外一方面，不管是不是inline函数，只要某函数拥有Compiler Barrier的子函数，那么它一定是一个Compiler Barrier

处理器乱序

Store Buffer

Store Buffer会将写入异步完成，因此会导致写入被延后

也就是先执行的写入，当后续指令执行才真正写入

Invalidate Queue

而Invalidate Queue会将别的CPU的写入异步处理，因此会导致读到脏数据

也就是在前置指令执行完毕后，后执行的读实际上读取的之前的旧数据

其他乱序

Store Buffer会导致写入延后，Invalidate Queue会导致读取提前

由于硬件上的各种各样的实现，写入也有可能被提前，读取也有可能被延后

例如CPU在读取缓存时未能命中，而写入时命中了缓存，那么此类指令重新排序可能会发生在某些处理器上

由于As-If rule，不同的硬件发生什么样的乱序都是有可能的

举例证明处理器乱序

考虑这样的例子

Thread1 Thread2
X = 1 Y = 1
r1 = Y r2 = X

即使在强内存模型的在x86-64平台上，有可能是乱序执行的，关于强内存模型在后面再详细介绍

这个例子有可能会执行成这样的顺序

时序 Thread1 Thread2
1 r1 = Y
2 r2 = X
3 X = 1
4 Y = 1

从而导致了r1和r2都为0

下面实际运行一下这个例子，平台刚才已经说了x86-64

Cpu型号为Intel(R) Xeon(R) CPU E5-2630 v3 @ 2.40GHz

在操作系统Ubuntu20.04下编译运行

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <mutex>
#include <thread>
#include <random>
#include <condition_variable>
#include <iostream>

std::mutex g_mtx;
std::condition_variable g_start_cv1, g_start_cv2, g_end_cv;
int X, Y, r1, r2;

std::random_device g_rd;
bool g_start1{false}, g_start2{false};
int g_end{2};

void thread1() {
    std::mt19937 gen{g_rd()};
    std::uniform_int_distribution<int32_t> dis;
    while (true) {
        {
            std::unique_lock<std::mutex> lock(g_mtx);
            g_start_cv1.wait(lock, []() {return bool(g_start1);});
        }
        g_start1 = false;
        while(dis(gen) % 8 != 0);

        X = 1;
        asm volatile("" ::: "memory");//防止编译器重排
        r1 = Y;

        std::unique_lock<std::mutex> lock(g_mtx);
        g_end--;
        g_end_cv.notify_one();
    }
}

void thread2() {
    std::mt19937 gen{g_rd()};
    std::uniform_int_distribution<int32_t> dis;
    while (true) {
        {
            std::unique_lock<std::mutex> lock(g_mtx);
            g_start_cv2.wait(lock, []() {return bool(g_start2);});
        }
        g_start2 = false;
        while(dis(gen) % 8 != 0);

        Y = 1;
        asm volatile("" ::: "memory");//防止编译器重排
        r2 = X;

        std::unique_lock<std::mutex> lock(g_mtx);
        g_end--;
        g_end_cv.notify_one();
    }
}

int main() {
    std::thread t1(thread1);
    std::thread t2(thread2);

    int detected = 0;
    for (int i = 0;;i++) {
        X = 0;
        Y = 0;
        {
            std::unique_lock<std::mutex> lock(g_mtx); 
            g_start1 = true;
            g_start2 = true;
            g_start_cv1.notify_one();
            g_start_cv2.notify_one();
        }
        {
            std::unique_lock<std::mutex> lock(g_mtx);
            g_end_cv.wait(lock, []() {return g_end == 0;});
        }
        g_end = 2;
        if (r1 == 0 && r2 == 0) {
            detected++;
            std::cout << detected << " reorders detected after " << i << " iterations" << std::endl;
        }
    }

    t1.join();
    t2.join();
}

g_start1和g_start2的条件和条件变量，都是为了控制thread1和thread2同步到同一时刻一起运行

而end的条件和条件变量，是为了控制主线程阻塞到thread1和thread2都结束以后，检查一下r1和r2的值，如果都为0说明两个线程都乱序执行了

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
$ g++ -std=c++11 store_load_detect.cpp -o out.exe -g -Wall -pthread && ./out.exe
1 reorders detected after 192 iterations
2 reorders detected after 787 iterations
3 reorders detected after 978 iterations
4 reorders detected after 1410 iterations
5 reorders detected after 1821 iterations
6 reorders detected after 1984 iterations
7 reorders detected after 2509 iterations
8 reorders detected after 3258 iterations
9 reorders detected after 4291 iterations
10 reorders detected after 4324 iterations
11 reorders detected after 4669 iterations
12 reorders detected after 4885 iterations
13 reorders detected after 5282 iterations
14 reorders detected after 5293 iterations
15 reorders detected after 5296 iterations
16 reorders detected after 7094 iterations
17 reorders detected after 7759 iterations
18 reorders detected after 7983 iterations
19 reorders detected after 8046 iterations
20 reorders detected after 8263 iterations
21 reorders detected after 8751 iterations
22 reorders detected after 9381 iterations
23 reorders detected after 9794 iterations
24 reorders detected after 9855 iterations
25 reorders detected after 10831 iterations

看起来没几百个循环就会导致1次两个线程都乱序执行，那么两个线程有任何一个乱序执行的概率就更高了

解决办法

修改编译器屏障的那一行代码，改为

1
asm volatile("mfence" ::: "memory");

再次编译执行，乱序就消失了，这个神奇的mfence就是内存屏障在x86-64上的汇编指令

内存屏障

各个平台的内存屏障指令是各种各样的

但是他们都可以抽象成四种内存屏障，这是为了解决四种内存乱序方式

  • LoadLoad屏障

    Invalidate Queue会导致读取到旧数据，导致读取的位置看起来比实际更提前

    处理完Invalidate Queue，当前cpu就不再有脏数据了

    （虽然其他的cpu存在Store Buffer，可能有更新数据还没写入，但是其他cpu没有发送出来的Invalidate ack就不算真正的写入数据，就不影响当前cpu的读取）

    再关闭其他的编译器+处理器乱序优化，就可以完成LoadLoad屏障，又叫读屏障

  • StoreStore屏障

    Store Buffer会导致写入异步执行，导致写入被延后

    处理完Store Buffer，当前的写入就一定同步到内存了

    (不过因为其他cpu的Invalidate Queue，不一定保证其他cpu读取屏障前后的两个数据的顺序)

    再关闭其他的编译器+处理器乱序优化，就可以完成StoreStore屏障，又叫写屏障

  • LoadStore屏障

    和Invalidate Queue以及Store Buffer无关

    其他的处理器乱序都有可能导致这个出现，和硬件有关

  • StoreLoad屏障

    刚才提到了，设置了StoreStore屏障后，写入不再被延后，但是读取依然有可能被提前

    所以需要同时处理Store Buffer和Invalidate Queue

    可以看做是原子执行的LoadLoad屏障+StoreStore屏障，这在各个平台都是最强屏障了，因此又叫全屏障

    很显然，他的执行代价也是最高的

    在PowerPC上，StoreLoad叫做sync，而LoadLoad+StoreStore+LoadStore叫做lwsync，意思是lightweight sync，可见StoreLoad屏障的代价之高

硬件平台的内存模型

刚才总结的四种内存屏障，对应的四种内存乱序方式，在不同的硬件上是不一样的

硬件的内存模型有非常多种，参见wiki

这里只简单介绍三种

顺序一致性模型（Sequential consistency）

理想模型，没有乱序的存在。由于对重排的限制过大，性能不好，因此没有一个硬件体系实现这个级别的一致性

强一致性模型 (Strong consistency)

Total Store Ordering

刚才举例的X86-64就是这个级别的一致性模型

它没有Invalidate Queue，因此不需要LoadLoad屏障

Store Buffer实现成了一个队列，保证了StoreStore顺序

也没有任何额外的处理器乱序导致LoadStore出现

综上，LoadLoad+StoreStore+LoadStore都是不存在的

在这种情况下，提供的lfence（Load Fence）和sfence（Store Fence）分别对应的LoadLoad屏障和StoreStore屏障，实际上不会产生任何作用

只有刚才使用的mfence（Memory Fence）代表了StoreLoad屏障

弱一致性模型 (Weak consistency)

Weak With Data Dependency Ordering

ARM, PowerPC, Itanium，在Aplpha的基础上，支持数据依赖排序，A->B，它能保证加载B时，必定已经加载最新的A

Really Weak Ordering

DEC Alpha是弱内存模型，它可能经历所有的四种内存乱序

最后放一张图在这里，总结常见的内存模型

各平台的内存模型实际上我也没有研究的太仔细，这是因为我是一个C++程序员，托C++的福，把这些底层细节都已经封装好了

C++的各种操作对应的各平台实现点击这里查看

因此我只需要了解C++的内存模型即可

C++的Memory Order

C++分为六种内存序

1
2
3
4
5
6
7
8
typedef enum memory_order {
  memory_order_relaxed,
  memory_order_consume,
  memory_order_acquire,
  memory_order_release,
  memory_order_acq_rel,
  memory_order_seq_cst
} memory_order;

我第一次看到的时候头皮发麻，这么多Memory Order，标准库的不同操作能使用的Memory Order还不一样，这可怎么记呀

实际上memory_order_consume可以不用管，自C++17起已经不鼓励使用

详见P0371R1

It is widely accepted that the current definition of memory_order_consume in the standard is not useful. All current compilers essentially map it to memory_order_acquire. The difficulties appear to stem both from the high implementation complexity, from the fact that the current definition uses a fairly general definition of "dependency", thus requiring frequent and inconvenient use of the kill_dependency call, and from the frequent need for [[carries_dependency]] annotations.

C++17 开始不建议使用 memory_order_consume，这是由于其实现和使用上的困难。据 C++ 标准库工作组指出，其表现并未如预期那样带来性能优势。

memory_order_consume 的设计初衷是提供一种选择，在某些硬件平台上，它可能比 memory_order_acquire 更有效率。然而，memory_order_consume 的实际效用取决于编译器如何确定哪些后续操作实际上依赖于原子操作的结果。这可能需要复杂的编译器分析和硬件特性支持，这些在许多现实场景和平台中都很难实现。因此当前所有编译器本质上都将其映射到 memory_order_acquire上。

那么剩下的5种Memory Order实际对应了3种模型，他们也遵循了刚才提到的硬件平台的三种主流模型

C++的内存模型

和硬件平台的内存模型中顺序相反，从最宽松的模型开始介绍，这是因为后续的严格模型的代码会用到宽松模型

弱一致性模型(Weak consistency)

Relax模型

memory_order_relaxed是C++的atomic<T>和atomic_thread_fence的最宽松的等级

相当于硬件平台的内存模型中的Really Weak Ordering

任何乱序都有可能产生，包含了LoadLoad+StoreStore+LoadStore+StoreLoad的内存屏障期望避免的全部乱序

一般当单个原子变量进行模糊计数，读取方不需要精确值的时候，大概估计个次数，就可以使用它

强一致性模型 (Strong consistency)

Acquire-Release模型

包含了memory_order_acquire, memory_order_release, memory_order_acq_rel

在介绍Acquire-Release模型的概念之前，首先介绍一下C++ 中用来描述多线程内存顺序（memory ordering）关系的术语

多线程内存顺序（memory ordering）关系
  • sequenced-before：
    • 这是单线程中的概念，定义了在同一线程中的两个表达式的执行顺序。如果表达式 A 顺序在表达式 B 之前，那么在执行过程中，A 的效果将在 B 之前产生。
  • synchronizes-with：
    • 这是多线程之间的概念。当一个线程的释放操作（release operation）与另一个线程的获取操作（acquire operation）对同一原子变量进行操作时，我们说这两个操作存在 synchronizes-with 的关系。
    • 简单来说，如果线程 A 写入一个值，线程 B 读取该值，则 A synchronizes-with B
  • happens-before也叫Happened-before：
    • Happened-before wiki定义
    • 对单线程来说，happens-before 意味着 sequenced-before
    • 对多线程来说，happens-before 意味着synchronizes-with
    • 和上述的两个关系侧重点不同，happens-before 的关系可以传递，它定义了在并发程序中的内存可见性和操作顺序。

在实践中，以下的规则可以帮助理解这些关系：

  • 如果 A sequenced-before B，那么 A 的结果将在 B 可见。
  • 如果 A synchronizes-with B，那么 A 和 B 将会看到彼此在原子变量上的操作。
  • 如果 A happens-before B，那么线程中对于内存操作的顺序将和程序中指定的顺序一致。

请注意，如果两个操作没有任何的 happens-before 关系，那么这些操作就是并发的，编译器和处理器可能会以你不期待的方式对它们进行重新排序，这可能会导致非预期的行为。

对Acquire-Release模型而言

"release"（释放）可以被理解为线程在完成对共享数据的读写后"释放"它的访问权限。这样可以确保在释放操作前的所有读或写都在释放操作之前完成，从而允许其他线程安全地访问该数据。

"acquire"（获取）可以被理解为线程在开始读取或修改共享数据之前需要"获取"访问权限。这样可以确保在获取操作后的所有读取或写入都在获取操作之后发生，从而避免了可能出现的数据竞争。

一个线程使用release写数据，然后另外一个线程使用acquire获取数据，就可以构造出多线程的synchronizes-with的关系，配合单线程sequenced-before，完成可以传导的happens-before关系

举个例子

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
#include <atomic>
#include <cassert>

std::atomic<bool> x = false;
std::atomic<bool> y = false;
std::atomic<int> v[2];

void f() {
  // v[0]、v[1] 的设置没有先后顺序，但都 happens-before 1
  v[0].store(1, std::memory_order_relaxed);
  v[1].store(2, std::memory_order_relaxed);
  x.store(true,
          std::memory_order_release);  // 1 happens-before 2（由于 2 的循环）
}

void g() {
  while (!x.load(std::memory_order_acquire)) {  // 2：happens-before 3
  }
  y.store(true,
          std::memory_order_release);  // 3 happens-before 4（由于 4 的循环）
}

void h() {
  while (!y.load(
      std::memory_order_acquire)) {  // 4 happens-before v[0]、v[1] 的读取
  }
  assert(v[0].load(std::memory_order_relaxed) == 1);
  assert(v[1].load(std::memory_order_relaxed) == 2);
}

在这个例子中，无论如何可以保证v0和v1读取的值分别为1和2不会有任何乱序

这个模型非常适合用来实现多级的生产消费模型

实现原理

memory_order_acquire由LoadLoad+LoadStore组成，从cpu结构来看意味着读取时处理完了Invalidate Queue的全部数据

memory_oder_release由LoadStore+StoreStore组成，从cpu结构来看意味着写入后处理完了Store Buffer的全部数据，或者保证Store Buffer不会对写入出现任何重排

这也意味着在x86-64平台上，由于Total Store Ordering的强一致性模型，只会出现StoreLoad重排，因此在这个平台上使用这个模型除了编译器屏障不会有任何其他作用

刚才提到的各种操作对应的各平台实现也可以验证这个逻辑

Architectures

x86 (including x86-64)

C/C++11 Operation x86 implementation
Consume Fence:
Acquire Fence:
Release Fence:
Acq_Rel Fence:

顺序一致性模型（Sequential consistency）

memory_order_seq_cst是C++的atomic<T>和atomic_thread_fence的默认操作等级

在硬件平台的内存模型中提过，这是最强的一致性，包含了LoadLoad+StoreStore+LoadStore+StoreLoad的全部内存屏障

顺序一致性虽然是默认等级，但是很多场景下也是仅有的选择

例如Peterson lock

使用场景：Peterson lock

Peterson lock介绍可以看Peterson算法理解

假设有两个人共同进入一个房间办事，一次只能进入一个人，一个人进入了，另一个人就要在外面等待。每个人要表达一次我想进去和谦让，最后检查谁符合条件，谁就可以进去，

甲：我想进去（flag[0] = 0)

甲：我想让你进去（turn = 1)

乙：我想进去（flag[1] = 1)

乙：我想让你进去（turn = 0)

此时他们都表达了一次谦让和想进去。但由于甲想进去，乙作出了最后的谦让，所以甲可以进去房间办事。( while ((flag[1] == 1) && (turn == 1 )) )

这个算法只能在两个线程中使用，本身的应用面不是很广，和双buffer的逻辑有点相似

这个算法必须使用StoreLoad的内存屏障实现

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
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <thread>
#include <atomic>

const int N = 2;
int flag[N] = {0, 0};
int turn;
std::atomic<int> shared_resource = {0};

void peterson_lock(int threadID)
{
    int otherThreadID = 1 - threadID;
    flag[threadID] = 1;
    turn = otherThreadID;

    while (flag[otherThreadID] && turn == otherThreadID); // Wait for other thread
}

void peterson_unlock(int threadID)
{
    flag[threadID] = 0;
}

void worker(int threadID)
{
    for (int i = 0; i < 10000000; ++i)
    {
        peterson_lock(threadID);

        int tmp = shared_resource;
        shared_resource = tmp + 1;

        peterson_unlock(threadID);
    }
}

int main()
{
    std::thread t1(worker, 0);
    std::thread t2(worker, 1);

    t1.join();
    t2.join();

    std::cout << "shared_resource:" << shared_resource << std::endl;

    return 0;
}

这里使用了一个原子变量来累加，从而证明是lock的实现有问题导致临界区数据被污染

1
2
$ g++ -std=c++11 peterson_lock.cpp -o out.exe -g -Wall -pthread && ./out.exe
shared_resource:19999956

将peterson_lock这个函数改成

1
2
3
4
5
6
7
8
9
10
11
12
void peterson_lock(int threadID)
{
    int otherThreadID = 1 - threadID;
    flag[threadID] = 1;
    turn = otherThreadID;

    // Memory barrier to ensure flag and turn updates are visible to the other thread
    // asm volatile ("mfence" ::: "memory");
    std::atomic_thread_fence(std::memory_order_seq_cst);

    while (flag[otherThreadID] && turn == otherThreadID); // Wait for other thread
}

插入了一个memory_order_seq_cst的atomic_thread_fence，在 x86-64上相当于mfence

1
2
$ g++ -std=c++11 peterson_lock.cpp -o out.exe -g -Wall -pthread && ./out.exe
shared_resource:20000000

参考资料

附录

内存到缓存映射

wiki百科

  • 直接映射

    假设有一个缓存系统，包含4个缓存行，每个缓存行能存放一个内存块，因此有4个块：缓存行0，缓存行1，缓存行2，缓存行3。同时主存包含8个内存块，分别为块0，块1，块2，块3，块4，块5，块6，块7。

    按照直接映射方法，我们将主存的内存块按照缓存行的数量进行分组。在这个例子中，缓存行数量为4，所以主存被分成两组：组0(包括内存块0、1、2、3)和组1(包括内存块4、5、6、7)。

    每个组中的内存块按照组内块号取模映射到对应的缓存行。组0的映射关系如下：

    • 内存块0（组内块号为0 % 4 = 0）映射到缓存行0
    • 内存块1（组内块号为1 % 4 = 1）映射到缓存行1
    • 内存块2（组内块号为2 % 4 = 2）映射到缓存行2
    • 内存块3（组内块号为3 % 4 = 3）映射到缓存行3

    组1的映射关系如下：

    • 内存块4（组内块号为4 % 4 = 0）映射到缓存行0
    • 内存块5（组内块号为5 % 4 = 1）映射到缓存行1
    • 内存块6（组内块号为6 % 4 = 2）映射到缓存行2
    • 内存块7（组内块号为7 % 4 = 3）映射到缓存行3

    让我们说CPU想要访问主存中的内存块5。首先检查缓存行1（因为组1的组内块号为1，对应到缓存行1），如果缓存行1中的数据与内存块5匹配，则直接从缓存行1中提取数据。如果不匹配，CPU从主存中读取内存块5，并将其存储到缓存行1中。特别是在这个例子中，内存块1和内存块5不能同时存在于缓存行1中，所以如果内存块5被加载到缓存，内存块1将被替换。

  • N路组相联

    假设有一个缓存系统，包含4个缓存行，将缓存划分为2组，每组包含2个缓存行。主存包含8个内存块，分别为块0，块1，块2，块3，块4，块5，块6，块7。

    按照组相连映射方法，主存将被分为两组：组0(包括内存块0、1、2、3)和组1(包括内存块4、5、6、7)。在这个例子中，缓存有2组，每组有2个缓存行，因此主存中的内存块可以映射到同一组的多个缓存行。

    映射关系如下：

    • 组0的缓存行：缓存行0，缓存行1
    • 组1的缓存行：缓存行2，缓存行3

    在组相连映射中，每个组内的内存块可以映射到该组的任意缓存行。例如，组0的内存块0、1、2、3可以映射到缓存行0或缓存行1。组1的内存块4、5、6、7可以映射到缓存行2或缓存行3。

    当访问数据时，首先确定内存块属于哪个组。例如，如果想访问内存块5，则它属于组1。接着在组1的缓存行（缓存行2和缓存行3）中查找内存块5。如果在组1的任何一个缓存行中找到内存块5，则称为缓存命中。如果组1的缓存行都没有内存块5，则需要将内存块5从主存加载到组1的一个缓存行中，这时如果组1的两个缓存行都已满，则需要按照某种替换策略（如最近最少使用-LRU）来决定替换哪个缓存行的数据。

    N路组相联的一个极端是直接映射，可以看做1路组相联

  • 全相联

    N路组相联的另外一个极端是全相联。这种缓存意味着内存中的数据块可以被放置到缓存的任意区域。

    也就是只存在1组，cpu查询数据时遍历组内全部缓存行

写缓存策略

wiki百科

  • 按写分配和不按写分配

    引自wiki百科

    按写分配是指，先如处理读失效一样，将所需数据读入缓存，然后再将数据写到被读入的单元。不按写分配则总是直接将数据写回内存。

  • 写回和写通

    假设采用写分配的方式

    假设程序需要频繁地读写一个整数变量x。假设我们的计算机系统有一个CPU缓存和内存，x当前的值分别存在缓存和内存中。

    写直达策略： 当程序对变量x进行修改时，写直达策略要求CPU立即将修改后的x值同时写入缓存和内存中。这样，缓存中的x值和内存中的x值保持强一致性。但每次修改x值后都要同时更新缓存和内存，这会影响写操作的性能。

    写回策略： 为了提高性能，写回策略在发生读写操作时进行如下操作：

    • 当缓存命中数据时（即缓存中有x的副本），直接在缓存中修改x值，同时标记该缓存行为已修改（表示x值已经被更改）。

    • 当缓存未命中数据时，如果x值对应的缓存行已满并且该缓存行被标记为已修改： a）将缓存行中的数据写回内存（即将已修改的数据同步到内存中）； b）将当前要获取的x值从内存读到缓存中； c）在缓存中修改x值，并标记该缓存行为已修改。

    • 如果该缓存行未被标记为已修改，则直接将x值从内存读到缓存行中，修改x值后标记该缓存行为已修改。