浅谈C++内存模型

前言

本文介绍简化的C++内存模型，涉及到memory order，modification order和release sequence等概念。虽然内容对于C++标准有所删减，但我希望相比C++标准和cppreference都更易于理解。

问题

先给出一个问题：如果有2个线程并发执行以下代码，结果是否正确（断言assert是否为真）？

int val;
bool flag {false};

void writer() {
    val = 1;
    flag = true;
}

void reader() {
    while(!flag);
    assert(val == 1);
}

上面的代码描述：writer线程写完val数据后设置flag表示操作已完成，reader等待flag设置后读取val数据。

虽然过程很直观，但是断言不一定为真：因为这些非原子的读写操作不满足强制的内存访问顺序。

语言标准是基于抽象机器去描述的，因此这里不必（也不应该）从具体的体系结构去分析原因。

而所需要的强制内存访问顺序在C++中需要2种关系去确认：

happens-before（先行关系）
synchronizes-with（同步关系）

先行关系

先行关系的概念用于确定操作之间的可见性（visible side effect）。如果说操作A先行于操作B，那么A对B可见。

这里的操作就是执行的语句，包括表达式求值和副作用。

而可见性能约束对非原子变量执行读操作时能读到的范围（reads-from）。

那么怎样才能得到先行关系？单线程下如果满足先序关系（sequenced-before）即可得到一种先行关系。而先序关系指的是程序顺序（program order）的前后顺序。比如有如下代码：

int x = 5; // L1
int y = 7; // L2

在程序顺序上，第一行代码（L1）早出现在第二行代码（L2）的前面，因此L1先行于L2。

但是此时只有先序关系并不能保证线程安全，因为先序关系只适用于单个线程，只提供了某种“偏序”。回到问题提到的代码里：

void writer() {
    val = 1;            // xL1
    flag = true;        // xL2
}

void reader() {
    while(!flag);       // yL1
    assert(val == 1);   // yL2
}

按照先行关系，显然xL1 < xL2，且yL1 < yL2。但是xL2和yL1的关系并没有确认，换句话说就是根本不能假定y能看到x操作产生的结果。

怎样才能描述线程安全？可惜C++标准中没有线程安全的定义。但可简单认为至少需保证免数据竞争（data-race-free）。

简单来说，以下条件全部符合则是data race：

有任意2个操作。
是对同一地址/对象的操作。
至少有一个写操作。
操作不在同一线程。
任意一边为非atomic操作。
双边不具有happens-before关系。

反过来，只需破坏以上任一条件就是data-race-free。你可以看到最后一个条件就是先行关系。

同步关系

为了解决线程间的先行关系，还需引入新的概念：同步关系。同步关系通过可传递性，从而构成线程间的先行关系（inter-thread happens-before）。

同步关系相比先行关系，性质比较特殊：

只作用于同一个原子变量的读写操作。
需要加上合适的标记，才允许读写操作之间产生同步关系。
不同的标记可提供不同强度的同步关系。

而上面提到的标记即是内存序（memory order），用于指定如何进行内存访问。

一般来说，内存序有三种标记提供给开发者使用：

relaxed
acq-rel
seq-cst

这种内存访问分类也是按照同步的强弱程度划分的：

不需要同步：relaxed宽松模型。
需要同步：acquire-release获取释放模型。
需要同步且要求全局顺序一致：sequential consistency顺序一致模型。

如果希望获取同步，则至少需要使用获取释放模型，且读操作获取（acquire）到写操作释放（release）的对应值，才能构成读操作与写操作之间的同步关系。

内存序需要完整标记，如果有一个writer thread的原子变量的写操作施放seq_cst而对应reader thread同一原子变量的读操作却只施放relaxed，那么在语言层面上并不提供同步和全局顺序一致性的保证。

内存序中还存在一种consume标记，但是redhat的某篇分享中提到consume实现上可能存在歧义（TL;DR: Don’t use memory_order_consume）。虽然C++20对此已经有所进展，但是本文仍不做讨论。

全局顺序一致指的是所有的线程能同一个顺序地观测到所有的改动，即只要某个线程观测到某个操作的结果，那么所有线程也都能观察到。大白话就是全局只有一种顺序。

现在把问题中的代码修改为atomic类型，来提供同步关系：

int val;
std::atomic<bool> flag {false};

void writer() {
    val = 1;                                        // xL1
    flag.store(true, std::memory_order_release);    // xL2
}

void reader() {
    while(!flag.load(std::memory_order_acquire));   // yL1
    assert(val == 1);                               // yL2
}

此时使用了获取释放模型来让xL2同步于yL1，只要yL1读到xL2提供的值（因为flag是atomic，原子变量本身是可以看到自身的改动），那么就产生同步关系构成线程间的先行关系，即xL1 < xL2 < yL1 < yL2。

简单来说，通过synchronizes-with和happens-before的可传递性，即可保证线程安全。

*po = program order
*sw = synchronizes-with

为什么不把同步关系等同视为线程间先行关系？这说的好像同一回事啊——那当然是概念上有简化，比如inter-thread happens-before还可以通过dependency-ordered before来构成，需要更深入的了解可以翻文档。

在cppreference描述中，先行关系满足两者之一即可构成，一是sequenced-before，二是inter-thread happens-before。

补充一点内存序与可见性的联系。这章节总结得出内存序通过同步关系构成了先行关系，而前面提到先行关系可以提供可见性，这是怎样关联的？其实有2条规则：

Every write action that happens-before the read with no intervening write is a visible side effect.
Non-atomic actions must read-from visible side effect.

改动序列

前面提到，原子变量本身可以看到自身的改动，这涉及到改动序列（modification order）。

可以认为，每个原子变量都维护一个全局（所有线程可见）的改动序列，其序列中的每一个值由写操作提供，而读操作则读入改动序列中的某一个值。

严格来说这里又得引入读写连贯性（read-write coherence）的概念，但这里简化一些，知道一些感性的规则即可：

序列中的每个值由写操作提供。
序列中的第一个值就是原子变量初始化时提供的值。
如果某线程的读操作得到某个值v，那么这个线程此后读的结果要么是v，要么是序列中比v更靠后（更新）的值，这个线程后续的写操作提供的值也会append到序列的后方。
如果某线程进行写操作后接着读操作，那么该线程读操作得到的值要么是刚才最后一次写操作的结果v，要么是序列中比v更新的值。

因此，你可以得知atomic::load()函数就是获取改动序列某个下标的值：这个序列在所有线程中都长一样且同步更新，但是每个线程私有的访问下标却不一样，但不管怎样，每个线程的下标都是单调递增地变动。也就是说原子读操作可能读到“旧值”，但肯定不是“脏值”。

另外，RMW操作（read-modify-write，比如atomic::exchange()函数）总是能读到改动序列中最新的值。

释放序列

当一个原子变量执行了release操作（记为A），此后任意线程对该原子变量的RMW操作所形成的最长子序列就称为——以A为首的释放序列（release sequence）。

这个概念有什么用？其实是用于补全释放获取模型的完整性，使得代码符合开发者直觉。在释放获取模型中，直接的理解就是：标记acquire的读操作能看到release前的所有操作（只要能读到对应的值）。但加上释放序列的概念后还可以如此补充：标记acquire的读操作能看到释放序列前的所有操作（只要能读到对应的值）。

可以看如下的生产者-消费者例子，如果缺少释放序列，那么这段代码可能是错误的：

#include <atomic>
#include <thread>
#include <vector>
#include <iostream>
#include <mutex>
std::vector<int> queue_data;
std::atomic<int> count;
std::mutex m;

void process(int i) {
    std::lock_guard<std::mutex> lock(m);
    std::cout << "id " << std::this_thread::get_id() << ": " << i << std::endl;
}

void populate_queue() {
    unsigned const number_of_items = 20;
    queue_data.clear();
    for (unsigned i = 0;i<number_of_items;++i) {
        queue_data.push_back(i);
    }
    count.store(number_of_items, std::memory_order_release); //#1 The initial store
}

void consume_queue_items() {
    while (true) {
        int item_index;
        if ((item_index = count.fetch_sub(1, std::memory_order_acquire)) <= 0) { //#2 RMW
            std::this_thread::sleep_for(std::chrono::milliseconds(500)); //#3
            continue;
        }
        process(queue_data[item_index - 1]); //#4 Reading queue_data is safe
    }
}

int main() {
    std::thread a(populate_queue);
    std::thread b(consume_queue_items);
    std::thread c(consume_queue_items);
    a.join();
    b.join();
    c.join();
}

这段代码中有一个生产者a，两个消费者b和c。a处理好私有数据后通过release操作发布queue_data，后续被b和c不断消费。

这段代码是符合开发者直觉的，但是如果没有释放序列的话，虽然有以下的同步关系：

a#1 < b#2
a#1 < c#2

但是注意如果线程是按照这样的顺序执行：

a生产queue_data，通过release发布出去。
b消费了一个item_index。
c消费了一个item_index。

这里由于步骤2的操作是RMW，改动了atomic类型count的值，那么步骤3的操作并没有与步骤1构成同步关系，此时c接着读入queue_data就是一个未定义行为（因为此时count已经不是由a#1通过release标记写入的值，c#2中acquire标记已经无济于事，所以queue_data也未发布给c）。