【操作系统百科】spinlock 家族

spinlock 是内核最基本的同步原语——持有时不能睡眠、不能被抢占。从最简单的 test-and-set 到如今的 qspinlock，四代演进都在解决一个问题：公平性和 NUMA 扩展性。

一、先看图

flowchart LR
    TAS[test-and-set<br/>不公平] --> TICKET[ticket lock<br/>FIFO 公平]
    TICKET --> MCS[MCS lock<br/>本地自旋]
    MCS --> QSPIN[qspinlock<br/>混合方案<br/>4 字节]
    QSPIN --> PVQSPIN[paravirt qspinlock<br/>虚拟化优化]

    classDef gen fill:#388bfd22,stroke:#388bfd,color:#adbac7;
    class TAS,TICKET,MCS,QSPIN,PVQSPIN gen

二、原始 spinlock（test-and-set）

while (test_and_set(&lock))
    cpu_relax();  // 自旋

问题：

• 不公平：多核竞争时，物理距离近的核更容易抢到
• cache line 风暴：所有核对同一 cacheline 做原子操作

三、ticket lock

struct ticket_lock {
    atomic_t next;   // 取号
    atomic_t owner;  // 当前持有者
};

每个线程取号 → 等自己号码 = owner → 公平（FIFO）。

问题：所有核自旋在同一 cacheline（owner）→ 释放锁时 invalidate 风暴。

四、MCS lock

struct mcs_node {
    struct mcs_node *next;
    int locked;  // 本地自旋变量
};

每个核在自己的 mcs_node.locked 上自旋（本地 cacheline）→ 释放锁时只唤醒下一个。

优势：O(1) cache invalidation → NUMA 友好。 问题：需要额外内存（每核一个 node）→ 不能直接替换 4 字节 spinlock。

五、qspinlock

Linux 4.2+ 的默认 spinlock。4 字节内编码三层状态：

union {
    atomic_t val;
    struct {
        u8 locked;    // 是否已锁
        u8 pending;   // 是否有人等待（fast path）
        u16 tail;     // MCS 队列尾
    };
};

5.1 三路径

1. Fast path：lock 为 0 → CAS 获取（一条原子指令）
2. Pending path：lock 被持有但无队列 → 设 pending 位 → 自旋等 locked 清零
3. Slow path：已有 pending → 入 MCS 队列 → 本地自旋

5.2 优势

• 无竞争：和 test-and-set 一样快
• 中等竞争：pending 避免建队列
• 高竞争：MCS 队列避免 cacheline 风暴

六、paravirt qspinlock

虚拟化场景：持锁 vCPU 被 hypervisor 调度走 → 其他 vCPU 白白自旋（lock holder preemption）。

PV qspinlock（4.8+）：检测到持锁者未运行 → halt 当前 vCPU → hypervisor 优先调度持锁者。

七、spin_lock 变体

错误使用 → 死锁或中断延迟。

八、rwlock 的退休

rwlock_t：多读者并行、写者独占。

问题：读者侧仍是全局计数器 → cache line bouncing → 多核性能差。

替代：RCU（读侧零开销）、percpu_rwsem。

九、PREEMPT_RT 下的 spinlock

PREEMPT_RT 把 spinlock_t 替换为 rt_mutex → 可睡眠 → 优先级继承。

只有 raw_spinlock_t 保持真正的自旋（硬中断路径等）。

十、小结

• test-and-set → ticket → MCS → qspinlock：公平性和扩展性不断改进
• qspinlock 是 Linux 默认，4 字节内编码三路径
• paravirt 解决虚拟化下的 lock holder preemption
• PREEMPT_RT 把 spinlock 变成可睡眠锁

参考文献

• kernel/locking/qspinlock.c
• Documentation/locking/
• Waiman Long, “qspinlock: a 4-byte queue spinlock.” 2014
• include/linux/spinlock_types.h

工具

• lockstat（/proc/lock_stat）
• perf lock
• bpftrace -e 'kprobe:queued_spin_lock_slowpath { @[kstack] = count(); }'

上一篇：原子 RMW 下一篇：mutex/rwsem