进程同步与互斥：信号量、PV 操作和生产者—消费者¶
这部分属于 操作系统 → 进程管理 → 进程同步与互斥。前驱图描述任务之间的先后关系，信号量和 PV 操作则用于实现等待、通知和互斥访问；生产者—消费者是把这些机制组合起来的经典模型。
学习时先确定“哪些进程要协作、共享什么、各自在等什么”，再写信号量和 PV 操作。
1. 同步和互斥分别解决什么问题¶
| 概念 | 要解决的问题 | 流水线中的例子 |
|---|---|---|
| 同步 | 让任务在条件满足后继续，协调先后关系 | 箱子有空位才能放，有产品才能取 |
| 互斥 | 同一时刻只允许一个执行流进入相应临界区，避免冲突访问共享数据 | 放入或取出时，需要保护箱子的存取位置等共享数据 |
临界区 是访问共享资源、需要互斥保护的那段程序。箱子是共享资源，修改它的存取位置、放入或取出数据的代码属于临界区。初步加工、继续加工、检验等工作通常可以在临界区外完成。
同步关注“条件够不够”，互斥关注“现在谁能操作”。即使箱子还有空位，生产者也可能因为消费者正在操作箱子而等待锁。
2. 信号量是什么，P 和 V 又是什么¶
信号量是一种同步机制，可以先理解为 带等待功能的许可计数器。它既可以表达可用资源数量，也可以表示一个任务已经完成、另一个任务可以继续。
这里 S3 是变量名，0 是初值。“3”不是信号量当前的数值，也不表示它必然属于进程 P3。
| 记号 | 含义 |
|---|---|
| P1、P2、P3 | 进程的名字 |
P(S)，也称 wait |
申请一个许可；没有可用许可时阻塞等待 |
V(S)，也称 signal |
归还或增加一个许可，使一个等待者有机会继续 |
P 不是生产，V 不是消费。 加工、放入、取出、检验是实际工作；PV 操作控制这些工作何时可以执行。生产者和消费者都会使用 P，也都会使用 V。
P 也不只是“检查一下”：成功通过 P 就取得了一个许可。例如 P(empty) 会预留一个空位，避免多个生产者把同一个空位重复使用。P/V 必须保证原子性以及正确的等待、唤醒协调，普通变量的加减不能直接替代它们。
P(S3) 是否意味着 S3 等于 1¶
不意味着。假设 S3 表示可领取半成品的许可，在没有并发操作和等待者的简单情况下：
| 动作 | 可用许可数 |
|---|---|
| 箱子最初为空 | 0 |
放入一件，执行 V(S3) |
1 |
再放入一件，执行 V(S3) |
2 |
消费者成功执行一次 P(S3) |
1 |
一次 P 申请一个许可，S3 则管理可能有多个的许可。 许可已经被领取、物品还没实际取出时，两者之间存在短暂的预订状态，所以运行中的许可数不一定等于箱子里肉眼可见的物品数。
补充：有些教材为什么会出现负数信号量
上文用“可用许可数”帮助理解，数量不会小于 0。教材中的记录型信号量还可以把等待者编码到同一个整数中，常见规则是：
- P：先将值减 1，若结果小于 0，就阻塞调用者。
- V：先将值加 1，若结果小于或等于 0，就唤醒一个等待者。
- 值为负时，其绝对值表示等待者数量；不是有“负数件产品”。
例如初值为 0，一个进程先执行 P，值变为 -1 并阻塞；另一个进程执行 V，值变为 0，前者被唤醒并完成这次 P，不需要再额外减一次。做数值变化题时，要先确认题目采用哪一种定义，不能混用这两种计数表达。
3. 互斥信号量、同步信号量与初值¶
“互斥”和“同步”描述信号量的用途，并不是通过 S 后面的编号区分的。
| 用途 | 它管理的许可 | 常见初值 |
|---|---|---|
| 互斥访问 | 进入临界区的一份访问权 | 初始未加锁时设为 1 |
| 前驱完成通知 | 前驱已经完成、后继可以继续的许可 | 前驱尚未完成时设为 0 |
| 空位计数 | 可申请的缓冲区位置 | 初始空位数 |
| 物品计数 | 可领取的缓冲区物品 | 初始物品数 |
不存在适合所有场景的自动“默认值”。应先问：这个信号量代表什么？开始时有几份许可？
容量为 N、初始已有 k 件物品的缓冲区，通常设置为：
例如容量 5、已有 2 件物品：mutex = 1、empty = 3、full = 2。互斥信号量初值为 1 与箱子容量无关；同步信号量也不一定从 0 开始。
两类信号量都需要 P、V 配合¶
互斥信号量通常在 同一个进程里 包围临界区：
同步信号量通常由 不同进程 协作：
不能说“同步信号量不成对”，也不能要求任意时刻 P、V 的执行次数都一样。初值本身可以提供许可，例如初始空位为 N，生产者不必等到第一次 V(empty) 才能使用空位。
这里的同进程、跨进程是常见用法。信号量通常没有专用互斥锁那样的持有者约束，不能把所有二值信号量直接等同于互斥锁。
4. 前驱图：用 PV 实现“先完成，再开始”¶
前驱图是描述先后依赖的有向无环图。A → B 表示 A 的相应任务完成后，B 才能开始；有多个前驱时，必须等所有前驱条件满足。
题目中的关系是：
flowchart LR
P1 --> P2
P2 --> P3
P2 --> P4
P3 --> P5
P4 --> P5P3、P4 没有相互的先后约束，可以并发执行；P5 必须等两者都完成，并不要求 P3、P4 同时开始或结束。
按本题“每条依赖边设置一个信号量”的方法，五个信号量初值都设为 0：
| 依赖边 | 信号量 | 前驱完成后 | 后继开始前 |
|---|---|---|---|
| P1 → P2 | S1 | P1 执行 V(S1) |
P2 执行 P(S1) |
| P2 → P3 | S2 | P2 执行 V(S2) |
P3 执行 P(S2) |
| P2 → P4 | S3 | P2 执行 V(S3) |
P4 执行 P(S3) |
| P3 → P5 | S4 | P3 执行 V(S4) |
P5 执行 P(S4) |
| P4 → P5 | S5 | P4 执行 V(S5) |
P5 执行 P(S5) |
对应原题 a～g 的填写结果：
| 位置 | 内容 | 原因 |
|---|---|---|
| a | V(S1) |
P1 完成后通知 P2 |
| b | P(S1) |
P2 等待 P1 |
| c | V(S2)、V(S3) |
P2 分别通知 P3、P4 |
| d | P(S2) |
P3 等待 P2 |
| e | V(S4) |
P3 完成后通知 P5 |
| f | P(S3) |
P4 等待 P2 |
| g | P(S4)、P(S5) |
P5 等 P3、P4 都完成 |
图中 P4 结束处的 V(S5) 已经给出。按这些选项，第 15 题选 A，第 16 题选 B；第 17 空对应 f、g 的上述组合。
解题时，看一个进程的 全部直接前驱和后继：在本题方案下，几条边进入，就在开始前放几个对应的 P；几条边出去，就在完成后放几个对应的 V。
信号量的名字可以整体换，只要两端配对一致。b 写 P(S1) 是因为 a 发的是 V(S1)，并不是因为 P2 应该匹配某个固定编号。g 的两个 P 可以交换顺序，但都必须通过。单次 V 只提供一个许可，不会自动通知所有后继。
5. 两级生产者—消费者流水线¶
题目中，P1 初步加工，P2 继续加工，P3 检验：
P1 是 B1 的生产者；P2 既是 B1 的消费者，又是 B2 的生产者；P3 是 B2 的消费者。两个箱子分别需要空位许可、物品许可和互斥锁。
六个信号量分别代表什么¶
B1 容量为 n，B2 容量为 m，两箱最初为空：
| 箱子 | 信号量 | 含义 | 用途 | 初值 |
|---|---|---|---|---|
| B1 | S1 | B1 的操作许可 | 互斥 | 1 |
| B1 | S2 | B1 的空位许可 | 同步、数量条件 | n |
| B1 | S3 | B1 的半成品许可 | 同步、数量条件 | 0 |
| B2 | S5 | B2 的操作许可 | 互斥 | 1 |
| B2 | S4 | B2 的空位许可 | 同步、数量条件 | m |
| B2 | S6 | B2 的成品许可 | 同步、数量条件 | 0 |
因此第 21 题选 C：S1、S5 都是互斥信号量，初值均为 1。第 22 空是 n、m。
这里的 S1～S6 与上一道前驱图题中的同名变量没有关系，每道题都要重新识别含义。
P1：预留空位，再拿锁，最后放入¶
P(S2) 负责“有没有空位，并预留一个”；P(S1) 负责“现在能不能由我操作箱子”。末尾 V(S3) 表示有一件半成品可取，让 P2 有机会继续，不是把物品消费掉。
P2：先消费 B1，再生产到 B2¶
P3：取走成品后归还空位¶
为什么先等空位或物品，再拿锁¶
如果消费者先拿锁，再在空箱子上等物品，就可能出现：
- 消费者持有箱子的锁，执行
P(full)后等待物品。 - 生产者想放入物品，却在
P(mutex)处等消费者释放锁。 - 消费者等物品，生产者等锁，双方都不能继续。
因此这个模型的基本顺序是：先等数量条件，再拿锁，操作箱子，释放锁，更新另一类许可。 锁只保护必要的共享操作，避免持锁等待对方才能提供的条件。
6. 做题时按什么顺序分析¶
- 找实际工作和共享资源。 区分加工、放入、取出等动作，以及需要保护的共享数据。
- 给每个信号量写一句含义。 用“B1 空位”“B1 物品”“B1 锁”替代机械记忆 S1、S2、S3。
- 按初始状态数许可。 锁未占用通常是 1；空位是容量减已有物品数；物品是已有数量；尚未发生的完成通知是 0。
- 看 P 申请了什么、V 提供了什么。 同一个信号量的申请和释放应能对应起来，也要考虑初始已有的许可。
- 检查等待与加锁顺序。 尤其检查是否持有别人必需的锁，却在等待别人才能满足的条件。
- 检查多前驱、多后继。 是否等齐所有必要条件，是否提供了足够的完成许可。
前驱图与资源分配图不要混淆：前驱图的边连接任务，表达先后依赖；资源分配图连接进程与资源，表达申请或分配，用于分析资源等待与死锁。参见死锁与资源分配图。