玻尔百科在多核处理器的世界里，让多个线程在不破坏共享数据的情况下协同工作是一项核心挑战。使用锁的传统方法——一次只授予一个线程独占访问权——是一种悲观策略，可能导致性能瓶颈，在更糟的情况下，还会导致被称为死锁的系统范围僵局。这就提出了一个关键问题：是否可以在不强迫线程相互等待的情况下，安全地协调并发操作？
本文探讨了一种强大、乐观的替代方案，它位于现代高性能计算的核心：比较并交换（Compare-and-Swap, CAS）操作。CAS 不锁定数据，而是允许线程提议一个更新，该更新仅在数据在此期间未被其他线程更改时才会成功。这种简单的原子性保证是构建“无锁”系统的基石，这些系统具有弹性、可扩展性，并且没有死锁的危险。
在接下来的章节中，您将深入了解这个基本工具。“原理与机制”一章将解构 CAS 操作，从其逻辑功能到硬件实现，并探讨其带来的微妙但关键的挑战，如臭名昭著的 ABA 问题。随后，“应用与跨学科联系”一章将揭示这条单一指令如何被用来构建从高效的并发数据结构到机器人和分布式计算等领域中复杂的协调模式等一切事物。
想象一下，你和你的同事正在共同撰写一本共享日记。为了添加一段连贯的条目，你必须先阅读最后写的句子，思考要添加什么，然后再写下你的贡献。但问题来了：如果在你读完最后一句和动笔写作之间，别人已经添加了他们自己的想法，会发生什么？你精心构思的句子，基于你以为是故事结尾的内容，现在变得毫无意义。这就是经典的读-改-写问题，是并发编程世界中的一个根本性挑战。
一个简单的解决方案是使用锁。我们可以把日记放在一个只有一个钥匙的盒子里。要写作，你必须拿到钥匙，打开盒子，完成你的阅读和写作，然后锁上盒子并归还钥匙。这方法可行，但效率极低。如果持有钥匙的人分心或花了很长时间，其他所有人都只能干等着。在拥有许多处理核心的计算机系统中，这种等待可能导致性能瓶颈，在更复杂的情况下，还会导致一种可怕的死锁状态，即多个进程被冻结，每个进程都在等待对方持有的资源。我们需要一种更优雅、不那么悲观的协调方式。
如果我们能以一种神奇的条件来提议更新呢？想象一下，你能对日记的守护者说：“我期望最后一句话是‘夕阳正在落下’，并且当且仅当这句话是正确的，请加上我的句子‘在山谷中投下长长的影子’。”如果在此期间有人写了别的东西，你的请求就会被简单地拒绝，你可以在重新阅读新的最后一句话后再试一次。
这就是现代处理器中一种强大指令的精髓：比较并交换（Compare-and-Swap），或称 CAS。它是一条单一的命令，告诉处理器：
这个契约最关键的部分是，这些步骤是原子地发生的。对于宇宙中的其他部分来说，整个操作是不可分割且瞬时完成的。该内存位置的值要么是旧值，要么是新值；任何观察者都无法捕捉到它处于部分改变的状态，或者在比较和交换之间插入更新。这是一次量子跃迁，而非渐进的过渡。
这种“原子闪现”并非魔法；它是一项深入处理器及其内存系统核心的工程杰作。人们可能天真地认为处理器只是执行一个快速的读周期，然后是一个写周期。但在多核系统中，读和写之间的微小间隙为另一个核心修改内存提供了一个巨大的机会窗口，从而导致我们试图解决的那个问题。
真正的解决方案是让处理器核心暂时性地获得那块内存的独占、无可争议的所有权。在现代架构中，这是由缓存一致性协议（如 MESI）精心安排的。当一个核心执行 CAS 指令时，它实际上是通过芯片的高速互连发送一条消息，说：“其他所有人，别碰这个缓存行！我正在执行一个神圣的仪式。”它为那块内存获得一个短暂的“锁定”状态，使其能够在本地不受干扰地执行其读-比较-写序列。只有在序列完成后，锁才被释放，如果发生了写操作，新值将被广播到所有其他核心，以保持它们对内存视图的一致性。
这整个序列是处理器内部微操作的精心编排之舞。硬件必须在内存总线上断言一个 LOCK 信号，读取值，执行比较，并有条件地发出写操作，所有这些都必须在 LOCK 信号释放之前完成。为保证原子性，在整个持续时间内保持锁是不可协商的。这一要求产生了深远的影响，甚至对处理器复杂的内部流水线也是如此。一个喜欢为了性能而重排指令的乱序执行引擎，必须被教会尊重 CAS。它不能允许对同一内存地址的后续 load 操作在 CAS 完成前进行推测性执行。硬件必须将 CAS 视为该地址的一个特殊栅栏，通常通过检测并取消任何可能违反其原子性的推测性操作来实现。
有了我们的原子之锤，我们现在可以不使用传统锁来构建极其优雅的并发数据结构。一个经典的例子是无锁栈。想象一下，栈顶由一个单一的共享指针 head 表示。
要 push 一个新项，线程会创建一个新节点，将其 next 字段指向当前的 head，然后使用 CAS 尝试将 head 指针指向其新节点。逻辑大致如下：
如果 CAS 失败，那仅仅意味着在我们的读操作和 CAS 尝试之间的微小窗口内，另一个线程修改了 head。没有造成任何损害。我们只需循环，重新读取现在更新的 head，然后重试。这种乐观的“自旋后提交”策略是无锁编程的核心。pop 操作也采用类似的逻辑。线程的 CAS 成功的那一刻就是线性化点——其操作看起来已原子地、确定地生效的精确时间点 [@problem_id:3205711, @problem_id:3247241]。
这种乐观的方法虽然强大，但隐藏着一个微妙而危险的陷阱：ABA 问题。因为 CAS 纯粹基于值，它可能被一系列事件所欺骗，从而对历史变化视而不见。
想象一个线程 T1，想要从一个栈中弹出一个项，该栈的顶部是节点 A，指向节点 B。T1 读取 head 为 A，A.next 为 B。它现在准备执行 CAS(, A, B)。但就在这时，T1 被操作系统挂起。
在 T1 休眠期间，系统很忙：
A。栈顶现在是 B。B。A 的内存现在被释放了。A 过去占用的完全相同的内存地址。A 的新节点推入栈中。head 指针再次包含了值 A。现在，T1 醒来。它继续其原计划：CAS(, A, B)。CAS 检查 head 指针，发现其值确实是 A，于是成功了！它“乐于助人”地将 head 更新为指向 B，而 B 是一个指向很久以前就被弹出节点的陈旧指针。栈现在被破坏了，可能导致数据丢失或系统崩溃。
CAS 被欺骗了，因为它只看到值再次变为了 A；它不知道它现在看到的 A 与它最初看到的 A 是完全不同的概念实体。这是一个根本性的限制。有趣的是，其他一些原子原语，如加载链接/条件存储（LL/SC），则不会受此问题影响。LL/SC 的工作方式是在一个内存地址上创建一个硬件“预留”。对该地址的任何写操作，即使是恢复原始值的写操作，也会破坏这个预留，导致后续的条件存储失败。它能感知历史，而不仅仅是值 [@problem-id:3654157]。
要用 CAS 解决 ABA 问题，我们必须赋予它所缺乏的历史记忆。标准的解决方案是给指针“加标签”。我们的 head 变量不再仅仅是一个内存地址，我们将其视为一个更宽的数据结构，包含指针和版本计数器（或标签）。
head 现在是一个对：(指针, 版本号)。每次我们成功更新 head 时，我们不仅改变指针，还递增版本号：(A, v) 变成 (B, v+1)。
让我们重演一下刚才的场景。T1 读取 head 为 (A, v)。在它被暂停时，其他线程的操作将导致版本计数器随着每次更改而递增。当内存地址 A 被重新推入栈时，head 将是 (A, v+3) 或某个其他更高的版本。当 T1 醒来并尝试其 CAS(, (A, v), ...) 时，操作将会失败，因为当前版本 v+3 与其期望的版本 v 不匹配。幽灵被识破，数据损坏得以避免。
这个优雅的解决方案引入了一个实际的工程问题：版本标签需要多少位？如果标签计数器太小，它本身可能会回绕（例如，一个 4 位标签从 15 回到 0），从而使 ABA 问题可能再次出现，尽管可能性很小。我们实际上可以根据线程数量及其最大更新速率，计算出在系统预期运行寿命内保证不发生回绕所需的最小位数。这类计算揭示了架构的现实约束；对于给定的高性能工作负载，所需的标签位数在 32 位系统上可能不可行，但在 64 位字中则可以轻松容纳。
使用 CAS 的无锁算法因消除了死锁而备受赞誉。如果一个线程在操作中途被暂停，它不持有任何锁，因此不会阻塞任何其他线程。这保证了系统范围的进展，被称为无锁（lock-free）属性。
然而，这种自由是有代价的。无锁不等于无等待（wait-free）。理论上，一个不幸的线程可能会永远无法成功执行其 CAS 操作，而其他线程则不断成功。这种现象称为饥饿，它违反了有界等待——即保证一个线程只需等待有界数量的其他线程先行通过。
当许多核心试图同时对同一内存位置进行 CAS 操作时，即在高竞争下，这种风险就变成了现实。持有数据的单个缓存行在核心之间疯狂地“反弹”，每次传输都带来显著的延迟。单个核心在其自身成功操作之间必须等待的时间与竞争者的数量成线性关系。大多数 CAS 尝试都失败了，在徒劳的自旋中浪费 CPU 周期。
解决这种交通拥堵的实用方法是随机指数退避。当一次 CAS 失败时，线程不会立即重试。它会等待一个小的、随机的时间。如果再次失败，它会等待一个更长的随机间隔，依此类推。这个简单的策略巧妙地使线程的操作去同步化，减少了冲突，并使尝试更有效率。虽然它不能从理论上消除饥饿的可能性，但在实践中使其变得极不可能，并显著提高了整个系统的吞吐量，同时保留了无锁设计宝贵的非阻塞特性。
理解了比较并交换（CAS）操作简单、粗暴而优雅的本质后，人们可能会想：这仅仅是一个巧妙的技巧，一个供深奥程序员使用的工具吗？答案是响亮的“不”。CAS 是现代数字世界的无声主力。它是宏观并发软件杠杆所依赖的微观支点，使我们习以为常的速度和规模成为可能。
在本章中，我们将踏上一段旅程，看看这一条指令如何构建世界。我们将从平凡之事——预订一张机票——走向机器人技术和分布式计算的前沿，发现并发的挑战以及 CAS 提供的优雅解决方案是普遍存在的。
从本质上讲，CAS 允许我们创建一个具有牢不可破保证的数字对象。想象一下为数有限的飞机座位而发生的疯狂抢夺。系统如何保证一个座位一旦售出，就绝不会再次售出？一个非原子性的方法，即代理首先读取座位的状态然后写入其声明，注定会失败。两个代理可能几乎同时读取到“可用”，然后都继续声明它，导致航班超售。
CAS 提供了完美的、不可分割的裁决。要声明一个座位，代理只需执行 CAS(seat_status, AVAILABLE, my_id)。这是一个全有或全无的命令：如果座位确实可用，它会瞬间变成你的。如果不是，你的尝试就会失败。没有中间状态，没有其他代理可以干预的机会窗口。这提供了绝对的安全性保证，防止超售。
然而，虽然 CAS 是一个完美的仲裁者，但它并非一个公平的仲裁者。它保证有人会得到座位，但没有指定是谁。在对抗性条件下，一个不幸的代理理论上可能每次都输掉座位争夺战，导致饥饿。这种在确保正确性（安全性）和确保每个人都能取得进展（活性）之间的根本性张力是并发编程中的一个核心主题。
这种安全的、单向门的想法可以被推广。考虑一个试图保护自己免受过多请求冲击的 Web 服务。它可能会施加速率限制：每秒不超过 1000 个请求。一个共享计数器跟踪请求。一个简单的 counter = counter + 1 操作是一个经典的竞争条件。当多个线程递增计数器时，一些更新将会丢失，服务将允许远超预期的流量进入。
像 fetch-and-add 这样的原子指令（CAS 的近亲）干净地解决了这个问题。它的作用就像熟食店的取号机：它给你一个号码（你递增前的计数器值），并在一个不可分割的动作中更新主计数。一个线程调用 fetch-and-add，收到票号 k，如果 小于 1000 的限制，它的请求就被接受。这创建了一个严格的、不可博弈的预算，确保了系统稳定并防止过载。
有了安全更新单个内存位置的能力，我们能否构建更复杂的东西？我们能否不仅管理一个数字，还能管理一个动态的、不断变化的数据集合，比如列表或队列？这正是 CAS 大放异彩的地方，它构成了我们所谓的无锁数据结构的支柱。
让我们从一个简单的栈（后进先出，或 LIFO，结构）开始。“Treiber 栈”是一个经典的无锁实现。它看起来很简单：要推入一个新项，我们创建一个新节点，并使用 CAS 将共享的 head 指针指向我们的新节点。要弹出，我们读取当前的 head，找到其 next 节点，并使用 CAS 将 head 指针指向那个 next 节点。
但在这里，在指针和动态内存的世界里，我们遇到了基于 CAS 算法的巨大克星：ABA 问题。这是并发编程中最微妙、最深刻的错误之一。想象一个线程 T1，想要弹出一个项。它读取 head 指针，该指针指向内存地址 A 处的一个对象。在 T1 能够行动之前，系统暂停了它。在那稍纵即逝的瞬间，其他线程来了，弹出了地址 A 的对象，操作系统回收了它的内存。然后，命运弄人，系统为其他目的在完全相同的地址 A 处分配了一个新对象，而这个新对象被推入了栈！当 T1 最终醒来时，它查看 head 指针。它仍然看到地址 A。它的 CAS 操作 CAS(head, A, A-next) 成功了。但它刚刚操作了一个幽灵——一个恰好共享一个旧地址的完全不同的对象。数据结构现在很可能已被破坏。
我们如何与幽灵战斗？最优雅的解决方案是给我们的指针一个记忆，一段历史。这被称为版本化（versioning）或使用带标签的指针。我们不再只存储地址 A，而是存储一个对：(地址, 版本号)。每次我们成功更改指针时，我们都递增版本号。现在，当我们的可怜线程 T1 醒来时，它期望看到 (A, version 17)。但经过所有中间活动后，当前的 head 指针是 (A, version 18)。CAS 失败了，因为元组不匹配。幽灵被揭穿，正确性得以保留。这种强大的技术在构建其他基本并发工具时也至关重要，例如管理系统命脉的无锁内存分配器。
从栈，我们可以转向队列（先进先出，或 FIFO）。并非所有队列都是生而平等的。当我们能施加约束时，我们可以实现惊人的效率。对于一个单生产者、单消费者（SPSC）队列，一个线程只负责入队，另一个只负责出队。通过让他们操作独立的头指针和尾指针，我们可以设计一种算法，使他们的 CAS 操作永远不会相互干扰。这使得算法无等待（wait-free）——每个操作都保证在有界步数内完成，无论另一个线程在做什么。这是非阻塞进展的顶峰，在两个线程之间创建了一个极其快速和可靠的通信通道。
推广到多生产者、多消费者（MPMC）队列，如著名的 Michael-Scott 队列，又带回了竞争和 ABA 问题的复杂性，但同样的 CAS 和版本化工具包仍然适用。这些原则可以扩展，使我们能够构建一个庞大的无锁结构生态系统，甚至用于复杂的算法，如并行不相交集联合，其中内部启发式方法的选择（例如，路径分裂优于路径压缩）可以显著减少竞争下的 CAS 失败次数。
CAS 的影响力远远超出了构建数据容器。它为协调庞大、复杂的系统提供了一套词汇。
考虑一群被分配了大型计算任务（如绘制建筑物地图）的机器人。它们如何高效地让自己保持忙碌？如果一个机器人完成了它被分配的部分，它可以向一个中央协调器请求更多工作。但那个协调器是一个瓶颈。一个远为优雅的解决方案，在从机器人技术到高性能计算等领域都有使用，是工作窃取（work-stealing）。
每个机器人维护自己的待办事项列表，通常是一个双端队列（deque）。它从一端——“头部”——添加新子任务并获取其下一个任务。这是它的私人工作区。当一个空闲的机器人决定窃取时，它会悄悄地靠近一个忙碌机器人双端队列的另一端——“尾部”——并使用 CAS 抢走一个任务。
这里的精妙之处有两点。首先，所有者和窃贼在相反的两端操作，极大地减少了他们互相干扰的机会。其次，它深刻地尊重了计算的物理学：局部性（locality）。一个机器人最近添加的任务在其处理器缓存中是“热”的。通过从头部工作（LIFO），它能使其热数据保持就近。窃贼从尾部窃取最旧的任务（FIFO），这个任务很可能是“冷”的，并且已不在所有者的缓存中。这最大限度地减少了对受害者的性能干扰。这是由一条原子指令编排的美丽高效之舞。
当然，当许多空闲的机器人试图同时从同一个受害者那里窃取时会发生什么？你会得到一个由失败的 CAS 尝试组成的交通堵塞。解决方案出奇地人性化：礼貌。指数退避是一种策略，它告诉一个线程：如果你的 CAS 失败了，在再次尝试前等待一个随机的时间。如果再次失败，等待一个更长的随机时间。这错开了尝试的时间，缓解了竞争，并使系统能够优雅地恢复。
我们旅程的最后一站将我们从一台计算机带到整个地球。想象一个分布在各大洲的数据库。东京的一个节点和伦敦的一个节点都想更新同一条记录。一条消息穿越地球所需的时间在计算上是永恒的，这创造了终极的对抗性调度器。我们最初作为处理器线程间竞争遇到的 ABA 问题，在这里作为网络数据包间的竞争再次出现。东京的一个节点读取值 A，在它能发送更新之前，来自其他大洲的一系列活动将值更改为 B 然后又改回 A。
值得注意的是，解决方案是相同的。最稳健的分布式系统，必须提供强线性化一致性，它们使用带版本的值。要更新一条记录，客户端必须提供它上次读取的值和版本。系统对 (值, 版本号) 元组执行 CAS。这证明了并发的逻辑——从独立的观察中建立一个共享、一致的现实视图——是信息处理的一个普遍原则。围绕 CAS 构建的知识工具包，对于协调全球数据中心和管理单个硅芯片上的线程同样重要。
比较并交换不仅仅是一条指令；它是一个承诺。一个原子性的承诺，一个在混乱、并发世界中的确定性奇点。在这个简单的承诺之上，我们构建了定义我们这个时代的高耸、复杂和快得惊人的数字基础设施。它证明了一个简单、美丽思想的力量。
procedure push(newItem):
loop:
oldHead = read_current_head()
newItem.next = oldHead
if CAS(, oldHead, newItem) then
return // Success!
// CAS failed, another thread interfered. Try again.