Home 浅谈 C++ 内存模型
Post
Cancel

浅谈 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

简单来说,以下条件全部符合则是 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 提供的值(因为 flagatomic,原子变量本身是可以看到自身的改动),那么就产生同步关系构成线程间的先行关系,即 xL1 < xL2 < yL1 < yL2。

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

acq-rel

*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,两个消费者 bca 处理好私有数据后通过 release 操作发布 queue_data,后续被 bc 不断消费。

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

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

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

  1. a 生产 queue_data,通过 release 发布出去。
  2. b 消费了一个 item_index
  3. c 消费了一个 item_index

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

而如果引入释放序列来修正获取释放模型,那么 c#2 读到的是以 a#1 为首的释放序列当中的任意值,因此仍然满足 acquire-release

RMW 操作即使是 relaxed 标记,也能形成释放序列。

操作 A 是 release 操作而不只是写操作,也就是要求写操作时施放 release 标记才行。

“读到对应的值”指的不仅是 release 操作写入的值,还包括以它为首的整个释放序列中的任意值。

如果该例子中只有一个消费者,那无需释放序列也能保证正确性。

References

C++ Concurrency in Action, 2nd
std::memory_order – cppreference
c++ - What does “release sequence” mean? – Stack Overflow
Release-acquire ordering: must load the value that was stored – cppreference
Concurrency: Algorithms and Theories – Hongjin Liang’s homepage

原文发布于 2023/02/02,全文重写于 2023/11/20。

This post is licensed under CC BY 4.0 by the author.
Contents