Post

并发控制：互斥（Mutual-Exclusion）

Posted
By 何翌闻
31 min read
并发控制：互斥（Mutual-Exclusion）

0. 写在前面：为什么操作系统课要讲并发？

并发不是“多线程编程”的内容吗，为什么放在操作系统里讲？

原因来自 UNIX 的 fork-execve 模型。在这个模型下，进程之间是不共享内存的——这看起来已经把并发问题给隔离掉了。但是有一个例外：系统调用是共享内存的。

当进程执行 syscall 指令时，控制流跳转到操作系统内核代码。所有进程的内核代码运行在“同一个 C 程序”里，访问同一份内核数据结构。考虑这种情景：

  • 进程 P1 执行 read(fd, buf, size)
  • 进程 P2 执行 write(fd, buf, size)

它们可以访问同一个文件、同一个 inode、同一个文件描述符表。每个进程的“系统调用部分”实际上就成了内核里的一个线程，而所有这些线程共享内核的全部数据。

操作系统是人类历史上第一个真正严肃的大型并发程序。

所以并发控制是 OS 内核自身实现就必须解决的问题。

1. 问题的源头：1 + 1 为什么会算错？

回顾上一讲的经典例子：

1
2
3
4
5
6
7

long sum = 0;

void T_sum() {
    for (int i = 0; i < N; i++) {
        sum++;
    }
}

两个线程并发执行 T_sum，最终 sum 的值可能小于 2N。原因是 sum++ 不是原子的，它实际上是三条指令：

1
2
3

load  sum -> reg
add   reg, 1
store reg -> sum

两个线程的这三条指令可以任意交错，导致更新丢失。

我们想要一个语言机制或 API，使得无论怎么调度，结果都是正确的。这个需求的本质是：阻止某些代码段的并发执行，让它们看起来像是依次发生的。这就是互斥（mutual exclusion）。

如果用一个魔法关键字 make_it_work：

1
2
3
4
5

void T_sum() {
    make_it_work {
        sum++;
    }
}

顺便一提：如果这个机制真的存在，恭喜你发明了 Transactional Memory（事务内存）。Intel 在 Haswell 之后引入了 TSX 扩展（xbegin/xend），但因为各种安全漏洞和性能问题，事务内存至今没有成为主流方案。

2. 在内核里实现互斥的最朴素思路

2.1 单处理器：关中断

在单核机器上，并发的唯一来源是中断：时钟中断会触发线程切换。所以只要关掉中断，当前代码就不可能被打断：

1
2
3

disable_interrupt();
sum++;
enable_interrupt();

简单粗暴，效果拔群。但有几个问题：

  1. 只在内核里能用：用户程序无权关中断（否则一个 while(1) 就能让整台机器卡死）。
  2. 不能持续太久：长时间关中断会让系统失去响应。
  3. 完全不适用于多处理器：关掉一个核的中断，其他核照样在跑。即使把所有核的中断都关了——首先这本身就需要互斥来协调，是个鸡生蛋的问题；其次系统失去了所有响应能力。

所以关中断只是单核内核里的一个临时手段，不是通用方案。

3. 互斥锁：API 与思维模型

3.1 API 长什么样

我们希望有这样一对 API：

1
2
3
4

lock();
// 临界区（critical section）：任意代码
sum++;
unlock();

凡是被 lock() / unlock() 包裹的代码块，互相之间是 mutually exclusive 的——同一时刻最多只有一个线程在执行其中之一。这种机制叫做 mutex lock（互斥锁）。

3.2 两个直观的拟人模型

理解锁有两个非常有用的比喻。

模型一：宿舍厕所的包厢（什么鬼模型🫠

  • lock()：进了包厢就把门反锁，别人进不来；但你自己可以继续在里面活动。
  • unlock()：开门出来，别人才能进。

模型二：桌上的一把钥匙

  • lock()（或称 acquire）：桌上有钥匙就拿走，没有就等着。
  • unlock()（或称 release）：把钥匙放回桌上。

这两个模型都强调一个关键点：同一时刻最多一个线程持有锁。

3.3 多把锁

没有人规定整个程序只能有一把锁。我们可以为不同的资源准备不同的锁：

1
2
3
4
5
6
7
8
9
10

mutex_t lock_a = MUTEX_INIT();
mutex_t lock_b = MUTEX_INIT();

mutex_lock(&lock_a);
x++;
mutex_unlock(&lock_a);

mutex_lock(&lock_b);
y++;
mutex_unlock(&lock_b);

修改 x 和修改 y 的代码完全不冲突，可以真正并行。这就是锁的粒度（lock granularity）问题：粒度越细，并行度越高，但管理成本也越高。

4. 用锁的“陷阱”：API 简单不代表用对了

假设你正确使用了锁——也就是说，临界区外的线程不会去读写临界区里访问的数据——那么程序的行为就和“暂停整个世界、只让临界区里的代码跑”完全等价。

这句话听起来很美好。但正确使用锁完全是程序员的责任，编译器和运行时不会帮你检查。一旦写错，崩溃的姿势千奇百怪，而且往往很难复现。

4.1 经典错误：锁错了对象

1
2

T1: lock(&l); sum++; unlock(&l);
T2: lock(&I); sum++; unlock(&I);

注意区别了吗？l（小写 L）和 I（大写 i）是两把不同的锁。两个线程拿着不同的锁去保护同一个变量，等于没保护。

不要笑——在几十把锁、十几个文件的真实代码里，没有人能保证自己永远清醒。

4.2 更难的例子：链表的并发访问

考虑一个并发的双向链表，每个节点带自己的锁：

1
2
3
4

struct node {
    lock_t lock;
    struct node *prev, *next;
};

要正确地并发操作它，需要：

  • 遍历：要采用“hand-over-hand locking”（交替持锁）——先锁 next，再解锁 current，否则中间可能被插入或删除。
  • 插入/删除：需要同时持有 prev、current、next 三把锁，而且加锁顺序必须固定（否则会死锁）。
  • 内存回收：删除一个节点后什么时候 free 它？必须确保没有任何线程还持有指向它的引用——这本身就是一个非常困难的问题（参见 RCU、hazard pointer、epoch-based reclamation 等技术）。

4.3 一条朴素但极有价值的工程建议

从“一把大锁保平安”开始。

Linux 内核早期就只有一把“大内核锁”（Big Kernel Lock, BKL），所有内核代码串行执行。随着对性能的要求提高，才逐步把大锁拆成更细的锁。

这背后的格言是 Knuth 的那句老话：

Premature optimization is the root of all evil.

写并发代码，先保证正确，再考虑性能。任何“看起来更聪明”的优化，都需要严格的论证和测试。

5. 一个反向思考：既然加锁这么麻烦，干脆别并发？

加锁的代码本质上是串行的，那把所有代码都用一把大锁保护，不就退化成单线程了吗？多核还有什么意义？

这里有两个对立的“定律”。

5.1 悲观的 Amdahl’s Law

如果程序中有 $1/k$ 的部分无法并行，那么无论有多少处理器，加速比都受限于：

\[T_\infty > \frac{T_1}{k}\]

也就是说，串行部分会成为不可逾越的瓶颈。哪怕只有 5% 的代码不能并行，最大加速比也只有 20 倍。这个定律一度让人对多核失去信心。

5.2 乐观的 Gustafson’s Law

但 Gustafson 指出：当问题规模本身可以扩大时，可并行的部分会随规模线性增长，而串行部分基本不变。也就是说，多核给我们的不是“更快地解决相同的问题”，而是“在相同时间内解决更大的问题”。

更精细一点：

\[T_p < T_\infty + \frac{T_1}{p}\]

5.3 物理世界本就是大规模并行的

经典物理有一个朴素的局部性原理：一个物体对相邻物体的影响需要时间传递。这意味着任何对物理世界的模拟天然就是可并行的——空间上分得足够开的部分可以独立计算。

一些“embarrassingly parallel”（高度可并行）的例子：

  • 图书馆 vs 分布式数据存储：每本书可以独立借阅，每个数据分片可以独立访问。
  • 大脑 vs 深度神经网络：神经元之间的连接是局部的，可以分块并行计算。
  • NP-Hard 问题的搜索：搜索树的不同分支可以独立探索（fork-based DFS）。

所以并发不是“不得不做”的麻烦事，而是充分利用硬件的根本路径。

6. 用 load/store 实现互斥：一条死胡同

6.1 历史尝试：Dekker 和 Peterson

在硬件原子指令出现之前，理论计算机科学家们尝试只用普通的 load/store 实现互斥。1965 年的 Dekker 算法和 1981 年的 Peterson 算法是其中最著名的两个。

Peterson 算法的描述：

一个进程 P 可以进入临界区，如果另一个进程不想进入；或者它已经表达了进入意愿，并且把“轮到对方”的标志让给了对方。

用拟人化的厕所模型🚽来理解：

三个共享变量：你的旗子、他的旗子、厕所门上的便签。

进入流程：

  1. 举起自己的旗子（声明：我想进）
  2. 把“对方的名字”贴在门上（声明：让对方先）
  3. 进入观察循环：
    • 如果对方没举旗，进入。
    • 如果门上贴的是自己的名字（说明对方后到、覆盖了便签），进入。
    • 否则继续观察。

离开流程：放下自己的旗子（不用管门上的便签）。

为什么对：

  • 如果只有一人举旗，他独占资源。
  • 如果两人同时举旗，门上的便签决定谁等——后贴的覆盖先贴的，所以“手快有、手慢无”，避免了无限互让。

6.2 并发算法的可怕之处：你看不出它对不对

Peterson 算法只有几行，但要论证它的正确性极其困难。一个有趣的事实：

n 个线程循环 m 次执行带锁的 sum++，问 sum 的最小可能值是多少？这是一个 NP-Complete 甚至更难的问题。

也就是说，判断一段并发代码“在最坏情况下能错到多离谱”本身就是计算困难的。

6.3 验证并发算法的两种现代手段

  • Brute force（穷举）：Peterson 算法的状态空间是有限的——(x, y, turn, PC1, PC2) 总共没几个状态。可以用模型检查器穷举所有可能的执行路径。这正是 2007 年图灵奖（Edmund Clarke、Allen Emerson、Joseph Sifakis）的主题：模型检查（Model Checking）。
  • Induction（归纳）：当状态空间无限时，需要找到一个不变式（invariant），证明它在每一步都成立。本质上是把状态空间做了划分。

6.4 致命问题：Peterson 算法在现代硬件上是错的

理论上 Peterson 算法是对的，但它依赖两个现实中不成立的假设：

  1. load/store 是瞬间完成且全局可见的——错。现代 CPU 有 store buffer，写操作不会立即对其他核可见。
  2. 指令按程序书写的顺序执行——错。编译器会重排指令，CPU 会乱序执行。

具体来说，现代 CPU 普遍采用弱内存模型（weak memory model）。比如 x86 是 TSO（Total Store Order），但即使是 TSO 也允许 store-load 重排。考虑 Peterson 算法的关键步骤：

1
2
3

flag[me] = true;       // store
turn = other;          // store
while (flag[other] && turn == other);  // load

在弱内存模型下，编译器或 CPU 可能把 flag[me] = true 这个 store 缓冲起来，让后面的 load 先执行。结果两个线程都看到对方没有举旗，同时进入临界区。

6.5 修复：内存屏障

要让 Peterson 算法在现代硬件上正确工作，必须显式插入屏障：

  • 编译器屏障（compiler barrier）：asm volatile("" ::: "memory") 或使用 volatile 变量，告诉编译器不要跨过这个点重排内存访问。
  • 内存屏障（memory barrier）：__sync_synchronize()，对应不同架构：
    • x86：mfence
    • ARM：dmb ish
    • RISC-V：fence rw, rw

加上屏障之后，Peterson 算法才能在现代硬件上正常工作。但代价是：每次进入临界区都要做完整的内存同步，性能极差。

6.6 路线错误的反思

试图只用 load/store 实现互斥，是一个方向错误。

这是计算机科学和自然科学的一个根本不同：自然科学中，规则是上帝定的，我们只能去发现；而计算机系统是我们造的，我们可以修改规则。

既然 load/store 不好实现互斥，那我们就让硬件加几条专门的指令——这才是工程上正确的方向。

7. 硬件帮忙：原子指令

7.1 atomic

希腊语 ἄτομος（atomos）意为 “indivisible”——不可分割的。原子指令的含义就是：一段 load + 计算 + store 的组合，从外部观察是不可分割的，要么完全发生，要么完全没发生。

7.2 各架构的原子指令

不同架构提供原子性的方式不同：

  • x86：lock 前缀。给任何内存操作指令加上 lock，CPU 就会通过总线锁或缓存一致性协议保证这条指令的原子性。比如 lock cmpxchg、lock xadd。
  • RISC-V：原生提供 LR/SC（Load-Reserved / Store-Conditional），思想来自 MIPS 的 LL/SC。LR 读一个值并标记地址，如果 SC 之间这个地址没被其他核改过，SC 成功；否则失败重试。同时 RISC-V 还有 A 扩展提供原子算术指令。
  • ARM：ldxr/stxr（与 RISC-V 的 LR/SC 类似）；ARMv8.1 之后引入了 stadd 等单指令原子操作。

7.3 用原子指令实现锁

最直观的就是 compare-and-swap（CAS）：原子地比较内存位置的值，如果等于期望值就替换为新值，并返回是否成功。

1
2
3
4
5
6
7
8
9
10
11
12

void lock() {
retry:
    if (can_go == AVAILABLE) {
        can_go = TAKEN;     // 这个 if + 赋值必须原子
    } else {
        goto retry;
    }
}

void unlock() {
    can_go = AVAILABLE;
}

把 if + 赋值用原子指令实现：

1
2
3

movl $AVAILABLE, %eax
movl $TAKEN, %edx
lock cmpxchgl %edx, (can_go)

cmpxchg 比较 %eax 和内存值，相等就把 %edx 写入内存。lock 前缀保证整个过程不被打断。

GCC 提供了跨平台的 built-in：__atomic_compare_exchange_n、__atomic_fetch_add 等，编译器会根据目标架构生成最优指令。

7.4 甚至连锁都不用

对于 sum++ 这种简单操作，根本不需要锁，直接用一条原子加法指令就行：

1

lock addq $1, (sum)

这就是无锁（lock-free）编程的入口。但要注意：原子指令只解决了单个变量的原子更新，复杂的不变式仍然需要锁或更高级的机制（如 RCU、事务内存）。

8. 自旋锁的性能问题

用原子指令直接实现的锁叫自旋锁（spinlock）——拿不到锁就在 retry 上反复循环（”自旋”）。它有两个严重的性能问题。

8.1 问题一：CPU 空转

“一核有难，八核围观。”

只有一个线程在临界区里干活，其他试图获取锁的线程都在原地空转，浪费 CPU。

如果临界区代码只跑几十个时钟周期，自旋一下就能拿到锁，开销很小。但如果临界区要跑几毫秒甚至更久（比如要做 I/O），自旋几亿次都拿不到锁，等于把 CPU 烧光。

结论：自旋锁只适合保护极短的临界区。

8.2 问题二：持锁线程被切换走

更糟糕的情况：

  1. 线程 A 在用户态获得了自旋锁。
  2. 时钟中断到来，调度器把 A 换出，调度器决定运行线程 B。
  3. B 试图获得同一把锁——A 还没释放呢。
  4. B 自旋……一直自旋……直到时间片用完。
  5. 调度器再换上 C、D……所有线程都在自旋等 A，但 A 根本没机会运行。

应用程序在用户态不能关中断，所以没法防止持锁时被切换。结果就是 100% 的 CPU 浪费。

8.3 解决方案：让操作系统介入

线程自己解决不了的事，让操作系统帮忙。把”获取锁失败”这件事告诉内核：

1
2

syscall(SYSCALL_acquire, &lk);  // 拿不到就睡觉
syscall(SYSCALL_release, &lk);  // 释放并唤醒等待者

内核的实现思路：

  • 进入内核态（这时可以关中断了），用一个短暂的自旋锁保护锁的元数据。
  • 尝试获取目标锁。
  • 成功 → 返回用户态。
  • 失败 → 把当前线程标记为”不可执行”（睡眠），加入等待队列，调度其他线程。
  • 释放锁时，唤醒等待队列中的一个线程。

这样，等待锁的线程不消耗 CPU，让出来的时间片可以做其他有用的工作。

8.4 Futex：现代 Linux 的实现

实际生产中，Linux 用 futex（Fast Userspace muTEX） 实现这个机制，它有一个关键优化：fast path 完全在用户态完成。

  • 无竞争时（fast path）：用户态用 CAS 直接获取锁，零系统调用开销。
  • 有竞争时（slow path）：才陷入内核，调用 futex(FUTEX_WAIT, ...) 让线程睡眠。
  • 释放锁时检查是否有等待者，有的话才调用 futex(FUTEX_WAKE, ...)。

这样在常见的”很少冲突”场景下，几乎没有内核开销；只在真正冲突时才付出系统调用的代价。pthread_mutex 就是基于 futex 实现的。

推荐阅读：Ulrich Drepper 的《Futexes Are Tricky》——这篇文章的标题已经说明了一切，它的内容会让你彻底理解为什么”看起来简单”的并发原语在工程实现上有多少坑。

9. 三种锁的对比与定量评估

我们有了三种”锁”的实现：

实现方式用户/内核拿不到锁时适用场景
关中断仅内核——单核 OS 内核短临界区
自旋锁都可空转极短临界区、内核
互斥锁（futex）用户睡眠通用，临界区可长可短
单条原子指令用户不存在单变量更新

9.1 怎么严肃地比较性能

直接的对比实验思路：

  1. 固定总工作量：比如总共做 $N$ 次 sum++。
  2. 改变线程数：$T = 1, 2, 4, 8, 16$。
  3. 重复多次取均值并算误差：每个配置跑 5 次，画带 error bar 的图。
  4. 指标：单次 sum++ 的平均耗时。

预期看到的现象：

  • 单线程时，自旋锁最快（无系统调用），原子指令更快。
  • 多线程时，自旋锁性能急剧下降（缓存行竞争 + 空转）。
  • 互斥锁随线程数增加相对稳定。
  • 单条原子指令在所有场景都很快，但只能用于最简单的更新。

9.2 性能评估的“罪行”

推荐 Gernot Heiser 的《Systems Benchmarking Crimes》。常见的错误包括：

  • 没有控制变量
  • 只报告最好成绩，不报告分布
  • 不报告硬件配置
  • 用不公平的对比基准
  • 不做误差分析
  • 用不真实的工作负载

做并发性能测量时，这些坑随处可见。

10. 全局回顾：实现互斥的思想链

把整节课的逻辑梳理一遍：

  1. 问题：并发程序中，对共享数据的非原子访问会出错（sum++ 算不对）。
  2. 目标：找一个机制，让某段代码”看起来不被打断”。
  3. 最直接的方案：单核内核可以关中断。但用户程序不行，多核也不行。
  4. 想要 API：希望有 lock() / unlock()，使用者只管包住临界区。
  5. 天真的尝试：只用 load/store 实现锁（Peterson 算法）。在现代硬件上需要内存屏障，且性能差，方向错误。
  6. 正确方向：让硬件提供原子指令（lock cmpxchg、LR/SC 等）。
  7. 第一个工程方案：自旋锁。简单有效，但临界区长或线程被切换时性能崩溃。
  8. 更好的方案：让操作系统介入，拿不到锁时让出 CPU 去睡觉（futex）。
  9. 极致优化：fast path 在用户态完成，仅在冲突时陷入内核。

整个故事的核心思想是：先正确，再高效；硬件能解决的不要在软件里硬扛；操作系统的存在是为了把困难的事情封装成简单的 API。

##

Best Practice

  • 从一把大锁保平安开始。先正确，再优化。
  • 使用锁是程序员的责任，编译器不会帮你查。多写测试、多做压力测试。
  • 判断并发代码的正确性是计算困难的。不要相信”我看了一下觉得没问题”。
  • 加锁意味着串行。锁的粒度决定了并行度的上限。
  • 临界区越短越好。能不持锁做的事就不要持锁做（比如 I/O、内存分配）。
  • 现代 CPU 是弱内存模型。任何”看起来对的 lock-free 算法”如果没有屏障，几乎可以肯定是错的。
  • 不要重复发明轮子。futex、pthread mutex、std::mutex 已经踩过了所有的坑，自己实现一个对的非常困难。

总结

互斥的本质是限制并发，硬件的进步让限制的代价越来越小，但程序员永远要为正确使用它负责。

操作系统
笔记
This post is licensed under CC BY 4.0 by the author.

Trending Tags

笔记 随笔 插件