PDF实用同步原语的可扩展性技术
以性能为导向设计锁原语
Davidlohr Bueso，SUSE 实验室
在理想情况下，应用程序在越来越大型的系统上执行时，应能自动扩展。然而，在实践中，这种扩展不仅不会发生，而且常见的情况是，在这些更大的系统上，性能实际上会恶化。
虽然性能和可扩展性可能是含义模糊的术语，但当问题出现在软件堆栈的底层时，它们的含义就变得清晰起来。这仅仅是因为在评估性能问题时需要考虑的因素减少了。因此，并发多线程程序（如操作系统内核、虚拟机监控程序和数据库引擎）在误用硬件资源时可能会付出高昂的代价。
这会转化为堆栈中更上层应用程序的性能问题。一个明显的例子是共享内存系统的同步原语（锁）的设计和实现。锁是一种允许多个线程并发执行的方式，通过互斥提供安全且正确的执行环境。为了实现序列化，锁通常需要硬件支持，通过使用原子操作，如 CAS（比较并交换）、fetch-and-add 和算术指令。虽然不同缓存一致性架构之间的细节有所不同，但原子操作会在内存总线上广播更改，为每个核心更新共享变量的值，强制缓存行失效，因此导致更多的缓存行未命中。软件工程师经常滥用这些原语，导致因锁粒度不佳或延迟过高而导致的性能显著下降。
锁的正确性和性能都取决于底层的硬件架构。这就是为什么可扩展性和硬件影响在锁算法的设计中如此重要。不幸的是，这些在现实世界的软件中很少被考虑。
随着规模越来越大的多核和众核 NUMA（非统一内存访问）系统的出现，糟糕的锁实现的性能损失变得令人痛苦地明显。这些损失适用于原语的实际实现及其使用，后者许多开发人员通过设计用于数据序列化的锁定方案直接控制。经过数十年的研究，这是一个众所周知的事实，并且在今天比以往任何时候都更加真实。尽管最近出现了锁省略和事务内存等技术，但并发、并行编程和同步对于从业者来说仍然是具有挑战性的主题。10
此外，由于事务内存系统（如 TSX（事务同步扩展））在事务不成功时仍然需要使用常规锁作为回退路径，因此这些挑战不会在短期内消失。此外，事务系统不保证超出无饥饿的特定进度；因此，对于常规锁定方案，这并不总是可行的选择。由于这些复杂性，系统不仅可能缺乏可扩展性，而且其整体性能也可能被拖垮。先前的工作已经证明，糟糕的、不可扩展的锁定实现的成本会随着系统中核心数量的增加而增长。2 性能崩溃的发生实际上可能非常突然，只需在等式中添加几个核心即可。性能和可扩展性问题远远超出综合工作负载和基准测试，影响着现实世界的软件。
最近，在大型高端服务器上的 Linux 内核中，已经做出了重大努力来解决锁扩展问题。3 许多问题和解决方案适用于类似的系统软件。本文将通用思想和经验教训应用于更广泛的系统环境，希望它能够帮助那些遇到类似扩展问题的人。当然，锁在任何共享内存系统中都很重要，但优化它们并不意味着忽略更重要的方面：这些锁的使用方式以及序列化的内容。
混合锁定模型和乐观自旋
锁定原语传统上分为忙等待或阻塞，这取决于当锁不可立即用时会发生什么。如果锁持有时间很短，例如仅序列化引用计数操作，那么避免所有阻塞开销并在短时间内仅消耗 CPU 周期更有意义。这通常通过循环 CAS 调用来实现，直到满足解锁条件。另一种选择是阻塞，直到该条件变为真。除了更高的开销和延迟之外，阻塞原语通常可能严格依赖于操作系统内核的调度程序。因此，线程调度策略将越来越依赖于软件堆栈中以前的执行级别，例如硬件、内核或多个用户空间层。多种调度策略可能会影响锁的公平性和确定性。
在构建睡眠锁时，抖动是另一个需要牢记的因素。从业者必须考虑重度锁争用下的系统后果。忙等待原语的常见示例是内存屏障和自旋锁。阻塞机制通常包括信号量和监视器。例如，Linux 内核有三种主要的睡眠信号量：互斥锁（二进制）和两种计数信号量，其中包括广泛使用的读/写变体。
使用混合模型是处理每种锁类型权衡的常用方法。目标是尽可能延迟阻塞，并乐观地忙等待直到锁可用。然而，确定锁何时休眠会影响性能。该算法需要对可能受益不同的工作负载表现同样出色。换句话说，明确需要睡眠锁特性的用户不能在 CPU 首先在锁上自旋一段确定时间（通常甚至根本不自旋）时付出性能损失。此外，通用锁定原语的用户绝不应被允许影响其算法行为。错误设计的锁定 API 可能会在以后导致意外后果，例如当锁被大量使用时。简单性非常重要——并且是精心设计的锁定接口的结果。
通过使用锁所有权的概念，Linux 内核保留指向当前持有锁的任务的指针。了解锁所有者的好处是双重的：它是确定何时停止自旋的关键数据；它还用于调试目的，例如死锁检测。类似策略可以追溯到 1975 年，当时首次在数据库中提出了锁所有权的概念。8 由于维护锁所有权的开销，实现者可以决定反对可重入锁，后者通常也使用计数器字段。15
乐观自旋背后的原理是，如果拥有锁的线程正在运行，那么它很可能很快就会释放锁。在实践中，Linux 内核互斥锁或 rw_semaphore（读写信号量），这是整个系统中最常用的两种锁，在获取锁时，根据其当前状态，最多可以遵循三种可能的路径：12
• 快速路径。它尝试通过修改内部计数器（如 fetch_and_add 或原子递减）来原子地获取锁。此逻辑特定于架构。如此处所示，对于 x86-64，互斥锁快速路径对于锁定和解锁调用只有两条指令
0000000000000e10 <mutex_lock>
e21: f0 ff 0b lock decl (%rbx)
e24: 79 08 jns e2e <mutex_lock+0x1e>
0000000000000bc0 <mutex_unlock>
bc8: f0 ff 07 lock incl (%rdi)
bcb: 7f 0a jg bd7 <mutex_unlock+0x17>
• 中等路径（又名乐观自旋）。当锁所有者正在运行时，并且没有其他更高优先级的任务准备好运行，需要重新调度时，它会尝试自旋以获取锁。自旋线程使用 MCS 锁排队，以便只有一个自旋线程可以竞争锁。
• 慢速路径。 作为最后的手段，如果仍然无法获取锁，则将任务添加到等待队列并休眠，直到解锁路径唤醒它。
由于混合锁仍然可能阻塞，因此这些原语需要在睡眠环境中安全使用。乐观自旋已证明其在操作系统内核（如 Linux 和 Solaris）中的价值。即使在今天，简单地延迟任何类型的阻塞开销也可能对系统软件产生重要影响。在 Linux VFS（虚拟文件系统）create+unlink 微基准测试中，为了测试互斥锁的压力，乐观自旋在商品桌面系统上的吞吐量提升了约 3.5 倍，而不是立即休眠。同样，对于 AIM7 工作负载上的 rw_semaphores，混合锁定使吞吐量提高了约 1.8 倍。3
Linux 内核中 rw_semaphores 和互斥锁之间的一个显着区别是它们如何处理锁所有权。当锁是共享的时，所有权的概念比排他锁更模糊。当工作负载结合了读取器和写入器时，乐观自旋可能会使写入器过度自旋，因为当读取器持有锁时，没有所有者可以自旋。存在克服此问题的策略，例如使用启发式方法和幻数来确定何时停止读取器的自旋。然而，读取器所有权可能特别棘手，并且倾向于在乐观自旋快速路径中增加额外的复杂性和开销。此外，在锁定原语中使用幻数可能会带来意想不到的后果，并且绝不能轻易使用。就其本质而言，启发式方法可以在特定场景中提供帮助，但在常见情况下实际上会损害性能。可扩展性不是为 1% 进行优化而不考虑其他 99%，而是恰恰相反。此外，在考虑过于复杂的原语之前，解决实际的争用来源可能是一种有效的替代方案。
导致锁扩展性差的因素
在任何给定时间，找到导致锁性能差的多种因素并不少见。当然，影响将因每个系统和工作负载而异。此处描述的因素和锁属性可以在软件工程级别上划分：在实现者（通常设计和实现锁定原语）与用户（严格将其应用于其并行或并发工作负载和算法）之间。
• 临界区长度。 缩短临界区的长度肯定有助于缓解锁争用。此外，用于在锁实现中序列化并发线程的原语类型可以在性能方面发挥关键作用。在慢速路径中持有锁时，例如那些处理获取或释放锁时的争用场景，从业者通常需要管理等待执行某些操作的线程的内部等待队列。在这些情况下，实现者必须确保临界区足够短，不会引起不必要的内部争用。例如，预检查或唤醒（对于睡眠原语）可以轻松地异步发出，而无需任何额外的序列化。最近，在 Linux 内核中，缩短互斥锁和 SysV 信号量（以及其他形式的进程间通信）中的临界区的努力提供了重要的性能优势。3,13
• 锁开销。 这是使用特定锁的资源成本，包括大小和延迟。例如，嵌入在数据结构中的锁会使该类型膨胀。更大的结构大小意味着更多的 CPU 缓存和内存占用。因此，当结构在整个系统中被频繁使用时，大小是一个重要的因素。实现者在非平凡修改后扩大锁类型时，还需要考虑锁开销；这可能会在意外的地方导致性能问题。例如，Linux 内核文件系统和内存管理开发人员必须特别注意 VFS struct inode（索引节点）和 struct page 的大小，并尽可能优化。4 这些数据结构分别表示有关系统上每个文件和每个物理页帧的信息。因此，存在的文件或内存越多，内核处理的这些结构的实例就越多。拥有数千万个缓存 inode 的机器并不少见，因此将 inode 的大小增加 4% 是很重要的。这足以使工作负载从良好平衡变为无法将 inode 的工作集放入内存中。实现者必须始终牢记锁定原语的大小。
至于延迟，由于其简单性，忙等待原语比更复杂的锁具有更好的延迟。初始化调用，特别是获取或释放锁的调用，需要便宜，产生的 CPU 周期最少。控制原语的内部逻辑不得与影响调用延迟的其他因素（如持有时间和争用）相混淆。阻塞（或睡眠）锁预计会更昂贵，因为任何算法至少必须考虑诸如使线程进入睡眠状态并在锁可用时唤醒它们之类的事件。当然，权衡之处在于，用户仅在处理大型临界区或在需要睡眠的环境（例如在分配内存时）中执行时才选择阻塞锁。因此，如果线程预期等待的平均时间少于上下文切换时间的两倍，那么自旋实际上比阻塞更快。15 服务质量保证是在自旋锁和睡眠锁之间进行选择时需要考虑的另一个因素，尤其是在实时系统中。在更大的 NUMA 系统上阻塞最终可能会使系统资源匮乏。
此外，读写原语在处理共享路径或排他路径时可能具有不同的延迟。这不是理想的情况，因为用户必须考虑额外的开销损失，例如在共享锁时。更糟糕的是，用户甚至可能没有意识到这种差异，因此，共享锁实际上会导致比使用排他锁更差的性能。读写比率（稍后提到）是确定共享锁是否真的值得使用读锁的额外成本的重要因素。一般来说，选择错误的锁类型可能会影响性能，导致不必要的开销。
• 锁粒度。 这指的是锁保护的数据量，通常在复杂性和性能之间进行权衡。粗粒度往往更简单，使用更少的锁来保护大型临界区。另一方面，细粒度可以提高性能，但代价是更复杂的锁定方案，当锁发生争用时，细粒度尤其有利。在设计并发算法时，粗粒度锁可能会被误用，仅仅因为它们可能比细粒度替代方案更简单，并且最初更明显。由于与同步相关的错误（如死锁、竞争条件和一般损坏）可能特别难以调试，因此程序员可能仅仅因为恐惧和不确定性而更喜欢它们，并假设保护过多比保护不足更好。
更糟糕的是，这些问题很容易使整个软件系统不可靠，因此实际上毫无用处。即使经验丰富的锁从业者也可能忽略细粒度锁定的潜在性能优势，直到问题被报告后才注意到扩展问题。也许 Linux 内核中最著名的粗粒度锁是现在已被替换的 BKL（大内核锁），它序列化进入内核空间以服务系统调用的线程。由于该锁保护了如此多的数据，因此此类原语也称为巨型锁。Futex 是内核中另一个可能遭受粗粒度锁定方案影响的区域。使用链接哈希表架构，保护链的自旋锁可能仅因冲突而变得高度争用。通过简单地增加哈希表的大小，可以更精细地划分和并行化这些路径。这种方法将哈希吞吐量提高了高达八倍。3 这种细粒度技术也称为锁剥离，通过使用多个锁来序列化数组或基于列表的数据结构的不同、非依赖部分，从而提高并发性。
然而，粗粒度锁肯定有其用武之地。在处理粗粒度锁时，需要考虑的一个重要因素是单个锁的开销。在某些情况下，嵌入额外锁的额外内存占用将超过缓解争用的好处。滥用细粒度锁定可能对性能产生与滥用粗粒度锁定一样负面的影响。此外，当争用不是问题且临界区和持有时间很短时，粗粒度可能特别好，尽管这种情况很少见。
实践和研究都表明了结合粗粒度和细粒度的性能优势，尽管它通常更复杂。已经为 Hurricane 内核中的锁定提出了混合策略，结合了两种粒度的优点。16 20 多年来，Linux 内核的 SysV 信号量实现在处理semtimedop(2)系统调用时，一直遭受粗粒度锁定的困扰。当为这些调用引入更细粒度的锁定模型以处理任务等待操作包含多个信号量的数组中的单个信号量的常见情况时，基准测试吞吐量提高了九倍以上。13 这种混合策略还直接影响重要的 RDBMS（关系数据库管理系统）工作负载，后者严重依赖这些信号量进行内部锁定，争用从大约 85% 降至 7%。当操作多个信号量时，IPC（进程间通信）中的粗粒度锁定仍然可能发生。选择锁粒度必须是一个明智的决定。在程序生命周期后期更改粒度可能是一项昂贵且容易出错的任务。
• 读写比率。 这是只读临界区数量与数据被修改的区域数量之间的比率。读写锁将利用这些场景，允许多个读取器持有锁，同时在修改受保护数据时独占获取锁。多项研究和开发工作试图优化主要用于读取情况的原语，使读取器同步的成本尽可能低——通常以写入器线程的更高成本或开销为代价。示例包括 RCU（读取-复制更新）机制的变体、序列锁 (seqlocks) 和 FreeBSD 中的主要用于读取的锁 (rmlocks)。
众所周知，Linux 内核大量使用 RCU，允许无锁读取器与写入器共存。由于读取器实际上不持有锁，因此它是一种特别快速的机制，避免了常规读写锁产生的开销和硬件影响。RCU 通过以下方式处理更新：(1) 通过单指针读取和写入使更新对读取器可见，确保读取器在修改之前或之后执行，具体取决于他们是否及时看到更新；(2) 延迟数据结构的回收，直到所有读取器都完成其临界区，因为它保证没有读取器持有对数据结构的引用，类似于垃圾回收方法。在 2.5 时代初期，即 2000 年代初期引入，Linux 内核中 RCU 的采用大幅增长并非巧合，其中包括目录项 (dentry) 缓存、NMI（不可屏蔽中断）和进程 ID 处理的扩展等诸多示例。11 最近，将 epoll 控制接口从使用全局互斥锁转换为 RCU，允许文件描述符的添加和删除并发执行，从而实现了显着的性能改进。具体而言，重要的基于 Java 的工作负载在大型 HP 和 SGI NUMA 系统上获得了高达 2.5 倍的吞吐量提升。
• 公平性。 最重要的是，公平性通过使用严格的语义来选择在争用场景中哪个任务接下来有资格获取锁，从而避免锁饥饿。不公平自旋锁的一个常见示例是任何线程获取锁，而不考虑其他线程是否已经在等待它。这包括同一任务不断重新获取锁。不公平锁倾向于最大化吞吐量，但会产生更高的调用延迟。如果这种情况变得病态，则会真正引起对锁饥饿和缺乏进展的担忧——这在现实世界的软件中是不可接受的。对此的广泛使用的解决方案是票证自旋锁的不同变体。公平锁解决了饥饿问题，但代价是增加了抢占敏感性，1,6 这使得它们有时不适用于无法控制抢占的情况，例如用户空间应用程序。如果内核的 CPU 调度程序抢占了接下来要获取锁的任务，并且锁在此期间被释放，那么这将导致其余争用线程等待，直到抢占的任务被重新调度。同样，锁获取或释放的成本越高，过度排队导致性能下降的可能性就越大。
实验得出结论，不公平锁在每个核心运行多个线程时特别有用，因为它们在高度争用的场景中可以胜过公平替代方案。7 当然，由于线程必须等待更长时间才能获取锁，因此在处理 NUMA 系统时，这个问题可能会变得更加明显，特别是当公平锁导致昂贵的缓存行问题时，如下所述。
从统计学上讲，在 NUMA 系统中可能存在不同程度的公平性。例如，由于 CPU 节点局部性，如果线程位于本地内存节点上，则线程更有可能获取锁。通过将任何类型的忙等待锁转换为 NUMA 感知原语，开发了队列锁来解决其中的一些问题。在此方案中，写入器锁在同一 NUMA 节点内的争用线程之间传递，而读取器在同一节点内维护共享资源。
当处理读/写锁时，公平性会发生不同的转变，具体取决于上下文、工作负载和读写比率。在某些情况下，更适合优先考虑读取器，反之亦然。无论哪种方式，从业者都应特别注意原语不会使读取器或写入器线程饥饿到在某些用例中锁性能不佳的程度。一种替代方案是实现具有特定公平性偏好的同一读/写原语的不同变体，但这也可能导致开发人员在不同上下文中误用。出于性能原因，Linux 内核对 rw_semaphores 使用写入器锁窃取概念，打破了写入器的严格 FIFO（先进先出）公平性。写入器可以原子地获取锁，即使其他写入器已经排队。
• 缓存行处理不当。 对于低级锁定原语而言，缓存行抖动和争用可能是大型 NUMA 系统上最糟糕的两种性能下降形式。在争用锁上自旋的任务将尝试以某种形式的紧密 CAS 循环重复获取锁缓存行。对于每次迭代，通常在原子上下文中，包含锁的行都会从一个 CPU 缓存移动到另一个 CPU 缓存。很容易看出，随着 CPU 数量的增加，这种抖动将如何降低性能，导致昂贵的内存总线和互连使用损失。此外，如果受锁保护的数据结构与锁在同一缓存行中，则会显着减慢锁持有者的进度，从而导致锁持有时间更长。
一种解决缓存行抖动的直接方法是 30 年前14 提出的 CCAS（比较比较并交换）技术。其思想是对锁状态进行简单读取，仅在锁可用时才产生读-修改-写 CAS 操作。Linux 内核现在依赖 CCAS 技术来检查互斥锁和读/写信号量的内部计数器，以尝试独占获取锁（请注意，共享锁不需要这种 CAS 风暴）。具体而言，对于互斥锁，基于 Java 的基准测试在 16 插槽、240 核系统上体验了高达 90% 的吞吐量增长3。旨在主要在内核空间中执行的 AIM7 基准测试工作负载在八节点、80 核 Westmere 系统上也看到了显着的改进，吞吐量提高了高达三倍。至于读/写信号量，来自小型四核桌面系统上 pgbench 的 CCAS 结果显示，在 1 GB PostgreSQL 数据库上提高了高达 40%。最显着地改善了 mmap_sem 大量争用时发生的缓存行抖动，此锁的设计目的之一是序列化并发地址空间操作。
总的来说，实验表明，CCAS 技术将有助于具有四个或更多插槽或 NUMA 节点的大型高端系统。通常，在非争用情况下，检查计数器的开销非常低，以至于不会对较小系统的性能产生负面影响。性能工作必须始终确保不会在低端机器中引入任何退化，尤其是在 Linux 内核中，它涵盖了庞大的用户群。
或者，使用回退算法可以帮助缓解缓存行抖动和内存互连开销，这些算法解决了在锁上自旋时昂贵的 CAS 操作。与 CCAS 技术一样，其思想是在紧密自旋循环中延迟读-修改-写调用，主要区别在于锁不可立即用时的延迟因子。大量研究试图估计跨多个系统和工作负载的最佳延迟因子；不同的算法和启发式方法可以分为静态和动态。静态延迟时间可以针对特定工作负载进行优化，但当然，在需要通用锁定解决方案时，不一定表现良好。为此，动态延迟更现实，但代价是启发式方法中的额外开销以及误算回退策略的风险：线程不应回退太长时间，因为这会消除这些策略试图引入的任何性能优势。
回退算法的良好启发式方法基于尝试获取锁的 CPU 数量，例如成比例和指数，并借鉴了 CSMA（载波侦听多路访问）网络（如以太网）的类比。为了获得最佳延迟时间，需要估计临界区的长度和锁持有者释放锁的延迟，以便另一个线程可以获取锁。6,15 毋庸置疑，这种信息在现实世界的工作负载中很少可用。此外，回退算法没有解决以下事实：与常规 CAS 和 CCAS 自旋锁一样，所有线程都在同一共享位置上自旋，从而在每次成功获取锁时都会导致缓存一致性流量。考虑到这些注意事项，回退算法不适用于 Linux 内核也就不足为奇了，尽管在票证自旋锁和比例回退策略中已经看到了有希望的结果。5
演示缓存行争用的影响
锁定和并发的唯一目的是通过允许线程的正确并行执行来提高系统性能。即使在单处理器系统上，并发也允许在抢占式调度环境中产生多任务处理的错觉。如果锁定原语妨碍了性能，那么它们就只是坏掉了。当然，与正确性属性不同，性能不佳的锁在更大的系统上会更重要。
在现代大型多核 NUMA 系统中，缓存行争用的影响可能从产生适度可接受的开销到成为严重系统问题的罪魁祸首。表 1 显示了用作测试系统的三台高端 HP x86-64 服务器。3 所有这些机器都遵循正常的 NUMA 拓扑，其中核心和内存资源在节点之间均匀分布。因此，没有异常的 NUMA 用例。9 每个插槽或节点有 15 个核心，内存也均等分配。一个简单的自旋锁微基准测试就足以衡量大型 NUMA 系统中缓存行争用的成本——在这种情况下，使用基于 Linux 3.0 的自旋锁实现，在一个紧密的循环中迭代一百万次，仅获取和释放锁，类似于 rcutorture 等折磨程序会做的那样。
虽然这种病态行为不属于现实世界类别，但它很好地例证了锁争用等理论问题。此外，确实存在具有非常相似行为的真实软件，从而导致可怕的争用。根据线程数和循环迭代计数，当 N 个 CPU 参与缓存行争用时，可以计算出每个 CPU 每秒的平均操作数。这用作基准测试吞吐量。
为了充分理解缓存行争用的影响，必须在单个插槽内进行检查。否则，NUMA 感知和互连成本等因素将无法从结果中区分出来。此外，它应该提供最小的性能影响，因此可以为与其他涉及多插槽通信的结果进行比较提供一个基准。图 1 显示了在单个插槽内增加核心数时微基准吞吐量的回归。
很容易看出，随着更多核心参与缓存行争用，性能如何平稳地下降。通过最大化资源并使用单个插槽中的所有核心（即，七倍的因子），与仅使用两个核心相比，微基准吞吐量下降了 91.8%。因此，情况最终与幼稚的开发人员通常会直觉到的情况完全相反，他们期望通过盲目地投入更多核心，性能至少会“有所”提高。此外，在评估将逻辑上围绕 NUMA 拓扑结构划分其软件架构的系统时，91.8% 的下降可以被视为最大的性能损失。这通常是为了避免在处理远程内存时产生的延迟损失，尤其是在高端大型机器上。
当然，情况并没有好转。事实上，情况变得更糟。表 2 比较了单插槽和双插槽中缓存行争用的成本。最明显的是，当从 15 个核心增加到 30 个核心时，吞吐量下降了 80% 以上。
此外，当使用双插槽时，将锁的内存位置放在远程节点上的成本明显更高，与单插槽相比，吞吐量降低了 90% 以上。在这种情况下，基准测试的运行时间甚至更令人担忧，当内存完全远程时，完成一百万次迭代的时间从 2 秒增加到 21 秒。
核心数量不是衡量这种争用时唯一要考虑的因素。分配方法在性能中起着关键作用：当所有争用都包含在尽可能少的插槽中时，缓存行争用总是会更好。3 随着核心数量的增加，FF（首次填充）方法将始终尝试使用同一插槽中可用的核心，而 RR（轮询）分配将使用来自越来越多插槽的核心。
图 2 展示了内部缓存行争用与跨缓存行争用的概率，通过计算 100/插槽数来估计。因此，越来越大型的多插槽系统，两个随机核心参与同一缓存行争用时，它们位于同一插槽的可能性会大大降低。
这可能会对性能产生灾难性的影响，并表明双插槽系统中的争用与 16 插槽系统中的争用截然不同。因此，为较小系统调整的应用不能盲目地在较大系统上执行，并立即期望获得良好的结果，而没有事先仔细的思考和分析。正如先前所见，仅基于 CPU 数量的扩展很可能会在 Linux 内核内部引入显著的锁和缓存行争用。
排队/MCS：可扩展锁
正如已经讨论过的，即使是带有 CCAS 或退避策略的忙等待锁，也可能产生足够的缓存行争用，从而显著影响大型机器上的整体系统性能。因此，它们固有的不公平性使它们在锁变得争用时暴露于不规则数量的缓存未命中。另一方面，真正的可扩展锁是指每次获取操作产生恒定数量的缓存未命中或远程访问的锁2，从而避免了非可扩展替代方案中发生的突然性能崩溃。排队锁通过确保每个争用线程都在 CPU 的本地内存而不是锁字上自旋来做到这一点。由于这种确定性，排队锁是公平的，通常以 FIFO 顺序将锁的所有权授予等待线程。这些锁的另一个吸引人的特性是开销，对于 n 个线程和 j 个锁，仅需要 O(n+j) 空间15，而不是非可扩展原语的 O(nj)。大多数形式的排队锁——MCS、K42 和 CLH，仅举几个流行的例子——都维护一个等待者队列，每个等待者都在其自己的队列条目上自旋。这些锁的区别在于如何维护队列以及锁接口所需的更改。
一个常见的实验是用 MCS 锁2,3 替换常规自旋锁，总是在内核空间（通常使用 Linux 内核）中获得非常好的结果。图 3 比较了 vanilla 2.6 Linux 自旋锁和一个原型 MCS 实现，在 AIM7 文件系统基准测试中，使用单个锁序列化并发链表操作。此全局自旋锁上的争用是所有缓存行争用的原因。
随着更多用户添加到工作负载中，spinlock 情况下的吞吐量（每分钟作业数）迅速趋于平稳，而 MCS 锁的情况则稳步提高了 2.4 倍。同样，系统时间从 54% 下降到仅 2%；因此，瓶颈被完全消除。由于没有进行额外的优化工作，例如更细粒度的锁，因此可以安全地得出结论，MCS 锁仅通过最小化插槽间缓存行流量就产生了巨大的影响。
为此，MCS 锁已添加到 Linux 内核2 中，尤其是在休眠信号量的自旋逻辑中。对于互斥锁，这在流行的 Java 工作负载中，在用于 SAP HANA 的 16 插槽、240 核 HP 融合系统 900 上，提供了约 248% 的吞吐量提升。以下代码显示了原语的接口
struct mcs_spinlock {
struct mcs_spinlock *next;
int locked;
};
void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node);
void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node);
其想法是，当线程需要获取争用锁时，它将传递自己的本地节点作为参数，以无等待方式将自己添加到队列中，并在其自己的缓存行（特别是 node->locked）上自旋，直到轮到它获取锁。FIFO 公平性自然而然地到来，因为当前锁持有者将在释放锁时将锁传递给链表中的下一个 CPU。该算法的一个缺点是，为了将自身添加到等待队列中，任务必须将其本地节点的指针存储在其前驱的 ->next 字段中，如果前驱任务需要释放锁，则可能会产生额外的开销。
不幸的是，如果不扩大锁的大小，就无法在常规票据自旋锁中使用 MCS 锁。自旋锁在整个内核中使用，并且不能大于 32 位字长。为此，其他排队锁定方法17 为当前的票据系统提供了有效的替代方案。
结论
在设计锁定原语时考虑到性能，不仅通常是一种良好的实践，而且还可以缓解未来的问题。本文源于使用大型服务器的经验，以及影响 Linux 用户的实际问题。虽然 Donald E. Knuth 曾说过“过早的优化是万恶之源”，但在实现锁定原语时却恰恰相反。经验数据和实验表明了误用锁或忽略锁定的底层硬件影响的代价。此外，用户和实现者都必须特别注意如何使用这些锁以及锁生命周期中特定决策的后果，例如不同程度的争用。
未来，随着计算机系统的发展和处理能力的提高，锁定原语的实践和理论也需要相应地调整，最终更好地利用硬件架构。即使在今天，也有非常专业的锁可用，例如队列锁和分层原语（如 HCLH），它们针对内存局部性进行了优化，解决了基于退避锁的公平性问题，同时保留了基于排队锁的优势。
当然，没有适用于锁定性能和可扩展性的单一秘诀，读者还可以继续关注许多其他相关主题，包括无锁数据结构以及解决特定系统（例如实时环境的优先级反转和继承）的特定约束。本文至少应作为一种在从业人员在大型系统上处理严重的扩展问题时提高意识的方式。
致谢
Linux 内核中的扩展工作是团队共同努力的结果，包括 Hewlett-Packard Linux 性能组内部和上游内核社区，他们提供了宝贵的反馈和有趣的讨论。非常感谢 Scott J. Norton。如果没有他的分析和经验数据，将很难意识到不良实现的原语所带来的深刻的架构影响。我感谢 Paul E. McKenney 的支持和 Samy Al Bahra 的仔细审查和建议，使本文更加完善。感谢 Jim Maurer 和 Queue 团队其他成员的支持和反馈。
法律声明
这项工作代表了作者的观点，并不一定代表 SUSE LLC 的观点。Linux 是 Linus Torvalds 的注册商标。其他公司、产品和服务名称可能是其他公司的商标或服务标志。
参考文献
1. Al Bahra, S. 2013. 非阻塞算法和可扩展多核编程。 11(5).
2. Boyd-Wickizer, S. Kaashoek, F. M., Morris, R. Zeldovich, N. 2012. 不可扩展的锁是危险的。Linux Symposium 会议论文集。加拿大渥太华。
3. Bueso, D., Norton, S. J. 2014. 内核锁改进概述。LinuxCon 北美，伊利诺伊州芝加哥；http://events.linuxfoundation.org/sites/events/files/slides/linuxcon-2014-locking-final.pdf.
4. Corbet, J. 2013. 在 struct page 中塞入更多内容。LWN.net；http://lwn.net/Articles/565097/.
5. Corbet, J. 2013. 改进票据自旋锁。LWN.net；http://lwn.net/Articles/531254/.
6. Crummey-Mellor, J. M., Scott, M. L. 1991. 共享内存多处理器上的可扩展同步算法。 Transactions of Computer Systems 9(1): 21-65.
7. Fuerst, S. 2014. 不公平和锁定。Lockless Inc.; http://locklessinc.com/articles/unfairness/.
8. Gray, J. N., Lorie, R. A., Putzolu, G. R., Traiger, I. L. 1975. 共享数据库中锁的粒度和一致性程度。加利福尼亚州圣何塞：IBM 研究实验室。
9. Lameter, C. 2014. NUMA 功能的正常和非常规用例。Linux Foundation Collaboration Summit，加利福尼亚州纳帕。
10. McKenney, P. E. 2014. 并行编程很难吗？如果是，您能做些什么？；https://linuxkernel.org.cn/pub/linux/kernel/people/paulmck/perfbook/perfbook.html.
11. McKenney, P. E., Boyd-Wickizer, S., Walpole, J. 2013. Linux 内核中 RCU 的使用：十年之后；http://www2.rdrop.com/users/paulmck/techreports/RCUUsage.2013.02.24a.pdf.
12. Molnar, I. Bueso, D. 2014. 通用互斥子系统的设计。Linux 内核源代码：documentation/mutex-design.txt。
13. van Riel, R., Bueso, D. 2013. ipc,sem: sysv 信号量可扩展性。LWN.net；http://lwn.net/Articles/543659/.
14. Rudolph, L., Segall, Z. 1984. MIMD 并行处理器的动态分散缓存方案。第 11 届年度国际计算机体系结构研讨会会议记录：340-347。
15. Scott, M. L. 2013. 共享内存同步。 计算机体系结构综合讲义。 加利福尼亚州圣拉斐尔：Morgan & Claypool Publishers。
16. Unrau, R. C. Krieger, O. Gamsa, B., Stumm, M. 1994. NUMA 多处理器操作系统内核中的锁定经验。操作系统设计与实现研讨会；https://www.usenix.org/legacy/publications/library/proceedings/osdi/full_papers/unrau.a.
17. Zijlstra, P., Long, W. 2014. locking: qspinlock。LWN.net；http://lwn.net/Articles/590189/.
喜欢还是讨厌？请告诉我们
Davidlohr Bueso 是 SUSE 实验室的性能工程师。他是 Linux 内核的活跃贡献者，领域包括同步原语、内存管理和 IPC——所有这些都特别关注可扩展性。他对性能的兴趣可以追溯到研究生院，他在那里探索了改进虚拟机监控程序内存管理的方法，以完成他的理学硕士论文。最近，作为 Hewlett-Packard 的软件工程师，他参与了大型高端 x86-64 系统上重要的 Linux 内核扩展工作。
© 2014 1542-7730/14/1100 $10.00
最初发表于 Queue vol. 12, no. 11—
在 数字图书馆 中评论本文
更多相关文章
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 的更好抽象来解决。这些允许程序员将异步函数调用连接在一起，等待每个函数返回成功或失败，然后再运行链中的下一个适当函数。
John T. Richards, Jonathan Brezin, Calvin B. Swart, Christine A. Halverson - 并行编程的生产力：十年的进展
2002 年，DARPA（国防高级研究计划局）启动了一项 HPCS（高生产力计算系统）的重大计划。该计划的动机是相信，即将到来的并行机器的利用受到在 peta 规模上编写、调试、调整和维护软件的难度的限制。
© 保留所有权利。