南京大学操作系统 (JYY) 学习笔记：并发控制与互斥锁的底层演进 (Mutual Exclusion)

Rain050415

740人浏览 · 2026-07-30 11:58:50

Rain050415 · 2026-07-30 11:58:50 发布

写在前面：这是本系列的第十四篇。

在上节课中，我们见识到了“并发”这头猛兽的威力：线程并发给了我们利用多核处理器的能力，但也彻底摧毁了程序状态迁移的确定性，带来了“极难编程”的挑战。连最简单的 1 + 1 都会算错，这代码还怎么写？

本讲内容：既然无法驾驭乱序的并发，我们的策略就是——阻止它！ 我们将探讨基础并发控制的核心概念：互斥 (Mutual Exclusion)，以及人类为了实现绝对安全的 lock/unlock，是如何从软件算法一路卷到硬件指令，最后由操作系统接管一切的。

在这里插入图片描述

入门：线程库与确定性的丧失

线程库回顾

spawn(fn): 创建共享内存的线程 (执行流、状态机)。
join(): 等待线程结束。

放弃：确定性 & 执行顺序 & 全局一致性

人类是 “Sequential Creatures” (顺序生物):
具备 $ A \rightarrow \dots \rightarrow B $ 简化为 $ A \rightarrow B $ 的直觉本能。编译器（甚至处理器这种“硬件编译器”）也是基于这种单线程的顺序假设来设计的。
多处理器彻底改变了“执行”的含义:
在并发世界里，任何 load 都可能读到（也可能读不到）其他线程刚刚写入（store）的值。连 1 + 1 都无法保证正确执行，这还怎么玩？

真的要放弃并发编程？？？

不要急。我们可以做一个类比映射：

线程 = 人： 大脑能完成局部存储和计算。
共享内存 = 物理世界： 物理世界天生就是并行的（多个人同时在一个房间里活动）。
程序 = 状态机： 物理世界其实也可以用状态迁移来严格建模。

互斥：阻止并发 (并行) 的发生

从最简单的问题入手

1 + 1，够简单了吧？

long sum = 0;

void T_sum() {
    sum++;
}

为了让这个简单的自增在多线程下绝对正确，我们希望有一个 API：无论怎么执行，sum** 的求和结果都是正确的。**
这就引入了互斥 (Mutual Exclusion)：互相排斥，阻止同时发生 sum++！

Stop the World (时间停止)

让硬件给我们提供一条“ザ・ワールド” (The World，时停) 指令行不行？

long sum = 0;

void T_sum() {
    stop_the_world();
    // 此时进入 ザ・ワールド 状态，全世界其他线程全被冻结
    sum++;
    resume_the_world();
}

这显然有些“Overkill” (杀鸡用牛刀)：

只要能声明“不能并发”的特定代码块就可以了。
其他（和 sum 无关的）代码还是应该允许同时执行的。
我们不需要让整个世界都停下来，而是只让访问相关寄存器/内存的代码排队。

互斥机制的诞生

lock();
sum++;
// 或者任意共享资源操作代码
unlock();

拟人视角：
用 lock/unlock 标记一个代码块。这就好比获得了一把钥匙：如果锁已经被别人占用，当前线程就会被阻塞（排队等待）；操作完成后 unlock，允许下一个人进入。
在任何时刻，只能有一个人拥有这把锁。所有被标记的代码块被称为临界区 (Critical Section)，它们之间是 “Mutually Exclusive” 的。
状态机视角：
加上锁之后，被标记代码块的执行，在宏观上就可以被理解为“一次原子的状态迁移”（不可分割的一步）。

不并发，还需要线程吗？

既然加了锁变成了排队串行，那我们还需要多核和多线程吗？

悲观的 Amdahl’s Law (阿姆达尔定律)

如果你有 $ 1/k $ 的代码是加锁不能并行的，那么无论你加多少个 CPU，你的最大加速比都存在理论上限：

$ T_\infty > \frac{T_1}{k} $

乐观的 Gustafson’s Law (古斯塔夫森定律)

随着计算规模的增大，并行计算的红利总是能覆盖串行的开销：

$ T_p < T_\infty + \frac{T_1}{p} $

(注：$ T_n $KaTeX parse error: Expected group after '_' at position 6: _ 代表 _̲$ n $_ 个处理器的运行时间)_

实际生活：许多计算是高度可并行的

经典物理的局部性原理： 物体对相邻物体的影响需要时间（即便在量子力学纠缠态严格来说不成立，但在宏观依然是极好的近似）。
推论： 任何物理世界的模拟皆可以大规模并行（$ T_\infty \ll T_1 $）。

Embarrassingly Parallel (尴尬的并行/完美并行) 例子：

图书馆管理 v.s. 分布式数据存储系统。
人类大脑 v.s. 深度神经网络矩阵乘法。
NP-Hard 问题的暴力穷举搜索。

软件方案的困境：使用共享内存实现互斥 (Spicy 🌶️)

早期计算机科学家试图只用软件（普通的 load/store）来实现互斥。

Dekker’s Algorithm 与 Peterson’s Algorithm

绕口令般的算法： “A process P can enter the critical section if the other does not want to enter, or it has indicated its desire to enter and has given the other process the turn.”

Peterson 协议的拟人比喻：
假设有三个变量：你的手（旗子）、他的手（旗子）、厕所门上的字条。

如果想进厕所：先举起自己的旗子，然后把写有对方名字的字条贴在门上。
持续观察模式：看看对方是否举旗？看看门上是不是自己的名字？

如果对方没举旗，或者门上的名字是自己，进入厕所；否则死循环继续观察。

出了厕所后：放下自己的旗子。

软件并发的极端危险

你很难从字面上判断这些并发算法到底对不对！
就像你无法用肉眼看出“n个线程循环m次，sum的最小值是多少”，哪怕是今天的顶级大模型也推导不出所有状态。

必须借助 Model Checker (模型检查器)！把代码转换成图，交给电脑去进行状态空间的穷举遍历。
电脑为什么叫“电脑”？因为它能替代人类机械的思维活动。

致命假设：编译器和 CPU 不会乱序

直接写一个 Peterson 算法在现代电脑上跑，绝对是错的！
因为这类算法做了一个现代 CPU 早已放弃的假设：

Load/store 指令是瞬间完成且对所有人立刻生效的。
指令是严格按照程序书写顺序执行的。

现代修复方案：
必须在关键位置强行插入屏障！

Compiler barrier (编译优化屏障): asm volatile("" ::: "memory");
Memory barrier (内存屏障): __sync_synchronize() (对应底层的 mfence, dmb ish, fence rw, rw 等指令，强制保证读写的先后和可见性)。

结论：智力体操不是我们想要的！ 我们需要的是 “Absolutely Correct” 的绝对安全的工程化方案。

降维打击：使用原子指令实现互斥

既然软件不好解决，那就让硬件来凑！

硬件协助：Stop-the-world 的小操作

我们能不能请求硬件提供一条绝对不会被打断的指令？

早期单核时代：cli (x86 清除中断标志) 或 csrci mstatus, 8 (RISC-V 关中断)。关了中断，系统就不会调度，代码自然互斥。
多核时代： 关中断没用了！我们需要真正的 原子指令 (ἄτομος / indivisible)。

硬件厂商在 CPU 指令集里提供了自带“魔法”的指令，能在一个不可分割的周期里同时完成 load + calc + store：

x86: lock 前缀 (如 lock cmpxchgl)。
RISC-V: LR/SC (Load-Reserved/Store-Conditional) 及 A 扩展。
ARM: ldxr/stxr。

自旋锁 (Spinlock)：API 与实现

有了原子指令（如 atomic_cmpxchg），我们终于可以写出绝对安全的锁了：

typedef struct {
    int status; // ✅ (0) 或 ❌ (1)
} lock_t;

void spin_lock(lock_t *lk) {
retry:
    // 如果 status 是 0，原子的把它变成 1，并进入临界区
    // 否则，疯狂死循环重试！
    if (!atomic_cmpxchg(&lk->status, 0, 1)) {
        goto retry;
    }
}

void spin_unlock(lock_t *lk) {
    lk->status = 0;
    __sync_synchronize(); // 确保释放锁之前的数据修改全部刷入内存
}

Caveat (警告)：lock/unlock 是万恶之源

从设计出这个 API 开始……人类就走上万劫不复的错误道路了。

因为 lock 和 unlock 都是程序员全权负责的！
程序员 100% 会花式犯错：忘记加锁、加了忘记解、在 if 里提早 return 忘了 unlock 导致全局死锁……
Linux 内核里至今仍有无穷无尽的这种 Bug。

// 不要笑，下面这个小丑 🤡 就是你自己！
T1: spin_lock(&l); sum++; spin_unlock(&l);
T2: spin_lock(&I); sum++; spin_unlock(&I); // 复制粘贴时字母小写 l 写成了大写 I

终极方案：使用系统调用实现互斥 (OS 来帮忙)

自旋锁的 Scalability (可扩展性) 灾难

Spinlock 在多核下简直是 Performance Bug：

性能灾难 1： “一核有难，八核围观”。拿不到锁的线程在其他 CPU 上疯狂空转，白白消耗 100% 的算力和电量。
性能灾难 2： 如果持有锁的线程被操作系统调度器切换下去了（或者发生了中断），此时所有空转等待的线程将面临无穷无尽的等待！

把上锁和解锁的操作交给 OS！

既然线程自己解决不了空转，那就求助操作系统内核：

syscall(SYSCALL_acquire, &lk);
试图获得锁。如果失败，OS 会直接把当前线程标为“睡眠”状态，切换去执行其他线程！ 绝不空转浪费 CPU。
syscall(SYSCALL_release, &lk);
释放锁，并告诉 OS：“我用完了，你可以去唤醒之前那些在睡觉等待的线程了。”

(注：自旋锁并没有被淘汰，在内核底层，自旋锁依然被用来保护极其短暂的不可被中断的数据结构，但普通的应用程序绝对不该用自旋锁)。

完美工程解：pthread Mutex Lock 与 Futex

pthread_mutex_t lock;
pthread_mutex_init(&lock, NULL);

pthread_mutex_lock(&lock);
pthread_mutex_unlock(&lock);

编程的时候，直接用 pthread_mutex 就可以了！
为什么它性能好？因为它底层采用了 Futex (Fast Userspace muTexes) 技术。

Futex：小孩子才做选择，我全都要！

性能优化的最常见技巧是优化 fast path。

Fast Path (快车道): 绝大部分时候锁其实是没竞争的。此时直接在用户态用一条原子指令抢锁，瞬间进入临界区，根本不需要陷入操作系统内核！
Slow Path (慢车道): 只有当发生争抢（原子指令失败）时，才触发极其昂贵的系统调用 futex_wait，让 OS 帮我把线程催眠排队。

Futex 极其复杂，连它的发明人 Ulrich Drepper 第一次用的时候都写出了 Bug。但对我们来说，直接调用封好的 API 享受它带来的极致性能即可。