文章译自 Lock-free multithreading with atomic operations，https://www.internalpointers.com/post/lock-free-multithreading-atomic-operations。点击阅读原文可查看英文原文。如果喜欢，还请点个「在看」并帮忙扩散！
本系列的其它文章：
这篇文章已经由 Federica Rinaldi 仔细校对过了。谢谢！
希腊语 “atom” (ἄτομος; atomos)的意思是不可切割的。当计算机执行的任务不可再分时，它被称为原子的(atomic)：你无法再把它分解成更小的步骤。
原子性(atomicity)是多线程操作的一个重要特性：由于它是不可分割的，当一个线程在执行原子操作时，另一个线程便不能中途介入。例如，当一个线程在共享数据上进行原子写操作时，没有其他线程可以读取到部分修改。相反，当一个线程原子化地从共享数据中读取数据时，它看到的是该时间点的完整的值。换句话说，不存在数据竞争的风险。
在上一篇中，我介绍了所谓的同步原语，这是线程同步最常用的工具。撇去其他的用途，它们为跨线程共享数据的操作提供原子性。怎么说？它们只允许单个线程执行其并发任务，而其他线程则被操作系统阻塞，直到第一个线程完成任务。理由是阻塞的线程不会对其他线程造成破坏。考虑到它们冻结线程的能力，这种同步原语也被称为阻塞机制。
在上一篇中看到的阻塞机制对于绝大多数应用程序都非常有用。如果正确使用，它们是快速且可靠的。但是它们也有一些缺点，有时需要我们考虑：
它们会阻塞其他线程 —— 休眠线程只能等待唤醒信号，其它什么也不能做：这可是在浪费宝贵的时间；
它们可能会让你的应用程序挂起(hang住, 即不响应) —— 如果一个持有锁的线程由于任何原因崩溃，锁本身永远不会被释放，其它等待中的线程将永远被卡住；
你几乎无法控制哪个线程先休眠 —— 通常由操作系统来选择要阻塞哪个线程。这可能会导致一个被称为优先级倒置的不利情况：正在执行非常重要的任务的线程被另一个优先级较低的线程阻塞。
大多数情况下，你不必关心这些问题，因为它们不会影响程序的正确性。但在另一方面，有时你需要让线程一直运行，特别是当你想充分利用多处理器/多核硬件时。也许是你无法承担因线程死亡而卡住的系统。或者，优先级倒置问题已经严重到不能忽视的地步了。
让lock-free算法来帮忙
好消息是：有另一种方法可以控制多线程应用程序中的并发任务，并能防止出现上述3点问题。它被称为 lock-free programming 或 lockless programming (都是无锁编程的意思)，是一种在多个线程之间安全地共享不断变化的数据的技术，它无需锁定和解锁操作。
坏消息是：这是更底层(low level)的东西。比使用传统的同步原语（如互斥锁和信号量）低级得多：更接近金属层(硬件层)。尽管如此，我发现无锁编程是一个很好的心智挑战，也是一个更好地理解计算机实际工作原理的好机会。
无锁编程依赖于 atomic instructions(原子指令)，即CPU直接执行的原子操作。因为它是无锁编程的基础，在本文的其余部分中，我将首先介绍原子指令，然后演示如何将它们用于并发控制。我们开始吧！
什么是原子指令？
想象一下计算机执行的任何操作，例如在屏幕上显示图片。这种操作由许多较小的操作组成：将文件读入内存、对图像进行解压、点亮屏幕上的像素等等。如果你递归地放大其中一个子任务，也就是说，如果你把它分解成越来越小的部分，你最终会到达一个死胡同(即不可分解点)。由处理器执行的人类可见的最小的操作称为 machine instruction机器指令，它是由硬件直接执行的命令。
(1. 计算机程序的多层组成。虚线是软件，实线是硬件。)
根据CPU体系结构的不同，有些机器指令是原子的，也就是说，它们是在一个单一的、不可分拆的、不可中断的步骤中执行的。另一些则不是原子的：处理器以更小的操作（称为micro-operations 微操作）的形式在背地里做更多的工作。让我们关注前一类：原子指令是CPU操作，不能进一步分解。再具体一点，原子指令可以分为两大类：store and load(存储/加载) 和 read-modify-write (RMW,读/改/写)。
store/load 原子指令
任何处理器的构建基础都是：它们被用于在内存中写入（store）和读取（load）数据。许多CPU体系结构保证这些操作本质上是原子的(在某些情况下)。例如，实现x86体系结构的处理器具有 MOV 指令，MOV 指令从内存中读取字节并将其提供给CPU。如果对对齐的数据(aligned data)执行此操作，则能保证此操作是原子的，即存储在内存中的信息，使得CPU能够轻松地一次性读取它时。
Read-modify-write (RMW) 原子操作
一些更复杂的操作不能单独使用简单的存储和加载来执行。例如，递增内存中的一个值将需要至少三个原子加载和存储指令的混合，从而使整个过程变成非原子的。Read-modify-write指令使你能够在一个原子步骤中计算多个操作，从而填了这个坑。这类指令有很多。一些CPU架构提供了所有这些指令，而另一些只提供了一个子集。举几个例子：
test-and-set —— 将1写入内存位置，并在单个原子步骤中返回旧值；
fetch-and-add —— 在内存中递增一个值，并在一个原子步骤中返回旧值；
compare-and-swap (CAS) —— 将内存位置的内容与预期值进行比较，如果它们相等，则将该内存位置的内容修改为新的给定值。
所有这些指令都是在一个原子步骤中执行内存中的多个操作。这是一个重要的特性，它让read-modify-write指令适合于无锁化的多线程操作。我们将在后续内容中了解原因。
3层原子指令
上面看到的所有指令都属于硬件层：它们要求你直接与CPU对话。使用这种方式显然是困难的和不可移植的，因为有些指令在不同的体系结构中可能有不同的名称。有些处理器型号甚至不存在这些指令！所以你不太可能接触到这些东西，除非你正在为某一台特定的机器开发非常底层的代码。
跳到软件这一层，许多操作系统提供了自己版本的原子指令。我们暂称之为原子操作(atomic operations)，因为它们是从物理对等部分抽象而来。例如，在Windows中可以找到 Interlocked API，这是一组以原子方式处理变量的函数。MacOS的 OSAtomic.h头文件也有同样的作用。它们确实隐藏了硬件实现，但你仍然是被绑定到特定的环境(OS)上的。
执行可移植原子操作的最佳方法是依赖所选编程语言所提供的原子操作。例如，在Java中，你将使用 java.util.concurrent.atomic package；C++提供了 std::atomic header；Haskell有 Data.Atomics package等。一般来说，如果一种编程语言支持多线程，那么它很可能支持原子操作。这类方法依赖编译器（如果是编译型语言）或虚拟机（如果是解释型语言）来找到实现原子操作的最佳指令，这个指令可能来自底层操作系统API或直接来自硬件。
(2. 原子指令和原子操作的层次结构。虚线是软件，实线是硬件。)
例如，GCC —— 一种C++编译器 —— 通常将C++原子操作和对象直接转换成机器指令。当某个操作无法直接映射到硬件时，它还会使用其它原子指令进行模拟（如果有的话）。最坏的情况是：在一个不提供原子操作的平台上，它可能依赖于其他的阻塞策略，当然，这些策略不再是lock-free的。
在多线程中使用原子操作
现在让我们看看原子操作是如何使用的。考虑递增一个简单的变量，这个任务本质上不是原子的，因为它由三个不同的步骤组成 —— 读取值，增加值，存储新值。传统上，你可以使用互斥锁来调节操作（以下是伪代码）：
mutex = initialize_mutex()x = 0reader_thread()mutex.lock()print(x)mutex.unlock()writer_thread()mutex.lock()x++mutex.unlock()
获取锁的第一个线程继续往下走，而其他线程则排队等待锁结束。
相反，无锁方法引入了一种不同的模式：通过使用原子操作，线程可以在没有障碍的情况下自由运行。例如：
x = 0reader_thread()print(load(x))writer_thread()fetch_and_add(x, 1)
我们假定 fetch_and_add() 和 load() 是基于相应硬件指令的原子操作。如你所见，这里没有任何锁。并发调用这些函数的多个线程都不需要等待。 load() 的原子性确保了读线程不会读到不完整的共享数据；而有了 fetch_and_add() ，写线程完整性也不会被破坏。
现实世界中的原子操作
上面例子向我们展示了原子操作的一个重要特性：它们只处理原始类型(primitive types) —— 布尔、char、short、int等等。而另一方面，实际的程序需要对更复杂的结构（如数组、向量、对象、数组向量、包含数组的对象等）进行同步... 。我们如何通过原始类型的原子操作来保证这些复杂实体的原子性？
lock-free编程迫使你跳出常规同步原语的框框。你不再直接使用原子操作保护共享资源，像使用互斥锁或信号量那样。相反，你基于原子操作编写lock-free算法或lock-free数据结构，来决定多个线程将如何访问你的数据。
例如，前面看到的 fetch_and_add() 操作可以用来生成一个基本的信号量，然后，你可以使用它来调节线程。毫不奇怪，所有传统的阻塞同步实体实际上都基于原子操作。
人们已经编写了无数的无锁数据结构，比如 Folly's AtomicHashMap、Boost.Lockfree library、支持多生产者/多消费者 FIFO queues 或者像 read-copy-update (RCU) 和 Shadow Paging 这类算法。从头开始编写这些原子武器是很困难的，更不用说让它们正常工作了。这就是为什么大多数时候你会去使用现有的、经过考验的算法和数据结构而不是自己重造轮子的原因。
compare-and-swap (CAS) loop (CAS 循环)
向真实世界的应用程序再进一步，compare-and-swap loop（又叫 CAS loop）可能是最常用的无锁编程策略，无论你是在使用现有的数据结构，还是从头开始编写算法。它基于相应的 compare-and-swap 原子操作，该操作有一个很好的特性：它支持多个写入者(writer)。这是并发算法的一个重要特征，特别是在复杂系统中。
CAS loop 很有趣，还因为它在无锁代码中引入了一个循环模式，以及一些理论概念。让我们仔细看看。
CAS loop 实战
操作系统或编程语言提供的CAS函数可能看起来像下面这样：
boolean compare_and_swap(shared_data,expected_value,new_value);
它接受一个指向某些共享数据的引用或指针、当前预期值和要应用的新值。仅当值没有更改（即shared_data.value==expected_value）时，函数才会用新值替换当前值（并返回true）。
CAS loop中的理念是，反复比较(compare)和交换(swap)，直到操作成功。在每次迭代中，你都向CAS函数提供引用/指针、预期值和更新值。为了考虑同一时间执行相同操作的其他writer线程，这是必需的：如果另一个线程同时更改了数据，即共享数据不再匹配预期值，那么CAS函数将失败。这也就达到了支持多个writer(写入者)的目的！
假设我们想用CAS loop重写前面片段中的fetch_and_add算法。大概会像下面这样（伪代码）：
x = 0reader_thread()print(load(x))writer_thread()temp = load(x) (1)while(!compare_and_swap(x, temp, temp + 1)) (2)
如此，(1) 算法加载共享数据的现有值，然后尝试将其与新值交换，直到成功（2）也就是说CAS函数返回true为止。
The swapping paradigm (swapping 范式, 即使用模式)
如前所述，CAS loop在许多无锁算法中引入了循环模式：
创建共享数据的本地副本(local copy)；
根据需要修改本地副本；
准备好后，通过将共享数据与之前创建的本地副本进行交换(swapping)来更新共享数据。
第3点是关键：交换(swap)是以原子方式执行的。脏活(dirty job)是由写线程在本地(locally)完成，然后仅在准备就绪时才发布出去。这样，另一个线程只能看到2种状态的共享数据：原来的或最新的。由于原子交换，不会出现半完成的或损坏的更新。
这在思想上也与有锁方式不同：在无锁算法中，线程只在短暂的原子交换期间保持联系，在剩余的时间内则不受干扰地运行，也不知道其他线程的存在。线程之间的接触点被缩小并限制在原子操作的持续时间内。
A gentle form of locking (一种温和的锁)
上面提到的 spin until success(回旋直到成功) 策略被很多的无锁算法所采用，也被叫作spinlock：一个简单的循环，线程在循环中反复尝试执行某些操作，直到成功。这是一种温和的锁定形式，线程在其中启动并保持运行 —— 操作系统不会强制其休眠，尽管在循环结束之前线程不会有任何进展。在互斥锁或信号量中使用的常规锁要昂贵许多，因为挂起/唤醒周期需要做大量的工作。
The ABA problem (ABA 问题)
上面第(1)行和第(2)行中的指令都是原子的，但又是各自独立的。另一个线程可能会从中介入，并在读取(1)后更改共享数据的值。具体地说，它可以将初始值（例如A）转换为另一个值（例如B），然后在(2)中开始比较和交换操作之前又将其变为A。运行CAS loop的线程不会注意到更改并成功执行交换。这就是众所周知的ABA问题：如果你的算法像上面那样简单，你可以轻易地忽略它。但有时你会想避免这种情况，因为它会在你的程序中引入一些难以发现的错误。幸运的是，存在一些解决办法(https://en.wikipedia.org/wiki/Compare-and-swap#ABA_problem)。
You can swap anything inside a CAS loop (CAS loop中可以交换任何数据)
CAS loop 通常用于交换指针，它是 compare-and-swap 指令所支持的。当你想要修改一个复杂的数据集合（如类或数组）时，就派上用场了：只需创建本地副本，根据需要修改它，然后在准备好时用指向全局数据的指针交换指向本地数据的指针。这样，全局数据将指向本地副本分配的内存，其他线程将看到最新的信息。
这个技术允许你同步非原始实体(non-primitive entities)，但让它正常工作仍然很难。如果在交换之后，有一个读线程仍然在使用旧指针呢？如何正确删除以前的副本而不生成危险的悬挂指针？工程师们再一次找到了一些解决方案，比如使用一种支持垃圾回收的语言，或者一些内行人才懂的技术，比如 epoch-based memory reclamation, hazard pointers 或 reference counting。(点击 阅读原文 可以查看这些技术的链接)
Lock-freedom vs. wait-freedom (无锁 和 无等待的比较)
每个基于原子操作的算法或数据结构都可以分为两组：无锁的或无等待的。当必须评估基于原子的工具对程序性能的影响时，这是一个重要的区别。
无锁算法允许剩余的线程继续执行有用的工作，即使其中一个线程暂时很忙。换言之，至少有一个线程在取得进展。CAS loop 是一个完美的 lock-free 示例，因为如果CAS loop的一次迭代失败，通常表明其他线程成功地修改了共享资源。然而，一个无锁算法可能会花费不可预知的时间来进行回旋(spin,循环)，特别是当有许多线程在竞争同一资源时：以技术的术语说，当竞争(contention)很激烈时(contention is high)。如果把它推到极限，一个无锁算法在CPU资源上的效率可能远低于一个使阻塞的线程进入休眠状态的互斥锁(即，有些情况下无锁算法更消耗cpu资源)。
另一方面，在无等待算法(无锁算法的一个子集)中，无论其他线程的执行速度或工作负载水平如何，任何线程都可以以有限的数量或步骤完成其工作。本文中基于fetch_and_add 操作的第一个片段是一个无等待算法的示例：没有循环，没有重试，只有未受干扰的流程。另外，无等待算法是容错性(fault-tolerant)的：其他进程的失败或速度的任意变化都不会影响无等待算法的顺利完成。这些特性使得无等待算法适用于复杂的实时系统，这类系统中，让并发代码的行为可预测是必须的。
3. 无等待算法是无锁算法的一个子集。
无等待是并发代码的一个非常理想的属性(即，都想写出lock-free的并发代码)，但是很难求得。总之，不管你是在构建一个阻塞算法还是无锁或无等待的算法，黄金法则是，始终对代码进行基准测试并评估结果。有时，一个好的但老旧的互斥锁可以胜过其它更高大上的同步原语，特别是当并发任务复杂度较高时。
Closing notes 结束语
原子操作是无锁编程的必要组成部分，即使在单处理器机器上也是如此。如果没有原子性，线程可能会在事务途中被中断，从而导致不一致的状态。在本文中，我只触及了一个表面，随着多核/多处理器的引入，一个带有各种问题的新世界出现了。sequential consistency(顺序一致性) 和 memory barriers(内存屏障) 等主题是这些问题的关键部分。如果你想从无锁算法中获得最佳效果，就不能忽略这些主题。我将在下一篇文章里对它们一一道来。
参考:
Preshing on Programming - An Introduction to Lock-Free Programming
Preshing on Programming - Atomic vs. Non-Atomic Operations
Preshing on Programming - You Can Do Any Kind of Atomic Read-Modify-Write Operation
StackOverflow - Do I need a mutex for reading?
..文章的参考有很多，点击阅读原文查看吧
