PDF非阻塞算法和可扩展多核编程
探索基于锁的同步的一些替代方案
Samy Al Bahra，AppNexus
具有复杂服务质量保证的现实世界系统可能需要在吞吐量和延迟之间取得微妙的平衡，以经济高效的方式满足运营要求。商品化多核和众核系统的日益普及和成本降低使得并发和并行对于满足苛刻的性能要求变得越来越必要。不幸的是，设计和实现正确、高效且可扩展的并发软件通常是一项艰巨的任务。
商品化多核处理器上的并发系统通常依赖于基于锁的同步来保证共享可变状态的一致性。然而，基于锁的同步存在一些局限性，包括对抢占的敏感性和死锁的可能性，这使其在某些环境中不适用或不切实际。但这并不意味着基于锁的同步是设计和实现高效且可扩展软件的障碍。
非阻塞同步可用于构建可预测且具有弹性的系统，同时避免基于锁的同步的问题。这类同步并非万能灵药，尤其是在最初定义其性能特性的抽象模型之外。与基于锁的同步相关的几个性能瓶颈和错误条件仍然存在（尽管以更模糊的形式存在）；因此，确保正确性需要更复杂的验证方法，并且在某些情况下，非阻塞算法需要采用复杂的支持系统。这些复杂性经常使非阻塞同步成为炒作、恐惧、不确定性和怀疑的受害者。本文旨在使读者掌握所需的知识，以识别从非阻塞同步中获益的情况。
通用原则
在详细阐述采用非阻塞数据结构的典型动机之前，本节重点介绍一些重要原则，以理解传统线程模型中多处理器系统上的可扩展性。基于锁和非阻塞同步都具有性能特征，这些特征是这些原则的函数。已经非常熟悉缓存一致性多处理器、乱序执行以及基于锁的同步对象的设计和实现的从业人员可能希望跳过本节。虽然本节绝非详尽无遗，但已提供了其他参考资料。Paul E. McKenney 概述了一种选择合适的基于锁的同步机制的方法19，之前的文章中也描述了其他通用原则。6,15,21
争用抑制可扩展性
并行应用程序中共享对象的争用是可扩展性和可预测性的主要障碍。无论使用何种更高级别的同步机制，共享对象的争用都涉及底层运行时环境的某种形式的序列化，无论是语言运行时还是共享内存多处理器。
利特尔法则 (L = λW) 是排队论的基本结果，可用于更好地理解争用对序列化资源的影响。该定律指出，系统中平均未完成请求数 (L) 是请求的有效到达率 (λ) 和平均请求完成时间 (W) 的乘积。争用是共享资源的请求有效到达率的产物，会导致排队效应，直接影响系统的响应能力。
无论使用哪种同步方案，共享数据的争用都会抑制并行应用程序的可扩展性和可预测性（在延迟和有时吞吐量方面）。程序设计者有责任在系统层面最大限度地减少争用，以实现更高的性能。所选择的同步范式，无论是基于锁的还是非阻塞的，在存在争用的情况下都会表现出性能下降。
共享可变状态和争用
理解多处理器上提供一致性保证的机制是理解此类系统上争用的先决条件。缓存一致性协议是保证跨多个缓存一致性处理器共享状态最终一致性的主要机制。这些协议在缓存行级别实现一致性保证，缓存行是缓存写入和读取主存储器的单元（至少从一致性机制的角度来看）。
商品处理器上三种主要的缓存一致性协议——MOESI、MESI 和 MESIF——它们的缩写词来源于它们为缓存行定义的状态：已修改 (Modified)、已拥有 (Owned)、
独占 (Exclusive)、共享 (Shared)、无效 (Invalid) 和转发 (Forward)。缓存一致性协议在内存一致性机制的帮助下管理这些状态，该机制保证共享内存的最终一致性。图 1 说明了与 MOESI 协议相关的状态机。1 您可以将探测转换解释为由来自其他内核的外部内存访问触发的转换。
以下示例说明了缓存一致性多处理器中共享读写操作的生命周期。为了简洁起见，与此生命周期相关的状态机已得到简化。此程序派生一个线程，该线程读取一个已修改的变量
volatile int x = 443;
static void *
thread(void *unused)
{
fprintf(stderr, "Read: %d\n", x);
return NULL;
}
int
main(void)
{
pthread_t a;
x = x + 10010;
if (pthread_create(&a, NULL, thread, NULL) != 0) {
exit(EXIT_FAILURE);
}
pthread_join(a, NULL);
return 0;
}
该示例假设所使用的一致性机制是总线窥探，它允许任何处理器监视对共享位置的任何内存访问。系统的初始状态如下所示。有两个插槽，每个插槽有一个内核和一个 256 字节的 L2 直接映射写回缓存，缓存行大小为 64 字节。（参见图 2）。
该进程最初在内核 0 上执行。假设变量的地址x是0x20c4。将值 10010 递增到x (x = x + 10010;)可以分解为三个操作
• 从内存加载x到 CPU 寄存器中。
• 将寄存器递增 10010。
• 将寄存器的值存储到x.
的内存位置中。x是0x20c4的地址，并哈希到缓存行 3。由于此缓存行处于已修改状态，并且包含来自不同地址的数据 (0x00c0)，因此必须将其写回主存储器。没有其他插槽包含0x20c4的缓存行，因此将 64 字节块（从0x20c0开始）从主存储器读入缓存行 3，并设置为独占状态（参见图 3）。存储到x会将缓存行从独占状态转换为已修改状态，如图 4 所示。
新线程派生并最终开始执行thread函数。假设此执行发生在内核 1 上。thread函数执行从x的地址加载，作为fprintf函数调用的输入。此加载会发出读取探测，需要从已修改状态转换为已拥有状态（参见图 5）。MOESI 允许缓存到缓存的数据传输，如果探测延迟低于到主存储器的延迟，则这是一个优势。在此特定配置中，此操作涉及通常是更高延迟内存互连上的探测（到插槽内缓存访问的更高延迟）。与探测相关的延迟也是拓扑的函数。在具有不对称互连拓扑的更大规模机器上，内存访问可能存在显着的性能不匹配；某些插槽可能需要一个跃点才能进行无效周期，而其他插槽可能需要两个或更多跃点。
缓存友好的程序（能够以最小的一致性流量将共享状态保留在缓存中的程序）在现代缓存一致性多处理器上可以很好地扩展。对主动共享状态的修改直接导致争用，因为缓存控制器会调解缓存行的所有权。
一致性粒度
如前所述，缓存行是在缓存一致性多处理器系统上维护一致性的粒度。这也是争用的单位。如果逻辑上不同的可变对象共享同一个缓存行，则对这些对象的操作会表现出争用，并可能成为可扩展性瓶颈。这称为伪共享。
考虑以下 C 代码片段。每个线程都提供一个唯一的索引 (UNIQUE_THREAD_ID) 到计数器数组中，每个线程都从中读取和写入。由于这些计数器在内存和缓存中顺序布局，因此缓存行所有权在所有递增计数器值的处理器之间来回切换。这种无效/共享/已修改/已拥有缓存行转换的恶性循环是可能由于伪共享而发生的缓存行乒乓效应的一个示例。
#define N_THR 8
struct counter {
unsigned long long value;
};
static volatile struct counter counters[N_THR];
void *
thread(void *unused)
{
while (leave == false) {
counters[UNIQUE_THREAD_ID].value++;
}
return NULL;
}
避免此问题的一种方法是保证给定缓存行中最多只有一个计数器，方法是填充到缓存行大小。假设应用程序的主机处理器具有 64 字节的缓存行，则以下修改可以避免伪共享
struct counter {
unsigned long long value;
char pad[64 - sizeof(unsigned long long)];
};
同样，只有在必要时才应进行填充。记住访问模式仍然很重要。例如，如果在热路径（即，最频繁执行的代码段）上连续获取两个互斥锁，则缓存行填充几乎无济于事，只会增加锁操作延迟。过度填充可能会影响应用程序的总体内存占用，从而增加内存资源压力。还存在其他方法来检测和最大限度地减少伪共享。16,17,19 在现代架构上，应用于缓存内存位置的原子操作依赖于缓存一致性协议来确保原子性。较旧的系统仅依赖总线锁定来提供此类原子性保证。在缓存行无效步骤之后，总线锁定信号断言会阻止所有处理器进一步访问主存储器和从主存储器访问。这可能会导致系统范围内的性能显着下降。避免跨越缓存行边界的原子操作。即使目标架构支持它，它也可能通过某种形式的总线或目录锁定来实现。例如，在 x86 架构上，此类原子拆分事务被定义为断言总线锁定信号。
排序和可见性保证的不可避免的成本
某些正确性要求需要使用比原子加载和存储更重的同步指令。为了提高性能，许多现代处理器批量处理内存操作和/或提供某种形式的指令级并行性。这些优化的存在可能需要使用内存屏障（或串行化）指令来强制执行内存操作及其预期副作用的排序。（术语内存屏障可以与内存栅栏互换使用。）对屏障指令的需求取决于处理器内存模型，该模型也定义了内存操作的重新排序可能性。
考虑以下源代码片段
volatile int w, x, y, z;
w = 0;
x = 1;
z = y;
在顺序一致性模型下，指令（包括加载和存储）按顺序执行。对x的存储发生在对w的存储之后，并且发生在从y到z的加载之前。能够一次处理多个加载或存储的现代处理器通常对这些操作的排序施加更宽松的约束，以提高性能。一些现代架构甚至实现了无死锁缓存2，它可以并行处理多个缓存未命中，同时仍然允许缓存访问。例如，从y的加载可能在对x的存储之前得到服务，或者对x的存储可能在对w的存储之前执行。即使在没有指令重新排序的情况下，远程处理器仍然有可能在某些架构上看到对z的存储早于对w的存储。这是一个不太无害的例子
volatile int ready = 0;
void
produce(void)
{
message = message_new();
message->value = 5;
message_send(message);
ready = 1;
}
void
consume(void)
{
while (ready == 0) {
; /* 等待 ready 变为非零。 */
}
message = message_receive();
result = operation(&message->value);
}
在此伪代码中，在专用处理器上执行的生产者线程创建一个消息，然后通过更新ready来向另一个处理器上的专用消费者线程发出信号。在没有内存屏障的情况下，执行consume的处理器有可能在对ready的远程存储完成和/或对其他处理器可见之前接收或处理对message->value的远程存储。为了保证produce在message->valueready = 1操作之前提交对的存储，可能需要内存屏障。然后，为了保证在消费者在非零状态下观察到consume之后，在ready中接收到的消息包含在随附的操作之前提交对操作（在produce中）之前的任何内存更新，可能需要另一个内存屏障
volatile int ready = 0;
void
produce(void)
{
message = message_new();
message->value = 5;
message_send(message);
/*
* 确保上述内存操作在
* 任何后续内存操作之前完成。
*/
MEMORY_BARRIER();
ready = 1;
}
void
consume(void)
{
while (ready == 0) {<
; /* 等待 ready 变为非零 */
}
/*
* 确保我们相对于 ready 变量的更新具有最新的内存视图。
* 确保我们相对于 ready 变量的更新具有最新的内存视图。
*/
MEMORY_BARRIER();
message = message_receive();
result = operation(&message->value);
}
某些处理器具有专门的屏障指令，这些指令仅保证某些内存操作的部分排序（示例包括仅对彼此串行化存储，或仅对彼此串行化加载）。对内存屏障的要求取决于底层内存模型。现代通用处理器上最常见的内存排序保证是
TSO（总存储排序）
• 加载操作不会相对于彼此重新排序。
• 存储操作不会相对于彼此重新排序。
• 存储操作不会相对于先前的加载操作重新排序。
• 加载操作可以相对于先前的存储操作重新排序。
• 对同一位置的存储操作具有全局排序。
• 原子操作是串行化的。
• 示例包括 x86 TSO26 和 SPARC TSO。
PSO（部分存储排序）
• 加载操作不会相对于彼此重新排序。
• 存储操作可以相对于彼此重新排序。
• 加载操作可以相对于存储操作重新排序。
• 对同一位置的存储操作具有全局排序。
• 原子操作可以相对于存储操作重新排序。
• 示例包括 SPARC PSO。
RMO（宽松内存排序）
• 加载操作相对于彼此重新排序。
• 加载操作可以相对于存储操作重新排序。
• 存储操作可以相对于彼此重新排序。
• 对同一位置的存储操作具有全局排序。
• 原子操作可以相对于存储和加载操作重新排序。
• 示例包括 Power27 和 ARM。7
同样，Paul McKenney 提供了有关这些内存模型的更多详细信息。19
更糟糕的是（就复杂性而言），某些语言允许其编译器和运行时环境重新排序操作。直到最近，即使是 C 和 C++ 也缺乏并发内存模型（因此并发访问的语义在很大程度上取决于编译器和环境）。许多编程语言可能会通过获取/释放语义专门发出内存屏障。内存模型及其含义将在即将到来的 文章中更详细地探讨。
流行的基于锁的同步机制通过具有隐式的重量级内存屏障，向程序设计者隐藏了内存屏障的细节。这简化了并发程序，因为开发人员只需推理可串行化性3，但有时会以降低性能为代价。
内存屏障对于许多其他并发算法也是必要的，尤其是那些不依赖锁及其排序保证的算法类。最终，避免重量级同步机制的能力取决于数据结构的正确性和可见性要求。最近，在常见访问模式存在的情况下，某些正确性约束对昂贵的同步指令的要求已被形式化。4
原子读-修改-写操作成本高昂
原子读-修改-写操作的成本取决于底层架构和实际编程语言实现。TSO 正变得越来越普遍的商品处理器内存模型。除其他外，此内存模型将原子操作定义为具有总排序。即使在没有争用的情况下，此保证也需要付出巨大的代价。表 1 说明了原子 CAS（比较并交换）操作 (lock cmpxchg) 与常规 CAS 操作 (cmpxchg) 的非争用吞吐量。原子 CAS 可以提供跨多个处理器的总排序和原子性保证，而常规 CAS 则不能。这些测量是在 2.30 GHz 的 Intel Core i7-3615QM 上进行的，包括寄存器溢出的开销。
在 TSO 架构上，这些原子操作意味着重量级内存屏障语义。即使在内存模型较弱的架构上，原子操作也可以通过复杂指令来实现，这些指令会在流水线中产生长依赖链的成本。在其他情况下，编程语言本身可能会定义这些指令的总排序，这可能会导致发出不必要的重量级内存栅栏。原子操作应仅在必要时使用。在大多数架构上，原子读-修改-写指令的成本很高（相对于其他指令）——即使在没有争用的情况下也是如此。
在决定使用原子操作之前，请考虑实际原子实现的进度保证。例如，某些依赖 LL/SC（加载链接/存储条件原语）的架构（如 ARM 或 Power 架构）即使在没有争用的情况下，仍可能使应用程序容易受到外部干扰（抖动）的影响，例如抢占。
利用原子操作库提供的获取语义。如果平台提供原子获取并递增操作或返回先前值的 CAS 操作，请使用它。
int shared_flag = 0;
void
worse(void)
{
int old_value = 0;
/*
* 在争用下，这可能涉及写入无效
* 然后转换为共享状态（至少
* 两次探测）。
*/
while (atomic_cas(&shared_flag, old_value, 1) == false) {
old_value = atomic_load(&shared_flag);
}
}
void
better(void)
{
int old_value = 0;
int snapshot;
while (true) {
/*
* 我们生成单个写入周期来检索
* 我们正在比较的值。这可以减少
* 缓存一致性流量至少 50%，与
* 之前的 worse() 使用模式相比。
*/
snapshot = atomic_cas_value(&shared_flag, old_value, 1);
/* 操作已完成，退出循环。 */
if (old_value == snapshot)
break;
old_value = snapshot;
}
}
警惕拓扑
内存访问的延迟和吞吐量属性因内存访问的类型而异。例如，访问远程缓存中的内存可能比访问本地未缓存的内存更便宜，而访问远程未缓存的内存比访问本地未缓存的内存更昂贵。表 2 显示了在 2.27 GHz 的双插槽 12 核 Intel Xeon L5640 机器上点对点唤醒的延迟。延迟以 CPU TSC（时间戳计数器）滴答声为单位进行测量。在一种场景（本地）中，一个内核上的线程向同一插槽上另一个内核上的线程发出信号。在第二种场景（远程）中，一个插槽上的线程向另一个插槽上的线程发出信号。远程场景包括通过内存互连的开销。这种性能不对称性是非可忽略的 NUMA（非均匀内存访问）因素的一个示例。NUMA 因子越高，这种不对称性越高。优化跨内核共享的对象的放置可以最大限度地减少 NUMA 效应。例如，如果共享状态由单个插槽上的一组线程访问，则该对象没有理由包含在远程内存中。
如果对象在系统上的多个插槽之间共享，请确保对象位于根据工作负载最大限度地减少到尽可能多内核的跃点距离的位置。默认情况下，NUMA 感知内核（如 Linux 或 Solaris）在确定内存页放置时具有首次访问策略。页面的放置由首次访问它的线程在 NUMA 层次结构中的位置决定。此行为是可配置的。24,25
非 NUMA 感知的同步对象也可能容易受到 NUMA 效应的影响。这些效应不仅表现为内核之间快速路径性能不匹配，而且还表现为负载下的饥饿甚至活锁。
表 3 显示了在同一插槽（本地场景）上执行的两个线程的单个自旋锁上的锁-解锁操作的吞吐量，以及在不同插槽（远程场景）上的相同行为。测量单位是 a/s（每秒获取次数）。远程场景显示饥饿现象急剧增加。
公平锁以增加抢占敏感性为代价来保证无饥饿性。这些锁的变体还允许可扩展的点对点唤醒机制。最近，锁队列被开发为一种通用方法，允许锁中的 NUMA 感知，但代价是更高的快速路径延迟。10 其他 NUMA 感知变体也存在于流行的原语中，例如读写锁。5,18
可预测性至关重要
可预测性是需要严格延迟或吞吐量限制的高性能并发应用程序中令人向往的属性。同步机制的进度保证定义了在存在争用和不可预见的执行延迟（可能包括抖动）时的行为。如果程序仅为快速路径而设计，那么执行和/或工作负载中的微小干扰可能会复合导致不可预测的低性能。
许多同步原语依赖于自适应方案来等待资源可用性。例如，许多互斥锁实现使用忙等待（轮询）一段有限的时间，然后回退到更重的轮询或异步信号设施（示例包括futex在 Linux 上，或 FreeBSD 上的有界 yield 和 sleep）。除其他外，这些语义允许在协同编程（同一内核上的多个进程）、负载下的公平性和改进的能源配置文件方面实现更好的系统范围响应。也就是说，它们在特定的执行历史记录下可能会表现出高操作延迟峰值。与更简单的忙等待机制相比，即使在无争用的执行中，它们也可能具有增加的恒定延迟开销。虽然系统的延迟配置文件在低争用情况下可能是可以接受的，但在即使是中等程度的争用或外部延迟下，情况也可能很快变得不稳定。
依赖于阻塞同步的系统可能尤其容易受到执行延迟的影响。持有同步对象的线程中的显着延迟会导致所有其他等待同一同步对象的线程的显着延迟。此类执行延迟的示例包括进程抢占和定时器中断。这些延迟的重要性取决于应用程序的延迟约束。如果应用程序需要处于微秒延迟范围内，那么即使是网络中断也可能很重要。在通用处理器和操作系统上，隔离所有外部延迟源很困难。如果对依赖于快速路径中阻塞同步的程序有严格的延迟要求，请考虑最大限度地减少外部干扰（实时调度策略和中断重定向很常见）。对于每次干扰都很重要的时间尺度，存在专门的实时操作系统和硬件来应对这些挑战。
非阻塞同步
在查看采用非阻塞数据结构的原因之前，本节介绍一些术语，并简要检查与非阻塞数据结构的实际设计、实现和应用相关的复杂性。
在文献中，非阻塞同步和非阻塞操作分为三类主要算法，每类算法都具有独特的进度保证集
• OF（无障碍性）。 该算法在不存在冲突操作的情况下提供单线程进度保证。
• LF（无锁性）。 该算法提供系统范围的进度保证。保证至少有一个操作的活动调用在有限的步骤数内完成。不保证无饥饿性。
• WF（无等待性）。 该算法提供按操作的进度保证。每个操作的活动调用都在有限的步骤数内完成。在没有过载的情况下，保证无饥饿性。
这些类算法具有总排序，因此任何无等待算法也是无锁且无障碍的；任何无锁算法也是无障碍的。非阻塞数据结构实现的操作满足非阻塞层次结构（如前所述）中针对某些（或无限）并发级别的进度保证。13 可以实现为有限数量的读者或写者提供非阻塞进度保证的数据结构。这方面的一个传统示例是 Michael Scott 的双锁队列，它在存在最多一个并发入队和一个并发出队操作的情况下提供无等待进度保证。23
数据结构也可以为不同的操作集实现不同的进度保证。示例包括具有多消费者阻塞出队操作的无等待入队操作，如 URCU（用户空间读取-复制-更新）库 (http://lttng.org/urcu) 中所见，以及具有单生产者无等待入队和多消费者无锁出队的有界 FIFO（先进先出），如 Concurrency Kit 库 (http://concurrencykit.org/) 中所见。
状态空间爆炸
非阻塞数据结构依赖于原子加载和存储或更复杂的原子读-修改-写操作。所使用的机制取决于数据结构打算支持的并发级别及其正确性要求。4,13 在基于锁的同步中，通常足以根据锁定依赖性和临界区（以及用于非对称基于锁的同步（如读写锁）的读端或写端临界区）进行推理。3 当在没有临界区的情况下（例如在非阻塞算法中）推理并发算法的正确性时，涉及共享变量交互的执行历史的数量可能是巨大的。对于仅仅通过基于状态的推理来严格穷尽此状态空间而言，人类可能会很快感到力不从心。考虑以下程序
int x = 1;
int y = 2;
int z = 3;
void
function(void)
{
/*
* 这会返回一个唯一的整数值
* 针对每个线程。
*/
int r = get_thread_id();
atomic_store(&x, r);
atomic_store(&y, r);
atomic_store(&z, r);
}
假设此程序由两个线程在实现 TSO 的内存模型下执行，如果仅考虑这三个存储操作——并认为它们完全统一且确定——则大约有 20 种可能的执行历史。对于四个线程，存在 369,600 种不同的执行历史。推导表明，对于具有 M 个不同动作的 N 个确定性进程，存在 (NM)! / (M!)N 种执行历史。28 加上编程语言重排序的可能性、处理器内存重排序的可能性以及乱序执行，状态空间将以更快的速度增长，变得更加复杂。
验证非阻塞算法（尤其是无等待和无锁类算法）的正确性，需要充分理解程序的基础内存模型。理解内存模型的重要性怎么强调都不为过，特别是当模型本身没有精确定义或允许依赖于机器或编译器的行为时（例如 C 或 C++ 等语言的情况）。看似微不足道的内存模型细节实际上可能违反程序的正确性。让我们仔细看看以下 C 代码片段
void
producer_thread(void)
{
message_t *message;
message = message_create();
memset(message, 0, sizeof *message);
send_to_consumer(message);
}
void
consumer_thread(void)
{
message_t *message;
message = message_receive();
/*
* 如果消息对象的任何内容为非零，则消费者线程可能会以错误的方式运行。
* 如果消息对象的任何内容为非零，则消费者线程可能会以错误的方式运行
* 对象的内容为非零值。
*/
assert(message->value == 0);
}
假设send_to_consumer仅由加载和存储操作组成，不包含任何串行化指令。在实现 TSO 的 x86 处理器上，对内存位置的存储操作会按顺序提交，但有一些例外。假设memset函数仅由常规存储指令组成，那么consumer_thread中的断言不应失败。但现实情况是，某些指令、操作和内存类型不能保证符合 x86 TSO 模型。26 在示例中，memset函数可以使用高性能的非临时和/或向量化存储指令来实现，这些指令会违反通常的内存排序语义。有必要确定编译器或标准库实现以及目标平台是否保证相对于memset的内存存储串行化。幸运的是，大多数（但并非全部）流行的memset实现使用这些指令时会发出某种内存屏障（通过默认约定），但这并非强制要求。如果您正在用低级语言设计无锁并发程序，请准备好探索类似的实现定义行为的黑暗角落。
正确性
对于非阻塞数据结构和操作，最常见的正确性保证是线性化。这要求操作看起来在它们的调用和完成之间的某个时间点原子性地完成。操作的线性化点是操作看起来已原子性完成的瞬间。这有助于根据数据结构的顺序规范来推理线性化点。由于上一节中描述的原因，证明算法的线性化通常并非易事。
为固定的并发级别专门化非阻塞数据结构可以大大降低状态空间的复杂性。然而，考虑到非阻塞并发算法的潜在状态空间大小，更高级的测试和验证方法对于验证是必要的。Mathieu Desnoyers 在本期 其他文章 "证明非阻塞数据结构的正确性" 中更深入地介绍了其中一些技术。
非托管语言的困境
缺乏对自动内存管理内置支持的语言（如 C 和 C++）需要专门的技术来管理动态分配的无锁对象。（对于那些计划专门使用具有自动内存管理的语言（如 Java 和 C#）的人来说，本节可能无关紧要。）
一种流行的减少基于锁的同步中的争用的方案涉及将对象的活跃性与其可达性解耦。例如，使用基于锁的同步的并发缓存实现可能具有一个互斥锁来保护缓存，但具有单独的互斥锁来保护对缓存中包含的对象的并发访问。此方案通常使用带内引用计数器实现
cache_t cache;
object_t *object;
object_t *
cache_lookup(int key)
{
object_t *object;
lock(cache);
/* 返回与该键关联的对象。 */
object = cache_find(key);
/* 未找到与该键关联的对象。 */
if (object == NULL) {
unlock(cache);
return NULL;
}
/*
* 递增引用计数器，该计数器在插入缓存时初始化为
* 1。
*
* 实际的引用计数器包含在或带内
* 它正在引用的实际对象。
*/
atomic_increment(&object->ref);
unlock(cache);
return object;
}
/* 从缓存中删除对象。 */
void
object_delete(object_t *object)
{
lock(cache);
cache_remove(object);
unlock(cache);
/* 删除缓存引用。 */
object_delref(object);
}
void
object_delref(object_t *object)
{
int new_ref;
/*
* 原子性地递减参数指向的整数
* 并返回新递减的
* 值。
*/
new_ref = atomic_decrement(&object->ref);
if (new_ref == 0) {
/*
* 如果引用计数为 0，则对象
* 不再可达，并且当前未被
* 其他线程使用，因此可以安全地
* 销毁它。
*/
free(object);
}
}
此方案允许并发访问从缓存中获取的对象，同时仍然允许并发获取继续进行（尽管请注意，由于引用计数器的争用，它可能无法为高频率、短寿命的事务扩展）。该方案在当前示例中有效，因为对象的可达性是相对于引用计数器以原子方式管理的。换句话说，永远不会出现引用计数为 0 且对象仍在缓存中的状态。如果仍然存在对对象的引用，则永远不会销毁该对象。在这种情况下，引用计数器提供了一种机制，允许程序安全地回收与并发访问的对象关联的内存，这些对象的可达性由缓存状态决定。
在现代处理器上，非阻塞数据结构是根据一次只能修改一个目标内存位置的原子操作来实现的。假设之前的缓存示例实际上已转换为无锁。缓存中对象的可达性很可能由对单个内存位置进行原子操作的线性化点决定。为了使引用计数方案有效，对象的可达性必须相对于对其传入的引用以原子方式进行管理。在缺乏对不同内存位置进行操作的原子操作的情况下，这种常见的带内引用计数方案无法提供足够的安全保证。9
因此，动态非阻塞和无锁数据结构（访问动态分配的内存，这些内存也可能在运行时释放的结构）通常必须依赖于替代的安全内存回收机制。除了成熟的垃圾回收之外，安全内存回收技术还包括
• EBR（基于时期的回收）。11 这是一种被动方案，允许通过仔细监控全局时期计数器的观察者来实现安全内存回收。它不适合保护以高频率创建和销毁的对象。尝试
使用 EBR 同步（立即）对象销毁的线程可能会阻塞，直到机制检测到安全销毁点。可以实现此方案的变体，在快速路径上成本极低。
• HP（Hazard 指针）。22 此方案通过实时检测对需要安全内存回收的对象的引用来工作。为了利用它，非阻塞算法需要针对此方案进行修改。然而，它更适合保护以高频率创建和销毁的对象，并且想要销毁受保护对象的线程不需要无限期地阻塞。此方案在快速路径上可能会带来高昂的成本（完全内存屏障），并且可能不适合遍历繁重的工作负载。
• QSBR（基于静止状态的回收）。8,20 这是一种被动方案，允许通过检测程序中的静止状态来实现安全内存回收，在静止状态下，可能不存在对具有活动引用的对象的引用。它不适合保护以高频率创建和销毁的对象。尝试使用 QSBR 同步（立即）对象销毁的线程可能会阻塞，直到机制检测到安全销毁点。此方案的变体可以在快速路径上以零成本实现。
• PC（代理收集）。 这是一种带外摊销引用计数方案。
还存在其他机制来实现安全内存回收。14 Thomas Hart 等人比较了前三种方案的性能属性。12 请注意，与引用计数相比，这些机制可能具有对许多工作负载有吸引力的性能属性，并且不需要专门与非阻塞数据结构一起使用。Paul McKenney 在本期 的其他文章 "结构化延迟：通过拖延实现同步" 中更详细地探讨了安全内存回收。
弹性
需要以下任何属性的系统可能会受益于使用无锁和无等待算法
• 死锁自由。没有锁意味着无等待和无锁数据结构对死锁条件免疫，而死锁条件在大型复杂的锁定层次结构中很难避免。
• 异步信号安全。在关键部分的异步中断的上下文中提供死锁自由和一致性是一个非常重要的问题。无等待和无锁同步对这些问题免疫。
• 终止安全。 满足线性化的无等待和无锁操作可以随时中止。这意味着处于无等待和无锁操作中间的处理器或线程可以终止，而不会牺牲系统的整体可用性。
• 抢占容忍度。 在资源不过载的情况下，即使存在抢占和其他外部延迟，无等待也能保证任何操作在有限的步骤内完成。无锁保证系统的整体进度，因为一个线程中的延迟只会导致另一个线程中有限的延迟（线性化可能需要其他线程协助完成延迟的操作，这可能需要在快速路径上执行额外的指令）。
• 优先级反转避免。 在没有内存等资源过载的情况下，无等待可以为优先级反转提供严格的界限保证，但这有时可能会给快速路径带来巨大的成本。可以通过针对固定并发级别专门化的算法来避免这种额外的开销。在单处理器系统上，在正确的调度策略下，无锁可以比基于锁的同步以更低的开销避免优先级反转。2 在争用程度高的多处理器系统上，有界优先级反转很难避免（可以避免的程度取决于底层一致性机制提供的公平性和优先级保证，而一致性机制通常对两者都几乎不提供任何保证）。即使在没有内存资源过载的情况下，无锁仍然容易受到无界优先级反转的影响，因为低优先级线程仍然可能导致任意数量的具有干扰操作的高优先级线程的延迟。可以使用争用避免来防止这种情况。
弥合抽象模型之间的差距
重要的是在实际硬件的背景下构建非阻塞同步的进度保证。在高内存和一致性资源争用程度非常高的情况下，无等待进度保证可能会在实际系统中崩溃。在这些争用级别下，可能会使处理器因无法接受的操作完成率而饿死。程序的进度保证只能与其构建的并发原语以及底层一致性机制的进度保证一样好。幸运的是，随着互连带宽持续增加，互连延迟持续降低，这个问题的严重性也在逐渐减弱。
当然，基于锁的同步也容易受到此问题的影响。在没有内存资源过载和存在抖动的情况下，无等待可以提供比基于锁的同步更强的延迟界限保证（因为对外部延迟的容忍度更高）。此延迟界限是底层微体系结构、内存资源和争用的函数。
非阻塞数据结构上的写操作的快速路径延迟通常高于基于锁的变体的快速路径延迟。这种权衡对于旨在适用于任何并发级别的非阻塞对象尤其常见，因为它们通常需要在快速路径上执行一个或多个更重的原子读-修改-写操作。快速路径延迟中的这种权衡是底层平台的锁实现成本和非阻塞算法复杂性的函数。
可以通过比较受自旋锁保护的堆栈与无锁堆栈（使用的实现来自 concurrencykit.org 的 ck_stack.h）的性能来说明这个概念。无锁堆栈包含一个单一的compare_and_swap操作，用于 push 和 pop 操作。在 x86 架构上，基于自旋锁的堆栈实现的快速路径延迟明显低于无锁堆栈实现。在 Power 7 架构上，情况并非如此。表 4 显示了这些各种操作的无争用延迟（以时钟周期为单位）。
在 x86 上，可以使用明显更便宜的原子操作（在本例中为xchg指令）来实现自旋锁，而不是无锁堆栈中使用的原子操作。架构的 TSO 不需要为此算法使用显式内存屏障。另一方面，无锁堆栈实现需要更复杂的cmpxchg（和cmpxchg16b）指令，该指令表现出更高的基线延迟。
在 Power 架构上，自旋锁和无锁实现都依赖于相同的底层 LL/SC 原语。主要区别在于自旋锁实现在每次堆栈操作调用时都需要一个重量级内存屏障，而无阻塞堆栈只需要更轻量级的加载和存储内存屏障。
无论架构强制的延迟权衡如何，非阻塞数据结构的理想属性都会在争用下显现出来。图 6 描绘了在 x86 服务器（Intel Xeon L5640）上跨四个线程在单个堆栈上进行纯推送工作负载的延迟分布。采取了积极措施来避免抖动，包括使用SCHED_FIFO调度类、核心亲和性和 IRQ（中断请求）亲和性 (Linux 2.6.32-100.0.19.el5)。
图 6 中所示的延迟分布不是单个堆栈操作更强延迟界限的结果，而是无锁算法提供的更强系统范围进度保证的副作用。具体而言，无锁算法能够在存在抢占的情况下保证进度。在阻塞数据结构中，堆栈操作关键部分内被抢占或阻塞的线程会阻止系统范围的进度。另一方面，仅当另一个线程通过更新堆栈取得进展时，无锁堆栈才会强制堆栈操作重试。如果从测试系统中移除了所有抖动源，那么基于自旋锁的堆栈的延迟曲线将占优势。
涉及写操作和只读操作组合的非对称工作负载也可以从非阻塞同步中受益。通常，结合此处描述的安全内存回收技术，可以为读取器提供强大的进度保证，并且在快速路径上几乎不需要重量级同步指令。这是一个理想的属性：它避免了流行的单优先级读写锁中出现的许多写端/读端公平性问题，同时也避免了与更重的公平读写锁相关的快速路径性能下降。
结论
在检查了多处理器系统上并行编程的一些常见原则以及非阻塞同步的实际意义之后，本文旨在为读者提供探索基于锁的同步替代方案所需的背景知识。即使非阻塞算法的设计、实现和验证都很困难，但这些算法在标准库和开源软件中正变得越来越普遍。此处提供的信息有助于识别需要非阻塞同步的弹性和性能特征的情况。
对于那些开始危险的自行设计非阻塞算法的读者，本期中的其他文章提供了有价值的信息（请记住通过工作负载专业化实现简化的机会）。
致谢
感谢 Mathieu Desnoyers 和 Paul McKenney 对开源社区中无锁同步的贡献，以及他们对本文的深刻见解反馈。感谢 Devon H. O'Dell 和 Gabriel Parmer 对本文以及整个过程的反馈。感谢 Theo Schlossnagle 在此过程早期阶段提供的支持。感谢 Silvio Cesare、Wez Furlong、Maxime Henrion、David Joseph、Paul Khuong、Abel Mathew、Shreyas Prasad、Brendon Scheinman、Andrew Sweeney 和 John Wittrock 提供的有益反馈。感谢 Jim Maurer、编辑委员会和 团队的其他成员的支持和反馈。
参考文献
1. AMD. 2007. AMD64 架构程序员手册，第 2 卷：系统编程。出版物 24593。
2. Anderson, J. H., Ramamurthy, S., Jeffay, K. 1997. 使用无锁共享对象进行实时计算。 Transactions On Computer Systems 15(2): 134-165; http://doi.acm.org/10.1145/253145.253159.
3. Attiya, H., Ramalingam, G., Rinetzky, N. 2010. 序列化可串行性的顺序验证。SIGPLAN Notices 45(1): 31-42; http://doi.acm.org/10.1145/1707801.1706305.
4. Attiya, H., Guerraoui, R., Hendler, D., Kuznetsov, P., Michael, M. M., Vechev, M. 2011. 顺序法则：并发算法中昂贵的同步无法消除。在第 38 届 SIGPLAN-SIGACT 编程语言原理年度研讨会论文集中：487- 498; http://doi.acm.org/10.1145/1926385.1926442.
5. Calciu, I., Dice, D., Lev, Y., Luchangco, V., Marathe, V. J., Shavit, N. 2013. NUMA 感知的读写锁。在第 18 届 SIGPLAN 并行编程原理与实践研讨会论文集中：157-166; http://doi.acm.org/10.1145/2442516.2442532.
6. Cantrill, B., Bonwick, J. 2008. 真实世界的并发。Queue 6(5): 16-25; http://doi.acm.org/10.1145/1454456.1454462.
7. Chong, N., Ishtiaq, S. 2008. 推理 ARM 弱一致性内存模型。在2008 年 SIGPLAN 内存系统性能和正确性研讨会论文集中：16-19; http://doi.acm.org/10.1145/1353522.1353528.
8. Desnoyers, M., McKenney, P. E., Stern, A. S., Dagenais, M. R., Walpole, J. 2012. 用户级读复制更新实现。IEEE Transactions on Parallel and Distributed Systems 23(2): 375-382.
9. Detlefs, D. L., Martin, P. A., Moir, M., Steele Jr., G. L. 2001. 无锁引用计数。在第 20 届 分布式计算原理年度研讨会论文集中：190-199; http://doi.acm.org/10.1145/383962.384016.
10. Dice, D., Marathe, V. J., Shavit, N. 2012. 锁队列组：一种设计 NUMA 锁的通用技术。在第 17 届 SIGPLAN 并行编程原理与实践研讨会论文集中：247-256; http://doi.acm.org/10.1145/2145816.2145848.
11. Fraser, K. 2003. 实用无锁自由。博士论文。剑桥大学计算机实验室。也以技术报告 UCAM-CL-TR-579, 剑桥大学提供。
12. Hart, T. E., McKenney, P. E., Demke Brown, A., Walpole, J. 2007. 无锁同步的内存回收性能。Journal of Parallel and Distributed Computing 67(12): 1270-1285; http://dx.doi.org/10.1016/j.jpdc.2007.04.010.
13. Herlihy, M. 1991. 无等待同步。 Transactions on Programming Languages and Systems 13(1): 124-149; http://doi.acm.org/10.1145/114005.102808.
14. Herlihy, M., Luchangco, V., Moir, M. 2002. 重复违规者问题：一种支持动态大小无锁数据结构的机制。技术报告。Sun Microsystems Inc.
15. Herlihy, M., Shavit, N. 2008. 多处理器编程的艺术。旧金山：Morgan Kaufmann Publishers Inc.
16. Kandemir, M., Choudhary, A., Banerjee, P., Ramanujam, J. 1999. 关于减少共享内存多处理器上的伪共享，同时提高局部性。在1999 年国际并行架构和编译技术会议论文集中：203-211。IEEE 计算机协会； http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=true&arnumber=807529&contentType=Conference+Publications.
17. Liu, T., Berger, E. D. 2011. SHERIFF：精确检测和自动缓解伪共享。在2011 年 国际面向对象编程系统语言和应用程序会议论文集中：3-18; http://doi.acm.org/10.1145/2048066.2048070.
18. Luchangco, V., Nussbaum, D., Shavit, N. 2006. 分层 CLH 队列锁。在第 12 届国际并行处理会议论文集，编辑：W. E. Nagel, W. V. Walter, W. Lehner, 801-810。Springer-Verlag Berlin Heidelberg; https://dx.doi.org/10.1007/11823285_84.
19. McKenney, P. E. 1996. 为并行编程选择锁定原语。Communications of the 39(10): 75-82; http://doi.acm.org/10.1145/236156.236174.
20. McKenney, P. E. 2004. 利用延迟销毁：操作系统内核中读复制更新技术分析。博士论文。俄勒冈健康与科学大学。AAI3139819。
21. McKenney, P. E. 2011. 并行编程很难吗？如果是，你能做些什么？kernel. org; https://linuxkernel.org.cn/pub/linux/kernel/people/paulmck/perfbook/perfbook.html.
22. Michael, M. M. 2004. Hazard 指针：无锁对象的安全内存回收。IEEE Transactions on Parallel and Distributed Systems 15(6): 491-504; http://dx.doi.org/10.1109/ TPDS.2004.8。
23. Michael, M. M., Scott, M. L. 1995. 简单、快速和实用的非阻塞和阻塞并发队列算法。技术报告。罗切斯特大学，纽约州罗切斯特。
24. Novell. Linux 的 NUMA API; http://developer.amd.com/wordpress/media/2012/10/LibNUMA-WP-fv1.pdf.
25. Oracle. 2010. 内存和线程放置优化开发者指南; http://docs.oracle.com/cd/E19963-01/html/820-1691/.
26. Owens, S., Sarkar, S., Sewell, P. 2009. 更好的 x86 内存模型：x86-TSO。在高阶逻辑定理证明中，编辑：S. Berghofer, T. Nipkow, C. Urban, 和 M. Wenzel, 391-407。Springer Berlin Heidelberg; https://dx.doi.org/10.1007/978-3-642-03359-9_27.
27. Sarkar, S., Sewell, P., Alglave, J., Maranget, L., Williams, D. 2011. 理解 POWER 多处理器。SIGPLAN Notices 46(6): 175-186; http://doi.acm.org/10.1145/1993316.1993520.
28. Schneider, F. B. 1997. 关于并发编程。纽约：Springer-Verlag New York Inc.
喜欢还是讨厌？请告诉我们
Samy Al Bahra 是 AppNexus 的工程团队主管，在领先的实时在线广告平台的开发中发挥着关键作用。在加入 AppNexus 之前，他曾参与 Message Systems 的高性能消息服务器的开发，并且是乔治华盛顿大学高性能计算实验室 UPC I/O 库参考实现的首席开发人员。他是 Concurrency Kit (http://concurrencykit.org) 的维护者，该库提供了大量的专用并发原语、无锁数据结构和其他技术，以帮助研究、设计和实现高性能并发系统。
© 2013 1542-7730/13/0500 $10.00
最初发表于 Queue vol. 11, no. 5—
在 数字图书馆 中评论本文
更多相关文章
Adam Morrison - 多核程序中的可扩展同步
为现代多核处理器设计软件提出了一个难题。传统的软件设计中，线程操作共享数据，其可扩展性有限，因为对共享数据更新的同步会串行化线程并限制并行性。另一种分布式软件设计中，线程不共享可变数据，消除了同步并提供了更好的可扩展性。但是，分布式设计使得实现共享数据结构自然提供的功能（例如动态负载均衡和强一致性保证）具有挑战性，并且并非适用于每个程序。然而，通常情况下，共享可变数据结构的性能受到当今使用的同步方法（无论是基于锁的还是无锁的）的限制。
Fabien Gaud, Baptiste Lepers, Justin Funston, Mohammad Dashti, Alexandra Fedorova, Vivien Quéma, Renaud Lachaize, Mark Roth - 现代 NUMA 系统上的内存管理挑战
现代服务器级系统通常由放置在单个系统中的多个多核芯片构建而成。每个芯片都有一个本地 DRAM（动态随机存取存储器）模块；它们一起被称为一个节点。节点通过高速互连连接，并且系统是完全一致的。这意味着，程序员透明地，内核可以向其节点的本地内存以及其他节点的内存发出请求。关键的区别在于远程请求将花费更长的时间，因为它们会受到更长的线路延迟的影响，并且可能必须在遍历互连时跳转多个跃点。
Spencer Rathbun - 使用 Promise 进行并行处理
在当今世界，有很多理由编写并发软件。提高性能和增加吞吐量的愿望导致了许多不同的异步技术。然而，所涉及的技术通常很复杂，并且是许多细微错误的原因，特别是当它们需要共享可变状态时。如果不需要共享状态，那么这些问题可以通过称为 Promise 的更好抽象来解决。这些 Promise 允许程序员将异步函数调用连接在一起，等待每个函数返回成功或失败，然后再运行链中的下一个适当的函数。
Davidlohr Bueso - 实用同步原语的可扩展性技术
在理想的世界中，应用程序有望在越来越大的系统上执行时自动扩展。然而，在实践中，不仅不会发生这种扩展，而且在那些更大的系统上，性能实际上变得更糟的情况也很常见。
© 保留所有权利。