c++ 11的多线程编程的原子操作涉及内存模型的选择，关于内存的模型是一个很复杂的话题，涉及了很多底层的知识，比如cpu缓存（cpu缓存会导致多线程访问时有些变量还没有回写到内存）、编译乱序等（编辑后的代码顺序和程序写的顺序并不一致）。涉及的概念包括happens-before、synchronized-with等

cpu高速缓存

现代计算机都包含多个处理器，每个处理器包含多个核心，每个核心又包含多线程（也可以叫做虚拟核）。CPU的缓存结构一般分三层，L1，L2和L3，级别越小的缓存，越接近CPU， 意味着速度越快且容量越少。

  • L1是最接近CPU的，它容量最小，速度最快，每个核上都有一个L1 Cache(准确地说每个核上有两个L1 Cache， 一个存数据 L1d Cache， 一个存指令 L1i Cache)；
  • L2 Cache 更大一些，例如256K，速度要慢一些，一般情况下每个核上都有一个独立的L2 Cache；
  • L3 Cache是三级缓存中最大的一级，例如12MB，同时也是最慢的一级，在同一个CPU插槽之间的核共享一个L3 Cache。

当CPU运作时，它首先去L1寻找它所需要的数据，然后去L2，然后去L3。如果三级缓存都没找到它需要的数据，则从内存里获取数据。寻找的路径越长，耗时越长。所以如果要非常频繁的获取某些数据，保证这些数据在L1缓存里。这样速度将非常快。下表表示了CPU到各缓存和内存之间的大概速度：

CPU查询 大约需要的CPU周期 大约需要的时间（单位ns）
寄存器 1 cycle
L1 Cache ~3-4 cycles ~0.5-1 ns
L2 Cache ~10-20 cycles 　　 ~3-7 ns
L3 Cache ~40-45 cycles 　　 ~15 ns
跨槽传输 ~20 ns
内存 ~120-240 cycles ~60-120ns

利用CPU-Z可以查看CPU缓存的信息：

1
2
3
4
5
6
7
8
[m_tgame@TENCENT64site ~]$ cat /sys/devices/system/cpu/cpu0/cache/index0/size
32K
[m_tgame@TENCENT64site ~]$ cat /sys/devices/system/cpu/cpu0/cache/index1/size
32K
[m_tgame@TENCENT64site ~]$ cat /sys/devices/system/cpu/cpu0/cache/index2/size
256K
[m_tgame@TENCENT64site ~]$ cat /sys/devices/system/cpu/cpu0/cache/index3/size
15360K

默认情况下，CPU核心所有的数据的读或写都存储在缓存中。当然，也有内存区域不能被缓存的，但是这种情况只发生在操作系统的实现者对数据考虑的前提下；对程序实现者来说，这是不可见的。这也说明，程序设计者可以故意绕过某些缓存

缓存，是由缓存行组成的。一般一行缓存行有64字节(以前是32字节)。所以使用缓存时，并不是一个一个字节使用，而是一行缓存行、一行缓存行这样使用；换句话说，CPU存取缓存都是按照一行，为最小单位操作的，因为缓存需要标识出缓存对应的内存地址，如果使用一个字节为最小单位，则额外的标记信息都会大于本身的缓存的信息

当某条指令修改内存时，仍然要先装入缓存行，因为任何指令都不可能同时修改整行。因此需要在写操作前先把缓存行装载进来。如果缓存行被写入，但还没有写回主存，那就是所谓的“脏了”。脏了的行一旦写回主存，脏标记即被清除。

更精确的cache实现需要考虑到其他更多的可能性，比如第二个CPU在读或者写他的cache line时，发现该cache line在第一个CPU的cache中被标记为脏数据了，此时我们就需要做进一步的处理。在这种情况下，主存储器已经失效，第二个CPU需要读取第一个CPU的cache line。通过测试，我们知道在这种情况下第一个CPU会将自己的cache line数据自动发送给第二个CPU。这种操作是绕过主存储器的，但是有时候存储控制器是可以直接将第一个CPU中的cache line数据存储到主存储器中。对第一个CPU的cache的写访问会导致本地cache line的所有拷贝被标记为无效。

一般来说，缓存失效有三种情况：

  1. 第一次访问数据, 在cache中根本不存在这条数据, 所以cache miss, 可以通过prefetch解决。
  2. cache冲突, 需要通过补齐来解决（伪共享的产生）。
  3. cache满, 一般情况下我们需要减少操作的数据大小, 尽量按数据的物理顺序访问数据。

参考：
https://www.cnblogs.com/techyc/p/3607085.html
https://www.oschina.net/translate/what-every-programmer-should-know-about-cpu-cache-part2?print

编译乱序

首先需要明确一个普遍存在，但却未必人人都注意到的事实：程序并不总是按照源码中的顺序被执行的，此谓之乱序，乱序产生的原因可能有好几种：

  • 编译器出于优化的目的，在编译阶段将源码的顺序进行交换。
  • 程序执行期间，指令流水被 cpu 乱序执行。
  • cache 的分层及刷新策略使得有时候某些写，读操作的顺序被重排。

以上乱序现象虽然来源不同，但从源码的角度，对上层应用程序来说，他们的效果其实相同：写出来的代码与最后被执行的代码是不一致的。

这个事实可能会让人很惊讶：有这样严重的问题，还怎么写得出正确的代码？这担忧是多虑了，乱序的现象虽然普遍存在，但它们都有很重要的一个共同点：在单线程执行的情况下，乱序执行与不乱序执行，最后都会得出相同的结果 (both end up with the same observable result), 这是乱序被允许出现所需要遵循的首要原则，也是为什么乱序虽然一直存在但却多数程序员大部分时间都感觉不到的原因。

从乱序的种类来看，乱序主要可以分为如下4种：

  1. 写写乱序(store store), 前面的写操作被放到了后面的操作之后，比如：

    1
    2
    3
    4
    5
    a = 3;
    b = 4;
    被乱序为：
    b = 4;
    a = 3;

  2. 写读乱序(store load)，前面的写操作被放到了后面的读操作之后，比如：

    1
    2
    3
    4
    5
    a = 3;
    load(b);
    被乱序为
    load(b);
    a = 3;

  1. 读读乱序(load load)， 前面的读操作被放到了后一个读操作之后，比如：

    1
    2
    3
    4
    5
    load(a);
    load(b);
    被乱序为：
    load(b);
    load(a);

  2. 读写乱序(load store), 前面的读操作被放到了后一个写操作之后，比如

    1
    2
    3
    4
    5
    load(a);
    b = 4;
    被乱序为：
    b = 4;
    load(a);

程序的乱序在单线程的世界里多数时候并没有引起太多引人注意的问题，但在多线程的世界里，这些乱序就制造了特别的麻烦，究其原因，最主要的有2个：

  • 并发不能保证修改共享变量的原子性，这会导致常说的 race condition，各个线程同时修改某块内存，因此像 mutex，各种 lock 之类的东西在写多线程时被频繁地使用。
  • 变量被修改后，该修改未必能被另一个线程及时观察到，因此需要“同步”。

解决同步问题就需要确定内存模型，也就是需要确定线程间应该怎么通过共享内存来进行交互

参考：https://en.wikipedia.org/wiki/Memory_model_(programming)

内存模型

内存模型所要表达的内容主要是怎么描述：一个内存操作的效果，在各个线程间的可见性的问题。我们知道，对计算机来说，通常内存的写操作相对于读操作是昂贵很多很多的，因此对写操作的优化是提升性能的关键，而这些对写操作的种种优化，导致了一个很普遍的现象出现：写操作通常会在 CPU 内部的 cache 中缓存起来。这就导致了在一个 CPU 里执行一个写操作之后，该操作导致的内存变化却不一定会马上就被另一个 CPU 所看到。

1
2
3
4
cpu1 执行如下：
a = 3;
cpu2 执行如下：
load(a);

对如上代码，假设 a 的初始值是 0, 然后 cpu1 先执行，之后 cpu2 再执行，假设其中读写都是原子的，那么最后 cpu2 如果读到 a = 0 也其实不是什么奇怪事情。很显然，这种在某个线程里成功修改了全局变量，居然在另一个线程里看不到效果的后果是很严重的,因此必须要有必要的手段对这种修改公共变量的行为进行同步。

1
2
3
4
x = y = 0;
Thread1		Thread2
x = 1;		y = 1;
r1 = y;		r2 = x;

理论上来说，r1 == r2 = 0 ，但现实往往是残酷的，编译器只需把Thread1中的x=1和r1=y操作互换即可。

第一次接触memory order的读者看到这里估计已经晕了，不幸的是我们还必须引入更多概念才能讲清楚。首先，我们必须铭记在心的是，c++11引入这些概念本质上是为了解决 “visible side-effects”的问题，用通俗的话来讲：

线程1执行写操作A之后，如何可靠并高效地保证线程2执行读操作B时，操作A的结果是完整可见的？
为了解决上述问题，C++11引入了“happens-before”关系，其比较完整的定义如下：

http://preshing.com/20130702/the-happens-before-relation/

OK，现在问题就转化为：如何在A、B两个操作之间建立起happens-before关系呢？

happens-before

如果 操作A happens-before 于 操作B，那么就可以确定，操作B执行完之后，j 的值一定为 1；因为happens-before关系可以向程序员保证：在操作B执行之前，操作A的执行后的影响[或者说结果]（修改 i 的值）操作B是可以观察到的[或者说可见的]

换句话说，如果一个操作执行的结果需要对另一个操作可见，那么这两个操作之间必须要存在happens-before关系，在这个例子就是A操作的结果要对B操作可见，那么必然存在A happens-before B
简而言之：使用happens-before的概念来阐述操作之间的内存可见性

那在编程中有哪些情况符合这个happens-before规则呢？

  • 程序顺序规则： 一个线程中的每个操作，happens-before于该线程中的任意后续操作（也就是说你写的操作，如果是单线程执行，那么前面的操作就会happens-before于后面的操作）
  • 监视器锁规则： 对一个锁的解锁，happens-before 于随后对这个锁的加锁
  • volatile变量规则： 对一个 volatile域的写，happens-before于任意后续对这个volatile域的读
  • 传递性：如果 A happens-before B,且 B happens-before C,那么A happens-before C

synchronized-with

不同线程间，对于同一个原子操作，需要同步关系，store（）操作一定要先于 load（），也就是说 对于一个原子变量x，先写x，然后读x是一个同步的操作，读x并不会读取之前的值，而是当前写x的值

c++11三种内存模型

relaxed（松弛的内存序）

没有顺序一致性的要求，也就是说同一个线程的原子操作还是按照happens-before关系（同一个线程本来就有这个关系，这个关系并不代表优先执行，即happen－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
30
31
std::atomic<bool> x, y;
std::atomic<int> z;

void write_x_then_y()
{
    x.store(true, std::memory_order_relaxed); // 1
    y.store(true, std::memory_order_relaxed); // 2
}

void read_y_then_x()
{
    while (!y.load(std::memory_order_relaxed)) // 3
    {

    }
    if (x.load(std::memory_order_relaxed)) // 4
        ++z;
}

int _tmain(int argc, _TCHAR* argv[])
{
    x = false;
    y = false;
    z = 0;
    std::thread a(write_x_then_y);
    std::thread b(read_y_then_x);
    a.join();
    b.join();
    assert(z.load() != 0);
    return 0;
}

其中即使1先于2（同一个线程保证原子执行顺序）但是在不同线程间的执行顺序是没有约束的，所以#4也有可能是false。有可能1被交换到了2之后执行，也有可能1执行的结果缓存在了cpu cache中。

sequential_consistency（内存一致序）

查看std::atomic接口可以发现，几乎每个方法都有一个类型为memory_order的默认参数，默认值是std::memory_order_seq_cst，内存一致性是默认参数

这个是以牺牲优化效率，来保证指令的顺序一致执行，相当于不打开编译器优化指令，按照正常的指令序执行(happens-before)，多线程各原子操作也会Synchronized-with，（譬如atomic::load()需要等待atomic::store()写下元素才能读取，同步过程），当然这里还必须得保证一致性，读操作需要在“一个写操作对所有处理器可见”的时候才能读，适用于基于缓存的体系结构。

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
std::vector<int> data;
std::atomic<bool> data_ready(false);

void writer_thread()
{
    data.push_back(10); // #1：对data的写操作
    data_ready = true; // #2：对data_ready的写操作
}

void reader_thread()
{
    while (!data_ready.load()) // #3：对data_ready的读操作
    {

    }
    std::cout << "data is " << data[0] << "\n"; // #4：对data的读操作
}

int _tmain(int argc, _TCHAR* argv[])
{
    std::thread a(writer_thread);
    std::thread b(reader_thread);
    a.join();
    b.join();
    return 0;
}    std::atomic<bool> data_ready(false);

在同一个线程中，执行顺序，#1->#2 （原子操作），#3->#4（原子操作），指令序顺序执行，同时 保证Synchronized-with，#2->#3 必须要先store原子操作，然后在load原子操作。最终保证顺序一致性。

当然要保证这种严格的顺序一致性，需要牺牲优化代价
1、在无缓存的体系结构下实现SC

  • 带有读旁路的写缓冲(Write buffers with read bypassing)
  • 读操作可以不等待写操作，导致后续的读操作越过前面的写操作，违反程序次序
  • 重叠写(Overlapping writes)
  • 对于不同地址的多个写操作同时进行，导致后续的写操作越过前面的读操作，违反程序次序
  • 非阻塞读(Nonblocking reads)
  • 多个读操作同时进行，导致后续的读操作越过前面的读操作先执行，违反程序次序

2、 在有缓存的体系结构下实现SC,对于带有缓存的体系结构，这种数据的副本（缓存）的出现引入了三个额外的问题：

  • 缓存一致性协议(cache coherence protocols)
  • 一个写操作最终要对所有处理器可见
  • 对同一地址的写操作串行化
  • cache coherence的定义不能推出SC（不充分）：SC要求对所有地址的写操作串行化。因此我们并不用cache coherence定义SC, 它仅作为一种传递新值(newly written value)的机制。
    检查写完成(detecting write completion)

acquire-release（获取-释放一致性）

这个是对relaxed的加强，relax序由于无法限制多线程间的排序，所以引入synchronized-with，但并不一定意味着，统一的操作顺序

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 "stdafx.h"
#include <atomic>
#include <thread>
#include <assert.h>
#include <vector>
#include <iostream>

std::atomic<bool> x, y;
std::atomic<int> z;

void write_x_then_y()
{
    x.store(true, std::memory_order_relaxed); // 1 自旋，等待y被设置为true
    y.store(true, std::memory_order_release);  // 2
}

void read_y_then_x()
{
    while (!y.load(std::memory_order_acquire));  // 3
    if (x.load(std::memory_order_relaxed))  // 4
        ++z;
}

int _tmain(int argc, _TCHAR* argv[])
{
    x = false;
    y = false;
    z = 0;
    std::thread a(write_x_then_y);
    std::thread b(read_y_then_x);
    a.join();
    b.join();
    assert(z.load() != 0);  // 5
}

同一个线程 #1->#2， 由于acquire-release，#2->#3 ，又在同一个线程中，#3->#4，所以传递happens-before， #4一定能够获取#1的值，必然为true。
如果#3的while去掉，#3 可能由于#2还没有写入数据，导致为false， #4 和 #1 因为relaxed内存序，在不同线程，所以没有排序。release-acquire 对一般配对出现，如果都为release或者acquire，则无法同步。

参考https://blog.csdn.net/lvdan1/article/details/54098559/
https://github.com/brpc/brpc/blob/master/docs/cn/atomic_instructions.md