Linux 内核 Queued Spin Lock 实现机制解析：从两CPU竞争到MCS队列的并发优化

上一篇文章介绍了Queued Spin Lock（队列自旋锁）的核心数据结构qspinlock。其设计精妙之处在于，通过一个union将一个32位整型变量划分为不同的位域，每个位域对应一个字段，分别服务于争抢锁的不同角色。该结构仅用4字节，既保持了与传统自旋锁API的兼容，又通过内置的MCS队列实现了公平的锁获取。

以下是qspinlock结构的字段划分。当只有两个CPU竞争自旋锁时，只会用到locked和pending字段，此时不会启用MCS等待队列。只有在竞争CPU超过两个时，才会使用MCS等待队列，tail字段将指向队列的尾节点。

在实现上，MCS节点采用静态分配方式，为每个CPU预先分配4个节点，分别对应四种可能的执行上下文（进程、软中断、硬中断、NMI）。结构体qspinlock中的tail字段并非直接指向节点指针，而是由两部分构成：tail cpu（队尾节点所属CPU编号加1）和tail index（队尾节点对应的CPU上下文编号）。

Queued Spin Lock将竞争锁的CPU划分为四个角色：

• Owner（持有者）：当前锁的持有者。加锁时负责将locked字段置1；解锁时负责将其清零。
• Pender（第一顺位等待者）：当前的第一等待者。它会将pending字段置1，并在locked字段上自旋等待。当Owner释放锁后，Pender会立刻检测到locked清零，随后将pending清零、locked置1，从而获取锁并晋升为Owner。
• Successor（后继者/队首等待者）：MCS等待队列中的第一个等待者，也是第二顺位等待者（只有第二及之后的竞争者才会入队）。它会在locked_pending（locked和pending的组合状态）字段上自旋。当Owner和Pender都退出后，Successor检测到locked_pending清零，便将locked置1以获取锁，并升级为Owner。
• Queuer（队列等待者）：MCS等待队列中除队首（Successor）外的其他等待者。它们各自在其MCS节点的locked字段上自旋等待。

接下来我们深入分析Linux内核中Queued Spin Lock的实现。加锁函数queued_spin_lock分为快速路径和慢速路径。快速路径适用于锁当前无人持有（lock->val=0）的情况，试图获取锁的CPU通过cmpxchg原子操作检查后，能立即将locked字段置1并成功获取锁。若快速路径失败（锁已被持有），CPU将进入queued_spin_lock_slowpath函数，这是Queued Spin Lock最核心、最复杂的部分。

解锁函数queued_spin_unlock非常简单，仅将locked字段清零。这引出一个疑问：按照经典MCS锁逻辑，解锁时应将锁所有权转移给下一个等待者（即置位其MCS节点的locked字段）。而这里的解锁函数并未这么做，那么所有权转移发生在哪里？答案就在前面的queued_spin_lock_slowpath函数中。

queued_spin_lock_slowpath函数集中体现了Queued Spin Lock的设计思想。该函数开头有一段以状态机形式解释其逻辑的注释，理解这段注释是掌握其实现的关键。

注释通过状态图描述了Queued Spin Lock的几种状态转换，状态由三元组 (queue tail, pending bit, lock value) 表示：

• queue tail：MCS等待队列尾节点的编号。0表示队列空；n表示尾节点编号；*表示任意值（该字段不影响当前状态）。
• pending bit：自旋锁的pending字段值。0表示无CPU等待或等待者已入队；1表示有CPU在等待且未入队（即存在Pender）。
• lock value：自旋锁的locked字段值。0表示锁空闲；1表示锁被持有。
  若pending bit和lock value的值为x/y，则表示这两个字段至少有一个为1。

状态机包含以下四种状态：

1. uncontended（无竞争状态）
   初始状态(0,0,0)，表示锁空闲且无等待者。一个CPU尝试获取锁，通过原子操作将值从0设为1，状态变为(0,0,1)（快速路径）。Owner释放锁后，状态变为(*,*,0)。

   (0,0,0) -> (0,0,1) -> (*,*,0)

2. pending（仅有Pender等待的状态）
   锁已被持有且MCS队列为空。此时另一个CPU尝试获取锁成为Pender，将pending置1，状态变为(0,1,1)。Owner释放锁后，Pender检测到locked清零，随后将pending清零、locked置1，状态变为(0,0,1)。

   (0,0,1) -> (0,1,1) -> (0,1,0) -> (0,0,1) -> (*,*,0)

3. uncontended queue（有Owner和Pender时，第三个竞争者加入）
   锁已被持有，且有Pender在等待。此时第三个CPU尝试获取锁，它将进入MCS队列，且成为队列中唯一的等待者（既是Successor也是队尾）。它将在locked_pending上自旋，直到Owner和Pender都释放锁。

   (0,1,1) -> (n,x,y) -> (n,0,0) -> (0,0,1) -> (*,*,0)

4. contended queue（存在Owner和Successor时，新竞争者加入）
   锁已被持有，且MCS队列中至少有一个等待者（queue tail非零）。此时新CPU尝试获取锁，只能入队成为Queuer，在其MCS节点的locked字段上自旋，等待前驱节点唤醒。当它被前驱节点唤醒（其MCS节点locked字段被置1），意味着它前面的Successor已升级为Owner，而它自己则升级为新的Successor，此后改为在locked_pending上自旋。

   (n,x,y) -> (*,x,y) -> (*,0,0) -> (*,0,1) -> (*,*,0)

这四种状态并非总会出现：

• 2个CPU竞争：仅出现uncontended和pending状态。
• 3个CPU竞争：出现uncontended、pending和uncontended queue状态。
• 超过3个CPU竞争：四种状态全部出现。

理解了状态机后，我们来看代码实现。queued_spin_lock_slowpath的第一部分主要处理只有两个CPU（Owner和Pender）竞争的情况。结合代码注释和下图中的说明，其逻辑清晰易懂。

第二部分代码的主要功能是：获取当前CPU的MCS节点，让qspinlock的tail字段指向该节点，并将其链接到MCS队列末尾（即让原队尾的next指向它）。如果原队列不为空，则当前CPU成为Queuer，在其MCS节点的locked字段上自旋。

如果判断出原队列为空，则当前CPU成为队首，即Successor。它将直接在locked_pending字段上自旋，这是第三部分代码的开始。第三部分主要处理两个逻辑：1）将队列中的Successor升级为Owner（获取锁）；2）将原Successor（刚升级的CPU）后面的那个CPU升级为新的Successor，使其解除在自身MCS节点locked字段上的自旋等待。这正是对前面疑问的回答：锁所有权的转移和队列唤醒逻辑并不在解锁函数中，而是在queued_spin_lock_slowpath函数内完成。

通过以上分析，可以看出Linux内核在设计与实现Queued Spin Lock时，在并发编程的复杂场景下做出了极致的权衡与优化，主要体现为：

1. 保证公平性：采用FIFO思想的MCS队列，确保锁获取的公平性。
2. 渐进式竞争处理：根据竞争者数量动态调整策略，从无竞争 → pending优化 → MCS队列，平滑过渡。
3. 最小化开销：在两个CPU竞争时避免不必要的队列操作，降低开销。
4. 避免性能瓶颈：超过两个CPU竞争时启用MCS队列，有效避免了传统自旋锁因缓存行颠簸（Cacheline Bouncing）导致的性能骤降问题，实现了高效的系统级性能优化。