第15讲 · 并发控制：同步与条件变量

2026 南京大学《操作系统原理》第十五讲 · 课堂实录重构

对应讲次：第15讲（南京大学 操作系统原理）

制作模型：deepseek-flash（coding-agent / pi；据 ~/.pi/agent/settings.json）

编者说明：本书由课堂录像的语音字幕重构而成，术语、章节骨架与参考链接已按课程官方讲义（lect15.md）校准。讲师的口语风格、类比与案例被尽量保留；编辑性的补充一律以「编者说明」或「编者拓展」标出。

引子：互斥没能解决的问题

(参考时间: 00:00)

上节课的互斥锁解决了 A/B 的先后（要么先 A 后 B、要么先 B 后 A）——它能实现并发数据结构、多处理器上的 malloc/free。但它没有解决：

如果我们要求一定 A 先、B 后（A → B），怎么办？

典型的例子就是 join：spawn 了 T1、T2、…，主线程要等所有线程结束再打印 sum——「上锁这件事是办不到的，因为两个线程一起往前执行，谁先到谁就把钥匙拿走了」。

今天要讲的是并发控制里最重要的部分——同步。「你只要学会了同步，99% 的现实问题都能在这里找到答案。今天听完这节课，你理论上就可以写任何并发程序了。」

📷 互斥解决了 A/B，但没解决 A → B（例如 `join`）
回到原视频 (00:01:00)

一、什么是同步

1.1 异步 vs 同步

(参考时间: 00:03)

把线程想象成人、把共享内存想象成物理空间：人是各管各的（异步/asynchronous）——点好外卖就不管了，送到了会有通知。

同步（synchronization）：「两个或两个以上随时间变化的量在变化过程中保持一定的相对关系。」

物理世界有各种同步机制：

• 同步电机：磁锁定；同步电路：时钟信号（时钟上升沿锁存寄存器）；
• 我们：约定 wall-clock time 10:10 上课（用物理时间同步）；
• 还有反人类的夏时制（中国也实行过！）。

在现实世界中，我们经常期望「同时发生」——比如乐团演奏，超过 20–30 ms 的不齐就能被察觉到。但对计算机来说，20–30 ms 已经能执行上亿条指令了。

那计算机怎么放音乐不断呢？ 不是靠精确时间，而是靠缓冲区：先填好未来 20–30 ms 的音频，用实时性强的硬件设备播放，只要每个 20 ms 内能填上下一个 20 ms，就听不出断续。

📷 吕指导与乐团：超过 20–30ms 的不齐人耳就能察觉
回到原视频 (00:07:00)

1.2 用代码表示「等待」

(参考时间: 00:10)

各种同步场景，用代码表示都是一个「等待」：

它们的共性是：等到某一个条件发生，然后继续分叉执行；如果现在条件不发生，一定有一个操作使它发生。而这个「握手」的瞬间，就有了一个全局同步的状态（同步点）——在同步点上，你可以 assert 一个条件；它确立了一种 happens-before 关系。

📷 用代码表示同步：while (!cond); 的等待模式
回到原视频 (00:10:30)

1.3 现场演示：实现一个同步的乐团

(参考时间: 00:16)

讲师用 fplay（调外部的 ffmpeg 工具播声音）实现了一个「同步乐团」：指挥（conductor）按回车放出这一拍，多个演奏线程（player）等待这一拍再演奏。

但直接写代码要小心——共享变量的访问一定要用 mutex 保护好（还记得 sum++ 的教训吗）：

do {
    mutex_lock(&lk);
    can_proceed = check_condition();
    mutex_unlock(&lk);
} while (!can_proceed);
assert(can_proceed);

这个乐团演示是正确的，但它很浪费：线程为了等这一拍，不停地在观察指挥的状态（盲等/spin），把 CPU 白白烧掉。「你可能要等几天，用几天时间浪费 CPU cycles，当然没有必要。」

📷 同步乐团演示：指挥按下回车，演奏线程才开始
回到原视频 (00:21:00)

二、条件变量：万能的同步方法

2.1 从 spin 到 cond_wait

(参考时间: 00:25)

既然等待都是这个「检查条件」的循环模式，那就让操作系统/库函数提供一个 API：条件不满足时把线程放到睡眠状态，条件满足时唤醒它——这就是条件变量（condition variable）。

mutex_lock(&lk);
while (!check_condition()) {   // 条件不成立就等
    cond_wait(&cv, &lk);       // 等待，并自动释放 lk；被唤醒时重新获得 lk
}
mutex_unlock(&lk);

• cond_wait(&cv, &lk) 做两件事：释放锁 + 立即进入等待睡眠——这两件事是「瞬间同时完成」的原子操作（操作系统保证不被打断）；
• 唤醒用 cond_signal(&cv)（唤醒一个）或 cond_broadcast(&cv)（唤醒所有等待者）。

编者拓展｜为什么必须带锁？ 因为你检查条件时如果不带锁，刚检查完条件就可能变了（还记得「山寨支付宝」的例子吗？）。条件变量的 API 强制你先上一把锁，再检查条件。

📷 cond_wait：释放锁与进入睡眠是原子的两步
回到原视频 (00:27:00)

2.2 万能同步的模板（「期末 20 分」）

(参考时间: 00:31)

讲师把这个模板称为「期末考试值 20 分的代码」：

// 线程 1（生产者/条件满足方）
mutex_lock(&lk);
// 修改可能使 sync_cond() 成立的共享状态
cond_broadcast(&cv);     // 唤醒等待的线程
mutex_unlock(&lk);       // Release

// 线程 2（等待方）
mutex_lock(&lk);         // Acquire
while (!sync_cond()) {   // 条件不成立时进入等待
    cond_wait(&cv, &lk); // 等待并自动释放 lk；被唤醒时重新获得 lk
}
// ... 执行后续操作
mutex_unlock(&lk);

三个关键点：

1. 一定是 while，不是 if——被唤醒后必须重新检查条件（可能被「不该唤醒」的信号唤醒，或条件被别人抢走了）；
2. 同步条件想清楚：sync_cond() 是什么；
3. 只要条件可能被满足，就上锁后 broadcast——这绝对安全。

while 退出时，你能同时保证：条件成立 且 你持有锁——于是你得到了一个「持有锁 + 全局同步状态」的可理解状态，可以 assert。

编者说明：可以说，条件变量就是「一个高效版的 spin loop」：条件不满足时可以去睡眠，而不是空转。

📷 条件变量模板：lock + while(!cond) wait + assert + broadcast + unlock
回到原视频 (00:32:00)

三、经典同步问题：生产者-消费者

(参考时间: 00:38)

这是最重要的问题——「你只要掌握这一个模型，基本上就可以解决 99% 的实际并发问题。」它也叫 Master-Slave（现在政治不正确，改叫 scheduler-worker） 模式。

• Producer：生产数据（放一个「苹果」到桌上/缓冲区）；缓冲区有空位就放，否则等待；
• Consumer：消费数据（拿走苹果）；缓冲区有数据就拿，否则等待。
• 同步：同一个 object 的生产必须 happens-before 消费。

简化描述：只用打印括号——Producer 打印 (、Consumer 打印 )，「深度」不能超过 buffer size $n$：

• $n=3$，((())())((( ✅；(((())))、(())) ❌。

只需回答一个问题：什么时候可以 produce / consume？

// Producer
mutex_lock(&lk);
while (!(depth < n)) { cond_wait(&cv, &lk); }
assert(depth < n);
depth++;
printf("(");              // put object to queue
cond_broadcast(&cv);
mutex_unlock(&lk);

// Consumer
mutex_lock(&lk);
while (!(depth > 0)) { cond_wait(&cv, &lk); }
assert(depth > 0);
depth--;
printf(")");              // pop object from queue
cond_broadcast(&cv);
mutex_unlock(&lk);

📷 生产者-消费者：括号序列 ( = push，) = pop
回到原视频 (00:42:00)

📷 运行结果：一放一拿（buffer size 决定并发深度）
回到原视频 (00:47:00)

编者拓展｜signal vs broadcast 的坑：一个「看起来正确」的版本把 broadcast 改成 signal——单独一对 producer/consumer 时它看起来是对的，但两对线程 + 桌上有两个空位时，输出明显错了。原因还包括把 while 写成了 if。

讲师的忠告：「不要相信你的眼睛」。写一个 check.py（读到 ( 就 +1、读到 ) 就 −1，检查任意时刻深度合法），让它长时间运行，用来验证程序正确性。while + broadcast 这两个「绝对安全」的组合起来，就可以实现任何同步。

📷 check.py：用另一个程序检查括号序列的合法性
回到原视频 (00:49:00)

四、奇怪的同步问题（万能方法的威力）

(参考时间: 00:51)

条件变量的「万能」体现在：再奇怪的同步条件，只要你把它写清楚，就能解。讲师举了两个例子：

1. H₂O（LeetCode 原题）：若干「释放 H 原子」「释放 O 原子」的线程，要拼出水分子；
2. 「鱼」：三种线程分别死循环打印 <、>、_，要求屏幕上看到的总是 <><_ 或 ><>_ 的组合（组成一条朝左或朝右的鱼）。

解法：画出状态机（A→B→C→D 朝左，A→E→F→D 朝右，D→A 回到起点）。然后回答三个问题：当前能打 < / > / _ 的条件是什么？——只要当前状态的下一个字符是我，且没有别人在打印，我就能打。

// 任何字符打印前：
mutex_lock(&lk);
while (!(next_char_of(cur_state) == my_char && printer == 0)) {
    cond_wait(&cv, &lk);
}
printer++;            // 占用打印权
mutex_unlock(&lk);

// 打印 my_char ...

mutex_lock(&lk);
printer--;
cur_state = next_state(cur_state);
cond_broadcast(&cv);
mutex_unlock(&lk);

📷 「鱼」同步问题：用状态机表达同步条件
回到原视频 (00:53:30)

📷 fish.c：用状态机表达同步条件（`can_print` / `next`）
回到原视频 (00:57:30)

编者说明：讲师强调——「我们不希望大家去做无厘头的智力题」，这些例子只是为了让大家理解「同步是怎么实现的」。真实并发编程里，大部分时候用的是生产者-消费者和计算图。

五、计算图：理解并行计算的通用模型

(参考时间: 00:58)

计算图是一个有向无环图（DAG） $G(V, E)$：

• 节点 $V$ 上放计算任务（可以访问共享内存）；
• 边 $(u, v)$ 表示 $v$ 的计算要用到 $u$ 产生的值——即一条 happens-before 关系；
• $v$ 开始时，必须能看到 $u$ 对共享内存的所有修改。

「几乎我们总是用这个视角去理解并行计算。」只要每个节点独立计算时间足够长，管理计算图的开销就忽略不计，算法就可高效并行。而且计算图可以是动态的（一边计算一边产生新节点，计算图本身就是共享内存里的数据结构）。

无处不在的计算图：

• 神经网络：PyTorch autograd / FX Graph；下一层依赖上一层的激活；
• Makefile：Makefile 本质是一个 DAG（有环会报错），GNU Make 能自动并行化（make -j4 / -j16）；
• 动态规划：Longest Common Subsequence 的二维网格依赖图；
• 电路模拟：Verilator 支持 partition 与并行仿真。

📷 PyTorch 的 FX Graph：一个有向无环的计算图
回到原视频 (01:01:00)

📷 LCS 动态规划的二维网格依赖图
回到原视频 (01:05:00)

5.1 实现任意计算图：两种方法

(参考时间: 01:07)

方法（1）：为每个节点分配一个线程 + 条件变量

void T_u() {   // u -> v
    ...  // u 的计算
    mutex_lock(v->lock);
    v->n_done++;
    cond_signal(v->cv);      // 这里可以 signal（每个节点独立条件变量）
    mutex_unlock(v->lock);
}

void T_v() {
    mutex_lock(v->lock);
    while (!(v->n_done == v->n_predecessors)) {   // 条件：所有前驱都完成
        cond_wait(v->cv, v->lock);
    }
    mutex_unlock(v->lock);
    ...  // v 的计算
}

方法（2）：Executor Pool（生产者-消费者 / 调度器-工作线程）

• 一个 scheduler（生产者）+ 许多 worker（消费者）；
• worker 的条件是「队列不空」；做完一个任务后，自己又变成生产者——把被激活的任务放回队列。

mutex_lock(&lk);
while (!(all_done || has_job(tid))) {
    cond_wait(&worker_cv[tid], &lk);
}
mutex_unlock(&lk);
if (all_done) break; else process_job(tid);
cond_signal(&sched_cv);

📷 Executor Pool / 计算图实现：少量 worker 线程 + 任务队列
回到原视频 (01:11:00)

编者拓展｜为什么用 Executor Pool？ 如果为几百万个节点各创建一个线程，线程创建本身的开销就得不偿失。用少量线程 + 队列（生产者-消费者），就能在少量 CPU 上跑大图。「生产 happens-before 消费」在这里再次出现。

重要优化：不需要整段代码都上锁——通常只需要在「从队列取出任务/更新依赖关系」的一小段上锁；如果任务持有的内存只有自己能访问（没有 data race），那大段计算可以放心地不上锁，从而真正利用多处理器。

📷 cgraph：node0 先执行，然后 1/2/3 并行，最后 4/5
回到原视频 (01:14:30)

编者说明：讲义还提到一种「为每条边分配一把锁」的写法（acquire(u->v) / release），虽然能跑，但是 pthread mutex 不允许的 undefined behavior——不要这么玩。

总结

• 同步 vs 异步：线程天生异步（各管各的）；同步是「两个或多个量保持一定的相对关系」，其实现是握手，握手瞬间产生一个全局同步点，确立 happens-before。
• 等待的通用形态：while (!cond) { ... }——但spin 会浪费 CPU。
• 条件变量（cond_wait / signal / broadcast）是万能的同步原语，它给出一段「高效版的 spin loop」：
• cond_wait：原子地「释放锁 + 睡眠」；
• 被唤醒时重新获得锁；
• 一定用 while（被唤醒后重新检查条件）；
• broadcast 绝对安全——只要条件可能被满足，就广播。
• 生产者-消费者是经典模型（99% 的实际并发问题都能用它建模）：想清楚「什么时候能 produce / consume」，然后照抄模板。
• 奇怪的同步问题（H₂O / 鱼）：用状态机表达同步条件，条件变量照样能解。
• 计算图（DAG）是理解并行计算的通用框架：节点计算、边是 happens-before；两种实现——每节点一线程+条件变量，或 Executor Pool（调度器-工作线程）。
• 核心方法论：想清楚「同步的条件是什么」，剩下的照抄模板；先写一个绝对正确的版本，不要为了一点点性能搬石头砸自己的脚。

附：官方参考与延伸阅读

本讲的讲义见课程主页，以下链接按书中出现顺序整理：

阅读材料：教科书 Operating Systems: Three Easy Pieces 第 30 章（Condition Variables）。

版权说明：本讲讲义与幻灯片作者为蒋炎岩，采用 Creative Commons BY-NC 4.0 许可，来源于 https://jyywiki.cn/OS/2026/。视频画面与字幕版权归原作者所有。本书为课堂内容的学习性重构。