2013年8月12日
第11卷，第7期

选择非阻塞特性的平衡艺术

非阻塞系统的设计需求

Maged M. Michael

什么是非阻塞进展？考虑一个简单的例子，即递增计数器C在多个线程之间共享。一种方法是通过保护递增的步骤C使用互斥锁L(即，acquire(L); old := C ; C := old+1; release(L);)。如果一个线程P持有L，那么另一个线程Q必须等待P释放L才能Q继续操作C。也就是说，Q被P.

阻塞。现在考虑使用以下方法实现递增操作：比较并交换(CAS) 原子原语。 CAS 原子地读取共享位置，并将读取的值与预期值进行比较。如果它们相等，则将新值写入该位置，并返回一个指示与预期值相等的指示符。在以下实现中&C是...的地址C:

do {old := C; } until CAS(&C, old, old+1);

此实现是非阻塞的，因为没有线程会被其他线程的不活动（例如，抢占、页错误，甚至终止）阻塞，无论其他线程在哪里停止。

非阻塞进展有三个已确定的级别无障碍 (obstruction-free)，无锁 (lock-free)，和无等待 (wait-free)。最弱的是无障碍性。一个操作是 无障碍的 (obstruction-free) 如果保证它在单独运行时在有限的步骤内完成。⁹ 一个无障碍的 (obstruction-free)操作不需要等待其他线程的动作，无论它们在哪里停止。然而，无障碍操作可能会饿死或最终陷入与一个或多个并发操作的活锁场景，其中线程的动作阻止它们全部取得进展。

无锁 (Lock-free) 进展结合了无障碍的 (obstruction-free)进展和活锁自由。也就是说，在只有无锁 (lock-free)操作的系统中，每当一个操作执行有限的步骤时，在此期间必须已完成某个操作（可能是不同的操作）。

最后， 无等待 (wait-free) 进展⁷ 结合了无锁 (lock-free)进展和无饥饿性 (starvation-freedom)。也就是说，一个无等待 (wait-free)操作保证在有限的自身步骤内完成，而无需考虑其他操作的动作或不活动。

值得注意的是，这些级别的进展保证要求原始的内存访问步骤在硬件仲裁和缓存一致性级别上至少具有相同的进展保证级别。例如，一个缓存一致性协议，可能导致某些原始内存访问无限期地重试，无法支持一个无等待 (wait-free)使用此类原语的算法。

非阻塞操作的用途

非阻塞操作通常用于系统或线程间交互，在这些情况下，让线程等待其他线程的动作会使系统容易受到死锁、活锁和/或长时间延迟的影响。此类用途的示例包括

•异步信号安全。 这允许异步信号的信号处理程序与被中断的线程共享数据或服务，并保证信号处理程序永远不需要等待被中断的线程——它，由于被中断，在信号处理程序完成之前无法运行。信号处理程序特别使用的非阻塞操作可以保证不存在此类等待并提供异步信号安全。

• 可终止安全 系统。 即使进程可能在任意点终止，此类系统也保证可用性。此要求出现在服务器系统中，其中终止表示客户端请求的进程的能力允许高服务器吞吐量。即使进程可能在任意点终止，此类系统也必须保证在操作共享结构或服务时的可用性。当在此类

系统中使用非阻塞操作时，剩余的进程永远不必等待动作——这永远不会发生——由已终止的进程。

•在通用系统上的软实时应用程序。 在此类系统（例如，媒体播放器）上使用非阻塞操作有助于避免优先级反转并提供抢占容忍度。也就是说，它消除了以下可能性，即一个活动的线程——可能正在执行一个高优先级任务——被阻塞，等待其他线程的动作，而这些线程被长时间延迟（例如，由于页错误）。这有助于使此类系统中长时间的明显延迟极不可能发生。

选择非阻塞特性

与共享计数器的示例不同，几乎任何涉及多个位置的非阻塞操作都会带来多种通常相互矛盾的考虑因素。本文探讨了权衡 (trade-offs)和在选择非阻塞操作的特性时必须考虑的折衷方案。这些权衡很少是直接的，有时需要妥协才能达到系统要求的最低限度。如果您一开始没有意识到所有潜在的陷阱，那么平衡这些权衡可能会令人望而生畏。

本文的目标是引导读者了解非阻塞操作的各种问题和特性以及要作出的各种选择；了解这些选项之间的相互作用；并培养对最佳路径的认识，以理清这些选择之间的相互依赖性，并快速修剪与首先使用非阻塞操作的主要目标不兼容的选项。

对于非阻塞操作的某些用途，例如可终止安全 (kill-safety)，对非阻塞进展的需求可能涉及对多个数据结构和服务的操作。在这些情况下，必须考虑各种非阻塞组件的特性之间相互依赖性的整体性，以达成可接受的解决方案。

运行示例

图 1 展示了经典无锁 (lock-free)IBM LIFO(后进先出)-无锁列表算法¹⁰ 的变体作为运行示例。变量列表算法¹⁰ 的变体作为运行示例。变量Header由一个打包的指针-整数对组成，可以通过双字宽 (double-width)CAS 原子地读取和操作。假设整数大小足够大，永远不会溢出。符号*b用于指示指针b.

Variant of the Classic Lock-free IBM LIFO Free List Algorithm

根据上下文，对Header的读取和 CAS 操作可以是单字宽或双字宽。

暂且忽略为什么整数与Header中的指针打包在一起（稍后解释），读者可以注意到，任何数量的线程在 Push 和 Pop 操作中的任何位置停止活动，都不会阻止其他线程操作列表。实际上，由于 Push 和 Pop 不仅是非阻塞的，而且也是无锁 (lock-free)，，那么只要有活动线程尝试这些操作，某些操作就会完成。每当任何线程在其中一个操作中执行五个步骤时，在此期间必须已完成某些操作（由同一线程或不同的线程）。

选择非阻塞特性的关键问题

以下是在选择非阻塞操作的特性时要考虑的关键问题。

进展保证级别

适当的非阻塞进展级别（例如，无障碍的 (obstruction-free)与无锁 (lock-free)）以及非阻塞操作的使用范围取决于系统所需的进展保证。

为了使用非阻塞操作实现异步信号安全，只需要信号处理程序的操作是非阻塞的，而主线程的操作可以是阻塞的。例如，在信号处理程序可能搜索哈希表的情况下，哈希表可能被可能被中断的线程更新，完全非阻塞算法不是必需的，而具有非阻塞搜索操作和阻塞添加和删除操作的算法（如 Steve Heller 等人⁶ 所述）可能就足够了。

如果唯一关注的是信号处理程序和被中断线程之间的交互，那么使用无障碍的 (obstruction-free)无障碍 (obstruction-free) 操作就足够了。可终止安全 (Kill-safety)往往需要更广泛地使用非阻塞操作来访问可能被任意终止的进程共享的对象。与异步信号安全类似，使用无障碍的 (obstruction-free)无障碍 (obstruction-free) 操作足以提供可用性。使用无锁 (lock-free) 或无等待 (wait-free)无等待 (wait-free) 操作分别保证活锁自由或无饥饿性。

为了避免软实时应用程序中的优先级反转，可能足以使高优先级操作无障碍 (obstruction-free)；然而，更强的进展保证（无锁 (lock-free)或无等待 (wait-free)）在这种情况下显然是更可取的。

无等待 (Wait-free)算法往往需要至少与可能同时运行的线程数呈线性的空间。¹ 除了空间开销外，一些最新的无等待 (wait-free)算法显示出相当具有竞争力的性能。^5,19无锁 (Lock-free)无锁 (lock-free) 算法可以实现与阻塞算法相媲美的性能，并且没有固有的高空间要求。几乎没有任何针对特定数据结构的自定义无障碍的 (obstruction-free)非无锁 (lock-free) 的特定数据结构算法；无锁 (lock-free)；然而，无障碍的 (obstruction-free)用于任意原子节（或事务内存）的无锁 (lock-free) 算法显然比相应的无锁 (lock-free)无等待 (wait-free) 算法更简单。

因此，在选择要使用的适当的非阻塞进展级别时，您必须考虑到为实现主要要求绝对需要什么（例如，可终止安全 (kill-safety)）与什么是可取的（例如，无等待 (wait-free)进展）以及这对其他问题意味着什么。

如果可以并发执行某些操作的线程数受到限制，那么与允许更高并发级别时相比，可以使用更简单的算法来实现强大的进展保证（例如，单生产者 (single-producer)或单消费者 (single-consumer)队列与多生产者多消费者队列）。

有时被忽略的一个问题是读取操作对更新操作的影响。考虑两个缓冲区实现。两者都支持 check （如果为空）和 add 操作。在这两种实现中，操作都是无锁 (lock-free) 的。第一种实现保证 check 操作永远不会阻止 add 操作完成。在另一种实现中，check 操作可能会干扰并阻止 add 操作完成（例如，由于使用引用计数，稍后讨论）。

您可以看到后一种实现是多么有问题，当检查缓冲区是否为空的行为可以阻止项目永远添加到缓冲区时。因此，在为非阻塞操作选择适当的进展级别时，仅仅要求实现是例如无锁 (lock-free) 的。的还不够。重要的是还要决定哪些操作必须免受其他操作的干扰。在缓冲区示例中，虽然 add 操作在两种实现中都是无锁 (lock-free)彼此之间是无锁 (lock-free) 的，但理想的情况是，单个 add 操作是无等待 (wait-free)相对于任何数量的并发 check 操作是无障碍 (obstruction-free) 的。

数据结构的选择

数据结构的选择是设计非阻塞环境时最重要的决策之一。这一步经常被忽略，因为数据结构选择可能继承自顺序或阻塞设计。在选择数据结构时，设计人员需要考虑最低要求和理想特性的范围。

例如，如果无锁 (lock-free)考虑 FIFO 列表，应该询问 FIFO 顺序是否确实必要，或者是否可以接受更宽松的顺序。如果是后者，那么可以简化设计，并且在某些条件下的性能可以通过使用无锁 (lock-free)LIFO 列表来代替。经典的 LIFO 列表算法具有更简单的内存安全要求（稍后讨论），并且通常比 FIFO 算法具有更短的路径长度。

另一个例子是，在顺序代码中可能是好选择的搜索结构（例如，平衡树）与哈希结构相比，可能不是非阻塞系统中的最佳选择。

此外，静态结构（例如使用开放寻址的哈希表）比动态结构（例如使用链式寻址的哈希表）更易于管理。

安全内存回收问题

根据定义，非阻塞操作不等待其他非阻塞操作的动作，也不能期望阻止其他非阻塞操作采取动作。这对取消引用指向可能被其他操作删除和释放的动态结构的指针的非阻塞操作提出了问题。如果没有适当的预防措施，当动态块从结构中删除并被另一个操作释放时，非阻塞操作可能即将访问该动态块。这可能会导致一些有问题的结果，例如，如果该块被释放回操作系统，则可能导致访问冲突，破坏恰好分配和使用已释放块的内存的不同结构，或返回不正确的结果。

以LIFO-无锁列表（在图 1 中）为例，可以看到 Pop 操作可能会导致访问已释放的内存。例如，一个线程P从变量A读取指向地址Header的指针，如 Pop 的第 1 行所示。然后，另一个线程Q弹出地址A处的块，并将其释放回操作系统。现在P继续执行 Pop 的第 2 行，并取消引用指向A的指针，可能导致访问冲突。

Paul McKenney¹³ 详细讨论了安全内存回收问题和解决方案。以下是内存安全解决方案及其含义的简要列表

•自动 GC（垃圾回收）。 在具有 GC 的系统上，例如 Java 应用程序，内存安全是隐式保证的。在前面的示例中，只要线程P持有对块A的引用，块A就保证不会被释放。当然，这提出了 GC 本身是否是非阻塞的问题。

•RCU （读取-复制-更新）和基于时期 (epoch-based) 的收集器。 简而言之，类 RCU (RCU-like)解决方案保证从某些数据结构中删除的块在确定所有线程都已达到静止点（在这些静止点，任何线程都不可能仍然持有对这些块的引用）之前不会被释放。¹⁴

•引用计数。 块与计数器相关联，当线程获取和释放对这些块的引用时，计数器会递增和递减。通常，只有当块的引用计数变为零并且保证不会创建对其的新引用时，才会释放该块。²⁰

•Hazard 指针。 简而言之，在这种方法中，每个可能遍历可能被删除和释放的块的线程都拥有多个 hazard 指针。在取消引用指针之前，线程将其 hazard 指针之一设置为指针值。其他可能删除该块的线程保证在没有 hazard 指针指向该块之前不会释放该块。^8,16

硬件事务内存可以简化非阻塞安全内存回收。⁴ 然而，正如稍后讨论的，大多数即将到来的主流 HTM 实现都是尽力而为 (best-effort)的，并且需要一个备选的非 HTM路径。

安全内存回收的选项按灵活性（和内存安全解决方案的难度）递增的顺序排列为

• 已释放的块将被重用，但永远不会为不同的用途释放。

• 已释放的块可以合并并重用于不同的类型和大小，但不会返回给操作系统。

• 已释放的块可以合并、任意重用或返回给操作系统。

请注意，对于某些算法（例如，经典的 LIFO 列表），如果操作系统支持非故障加载，则内存安全可能不是问题。在刚刚提到的线程P读取地址A在 Pop 的第 2 行中，在地址A处的块被释放到操作系统之后，具有非故障加载的系统将允许这样的读取。

ABA 问题预防

ABA 问题在乐观并发算法中很常见，包括非阻塞算法。术语 ABA 是指共享变量的值从A变为B再变回A。以LIFO 列表Pop 操作为例，并忽略与Header打包在一起的整数，以下是一个 ABA 问题场景，从包含块A和B的列表开始：（a.）一个线程P在 Pop 的第 1 行中读取值A，并在第 2 行中读取Header，并在第 2 行中读取B，并在第 2 行中读取*A；（b.）其他线程弹出块A和B并推送块C和A，使Header再次持有值A；（c.）P在 Pop 的第 3 行中对Header执行 CAS 操作，参数为A和B，CAS 成功。现在列表已损坏。Header指向B，而它不再在列表中。错误之处在于（没有打包的整数）P的 Pop 算法无法区分以下情况：在第 1 行和第 3 行之间Header从未更改，以及上述列表已更改但Header在第 3 行中的 CAS 之前返回其旧值的情况。

经典的 LIFO 算法将整数与Header变量中的指针打包在一起，其设计使得如果列表在 Pop 的第 1 行和第 3 行之间发生更改（假设计数器永远不会溢出），计数器将发生更改。

将整数与易受 ABA 问题影响的变量的主要内容打包在一起是经典的 ABA 问题预防解决方案。² 它在几十年中仍然是唯一的解决方案，但它有其局限性。它需要宽原子操作，以便为足够大的整数留出空间，使其不会溢出（或至少在一次操作的生命周期内不会溢出，例如示例中的 Pop）。此解决方案的另一个缺点是，它要求整数子字段无限期地保留其语义。这可能会使释放包含与ABA 问题预防计数器打包在一起的动态块的内存变得非常困难，这意味着内存无法合并或重用于不同的目的。

虽然 ABA 问题可能发生在不使用动态内存的算法中，但其解决方案与安全内存回收解决方案交织在一起。首先，如前所述，经典的 ABA 解决方案可能会阻碍内存回收。其次，任何内存安全解决方案（GC、RCU、引用计数、hazard 指针）都可以被调整以构建 ABA 解决方案，可能需要添加一个间接级别。

RCU 类型解决方案的一个优点是，遍历操作几乎没有开销，而引用计数和 hazard 指针对于遍历操作具有相当大的开销。另一方面，与 RCU 不同，引用计数和hazard 指针方法保证了未准备好重用的已删除块数量的界限。

引用计数的一个缺点在某些情况下可能很显着，那就是它可能导致一个本应是只读 (read-only)的操作（例如，前面提到的 check 操作）实际上写入共享数据（即，引用计数器）并阻止更新操作永远完成。

操作 LL（加载链接），SC（存储条件），和 VL（验证）本质上对 ABA 问题免疫。LL(location)返回共享位置中的值。VL(location)返回一个布尔指示符，指示自当前线程上次对其执行 LL 以来，共享位置是否已被另一个线程写入。SC(location, value)仅当自当前线程上次对其执行 LL 以来，该位置未被另一个线程写入时，才将新值写入该位置，并返回一个布尔指示符，指示是否发生了此类写入。如果 Pop 的第 1 行中的读取被替换为LL(&Header)并且 Pop 的第 3 行中的 CAS 被替换为SC(&Header,n)，那么 Pop 操作将对 ABA 问题免疫，而无需使用打包的整数。

支持 LL/SC 的实际架构（例如，IBM Power PC）不支持理想的 LL/SC/VL 的完整语义。没有一个支持 VL 操作，并且所有架构都对 LL/SC 之间可以执行的操作施加限制，并禁止在不同位置嵌套或交错 LL/SC 对。因此，虽然实际的 LL/SC 支持可以帮助无锁 (lock-free)LIFO 算法避免 ABA 问题，但它在总体上预防 ABA 问题方面是有限的。

虽然理想的 LL/SC/VL 的实现提供了一个绝对的 ABA 问题预防解决方案¹⁸，但其强大的语义不允许许多正确的场景。例如，无锁 (lock-free) LIFO 列表Push 操作中的所有 ABA 场景都是良性的。因此，建议考虑用读取和 CAS 操作表示的算法，并且仅解决 ABA 的有害情况，例如 LIFO 列表算法中的 Pop 而不是 Push。无锁 (lock-free) LIFO 列表算法。

建议一起考虑 ABA 问题预防和安全内存回收解决方案，以避免不必要的开销重复或与总体系统要求相矛盾或相反的解决方案。

所需原子操作的可移植性

非阻塞算法和方法所需的原子操作的硬件支持范围差异很大。如果可移植性是一个重要问题，设计人员需要在选择数据结构、算法以及安全内存回收和管理以及 ABA 问题预防的支持方法时考虑到这一点。

硬件支持要求包括

•没有支持。 例如，hazard 指针的读取和写入可能不是原子的。¹⁶

•非通用原子操作（例如fetch-and-add， test-and-set，和原子交换）。 Maurice Herlihy 表明，不可能设计无等待 (wait-free)（和无锁 (lock-free)）使用仅此类（非通用）操作来操作可由任意数量的并发线程操作的某些数据类型的实现。⁷

• 比较并交换 (Compare-and-swap)。 Herlihy 表明，CAS 是一种通用操作，可用于设计任何数据类型的无锁 (lock-free) 实现，而对操作它的最大线程数没有限制。无等待 (wait-free)操作，而对操作它的最大线程数没有限制。指针大小 (Pointer-size)CAS 可能会受到 ABA 问题的困扰。解决该问题的经典解决方案需要使用更宽的原子操作（例如，双字宽 (double-width)加载和 CAS 原语）。

•LL 和 SC 对（例如，larx和stcx在 IBM Power 架构上）。 Herlihy 也证明了这些是通用操作。如前所述，在 CAS 容易受到 ABA 问题影响的某些情况下，它们对 ABA 问题免疫。因此，指针大小 (pointer-size)LL/SC 可能就足够了，或者在需要 CAS 但没有 LL/SC 的情况下，代码可能更简单。双字宽 (double-width)在没有 LL/SC 的情况下需要 CAS。

•硬件事务内存。 最近，IBM（Blue Gene/Q²¹、System Z¹² 和 Power³）和 Intel¹¹ 架构正在为任意内存事务提供硬件支持。然而，大多数这些 HTM 架构（IBM System Z 除外）都是尽力而为 (best-effort)尽力而为 (best-effort) 的（即，它们要求程序员在硬件事务永远不成功的情况下提供非事务路径）。

请注意，如果可以并发执行某些操作的线程数受到限制，则非通用原子操作可能足以设计无锁 (lock-free) 实现。无等待 (wait-free)和无锁 (lock-free)的实现。例如，无等待 (wait-free) 单生产者 (single-producer)或单消费者 (single-consumer)FIFO 队列操作¹⁵ （通过跳过双锁算法中的适当锁）和单更新器 (single-updater)集合，具有无锁 (lock-free)多个线程的查找¹⁶，可以使用原子加载和存储来实现。

语言和内存排序的选择

除了原子操作的各种要求外，非阻塞算法在内存排序原语方面的要求也各不相同。例如，在运行示例（在图 1 中）的 Push 操作中，第 2 行中的写入必须在第 3 行中的写入（如果 CAS 成功）之前排序。硬件平台和LIFO 列表原语方面的要求也各不相同。例如，在运行示例（在图 1 中）的 Push 操作中，第 2 行中的写入必须在第 3 行中的写入（如果 CAS 成功）之前排序。硬件平台和高级编程语言提供了显式原语，以及内存访问之间排序的隐式保证，通常指定为架构或语言内存一致性模型。

在 Java 5 (2004) 和 C11/C++11 之前，这些语言无法可靠地使用（按照其标准指定）来完全表达所需的内存排序。程序员和自定义库编写者依赖于汇编语言和机器二进制代码来表达此类排序。

现在，借助 C11/C++11 和 Java（5 及更高版本），程序员可以将某些变量指定为受特殊排序约束（Java 中的 volatiles 和 C11/C++11 中的 atomics）。在某些情况下，这些指定可能过于强硬 (heavy-handed)，即使算法不需要，也会在这些变量周围强制排序。标准 C11/C++11 提供了更精细的排序级别，允许程序员指定所需的顺序。

此类语言的实现在不同的硬件平台上具有不同的开销。非阻塞实现的设计人员应考虑高级语言的选择及其内存排序在目标硬件平台上的性能。

算法的选择

数据结构和算法的组合选择是一个问题，可以在其中做出重大妥协，以设计一个满足其总体要求的系统。

非阻塞算法在其可移植性（例如，对特殊硬件支持的要求）、可靠性（例如，是否被广泛使用）、复杂性（例如，实现、维护和修改的合理易用性）、进展保证（例如，无等待 (wait-free)，无锁 (lock-free)，等）以及内存安全性和ABA 问题预防特性（例如，与某些方法的兼容性或不兼容性）方面各不相同。算法的选择与此处讨论的大多数问题交织在一起。

案例研究

以下示例的目的是演示本文中讨论的非阻塞特性和问题之间的相互作用。

考虑一个简化的可终止安全 (kill-safe)系统的示例，该系统要求进程共享可能很大的可变大小 (variable-size)记录（每个记录都有唯一的键值），这些记录可以在各种数据结构之间删除或任意移动）。对记录和数据结构的操作是搜索、添加、删除和更新某些字段。图 2 显示了动态可变大小 (variable-size)记录，这些记录可以被释放并在结构之间移动。

考虑到记录可以在数据结构之间来回移动，任何非阻塞算法都必须处理 ABA 问题。由于记录可能很大且大小可变，因此限制其内存的重用不是一个可接受的选项。经典的 ABA 解决方案（在LIFO 列表Pop 示例中使用的）可以排除，因为它会限制内存的任意重用。基于时期 (Epoch-based)解决方案也应排除，因为它们在任意终止下可能会变得非常复杂。但是，剩下的解决方案——引用计数和 hazard指针——也不是可接受的选项。它们依赖于防止记录在存在对其的活动引用时重新插入到相同的结构中（这是一个要求）。没有可接受的解决方案。

这可能是考虑妥协的好时机。如何为每个记录添加一个单独的描述符？描述符保存键值和遍历数据结构所需的任何字段；然后可以在适当位置更改这些字段，而无需从结构中删除和添加记录。通过这种妥协，完整记录的内存仍然可以释放，但可能可以接受阻止描述符被释放以进行任意重用。

现在让我们重新考虑 ABA 问题。也许经典的打包整数 (packed-integer)解决方案可以工作。这具有允许描述符（和相关的记录）在数据结构之间自由移动的优点，但它增加了对宽原子操作（例如，128 位CAS）的硬件支持的依赖性。其他选项（hazard 指针和引用计数）不需要宽原子操作，但需要在每次在数据结构之间移动记录时使用新的描述符（即，不包含任何旧操作遗留的旧引用的描述符）。此外，hazard 指针和引用计数都增加了开销（分别是内存排序和额外的原子操作）。最后，为了处理可变大小 (variable-size)记录的实际分配和释放，设计人员可以使用无锁 (lock-free)具有合并功能的分配算法以及将空闲内存返回给操作系统的能力。¹⁷

现在，设计人员的任务是平衡顺序性能（即，当使用带有双字宽 (double-width)原语的打包整数时）的优缺点和可移植性（当使用单字宽原语但为 hazard 指针添加额外的排序或为引用计数添加额外的原子操作时）。

正如读者所见，本案例研究经历了对各种选择的几次迭代，从绝对必要的开始，做出妥协（使用描述符并添加间接级别），最后达成一组合理的选项，以供进一步考虑其优缺点。

摘要

本文介绍了关键问题，这些问题可以帮助非阻塞系统的设计者做出经常需要的权衡和折衷，以达成一个可行的设计，满足所有需求。在考虑所有这些问题时，设计者应该多次审视这份特性和问题列表。首先，他们应该识别并区分绝对必要的功能和那些理想但可以妥协的功能。之后，他们可以开始考虑使用这些各种特性的影响。

致谢

作者感谢 Samy Al Bahra 和 Paul McKenney 对本文早期版本提出的深刻见解。

参考文献

1. Attiya, H., Hendler, D. 2005. 使用以下技术的实现的时间和空间下界k-CAS。在第19届国际分布式计算会议论文集： 169-183.

2. Brown, P. J., Smith, R. M. 1973. 美国专利 3,886,525。由多个用户控制的共享数据（1973年6月提交）。

3. Cain, H. W., Frey, B., Williams, D., Michael, M. M., May, C., Le, H. 2013. Power 架构中事务内存的稳健架构支持。/IEEE 第40届国际计算机体系结构研讨会 (ISCA)。

4. Dragojevic, A., Herlihy, M., Lev, Y., Moir, M. 2011. 论硬件事务内存简化内存管理的能力。第30届年度 SIGACT-SIGOPS分布式计算原理研讨会 (PODC) 99-108.

5. Fatourou, P., Kallimanis, N. D. 2011. 一种高效的无等待 (wait-free)通用构造。并行算法与体系结构研讨会 (SPAA) 325-334.

6. Heller, S., Herlihy, M., Luchangco, V., Moir, M., Scherer III, W. N., Shavit, N. 2005. 一种惰性并发的基于列表的集合算法。第九届国际分布式系统原理会议 (OPODIS) 3-16.

7. Herlihy, M. 1991。无等待 (Wait-free)同步。 编程语言和系统事务 13(1) 124-149.

8. Herlihy, M., Luchangco, V., Martin, P. A., Moir, M. 2005. 对以下项的非阻塞内存管理支持动态大小的数据结构。 计算机系统事务 23(2) 146-196.

9. Herlihy, M., Luchangco, V., Moir, M. 2003。无障碍的同步双端队列作为示例。第23届国际分布式计算系统会议 (ICDCS) 522-529.

10. IBM System/370 操作原理。1975。GA22-7000-4。

11. Intel 架构指令集扩展编程参考。2012。

12. Jacobi, C., Slegel, T. J., Greiner, D. F. 2012. IBM System Z 的事务内存架构和实现。第45届年度 IEEE/ 国际微体系结构研讨会 25-36.

13. McKenney, P. 2013. 结构化延迟：通过拖延进行同步。队列。 https://queue.org.cn/detail.cfm?id=2488549

14. McKenney, P. E., Slingwine, J. D. 1998。读取-复制更新：使用执行历史来解决并发问题。第10届 IASTED 国际并行与分布式计算和系统会议论文集。

15. Michael, M. M., Scott, M. L. 1996. 简单、快速且实用的非阻塞和阻塞并发队列算法。第15届年度分布式计算原理研讨会论文集 267-275.

16. Michael, M. M. 2004. 危害指针：安全的内存回收，用于无锁 (lock-free)对象。IEEE 并行分布式系统事务 15(6) 491-504.

17. Michael, M. M. 2004. 可扩展的无锁 (lock-free)动态内存分配。在2004 SIGPLAN 编程语言设计与实现会议论文集中。

18. Michael, M. M. 2004. 实用的无锁 (lock-free)和无等待 (wait-free)使用以下技术的 LL/SC/VL 实现64 位CAS。在第18届国际分布式计算会议论文集中 144-158.

19. Timnat, S., Braginsky, A., Kogan, A., Petrank, E. 2012。无等待 (Wait-free) 链表。第16届国际分布式系统原理会议 330-344.

20. Valois, J. D. 1995。无锁 (Lock-free)使用以下技术的链表比较并交换。在第14届年度分布式计算原理研讨会论文集中 214-222.

21. Wang, A., Gaudet, M., Wu, P., Amaral, J. N., Ohmacht, M., Barton, C., Silvera, R., Michael, M. M. 2012. Blue Gene/Q 硬件对事务内存支持的评估。在第21届国际并行体系结构与编译技术会议论文集中 127-136.

喜欢它，讨厌它？请告诉我们 [email protected]

Maged M. Michael 是 IBM Thomas J. Watson 研究中心的科研人员。他获得了罗切斯特大学计算机科学博士学位。他的研究领域包括并发算法、非阻塞同步、事务内存、多核系统和并发内存管理。他是杰出科学家，也是康涅狄格州科学与工程院院士。

最初发表于 Queue 卷 11，第 7 期—
在数字图书馆中评论本文

更多相关文章

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 - 实用同步原语的可扩展性技术
在理想的世界中，应用程序有望在越来越大的系统上执行时自动扩展。然而，在实践中，不仅这种扩展不会发生，而且在更大的系统上看到性能实际上恶化是很常见的。