作者：Matt Kline
日期：2020年4月28日
https://assets.bitbashing.io/papers/concurrency-primer.pdf
Systems programmers are familiar with tools like mutexes, semaphores, and condition variables. But how do they work? How do we write concurrent code when they’re not available, like when we’re working below the operating system in an embedded environment, or when we can’t block due to hard time constraints? And since your compiler and hardware conspire to turn your code into things you didn’t write, running in orders you never asked for, how do multithreaded programs work at all? Concurrency is a complicated and unintuitive topic, but let’s try to cover some fundamentals.
摘要
系统程序员熟悉工具，如互斥锁、信号量和条件变量，但它们究竟是如何运作的呢？当这些工具无法使用时，例如在嵌入式环境下位于操作系统之下，或者由于严格的时间限制不能进行阻塞操作时，我们应该如何编写并发代码呢？另外，由于编译器和硬件会合谋将您的代码转变成您从未编写过的形式，并按照您从未要求的顺序运行，多线程程序究竟是如何运作的呢？并发是一个复杂而不容易理解的主题，但让我们尝试涵盖一些基本原理。
1. Background
Modern computers run many instruction streams concurrently.On single-core machines, they take turns, sharing the cpu in short slices of time. On multi-core machines, several can run
in parallel. We call them many names—processes, threads,tasks, interrupt service routines, and more—but most of the same principles apply across the board.
While computer scientists have built lots of great abstractions, these instruction streams (let’s call them all threads for the sake of brevity) ultimately interact by sharing bits of state.
For this to work, we need to understand the order in which threads read and write to memory. Consider a simple example where thread A shares an integer with others. It writes the integer to some variable, then sets a flag to instruct other threads to read whatever it just stored. As code, this might resemble:
背景
现代计算机同时运行许多指令流。在单核处理器的计算机上，它们轮流执行，在短时间片内共享CPU。在多核处理器的计算机上，多个指令流可以并行执行。我们用许多不同的名称来称呼它们，比如进程、线程、任务、中断服务例程等等，但大多数相同的原则都适用。
尽管计算机科学家已经构建了许多出色的抽象概念，但这些指令流（为了简洁起见，让我们都称它们为线程）最终是通过共享一部分状态来相互交互的。为了使这一过程顺利进行，我们需要了解线程读写内存的顺序。举一个简单的例子，其中线程A与其他线程共享一个整数。它将这个整数写入某个变量，然后设置一个标志，以指示其他线程读取它刚刚存储的内容。
实现代码可能如下所示：
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...
}
We need to make sure that other threads only observe A’s write to v_ready after A’s write to v. (If another thread can “see” v_ready become true before it sees v become 42, this simple scheme won’t work.) You would think it’s trivial to guarantee this order, but nothing is as it seems. For starters, any optimizing compiler will rewrite your code to run faster on the hardware it’s targeting. So long as the resulting instructions run to the same effect for the current thread, reads and writes can be moved to avoid pipeline stalls* or improve locality.† Variables can be assigned to the same memory location if they’re never used at the same time. Calculations can be made speculatively, before a branch is taken, then ignored if the compiler guessed incorrectly.‡
我们需要确保其他线程只在A写入v之后观察到v_ready的写入。（如果另一个线程在看到v变为42之前就“看到”v_ready变为true，这个简单的方案就行不通了。）
你可能认为保证这个顺序是微不足道的，但事情并不像表面看起来那么简单。首先，任何优化编译器都会重新编写您的代码，以在其针对的硬件上更快地运行。只要最终的指令对于当前线程产生相同的效果，读取和写入可以被移动以避免流水线停顿*或提高本地化†（RAM不是以单个字节读取的，而是以称为缓存行的块读取的。如果一起使用的变量可以放置在同一缓存行上，它们将一次性全部读取和写入。通常，这会提供巨大的速度提升，但正如我们在第12节中所看到的那样，在必须在多个核心之间共享一行时，它可能会对我们造成影响。）。如果这些变量不在同一时间被使用，它们可以被分配到同一个内存位置。在分支被执行之前，可以进行计算的猜测性计算，而如果编译器猜测错误就忽略‡（这在使用基于性能分析的优化（profile-guided optimization）时特别常见。）。
Even if the compiler didn’t change our code, we’d still be in trouble, since our hardware does it too! A modern cpu processes instructions in a much more complicated fashion than traditional pipelined approaches like the one shown in Figure 1. They contain many data paths, each for different types of instructions, and schedulers which reorder and route instructions through these paths.
即使编译器没有改变我们的代码，我们仍然会遇到问题，因为我们的硬件也会这样做！现代CPU的指令处理方式比传统的流水线处理方法（如图1所示）要复杂得多。它们包含许多数据路径，每个路径用于不同类型的指令，并且包含重新排序和路由指令的调度器，使其通过这些路径执行。（"route instructions" 意指将指令分配给适当的执行单元或处理单元，以便在CPU中执行。在现代CPU中，有多个执行单元，每个执行单元专门处理不同类型的指令（例如，整数运算、浮点运算等）。调度器负责将指令分派到这些执行单元，以便高效地执行它们。因此，"route instructions" 指的是将指令分派到适当的执行单元，以便在CPU中执行。这有助于提高指令的并行执行和整体性能。）
Figure 1: A traditional five-stage cpu pipeline with fetch, decode, execute, memory access, and write-back stages. Modern designs are much more complicated, often reordering instructions on the fly. Image courtesy of Wikipedia.
It’s also easy to make naïve assumptions about how memory works. If we imagine a multi-core processor, we might think of something resembling Figure 2, where each core takes turns performing reads and writes to the system’s memory.
我们还很容易对内存的工作原理做出天真的假设。如果我们想象一个多核处理器，我们可能会想到类似图2的情况，其中每个核心轮流执行对系统内存的读写操作。
Figure 2: An idealized multi-core processor where cores take turns accessing a single shared set of memory.
But the world isn’t so simple. While processor speeds have increased exponentially over the past decades, ram hasn’t been able to keep up, creating an ever-widening gulf between the time it takes to run an instruction and the time needed to retrieve its data from memory. Hardware designers have compensated by placing a growing number of hierarchical caches directly on the cpu die. Each core also usually has a store buffer that handles pending writes while subsequent instructions are executed. Keeping this memory system coherent, so that writes made by one core are observable by others, even if those cores use different caches, is quite challenging.
但实际情况并不那么简单。虽然处理器速度在过去几十年里呈指数级增长，但内存的速度却没有跟上，导致运行指令所需的时间和从内存中检索数据所需的时间之间的差距越来越大。硬件设计师通过在CPU芯片上直接放置越来越多的分层缓存来进行补偿。此外，每个CPU核通常都有一个存储缓冲区，用于处理待处理的写操作，同时执行后续的指令。保持这种内存系统的一致性，以确保一个cpu核进行的写入操作可以被其他cpu核观察到，即使这些cpu核使用不同的缓存，也是相当具有挑战性的。
Figure 3: A common memory hierarchy for modern multi-core processors
All of these complications mean that there is no consistent concept of “now” in a multithreaded program, especially on a multi-core cpu. Creating some sense of order between threads is a team effort of the hardware, the compiler, the programming language, and your application. Let’s explore what we can do, and what tools we will need.
所有这些复杂性意味着在多线程程序中，尤其是在多核CPU上，没有一致的“现在”概念。在线程之间创建某种顺序感是硬件、编译器、编程语言和您的应用程序的共同努力。让我们探讨一下我们可以做什么，以及我们需要哪些工具。
2. Enforcing law and order
Creating order in multithreaded programs requires different approaches on each cpu architecture. For many years, systems languages like C and C++ had no notion of concurrency, forcing developers to use assembly or compiler extensions. This was finally fixed in 2011, when both languages’ iso standards added synchronization tools. So long as you use them correctly, the compiler will prevent any reorderings—both by its own optimizer, and by the cpu—that cause data races.* Let’s try our previous example again. For it to work, the “ready” flag needs to use an atomic type.
2. 强制规则和顺序
确保多线程程序的有序性在每个CPU架构上都需要采用不同的方法。多年来，像C和C++这样的系统语言没有并发的概念，迫使开发人员使用汇编语言或编译器扩展程序。这个问题在2011年得到解决，当时这两种语言的ISO标准都添加了同步工具。只要你正确使用它们，编译器将阻止任何可能导致数据竞争的重新排序，无论是由它自己的优化器还是由CPU进行的重新排序。让我们再次尝试前面的例子。为了使其正常工作，“ready”标志需要使用原子类型。
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...
}
The C and C++ standard libraries define a series of these types in <stdatomic.h> and <atomic>, respectively. They look and act just like the integer types they mirror (e.g.,
bool → atomic_bool, int → atomic_int, etc.), but the compiler ensures that other variables’ loads and stores aren’t reordered around theirs.
Informally, we can think of atomic variables as rendezvous points for threads. By making v_ready atomic, v = 42 is now guaranteed to happen before v_ready = true in thread A, just as my_v = v must happen after reading v_ready in thread B. Formally, atomic types establish a single total modification order where, “[…] the result of any execution is the same as if the reads and writes occurred in some order, and the operations of each individual processor appear in this sequence in the order specified by its program.” This model, defined by Leslie Lamport in 1979, is called sequential consistency.
C和C++标准库分别在<stdatomic.h>和<atomic>中定义了一系列这些类型。它们在外观和行为上与它们对应的整数类型相同（例如，bool → atomic_bool，int → atomic_int等），但编译器确保其他变量的加载和存储操作不会被重新排序。
简单来说，我们可以将原子变量视为线程之间的会合点。通过将v_ready设置为原子类型，现在可以确保在线程A中v = 42会在v_ready = true之前发生，就像在线程B中读取v_ready后，my_v = v必须发生一样。从正式的角度来看，原子类型建立了一个单一的总修改顺序，其中“[...] 任何执行的结果都与读取和写入以某种顺序发生时的结果相同，每个单独处理器的操作都按照其程序指定的顺序出现在此序列中。”这个模型由Leslie Lamport于1979年定义，称为顺序一致性。
3. Atomicity
But order is only one of the vital ingredients for inter-thread communication. The other is what atomic types are named for: atomicity. Something is atomic if it cannot be divided into smaller parts. If threads don’t use atomic reads and writes to share data, we’re still in trouble. Consider a program with two threads. One processes a list of files, incrementing a counter each time it finishes working on one. The other handles the user interface, periodically reading the counter to update a progress bar. If that counter is a 64-bit integer, we can’t access it atomically on 32-bit machines, since we need two loads or stores to read or write the entire value. If we’re particularly unlucky, the first thread could be halfway through writing the counter when the second thread reads it, receiving garbage. These unfortunate occasions are called torn reads and writes. If reads and writes to the counter are atomic, however, our problem disappears. We can see that, compared to the difficulties of establishing the right order, atomicity is fairly straightforward: just make sure that any variables used for thread synchronization are no larger than the cpu word size
但顺序仅仅是线程间通信的重要组成部分之一。另一个就是原子类型名称的来源：原子性。如果某物是原子的，那意味着它不能被分割成更小的部分。如果线程不使用原子读取和写入来共享数据，我们仍然会面临问题。比如一个包含两个线程的程序。其中一个线程处理文件列表，在每次完成一个文件的处理后都会递增一个计数器。另一个线程处理用户界面，定期读取计数器以更新进度条。
如果该计数器是一个64位整数，在32位计算机上无法以原子方式访问它，因为我们需要两次加载或存储操作才能读取或写入整个值。如果非常不幸，第一个线程可能在第二个线程读取计数器时正在写入，导致接收到垃圾数据。这些不幸的情况被称为撕裂读取和写入。然而，如果对计数器的读取和写入是原子的，就没这个问题了。可以看到，与建立正确的顺序相比，确保原子性相对较简单：只需确保用于线程同步的任何变量不大于CPU字长。
(CPU字长是指一个CPU一次性可以处理的最大位数，也就是它的寄存器大小。例如，一个32位的CPU一次可以处理32位的数据，而一个64位的CPU一次可以处理64位的数据。
当我们谈到确保原子性操作时，这意味着在并发编程中，我们希望某个操作要么完全执行，要么完全不执行，而不会被其他线程在中间进行干扰。这个特性在多线程环境下非常重要，因为我们通常需要避免数据的竞态条件（race condition）。
当我们说"只需确保用于线程同步的任何变量不大于CPU字长"时，基本上是在说如果你的变量大小不超过CPU字长，那么CPU可以在一个单一的操作中读取或写入该变量，这个操作是原子性的。这是因为CPU可以在一个时钟周期内完成这样的操作，而不需要担心在操作过程中被其他线程中断。
例如，如果你有一个32位的整数在一个64位的CPU上，那么这个CPU可以在一个操作中读取或写入这个整数，而不需要担心其他线程会在这个过程中改变这个整数的值。
然而，如果你的变量大小超过了CPU字长，那么CPU就不能在一个单一的操作中完成对这个变量的处理，它需要分多次操作来完成。这就可能导致原子性问题，因为在这个过程中，其他线程可能会访问或修改这个变量的值。
简而言之，保持变量大小不超过CPU字长可以帮助我们简化并发编程中的同步问题，因为这样可以保证我们的操作是原子性的。)
4. Arbitrarily-sized “atomic” types
Along with atomic_int and friends, C++ provides the template std::atomic for defining arbitrary atomic types. C, lacking a similar language feature but wanting to provide the same functionality, added an _Atomic keyword. If T is larger than the machine’s word size, the compiler and the language runtime automatically surround the variable’s reads and writes with locks. If you want to make sure this isn’t happening,† you can check with:
4. 任意大小的“原子”类型
除了atomic_int等相关类型，C++提供了std::atomic<T>模板，用于定义任意大小的原子类型。C语言虽然没有类似的语言特性，但为了提供相同的功能，引入了_Atomic关键字。如果T的大小超过了计算机的字长，编译器和语言运行时会自动在变量的读取和写入操作周围添加锁。如果您希望确保这种情况不会发生，†您可以使用以下方式进行检查：
std::atomic bar;
ASSERT(bar.is_lock_free());
在大多数情况下，*这些信息在编译时已知。 因此，C++17添加了is_always_lock_free： static_assert( std::atomic::is_always_lock_free);
std::atomic<Foo> bar;
ASSERT(bar.is_lock_free());
