要点
-
为什么编译器和 CPU 硬件对加载和存储进行重新排序。
-
为什么我们需要特殊的工具来防止这些重新排序在线程之间进行通信。
-
我们如何保证我们计划的顺序一致性。
-
原子读-修改-写操作。• 如何在弱序硬件上实现原子操作，以及这对语言级 API 有何影响。
-
我们如何使用非顺序一致的内存排序仔细优化无锁代码。
-
错误共享如何影响并发内存访问的性能。
-
为什么
volatile不适合线程间通信。 -
如何防止编译器以不希望的方式融合原子操作。
一、原子性
原子加载和存储
对于并发编程问题中的原子操作，我们要关注的问题主要是read-modify-write操作，除此之外，原子操作还涉及atomic loads and stroes。
如果相对于其他线程是单步完成的，那么一个在共享内存上的操作时原子的。当一个原子存储操作在一个共享变量上执行时，其他线程无法观察到其修改过程；当一个原子加载操作在一个共享变量上执行时，它读取某一时刻下完整的值。
但是非原子加载和存储无法作出这个保证。如果没有这种保证，那么无锁编程是不可能的，因为你不可能让不同的线程在同一时间操作一个共享变量，即：
每当两个线程同时对共享变量进行操作，并且其中一个操作执行写操作时，两个线程都必须使用原子操作
如果违背了这个规则，任何一个线程都将使用非原子操作，那么您将得到C++11标准所称的data race。导致data race的原因是：撕裂读torn reads和撕裂写torn writes。
1. 多个CPU指令的非原子化操作
假设我们有一个64-bit的全局变量。
uint64_t sharedValue = 0;
我们使用函数将给它赋一个64位的值
void storeValue()
{
sharedValue = 0x100000002;
}
如果我们使用gcc将其在32位的x86机器上进行编译，它会产生下面的汇编代码。
$ gcc -O2 -S -masm=intel test.c
$ cat test.s
...
mov DWORD PTR sharedValue, 2
mov DWORD PTR sharedValue+4, 1
ret
...
正如我们所看到的，编译器使用2个单独的汇编指令来完成64位赋值，第一个指令将低32位赋值为0x00000002，第二条指令将高32位赋值为0x00000001。显然，这个赋值的操作时非原子化的，如果此时sharedValue被其他线程并发获取，那么：
-
如果程序执行在上面两个中断指令之间被抢占，那么将在内存中留下
0x0000000000000002的值——torn write。这种情况下，如果另一个线程读取sharedValue，那么将收到一个虚假的值。 -
如果另一个线程在第一个线程重新运行前修改了
sharedValue，那么将会导致一个持久化的torn write：高32位的值来自一个线程，低32位的值来自另一个线程。 -
在多核设备上，甚至不需要抢占就可以造成
torn write，在不同内核上执行的任何线程都有可能在sharedValue只修改到一半的时候读取它。
并发读也会带来一系列问题：
uint64_t loadValue()
{
return sharedValue;
}
$ gcc -O2 -S -masm=intel test.c
$ cat test.s
...
mov eax, DWORD PTR sharedValue
mov edx, DWORD PTR sharedValue+4
ret
...
编译器在这里使用两个汇编指令执行读操作，将低32位存储到eax寄存器，高32位存储到edx寄存器。这种情况下，如果一个并发的存储在两条指令之间发生，将会导致torn read，即使并发存储操作是原子化的。
2. 单CPU指令的非原子化操作
即使由单个CPU指令执行，内存操作也可以是非原子的。例如ARMv7指令集包括的strd指令，它将两个32位源寄存器的内容存储到内存中的单个64位值中。
strd r0, r1, [r2]
在某些ARMv7处理器上，此指令不是原子指令。当处理器看到此指令时，它实际上在后台执行两个单独的32位存储。
这种情况下另一个在单独内核上运行的线程就有可能观察到torn write。对于单核设备，两个内部32位存储之间可能会发生系统中断（例如，调度线程上下文切换），这种情况下，当线程从中断中恢复时，它将重新启动strd指令。
作为另一个例子，众所周知，在x86上，如果内存操作数自然对齐，则32位mov指令是原子的，否则是非原子的。换句话说，只有当32位整数精确位于4倍数的地址时，才能保证原子性。
对于上述问题，C++提供了std:atomic模板用于定义任意的原子类型。C则通过_Atomic关键字提供了相同的功能。这种情况下，如果 T 大于计算机的字大小，编译器和语言运行时会自动用锁包围变量的读取和写入。
读取-修改-写入
如果我们要满足这样一个操作：读取一个值，修改它，然后将其写回的单个原子步骤。对于这个需求，有一些常见的rmw操作，在C++中，它们表示为std:atomic的成员函数，在C语言中，它们是独立的函数。
1. 交换
最简单的原子rmw操作是交换：读取当前值并替换为新值。让我们假设这么一个需求：UI希望显示每秒处理的文件数，而不是显示已处理文件的总数。我们可以通过让UI线程读取计数器后按每秒将其归零。但是，如果读取和归零是单独的步骤，我们可能得到以下竞态条件：1. UI线程读取计数器；2. 在UI线程有机会将其归零之前，工作线程会再次递增它；3. UI线程将计数器归零，这导致了之前的增量消失。
如果UI线程以原子方式将当前值与零交换，则争用消失。
2. 测试和设置
测试和设置操作对布尔值起作用：读取它，将其设置为true，并预先提取它持有的值。C和C++提供了一种专用于此目的的类型，称为atomic_flag。我们可以用它来构建一个简单的自旋锁：
std::atomic_flag af;
void lock()
{
while (af.test_and_set()) { /* wait */ }
}
void unlock() { af.clear(); }
如果我们调用lock()并且前一个值为false，则我们获取到该锁，并因此可以独占访问锁保护的任何内容，如果前一个值为true，则其他人已经取得了锁，我们必须等到它们通过unlock()函数将其释放。
3. 获取和修改
我们还可以读取一个值，对其执行简单的操作（加、减、按位异或等），并返回其先前的值，所有这些操作作为一个原子操作。在上述的例子中，工作线程的添加也必须是原子的，否者仍可能导致数据竞争：1. 工作线程将当前计数器加一；2. 在该线程将值存回之前，UI将计数器归零；3. 工作线程执行存储。
4. 比较和交换
比较和交换允许我们条件地（如果它的先前值和某个预期的值匹配）交换一个值（C A S），在C和C++中，我们通过以下方式执行原子化的比较和交换：
template <typename T>
bool atomic<T>::compare_exchange_strong(
T& expected, T desired)
{
if (*this == expected) {
*this = desired;
return true;
}
else {
expected = *this;
return false;
}
}
假设我们有一些长时间运行的任务，我们可能想要取消。我们将给它三种状态：空闲、正在运行和取消，并编写一个在取消时退出循环的操作：
enum class TaskState : int8_t {
Idle, Running, Cancelled
};
std::atomic<TaskState> ts;
void taskLoop()
{
ts = TaskState::Running;
while (ts == TaskState::Running) {
// Do good work.
}
}
If we want to cancel the task if it’s running, but do nothing if
it’s idle, we could cas:
bool cancel()
{
auto expected = TaskState::Running;
return ts.compare_exchange_strong(expected, TaskState::Cancelled);
}
原子操作作为构建块
原子加载、存储和rmw操作是每个并发工具的构建块（building block），这些工具分为两个阵营：阻塞和无锁。
阻塞同步方法通常更容易操作，但其可能使线程暂停任意的时间。考虑一个互斥锁，它强制线程轮流访问共享数据，如果某个线程锁定互斥锁，而另一个线程尝试执行相同的操作，则第二个线程必须等待或阻塞，知道第一个线程释放锁，无论时间长短。阻塞机制也很容易收到死锁和活锁的影响，即由于线程相互等待而导致整个系统卡住的错误。
相比之下，无锁同步的方法可以确保程序始终向前推进，这些操作都是非阻塞的，因为没有线程会导致另一个线程无限期地等待。考虑一个流式传输音频的程序，或者一个嵌入式系统，其中传感器在新数据到达时触发中断服务进程。在这种情况下，我们希望使用无锁的算法和数据结构，因为阻塞可能会破坏它们。（否则在第一种情况下，用户音频将开始卡顿，第二种情况下如果中断服务进程不能尽快完成，则可能会错过后续传感器的输入）
无锁算法并不一定比阻塞算法更好或更快，它们只是为不同的工作设计不同的工具。
二、顺序一致性
考虑以下代码，我们需要确保其他线程只在A写入v之后观察A对v的写入。
int v;
bool v_ready = false;
void threadA() {
// Write the value
// and set its ready flag.
v = 42;
v_ready = true;
}
void threadB() {
// Await a value change and read it.
while (!v_ready) { /* wait */ }
const int my_v = v; // Do something with my_v...
}
但是事实并非如此，任何带有优化功能的编译器都会重写这个代码，以便在目标硬件上运行得更快。即便编译器没有更改我们的代码，我们仍然会遇到麻烦，硬件本身也可能这么做，因为现代CPU处理指令的方法比传统的流水线发放要复杂得多，它们包含许多数据路径，每个路径用于不同类型的指令，并通过这些路径对指令进行重新排序。
上述的问题迫使开发人员对汇编或编译器进行扩展，如C和C++在2011年的ISO标准中都添加了同步工具，对这一问题进行了修复。我们可以用以下方式使用它们，防止任何导致数据竞争的重新排序：
int v = 0;
std::atomic_bool v_ready(false);
void threadA()
{
v = 42;
v_ready = true;
}
void threadB()
{
while (!v_ready) { /* wait */ }
const int my_v = v;
// Do something with my_v...
}
这种情况下，任何读取和写入按某种顺序的执行结果相同，并且每个处理器的操作都按照程序指定的顺序执行，这种排序方式的模型称为顺序一致性。
弱序硬件上的顺序一致性
不同的硬件架构提供了不同的内存模型。例如x64是相对强序的，在大多数情况下的加载和存储顺序是可以信任的。其他架构（如arm）是弱序的，因此不能假设加载和存储是按程序顺序执行的，除非CPU被赋予特殊指令（内存屏障，memory barriers）来避免将它们打乱。
以arm为例，考虑最简单的原子操作：加载和存储。
我们将原子变量和地址加载到暂存器(r3)中，将加载和存储夹在内存屏障（dmb）之间，然后返回。这些屏障为我们提供了顺序一致性（第一个确保先前的读取和写入不能放在我们的操作之后，第二个确保后续的读取和写入不能放到它们之前）。
使用LL/SC指令实现原子读-修改-写操作
与许多其他risc架构一样，arm缺少专用的rmw指令。由于处理器可以随时上下文切换到另一个线程，我们需要特殊的指令：加载链接和存储条件（ll/sc）。两者协同工作：加载链接从地址读取值（与任何其它负载一样），同时指示处理器监视该地址，仅当自相应的加载链接开始没有其它在该地址的存储时，存储条件才会写入给定值。
我们将当前值添加一，然后立即尝试用 sc 将其存储回去。如果失败，则另一个线程可能在我们的 ll指令执行以后写入了foo ，因此我们重试。通过这种方式，至少有一个线程总是在原子修改 foo 方面取得进展，即使有几个线程同时尝试这样做。
虚假的LL/SC失败
跟踪计算机上每个字节的加载链接地址需要太多的 CPU 硬件。为了降低此成本，许多处理器以某种更粗粒度（如缓存行）的方式监视它们。这意味着，如果 sc 之前写入受监视块中的任何地址，而不仅仅是加载链接的特定地址，则sc会失败。
这对于比较和交换来说比较麻烦，这也是是compare_exchange_weak存在的理由。考虑一个以原子方式乘以值的函数，即使在任何常见体系结构中都没有用于读写的原子指令。
void atomicMultiply(int by)
{
int expected = foo;
// Which CAS should we use?
while (!foo.compare_exchange_?(expected, expected * by)) {
// Empty loop.
// (On failure, expected is updated with
// foo's most recent value.)
}
}
许多无锁算法使用这样的 cas 循环在计算变量的新值时以原子方式更新变量： 1. 读取变量。2. 对其值执行一些（非原子）操作。3. 将新值与前一个值一起 CAS。4. 如果cas失败则重试。
如果我们对这一系列算法使用 compare_exchange_strong，编译器必须使用嵌套循环：一个内部循环用于保护我们免受虚假 sc 故障的影响，另一个外部循环重复执行我们的操作，直到没有其他线程中断我们。但与_strong版本不同的是，弱 cas 允许虚假失败，就像实现它的 ll/sc 机制一样。因此，使用 compare_exchange_weak，编译器可以生成单个循环，因为我们不关心虚假 sc 失败的重试与另一个线程修改变量引起的重试之间的区别。
是否需要确保顺序一致性
循序一致性防止了指令重排破坏我们的代码，我们还看到了在硬件上像arm这样的弱序架构使用内存屏障创建顺序一致性。当然这些屏障可能对性能产生影响，因为它们会抑制编译器和硬件本来会进行的优化。
考虑一个简单的情况，例如测试和设置中提到的自旋锁，在lock（）和unlock（）调用之间，我们可以安全地修改受锁保护的共享状态。在此部分之外，我们只读取和写入未与其他线程共享的内容。
deepThought.calculate(); // non-shared
lock(); // Lock; critical section begins
sharedState.subject = "Life, the universe and everything";
sharedState.answer = 42;
unlock(); // Unlock; critical section ends
demolishEarth(vogons); // non-shared
如果编译器和硬件可以根据需要将操作移动到受保护部分，不会造成任何麻烦，并且能运行更快，则以下内容没有问题：
lock(); // Lock; critical section begins
deepThought.calculate(); // non-shared
sharedState.subject = "Life, the universe and everything";
sharedState.answer = 42;
demolishEarth(vogons); // non-shared
unlock(); // Unlock; critical section ends
那么该如何让编译器这么做呢？
三、内存顺序
默认情况下，所有原子操作（包括加载、存储和各种风格的 rmw）都是按顺序一致的，但我们也可以通过其他顺序执行，这个顺序只是其中之一。这些顺序以及 C 和 C++ API 使用的枚举分别是：
-
顺序一致 （memory_order_seq_cst）
-
获取 （memory_order_acquire）
-
释放 （memory_order_release）
-
松弛（memory_order_relaxed）
-
获取-释放 （memory_order_acq_rel）
-
消费 （memory_order_consume）
可以将其作为可选参数提供，以选择要排序的方式。下面我们来看这些顺序是什么以及如何使用它们，并证明我们之前所看到的几乎所有示例实际上都不需要顺序一致的操作。
获取和释放
对于之前带锁获取和释放的例子，可以将它们视为“单向”屏障：一个只允许其他读写操作在该操作之后进行的获取请求，在 arm 和其他弱序架构上，这允许我们在每次操作中丢弃一个内存屏障。
int acquireFoo()
{
return foo.load(memory_order_acquire);
}
void releaseFoo(int i)
{
foo.store(i, memory_order_release);
}
松弛
当变量将在线程之间共享时，使用宽松的原子操作，但不需要特定的顺序。某个工作线程递增计数器，然后由 UI 线程读取计数器。
该计数器可以用 fetch_add（1， memory_order_relaxed） 递增，因为我们所需要的只是原子性——计数器不会同步任何内容。宽松的读取和写入对于在线程之间共享标志也很有用。考虑一些循环直到被告知退出的线程：
atomic_bool stop(false);
void worker()
{
while (!stop.load(memory_order_relaxed)) {
// Do good work.
}
}
int main()
{
launchWorker();
// Wait some...
stop = true; // seq_cst
joinWorker();
}
我们不在乎循环的内容是否围绕加载操作重新排列。只要stop变量仅用于告诉Woker退出，而不是“宣布”任何新数据，就不会发生任何坏事。最后，松弛载荷通常用于 cas 回路。返回我们的无锁乘法：
void atomicMultiply(int by)
{
int expected = foo.load(memory_order_relaxed);
while (!foo.compare_exchange_weak( expected, expected * by,
memory_order_release, memory_order_relaxed))
{
/* empty loop */
}
}
所有的加载操作都可以放宽——在我们成功修改我们的值之前，我们不需要强制执行任何顺序。预期的初始加载甚至不是严格必要的。如果 cas 之前没有其他线程修改 foo，它能为我们节省循环迭代。
获取-释放
memory_order_acq_rel 与需要加载-获取和存储-释放值的原子 rmw 操作一起使用。一个典型的示例涉及线程安全的引用计数，如 C++ 的shared_ptr：
void inc()
{
refCount.fetch_add(1, memory_order_relaxed);
}
void dec()
{
if (refCount.fetch_sub(1, memory_order_acq_rel) == 1) {
// No more references, delete the data.
}
}
递增引用计数时，顺序无关紧要，因为不会因此执行任何操作。但是，当我们递减时，我们必须确保：1. 对引用对象的所有访问都发生在计数达到零之前。2. 在引用计数达到零后执行删除操作。
获取-发布和顺序一致的操作之间的区别通常在于操作是否需要参与顺序一致操作的单一全局顺序。换句话说，获取-释放提供相对于加载-获取和存储-释放的变量顺序，而顺序一致的操作在整个程序中提供一些全局顺序。
消费
对于memory_order_consume，考虑一个数据很少更改，但经常由许多线程读取的情况。也许我们正在编写一个内核，我们正在跟踪插入机器的外围设备。此信息很少更改（仅当有人插入或拔出某些内容时），因此尽可能优化读取是有意义的：
std::atomic<PeripheralData*> peripherals;
// Writers:
PeripheralData* p = kAllocate(sizeof(*p));
populateWithNewDeviceData(p);
peripherals.store(p, memory_order_release);
// Readers:
PeripheralData* p = peripherals.load(memory_order_acquire);
if (p != nullptr) {
doSomethingWith(p->keyboards);
}
为了进一步优化读取器，加载操作可以避免弱序系统上的内存障碍。由于我们检查的数据（p->键盘）依赖于p的值，因此大多数平台（即使是弱序平台）也无法对初始加载（p =外围设备）进行重新排序，以便在只后发生（p->键盘）。 只需要编译器不要做出任何类似的推测，将读者更改为：
PeripheralData* p =peripherals.load(memory_order_consume);
if (p != nullptr) {
doSomethingWith(p->keyboards);
}
and an arm compiler could emit:
ldr r3, &peripherals
ldr r3, [r3]
// Look ma, no barrier!
cbz r3, was_null // Check for null
ldr r0, [r3, #4] // Load p->keyboards
b doSomethingWith(Keyboards*)
was_null:
...
弄清楚什么构成了表达式之间的“依赖关系”并不像人们所希望的那么简单，因此事实上所有编译器当前都将消费操作转换为获取操作。
四、其他
硬件融合
这里显示的所有程序集都是针对arm架构的第七个版本。第八代为无锁代码提供了巨大的改进。由于大多数编程语言已经汇聚到我们一直在探索的内存模型上，armv8 处理器提供了专用的加载获取和存储发布指令：lda 和 stl。
缓存和虚假共享
内存以称为缓存行的块在主存和CPU之间传输。这些行也是内核及其各自缓存之间传输的最小单元。如果一个内核写入一个值而另一个内核读取该值，则必须将包含该值的整行从第一个内核的缓存传输到第二个内核的缓存，以保持其内存“视图”的一致性。这会对性能造成较大的影响。
考虑读取器-写入器锁，它通过确保共享数据具有一个写入器或任意数量的读取器来避免竞争，但绝不会同时具有两个读取器。从本质上讲，它类似于以下内容：
struct RWLock {
int readers;
bool hasWriter; // Zero or one writers
};
写入器必须阻塞，直到读取器达到零，但是只要 hasWriter 为假，读取器就可以使用原子 rmw 操作来获取锁定。
对于我们读取共享数据的频率高于写入数据的情况，这似乎比独占锁（例如，互斥锁、旋转锁等）提供了巨大的性能优势，但这没有考虑缓存效应。
如果多个读取器（每个读取器在不同的内核上运行）同时获取锁定，则其缓存行将在这些内核的缓存之间跳动。除非被锁保护的部分非常大，否则解决此争用可能需要比运行被锁保护部分本身更多的时间。
当它发生在碰巧放在同一缓存行上的不相关变量之间时，这种减速更加隐蔽。在设计并发数据结构或算法时，必须考虑这种错误共享。避免这种情况的一种方法是用未共享数据的缓存行填充原子变量，但这是一个很大的时空权衡。
volatile不是答案。
也许是因为volatile在较旧的编译器和硬件中的工作方式，或者由于它在 Java 和 C# 等语言中的不同含义，有些人认为该关键字对于构建并发工具很有用。这基本是错误的。
volatile的目的是通知编译器一个值可以在正在执行的程序之外被修改。这对于内存映射 I/O （mmio） 非常有用，其中硬件将读取和写入某些地址转换为CPU指令。（这是大多数机器最终与外界交互的方式。volatile意味着两个保证：
-
编译器不会删除看似“不必要的”加载和存储。例如，如果我有一些函数：
void write(int* t)
{
*t = 2;
*t = 42;
}编译器通常会优化其为：
void write(int* t) { *t = 42; }*t = 2 通常假定是一个什么都不做的死存储。但是如果 t 指向某个 mmio 寄存器，则做出此假设是不安全的：每次写入都可能对与之交互的硬件产生一些影响。
-
出于类似的原因，编译器不会对该
volatile读写相对于其他volatile读写重新排序。这些规则没有为我们提供安全线程间通信所需的原子性或顺序。第二个保证仅防止
volatile操作相对于彼此重新排序，编译器仍然可以自由地重新排列所有其他“正常”加载和围绕它们的存储。即使我们把这个问题放在一边，volatile也不会在弱序硬件上发出内存屏障。仅当编译器和硬件都不执行重新排序时，该关键字才用作同步机制。
原子融合
最后，人们应该意识到，虽然原子操作确实阻止了某些优化，但它们并不能以某种方式免疫所有这些优化。优化器可以做一些相当平凡的事情，例如用 foo = 0 替换 foo.fetch_and（0），但它也可以产生令人惊讶的结果。如：
while (tmp = foo.load(memory_order_relaxed)) { doSomething(tmp); }
由于宽松加载不提供排序保证，编译器可以随意展开循环，也许：
while (tmp = foo.load(memory_order_relaxed)) {
doSomething(tmp);
doSomething(tmp);
doSomething(tmp);
doSomething(tmp);
}
如果像这样的“融合”读取或写入是不可接受的，我们必须使用volatile映射或如asm volatile("" ::: "memory")的指令来阻止它。 Linux 内核为此提供了 READ_ONCE（） 和 WRITE_ONCE（）。