os

futex 与内核同步原语底层：等待队列、唤醒机制与 PI mutex

pthread_mutex 无竞争时根本不进内核，有竞争时才通过 futex 系统调用挂起线程。本文拆解 futex 的用户态快路径、系统调用操作码、等待队列与唤醒，以及 PI futex 如何用优先级继承解决优先级反转。

Leeting Yan 10 分钟阅读 4540 字

在 Linux 上，一把没被争抢的 pthread_mutex 加锁解锁，全程不发生任何系统调用——它只是几条原子指令。只有当线程真正争抢时，才通过 futex（Fast Userspace muTEX）陷入内核挂起等待。这个"快路径在用户态、慢路径才进内核"的设计，是 Linux 同步原语高性能的根本原因，也是理解 pthread、C++ std::mutex、Go/Java 运行时锁实现的关键。

本文从 futex 的设计哲学出发，逐层拆解：原子操作如何构成用户态快路径、futex(2) 系统调用有哪些操作码、内核如何用等待队列挂起与唤醒线程、PI futex 如何用优先级继承对抗优先级反转、glibc 如何与内核协作，最后给出观测与调优方法。它与 https://plumephp.com/os-synchronization/（同步原语总览）、https://plumephp.com/os-deadlock/（死锁）、https://plumephp.com/os-process-thread/（线程模型）以及 https://plumephp.com/os-realtime-scheduling/（实时优先级）互相衔接。

一、futex 的设计哲学

1.1 问题的起点：系统调用太贵

早期 Linux 用 System V 信号量做同步，每次加解锁都要进内核。一次系统调用在现代硬件上约几百纳秒到微秒，而一条原子指令只要几十个周期。对于"绝大多数加锁都是无竞争"的实际情况，这完全是浪费。

futex 的核心洞察是：把"锁状态"这个整数放在用户态内存里，让无竞争路径完全在用户态完成；只有在需要睡眠/唤醒时才进内核，并把这块用户态内存的地址作为"身份证"传给内核。

1.2 两个角色

futex 由两部分组成：

  • 用户态整数（32 位，位于共享内存或进程地址空间）：表示锁状态，用原子指令读写。
  • 内核等待队列：以这个整数的虚拟地址为键，挂起等待的线程。
用户态内存:  [ futex word = 1 ]  ← 原子操作改这里
                    │ 地址作为键
                    ▼
内核:        hash(addr) → waitqueue → { task A, task B, ... }

1.3 快路径与慢路径

一把互斥锁的典型实现：

lock():
  原子 CAS: 若 0 -> 1 成功，直接返回      ← 快路径，无系统调用
  否则: 调用 futex(FUTEX_WAIT) 挂起        ← 慢路径，进内核

unlock():
  原子置 0
  若有等待者: 调用 futex(FUTEX_WAKE) 唤醒一个   ← 仅在有竞争时才调用

关键在于：unlock 也只在"检测到可能有等待者"时才调系统调用。glibc 用 futex word 的高位标记"有等待者"，让无竞争的 unlock 保持纯用户态。

二、futex 系统调用与操作码

2.1 接口原型

#include <linux/futex.h>
#include <sys/syscall.h>

long syscall(SYS_futex, int *uaddr, int futex_op, int val,
             const struct timespec *timeout, int *uaddr2, int val3);

参数中 uaddr 是那块用户态整数的地址，futex_op 决定操作类型。

2.2 主要操作码

操作码作用
FUTEX_WAIT若 *uaddr == val 则睡眠，否则立即返回 EAGAIN
FUTEX_WAKE唤醒最多 val 个等待者
FUTEX_WAIT_BITSET带位掩码的等待（可精确唤醒）
FUTEX_WAKE_BITSET带位掩码的唤醒
FUTEX_REQUEUE把等待者从 uaddr 移到 uaddr2
FUTEX_CMP_REQUEUE条件式 requeue（校验值）
FUTEX_LOCK_PI加锁并启用优先级继承
FUTEX_UNLOCK_PI解锁 PI futex
FUTEX_WAIT_REQUEUE_PI等待并转移到 PI futex

FUTEX_WAIT 的"值校验"是精髓：内核在挂起前会原子地检查 *uaddr 是否仍等于 val。若已被别人改动，说明状态变了，不必睡眠，直接返回 EAGAIN 让用户态重试。这消除了"检查后睡眠"之间的竞态窗口。

2.3 位集：一个 futex 支持多组等待者

FUTEX_WAIT_BITSET 允许一个 futex word 上挂多组等待者，每组用不同的位掩码。唤醒时只有掩码匹配的组被唤醒。这就是 condition variable（条件变量）的高效实现基础：不同条件可以共享同一个 futex word，却只唤醒相关的那组线程。

/* 等待：只对 bit 0x1 感兴趣 */
syscall(SYS_futex, &word, FUTEX_WAIT_BITSET | FUTEX_PRIVATE_FLAG,
        expected, &timeout, NULL, 0x1);

/* 唤醒：只唤醒 bit 0x1 组 */
syscall(SYS_futex, &word, FUTEX_WAKE_BITSET | FUTEX_PRIVATE_FLAG,
        1, NULL, NULL, 0x1);

2.4 PRIVATE 标志

FUTEX_PRIVATE_FLAG 表示这个 futex 只用于同一进程内的线程。内核据此走更快的内核路径（不需要跨进程查找 mm、可以用进程内的哈希表）。pthread_mutex 默认就用 private futex；PTHREAD_PROCESS_SHARED 的互斥量则不带这个标志。

进程内线程同步   → FUTEX_PRIVATE_FLAG   （快）
跨进程共享内存同步 → 无 PRIVATE 标志    （稍慢，需按 mm 查找）

三、等待队列与唤醒

3.1 内核数据结构

每个 futex word 对应一个 struct futex_q，挂在按地址哈希的桶上：

/* kernel/futex/core.c */
struct futex_q {
    struct plist_node list;         /* 挂在哈希桶的链上，按优先级排序 */
    struct task_struct *task;       /* 等待的任务 */
    spinlock_t *lock_ptr;
    union futex_key key;            /* 由用户态地址派生的全局键 */
    u32 bitset;
    struct hrtimer timer;           /* 带超时的等待用 */
    ...
};

struct futex_hash_bucket {
    atomic_t waiters;
    spinlock_t lock;
    struct plist_head chain;
};

全局有 futex_queues[256] 个哈希桶，键是 union futex_key（由 mm、地址、inode 等组合），保证不同进程的地址空间不会互相串扰。

3.2 挂起路径

FUTEX_WAIT 的内核流程：

futex_wait()
  → futex_wait_setup()      在桶锁保护下再次校验 *uaddr == val
  → futex_wait_queue()      把 futex_q 挂入桶
  → schedule()              让出 CPU，线程进入 TASK_INTERRUPTIBLE
  → （被唤醒后）futex_wait_cleanup()  从桶中摘除

注意第二行的"二次校验"：用户态已经检查过一次，但检查与挂起之间可能被抢占，所以内核在持桶锁的情况下再查一次，杜绝丢唤醒（lost wakeup）。

3.3 唤醒路径

futex_wake()
  → 按地址找到哈希桶
  → 遍历 plist，取前 val 个匹配 bitset 的等待者
  → wake_up_process() 逐个唤醒

plist_node（priority list）按优先级排序，因此高优先级线程优先被唤醒——这对实时性很重要：唤醒一个低优先级线程去跑、把高优先级线程晾着，会造成优先级反转。

3.4 一个裸 futex 的例子

不借助 pthread，直接用 futex 实现一个互斥锁：

#define _GNU_SOURCE
#include <linux/futex.h>
#include <sys/syscall.h>
#include <unistd.h>
#include <stdatomic.h>

static int futex_word = 0;   /* 0=空闲 1=已锁 2=已锁且有等待者 */

static int futex(int *uaddr, int op, int val) {
    return syscall(SYS_futex, uaddr, op | FUTEX_PRIVATE_FLAG, val,
                   NULL, NULL, 0);
}

void my_lock(void) {
    int c = 0;
    /* 快路径：0 -> 1 */
    if (atomic_compare_exchange_strong(&futex_word, &c, 1))
        return;
    /* 慢路径：置 2 并等待 */
    do {
        if (c == 2 || atomic_exchange(&futex_word, 2) != 0)
            futex(&futex_word, FUTEX_WAIT, 2);
        c = 0;
    } while (!atomic_compare_exchange_strong(&futex_word, &c, 2));
}

void my_unlock(void) {
    if (atomic_fetch_sub(&futex_word, 1) != 1) {
        atomic_store(&futex_word, 0);
        futex(&futex_word, FUTEX_WAKE, 1);
    }
}

这段代码与 glibc 内部逻辑同构：状态 2 表示"有等待者"，从而让 unlock 知道该不该调系统调用。

四、优先级继承：PI futex

4.1 优先级反转

实时系统里有个致命问题：低优先级线程 L 持有锁，高优先级线程 H 来抢锁被阻塞，中优先级线程 M 一直抢占 L 的 CPU——结果是 H 在等 M 跑完，优先级完全反转。1997 年火星探路者号就因此反复重启。

4.2 优先级继承

优先级继承（Priority Inheritance） 的思路：当 H 阻塞在 L 持有的锁上时，临时把 L 的优先级提升到 H 的级别，让它尽快跑完释放锁，然后恢复原优先级。

正常：L(10) 持锁，H(90) 阻塞，M(50) 抢占 L → H 等 M，反转！
PI  ：L 被临时提到 90，M 无法抢占 L → L 跑完放锁 → H 立即获得

4.3 PI futex 的使用

用户态通过 FUTEX_LOCK_PI / FUTEX_UNLOCK_PI 使用 PI 版本的 futex：

/* 加锁：内核会处理优先级继承 */
syscall(SYS_futex, &word, FUTEX_LOCK_PI, 0, &timeout, NULL, 0);

/* 解锁：内核恢复继承链上的优先级 */
syscall(SYS_futex, &word, FUTEX_UNLOCK_PI, 0, NULL, NULL, 0);

内核为每个 PI futex 维护一个 struct rt_mutex（实时互斥量），并保存 rt_mutex_waiter 的优先级链。当锁释放时，内核会沿着等待链重新计算并恢复被提升线程的优先级。

4.4 PI 的代价

  • 每次加解锁都可能进内核：PI futex 无法像普通 futex 那样"纯用户态快路径"，因为内核必须知道谁持有锁才能做继承。因此 PI mutex 明显更慢。
  • 优先级上限协议：另一种方案是 PTHREAD_PRIO_PROTECT（优先级天花板），把锁的优先级设为所有可能使用者的最大值，避免继承链的复杂度，代价是低优先级线程可能被过度提升。

4.5 何时该用 PI

只有实时或强优先级语义的系统才需要 PI。普通服务端应用用普通 futex 即可。glibc 里对应 PTHREAD_PRIO_INHERIT 属性：

pthread_mutexattr_t attr;
pthread_mutexattr_init(&attr);
pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);
pthread_mutex_init(&mtx, &attr);

五、glibc 与内核的协作

5.1 pthread_mutex 的状态机

glibc 的 pthread_mutex_t 内部就是一个 32 位 futex word，位布局大致为：

bit 0    : 锁是否被持有
bit 1    : 是否有等待者
bit 2    : 是否为 PI / robust 等标志
其余位    : 递归计数 / 拥有者 tid（用于 robust 与错误检测）

/* 简化后的加锁逻辑 */
int __pthread_mutex_lock(pthread_mutex_t *m) {
    /* 快路径：一条 CAS */
    if (atomic_cas(&m->__data.__lock, 0, 1) == 0)
        return 0;
    return __pthread_mutex_lock_slow(m);   /* 慢路径，调 futex */
}

5.2 自适应锁与自旋

glibc 提供 PTHREAD_MUTEX_ADAPTIVE_NP：慢路径会先自旋一小段时间（几十次），若锁很快被释放就不必进内核睡眠。这对"临界区极短、竞争不激烈"的场景有显著收益。内核 futex 也有 FUTEX_LOCK_PI2 等演进，但用户态自旋是第一道缓冲。

5.3 条件变量与信号量

  • pthread_cond_wait：内部用 FUTEX_WAIT_BITSET，配合序列号避免丢唤醒。
  • sem_wait：用 FUTEX_WAIT 等待计数变为正。
  • pthread_rwlock：读写状态编码进 futex word。

5.4 robust futex：线程崩溃时的锁清理

若持锁线程崩溃，锁会永久处于"已锁"状态。robust futex（PTHREAD_MUTEX_ROBUST）让内核在持有者退出时，把锁标记为"拥有者已死"，下一个加锁者会收到 EOWNERDEAD，从而有机会做恢复。这对共享内存中的跨进程锁尤其重要。

六、观测、调优与常见误区

6.1 观测 futex 行为

# 统计某个进程的 futex 系统调用次数与耗时
strace -c -e trace=futex ./app

# 追踪具体的 futex 调用（含操作码与地址）
strace -e trace=futex -T ./app 2>&1 | head -20

# 用 perf 看 futex 热点
perf top -e 'syscalls:sys_enter_futex'

# 查看线程阻塞在 futex 的栈
cat /proc/<pid>/task/<tid>/stack     # 需 root 与 CONFIG_STACKTRACE

strace -c 输出的 futex 占比是判断"锁竞争是否严重"的第一手信号：占比高说明线程频繁进出内核等待。

6.2 调优方向

  1. 减小临界区：临界区越短，竞争越少，快路径命中率越高。
  2. 减少共享：分片锁（sharded lock）、每线程数据（thread-local）比一把大锁更好。
  3. 自旋 + 退避：短临界区用自适应自旋，避免睡眠/唤醒的上下文切换开销。
  4. 读多写少用读写锁或无锁：rwlock 仍会写写竞争，读多场景可用 RCU 或原子读。
  5. 实时任务用 PI mutex：避免优先级反转，但接受更高的加解锁开销。

6.3 五个高频误区

  1. “futex 就是一把锁”。futex 只是一个"等待/唤醒"的机制，锁的语义完全由用户态实现。futex word 的编码方式由使用者定义。

  2. “PI mutex 更快”。恰恰相反，PI mutex 因需要内核介入而更慢，只在需要优先级继承时使用。

  3. “自旋锁适合所有场景”。自旋在单核或高竞争下是灾难：白白烧 CPU。自旋只适合临界区极短且核数充足的情况。

  4. “cond_wait 唤醒后条件一定成立”。pthread_cond_wait 存在虚假唤醒，必须放在 while 循环里重新检查条件。

  5. “进程共享的 futex 无成本”。跨进程 futex 不能带 PRIVATE 标志，内核查找更慢，且必须放在真正的共享内存（mmap MAP_SHARED）里。

6.4 一个典型死锁场景

/* 两个线程以不同顺序获取两把锁 -> 死锁 */
/* 线程 1 */ lock(A); lock(B);
/* 线程 2 */ lock(B); lock(A);

futex 层无法检测这种死锁（它只看到两个等待队列），但 lockdep 能在内核态发现锁序违规。用户态可用 helgrind（Valgrind）或 TSan 检测锁序违规。

结语

futex 把"锁"这个抽象从内核里赶回了用户态，只在真正需要睡眠时才请内核帮忙。理解它的三个要点——用户态快路径靠原子指令、慢路径靠 FUTEX_WAIT/WAKE 的二次校验、实时场景靠 PI 做优先级继承——就能看穿 pthread、std::mutex、Go 运行时锁的一切行为。它与 https://plumephp.com/os-cpu-scheduling/ 的调度决策结合，决定了多线程程序在高竞争下的真实吞吐与延迟。

延伸阅读

  1. Linux Kernel Documentation: Documentation/locking/futex2.rst 与 futex-requeue-pi 相关文档
  2. Linux 内核源码：kernel/futex/core.c（哈希与等待队列）、kernel/futex/waitwake.c（等待唤醒）
  3. Linux 内核源码：kernel/locking/rtmutex.c（PI 优先级继承实现）
  4. Ulrich Drepper 论文《Futexes Are Tricky》（futex 实现陷阱的经典分析）
  5. 《Computer Systems: A Programmer’s Perspective》第 12 章并发编程（原子操作与同步）

继续阅读

探索更多技术文章

浏览归档，发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「os」更多文章

  1. ARM64 体系结构与内核实现
  2. 内核网络栈：sk_buff、NAPI 与 XDP
  3. eBPF 开发实战：CO-RE 与 libbpf