测试并设置

在并发编程的世界里，确保共享资源被安全访问是一项至关重要的挑战。简单的操作在被多个线程同时执行时可能会灾难性地失败，从而导致竞争条件。为解决此问题，硬件提供了原始的、不可分割的操作。Test-And-Set 指令便是这些原子构建块中最基本的一种，它提供了一种看似直接的方法来创建锁并强制实现互斥。

然而，Test-And-Set 的表面简单性具有欺骗性。如果仅仅依赖这个原语而没有理解它与底层硬件和操作系统的深层交互，可能会导致系统不仅速度缓慢，而且在根本上是不正确或不安全的。本文旨在弥合原子指令的简单理论与构建健壮并发系统的复杂现实之间的鸿沟。

我们将首先剖析 Test-And-Set 的核心原理，展示其工作方式以及如何用它来构建一个基本的自旋锁。在“原理与机制”部分，我们将揭示这种简单锁背后隐藏的风险，从多核系统上的灾难性性能问题到微妙的内存可见性错误。然后，在“应用与跨学科联系”部分，我们将拓宽视野，探讨这些底层挑战如何在操作系统、设备驱动程序和大规模应用程序中表现为死锁和优先级反转等关键问题。通过这一旅程，您将了解到 Test-And-Set 不仅仅是一条指令，更是一个洞察现代系统设计中相互关联挑战的窗口。

想象一下，你和一位朋友正在用一块共享的黑板计票。你们都看到了当前的计票数，比如“7”，然后在脑海中各自加上自己的一票得到“8”，接着擦掉“7”写上“8”。如果你们俩在完全相同的时间这么做，会发生什么？你们都读到了“7”，都计算出“8”，然后都写上了“8”。投了两票，但计数只增加了一。这就是经典的​​竞争条件​​（race condition），并发编程中的一个根本性风险。

在计算机世界里，像 count = count + 1 这样的操作并非一步完成。它至少包含三个步骤：从内存中 load（加载）、一个 add（加法）操作，以及一个 store（存储）回内存。如果两个处理器核心试图同时执行此操作，它们的操作可能会交错进行，导致与黑板计票类似的错误。我们需要一种方法使这个操作序列变得​​原子化​​（atomic）——即表现得像一个单一、不可分割的瞬时步骤。

硬件设计者为此提供了一个强大而原始的工具：​​测试并设置（Test-And-Set）​​ 指令。可以把它想象成一种对内存进行的特殊“设置”操作。你告诉它：“将这个内存位置设为1（我们称之为‘已锁定’），但首先，告诉我你改变它之前的值是多少。”其神奇之处在于，硬件保证整个序列——读取旧值和写入新值——作为一个不可分割的单元发生。没有其他核心可以在“测试”和“设置”之间插入操作。

有了这个，我们就可以构建我们的第一个简单锁，即​​自旋锁​​（spinlock）：

获取锁：

释放锁：

这看起来异常简单。一个想要进入临界区（critical section）——我们比喻中的黑板——的线程会反复尝试“赢得”这个锁。如果它发现锁是0，就将其设置为1并进入。如果发现锁已经是1，它就在这场竞争中失败，并在while循环中“自旋”，一次又一次地尝试。这保证了​​互斥​​（mutual exclusion）：在任何时候，只有一个线程能够“赢得”竞争并持有锁。问题解决了吗？

并非如此。当我们层层深入时，会发现这幅简单的图景是危险且不完整的。

我们的自旋锁成功地阻止了两个线程同时处于临界区之内。但是，它能确保一个线程完成的工作能被下一个线程正确地看到吗？让我们考虑一个场景：线程$T_1$获取锁，写入x = 1，然后释放锁。紧接着，线程$T_2$获取同一个锁并读取x的值。$T_2$是否保证能看到x = 1？

直觉上的答案是“当然！”但在现代处理器上，答案却惊人地是“不一定”。处理器为了运行得更快会使用各种技巧，比如将写操作缓冲在本地的“存储缓冲区”（store buffer）中，或者对指令进行重排序。这可能导致$T_1$在主内存中更新锁变量的操作发生在其对x的写入对其他核心可见之前。于是，$T_2$可能获取锁，读取x，却看到旧值0。我们的锁提供了互斥，却没有提供数据​​可见性​​（visibility）。

这揭示了一个更深层次的原理：仅仅对锁变量进行原子操作是不够的。我们需要在锁操作与其保护的数据之间强制建立一种排序。为解决此问题，硬件提供了内存排序语义。其中最重要的两种是：

• ​​获取语义（Acquire Semantics）​​：一个具有获取语义的操作是一个屏障。在其后的代码中，任何内存读或写操作都不能被重排序到它之前发生。当你获取一个锁时，你希望确保能看到前一个所有者所做的所有更改。

• ​​释放语义（Release Semantics）​​：一个具有释放语义的操作也是一个屏障。在其前的代码中，任何内存读或写操作都不能被重排序到它之后发生。当你释放一个锁时，你希望确保你的所有更改在允许其他线程进入前都已变得可见。

一个正确的锁实现必须使用带有​​获取（acquire）​​语义的 test-and-set 进行加锁，并使用带有​​释放（release）​​语义的简单存储操作进行解锁。这种配对创建了一种“同步于”（synchronizes-with）关系。$T_1$在其释放操作之前所做的一切，都保证对$T_2$在其获取操作之后可见。原子性与内存模型之间这种微妙但至关重要的联系，是正确并发编程的真正基石。

现在我们有了一个正确的锁，但它是一个好锁吗？当许多不同核心上的许多线程试图同时获取我们的 test-and-set 自旋锁时，会发生什么？答案是一场性能灾难。

要理解原因，我们需要一个关于多核心如何共享内存的简单模型。每个核心都有自己的小型、高速内存，称为​​缓存​​（cache）。当一个核心需要写入某个内存位置时，缓存一致性协议（如常见的​​MESI​​协议）要求该核心拥有该数据的独占副本。如果其他核心拥有副本，它们必须被置为无效。这是通过在共享的系统总线或互连上传输消息来完成的。

我们那个朴素的 test-and-set 自旋锁让每个等待的线程都在一个紧凑的循环中执行 test_and_set(lock_variable)。记住，test-and-set 总是执行一次写操作。这意味着每个自旋线程的每一次尝试都构成一次写操作。每个自旋的核心都在大喊：“我需要对锁变量的独占访问权来写入它！”这会在总线上触发一个​​为获得所有权的读取（Read-For-Ownership, RFO）​​请求。

想象一下，当一个核心持有锁时，有15个核心正在自旋等待。核心A发出一个RFO请求，获取了缓存行，并执行了失败的 test-and-set。紧接着，核心B发出一个RFO请求，这会使核心A的副本失效，并将缓存行带到核心B。然后核心C也做同样的事情，依此类推。包含我们锁变量的单个缓存行在核心之间疯狂地传递，这种现象被称为​​缓存行乒乓​​（cache-line ping-ponging）。共享总线完全被这些一致性消息所饱和。CPU都处于100%的使用率，但它们只是在互相“喊叫”，没有取得任何有用的进展。

这些浪费的一致性消息的总数与竞争处理器的数量$P$成线性关系。对于单次锁的获取，缓存未命中的次数可能在$2(P-1)$的量级。 这是一个可扩展性的噩梦；你增加的核心越多，性能就越差。

一个常见的急救措施是​​测试并测试并设置（test-and-test-and-set, TTAS）​​锁。在这种方式下，线程首先在一个简单的读操作上自旋，读取锁变量。由于读取共享值不需要独占所有权，许多线程可以在它们本地的缓存副本上自旋，而不会产生总线流量。只有当一个线程看到锁的值变为0时，它才会尝试执行昂贵的 test-and-set。这是一个巨大的改进，但它并没有完全解决问题。当锁被释放时，所有等待的线程几乎同时看到它变为空闲，导致“惊群效应”（thundering herd），它们蜂拥而上执行 test-and-set，从而引发一阵争用风暴。

到目前为止，我们只考虑了硬件。当我们把操作系统（OS）的因素加进来时，情况会变得更糟。现代操作系统是抢占式的；它们可以在任何时候中断一个线程，让另一个线程运行。如果操作系统决定在一个线程持有我们的自旋锁期间抢占它，会发生什么？

这就是​​锁护航​​（lock convoy）的成因。 被抢占的线程$T_H$进入休眠状态，但仍然持有锁。所有其他等待该锁的线程现在都在一个不可能被释放的锁上自旋，直到操作系统最终决定再次调度$T_H$。在一个有很多线程的系统上，这可能是在几毫秒之后——对于CPU来说是永恒的时间。所有运行自旋线程的核心都被完全浪费了，它们燃烧着电力却一事无成。这种病态情况可能使整个系统陷入瘫痪。

如果持有锁的线程做了某些导致其长时间阻塞的事情，比如引发一个​​页错误​​（page fault），情况会更具灾难性。 如果临界区代码触及了不在物理内存中的数据，操作系统将阻塞该线程并从磁盘启动一个缓慢的I/O操作。现在，这个锁可能被持有数百万个CPU周期。在这种情况下，纯粹的自旋锁是毁灭性的，因为它将导致所有等待的核心在这整个期间内无用地自旋。

这引出了一条来之不易的智慧：​​纯自旋锁只应用于保护那些极短且保证不会阻塞的临界区。​​

我们的简单 test-and-set 锁已被证明充满了危险。它不仅效率低下，而且极不公平。在疯狂争抢一个被释放的锁时，无法保证等待时间最长的线程会获胜。完全有可能一对“幸运”的线程在它们之间来回传递锁，而一个“不幸”的线程则永远自旋，永远得不到机会。这被称为​​饥饿​​（starvation）。

幸运的是，我们可以使用简单的原子原语构建更好的锁。

为了解决公平性问题，我们可以设计一种​​票据锁​​（ticket lock）。其思想如同熟食店的柜台一样优雅：“取个号”。它使用两个计数器：next_ticket 和 serving_now。要获取锁，线程原子地增加 next_ticket 并将结果值作为其个人票号。然后它开始自旋，等待 serving_now 等于其票号。当一个线程释放锁时，它只需增加 serving_now。这强制执行了严格的先进先出（FIFO）顺序，保证了公平性并消除了饥饿。

为了解决缓存行乒乓的可扩展性问题，计算机科学家们设计了卓越的 ​​Mellor-Crummey and Scott (MCS) 锁​​。其见解是革命性的：停止在共享位置上自旋。相反，MCS锁构建了一个等待线程的链表。当一个线程想要锁时，它将自己添加到列表的末尾。然后，它在自己列表节点中的一个标志上自旋。这个标志是该线程本地的，因此自旋产生的总线流量为零。当当前的锁持有者完成时，它只需查看列表中的后继者，并翻转该后继者节点中的标志，从而有效地传递接力棒。每次锁获取的通信成本变为常数$O(1)$，与等待线程的数量无关。它公平、无饥饿，并且具有极佳的可扩展性。

我们与 test-and-set 的这段旅程揭示了计算机科学的一个缩影。我们从一个为解决根本问题而设计的简单、强大的硬件原语开始。然后我们发现了它微妙的缺陷——缺乏内存排序保证、在争用下的灾难性性能、与操作系统的危险交互。每一个缺陷都迫使我们更深入地探究，并建立起更复杂的理解层次，并最终构建出更精密的软件算法。从一条单一的原子指令中，我们看到了硬件架构、操作系统以及使并发计算成为可能的美妙算法之间相互交织的本质。

我们已经看到，一条简单的、原始的原子指令——测试并设置（Test-And-Set）——如何被用来构建一个锁，一个数字守门员，它一次只允许一个线程进入代码的“临界区”。这似乎是解决并发混乱的一个绝妙而简单的方案。它的确如此！但它也是一个极具欺骗性的解决方案。认为仅仅拥有这个原子工具就能解决我们所有的问题，就像相信拥有一块完美的砖头就足以建造一座大教堂一样。

构建正确且高效的并发系统的艺术和科学，不仅仅在于拥有原子“砖块”；它关乎架构、协议，以及对这些“砖块”所处环境的深刻、直观的理解。Test-And-Set指令是通向这个世界的一扇窗，通过它，我们可以看到最抽象的软件概念是如何与它们所运行的硅芯片的物理现实紧密相连的。让我们踏上一段旅程，探索其中一些联系，从操作系统的核心到现代计算的前沿。

操作系统是位魔术大师。它利用一个或少数几个CPU核心，就能变幻出成百上千个任务同时进行的假象。但当这些并发任务需要协调、共享某些信息时，各自独立的幻象便会破碎。它们必须相互协作，而我们的Test-And-Set自旋锁似乎是完美的裁判。

但请考虑最简单的情况：一个单CPU核心，操作系统在线程之间快速切换。一个“生产者”线程向共享缓冲区添加数据，另一个“消费者”线程从中移除数据。我们的自旋锁保护着这个缓冲区。假设生产者线程获取了锁。现在，如果操作系统决定进行上下文切换，转到消费者线程，会发生什么？消费者急于工作，试图获取锁。它执行Test-And-Set，发现锁已被占用，于是开始自旋，反复检查锁的状态。但这里存在一个深刻的悖论：唯一能够释放锁的线程是生产者，而它当前正处于休眠状态！消费者正忙于浪费其宝贵的CPU时间进行无用的自旋，等待一个在操作系统重新调度生产者之前绝不可能发生的变化。这就像守在电话旁，等待一个本该由自己拨打的电话。

这揭示了一个根本性的教训：在单核系统上，自旋锁通常是一种反模式（anti-pattern）。它的忙等待浪费了取得进展所必需的资源。在这种场景下，一个更好的方法是使用“休眠”互斥锁（sleeping mutex），等待的消费者线程会告诉操作系统：“当锁可用时唤醒我”，然后进入休眠，让出CPU，以便可以执行有用的工作——比如让生产者释放锁。。工具的选择完全取决于其应用场景。

现在，让我们给自己更多资源——多个CPU核心和多个锁。想象有两个线程$T_1$和$T_2$，以及两个资源$R_A$和$R_B$，每个资源都由其自己的自旋锁$L_A$和$L_B$保护。由于某个不幸的设计，$T_1$需要先获取$L_A$再获取$L_B$，而$T_2$则以相反的顺序获取它们，即先$L_B$后$L_A$。会发生什么？$T_1$可能成功抓取了$L_A$，而同一时刻，$T_2$抓取了$L_B$。现在，$T_1$持有$L_A$并自旋等待$L_B$。$T_2$持有$L_B$并自旋等待$L_A$。它们将永远自旋下去，陷入“死亡拥抱”。

Test-And-Set对单个锁的原子性在这里毫无帮助。它能确保你不能把两只手同时伸进同一个饼干罐，但它无法阻止两个人互相抓住对方的罐子，陷入永久的僵持。这就是经典的​​死锁​​（deadlock）问题。解决方案不在于原子指令层面，而在于更高层次的、架构性的协议层面。如果所有线程都遵守一个全局的“锁顺序”——例如，总是先获取$L_A$再获取$L_B$——那么这种循环依赖就变得不可能，死锁也就被避免了。。

当我们转向安全关键的实时系统时，比如机器人手臂的控制器，风险会变得更高。在这里，紧急停止线程必须能够立即行动。想象一下，这个高优先级线程需要获取一个自旋锁来停止手臂，但一个低优先级的工作线程已经持有了那个锁。更糟糕的是，为了确保其更新是原子的，低优先级线程暂时禁用了抢占。在单核系统上，结果将是灾难性的。高优先级的紧急线程已准备好运行，但操作系统被禁止停止低优先级线程。紧急操作被阻塞了，不是被同级任务阻塞，而是被系统中最不重要的任务阻塞了。这种危险情况被称为​​优先级反转​​（priority inversion）。响应紧急情况的延迟现在由任何工作线程的最长临界区决定。再一次，Test-And-Set原语按预期工作，但其周边的协议却制造了安全隐患。。

计算机不是一个封闭的宇宙。它必须通过设备与外部世界互动：网络、磁盘、传感器。这种通信通常是运行在CPU上的软件与自主硬件之间的一场精妙的舞蹈。

考虑一个网卡的设备驱动程序。网卡接收数据包，并使用一种称为直接内存访问（Direct Memory Access, DMA）的技术将它们直接写入主内存，同时更新一个“写指针”以告知驱动程序新数据已到达。不同CPU核心上的多个驱动程序线程使用Test-And-Set自旋锁来协调由谁来处理这些数据包。自旋锁正确地确保了在任何时候只有一个CPU核心处理数据包队列。但这还不够。

一个CPU核心如何知道它看到的是设备写入的绝对最新的数据？现代CPU和内存系统充满了各种技巧，如缓存和重排序，以提高性能。CPU可能会从其本地缓存中读取到一个过时的写指针值。或者，它可能在看到指针所指向的实际数据包数据之前就看到了更新后的写指针！这将是灾难性的。Test-And-Set对锁变量的原子性，对于强制其他不相关内存位置（如数据包缓冲区）的顺序或可见性毫无作用。要跨越CPU世界和设备世界之间的鸿沟，我们需要更强大的工具：​​内存屏障​​（memory barriers），这是一种特殊的指令，它告诉处理器“在开始任何新操作之前，完成所有先前的内存操作”。我们可能还需要执行显式的缓存管理，告知CPU使其过时的缓存失效并从主内存中获取新数据。简单的锁只是CPU、内存系统和外部设备之间复杂契约的一部分。。

这引出了一个更普遍的真理。想象一个嵌入式系统，其中软件线程使用自旋锁来安全地更新控制GPIO引脚的硬件寄存器。但是，如果还有一个硬件定时器，一个“流氓代理”，它自主地修改同一个寄存器呢？软件线程礼貌地排队，检查锁。而硬件定时器完全无视这个软件社会契约，随时随地闯入并写入寄存器。一个持有锁的软件线程所做的更新，可能会被定时器立即覆盖。锁是一种协议，它只约束那些同意遵守它的人。。

在操作系统和硬件之上，我们构建了庞大的应用世界，如数据库和机器学习框架。这些应用程序通常更喜欢自己管理并发，使用我们的基本原语作为构建块。

在数据库中，可能同时发生数千个事务。为防止它们相互干扰，数据库可能会使用自旋锁来保护单个数据行。如果发生死锁——两个事务各自等待对方锁定的行——操作系统对此一无所知。对操作系统来说，这两个数据库线程并未阻塞；它们在主动自旋，消耗CPU。这得由数据库引擎自己通过构建“等待图”（wait-for graph）来寻找依赖循环，从而检测到这种情况。保证正确性的责任已经从操作系统向上转移到了应用程序。。

随着我们转向大规模多核系统，焦点从仅仅追求正确性转向了追求原始性能。在这里，对Test-And-Set的朴素使用可能是一场无形的灾难。考虑一个机器学习工作负载，其中几十个线程正在训练一个共享模型。每个线程计算一个梯度，然后短暂地锁定模型以应用其更新。一个朴素的自旋锁在一个紧密循环中使用test-and-set。在多核机器上，这相当于房间里几十个人同时大喊“轮到我了吗？”。test-and-set是一个写操作。在一个缓存一致性系统中，一个自旋核心对锁变量的每一次写入都会使所有其他核心缓存中的副本失效，从而在内存总线上引发一场隐藏的流量风暴。这就是​​惊群​​（thundering herd）问题。对于一个耗时几毫秒的单次初始化，这种朴素的自旋可能导致数百万次不必要且昂贵的缓存失效，使系统陷入瘫痪。。

解决方案是更智能地等待。一种改进的策略是“测试并测试并设置”（TTAS），即线程首先在一个简单的读操作上自旋。这就像在尝试发言前，先静静地听着房间里是否安静下来。在锁被释放之前，总线保持安静。当锁被释放时，所有等待的线程都试图同时发言，但这种嘈杂是短暂的，而不是持续的。最终的解决方案是组织起来。基于队列的锁，如MCS锁，让每个等待的线程排成一个有序的队伍。每个线程得到一个“票号”，并在一个私有变量上自旋，实际上只关注排在自己前面的人。当锁被释放时，它会通过一次精准的“拍肩”优雅地传递给队伍中的下一个人。总线保持宁静，性能也得到了极佳的扩展。。

最后，我们来到了硬件设计的前沿，在这里我们简单的锁与更高级的功能，如硬件事务内存（Hardware Transactional Memory, HTM）相互作用。HTM是一种基于硬件的乐观主义：CPU尝试在没有锁的情况下推测性地执行一个临界区，只有在发生实际冲突时才中止。如果中止次数过多，它会“回退”到使用传统锁。在这里，我们发现了一个美妙的悖论。如果回退机制是一个朴素的Test-And-Set自旋锁，那么自旋的线程会不断地写入锁变量。一个正在检查锁状态作为其推测一部分的事务线程，会将这些写操作视为冲突并中止。我们的回退机制，本意是作为一种保障措施，却变成了阻止我们乐观事务成功执行的破坏者。。

从一条简单的指令出发，我们的旅程带领我们穿越了操作系统的设计、硬件I/O的复杂性、数据库的架构，以及处理器设计的最前沿。Test-And-Set指令不是一个答案，而是一个问题。答案取决于你是在单核还是多核上运行；是与软件还是与硬件对话；是优先考虑正确性、安全性还是速度。它的美不在于其自身简单、不可分割的动作，而在于它挑战我们去构建的那个广阔而复杂的协作系统世界。