理解原子操作和内存排序

共享内存

原子

重新排序

发布和获取

顺序一致性

弱排序

硬件怪癖

结论

原子操作和内存顺序总是让人感觉难以理解。在众多拙劣的解释中，我想补充一点，阐述一下我对这其中缘由的理解。这只是我个人的理解，如果您需要更完善、更正式的解释，我建议您阅读您所用编程语言的内存模型文档。就本文而言，应该是cppreference.com上描述的 C11 内存模型。

共享内存

在单线程代码执行方面，软件和硬件的性能正逐渐接近极限。为了持续提升计算性能，一种常见的解决方案是引入多个单线程执行单元——即多线程。这种计算方式体现在不同的抽象层面上，从单个CPU的多个核心到同一台机器上的多个CPU，甚至跨越网络的多台机器。本文将重点关注CPU的核心，并将其称为“线程”。

对于某些工作负载，任务可以清晰地划分并分配给不同的线程执行。这类任务被称为“极易并行”任务，彼此之间无需通信。这正是多线程算法应该努力达到的理想状态，因为它充分利用了单线程执行中所有现有的优化手段。然而，这种情况并非总是可行，有时任务之间需要通信和协调，这就是我们需要在线程间共享内存的原因。

当代码运行在抢占式调度环境下时，通信会变得十分困难。在这种环境下，你的代码随时可能被中断，以便其他代码运行。在应用程序中，操作系统内核可以决定从运行你的程序切换到运行另一个程序。在内核中，硬件也可以从运行内核代码切换到运行中断处理程序代码。这种任务切换被称为并发，为了实现同步/通信，我们需要一种方法在短时间内排除这种并发，否则我们可能会面临数据不完整或不完整的风险。

原子

幸运的是，CPU 为软件提供了特殊的指令，用于操作不可中断的共享内存。这些操作被称为原子内存操作，分为三类：加载 (Load)、存储 (Store) 和读修改写 (ReadModifyWrites，简称 RMW)。前两类操作顾名思义。RMW 也非常形象：它允许你从内存加载数据，对数据进行操作，然后将结果写回内存——所有操作都是原子性的。你可能听说过原子增量(atomic increment) 、原子交换 ( atomic swap ) 或原子比较并交换 (compare and swap)等 RMW 操作。

所谓“原子性”操作，是指某项操作必须完整地发生（或被观察到发生），否则就根本不会发生。这意味着它不能被中断。当某项操作是“原子性”的，那么操作的撕裂（即部分完成）是无法观察到的。原子操作使我们能够编写能够安全地处理共享内存的代码，从而避免并发中断。

原子操作的另一个特点是，当共享内存至少有一个写入者，并且可能存在多个读写者时，原子操作是与共享内存交互的唯一可靠（即定义正确）的方式。尝试不使用原子操作进行此类交互会被视为数据竞争，而数据竞争属于未定义行为（UB）。未定义行为是指依赖于目标程序模型（在本例中为 C11 内存模型）之外的假设。这样做是不可靠的，因为编译器或 CPU 可以执行其模型之外的任何操作。

数据竞争及其隐含的未定义行为并非仅仅是一个理论问题。我之前提到的单线程优化之一就涉及 CPU 或编译器对内存读写操作进行缓存。如果不使用原子操作，操作本身可能会被省略并替换为缓存结果，这很容易破坏代码的逻辑：

# should be an atomic_load() but its data race
while (not load(bool)):
    continue

# a potential single-threaded optimization
cached = load(bool)
while (not cached): # possibly infinite loop!
    continue

重新排序

原子操作仅能解决对原子访问内存的通信问题；但并非所有需要通信的内存都能被原子访问。CPU 通常只对几字节大小的内存进行原子操作。如果要进行其他类型的通用内存通信，我们需要找到一种方法，让线程能够通过其他方式访问这些内存。

将内存分配给其他线程实际上比听起来要复杂得多。让我们来看一个代码示例：

data = None
has_data = False

# Thread 1
write(&data, "hello")
atomic_store(&has_data, True)

# Thread 2
if atomic_load(&has_data):
    d = read(&data)
    assert(d == "hello")

乍一看，这似乎可行。即使每个线程在每条指令（此处为代码行）之间都被抢占，assert() 断言也应该总是成功。但根据我的描述，你可能已经意识到这个 assert() 断言实际上可能会失败！原因在于另一种单线程优化——重排序。

硬件（CPU）或软件（包括编译器）可以随意移动（即“重新排序”）你的代码和指令，只要最终结果与源代码的意图一致即可。这种“指令调度”的自由度使得各种优化成为可能。

重排序的一个例子是通过推测执行。在这种情况下，CPU 会开始执行尚未执行到的代码，寄希望于当最终执行到该代码时，结果已经准备就绪。这是一种惊人的单线程吞吐量优化，但也意味着 `a`atomic_store()可能在 `b` 之前启动write()，或者 `b`read()可能在 `c` 之前启动atomic_load()；这两种情况都可能导致 `assert()` 失败。

重排序的另一个例子是 CPU 缓存。CPU 不会直接读写共享内存，因为速度相对较慢。相反，每个 CPU 核心都有自己的快速访问本地内存，称为缓存。大多数内存操作都在 CPU 的缓存上执行，最终通过称为缓存一致性的过程，将数据刷新到其他缓存或从其他缓存刷新。在我们的示例中，数据atomic_store()可能在缓存刷新到共享内存之前就已经刷新到缓存write()（例如，如果刷新是后进先出 (LIFO) 的），或者数据atomic_load()可能在缓存刷新之前就已经刷新到缓存read()；这两种情况都可能导致 assert() 语句失败。

编译器可以重新排列指令，但只能重新排列那些没有依赖关系的指令。如果一条指令（一行代码）使用了前一条指令的结果，或者前一条指令是其副作用，则称该指令“依赖于”前一条指令。编译器可以自由地重新排列依赖关系之前的指令，但不能重新排列依赖关系之后的指令。这意味着a = 5; b = 10;可以重新排列指令，b = 10; a = 5;使其语义保持不变（实现相同的目标），因为“a”和“b”之间没有依赖关系。如果改为，a = 5; b = a + 1;则不能将“a”移动到“b”之后，因为这在逻辑上没有意义，因为“b”依赖于“a”。在我们的示例中，指令atomic_store()不依赖于write()，因此可以随意移动，但这可能会导致 `assert()` 语句失败。

至此，指令重排序确实存在，并且在操作共享内存时必须注意这一点。问题在于，原子操作本身并不能防止指令重排序。我们需要为原子操作引入一个额外的概念来解决这个问题。在 C11 中，原子操作接受一个名为“内存排序”的参数，这有助于解决这个问题。

在之前的代码示例中，存在两个主要问题：一是内存重排序，二是内存可见性。内存排序通过防止代码围绕原子操作进行重排序来解决这些问题，并确保某些数据或操作变得可见，或者在概念上从缓存中“刷新/重新加载”。让我们看看具体效果。

发布和获取

我们暂且引入两种内存排序方式：获取（Acquire）和释放（Release）。释放用于原子存储操作，确保所有在其之前声明的内存操作都会在其之前执行。获取用于原子加载操作，确保所有在其之后声明的内存操作都会在其之后执行。这样就解决了重排序问题。

然后我们声明另一个约束：所有在给定 Release 操作之前发生的内存操作，都必须在与之匹配的 Acquire 操作之前git push执行。你可以将其理解为从 Release 操作变得可见，到 Acquire 操作执行某种形式的“获取”操作之间的变化git pull。这样就解决了可见性问题。

让我们把这些添加到代码示例中：

data = None
has_data = False

# Thread 1
write(&data, "hello")
atomic_store(&has_data, True, Release)

# Thread 2
if atomic_load(&has_data, Acquire):
    d = read(&data)
    assert(d == "hello")

请注意，Release 和 Acquire 不会对数据就绪进行任何“等待”或“阻塞”。它们并非现有同步原语的替代品。相反，它们确保如果atomic_load() 的has_data值为 True，那么由于 Acquire 和 Release 屏障的匹配，也保证数据已准备就绪write(&data, "hello")，因此我们的断言永远不会失败。

对于 ReadModifyWrite (RMW) 原子指令，它们还可以接受一个名为 `Acquire` 的内存顺序AcqRel。鉴于 RMW 操作在概念上同时执行原子加载和原子存储，AcqRel`Acquire` 会分别使这两个操作执行原子获取和原子释放操作。这在需要执行一个原子操作时非常有用，该操作既能 1) 通过 `Release` 将内存释放给其他线程，又能 2) 通过 `Acquire` 接收其他线程释放的内存。

栅栏和变量

你会注意到我一直在说“匹配获取/释放”。在我们的示例中，匹配指的是使用同一个“原子变量”进行加载和存储操作&has_data。对不同原子变量执行的释放和获取操作不会同步，必须是同一个原子变量。

规则有一个例外，那就是内存栅栏。内存栅栏是一种建立普通内存操作和原子内存操作的内存顺序的方法，而无需与特定的内存操作关联。

栅栏对我来说有点棘手，因为我很难描述它们，但它们本质上是创建了事件发生之前的关系，以与所使用的内存顺序相对应的方式将原子操作包围起来：

• Afence(Release)与另一个建立了一种“先于”关系。fence(Acquire)
• fence(Release)如果后续的非 Release 原子存储具有匹配的 Acquire 原子加载或匹配的 Acquire 原子加载，则A会将它们转换为 Release 原子存储。fence(Acquire)
• fence(Acquire)如果先前的非 Acquire 原子加载有匹配的 Release 原子存储或匹配的 Release 原子存储，则A会将它们转换为 Acquire 原子加载fence(Release)。

以下是一个如何用内存屏障代替每次操作的内存排序的示例：

data = None
has_data = False

# Thread 1
write(&data, "hello")
fence(Release)
atomic_store(&has_data, True)

# Thread 2
if atomic_load(&has_data):
    fence(Acquire)
    d = read(&data)
    assert(d == "hello")

案例研究：互斥锁

您可能也注意到，本节标题为“释放和获取”，而不是“获取和释放”。这是有意为之，因为先执行“获取”操作通常会造成“先发生后发生”的错觉。与其考虑“锁定(获取)”和“解锁(释放)”，不如考虑“解锁(释放)”使关键部分的更改可供“锁定(获取)”使用：

mutex = Mutex()
data = None

# Thread 1 (assume locked)
    data = "hello"
    fence(Release)
    mutex.unlock()

# Thread 2 (assume unlocked)
    mutex.lock()
    fence(Acquire)
    assert(data == "hello")

互斥锁的释放顺序仅用于将更改“释放”给下一个互斥锁持有者，该持有者“获取”上一个互斥锁解锁者先前释放的更改。这种规范的逆序关系比简单地说“lock() 获取更改，unlock() 释放更改”更能体现释放和获取之间的先后关系。

我们在这里创建的称为部分排序。它指的是两组（内存）操作之间的排序。之所以称为“部分”，是因为它排序的是操作集合之间，而不是单个操作本身：释放操作之前的操作不需要按照获取操作描述的顺序执行，只需要观察到它们确实发生即可。

顺序一致性

有些情况下，我们需要确保某些原子操作按照特定的顺序执行。这时我们需要的就是全序关系。全序关系确保操作本身之间存在某种确定的顺序，而不是操作集合之间存在顺序，而SeqCst内存排序正是用于此目的。

我们来看另一个代码示例：

head = 0
tail = 0
buf = [...]

# Thread 1
steal():
    h = atomic_load(&head)
    t = atomic_load(&tail)
    if t > h:
        item = buf[h]
        if atomic_cas(&head, h, h + 1):
            return item
    return None

# Thread 2
pop():
    t = tail
    atomic_store(&tail, t - 1)
    h = atomic_load(&head)
    if t > h + 1: 
        return buf[t - 1]
    if t == h + 1 and atomic_cas(&head, h, t):
        return buf[t - 1]
    atomic_store(&tail, t)
    return None

这段代码取自Chase. Lev 实现的 LIFO 双端队列。它的具体功能并不重要，但它在SeqCst实际需要时是一个很好的示例。

对于 pop() 函数，我们需要确保tail在加载到目标位置之前观察到存储操作发生head。否则，pop() 可能无法检测到从 steal() 中移除的项。让我们尝试将 Acquire 和 Release 机制应用于 pop() 函数：

atomic_store(&tail, t - 1, Release)
h = atomic_load(&head, Acquire)

这并不完全符合我们的预期：Release 会阻止store()之前的内容被重新排序，而 Acquire 会阻止 load()之后的内容被重新排序到 load() 之前。但并不能保证 store() 和 load()本身不会被重新排序。

        other memory operations
    ^       |            
    |       X     store release----
    |                             |
    ----load acquire    X         |
                        |         v
        other memory operations

为了确保原子 store() 和 load() 保持其声明的顺序，我们需要在 store() 上使用 Acquire 屏障，这可以通过带有 AcqRel( atomic_swap(&tail, t - 1, AcqRel)) 的 RMW 操作在语义上实现，或者我们需要SeqCst。

atomic_store(&tail, t - 1, SeqCst)
h = atomic_load(&head, SeqCst)

SeqCst 在这里做了两件事：它像之前一样充当存储操作的 Release 和加载操作的 Acquire，但它也确保所有 SeqCst 操作之间存在完全顺序。这种完全顺序保证了对于其他完全顺序操作，存储操作会在加载操作之前执行。由于完全顺序仅适用于其他 SeqCst 操作，我们需要将 SeqCst 应用于所有依赖于完全顺序的操作。这包括 pop() 中的原子加载/获取操作以及 steal() 中的原子加载/获取操作。完全顺序属性也适用于其他操作，fence(SeqCst)因此我们可以使用这些操作来实现相同的重排序效果：

steal():
  t = atomic_load(&tail)
  fence(SeqCst)
  h = atomic_load(&head)
  ...

pop():
  atomic_store(&tail, t - 1)
  fence(SeqCst)
  h = atomic_load(&head)

需要明确的是，SeqCst不应该用它来获取存储操作的 Acquire 权限或在加载操作的 Release 权限。这会导致错误的使用：store(SeqCst); load(Acquire)它不能保证在 load() 之后存储操作不会被重新排序，因为 load() 操作本身并不参与存储操作的排序（它也不是 SeqCst 操作）。

它应该用于强制多个原子变量之间保持完全顺序，并引入部分顺序（如之前的获取/释放操作），两者结合可以达到相同的效果。需要强调的是，完全顺序仅适用于其他 SeqCst 原子操作或与其相关的周围操作fence(SeqCst)。更多警告请参见此问题。

弱排序

大多数情况下，你可能不需要对多个原子变量的操作进行全序操作。真正需要全序操作的情况SeqCst非常少见。然而，在实践中，SeqCst全序操作却经常被滥用，这恰恰表明程序员并不确定应该使用哪种内存排序方式……总之，当你不需要对不同的原子变量进行全序操作，也不需要偏序操作时，你应该选择松弛内存排序（在 LLVM 中也称为单调排序）。

这样做只是为了确保对同一个原子变量的所有原子操作之间具有全序关系。换句话说，其他不在同一内存位置的内存操作可以围绕它重新排序。因此，store(X); load(Y)它们之间可以相互重新排序，但store(Y); load(Y)不能。

所有其他内存顺序（获取/释放/获取释放/序列计数器）都继承了“单变量全序”的宽松特性，并且已知其强度更高。宽松特性适用于计数器或通用的单原子数据，例如读取、更新和检出的数据。您不能使用它来同步其他常规或原子内存操作。

甚至有些情况下，你不需要对同一个原子变量本身进行完全排序，而只是想原子地执行一些内存操作（即避免数据竞争）。对于这种情况，你可以使用 LLVM 的无序内存排序。这种排序方式的需求甚至比完全排序还要少见SeqCst。无序排序甚至没有出现在 C11 内存模型中（它只达到了“宽松”的程度）。

硬件怪癖

在现代 CPU 指令集架构 (ISA) 中，普通的内存操作默认是原子性的。好处是，对于宽松/无序的内存顺序或原子加载/存储操作，无需付出额外的性能代价。缺点是，ISA 中不存在数据竞争，因此很难判断是否存在数据竞争。幸运的是，有一些工具可以检测内存访问中的数据竞争，例如 LLVM 的ThreadSanitizer (TSAN)。

某些 CPU 指令集架构 (ISA) 具有全存储顺序 (Total-Store-Ordering，简称 TSO)，例如 x86 和 SPARC。在这种情况下，由于正常的内存操作是原子性的，因此它们也免费获得了部分顺序。这意味着默认情况下，加载操作是获取 (Acquire) 操作，存储操作是释放 (Release) 操作。与之前一样，您可以享受释放/获取操作没有额外开销（除了会抑制编译器优化）的好处，但它也有缺点。在这种情况下，您可以非常随意地使用内存顺序，因此您在宽松的内存顺序下编写的代码（原本应该使用释放/获取操作）在这些架构上可以正常工作，但在其他架构上则会出错，这很容易导致编写出内存顺序错误的代码。

文中提到的“其他”架构被称为弱序指令集架构（ISA）。这包括 ARM、AARCH64、POWERPC、RISC-V、MIPS 等。在这些架构中，加载和存储操作默认仍然是原子性的，但它们只是宽松的，并且获取/释放操作需要付出额外的代价。这意味着，如果指令顺序错误，出现异常行为的概率会更高。理论上，较弱的默认指令顺序允许 CPU 进行更多的重新排序，但考虑到现代 x86 CPU 在跨核通信方面通常表现更佳，这在实践中似乎无关紧要。

然而，就顺序一致性而言，几乎没有哪个平台能免费提供这种特性。fence(SeqCst)特别是，顺序一致性通常成本最高，因为它通常需要一个完整的屏障来实现，从而防止所有形式的重排序。在 x86 架构上，mfence虽然可以使用前缀指令来实现（前提是不需要同步写入合并的内存指令），但使用前缀指令可以更经济地实现lock。为了保持其语义，顺序一致性加载/存储操作通常需要提升为 RMW 操作或使用获取/释放屏障。这或许可以解释为什么有人认为顺序一致性操作“很慢”（实际上并非如此）。

结论

处理原子操作需要以与通常截然不同的方式思考内存问题。为了保证原子算法的有效性，你必须同时考虑并发性；为了保证算法内存访问的有效性，你还必须考虑重排序和可见性问题。难怪它被认为是一个极具挑战性的课题。

希望您已经通过本文获取了一些信息，从而更深入地了解了这些技术的运作方式。原子操作还有很多值得探讨的内容，例如如何构建正确的原子数据结构、处理并发内存回收以及减少同步操作。这些内容本身都很有意思，但最好留待以后再讨论。