原子指令

了解 bRPC 原子指令。

我们知道，在多线程编程中广泛使用锁来避免修改共享数据时的竞态条件]。当锁成为瓶颈时，我们尝试通过使用原子指令来绕开它。但通常很难用原子指令写出正确的代码，甚至理解竞态条件、ABA 问题]和内存屏障]也很困难。本文试图介绍原子指令的基础知识（基于 SMP]）。由于 原子指令] 在 C++11 中被正式引入，我们直接使用其 API。

顾名思义，原子指令不可再分解为更小的子指令。例如，x.fetch(n) 原子地将 n 加到 x 上，其任何内部状态对软件而言都是不可观察的。常见的原子指令如下：

你已经可以用这些指令原子地进行计数，例如统计多个线程的操作次数。然而可能出现两个问题：

• 操作速度不如预期快。
• 即便对某些资源的多线程访问由若干个看似正确的原子指令控制，程序仍有很大概率崩溃。

缓存行

当没有竞争、或仅由单个线程访问时，原子指令是很快的。“竞争”发生在多个线程访问同一个 cacheline 时。现代 CPU 大量使用缓存，并将缓存划分为多个层级，以较低的成本获得高性能。百度广泛使用的 Intel E5-2620 拥有 32K 的 L1 数据缓存和指令缓存、256K 的 L2 缓存以及 15M 的 L3 缓存。L1 和 L2 缓存由每个核心各自拥有，而 L3 缓存由所有核心共享。虽然一个核心将自己的数据写入自身的 L1 缓存非常快（4 个周期，约 2ns），但让其他核心看到 L1 缓存中的数据却并非如此，因为数据所触及的 cacheline 需要同步到其他核心。这个过程是原子的，对软件是透明的，其间不能插入任何其他指令。应用程序必须等待 cache coherence 完成，这比写入本地缓存耗时长得多。它涉及复杂的硬件算法，并使得原子指令在高竞争下变慢。在 E5-2620 上，当少量线程对某条指令存在高度竞争时，单次 fetch_add 可能需要超过 700ns。对被多个线程频繁共享和修改的内存的访问通常都不快。例如，即使临界区看起来很小，保护它的自旋锁可能仍然表现不佳。原因在于自旋锁所使用的指令，如 exchange、fetch_add 等，需要等待最新的 cacheline。一两条指令耗时数微秒也就不足为奇了。

为了提升性能，我们需要避免频繁地同步 cacheline，这不仅会影响原子指令本身的性能，也会影响程序的整体性能。最有效的方案很直接：尽可能避免共享。

• 依赖全局多生产者-多消费者（MPMC）队列的程序很难在多 CPU 核心上良好扩展，因为该队列的吞吐量受限于 cache coherence 的延迟，而不是核心数量。更好的做法是改用多个 SPMC 或 MPSC 队列，甚至 SPSC 队列，从而从一开始就避免竞争。
• 另一个例子是计数器。如果所有线程都频繁修改同一个计数器，性能将会很差，因为所有核心都在忙于同步同一条 cacheline。如果计数器仅用于定期打印日志或类似的低优先级用途，我们可以让每个线程修改自己的线程本地变量，并在读取前汇总所有线程本地数据，这样可以得到 好得多的性能。

一个相关的编程陷阱是伪共享：由于同一缓存行中的其他变量被频繁更新，对很少更新甚至只读变量的访问会显著变慢。多线程环境中使用的变量应按访问频率或访问模式分组，被其他线程频繁修改的变量应放入独立的缓存行。要让变量或结构体按缓存行对齐，include <butil/macros.h> 并使用宏 BAIDU_CACHELINE_ALIGNMENT 标记它，可在 brpc 源码中 grep 查找示例。

内存屏障

仅有原子计数并不能同步对资源的访问，像 自旋锁 或 引用计数 这类看似正确的简单结构同样可能崩溃。关键在于指令重排序，它可能改变读写顺序；如果不存在依赖关系，后面的指令可能被重排到前面。编译器 和 CPU 都可能进行重排序。

其动机很自然：CPU 希望在每个时钟周期中填入指令，并在给定时间内执行尽可能多的指令。如上一节所述，一条加载内存的指令可能因为缓存行同步而耗费数百纳秒。同步多个缓存行的高效方案是同时移动它们，而不是逐个移动。因此，一个线程对多个变量的修改，可能以不同的顺序对另一个线程可见。另一方面，不同线程需要不同的数据，按需同步是合理的，这也可能改变缓存行之间的顺序。

例如：第一个变量起开关的作用，控制对后续变量的访问。当这些变量被同步到其他 CPU 核心时，新值可能以不同的顺序变为可见，第一个变量可能不是最先被更新的，这会导致其他线程认为后续变量仍然有效，而实际上并非如此，从而引发未定义行为。查看下面的代码片段：

// Thread 1
// ready was initialized to false
p.init();
ready = true;

// Thread2
if (ready) {
    p.bar();
}

从人类的角度来看，这段代码是正确的，因为 thread2 只在 ready 为真时才访问 p，这意味着 p 已经按照 thread1 中的逻辑完成了初始化。但是这段代码在多核机器上可能不会按预期运行：

• thread1 中的 p.init() 可能被编译器或 CPU 重排到 ready = true 之前，导致 thread2 在 ready 为真时看到未初始化的 p。thread2 中也可能发生同样的重排，即 p.bar() 中的某些指令可能在检查 ready 之前被重排执行。
• 即使上述重排没有发生，ready 和 p 的缓存行也可能独立地同步到 thread2 所在的 CPU 核心，导致 thread2 在 ready 为真时看到未初始化的 p。

注意：在 x86/x64 上，load 默认具有 acquire 语义，store 默认具有 release 语义，因此上述代码在关闭编译器重排的情况下可以正确运行。

通过这个简单的示例，你可以初步了解原子指令的复杂性。为了解决重排问题，CPU 和编译器提供了内存屏障](memory fences)，让程序员自行决定指令之间的可见性顺序。boost 和 C++11 将内存屏障归纳为以下类型：

上述示例可以修改为如下形式：

// Thread1
// ready was initialized to false
p.init();
ready.store(true, std::memory_order_release);

// Thread2
if (ready.load(std::memory_order_acquire)) {
    p.bar();
}

thread2 的 acquire 栅栏与 thread1 的 release 栅栏相匹配，因此当 thread2 看到 ready 被置为 true 时，它也能看到 thread1 中 release 栅栏之前的所有内存操作。

注意，内存栅栏并不保证可见性。即使 thread1 将 ready 置为 true 后 thread2 立即读取它，thread2 也未必能看到新值，因为缓存同步需要时间。内存栅栏保证的是可见性之间的顺序：“如果我看到了 a 的新值，那么我也应该看到 b 的新值”。

一个相关问题：如何知道某个值是否被更新过？一般有两种情况：

• 该值是特殊的。在上面的例子中，ready=true 是一个特殊值。一旦 ready 为 true，就说明 p 已就绪。读到该特殊值与否都代表特定含义。
• 只增不减的值。有些场景没有特殊值，可以使用 fetch_add 这类指令来递增变量。只要取值范围足够大，新值就会在很长一段时间内与旧值不同，从而可以将它们区分开来。

更多示例可以参见 boost.atomic。关于原子操作的官方说明可见此处。

无等待与无锁

原子指令提供两个重要特性：无等待 和 无锁。无等待是指无论操作系统如何调度，所有线程都在做有用的工作；无锁的语义比无等待弱，指无论操作系统如何调度，至少有一个线程在做有用的工作。如果使用锁，持有锁的线程可能被操作系统挂起，此时所有试图获取该锁的线程都会被阻塞。因此，使用锁的代码既不是无锁的，也不是无等待的。为了在给定时间内完成任务，实时操作系统中的关键路径至少要是无锁的。百度内部的各种线上服务对运行时间也有着严格限制。如果 brpc 中的关键路径是无等待或无锁的，许多服务都能从中获得更好、更稳定的服务质量。实际上，brpc 中的读（即均匀分发意义上的读）和写都是无等待的，详情参见 IO。

需要注意的是，人们通常认为无等待或无锁算法更快，但事实未必如此，因为：

• 无锁和无锁等待算法必须处理更复杂的竞态条件与 ABA 问题，这意味着代码通常比使用锁的实现复杂得多。代码越多，运行时间越长。
• 互斥量通过退避来解决争用，也就是说当争用发生时，会转入另一条分支以暂时避开争用。未能成功加锁的线程会被置入睡眠，使持有互斥量的线程独占地完成任务甚至后续任务，这反而可能提升整体吞吐量。

互斥锁导致的性能低下，要么是因为临界区过大（限制了并发度），要么是因为竞争过于激烈（上下文切换的开销成为主导因素）。无锁/免等待算法的真正价值在于它们保证了系统的持续前进，而非绝对的高性能。当然，无锁/免等待算法在某些情况下表现更好：如果一个算法只需一两条原子指令就能实现，那么它可能比需要更多原子指令总数的互斥锁实现更快。

最后修改于 2022 年 5 月 17 日：更新 brpc 用户页面（devlive-community/knowforge#71）(a31ce10d3)](https://github.com/apache/brpc-website/commit/a31ce10d3d732f29e56dd2c8c8a0d07c3e633209)