Appearance
信号量
2026 大纲 二（三）4 信号量。
忙等的问题，只能靠一个能让进程睡过去的东西解决
上两节留下一个共同的天花板：Peterson、TSL、Swap 全是忙等。 拿不到就一直转，把时间片白白烧掉。
上一节的互斥锁给出了方向——让不出处理机就睡过去。 但它还有一个更大的局限：锁只能表达互斥，表达不了同步。
"互斥"说的是"这份资源同一时刻只能一个人用"； "同步"说的是"甲做完了某件事，乙才能继续"。 后者用锁做不到，因为锁有所有权——加锁和解锁必须是同一个进程， 而同步恰恰要求"甲来通知、乙来接收"。
信号量把这两件事统一了。 它就是一个整数加一对原子操作 P（申请）和 V（释放）， 而这个整数的含义是"这种资源现在还剩几份"。
于是三种用法的初值，全都从同一句话推出来——一开始有几份可用：
互斥用初值 1（这份资源一开始空着，一个人能进）； 同步用初值 0（"甲做完了"这件事一开始还没发生，所以一份都没有）； 资源信号量用初值
同步的写法也由此固定成一句口诀：「前 V 后 P」—— 做完那件事的人执行 V（我做完了，给你一份），等的人执行 P（我来领）。
⚠️ 还有一条最贵的规矩要先立住：需要多个 P 时，互斥的那个 P 必须放在最后。 否则就是"抱着锁去等资源"，而能给你资源的人进不来——当场死锁。
一、整型信号量：仍然是忙等
1965 年 Dijkstra 最初把信号量定义为一个表示资源数目的整型量 S，除初始化外只能通过两个标准的原子操作访问：
wait(S) {
while (S <= 0) ; /* 忙等，什么也不做 */
S--;
}
signal(S) {
S++;
}这两个操作长期被分别称为 P 操作（wait / proberen / 申请）与 V 操作（signal / verhogen / 释放）。它把"判断资源够不够"和"占用一份资源"包进一个原子操作里，缝隙没了、互斥可靠；但 wait 里只要 S <= 0 就不断地测试，教材的判定是该机制并未遵循"让权等待"准则，而是使进程处于忙等状态。
这一步是全章的枢纽
从同步互斥实现方法到这里，所有方案都倒在让权等待上，根因始终是同一个：没有"把自己挂起来"的手段。记录型信号量之所以能翻篇，正是因为它把 block()／wakeup() 这两个操作系统原语接了进来。
二、记录型信号量：接入 block/wakeup
要让等待者放弃处理机，就得有地方记住"谁在等"，于是在整型量之外增加一个进程链表：
c
typedef struct {
int value; // 代表资源数目
struct process_control_block *list; // 等待该资源的进程链表
} semaphore;P(S) {
S.value--;
if (S.value < 0) {
block(S.list); // 自我阻塞，放弃处理机，挂入 S.list
}
}
V(S) {
S.value++;
if (S.value <= 0) {
wakeup(S.list); // 唤醒 S.list 中的第一个等待进程
}
}P/V 六行代码逐句读出的语义：减到负数、加完仍 ≤ 0 各代表什么（想把这段练到能自己复述时展开）
| 代码 | 含义 | 为什么 |
|---|---|---|
S.value-- | 请求一个单位的该类资源 | 可分配数减一 |
if (S.value < 0) | 减完变成负数 ⇒ 资源已分配完毕 | 若还有富余，减完不会小于 0 |
block(S.list) | 自我阻塞、放弃处理机、挂进链表 | 这一句就是"让权等待"的全部内容 |
S.value++ | 释放一个单位资源 | 可分配数加一 |
if (S.value <= 0) | 加完仍 ≤ 0 ⇒ 链表里还有等待者 | 加完还不为正，说明之前欠着的不止这一个 |
wakeup(S.list) | 唤醒队首等待者 | 释放的资源要交给它 |
三、互斥、同步与前驱关系
// 互斥：mutex 初值 1
semaphore mutex = 1;
P(mutex); 临界区; V(mutex); // 两个进程都这么写
// 同步：让 P1 的 A 在 P2 的 B 之前执行，S 初值 0
semaphore S = 0;
// 进程 P1 // 进程 P2
操作 A; P(S); ← 等 A 完成
V(S); 操作 B;S 初值为 0，因此 P2 若先执行必定阻塞；只有 P1 执行完 A; V(S); 把 S 增为 1 后，P2 才能成功执行 B。
前驱关系图是一张有向无环图，节点是语句（或程序段），边表示"必须先做完起点才能做终点"。套"每条边配一个初值 0 的信号量、起点之后 V、终点之前 P"这条通法，每个节点的代码形如：
所有入边的 P； 该节点的语句； 所有出边的 V；通法在一张六条边的图上的完整走法：数边、列入出度、誊写、自检（想把通法练到不用想时展开）
设有五个程序段 A、B、C、D、E，前驱关系是：A→B、A→C、B→D、C→D、C→E、D→E。
第 1 步：数边，定信号量个数与初值。 边有 6 条：AB、AC、BD、CD、CE、DE ⇒ 6 个信号量，全部初值 0。初值 0 的含义是"这件事还没发生"，前驱关系表达的正是"某件事发生过没有"。
第 2 步：列每个节点的入度与出度。 这一步决定每段代码里 P 和 V 各写几个：入度决定"等几件事"，出度决定"通知几个人"。
| 节点 | 入边（→ P 的个数） | 出边（→ V 的个数） |
|---|---|---|
| A | 无（入度 0） | AB, AC（出度 2） |
| B | AB（1） | BD（1） |
| C | AC（1） | CD, CE（2） |
| D | BD, CD（2） | DE（1） |
| E | CE, DE（2） | 无（出度 0） |
第 3 步：誊写。 这一步不再需要思考。
semaphore s_AB = 0, s_AC = 0, s_BD = 0, s_CD = 0, s_CE = 0, s_DE = 0;
P_A() { A; V(s_AB); V(s_AC); }
P_B() { P(s_AB); B; V(s_BD); }
P_C() { P(s_AC); C; V(s_CD); V(s_CE); }
P_D() { P(s_BD); P(s_CD); D; V(s_DE); }
P_E() { P(s_CE); P(s_DE); E; }
main() {
cobegin P_A(); P_B(); P_C(); P_D(); P_E(); coend
}第 4 步：自检三条。 ① 每个信号量恰好被 V 一次、被 P 一次（6 个信号量各出现两次）；② 每个节点前面的 P 个数等于入度；③ 入度为 0 的 A 前面没有 P，出度为 0 的 E 后面没有 V。三条都对。
第 5 步：验证。 把这五个进程的所有交错穷举一遍（共 7 个可达状态）：能全部完成的终态 1 个、中途卡死 0 个、违反拓扑序 0 个——无论调度器怎么排，执行顺序一定满足 A 在 B/C 之前、B/C 在 D 之前、C 与 D 在 E 之前，且不会死锁。
四、AND 型信号量与信号量集
前面的讨论都假定进程一次只争一个临界资源。一个进程需要同时拿到两个以上资源时，逐个 P 会出问题，教材给的反例很干净：进程 A 与 B 都要访问共享数据 D 和 E，分别用 Dmutex、Emutex 保护（初值都是 1），但两人 P 的顺序相反：
process A: process B:
wait(Dmutex); wait(Emutex); // A 拿到 D，B 拿到 E
wait(Emutex); wait(Dmutex); // A 等 E，B 等 D交替执行时：Dmutex = 0 → Emutex = 0 → Emutex = -1（A 阻塞）→ Dmutex = -1（B 阻塞），已进入死锁状态。教材紧接着点明规律：进程同时要求的共享资源愈多，发生死锁的可能性也就愈大。
AND 型信号量把若干个资源的分配变成一个原子动作——要么把请求的资源全部分配，要么一个也不分配：
Swait(S1, S2, ..., Sn) // 全部 Si >= 1 才一起减 1，否则一个都不减，进程在第一个不足的 Si 上等待
Ssignal(S1, S2, ..., Sn) // 全部加 1，并把各队列上的等待进程移入就绪队列它消灭的是"持有一部分、再去请求另一部分"这个中间状态，也就是死锁四个必要条件里的请求并保持。哲学家进餐问题的"用 mutex 包住两次 P"走的是同一条思路。
信号量集在 AND 型的基础上加了两个参数：测试下限值
三个特例把前面所有形态统一了起来：
| 写法 | 含义 |
|---|---|
Swait(S, d, d) | 集合中只有一个信号量，每次申请 d 个；现有资源少于 d 时不予分配 |
Swait(S, 1, 1) | 蜕化为普通的记录型信号量（S > 1 时）或互斥信号量（S = 1 时） |
🔴 Swait(S, 1, 0) | 可控开关：d = 0 意味着只测试不占用，S ≥ 1 时可放多个进程进入某特定区，S 变为 0 后阻止任何进程进入——这是前面任何一种信号量都表达不了的语义 |
五、设计信号量方案的五步
同步场景看着千变万化，拆解流程是固定的。后面几个经典问题（生产者-消费者、读者-写者、哲学家进餐）都按这五步走：
- 找出各类进程和各类资源 —— 先理清有几"类"进程（生产者/消费者、读者/写者……）、几"类"资源（缓冲区、打印机……），别把同一类的当成不同的
- 分析进程之间的同步、互斥关系 —— 谁和谁互斥（抢同一临界资源）、谁必须等谁先做（同步/前驱），顺带想清楚哪种交错会导致死锁
- 定义信号量并确定初值 —— 一个关系配一个信号量：互斥初值 1，同步初值 0，资源信号量初值为资源个数
- 写出伪代码 —— 进临界区前 P、出临界区后 V；等事件的一方 P、做完事件的一方 V
- 回头检查 —— P/V 是否成对？多个 P 的先后顺序会不会死锁？是否覆盖了第 2 步列出的全部关系？
考点速记
- 发展链：整型 → 记录型 → AND 型 → 信号量集。 ⚠️整型与记录型的分界只在等不到时执行
while还是block——满足让权等待靠的是block原语，而不是那条等待链表。 - ⚠️**
S.value为负时，其绝对值就是等待进程数（仅记录型成立）。S.value为正时，它是还剩几份可用资源。** - 三种初值都从"一开始有几份该资源可用"推出：互斥用 1、同步用 0、资源信号量用资源个数。
- ⚠️同步是「前 V 后 P」：做完事的人
V，等的人P。 - ⚠️P/V 必须成对；需要多个 P 时，互斥的 P 必须放最后——否则抱着锁等资源，死锁。V 的顺序无约束。
- 前驱关系通法：每条边配一个初值 0 的信号量，起点之后 V、终点之前 P。由此得到三个计数关系——信号量个数
边数、每个结点 P 的个数 入度、V 的个数 出度。正确性来自图无环。 - 需要同时持有多个资源时改用
Swait（AND 型信号量），把多次申请合成一个原子动作，从根上消灭"请求并保持"条件。 - 由信号量当前值反推操作次数：设初值
、当前值 ，则 V的次数P的次数。若同时给出"有几个进程在等待"，等待数就是 （ 时）。
这一节在真题里被考过的形式：
信号量是 process 章大题最集中的一节——近年几乎年年一道 PV 大题。 但问法只有三类，而且各有固定套路。
- ① 由信号量的值反推 P/V 次数或阻塞进程数（2010-25、2026-26）。2010-25：初值 3、当前值 1，问已完成的 P 与 V 次数关系——用速记第八条
，即 P 比 V 多 2 次。2026-26：8 个进程、 S初值给定，问能同时访问资源的进程数与阻塞的进程数——能进的是初值那么多个，阻塞的是"总数 − 初值"。⚠️ 这类题只要抓住"S 为正是余量、为负其绝对值是等待数"就不会错。 - ② 给一个前驱图或一组操作约束，写 PV 代码（2020-45、2022-46）。套速记第六条：每条边一个初值 0 的信号量，起点后 V、终点前 P。⚠️ 检查方法是数一遍——信号量个数应等于边数，每个操作前的 P 个数应等于它的入度。
- ③ 生产者—消费者型的容量与同步问题（2011-45 银行窗口与座位、2015-45 双信箱辩论、2017-46 三线程读写、2024-46、2025-45 三人植树）。这一类的共同骨架是一个互斥信号量 + 若干个同步/资源信号量，判据在生产者-消费者问题详述。⚠️ 最贵的一个坑就是速记第五条：互斥的 P 放最后。 几乎每道大题的失分点都在这里。
复习优先级：必须拿满，这是 process 章分值最重的一节。 速记第三、四、五条（三种初值、前 V 后 P、互斥的 P 放最后）是写 PV 的全部基本功； 第六条那个前驱关系通法是送分题，练一遍就会；第八条那个反推公式每两三年考一次， 公式很短，记住即可。
易错：多个 P 操作时把互斥的 P 放在前面。必须放最后——否则抱着锁去等资源，当场死锁。
易错：认为 V 操作也有顺序要求。V 的顺序无约束，只有 P 的顺序要紧。
易错：把同步信号量的初值设成 1。同步用 0——"那件事"一开始还没发生。
易错：认为整型信号量也满足让权等待。它等不到时执行
while忙等；记录型用block才让权。
易错：把
S.value为负时的绝对值当成剩余资源数。为负时它是等待进程数，为正时才是余量。
易错：写前驱关系时给一个结点配一个信号量。是每条边配一个——P 的个数等于入度、V 的个数等于出度。
教材出处
- 整型信号量与"忙等"：汤小丹《计算机操作系统》2.4.3 节，印刷 p53——整型信号量的
wait(S){ while(S<=0); S--; }与signal(S){ S++; }；同页给出发展次序"从整型信号量经记录型信号量，进而发展为'信号量集'机制"。 - 记录型信号量遵循让权等待：同书印刷 p54——"当 S.value < 0 时……进程应调用 block 原语进行自我阻塞，放弃处理机……可见，该机制遵循了'让权等待'准则"；同页并说明
S->value绝对值表示已阻塞进程数目、初值为 1 时转化为互斥信号量。 - AND 型信号量与死锁反例：同书印刷 p54——进程 A、B 以相反顺序 wait(Dmutex)/wait(Emutex) 导致僵持，"我们称此时的进程 A 和 B 已进入死锁状态"。
- 信号量集的三个特例：同书印刷 p55——
Swait(S,d,d)、Swait(S,1,1)、Swait(S,1,0)（"相当于一个可控开关"）。 - 互斥信号量取值范围 (−1,0,1) 与 P/V 成对：同书 2.4.4 节，印刷 p56。
- 前驱关系的做法：同书印刷 p56—p57——"只需使进程共享一个公用信号量 S，并赋予其初值为 0，将 signal(S) 操作放在语句 S₁ 后面，而在 S₂ 语句前面插入 wait(S) 操作"，并按此为图中每条前驱边各设一个初值为 0 的信号量。