C++系列

Some Multi Thread

Edimetia3D

Edimetia3D

— 7 min read

背景

早在单核时代，为了充分利用硬件的多发射和乱序执行能力，编译器就可能在编译期调整指令顺序。编译器重排与硬件乱序执行叠加后，硬件的实际执行顺序可能与源代码中的顺序存在偏差。不过，这些调整都遵循一个基本原则：从单线程的可观察行为来看，最终执行效果应当与顺序执行一致。

例如，对于下面的代码，如果两次写入之间不存在依赖关系，那么无论先写入 a 还是先写入 b，都不应影响后续指令的正确性。

a = 8;
b = 9;

进入并发环境后，上述原则可以描述为：从线程自身来看，线程内代码的执行效果与顺序执行一致。编译器和硬件的优化都需要遵循这一原则，但这也从另一个角度说明：不同线程观察到的执行效果可能并不一致。

下面是一个经典示例。按照通常的直觉，我们可能认为：如果 R0 == 0，那么 Thread 0 应当已经执行完毕，而 Thread 1 还没有开始执行，因此 R1 一定等于 1。然而，在特定环境中，R0 == 0 且 R1 == 0 的结果也可能出现。如果程序逻辑依赖“这两个值不可能同时为 0”的假设，就可能产生错误。

std::atomic<int> A{0}, B{0};
int R0, R1;

// Thread 0
A.store(1, std::memory_order_relaxed);
R0 = B.load(std::memory_order_relaxed);

// Thread 1
B.store(2, std::memory_order_relaxed);
R1 = A.load(std::memory_order_relaxed);

为了避免此类错误，我们需要了解 Memory Model（内存模型）。它是一组针对多线程环境下内存相关操作的定义与约束，例如如何描述内存操作的影响，以及这些操作的可观测性和原子性。其中比较重要的有：

  • Atomicity（原子性）：一次内存访问是否不可分割？多条指令能否构成一个原子操作？
  • Coherence（一致性）：不同线程如何观察同一内存位置上的修改？
  • Ordering（内存排序）：Load/Store 是否可能相对于彼此重排序？每个核心观察到的 Load/Store 需要符合哪些规律？
  • 哪些硬件指令会影响上述三个方面的行为？

C++ 定义的 Memory Model 引入了 sequenced-before、happens-before、synchronizes-with、release、acquire、relaxed 等大量抽象概念，心智负担较重。

在一般开发中，建议优先使用 mutex 和默认内存序（seq_cst）的 atomic。在场景明确时，也可以使用 relaxed，但应尽量避免自行管理复杂的内存排序关系。

在对性能要求极高时，也可以参考对应硬件的手册。直接理解硬件指令的心智负担有时反而更小，因为硬件提供的指令通常更少，语义也更具体，理解起来可能更直接。

In Action

至此，我们已经介绍了足够多的基础概念。接下来看看它们可以解决哪些问题。

Lock-free（Lockless）

如果一个系统不会因为某个线程停止执行而永久卡死，其他线程仍然能够持续取得进展，那么这个系统就可以称为 lock-free。

Lock-free 是系统级的进展保证，只要求整个系统持续取得进展。更强的约束是 wait-free，它要求每个线程的操作都能在有限步骤内完成。一般而言，为了满足 wait-free 的要求，需要设计相当复杂的代码逻辑，因此采用这一约束的实现相对较少。

假设存在一个外部攻击者，通过某种手段让一个线程在获得 mutex 后永久阻塞，那么其他线程就再也无法获得这把锁，整个系统也可能永久卡住。这说明，使用 mutex 的算法并不具备 lock-free 属性。

另一方面，即使使用原子操作，如果代码逻辑不够严谨，也可能导致系统永久卡死，此时系统同样不能称为 lock-free。

此外，lock-free 实现经常需要使用 CAS loop。如果对CAS Loop的应用不够严谨，可能退化为类似 spin lock 的形式，相当于自己实现了一把 mutex，意义并不大。

你真的需要使用 lock-free 吗？可以先阅读 An Introduction to Lock-Free Programming 和 Locks Aren't Slow; Lock Contention Is。

Gossip of Mutex

“mutex 性能很差”的印象，在一定程度上是历史原因造成的。过去的部分 mutex 实现属于重量级的 kernel-space mutex，加锁可能需要进入内核，因此开销较大。

如今的 mutex 通常只有在 lock 竞争失败时，才可能需要系统调用。在锁竞争较弱时，系统调用的频率应当很低。例如，在理想情况下，一个线程可以直接在 user space 完成加锁，无须调用 wait；后续释放锁时，如果没有等待者，也无须调用 wake。因此，大部分操作可以完全不涉及系统调用。详情可参考 Futex 介绍。

参考相关 benchmark 后，一般可以认为：当 lock contention 不强烈时，mutex 实际上是一种性能良好且易于使用的工具。

Others

ABA

如果一个值从 A 变为 B，又从 B 变回 A，那么它究竟有没有发生过变化？在 lock-free 编程中，这类问题很容易出现，需要通过正确的算法设计加以处理。

Use CAS to Implement Any Atomic Operation

参考：You Can Do Any Kind of Atomic Read-Modify-Write Operation。

DCLP

Double-Checked Locking Pattern（DCLP）是一个经典问题，互联网上已有很多讨论。

不过，我们先讨论另一个重要特性：C++11 之后，局部 static 对象的初始化是线程安全的，并且能够保证正确的同步关系。下面的代码展示了这一特性。

MyType* Instance() {
    static MyType obj;
    return &obj;
}

上述代码是 C++11 之后实现单例模式的标准做法。巧合的是，大多数编译器正是通过类似 DCLP 的策略，来兼顾这段代码的线程安全性与性能。

下面以单例模式为例，介绍 DCLP 的逻辑。

std::atomic<Singleton*> Singleton::m_instance;

Singleton* Singleton::getInstance() {
    Singleton* tmp = m_instance;
    if (tmp == NULL) {
        Lock lock;
        tmp = m_instance;
        if (tmp == NULL) {
            tmp = new Singleton;
            m_instance = tmp;
        }
    }
    return tmp;
}

上面的代码使用默认的 seq_cst 内存序。在 C++ 内存模型下，这可能带来一些额外的性能开销。下面这个 DCLP 版本使用更精确的内存序来描述实际需要的约束：

std::atomic<Singleton*> Singleton::m_instance;
std::mutex Singleton::m_mutex;

Singleton* Singleton::getInstance() {
    Singleton* tmp = m_instance.load(std::memory_order_relaxed);
    std::atomic_thread_fence(std::memory_order_acquire);
    if (tmp == nullptr) {
        std::lock_guard<std::mutex> lock(m_mutex);
        tmp = m_instance.load(std::memory_order_relaxed);
        if (tmp == nullptr) {
            tmp = new Singleton;
            std::atomic_thread_fence(std::memory_order_release);
            m_instance.store(tmp, std::memory_order_relaxed);
        }
    }
    return tmp;
}

Barrier（Latch）

Barrier 用于确保 K 个线程都能到达某个同步点，这在并行计算中很常见（例如 CUDA 的 __syncthreads()）。C++20 提供了标准的 std::barrier 来实现这一功能，std::latch 也能实现类似的一次性同步功能。

经验谈

  • 使用的工具越高级，将来引入的 bug 就可能越复杂。
    • 例如，应当优先使用标准库的 atomic，而不应当自行编写 lock-free 代码。
  • std::mutex 的 lock/unlock 应尽量通过 std::unique_lock、std::lock_guard 等工具管理。
  • 为了避免不必要的麻烦，尽可能不要在多线程环境中使用 fork 和 signal。
  • 为了避免麻烦，尽量通过正常的函数返回来结束线程。

Read more

Coroutine

从一般概念上说, 协程是特殊的函数调用: 被调用的函数可以在可控的位置被中断，然后在下一次调用时，继续从上次中断的位置继续执行。 本文主要通过Python的协程来介绍协程, 这是我唯一熟悉的一种协程实现. Classic Coroutine 下面的python代码很好的说明了协程的核心功能 def co_routine(): recv0 = yield 996 # hangs here after first coro.send assert recv0 == "Second" yield 711 # hangs here after second coro.send return def main(): coro = co_routine() # Create a new coroutine object value = coro.send(None)

By Edimetia3D

GDB with Python

这篇文章的主要应用场景是调试Python的C/C++ Extension 1. 同时使用pdb / gdb 进行调试. 通俗点说, 既可以break在 .py 文件中,也可以break在 .cc 文件中 2. 在gdb中不但可以获得常规的调试信息, 还可以获得python VM 的调试信息, 例如获得python的调用栈, 访问Python局部变量等. 这将会在调试exception时(如Segmentfalut)非常有用, 这种场景下, 定位 Python VM 正运行到哪一行代码往往可以提供一些直观的重要信息. 第一步: 编译源码以获得一些辅助数据. 我们并不真的需要使用从源码编译的Python, 但是一些调试相关的辅助文件需要从源码中获得, 包括 python-gdb.py及debug symbol等. 在 https://www.python.org/ftp/python/ 或 https://github.com/python/cpython

By Edimetia3D

Bazel Notes

这是一篇2019年左右的记录, 内容可能过时, 也不太全面 杂谈 Bazel是Google为Monorepo服务而开发的构建工具. 首先是巨大,当问题的规模变大,事情总是会变得更复杂. 而Google面对的"巨大Monorepo",应该是世间罕有的. 然后是Monorepo,这极大的影响了代码的组织风格.例如,你要写一个操作系统内核ProjectOS,还要写一个游戏ProjectGame.在传统的开发习惯中,这两个项目会组织到两个不同的Repo里,PorjectOS和ProjectGame之间无法直接相互引用,例如,你在ProjectOS里写了一个高级的数据结构,想要在Game里也使用,要么直接复制粘贴,要么是创建一个新的CommonRepo,把可公用的代码都放在Common里,然后两个项目各自引入Common作为依赖. 使用MonoRepo则不存在这个问题,Game可以直接依赖OS内的组件,按照Bazel的语法描述,就是在Game中可以直接使用@ProjectOS//path/to/package:AdvancedStruct.当然,你仍然可以选择重构一

By Edimetia3D