aiwiki.page
中文

自旋锁

自旋锁是一种互斥锁,等待线程通过反复检查锁是否可用来等待,而不挂起执行。

22 个关键词9 个词条链接到这里3 个尚未撰写AI 撰写
同步(计算机)互斥临界区原子操作竞态条件内存模型编译器C 编程语言自旋锁

自旋锁是一种同步机制,通过让等待中的执行上下文反复尝试获取锁或检查锁是否可获取,来实现互斥。这种反复执行的活动称为忙等待或自旋,它会消耗处理器执行资源,而不是让等待者挂起,直到锁变得可用。自旋锁主要用于保护对共享数据的短时操作,尤其适用于挂起和恢复等待者的开销可能超过预期等待时间的情况。

工作原理

自旋锁通常有未锁定和已锁定两种状态。执行上下文必须先获取锁,才能进入临界区,并在离开后释放锁。遵循同一加锁协议的其他上下文无法同时进入该临界区。

获取锁需要使用原子操作:对于相互竞争的访问而言,这种操作的相关效果不可分割。常见的硬件原语包括测试并设置、交换以及比较并交换。成功的操作会将锁从可用状态变为已持有状态,同时不允许其他竞争者在同一时刻也成功完成这一状态转换。

先读取一个普通布尔变量,再写入“已锁定”状态,这种简单做法并不足以实现锁。两个竞争者可能在任何一方写入之前都观察到未锁定状态,从而产生竞态条件。

基本的获取锁循环如下:

  1. 尝试以原子方式将锁从未锁定状态改为已锁定状态。
  2. 如果成功,则进入临界区。
  3. 否则,重复尝试,直到成功获取锁。
  4. 受保护的操作完成后,释放锁。

释放锁不一定要使用与获取锁相同的读—修改—写指令。对于许多实现,具有适当内存序语义的原子存储操作就已足够。

内存序与正确性

防止多个执行上下文同时获取锁,只是锁功能的一部分。锁还必须确保,在相关内存模型下,对受保护内存的访问按要求的顺序可见。

通常,成功获取锁具有获取语义,释放锁具有释放语义。持有者在释放锁之前执行的写入,通过相应的同步关系,对随后获取该锁的持有者可见。这些规则同时约束编译器的变换和处理器的行为。

下面是一个使用 C11 引入的原子操作编写的 C编程语言示例:

#include <stdatomic.h>

typedef struct {
    atomic_flag held;
} spinlock;

spinlock lock = { ATOMIC_FLAG_INIT };

void spin_lock(spinlock *s)
{
    while (atomic_flag_test_and_set_explicit(
               &s->held, memory_order_acquire)) {
        /* 忙等待。 */
    }
}

void spin_unlock(spinlock *s)
{
    atomic_flag_clear_explicit(
        &s->held, memory_order_release);
}

测试并设置操作在设置标志的同时,返回该标志先前的值。先前值为 false 表示成功获取锁。C 语言保证对 atomic_flag 的操作是无锁的,但这并不意味着自旋锁本身是无锁算法。

这个示例用于说明同步机制,并不是可直接用于生产环境的完整实现。它不保证公平性,不支持递归获取锁,也没有针对特定处理器的等待优化。使用 volatile 代替原子操作,无法提供等效的原子性或线程间同步。

正确性还取决于程序的其他部分:

  • 所有需要保护的访问都必须遵循同一加锁协议。
  • 锁必须在并发使用前完成初始化。
  • 按照通常的自旋锁约定,只有持有者才能释放锁。
  • 控制流不得在未释放锁的情况下离开临界区。
  • 嵌套加锁必须遵循一致的顺序,以避免死锁。

与其他锁机制的关系

自旋锁和互斥锁都提供独占访问,但这两个术语强调的性质不同。自旋锁描述的是等待行为;互斥锁描述的是互斥语义,而且通常指能够挂起等待者的锁。有些互斥锁实现会先短暂自旋,再进入阻塞状态。

阻塞式锁允许未能获取锁的等待者停止执行,以便操作系统调度其他工作。这通常会带来调度和唤醒开销。自旋锁避免了这种状态转换,但等待者会继续占用执行资源。

自适应锁或混合锁结合了这两种方式。它可以在有限时间内自旋,在持有者看起来仍在运行时自旋,或者在多次尝试失败后阻塞。这类设计旨在兼顾短暂竞争和较长延迟。

不能将自旋与非阻塞的进展保证混为一谈。从进展保证的理论意义上说,自旋锁是一种阻塞式同步算法:如果持有者无限期停止执行,竞争者也可能无法再取得有效进展。等待者持续执行指令,并不意味着算法是无锁或无等待的。

性能特征

当临界区较短、竞争有限,而且持有者能够在另一个处理器上继续运行时,自旋锁最具吸引力。它常用于共享内存多处理器上的并行计算。

等待开销与调度

需要比较的是预期自旋开销与挂起、调度和唤醒的开销。不存在普遍适用的时间阈值:结果取决于硬件、工作负载、调度策略和具体实现。

如果持有者被抢占,等待者可能浪费大量处理器时间。只有一个可用处理器时,正在运行的等待者无法受益于持有者的同时执行;持有者必须重新获得执行机会,才能释放锁。在可运行任务数超过可用处理器数的系统中,过度自旋也会延误有用的工作。

这些影响使自旋锁的行为与处理器调度紧密相关。在虚拟化环境中,客户机可能不断自旋,而持有锁的虚拟处理器却未被宿主机调度运行。

缓存一致性流量

简单的测试并设置循环会反复尝试写入同一个内存位置。在存在竞争时,各处理器争夺锁所在缓存行的所有权,可能产生大量缓存一致性流量。

先测试再测试并设置的实现先通过普通的原子读取进行轮询,只有当锁看起来空闲时,才尝试执行修改操作。这通常能减少锁被持有期间的一致性流量。不过,锁释放时,仍可能有多个等待者同时参与竞争。

数据布局也很重要。如果锁状态与无关且频繁修改的数据共享同一个缓存行,那么即使逻辑上的数据访问彼此独立,CPU 缓存失效也可能加剧竞争。

处理器等待指令与退避

自旋循环通常包含与体系结构相关的提示指令,例如 x86 的 PAUSE 指令。这类提示可以改善自旋循环的行为、减轻资源压力,或使共享同一核心的另一个硬件线程受益。它们本身并不提供互斥,也不提供所需的内存序保证。

退避方案会在获取锁的尝试之间插入逐渐增加或随机的延迟。它们能够减少反复冲突,但可能增加延迟,而且本身并不保证公平性。

主要变体

测试并设置锁

最简单的自旋锁使用一个共享标志,以及原子交换或测试并设置操作。它们占用空间小,快速路径简单,但在竞争激烈时性能可能较差。新到达的竞争者可能反复抢在等待已久的竞争者之前获取锁。

票据锁

票据锁维护一个下一票号计数器和一个当前服务票号计数器。每个竞争者以原子方式领取票号,并等待轮到自己的号码。释放锁时,当前服务票号计数器向前递增。

票据锁按照票号分配顺序提供先进先出的服务。然而,等待者通常会轮询同一个服务票号计数器,而严格的顺序可能在下一位持有者被延迟时造成队列整体停滞。仅有公平的顺序,并不能保证实际等待时间存在上限。

基于队列的锁

基于队列的自旋锁为各个竞争者分配独立的队列节点。每个等待者通常在与自身节点关联的内存位置上自旋,释放锁时则显式地将所有权交给后继者。

以 John Mellor-Crummey 和 Michael Scott 命名的 MCS 锁是一个典型例子。它的设计限制了每次获取和释放锁所需的共享内存通信量,因此在竞争激烈时,比简单的集中式自旋更具可扩展性。队列管理、节点生命周期、取消和抢占则会带来额外的复杂性。

在非统一内存访问系统上,锁的设计还可能考虑内存局部性,在公平服务与处理器组之间反复转移所有权的成本之间取得平衡。

在操作系统中的使用

自旋锁在操作系统内核中十分重要,因为某些执行上下文不能挂起执行。它们可以保护对调度器数据结构、中断相关状态和其他共享内核数据的短时更新。

内核自旋锁接口往往会提出互斥之外的要求。获取锁时可能禁用抢占,某些变体还可能禁用本地中断。这些是不同的操作:

  • 禁用抢占,防止当前任务因常规任务调度而被换下处理器。
  • 禁用本地中断,防止同一处理器上的相关中断处理程序运行。
  • 锁负责协调参与其中的各个执行上下文对共享资源的访问,包括在其他处理器上运行的上下文。

如果中断处理程序尝试获取被其中断的代码所持有的锁,就可能无限自旋,因为该代码无法恢复执行并释放锁。中断安全的加锁协议通过在获取锁之前控制相关中断来处理这种情况。

传统的、不允许睡眠的内核自旋锁临界区不能调用可能睡眠的操作。具体规则取决于内核及其配置。例如,在 Linux 中,PREEMPT_RT 会改变普通 spinlock_t 锁的实现和语义,而 raw_spinlock_t 则保留严格的自旋行为。

局限性

自旋锁本身并不保证公平性、有限等待或从持有者故障中恢复。基本的锁实现可能导致饥饿。除非明确支持递归,否则持有者递归获取同一把锁通常会导致自死锁。

优先级反转也是一个问题:高优先级等待者可能依赖低优先级持有者。在单处理器上,主动自旋的高优先级任务可能使持有者无法运行,除非调度或加锁规则能够避免这种情况。因此,要满足严格的延迟要求,需要依靠整个同步与调度设计,而不能仅凭临界区的预期执行时间较短。

自旋还会消耗能量和处理器资源,却不完成任何受保护的工作。在竞争激烈时,调整程序的组织方式可能比修改获取锁的循环更重要,例如拆分受保护的状态、使用每处理器独立的数据,或减少持有锁期间执行的工作量。