第16讲 · 并发控制：信号量

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

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

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

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

引子：从「一个奇妙的想法」出发

(参考时间: 00:00)

上节课讲了同步：让异步的线程达到一个全局确定的状态（同步点），确立 happens-before。也给了条件变量这个万能模板：

lock(lk);
while (!cond) wait(cv, lk);
unlock(lk);
// 条件可能满足时：broadcast(cv);

这一讲，讲师要从零开始「发明」信号量——它比条件变量更「优雅」，代价是它只适合计数型资源。

一、发明信号量

1.1 一个奇妙的想法：用互斥锁实现同步

(参考时间: 00:03)

回忆计算图：$u \to v$ 表示 $v$ 的计算要在 $u$ 之后。要执行 $v$，得等所有前驱完成：

foreach (u -> v) while (!u_done) ;       // 或者
while (pred_done != n_pred) ;

一个聪明的想法：用互斥锁实现同步！

• 对每条边 $e: u \to v$ 放一把锁；
• 在 main 里先把所有的锁都 lock 掉（相当于管理员先把桌上所有的钥匙都没收了）；
• $T_u$ 做完：work(u); unlock(e);（做完任务，把钥匙放回桌上）；
• $T_v$ 开始：lock(e); work(v);（需要钥匙才能开始）。

关键洞察：release 和 acquire 天然实现了 happens-before——在一个线程 release、在另一个线程 acquire，就把一份「凭证」跨线程传递下去了。

编者拓展｜这其实是一个 UB hack：这个程序逻辑上正确，但互斥锁不允许这样做——pthread_mutex 要求 lock 和 unlock 在同一个线程（因为里面有 fast path 优化）。它是一个 undefined behavior。「今天我们会讲一个同步机制叫信号量，你就可以用它来做这件事。」

📷 cgraph-mutex 运行：node0 → 1/2/3 → 4/5
回到原视频 (00:11:00)

📷 cgraph-mutex：用互斥锁的「跨线程 release → acquire」实现计算图
回到原视频 (00:05:00)

1.2 为什么不能有多把钥匙？→ 信号量

(参考时间: 00:11)

既然「release = 在桌上放钥匙、acquire = 拿走钥匙」能实现同步，那为什么桌上不能同时有多把钥匙？

• Acquire：while (!(count > 0)) ; count--; —— 「拿走一把钥匙」「吃掉一个车位」；
• Release：count++; —— 「放回一把钥匙」「变出一个车位」。

现实中的类比：

• 停车场：有空位就能进，否则排队（「内部余位 2」）；
• 游泳馆：有手环（更衣柜）才能进，否则排队；
• 餐厅：有空桌就能坐，否则取号排队。

编者说明：1970 年代 Dijkstra 发明了 信号量（semaphore）——一个带计数器 count 的互斥锁。P（荷兰语 Prolaag = try + decrease）对应 acquire，V（Verhoog = increase）对应 release。用条件变量写出来就非常干净：

void P(sem_t *sem) {          // acquire
    mutex_lock(&sem->lk);
    while (!(sem->count > 0)) {
        cond_wait(&sem->cv, &sem->lk);
    }
    sem->count--;             // 消耗一个 token
    mutex_unlock(&sem->lk);
}

void V(sem_t *sem) {          // release
    mutex_lock(&sem->lk);
    sem->count++;             // 创建一个 token
    cond_broadcast(&sem->cv);
    mutex_unlock(&sem->lk);
}

初始的 count 相当于执行了 count 次 release（桌上有几把钥匙 / 停车场有几个车位）。每个 P 都能配一个 happens-before 的 V。

📷 停车场 / 游泳馆：计数型资源 → 信号量
回到原视频 (00:14:00)

📷 Semaphore API：P = 拿走一把钥匙，V = 放回一把钥匙
回到原视频 (00:17:00)

编者拓展｜信号量只管「入口」：P 通过意味着「我保证有一个车位」，但你具体停哪个车位，还需要别的机制和其他线程协商（比如再上一把互斥锁）。「P 就是停车场的闸门；你在停车场里干什么，它不负责任。」

二、用信号量实现同步

2.1 互斥锁 = 信号量的特例

(参考时间: 00:22)

sem_t sem = SEM_INIT(1);   // 只有一把钥匙 / 只有一个车位的停车场
void lock()   { P(&sem); }  // 拿走钥匙
void unlock() { V(&sem); }  // 放回钥匙

• 「互斥锁是信号量的特例，信号量是互斥锁的扩展。」（P/V 用条件变量写出来就一目了然。）

📷 `SEM_INIT(1)`：一个车位的停车场 = 互斥锁
回到原视频 (00:22:00)

• 反例：如果你的 unlock 调用了两次（bug），相当于变出了一个车位——从此两辆车都能进。

2.2 两种典型应用

(参考时间: 00:23)

（1）实现一次临时的 happens-before：A → B

• 信号量初始化为 0；
• A 做完：V(s)；B 开始：P(s)。这正是最初那个「用互斥锁实现同步」的想法。

（2）控制并发数 ≤ n（计数型资源）

• 游泳池里的人不能超过 n 个；停车场只有 n 个车位。「计数是个很有用的特性。」

2.3 线程 join 与计算图

(参考时间: 00:26)

线程 join：main 要等所有线程结束。

📷 join 的信号量实现：每线程一张桌子，或用一张桌子「数数」
回到原视频 (00:26:30)

• 为每条边计数：worker_t: V(done_t)；main: P(done_1); P(done_2); … P(done_n)；
• 为每个节点计数（更省空间）：所有 worker 都 V(done)，main P(done) 收 n 次。「收齐手环，关闭游泳馆。」

推广到任意计算图：

• 为每条边 $e: u \to v$ 计数：$T_u$ 做完 V(e)；$T_v$ 开始 P(e)；
• 为每个节点计数：$T_v$ 有 $k$ 条入边就先 P(v) $k$ 次，$T_u$ 做完 V(v)。

📷 join-sem：用计数型信号量等待正确数量的线程结束
回到原视频 (00:30:00)

📷 cgraph-sem：每个节点一个信号量，拿到和入边数量相同的钥匙才能计算
回到原视频 (00:33:00)

编者说明：讲师坦言，在计算图这个例子上，信号量比条件变量更好用——「条件变量的『同步条件』是个逻辑表达式，某种程度可以验证；但信号量要借助拟人化的『桌子/钥匙/人』来理解。」在解决计数型资源的问题上，信号量是非常推荐的用法。

三、Killer Application：生产者-消费者

(参考时间: 00:34)

信号量最优雅的应用，是生产者-消费者——只要两个信号量：

sem_t empty = SEM_INIT(depth);   // 初始有 depth 个「空位」
sem_t fill  = SEM_INIT(0);       // 初始没有「数据」

void T_produce() { P(&empty); printf("("); V(&fill); }
void T_consume() { P(&fill);  printf(")"); V(&empty); }

「极为对称、极为优雅」：想象有两张桌子 empty 和 fill：

• empty 桌上的每个玩具 = 缓冲区的一个空位；fill 桌上的每个玩具 = 一个已写入的数据；
• Producer：从 empty 拿一个球 → 生产（打印 (）→ 往 fill 放一个球；
• Consumer：从 fill 拿一个球 → 消费（打印 )）→ 往 empty 放一个球。

全局不变式：empty + fill + P_hold + C_hold = depth。通过 V → P 的配对，保证「生产 happens-before 消费」。

📷 pc-sem：两个信号量 empty/fill，对称而优雅
回到原视频 (00:35:30)

📷 运行结果：不同 buffer size 下括号深度受控
回到原视频 (00:43:30)

编者拓展｜别忘了互斥：printf 是线程安全的，但你自己实现的数据结构还需要互斥。信号量给的是「入口」，缓冲区内部的并发访问仍要自己保护好。

对比条件变量版本：上节课我们用 while(!cond) wait + broadcast，代码更啰嗦；而信号量版一看就对称、优雅。所以「遇到生产者-消费者，完全可以 follow 这个 pattern 用信号量实现」。

四、信号量 vs 条件变量

4.1 单信号量表达不了「或」

(参考时间: 00:44)

回到上节课的「鱼」问题（三类线程打印 <、>、_，组成 <><_ / ><>_）：同步的条件里有一个「或」——打印完 _ 后，可以打印 < 或 >。

• 信号量必须等待「一个计数器」，很难表达「或」（也不是不行：打印完 _ 后抛硬币决定 V 哪个信号量）；
• 条件变量可以是「任意全局状态的条件」，天然支持。

4.2 哲学家吃饭问题（Dijkstra, 1960）

(参考时间: 00:48)

5 个哲学家（线程）围坐，吃饭需要同时拿到左手和右手的两把叉子。

条件变量版（背模板即可）：同步条件 = avail[lhs] && avail[rhs]，拿两把叉子 → assert + 置零 + 吃完放回 + broadcast。「期末考试 100% 会考，这就是通关密码。」

信号量版（naive）：P(&sem[lhs]); P(&sem[rhs]); —— 看起来没问题，但当 5 个人同时举起左手叉子时，谁都在等右手，循环等待 → 死锁。

📷 哲学家吃饭：naive 信号量版（各拿左手叉子 → 死锁）
回到原视频 (00:49:00)

📷 运行日志：所有人拿了左手就卡住，系统陷入死锁
回到原视频 (00:58:30)

两种修复（但都不通用）：

• 从桌上赶走一个人：再加一个 table 信号量 SEM_INIT(N-1)——最多 4 人上桌，5 把叉子中必有 1 人能拿两把；
• Lock Ordering：给叉子编号，总是先拿编号小的（打破对称性）。

📷 修复一：table 信号量限制最多 N-1 人上桌
回到原视频 (01:00:30)

编者拓展｜为什么说「这不成功」：这两种修复的正确性「不写在程序里」——它依赖一个额外的证明/说明（「从桌上赶走一个人」是通过一个巧妙的不变式保证的）。Systems 要的是 absolutely correct 的方案：如果你用一个数值型资源表达不了同步条件，就要果断放弃信号量。

更麻烦的是「加强版生产者-消费者」：再加 close() / open() 两种线程，信号量就很难表达「not closing」这种二选一的语义；而条件变量只要在全局状态里加一个变量即可。

4.3 用信号量实现条件变量：surprisingly tricky

(参考时间: 01:06)

反过来，用信号量实现条件变量非常棘手（有一篇 2003 年的 report 专门讲 Implementing CVs）。一个「看起来符合逻辑」的实现：

void wait(cond_t *cv, mutex_t *mutex) {
    cv->nwait++;
    mutex_unlock(mutex);
    P(&cv->sleep);      // ⚠️ 这里出问题
    mutex_lock(mutex);
}
void broadcast(cond_t *cv) {
    mutex_lock(&cv->lock);
    for (int i = 0; i < cv->nwait; i++) V(&cv->sleep);
    cv->nwait = 0;
    mutex_unlock(&cv->lock);
}

问题：唤醒丢失（lost wakeup）——nwait++ 和 P 之间不原子：一个「早就 nwait++ 但还没 P」的线程抢走了一次唤醒，导致后面少唤醒一个线程，系统就错了。

编者拓展｜release-wait 必须是一个原子操作：这一点无法用普通信号量解决，只能求助于操作系统——实际实现靠的是 futex。「并发就是很绕——你唯一的办法就是试过所有的可能性（NP 完全），既然有『不需要试所有可能性』的条件变量这种万能的同步方法，那你为什么不先用它呢？」

📷 用信号量实现条件变量：nwait++ 与 P 之间不原子 → 唤醒丢失
回到原视频 (01:13:00)

五、把任何同步问题变成生产者-消费者：waiter

(参考时间: 01:17)

还有一种通用的方法：引入一个调度线程（waiter / 服务员）。

• 服务员持有全部 5 把叉子，是唯一能直接访问全局状态的线程；
• 任何哲学家想吃饭，就给服务员发一条消息（消息队列 = 缓冲区，就是生产者-消费者：「send = 往 buffer 放球，receive = 取球」）；
• 服务员是串行的——它按固定顺序处理消息，逻辑简单（查一下叉子在不在）。
• 好处：服务员可以做公平性、负载均衡等策略（谁被漏了多少次就延迟一会儿）；「只要你任务分解得好，对性能的损失几乎可以忽略」（一次判断是 O(1) 的几纳秒，而吃一顿饭要几十毫秒）。

void T_philosopher(int tid) {
    while (1) {
        send_message_to_waiter();     // 生产者：往消息队列放球
        P(&can_proceed[tid]);         // 消费者：等服务员答复
    }
}

📷 把任何同步问题变成生产者-消费者：由 waiter 串行管理全局状态
回到原视频 (01:19:00)

编者说明：这是「你不需要让每个线程自行 ADD hack 地 self-organize」的另一种思路——引入一个集中式的管理者，把指数多的调度可能性，压缩成一个串行、可见、可验证的逻辑。

总结

• 从「跨线程 release → acquire」的奇妙想法出发，把互斥锁扩展成「有多把钥匙」，就发明了信号量：一个带计数器的互斥锁。
• P（acquire） = while(!(count>0)) ; count--;（拿走钥匙/吃掉车位）；V（release） = count++（放回钥匙/变出车位）。
• 互斥锁是信号量的特例（SEM_INIT(1)）；信号量有两种典型应用：一次临时的 happens-before（A→B） 和 控制并发数 ≤ n。
• 信号量适合计数型资源：线程 join、计算图、以及优雅的生产者-消费者（empty/fill 两个信号量，全局不变式 empty+fill+hold=depth）。
• 信号量不是万能的：单信号量表达不了「或」（鱼问题）；哲学家吃饭用 naive 信号量会死锁，两种修复（赶走一人 / lock ordering）正确性不写在程序里；close/open 这类二选一语义很难表达。
• 用信号量实现条件变量 surprisingly tricky（唤醒丢失），release-wait 的原子性只能靠 futex——所以：能用条件变量就用条件变量。
• 万能兜底：引入 waiter（调度线程），把任何同步问题变成生产者-消费者——串行逻辑简单、可验证，还顺带能做公平性与负载均衡。
• 核心方法论：想清楚「同步的条件是什么」；先写绝对正确的简单方案，性能问题后面再针对性优化（任务分解得好，同步开销可忽略）。

附：官方参考与延伸阅读

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

阅读材料：教科书 Operating Systems: Three Easy Pieces 第 31 章（Semaphores）。

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