haohaolee's blog

nerd以上，geek未满

C++2011 Memory Model 笔记

C++0x 的内存模型怕是 0x 里面最难啃的骨头之一了吧，至少相对于那些语法糖的增加来说。每次回来看都有些新的收获，这里做个记录。没有系统地总结，尽量给出处吧。标准参考的是 n3291，和 FDIS 是一样的。

Memory ordering

C++ 的内存模型有3种 Memory Ordering

  1. sequential-consistent ordering

  2. acquire-release ordering

  3. relaxed ordering

标准中对 atomic type 的 order 定义如下(29.3)：

1
2
3
4
5
6
7
8
9
10

    namespace std {
     typedef enum memory_order {
       memory_order_relaxed, // relaxed ordering
       memory_order_consume, // acquire-release ordering (acquire part)
       memory_order_acquire, // acquire-release ordering (acquire part)
       memory_order_release, // acquire-release ordering (release part)
       memory_order_acq_rel, // acquire-release ordering (both)
       memory_order_seq_cst  // sequential-consistent ordering
     } memory_order;
    }

默认是 memory_order_seq_cst，也就是 sequential-consistent，注意这里说的都是针对 atomic types。因为 C++ 标准不允许 non-atomic 的 data race，包含 data race 的程序视为 undefined behavior(1.10-21)。所以解决潜在的 data race 必须依赖 locks 以及 atomic operation。再强调一下，C++11 中凡是非 atomic type 的 data race 都是未定义行为，程序不可移植，等价于错误的程序。lock 这里不谈，因为使用上是符合直觉以及传统的，目的就是保护好 shared 对象，防止 data race。

Seqential Consistent Ordering

默认的 sequential-consistent model 是沿袭 Java 的内存模型(确切的说是 sequential-consistent with data-race-free)，所有的 atomic 操作都可以看作满足唯一 total order 的操作，也就是说，可以把这样的多线程程序理解成一个有先有后交叉运行的单线程程序(对atomic type而言)，这在推理时是有帮助的。每个 shared atomic 对象的改变在每个线程看来都是一样的，包括时间顺序以及值。这样一个默认的模型是相对来说符合直觉和容易处理的。举一个 Double-checked locking 的例子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

    class singleton
    {
        mutable std::mutex m;
        mutable std::atomic<expensive_data *> data;

    public:
    // initialize data to 0 in constructor
    //.....
        const expensive_data* get_instance() const
        {
            expensive_data* result = data.load();
            if(!result)
            {
                std::lock_guard<std::mutex> lk(m);
                result = data.load();
                if(!result)
                {
                    result = new expensive_data;
                    data.store(result);
                }
            }
            return result;
        }
    };

这里的 load 和 store 默认参数都是memory_order_seq_cst, 等价于调用 data.load(std::memory_order_seq_cst) 和 data.store(result, std::memory_order_seq_cst)。

  1. shared data 要么在 mutex 内部，要么必须是 atomic type

  2. 这个正确实现是符合直觉的，而且它和其它平台(比如 Java)的实现几乎是一样的。只要不考虑其它的 ordering，正确性相对容易保证。

结论：默认的 sequential consistent 语义虽然相对保守，但是容易写出正确的程序，这也是推荐的处理方式。不到万不得已(性能不可接受)，不要使用其它语义，即上面提到的另外两种 ordering

Relaxed Memory Ordering

一旦进入剩下两种 ordering 的世界，程序的编写就得格外小心——因为它处处违反直觉。举标准一例：

1
2
3
4
5
6
7
8

    // Thread 1:
    r1 = y.load(memory_order_relaxed);
    x.store(r1, memory_order_relaxed);


    // Thread 2:
    r2 = x.load(memory_order_relaxed);
    y.store(42, memory_order_relaxed);

x,y 初始值为0，该程序结果不唯一，这是显而易见的。但是 r1 == r2 == 42 也是一个正确的结果，是不是很违反直觉？要产生这个结果，那么实际顺序必须是：

1
2
3
4

    y.store(42, memory_order_relaxed);
    r1 = y.load(memory_order_relaxed);
    x.store(r1, memory_order_relaxed);
    r2 = x.load(memory_order_relaxed);

  1. 对于 thread 1 而言，thread 2 的执行不是顺序的(所谓的 program order)

  2. 整体顺序完全不确定，这4条指令完全可以以任意顺序排列(实际执行也许根本不是 sequential 的)

relaxed ordering 是最松散的一种语义：

  • 完全不参与多线程间的同步，编译器可以随便优化

  • 对于自身线程，data-dependency 产生的依赖需要满足，这是单线程程序正确性的要求

  • 此外它唯一的作用就是属于原子操作，所以不会产生 data race

Acquire-Release Ordering

该语义即同步语义，每一个 acquire 对应一个 release(跨线程的)，详细定义参见标准(29.3-2)。需要注意的是 C++ 的同步语义不是先验的，我们无法通过之前的执行判断之后两个操作是否同步了，而只能通过推理所有的情况来验证程序的正确性。具体来说，对于一个可能的 acquire-release pair，我必须考虑他们同步时的情况，也需要考虑他们没有同步时的情况。推理 C++ 多线程程序的正确性，特别是在这两种 ordering 情况下，需要塑模 happens-before 的关系(标准1.10-12)，通俗点说，就是推理出相关操作之间所有可能发生的顺序(或者根本就无序)。所以说带锁的多线程的程序很难写正确，更别说无锁的，可见一斑。 举例：

1
2
3
4
5
6
7
8
9
10
11

    // x0, x1 is atomic bool and initialized to false
    // victim is atomic int and initialized to 0
    // Thread 0
    x0.store(true, memory_order_relaxed);
    r0 = victim.exchange(0, memory_order_acq_rel);
    r1 = x1.load(memory_order_acquire);

    // Thread 1
    x1.store(true, memory_order_relaxed);
    r2 = victim.exchange(1, memory_order_acq_rel);
    r3 = x0.load(memory_order_acquire);

如何分析线程间可能的同步状态？因为 acquire 要和 release 对应，而两个线程中唯一可能同步的就是 victim 变量了，因为它的 exchange(即 read-modify-write 操作) 是 memory_order_acq_req，先读后写，读时 acquire，写时 release。这里先总结相关要点：

  1. 当一个 atomic 对象的 acquire 同步 release 时(不同线程)，acquire 读到的值不一定是 release 上次写的值(不保证cache-coherence)，也可能是之前该 atomic 对象的值。准确的说，对于一个 atomic 对象，它存在唯一一个 modification order，即该对象从诞生以来被修改的顺序，可以想成一个 list {init, x1, x2, x3, …}。而 acquire 读到的值可以是从上次读取到最近修改中间任意一个(包括上次读取的值)。假如 acquire 这次读到一个值 x1，那么下次 acquire 就可能读到 x1, x2, x3 等等，但是不可能读到 init 了。

  2. read-modify-write 操作含有特殊的语义，它每次都可以读到该 atomic 变量的最新的值。所以当该类操作同步时，读到的都是 modification order 最后的值。

    • 如果线程0中的 victim 读到 1，即 r0 返回 1，说明和线程1的 victim 写入同步，我们可以推理如下，按时间顺序:

      1. 线程1中 “x1 置为 true” happens before “victim 置为 1”，这是 program order 保证的

      2. 线程1中 “victim 置为 1” happens before 线程0 “victim exchange”，这是同步

      3. 线程0中 “victim 读到 1，然后置为 0” happens before “x1 load”

    所以结论是 r1 == true r2 == 1，而 r3 未知，可以是 true，也可以是初始值 false，因为他们没有同步关系。

    • 如果线程0中的 victim 读到 0，即 r0 返回 1，那么 victim 读取的是初始值 0，那么反过来线程1的 victim 就会读到线程0 的 victim 值了：

      1. 线程0中 “x0 置为 true” happens before “victim 置为 0”

      2. 线程0中 “victim 置为 0” happens before 线程1中 “victim exchange”

      3. 线程1中 “victim 读到 0，然后置为 1” happens before “x0 load”

    所以结论是 r3 == true r2 == 0，r1 是不确定的。

这里只有两个线程，同时各执行一次，atomic 修改的次数也不多。所以推理起来尚属容易。

Peterson’s lock

最后以一个 Peterson’s lock 为例结束本文。该例是从 这篇blog 抄来的。

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

    std::atomic<int> flag0(0),flag1(0),turn(0);

    void lock(unsigned index)
    {
        if (0 == index)
        {
            flag0.store(1, std::memory_order_relaxed);
            turn.exchange(1, std::memory_order_acq_rel);

            while (flag1.load(std::memory_order_acquire)
                && 1 == turn.load(std::memory_order_relaxed))
                std::this_thread::yield();
        }
        else
        {
            flag1.store(1, std::memory_order_relaxed);
            turn.exchange(0, std::memory_order_acq_rel);

            while (flag0.load(std::memory_order_acquire)
                && 0 == turn.load(std::memory_order_relaxed))
                std::this_thread::yield();
        }
    }

    void unlock(unsigned index)
    {
        if (0 == index)
        {
            flag0.store(0, std::memory_order_release);
        }
        else
        {
            flag1.store(0, std::memory_order_release);
        }
    }

Peterson lock 是最简单的锁实现之一，它只提供两个线程之间的锁同步。该实现为了追求性能，采用了更弱的 ordering，所以这意味着正确性需要严格的证明。这里只总结一下要点：

  1. 代码并非处处使用 acquire-release 同步，也有使用 relaxed ordering 的地方，但是正确性需要严格证明

  2. 正确的关键在 turn.exchange 的使用和处理，exchange 保证了读取的值是最近修改的，而 memory_order_acq_rel 则保证了同步，从而使得跨线程的 happens-before 关系正确建立，并且 while 循环里 turn 和 flag 可以读到最新的值

完整的证明可以参考出处。

值得一提的是，如果采用 sequential-consistent ordering —— flag 和 turn 都用 memory_order_seq_cst 的话 —— 立刻就得到一个正确的实现，这也是目前大多数 peterson lock 的实现。基于 sequential-consistent 的 peterson lock 证明也更容易，可以参考 The Art of Multiprocessor Programming 第二章。

本文参考:

  1. C++ atomics and memory ordering

  2. The Inscrutable C++ Memory Model

  3. Peterson’s lock with C++0x atomics

  4. n3291

  5. 为什么程序员需要关心顺序一致性（Sequential Consistency）而不是Cache一致性（Cache Coherence？）

Posted via UltraBlog.vim.

Comments