ACM通信

实践

用于实际同步原语的可伸缩性技术

由Davidlohr Bueso
ACM通信，2015年1月，第58卷第1期，第66-74页
10.1145 / 2687882
评论

在理想的情况下，当在越来越大的系统上执行时，应用程序应该能够自动伸缩。然而，在实践中，这种扩展不仅不会发生，而且在那些大型系统上，性能实际上还会恶化。

而性能而且可伸缩性可能是模棱两可的术语，但当问题出现在软件堆栈的较低端时，就不那么模棱两可了。这只是因为在评估性能问题时要考虑的因素减少了。因此，并发多线程程序(如操作系统内核、管理程序和数据库引擎)在滥用硬件资源时会付出很高的代价。

这将转化为在堆栈中较高位置执行的应用程序的性能问题。一个明显的例子是共享内存系统的同步原语(锁)的设计和实现。锁是一种允许多个线程并发执行的方法，通过互斥提供安全和正确的执行上下文。为了实现序列化，锁通常需要通过使用原子操作(如比较-交换(CAS)、获取-添加和算术指令)来获得硬件支持。虽然细节在不同的缓存相关体系结构中有所不同，但原子操作将在内存总线中广播更改，为每个核心更新共享变量的值，强制缓存线失效，从而导致更多的缓存线丢失。软件工程师经常滥用这些原语，导致糟糕的锁粒度或高延迟导致显著的性能下降。

锁的正确性和性能都取决于底层硬件架构。这就是为什么可伸缩性和硬件影响在锁定算法的设计中如此重要。不幸的是，在真实的软件中，这些都是很少需要考虑的。

随着越来越大的多核和多核NUMA(非统一内存访问)系统的出现，糟糕的锁定实现的性能损失变得非常明显。这些惩罚适用于实际原语的实现及其使用，许多开发人员通过为数据序列化设计锁定方案直接控制后者。经过几十年的研究，这是一个众所周知的事实，从来没有比今天更真实。尽管最近出现了诸如锁省略和事务内存等技术，但是，并发性、并行编程和同步对于从业者来说仍然是具有挑战性的主题。¹⁰

此外，由于事务同步扩展(TSX)等事务内存系统在事务不成功时仍然需要一个带常规锁的回退路径，因此这些挑战不会很快消失。此外，交易系统不能保证饥饿自由之外的具体进展;因此，对于常规锁定方案，这并不总是可行的选择。由于复杂性，系统不仅缺乏可伸缩性，而且其整体性能也会受到影响。以前的工作已经证明，糟糕的、不可扩展的锁定实现的成本会随着系统中内核数量的增加而增加。²事实上，性能崩溃的发生可能非常突然，只需要在等式中增加几个核心。性能和可伸缩性的问题远远超出了合成工作负载和基准测试，影响了真实的软件。

最近，在解决大型高端服务器上Linux内核中的锁扩展问题方面做出了重大努力。^3.许多问题和解决方案适用于类似的系统软件。本文将一般思想和经验教训应用于更广泛的系统受众，希望对遇到类似伸缩问题的人有所帮助。当然，锁在任何共享内存系统中都很重要，但是优化它们并不意味着忽略更重要的方面:如何使用这些锁以及序列化什么。

回到顶部

混合锁定模型和乐观自旋

锁定原语传统上被分类为忙等待或阻塞，这取决于锁不是立即可用时发生的情况。如果锁保持时间很短，比如只序列化引用计数操作，那么避免所有阻塞开销，只在短时间内消耗CPU周期更有意义。这通常通过循环CAS调用来实现，直到满足解锁条件。另一种方法是阻塞，直到该条件变为真。除了更高的开销和延迟之外，阻塞原语通常严格依赖于操作系统内核的调度器。因此，线程调度策略将越来越依赖于软件堆栈中的前一执行级别，例如，在硬件、内核或多个用户空间层。多个调度策略会影响锁的公平性和确定性。

在建造睡眠锁时，颠簸是另一个需要注意的因素。实践者必须考虑重度锁争用下的系统后果。忙-等待原语的流行例子是内存障碍和自旋锁。阻塞机制通常包括信号量和监视器。例如，Linux内核主要有三种睡眠信号量:互斥锁(二进制)和两种计数信号量，其中包括一个广泛使用的读写器变体。

使用混合模型是处理每种锁类型的权衡的常用方法。目标是尽可能地延迟阻塞，并乐观地忙碌等待，直到锁定可用。但是，确定锁何时休眠会影响性能。该算法需要在不同的工作负载中同样出色地执行，但受益可能不同。换句话说，当CPU在一段确定的时间内第一次启动一个锁时，那些明确希望获得休眠锁特性的用户不会付出性能代价——通常情况下，甚至根本不会。此外，不应该允许通用锁定原语的用户影响他们的算法行为。错误地设计锁定api可能会在以后导致意想不到的后果，比如当锁定被大量使用时。简单是一个优点，也是设计良好的锁定接口的结果。

通过使用锁所有权的概念，Linux内核保留了一个指向当前持有锁的任务的指针。了解锁的所有者有两个好处:在确定何时停止旋转时，这是一个关键数据;它用于调试，例如，死锁检测。类似的策略可以追溯到1975年，提出了数据库中锁所有权的概念。⁸由于维护锁所有权的开销，实现者可以决定不使用可重入锁，可重入锁通常也使用计数器字段。¹⁵

乐观旋转背后的基本原理是，如果拥有锁的线程正在运行，那么它很可能很快就会释放锁。在实践中，Linux内核互斥锁或rw_semaphore(读写信号量)是整个系统中最常用的两种锁，根据其当前状态，在获取锁时可以遵循三条可能的路径:¹²

• 快速路径。它试图通过修改内部计数器(如fetch_and_add或原子递减)原子地获取锁。这个逻辑是特定于体系结构的。所示图1在x86-64中，互斥锁快速路径只有两个用于锁定和解锁调用的指令:
• Midpath(又名乐观旋转)。它尝试在锁所有者正在运行且没有其他高优先级的任务准备运行时进行旋转获取，因此需要重新调度。微调线程使用MCS锁进行排队，这样只有一个微调线程可以竞争锁。
• Slowpath。作为最后的手段，如果仍然无法获得锁，任务将被添加到等待队列并休眠，直到解锁路径唤醒它。

因为混合锁仍然会阻塞，所以这些原语需要在睡眠环境中安全地使用。乐观旋转已经在Linux和Solaris等操作系统内核中证明了它的价值。即使到今天，简单地延迟任何类型的阻塞开销都可能对系统软件产生重要影响。在Linux虚拟文件系统(VFS)创建+断开连接的微基准测试上，与立即休眠相比，乐观旋转在普通桌面系统上的吞吐量提高了约3.5倍。类似地，对于AIM7工作负载上的rw_信号量，混合锁定提供了大约1.8倍的吞吐量。^3.

在Linux内核中，rw_semapore和互斥锁之间的一个显著区别是它们处理锁所有权的方式。当一个锁被共享时，所有权的概念比独占锁更加模糊。当工作负载同时包含读取器和写入器时，乐观旋转可能会使写入器过度旋转，因为当读取器持有它时，没有所有者可以旋转。克服这个问题的策略是存在的，比如使用启发式和神奇数字来决定读者何时停止旋转。然而，读者所有权可能特别棘手，而且往往会在乐观的快速路径中增加额外的复杂性和开销。此外，在锁定原语中使用魔法数可能会带来意想不到的后果，因此不能轻率使用。就其本质而言，启发式可以帮助特定的场景，但在普通情况下实际上会损害性能。可伸缩性不是针对1%的用户进行优化，而不考虑其他99%的用户，而是恰恰相反。此外，在考虑过于复杂的原语之前，解决实际的争用源是一种有效的替代方法。

回到顶部

导致锁伸缩性差的因素

在任何给定的时间内，发现导致锁性能低下的多种因素并不罕见。当然，影响将根据每个系统和工作负载而不同。这里描述的因素和锁属性可以在软件工程级别进行划分:实现人员(通常设计和实现锁定原语)和用户(严格将它们应用于并行或并发工作负载和算法)之间。

• 临界区长度。减少临界区域的长度当然有助于缓解锁争用。此外，锁实现中用于序列化并发线程的原语类型在性能方面也起着关键作用。在慢路径中持有锁时，例如在获取或释放锁时处理争用场景的锁，实践者通常需要为等待采取某些操作的线程管理内部等待队列。在这些情况下，实现者必须确保关键区域足够短，以免引起不必要的内部争用。例如，发出预检查或唤醒(用于休眠原语)可以很容易地异步完成，而不需要任何额外的序列化。最近，在Linux内核中，缩短互斥锁和SysV信号量(以及其他形式的进程间通信)中的关键区域的努力提供了重要的性能优势。^3.，13
• 锁的开销。这是使用特定锁在大小和延迟方面的资源成本。例如，嵌入在数据结构中的锁将使该类型膨胀。更大的结构大小意味着更多的CPU缓存和内存占用。因此，当一个结构在整个系统中频繁使用时，大小是一个重要因素。在经过一些重要的修改之后，在扩大锁类型时，实现者还需要考虑锁开销;这可能会在意想不到的地方导致性能问题。例如，Linux内核文件系统和内存管理开发人员必须特别注意VFS结构inode(索引节点)和结构页面的大小，尽可能地进行优化。⁴这些数据结构分别表示关于系统上每个文件和每个物理页帧的信息。因此，存在的文件或内存越多，内核处理的这些结构的实例就越多。拥有数千万个缓存inode的机器并不少见，因此将inode的大小增加4%是非常重要的。这足以使工作负载从平衡良好到无法适应内存中的inode工作集。实现者必须始终牢记锁定原语的大小。

由于其简单的性质，忙碌-等待原语比更复杂的锁具有更好的延迟。初始化调用，特别是获取或释放锁的调用，需要很便宜，只需要最少的CPU周期。管理原语的内部逻辑不能与影响调用延迟的其他因素混淆，例如保持时间和争用。阻塞(或休眠)锁的成本预计会更高，因为任何算法都至少必须考虑到一些事件，比如让线程休眠并在锁可用时唤醒它们。当然，代价是用户只在处理大型关键区域或在需要休眠的上下文中执行时(例如分配内存时)才选择阻塞锁。因此，如果线程期望等待的平均时间少于上下文切换时间的两倍，那么旋转实际上会比阻塞快。¹⁵服务质量保证是选择旋转锁和休眠锁时要考虑的另一个因素，特别是在实时系统中。在较大的NUMA系统上阻塞最终会使系统资源枯竭。

---

在任何给定的时间内，发现导致锁性能低下的多种因素并不罕见。当然，影响将根据每个系统和工作负载而不同。

---

此外，读写原语在处理共享或独占路径时可能具有不同的延迟。这不是一个理想的情况，因为用户将不得不考虑在共享锁时额外的开销。更糟糕的是，用户甚至可能没有意识到这种差异，因此，共享锁实际上会导致比使用排他锁更差的性能。当决定共享锁是否值得使用读取器锁的额外成本时，读:写比率(稍后讨论)是一个重要因素。一般来说，选择错误的锁类型会影响性能，产生不必要的开销。

• 锁的粒度。这是指锁保护的数据量，通常需要在复杂性和性能之间权衡。粗粒度往往更简单，使用更少的锁来保护大的关键区域。另一方面，细粒度可以以更复杂的锁定方案为代价提高性能，特别是在锁处于争用时。在设计并发算法时，粗粒度锁可能会被误用，因为它们比细粒度的替代方案更简单，而且在最初更明显。因为与同步相关的bug，如死锁、竞态条件和一般的破坏，可能特别难以调试，程序员可能只是因为恐惧和不确定性而偏爱它们，认为保护得太多总比不够好。

更糟糕的是，这些问题很容易使整个软件系统变得不可靠，实际上是无用的。即使是经验丰富的锁实践者也会忽视细粒度锁的潜在性能优势，直到报告才会注意到伸缩性问题。也许Linux内核中最著名的粗粒度锁是现在被取代的大内核锁(BLK)，它序列化进入内核空间的线程，为系统调用提供服务。由于锁保护了如此多的数据，这样的原语也被称为巨型锁。Futexes是内核中另一个可能受到粗粒度锁定方案影响的区域。在链式哈希表体系结构中，保护链的自旋锁只会因为碰撞而变得严重争用。通过简单地增加哈希表的大小，可以实现更细的粒度化和并行化这些路径。这种方法将哈希吞吐量提高了多达8倍。^3.这种细粒度技术也称为锁剥离，通过使用多个锁来序列化数组或基于列表的数据结构中不同的、不相关的部分，从而提高并发性。

尽管如此，粗粒度的锁确实有它们的一席之地。在处理粗粒度锁时，要考虑的一个重要因素是单个锁的开销。在某些情况下，嵌入额外锁的额外内存占用会掩盖缓解争用的好处。滥用细粒度锁定对性能的负面影响与滥用粗粒度锁定同样严重。此外，当争用不是问题并且临界区域和保持时间很短(尽管很少)时，粗粒度可能特别好。

实践和研究都显示了组合粗粒度和细粒度的性能优势，尽管它通常更复杂。

---

在慢路径中持有锁时，实践者通常需要管理等待采取某些操作的线程的内部等待队列。

---

已经提出了用于锁定Hurricane内核的混合策略，结合了这两种粒度的优点。¹⁶20多年来，Linux内核的SysV信号量实现在处理时一直受到粗粒度锁定的困扰semtimedop(2)系统调用。当为这些调用引入细粒度的锁定模型来处理任务等待操作包含多个信号量的数组中的单个信号量的常见情况时，基准吞吐量提高了9倍以上。¹³这种混合策略还直接影响严重依赖这些信号量进行内部锁定的重要RDBMS(关系数据库管理系统)工作负载，竞争将从大约85%下降到7%。当操作多个信号量时，IPC(进程间通信)中的粗粒度锁定仍然会发生。选择锁粒度必须是一个明智的决策。在程序生命周期的后期更改粒度可能是一项昂贵且容易出错的任务。

• 读/写比率。这是只读临界区域的数量与被修改数据的区域数量之间的比率。读取器/写入器锁将利用这些场景，允许多个读取器持有锁，同时在修改受保护数据时独家获取它。许多研究和开发工作都试图针对大多数读操作的情况优化原语，使读取器同步的成本尽可能最小，但写入器线程的成本或开销更高。例如，FreeBSD中的RCU(读拷贝更新)机制、序列锁(seqlocks)和读大部分锁(rm-locks)的变体。

众所周知，Linux内核大量使用了RCU，允许无锁读器和写器共存。因为读取器实际上并不持有锁，所以它是一种特别快的机制，可以避免常规读取器/写入器锁带来的开销和硬件影响。RCU处理更新的方式是:通过单指针读和写，使它们对reader可见，确保reader在修改之前或之后执行，取决于它们是否及时看到更新;并且延迟数据结构的回收，直到所有读取器都完成了它们的临界区域，因为可以保证没有读取器持有对数据结构的引用，这与垃圾收集方法类似。RCU引入于2.5时代，在21世纪初，它在内核中的应用得到了大幅增长，这并非巧合，其中包括dentry(目录条目)缓存、NMI(不可屏蔽中断)和进程ID处理的扩展。¹¹最近，将epoll控制接口从使用全局互斥锁转换为RCU，通过允许文件描述符的添加和删除并发进行，显著提高了性能。具体来说，在大型HP和SGI NUMA系统上，重要的基于java的工作负载得到了提升，吞吐量提高了2.5倍。

• 公平。最重要的是，公平性通过使用严格的语义来选择在竞争场景中下一个获得锁的任务，从而避免了锁短缺。不公平自旋锁的一个常见例子是，任何线程在获取锁时都不考虑其他线程是否已经在等待它。这包括不断重新获取锁的相同任务。不公平锁定往往会使吞吐量最大化，但会导致更高的调用延迟。如果这样的场景变成病态的，那么就会真正担心在现实世界的软件中无法接受的锁短缺和进度不足。对此广泛使用的解决方案是不同的票据自旋锁变体。公平锁以增加抢占敏感性为代价解决了饥饿问题，^1，6在抢占无法控制的情况下，例如在用户空间应用程序中，使它们不适合使用。如果内核的CPU调度程序抢占下一个获取锁的任务，并且锁在此期间被释放，那么它将导致其他竞争线程等待，直到被抢占的任务被重新调度。类似地，获取或释放锁的成本越大，过度排队导致性能差的可能性就越大。

实验得出的结论是，当每个核心运行多个线程时，不公平锁特别有用，因为在高度竞争的场景中，不公平锁的性能优于公平锁。⁷当然，由于线程必须等待更长的时间才能获得锁，因此在处理NUMA系统时，这个问题会变得更加明显，特别是在公平锁导致昂贵的缓存线问题时(如后面所述)。

统计上，在NUMA系统中可能有不同程度的公平。例如，由于CPU节点的位置，如果锁位于本地内存节点上，线程就有更好的机会获得锁。通过将任何类型的忙等待锁转换为numa感知的原语，队列锁被开发出来以解决其中一些问题。在此方案中，写入器锁在同一NUMA节点内的竞争线程之间传递，而读取器维护同一节点内的共享资源。

在处理读/写锁时，公平性会发生不同的变化，这取决于上下文、工作负载和读写器比。在某些情况下，优先考虑读者更合适，反之亦然。无论哪种方式，实践者都应该特别注意原语不要使读线程或写线程处于饥饿状态，从而使锁在某些用例中性能很差。一种替代方法是使用特定的公平首选项实现相同读/写原语的不同变体，但这也可能导致开发人员在不同的上下文中误用。出于性能原因，Linux内核对rw_信号量使用了写锁窃取的概念，打破了对写器严格的FIFO(先进先出)公平性。写入器可以原子地获取锁，即使其他写入器已经排队。

• 高速缓存线路处理不当。当涉及到低级锁定原语时，缓存线反弹和争用可能是大型NUMA系统上最严重的两种性能退化形式。在争用锁上旋转的任务将尝试以某种紧凑的CAS循环形式重复获取锁缓存线。对于每次迭代(通常在原子上下文中)，包含锁的行将从一个CPU缓存移动到另一个CPU缓存。很容易看出，随着CPU数量的增加，这种反弹将如何降低性能，导致昂贵的内存总线和互连使用损失。此外，如果锁保护的数据结构在同一条缓存线中，它会显著降低锁持有者的进程，导致锁持有时间更长。

30年前就有人提出了一种解决缓存线反弹的直接方法¹⁴使用比较、比较和交换(CCAS)技术。其思想是对锁状态进行简单的读取，并仅在锁可用时触发读-修改-写CAS操作。Linux内核现在依赖CCAS技术来对互斥锁和读/写信号量进行内部计数器检查，当试图独占获取一个锁时(注意，共享锁不需要这样的CAS风暴)。具体来说，对于互斥锁，基于java的基准测试的吞吐量增加了90%^3.在一个16插座，240核的系统上。设计为主要在内核空间中执行的AIM7基准工作负载在八节点、80核的Westmere系统上也有明显的改进，吞吐量增加了三倍。至于读/写信号量，pgbench在较小的四核桌面系统上的CCAS结果显示，在1GB PostgreSQL数据库上提高了高达40%。最显著的改善是在mmap_sem严重争用时发生的缓存线反弹，该锁被设计为(除其他外)序列化并发地址空间操作。

一般来说，实验表明CCAS技术将有助于具有四个或更多套接字(或NUMA节点)的大型高端系统。通常，在无争用情况下，检查计数器的开销非常低，因此不会对较小系统的性能产生负面影响。性能工作必须始终确保在低端机器中不引入倒退，特别是在Linux内核中，它跨越了巨大的用户基础。

另外，使用回退算法(在旋转锁时处理昂贵的CAS操作)可以帮助减轻缓存线反弹和内存互连开销。与CCAS技术一样，其思想是在紧密的循环中延迟读-修改-写调用，主要的区别是当锁不是立即可用时的延迟因素。大量研究试图估算跨多个系统和工作负载的最佳延迟因子;不同的算法和启发式可分为静态和动态。对于特定的工作负载，可以对静态的延迟时间进行优化，但是在需要通用锁定解决方案时，这当然不一定能很好地执行。为此，动态延迟要现实得多，但代价是要付出额外的启发式开销和错误计算后退策略的风险:线程不应该后退太长时间，因为这可能会掩盖这些策略试图引入的性能好处。

撤销算法的良好启发式是基于试图获取锁的cpu数量(如比例和指数)，并与CSMA(载波感知多路访问)网络(如以太网)进行类比。延迟最佳时间需要估计临界区域的长度和锁持有者释放锁以便另一个线程获得锁的延迟。^6，15不用说，这类信息在实际工作负载中很少可用。此外，回退算法不能解决以下事实:与常规CAS和CCAS自旋锁一样，所有线程都在相同的共享位置上自旋，在每次成功获取锁时导致缓存一致性流量。有了这些警告，后退算法不适合Linux内核就不足为奇了，尽管票证自旋锁和比例后退策略已经看到了有前景的结果。⁵

回到顶部

演示缓存线争用的效果

锁定和并发的唯一目的是通过允许线程的正确并行执行来提高系统性能。即使在单处理器系统上，并发性也允许在抢占式调度环境中出现多任务处理的假象。如果锁定原语妨碍了性能，那么它们就是被破坏了。当然，与正确性属性不同，性能较差的锁在较大的系统中更重要。

在现代大规模多核NUMA系统中，缓存线争用的影响可能会从产生中等可接受的开销变成严重系统问题的罪魁祸首。表1展示了三台用于测试系统的高端HP x86-64服务器。^3.所有这些机器都遵循正常的NUMA拓扑，其中核心和内存资源在节点之间均匀分布。因此，不存在奇异的NUMA用例。⁹每个套接字或节点有15个核，内存也被平均分配。一个简单的自旋锁微基准足以衡量大型NUMA系统中缓存线争用的成本。在本例中，使用基于Linux 3.0的自旋锁实现，在一个紧密的循环中迭代100万次，仅仅是获取和释放锁，类似于rcutorture等折磨程序所做的。

虽然这种病态行为不属于现实世界的范畴，但它很好地说明了锁争用等理论问题。此外，具有非常相似行为的真实软件确实存在，这导致了可怕的竞争。根据线程数和循环迭代计数，当个CPU参与缓存线竞争时，可以计算每个CPU每秒的平均操作数。这作为基准吞吐量。

为了充分理解缓存线争用的影响，检查必须包括单个套接字。否则，NUMA意识和互连成本等因素无法从结果中区分出来。此外，它应该提供最小的性能影响，因此可以提供一个与涉及多套接字通信的其他结果进行比较的基础。图2通过增加单个套接字内的核心计数显示微基准吞吐量回归。

很容易看出，随着更多的核心参与缓存线争用，性能是如何平稳地下降的。通过最大限度地利用资源并在一个套接字中使用所有内核(即7倍)，与仅使用两个内核相比，微基准测试吞吐量降低了91.8%。因此，这种情况的结果与天真的开发人员通常的直觉完全相反，他们期望通过盲目地添加更多的内核，性能至少会提高“一些”。此外，在评估将软件架构逻辑上围绕NUMA拓扑划分的系统时，91.8%的回归可以被认为是最大的性能损失。通常这样做是为了在处理远程内存时避免延迟，特别是在大型机器上。

当然，情况并没有好转。事实上，情况会变得更糟。表2比较单个套接字与两个套接字中缓存线争用的代价。最值得注意的是，当从15核到30核时，吞吐量下降了80%以上。

此外，当使用两个套接字时，将锁的内存位置放在远程节点上的成本显然更低，与单个套接字相比，吞吐量降低了90%以上。在这种情况下，基准测试运行时更加令人担忧，当内存完全位于远程时，完成百万次迭代的时间从2秒到21秒不等。

在度量这类争用时，内核的数量并不是唯一要考虑的因素。分布方法在性能上起着关键作用，当所有的争用都包含在尽可能少的套接字中时，缓存线争用总是更好的随着内核数量的增加，FF(第一个填充)方法将总是尝试使用同一套接字中可用的内核，而RR(轮循)分布将使用来自不断增加的套接字计数的内核。

图3通过计算100/num_sockets，显示缓存线间与缓存线内争用的概率。因此，越来越大的多套接字系统中，参与同一缓存线竞争的两个随机内核驻留在同一套接字上的几率将大大降低。

这可能会对性能产生灾难性的影响，并说明双套接字系统中的争用与16套接字系统中的争用截然不同。因此，针对较小系统调优的应用程序不能盲目地在较大的系统上执行，也不能在没有事先仔细考虑和分析的情况下立即期待良好的结果。如前所述，仅基于cpu数量的扩展可能会在Linux内核中引入大量的锁和缓存线争用。

回到顶部

排队/ MCS:可伸缩的锁定

如前所述，即使是CCAS的忙等待锁或后退策略也会引起缓存线争用，从而在大型机器上显著影响整体系统性能。因此，当锁成为争用时，它们固有的不公平性质使它们面临不规则数量的缓存丢失。另一方面，真正可伸缩的锁是在每次获取时产生恒定数量的缓存丢失或远程访问，²这样就避免了不可伸缩替代方案突然出现的性能崩溃。队列锁通过确保每个竞争线程旋转以获得CPU本地内存上的锁(而不是锁字)来实现这一点。由于这种确定性，排队锁是公平的，通常以FIFO的顺序将锁所有权授予等待线程。这些锁的另一个吸引人的特性是开销，n个线程和j个锁只需要O(n+j)空间，¹⁵而非可伸缩原语的O(nj)。大多数排队的locksMCS、K42和CLH(举几个流行的例子)都维护一个等待者队列，每个等待者都在自己的队列条目上旋转。这些锁的区别在于队列的维护方式以及锁的接口所需要的更改。

一个常见的实验是用MCS锁替换常规的自旋锁，^2，3.在内核空间(通常使用Linux内核)中总是有非常出色的结果。图4将普通的2.6 Linux自旋锁与aiaim7文件系统基准上的MCS原型实现进行比较，后者使用单个锁序列化并发链表操作。这个全局自旋锁上的争用是所有缓存线争用的原因。

随着更多的用户添加到工作负载中，自旋锁情况下的吞吐量(每分钟任务)很快就会趋于平缓，而使用MCS锁时，吞吐量稳定地提高了2.4倍。类似地，系统时间从54%下降到仅仅2%;因此，瓶颈被完全消除了。由于没有进行额外的优化工作，例如细化锁的粒度，因此可以有把握地得出结论，MCS锁仅通过最小化套接字间缓存线流量而产生巨大的影响。

为此，MCS锁被添加到Linux内核中，²特别是在休眠信号量的旋转逻辑中。在互斥锁的情况下，在SAP HANA的16套接字、240核HP convergence - system 900上，这为流行的Java工作负载提供了约248%的吞吐量提升。中的代码图5显示原语的接口。

其思想是，当线程需要获取争用锁时，它将传递自己的本地节点作为参数，以无等待的方式将自己添加到队列中，并在自己的缓存线上旋转(特别是在节点->锁定上)，直到轮到它获取锁。FIFO公平是自然而然的，因为当前的锁持有者在释放锁时将把锁传递给链表中的下一个CPU。该算法的一个缺点是，为了将自身添加到等待队列，任务必须将其本地节点的指针存储在其前身的->next字段中，如果前身任务需要释放锁，可能会产生额外的开销。

不幸的是，要在普通车票自旋锁中使用MCS锁，就必须加大锁的尺寸。自旋锁在整个内核中使用，并且不能大于32位字的大小。为此，还有其他排队锁定方法¹⁷为当前票务系统提供有效的替代方案。

回到顶部

结论

在设计锁定原语时考虑到性能，这不仅是一种良好的实践，而且还可以减轻未来的问题。本文基于使用大型服务器的经验，以及对使用Linux的实际客户端产生影响的实际问题。虽然Donald E. Knuth说过“过早优化是万恶之源”，但在实现锁定原语时情况恰恰相反。经验数据和实验已经表明，误用或忽视锁的底层硬件含义会带来代价。此外，用户和实施者都必须特别注意如何使用这些锁，以及在锁的生命周期中特定决策的结果，例如不同程度的争用。

在未来，随着计算机系统的发展和处理能力的提高，锁定原语的实践和理论将需要相应地适应，最终更好地利用硬件体系结构。即使在今天，也有非常专门的锁可用，例如队列和分层原语(如HCLH)，它们针对内存局部性进行优化，解决了基于回退的锁的公平性问题，同时保留了基于队列的锁的好处。

当然，锁定性能和可伸缩性的主题没有单一的解决方案，读者可以继续研究更多相关的主题，包括无锁数据结构和处理专门系统的特定约束，如实时环境的优先级反转和继承。在处理大型系统上严重的伸缩性问题时，这种性质的文章至少可以作为一种提高从业者意识的方法。

回到顶部

致谢

Linux内核中的扩展工作是一个团队的工作，包括在Hewlett-Packard Linux性能组内部和上游内核社区。非常感谢Scott J. Norton, Paul E. McKenney和Samy Al Bahra。

本文仅代表作者的观点，并不代表SUSE LLC的观点。Linux是Linus Torvalds的注册商标。其他公司、产品和服务名称可能是其他公司的商标或服务标志。

相关文章
在queue.acm.org

非阻塞算法与可扩展多核编程
萨米Al Bahra
http://queue.acm.org/detail.cfm?id=2492433

用建模解决架构复杂性
凯文Montagne:
http://queue.acm.org/detaiLcfm?id=1862187

结构化延迟:通过拖延实现同步
保罗·e·麦肯尼
http://queue.acm.org/detail.cfm?id=2488549

回到顶部

回到顶部

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2015 ACM, Inc.