Katyusha's blog

互斥问题的基本模型#

线程共享地址空间后，问题不再是“有没有两个核”，而是“多个执行流会不会以不受控制的顺序访问同一份共享状态”。如果会，那么像 sum++、check-then-act 这样的操作就可能被撕成可交错的 load/add/store，从而破坏不变量。

这时就需要把一段“不能被并发打断”的代码圈出来。这段代码叫 critical section。它是一个语义边界，表示：

• 这一段访问了共享状态；
• 若多个线程同时执行，会破坏正确性；
• 因而需要某种机制保证它对外表现得像“一个一个来”。

所以三者不要混：

• critical section：问题定义，指出哪段代码必须受保护；
• mutex：最常见的实现机制，用 lock/unlock 把临界区串行化；
• transactional memory：另一种更高层机制，把一段代码当作事务执行，冲突时回滚重试。

也就是说，临界区不是锁；锁只是实现临界区的一种办法。课堂主线关注的是 mutex，因为它最直接、最工程化。

互斥锁的语义保证#

讲义里最重要的直觉是：lock/unlock 相当于对一段代码做了一次局部的 stop the world。

1
lock();
2
// critical section
3
unlock();

只要程序员正确使用同一把锁保护相关共享状态，就可以把这段代码近似看成：

• 进入前，别的线程不能同时执行同一把锁保护的临界区；
• 离开后，临界区里的写入会对下一个拿到锁的人可见。

这也是为什么 mutex 不只是“门口放一把钥匙”，它还自带内存顺序语义：

• lock 近似 acquire：拿到锁后，能看到上一个 unlock 之前写入的内容；
• unlock 近似 release：离开临界区前，把这段代码的写入对后继持锁者发布出去。

所以互斥锁解决的不只是“同时只能进一个人”，还顺手建立了 happens-before。这正是它比“自己写两个共享变量轮询”可靠得多的原因。

互斥锁的使用原则与粒度策略#

锁最常见的 bug 不是算法高深，而是保护边界画错了。最重要的原则有三条：

• 保护同一组共享不变量的代码，必须用同一把锁；
• lock 和 unlock 必须成对，且异常路径也不能漏；
• 临界区里尽量不要做 I/O、睡眠、阻塞等待等长耗时操作。

一个经典错误是“访问同一个共享变量，却用了两把不同的锁”：

1
lock_t L, I;
2

3
void T1() { lock(&L); sum++; unlock(&L); }
4
void T2() { lock(&I); sum++; unlock(&I); } // BUG

看起来都“加锁了”，其实没有互斥，因为两段代码没有被同一把锁串行化。

关于锁粒度，课程给出的工程建议非常朴素：从一把大锁开始。

• 一把大锁最不容易错；
• 先把程序写对，再做压力测试和 profile；
• 只有证明锁竞争真是瓶颈，才拆成细粒度锁。

Linux 早期的 Big Kernel Lock 就是这么来的：先让系统在多处理器上“能工作”，再花很多年沿着真实瓶颈慢慢拆。对学习和工程都一样，先正确，再优化。

互斥与并行性的关系#

乍看上去，互斥就是强行串行化，似乎和并行完全对立；但真正的判断标准是“被串行化的部分到底占多大”。

从固定工作量看，Amdahl’s Law 说：

$S(N) = \frac{1}{s + \frac{1-s}{N}}$

其中 s 是不可并行部分。它强调的是瓶颈：只要串行部分不为 0，加速比就有上限。锁把临界区串行化，等于增大了 s，所以临界区越大，并行扩展性越差。

从可扩展工作量看，Gustafson’s Law 则更乐观：如果总运行时间大致固定，而问题规模可以随处理器数增加，那么绝大多数并行部分都能扩张，多核仍然有意义。

所以二者并不矛盾，只是回答不同问题：

• Amdahl：固定任务规模下，加核的上限有多高；
• Gustafson：在相近时间预算下，机器变强后能把问题做多大。

对锁的启发是：不要空想“完全无锁的完美并行”，而是要问“真正被锁住的关键路径有多长，能否足够局部化”。

互斥实现的历史路径：Peterson 到原子指令#

讲义专门走了一遍历史路径：先尝试纯软件互斥，再承认这条路在现代机器上不对劲，最后让硬件提供原子指令。

Peterson 协议是两线程互斥的经典算法：

1
int flag[2] = {0, 0};
2
int turn;
3

4
void lock(int self) {
5
    flag[self] = 1;
6
    turn = 1 - self;
7
    while (flag[1 - self] && turn == 1 - self) {
8
        ;
9
    }
10
}
11

12
void unlock(int self) {
13
    flag[self] = 0;
14
}

它在顺序一致性假设下是正确的：两个线程都想进时，用 turn 打破平局；如果只有一个线程想进，它可以直接进入。

但它有两个致命边界：

• 只直接适用于 2 个线程；推广到 n 线程虽有 Filter lock、Bakery algorithm 一类方案，但代价高，工程上几乎不用；
• 它依赖“普通 load/store 原子且按程序顺序生效”的强假设，而现代编译器和 CPU 的重排会破坏这个前提。

所以 Peterson 的价值主要是：

• 它说明了互斥问题本身可以被精确定义和证明；
• 它说明“测试很多次没出错”不等于程序正确；
• 它也说明在现代机器上，直接靠普通共享变量硬写锁并不是对的努力方向。

更现实的解法是让硬件直接给出原子读改写指令，例如 LOCK、LL/SC、CAS、fetch_add。这样“不可分割”不再靠协议模拟，而由 ISA 保证。

自旋锁的实现机制与适用边界#

有了硬件原子指令之后，最直接的锁实现就是自旋锁：

1
typedef int spinlock_t;
2
#define LOCKED 1
3
#define UNLOCKED 0
4

5
void spin_lock(spinlock_t *lock) {
6
    while (__atomic_exchange_n(lock, LOCKED, __ATOMIC_ACQUIRE) == LOCKED) {
7
        ;
8
    }
9
}
10

11
void spin_unlock(spinlock_t *lock) {
12
    __atomic_store_n(lock, UNLOCKED, __ATOMIC_RELEASE);
13
}

它的模型非常简单：

• 抢锁成功就继续；
• 抢不到就原地 busy wait。

spinlock 解决的是互斥，但它的等待方式非常激进：拿不到锁时不睡觉，只烧 CPU。它因此只适合很窄的场景：

• 临界区极短；
• 持锁线程几乎不会被抢占；
• 等待时间预计远小于一次睡眠/唤醒/调度切换的成本。

它的两大缺陷也正来自这里：

• 一个线程持锁时，其他核可能“一核有难，八核围观”，全部空转；
• 更糟的是持锁线程若被调度出去，等待者还会继续白烧 CPU，直到它重新被调回来。

这也是为什么线程数超过 CPU 核数后，spinlock 往往性能断崖式下跌。

内核参与的阻塞式加锁机制#

只靠 spinlock，线程拿不到锁时唯一能做的就是一直试。但如果想做到“拿不到锁就睡，锁可用时再醒”，线程自己做不到，必须让操作系统参与。

这就是“把锁的实现放入操作系统中”的含义：等待锁不再只是用户态里的循环，而变成：

• 线程发现锁被占用；
• 进入内核，告诉调度器“我在等这把锁”；
• 内核把它挂到等待队列，标记为休眠/阻塞；
• 解锁时内核再唤醒等待者。

最朴素的伪代码是：

1
void lock(int *m) {
2
    while (syscall(SYS_mutex_acquire, m)) {
3
        ; // 内核内部会把当前线程睡眠
4
    }
5
}
6

7
void unlock(int *m) {
8
    syscall(SYS_mutex_release, m);
9
}

这样做的好处是：

• 等待者不再空转；
• 调度器知道谁在等谁；
• 可以用睡眠-唤醒代替忙等。

代价是：

• 每次 lock/unlock 可能都要进内核；
• 系统调用和上下文切换都有开销。

所以“全靠用户态自旋”和“每次都进内核”都太极端。现代系统采用的是折中路线。

Futex 的混合实现模型#

futex 的全称就是 fast userspace mutex。它不是“另一种高层语义上的锁”，而是一种把用户态原子操作和内核睡眠/唤醒拼起来的底层机制。

核心思想是两条路径：

• fast path：没人竞争时，直接在用户态用原子指令拿锁和放锁，不进内核；
• slow path：抢不到锁时，调用 futex(FUTEX_WAIT, ...) 让内核把线程挂起；释放锁时若发现有等待者，再 futex(FUTEX_WAKE, ...) 唤醒它们。

因此四个概念必须分清：

• spinlock：互斥语义，等待方式是忙等；
• mutex：互斥语义，等待方式通常是阻塞；
• futex：底层睡眠/唤醒机制，用来高效实现前者中的阻塞路径；
• pthread_mutex_t：对程序员暴露的高层 mutex API，glibc 背后常常靠 futex 实现。

所以“mutex 和 futex 有什么区别”时，最准确的答案是：

• mutex 是同步语义；
• futex 是 Linux 里常见的实现机制。

讲义里的 benchmark 结论也很直观：多数场景下性能大致是 atomic > mutex > spin > trap。其中 trap 指每次都强行进内核的朴素方案，它慢正说明了为什么 futex 一定要保留用户态快路径。

相关概念辨析#

• critical section：一段必须看起来原子执行的代码区域，是问题定义；
• mutex：保证临界区互斥进入的高层原语；
• transactional memory：另一种实现临界区原子性的机制，冲突时回滚；
• Peterson：两线程、顺序一致性假设下的纯软件互斥协议，教学价值大于工程价值；
• spinlock：基于原子交换的忙等锁，适合极短临界区；
• syscall-based lock：拿不到锁就交给内核阻塞，正确但慢；
• futex：用户态快路径 + 内核慢路径的混合机制，是现代 pthread_mutex_t 的常见底层。

本节小结#

1
1. critical section 是“哪段代码必须受保护”，mutex 是“怎么保护”的机制。
2
2. lock/unlock 不只是串行化，还建立 acquire/release 语义和 happens-before。
3
3. 锁的第一原则是“同一组共享不变量用同一把锁”，工程上先一把大锁，再按瓶颈细化。
4
4. Amdahl 讲固定规模下的串行瓶颈上限，Gustafson 讲固定时间下的规模扩展。
5
5. Peterson 协议能帮助理解互斥证明，但只直接适用于 2 线程，且依赖现代机器并不满足的强假设。
6
6. spinlock 用忙等换低延迟；一旦等待时间长或线程数超过核数，就会浪费 CPU 甚至崩溃。
7
7. 把锁“放进操作系统”就是把等待锁这件事交给调度器，用睡眠/唤醒替代空转。
8
8. futex 不是 mutex 的同义词，而是 Linux 中常用的底层实现机制：无争抢走用户态，争抢走内核。