【万字长文解读锁1】【论文阅读 | TOCS】Lock–Unlock: Is That All? A Pragmatic Analysis of Locking in Software Systems

导读

一篇很全面的关于同步锁的综述，比较了多种类型的锁在不同的负载情况下的情况，对于了解前人针对锁设计上做出的重要贡献很有帮助。

文章以笔记和翻译为主。

当然，更建议直接阅读原文。

摘要

在过去的25年中，为了缓解与临界区和锁相关的性能瓶颈，研究者们设计了大量的优化互斥锁算法。然而，目前尚缺乏对这些优化锁算法在实际应用中的行为进行全面研究，尤其是考虑到不同性能指标（如能效和尾延迟）的情况。本文旨在对同步机制进行深入且实用的分析，旨在为软件开发人员提供足够的信息，以设计出快速、可扩展且高效的同步机制。首先，我们在四种不同的多核机器上，对28种先进的互斥锁算法在40个应用中的性能进行了研究。我们不仅考虑了传统的性能指标——吞吐量，还关注了日益重要的能效和尾延迟。其次，我们通过深入分析总结了所有研究应用中的发现，具体描述了九种与锁相关的性能瓶颈，并提出了六条指导原则，帮助开发人员根据锁的特性和应用需求选择合适的锁算法。

First, we perform a performance study of 28 state-of-the-art mutex lock algorithms, on 40 applications, on four different multicore machines. We consider not only throughput (traditionally the main performance metric) but also energy efficiency and tail latency, which are becoming increasingly important. Second, we present an in-depth analysis in which we summarize our findings for all the studied applications. In particular, we describe nine different lock-related performance bottlenecks, and we propose six guidelines helping software developers with their choice of a lock algorithm according to the different lock properties and the application characteristics.

通过我们的详细分析，我们得出了关于锁算法和应用行为的若干观察结果，其中一些是此前未被发现的：

(i) 应用程序不仅对锁的加锁-解锁接口施加压力（请求），还会对完整的锁API（例如trylocks、条件变量）施加压力；

(ii) 锁的内存占用会直接影响应用程序的性能；

(iii) 对于许多应用程序而言，锁与调度之间的交互是影响应用性能的重要因素【例如，优先级高的应用线程可能会优先拿到锁资源】；

(iv) 锁的尾延迟可能影响也可能不影响应用程序的尾延迟【这取决于锁是否在程序运行的关键路径上】；

(v) 没有一种锁在所有情况下都是最优的；【no single lock is systematically the best;】

(vi) 选择最佳锁算法是困难的；【不同的业务可能会有不同的选择，需要根据负载的特征来选择】

(vii) 在锁算法的背景下，能效和吞吐量是相辅相成的。

这些发现表明，锁机制的设计不仅仅涉及简单的加锁/解锁接口，还需要进一步研究如何设计低内存占用的自适应锁，这些锁应全面且高效地支持完整的锁接口，并考虑所有性能指标。

Introduction

如今，多核机器已经无处不在，但充分利用它们的能力并非易事。许多多线程应用程序都面临着与临界区及其对应的锁相关的性能瓶颈问题 [5, 8, 9, 15, 25, 27, 32, 42, 52, 56, 60, 63, 67–70, 76, 83, 91]【感兴趣可以具体去看一看，这里面有很多多线程应用程序并发性能的经典文章】。在过去的25年中，研究者们设计了大量的优化互斥锁（mutex）算法以缓解这些问题 [8, 20, 21, 24, 27, 29–32, 36, 37, 39, 46, 47, 55, 59, 65, 66, 70, 74, 77, 79, 81, 98]。应用程序和库开发人员可以从这些算法中选择合适的方案来实现高效的同步机制。然而，目前尚缺乏一项完整的研究来指导开发人员在现实应用中选择合适的锁算法。  

特别是，尽管最近关于多核同步的最全面实证性能评估 [27] 涵盖了从硬件协议到高级数据结构的广泛内容，但它仅部分覆盖了锁算法。该研究仅考虑了九种算法，未涉及混合自旋/阻塞等待策略，忽略了新兴方法（例如第2.1节中描述的负载控制机制），并且对层次化锁 [20, 21, 32]（一种针对NUMA架构的高效方法）的覆盖也较为有限。通常，现有文献中的大多数观察结果都基于微基准测试，并且仅关注加锁/解锁接口，而忽略了其他与锁相关的操作，例如条件变量和trylocks。此外，在提出新锁算法的论文中，实证观察通常集中在锁设计所针对的特定工作负载特性上 [52, 63]，或者主要基于微基准测试 [30, 32]。最后，现有分析主要关注传统性能指标（如吞吐量），而未涵盖其他日益重要的指标，例如能效和尾延迟。  

在本文中，我们对同步机制进行了全面且实用的分析，旨在为软件开发人员提供足够的信息，以设计出快速、可扩展且高效的同步机制。

本文的第一个贡献是对28种先进的互斥锁算法在40个现实且多样化的应用上进行了广泛的性能研究（第5至第7节），这些应用运行在Linux/x86平台（即运行在AMD/Intel x86 64位处理器上的Linux操作系统）上。这些应用包括PARSEC、Phoenix、SPLASH2基准测试套件，以及MySQL、Kyoto Cabinet、Memcached、RocksDB、SQLite、upscaledb和一个SSL代理【看起来在 paper 中 Redis 会被抛弃掉：）】。在这40个应用中，我们发现大约60%的应用性能会因锁的选择而有所不同，并针对这些应用进行了深入分析。我们相信这些应用具有代表性，能够反映现实世界中的实际需求：我们不仅考虑了在不同程度上对经典加锁/解锁接口施加压力的应用，还涵盖了条件变量、trylocks、屏障等不同使用模式的应用，以及使用不同数量锁的应用（从单个全局锁到数千个锁）。  

我们在四种不同的多核机器上进行了实验，并考虑了三种不同的性能指标：吞吐量、尾延迟和能效。在探索锁行为的过程中，我们发现，通过为每种配置选择最佳锁，应用程序的平均吞吐量提升了90%，能效提升了110%，尾延迟降低了12倍（相对于默认的POSIX互斥锁）。【足以看出来，针对性的选择锁策略对应用是有正反馈的，例如对于延迟敏感型应用，选择自旋锁要比阻塞锁性能要好一些】需要注意的是，在许多情况下，不同的锁会优化不同的性能指标。正如本文所示，选择性能优异的锁是困难的，因为这一选择依赖于许多不同的参数：工作负载、底层硬件、并行度、锁的数量及其使用方式、应用程序所施加压力的锁相关接口（例如加锁/解锁、trylock、条件变量）、应用程序与调度器之间的交互，以及所关注的性能指标。【参数过多，要求工程师需要有足够的领域知识来判断，这就对工程师提出了很高的需求。】

本文的第二个贡献旨在简化软件开发人员的工作：我们对研究应用中出现的不同类型的锁相关性能瓶颈进行了深入分析。具体而言，我们描述了九种不同的锁相关性能瓶颈。基于这些分析的洞察，我们提出了六条指导原则，帮助开发人员根据锁的特性和应用需求选择合适的锁算法。更具体地说，通过回答关于应用程序的几个问题（例如，线程数是否多于核心数？是否存在阻塞系统调用？）以及查看一些与锁相关的指标（例如，分配的锁数量、同时尝试获取锁的线程数量），开发人员能够快速且轻松地理解在特定用例中应选择或避免哪些锁算法。  

我们的第三个贡献是LiTL，这是一个开源的、符合POSIX标准 [48] 的低开销库，支持透明地替换Pthread互斥锁操作，并提供对条件变量等主流功能的支持。事实上，为了开展本研究，手动修改所有应用程序以适配所研究的锁算法将是一项艰巨的任务。此外，使用允许在通用API下插入不同锁算法的元库（例如liblock [63] 或libslock [27]）也无法完全解决问题，因为这仍然需要对每个应用程序进行大量的重新工程化工作。此外，这些元库对许多应用程序中使用的Pthread条件变量等重要功能的支持有限或根本不支持。我们的方法是一种实用主义的方法：类似于之前关于内存分配器的工作 [3, 12, 41, 58]，我们认为透明地切换锁算法（或内存分配器）是一种高效且实用的解决方案。  

通过我们的全面研究和深入分析，我们得出了关于锁算法和应用行为的若干观察结果，其中一些是此前未被发现的（据我们所知）。

应用程序不仅会对锁的加锁/解锁接口（lock/unlock interface）施加压力，还会测试完整的锁操作接口（例如，trylock 和条件变量）。大多数现有研究主要集中在锁的加锁/解锁接口的性能上。然而，我们观察到，许多性能瓶颈与其他较少被关注的锁操作相关。例如，应用程序使用 trylock 实现忙等待（busy waiting），因为传统的 Pthread 互斥锁实现会在线程等待锁时强制其进入非调度状态。然而，许多针对加锁/解锁接口优化的锁算法在 trylock 操作上表现较差。此外，应用程序广泛使用条件变量，而条件变量与锁实例直接交互的特性在锁算法设计中大多被忽视。从实用的角度来看，锁的设计应当不仅优化加锁/解锁接口，还需同时优化 Pthread 互斥锁 API 提供的所有其他锁操作接口。

锁的内存占用（memory footprint）可能直接影响应用程序的性能。许多锁算法通过使用更复杂的数据结构来提高性能。例如，一些算法使用每线程上下文（per-thread context）来存储线程的锁获取状态，而另一些算法则将统计信息存储在锁实例中，并在运行时利用这些统计信息调整锁获取策略。然而，这些复杂性的引入是有代价的，因为它增加了每个锁实例的内存占用。事实上，我们观察到，一些应用程序会分配数千个锁实例，有时还会同时分配。这种行为不仅给内存分配器带来压力，还会降低处理器缓存的局部性（cache locality），从而对应用程序性能产生不利影响。因此，锁算法设计者需要牢记，算法的内存占用是一个重要因素，应尽量设计低内存占用的算法。

对于许多应用程序而言，锁与调度之间的交互是影响性能的重要因素。已有研究[14]表明，一些锁算法在超线程【或者用超载可能合适】（overthreading，即线程数量超过可用核心数量）环境中表现出较差的性能。更为重要的是，我们进一步观察到，锁与调度器之间的交互会显著影响许多应用程序的性能。实际上，由于应用程序不仅使用锁的加锁/解锁接口（如条件变量），还使用其他阻塞函数（如同步屏障和 I/O 系统调用），Linux 调度器可能会做出导致某些锁算法下应用程序性能下降的调度决策。特别是，文献中广泛讨论的锁持有者被抢占（lock holder preemption）问题[14]和锁等待者被抢占（lock waiter preemption）问题[85]在实际中频繁出现。基于这一观察，我们可以得出一个直接结论：锁算法设计者应认识到调度器的决策可能阻碍应用程序性能，因此应设计能够适应次优调度情况的锁算法【因此，基于这种想法，在固定的场景下，可能会产生多种优秀的算法策略】。

锁的尾延迟（tail latency）可能会或可能不会影响应用程序的尾延迟。一些锁算法专为线程获取的绝对公平性而设计，而另一些算法则通过牺牲公平性换取更高的锁获取吞吐量。这些属性会直接影响锁的尾延迟。然而，我们发现锁的尾延迟对应用程序尾延迟的影响并非显而易见。更具体地说，如果一个高级应用程序操作主要通过单一临界区实现，那么该操作的性能（吞吐量和尾延迟）将高度依赖于锁的特性。因此，如果需要较低的尾延迟，可以选择专为公平性设计的锁算法。相反，如果开发者愿意在应用程序尾延迟上进行权衡以换取更高的吞吐量，那么以牺牲公平性换取吞吐量的锁算法是一个不错的选择。

然而，对于并发性有限的应用程序（即一个操作或请求由多个临界区和/或顺序部分组成），锁的尾延迟对应用程序尾延迟的影响并不显著。在这种情况下，我们观察到，较低的应用程序尾延迟通常意味着更高的应用程序吞吐量。因此，开发者应选择能够最大化吞吐量的锁算法，以优化应用程序性能。

我们在更大规模的应用程序、机器和锁算法上验证了先前研究[27, 36, 43]的发现：没有一种锁能够在所有场景中始终表现最佳。我们观察到，在我们考虑的三个评估指标中，大约 60% 的被研究应用程序显著受锁性能影响，我们称之为锁敏感应用（lock-sensitive applications）。对于锁敏感应用，在经过单独优化争用程度后，性能最佳的锁在任何场景下的占比均未超过 53%。这一现象的直接意义在于，仅向开发者提供一种锁算法（如 Pthread 锁）会导致大多数应用程序的性能无法达到最优。【针对性的优化是十分重要的，即使是简单策略的替换，对于延迟敏感与否的应用程序都会带来很大影响。】

选择最佳锁算法是一项复杂任务。对于特定应用程序，最佳锁的选择会随争用核心数、硬件配置和工作负载的变化而变化。更糟糕的是，选择错误的锁算法可能对应用程序造成显著影响，因为在某些工作负载下，所有锁算法的性能都可能远逊于最佳选择。因此，开发者不应将锁算法的选择硬编码到应用程序中。【事实上，在开发中确实如此，我们需要通过调优阶段来调整，但很难保证生产环境中和理想（或者称为假设）是100%相同的】

在锁算法的设计中，能效（energy efficiency）与吞吐量（throughput）密切相关。已有研究[36]提出了 POLY 2 假设（POLY conjecture），该假设指出：“在锁算法的背景下，能效和吞吐量是相辅相成的。”更具体地说，POLY 假设认为：“锁算法可以通过优化来提高能效而不降低吞吐量”，并且“[来自]以吞吐量为导向的锁算法研究的洞见几乎可以直接应用于能效锁的设计中。”我们在大量锁算法和应用程序中验证了 POLY 假设（相比之下，最初的 POLY 研究仅考察了三种锁算法和六个应用程序）。

以上观察的高层次启示是，研究社区应将重点放在设计低内存占用、适应性强且能够高效支持完整锁操作接口的锁算法上，同时综合考虑所有性能指标。

文章余下内容的组织结构如下：第 2 节介绍现有锁设计的分类和本研究涉及的算法清单；第 3 节描述我们的实验设置以及所研究的应用程序；第 4 节介绍 LiTL 库；第 5 至第 7 节分别展示主要的吞吐量、能效和尾延迟实验结果；第 8 节对锁相关性能瓶颈进行了详细分析，并提出了关于锁算法选择的指导建议；第 9 节讨论了相关工作；第 10 节对本文进行了总结。

2 锁算法 LOCK ALGORITHMS

【这一章节偏向于基础知识，因此可以选择性阅读】

在本节中，我们介绍了本研究中所涉及的 28 种多核锁算法，并根据它们的设计属性将其划分为五类。随后，我们讨论了锁算法设计中的一个重要维度，即等待策略（waiting policy）的选择——线程在无法立即获得所请求的锁时的行为。最后，我们列出了本实证研究所选用的锁算法清单。

2.1 背景

所有现代锁算法都依赖于硬件的原子指令来确保临界区在互斥的条件下被执行。为了提供原子性，处理器利用机器的缓存一致性协议（cache-coherence protocol）在内存地址上实现原子的读-修改-写操作。已有研究[27]表明，锁算法的性能主要取决于硬件特性。例如，锁算法必须考虑底层硬件的特性。因此，锁算法的设计需要在数据结构、锁的获取/释放策略以及（可能的）负载控制机制之间进行精心权衡。

• 第 2.1.1 节介绍了锁操作接口（locking API）。
• 第 2.1.2 节将锁算法分类为五大类别。
• 第 2.1.3 节讨论了各种等待策略。

2.1.1 同步原语

加锁是目前最常用的同步方法。几乎所有现代软件系统在设计和实现中都采用了锁机制。加锁流行的主要原因在于它提供了一种直观的抽象模型：锁保证了互斥访问，即只有持有锁的线程能够继续执行。受锁保护的执行区域称为临界区（critical section）。互斥是一种用于同步并发访问的方法，例如，线程通过协调，避免在一个线程退出临界区之前，另一个线程进入该区域。此外，条件变量（condition variable）通过在线程之间建立先发生关系（happened-before relationship），使线程可以在临界区内协作。

互斥机制

加锁/解锁（Lock/Unlock）

在进入临界区时，线程必须通过加锁操作（lock operation）获取锁。加锁操作是阻塞式的（blocking），即当线程尝试获取一个已经被占用的锁实例时，必须等待该锁实例变为可用。当持有锁的线程退出临界区时，必须调用解锁操作（unlock operation）显式释放锁。如何获取锁、在等待锁时的行为，以及如何释放锁，都是锁算法设计需要权衡的关键点。

尝试加锁（Trylock）

当锁被占用时，线程可以选择不阻塞，而是执行其他任务。在这种情况下，可以使用非阻塞式的尝试加锁操作（trylock operation）。该操作会返回一个状态码，指示锁是否被成功获取。当 trylock 操作未成功获取锁时，线程的后续行为由软件开发者决定，而非锁算法。我们观察到，开发者经常使用 trylock 实现忙等待（busy waiting），以避免线程被调度器暂停（这是 Pthread 锁算法在等待锁时采用的策略）。这种策略在开发者知道受锁保护的临界区较短，并且线程很可能快速获取锁的情况下非常有用。【延迟敏感类应用在小临界区的操作使用自旋锁就是一个典型的例子】一旦 trylock 成功获取锁，持有锁的线程必须调用 unlock 来释放锁。

条件变量（Condition Variables）

线程通常依赖条件变量在事件发生时接收通知（例如，当数据被放入队列中）。希望等待条件变量的线程在持有锁的状态下调用 wait 操作。调用后，线程会释放锁并进入阻塞状态。当条件满足时，另一个线程会调用 signal 或 broadcast，分别唤醒一个或所有被阻塞的线程。在被唤醒时（并在退出 wait 之前），线程会竞争锁以重新进入临界区。在锁之上高效实现条件变量并非易事（详见第 4.1 节）。

2.1.2 锁算法的分类

针对多核体系结构的优化锁算法研究领域非常丰富多样，可以分为以下五类。前两类（竞争性继承和直接传递继承）基于锁算法的继承策略（succession policy）[30]，即锁在解锁时如何转移所有权。这两类是互斥的。后三类则包含从前两类派生的算法（分层方法）、改变临界区执行方式的算法（基于委托的方法），以及通过负载控制机制改进现有锁的算法。需要注意的是，这些类别之间存在重叠：某些算法可能属于多个类别。

(1) 竞争性继承 Competitive succession

一些算法依赖于竞争性继承策略，即锁的持有者将锁设置为可用状态，然后所有竞争线程可能同时尝试获取锁，并对同一内存地址执行原子操作。这类算法通常会对缓存一致性协议（cache-coherence protocol）造成较大压力，因为它们会在解锁时触发对所有等待锁的核心的缓存行失效（cache-line invalidations），但最终只有一个核心成功获取锁。

竞争性继承算法可能允许插队（barging）——例如，“新到达的线程可以插队到其他等待线程之前”[30]，从而导致不公平性（unfairness）和饥饿问题（starvation）。采用竞争性继承策略的算法包括：

• 简单自旋锁（simple spinlock）[83]
• 回退自旋锁（Backoff spinlock）[8, 70]
• 测试和测试并设置锁（test and test-and-set，TTAS lock）[8]
• Mutexee 锁 [36]
• 标准 Pthread 互斥锁 [48, 59]

(2) 直接传递继承 Direct handoff succession

直接传递锁（direct handoff locks，也称为队列锁 queue-based locks）是一种在解锁操作中明确识别下一个等待线程，并将锁的所有权传递给该线程的算法[30]。由于当前锁的持有者可以明确知道其后继线程，因此每个等待线程只需在一个非全局共享的内存地址上（即每个线程有一个私有内存地址）等待。而锁的持有者利用这个私有内存地址将所有权传递给后继线程，从而避免了类似竞争性继承策略中对其他竞争核心的缓存行失效。

这种方法以更高的公平性著称，并且在高竞争情况下相比于简单的锁（如自旋锁）通常具有更高的吞吐量。直接传递锁让每个线程只在自己的局部变量上自旋，因此避免了基于全局变量的锁在获取/释放时向所有其他自旋线程发送缓存行失效的情况。采用直接传递继承策略的锁算法包括：

• MCS 锁 [70, 83]
• CLH 锁 [24, 66, 83]

某些算法虽然使用全局共享内存地址，但仍采用直接传递继承策略。例如：

• Ticket 锁 [79]：通过非原子方式反复读取一个内存地址，等待自己的轮次。
• 分区 Ticket 锁 [29]：使用一种混合方案，其中同一内存地址可以被一部分竞争线程观察到。

(3) 分层方法（Hierarchical Approaches）

分层方法旨在为 NUMA（非均匀存储访问）架构提供可扩展的性能，核心目标是降低锁迁移的频率（即缓存行的跨 NUMA 节点传输），因为这种迁移在 NUMA 节点间代价极高。属于该类别的算法包括：

• HBO [77]
• HCLH [65]
• FC-MCS [31]
• HMCS [20]
• 来自锁分群框架（lock cohorting framework）的相关算法 [32]

分群锁（cohort lock）基于两种锁算法（可以是相同或不同的）的组合：一种用于全局锁，另一种用于本地锁（每个 NUMA 节点有一个本地锁）。在常见的 C-LA-LB 表示法中，LA 和 LB 分别代表全局锁算法和节点级锁算法。典型实例包括：

• C-BO-MCS
• C-PTL-TKT
• C-TKT-TKT（也称为 HTicket [27]）

其中，BO、PTL 和 TKT 分别对应于回退锁（Backoff lock）、分区 Ticket 锁（Partitioned Ticket lock）以及标准 Ticket 锁（Ticket lock）。

(4) 基于委托的方法（Delegation-Based Approaches）

基于委托的锁算法（delegation-based lock algorithms）允许线程将执行临界区的任务（有时或始终）委托给另一个线程。这种方法的主要预期收益包括：

• 提升缓存局部性（cache locality）
• 在高锁争用环境下表现出更强的适应能力

属于这一类别的算法包括：

• Oyama [74]
• Flat Combining [47]
• RCL [63]
• FFWD [81]
• CC-Synch [37]
• DSM-Synch [37]

(5) 负载控制机制（Load-Control Mechanisms）

负载控制机制包含那些实现了适应机制的锁算法，这些机制能够检测需要调整锁行为的情况，例如：

• 应对不断变化的争用水平（即同时尝试获取锁的线程数量）
• 避免与锁相关的病态行为（例如，为了执行等待锁的线程而导致锁持有者被抢占）

这一类别的算法包括：

• MCS-TimePub4 [46]
• GLS [9]
• SANL [98]
• LC [52]
• AHMCS 5 [21]
• 所谓的马尔萨斯算法（Malthusian algorithms），如 Malth_Spin 和 Malth_STP6 [30]

2.1.3 等待策略

锁算法设计中的一个重要维度是在线程无法立即获取所请求的锁时所采用的等待策略 [30]。主要存在以下三种方法：

1. 自旋 (Spinning)

自旋是一种最为直接的等待方式，线程会不断检查锁的状态，直到锁变为可用。然而，这种策略可能导致能量浪费，同时线程在核心上花费的等待时间可能阻碍其他被调度出队的线程的进程。

处理器优化支持： 处理器提供了特定的指令，用于在线程处于自旋状态时通知CPU微架构。例如，x86处理器提供了PAUSE指令 [30]，该指令专门设计用于减少分支预测错误，并通知核心释放共享流水线资源以供同线程的超线程使用。

降低自旋开销的优化策略：

• 退避机制 (Backoff)：通过固定或随机退避（即线程在尝试获取锁失败后避免在一段时间内重新尝试），可以减少并发原子操作的数量，从而降低缓存一致性流量的压力。
• 硬件支持：硬件可以通过动态电压和频率缩放（DVFS [92]）降低等待线程核心的频率，或通过特权指令MONITOR/MWAIT [36]通知核心进入空闲状态以节省能量（需运行于特权模式下，或通过内核模块 [7] 提供支持）。
• 自愿放弃核心：线程还可以通过调用sched_yield或sleep以一种较为温和的方式主动放弃核心的使用权。

sched_yield 机制详解

1. sched_yield 概述

sched_yield 是 POSIX 线程库（pthreads）提供的一个系统调用（或库函数），用于显式让出当前线程的 CPU 时间片【例如，得不到资源时，放弃核心，让给其他任务，提高资源利用率】，使操作系统调度器可以选择运行其他可执行线程。它的主要目的是在自旋等待或低优先级任务中，提高系统的整体调度效率，减少 CPU 资源浪费。

2. sched_yield 的作用

当一个线程调用 sched_yield 时，调度器会立即将该线程放入可运行队列 (run queue)，并尝试运行同一优先级或更高优先级的其他线程。如果没有更高优先级或相同优先级的可运行线程，则操作系统可能会让当前线程继续运行。

其核心作用包括：

• 主动放弃 CPU 控制权，让调度器选择其他线程运行；
• 降低锁争用，特别是自旋锁等待时，减少对 CPU 的无效占用；
• 提高系统吞吐量，在 I/O 线程或低优先级任务中避免不必要的 CPU 轮转；
• 优化高优先级任务的响应时间，确保关键任务可以更快被调度执行。

3. sched_yield 的实现机制

man 2 sched_yield 的官方描述如下：

#include <sched.h>

int sched_yield(void);

• 返回值：始终返回 0（成功执行）。
• 无参数，调用后不会进入睡眠状态，而是将 CPU 控制权交还给调度器。

工作流程

1. 当前线程调用 sched_yield。
2. 操作系统调度器检查当前线程的优先级和就绪队列中的其他线程：
   • 如果有相同或更高优先级的线程处于就绪状态，调度器会切换到该线程执行；
   • 如果没有可运行的同级或高优先级线程，那么当前线程可能会立即重新运行（相当于无效调用）【这个需要注意，在某些场景下，该问题可能也会隐式触发性能问题，然而可能不会被在意】。
3. 线程状态不会变为阻塞（BLOCKED），而是仍然处于就绪（RUNNABLE）状态。

4. sched_yield 的适用场景

尽管 sched_yield 提供了一种主动让出 CPU 的方法，但它的应用场景较为特殊，主要适用于以下情况：

（1）自旋锁等待优化

在高并发程序中，如果线程尝试获取某个锁但暂时无法获取（例如另一个线程持有该锁），可以选择：

• 纯自旋 (Busy-waiting)：线程持续轮询锁的状态，但这会消耗大量 CPU 资源。
• 带让步的自旋 (Polite spinning with sched_yield)：线程在某些迭代中调用 sched_yield，让出 CPU 以减少能量消耗，提高系统吞吐量。

示例：

while (atomic_flag_test_and_set(&lock)) {  // 尝试获取锁
    sched_yield();  // 让出 CPU，避免忙等
}

这种方式适用于低锁竞争的情况，因为如果锁长期不可用，线程仍然会不断被重新调度，可能导致不必要的 CPU 消耗。

（2）忙等待（Busy-wait）任务

当一个线程需要等待某个事件发生（例如数据准备就绪、I/O 操作完成），但无法使用阻塞方法（如 pthread_cond_wait），可以使用 sched_yield 降低 CPU 资源浪费：

while (!data_ready) {
    sched_yield();  // 让出 CPU，等待数据准备完成
}

这在实时系统或高吞吐任务中较为常见。

（3）提高系统吞吐量

在某些 CPU 负载较高的场景，低优先级任务可以使用 sched_yield 让高优先级任务更快被调度：

for (int i = 0; i < WORKLOAD; i++) {
    do_some_work();
    if (i % 100 == 0) {
        sched_yield();  // 让出 CPU 以提高系统公平性
    }
}

（4）多线程公平调度

某些应用（如调度器本身）可能希望确保所有线程能公平执行，而不是某些线程一直占用 CPU。通过定期调用 sched_yield，可以减少某个线程长期占用 CPU 资源的问题。

5. sched_yield 的局限性

尽管 sched_yield 提供了一种调度优化的方法，但它并不是适用于所有情况：

• 无法保证让出 CPU 后就会调度其他线程：
  • 如果当前线程是最高优先级，并且没有其他可运行线程，sched_yield 可能只是一个空操作（no-op），线程仍然会被调度执行。
• 可能导致性能下降：
  • 在高锁竞争情况下，过度使用 sched_yield 可能会使线程不断被重新调度，而不是进入睡眠状态，反而导致 CPU 资源浪费。
• 依赖操作系统的调度策略：
  • 在 Linux 内核中，基于 CFS（Completely Fair Scheduler）的调度器可能不会优先考虑 sched_yield 让出的 CPU 资源，而是按优先级和时间片分配 CPU。
  • 在实时调度策略（如 SCHED_FIFO）中，sched_yield 可能会影响线程优先级队列的重新排序。

6. sched_yield vs. 其他让出 CPU 方法

• 如果线程只是短时间等待，sched_yield 可能是一个合适的选择；
• 如果线程需要较长时间等待（如等待 I/O 事件或互斥锁），pthread_cond_wait 或 futex 更合适；
• 如果线程需要明确的时间间隔，可以使用 sleep(n) 或 nanosleep()。

7. 结论

sched_yield 是一个轻量级的 CPU 让出机制，适用于低锁争用、忙等待优化以及提高系统吞吐量等场景。然而，它的行为依赖于操作系统的调度策略，并不能保证一定会调度其他线程。因此，在实际应用中，应根据具体情况选择合适的等待机制，以优化性能和能效。

2. 立即挂起 (Immediate Parking)

在立即挂起策略下，线程如果无法获取已被占用的锁，会立即阻塞，直到有机会获取锁 [8]。

• 实现机制：这种策略需要内核支持（例如Linux上的futex系统调用），以通知调度器线程正在等待锁，从而避免在锁释放前将线程重新调度。
• 解锁时的操作：当锁持有者释放锁时，需负责通知调度器锁已经可用。

3. 混合策略 (Hybrid Approaches)

混合策略的动机在于，不同等待策略具有不同的开销。例如，自旋后挂起策略 (Spin-then-Park) 是一种混合方法，采用固定或自适应的自旋阈值 [54]【自适应的方式需要考虑较多因素，或者根据负载来设置某一个或一些规则】，旨在降低挂起的代价，因为阻塞和解除阻塞操作在能量和性能上都非常昂贵。

实现细节：

• 自旋阈值的设定：通常设为往返上下文切换时间。
• 多种自旋策略的组合：例如将退避机制与sched_yield结合使用 [27]。
• 复杂组合优化：某些算法 [36, 90] 通过自适应解锁 (Adaptive Unlock) 提高吞吐量（代价是牺牲公平性），避免在解锁时唤醒阻塞线程，如果当前有其他线程正在自旋【正如前面所述，这种情况下可能导致阻塞的线程一直得到锁资源，从而一直推迟执行】。

等待策略的选择与影响

等待策略在设计上与锁结构大体正交，但实际上，纯自旋策略通常仅适用于某些特定类型的锁，例如直接传递型锁（第2、3和5类锁）、Mutexee以及标准的Pthread互斥锁。然而，等待策略直接影响锁的能量效率与性能：

• 自旋的能量消耗：Falsafi等人 [36] 的研究发现，纯自旋本质上会导致高功耗，且几乎没有实际方法可以降低纯自旋的功耗。
• 阻塞的能量效率：阻塞确实可以节省能量，因为线程阻塞后，内核可以将核心置于低功耗空闲状态 [6, 50]。
• 阻塞的开销：但阻塞与解除阻塞操作的高昂开销可能会降低效率。若频繁在阻塞与解除阻塞之间切换，其能量效率甚至可能比纯自旋更差。

因此，在自旋与挂起之间存在能量效率的权衡（Tradeoff）。本文后续使用“挂起策略 (Parking Policy)”一词统一指代立即挂起与自旋后挂起等待策略。

2.2 研究的锁算法

本节描述了 28 种互斥锁（mutex lock）算法，这些算法既涵盖了成熟的传统方法，也包含了最新的前沿技术。我们的锁算法选择标准是关注可移植性，因此，我们排除了以下几类锁：

1. 依赖特定应用或操作系统行为、需要修改代码或对性能调优较为敏感的锁，如 HCLH、HBO 和 FC-MCS。Dice 等人 [32] 提出了详细的排除理由。
2. 基于委托（delegation-based）的锁，因为此类算法要求关键区（critical section）以闭包（closure，即函数）的形式表达 [32]，这与我们的透明方法（即无需修改源代码）不兼容。
3. 依赖运行时支持的锁，如 LC 和 GLS，这些算法需要特定的内核支持和/或监控线程。

在命名方案上，我们使用 _Spin 和 _STP 后缀来区分仅在等待策略（纯自旋 vs. 自旋后阻塞）上有所不同的算法变体。除非锁算法的具体实现另有规定，我们在自旋循环的迭代之间默认使用 PAUSE 指令进行暂停。此外，-ls 标记表示该算法源自 libslock 库 [27]。

值得注意的是，Linux 的 GNU C 库提供了两种 Pthread 互斥锁实现 [40]：

• 默认版本 采用**立即阻塞（immediate parking）**策略（通过 futex 系统调用实现）。
• 自适应自旋-后阻塞（adaptive spin-then-park） 版本可通过 PTHREAD_MUTEX_ADAPTIVE_NP 选项启用 [59]。

本研究中所涵盖的锁算法如 表 1 所示，包括：

• 8 种竞争式继承（competitive succession）锁：Backoff、Mutexee、Pthread、PthreadAdapt、Spinlock、Spinlock-ls、TTAS、TTAS-ls。
• 10 种直接交接（direct handoff）锁：ALock-ls、CLH-ls、CLH_Spin、CLH_STP、MCS-ls、MCS_Spin、MCS_STP、Ticket、Ticket-ls、Partitioned。
• 6 种分层（hierarchical）锁：C-BO-MCS_Spin、C-BO-MCS_STP、C-PTL-TKT、C-TKT-TKT、HTicket-ls、HMCS。
• 4 种负载控制（load-control）锁：AHMCS、Malth_Spin、Malth_STP、MCS-TimePub。

本研究将对上述锁算法进行系统性分析，以评估其在多核环境下的性能表现。

具体的讲解请看下一篇内容。 另：如同本文一开始所说，建议直接阅读原文，纵享原始表达方式。