Appearance
生产者-消费者问题
2026 大纲 二（三）6 经典同步问题的生产者-消费者部分（读者-写者见《读者-写者问题》）。
第一个经典问题：两边速度不一样，怎么配合
前面把工具备齐了：信号量能互斥也能同步，初值怎么定、P V 怎么摆都有了口诀。 接下来三节是拿这套工具去解三个经典问题——它们之所以经典， 是因为几乎所有真实的同步场景都能归到这三类里。
第一个是生产者—消费者：一边往缓冲区放，一边从缓冲区取， 而两边的速度并不一样。
这里同时存在两种制约关系，必须分开处理：
互斥——缓冲区是临界资源，不能两个人同时动它； 同步——缓冲区满时生产者必须等，空时消费者必须等。
前者用一个初值 1 的 mutex。后者需要两个信号量， 而它们的初值由那句口诀直接给出——一开始有几份可用： empty = N（一开始有 N 个空格子）、full = 0（一开始没有产品）。
⚠️ 值得留意的是 empty 和 full 数的是同一批格子的两种状态， 所以它们的和恒等于
骨架因此固定成 P(empty) → P(mutex) → 放 → V(mutex) → V(full)，消费者对称。
而这个顺序里最贵的一条就是"P 必须先同步后互斥"—— 如果写成 P(mutex) → P(empty)，生产者就会抱着锁去等空格子， 而唯一能腾出空格子的消费者进不来（锁在生产者手上），当场死锁。
交互可视化
一、问题与信号量设计
一组生产者向缓冲池放数据、一组消费者取数据，缓冲池含 N 个缓冲区，按环形队列使用（in 指向下一个写入位置，out 指向下一个读出位置）。只要池未满生产者就可以送入，只要池未空消费者就可以取走。
按信号量五步法走：进程分两类（生产者、消费者），资源分两类（空缓冲区、满缓冲区——同一批格子的两种状态），关系是一互斥两同步，于是三个信号量与初值就定下来了。
二、完整解答
int in = 0, out = 0;
item buffer[N];
semaphore mutex = 1, empty = N, full = 0;
// 生产者进程
producer() {
do {
produce an item nextp; // 生产，在临界区外
P(empty); // ① 申请一个空缓冲区
P(mutex); // ② 进入临界区
buffer[in] = nextp;
in = (in + 1) % N;
V(mutex); // ③ 离开临界区
V(full); // ④ 满缓冲区数 +1
} while (TRUE);
}
// 消费者进程
consumer() {
do {
P(full); // ① 申请一个满缓冲区
P(mutex); // ② 进入临界区
nextc = buffer[out];
out = (out + 1) % N;
V(mutex); // ③ 离开临界区
V(empty); // ④ 空缓冲区数 +1
consume the item in nextc; // 消费，在临界区外
} while (TRUE);
}生产者与消费者的代码是对称的：把 empty 与 full 互换、in 换成 out，就从一方变成另一方。记住一方即可推出另一方。
一轮完整交错的逐拍走查：满了怎么等、又怎么被唤醒（想在时间轴上看清同步过程时展开）
N = 2，一个生产者一个消费者。信号量按记录型语义：P 先减一，减完为负就阻塞；V 先加一，加完仍 ≤ 0 说明队列里有人，唤醒队首。
| 节拍 | 谁执行什么 | mutex | empty | full | 池中产品 | 说明 |
|---|---|---|---|---|---|---|
| 0 | 初始 | 1 | 2 | 0 | 0 | |
| 1 | 生产者 P(empty) | 1 | 1 | 0 | 0 | 领到一个空位 |
| 2 | 生产者 P(mutex) | 0 | 1 | 0 | 0 | 进临界区 |
| 3 | 生产者写入产品①，in 0→1 | 0 | 1 | 0 | 1 | |
| 4 | 生产者 V(mutex) | 1 | 1 | 0 | 1 | 出临界区 |
| 5 | 生产者 V(full) | 1 | 1 | 1 | 1 | 宣布"有货了" |
| 6–9 | 生产者再走一遍，写入产品② | 1 | 0 | 1 | 2 | in 1→0（环形绕回） |
| 10 | 生产者 V(full) | 1 | 0 | 2 | 2 | 缓冲池已满 |
| 11 | 生产者 P(empty) | 1 | −1 | 2 | 2 | 阻塞——注意它手里没有 mutex |
| 12 | 消费者 P(full) | 1 | −1 | 1 | 2 | 领到一个满缓冲区 |
| 13 | 消费者 P(mutex) | 0 | −1 | 1 | 2 | 顺利进入——锁没被人攥着 |
| 14 | 消费者取走产品①，out 0→1 | 0 | −1 | 1 | 1 | |
| 15 | 消费者 V(mutex) | 1 | −1 | 1 | 1 | |
| 16 | 消费者 V(empty) | 1 | 0 | 1 | 1 | 加完仍 ≤ 0 ⇒ 唤醒生产者 |
| 17 | 生产者被唤醒，P(mutex) | 0 | 0 | 1 | 1 | 接着往下跑 |
节拍 11 是全表的枢纽：生产者阻塞在 P(empty) 上时 mutex 仍是 1。正因为同步的 P 排在互斥的 P 前面，它是"空着手睡下"的，消费者才能在节拍 13 照常进临界区、在节拍 16 把它唤醒。把这两个 P 对调，卡住的是同一个位置，区别只在"睡下时手里还攥着 mutex"。
互斥的 P 必须放在同步的 P 之后
// 错误写法
producer() {
P(mutex); // 先拿锁
P(empty); // 再申请空缓冲区 —— 缓冲池满时阻塞在这里
... // 而 mutex 还攥在手里！
}缓冲池满时，生产者持有 mutex 却阻塞在 P(empty) 上；消费者本可以取走一个产品腾出空位，却因为拿不到 mutex 而进不了临界区。两边互相等 → 死锁。
这条死锁的执行序列，与两种写法的穷举模型检验（想自己验证顺序约束时展开）
设 N = 2，两个生产者、两个消费者，生产者用上面的错误写法。
第 1 步：先把系统推到"缓冲池满"。 死锁只在"资源已耗尽 + 有人持锁去要它"时触发，所以必须先把 empty 压到 0。让生产者 A 连续完整地放两次：
| 事件 | mutex | empty | full | 缓冲池 |
|---|---|---|---|---|
| 初始 | 1 | 2 | 0 | 空 |
| A 放入第 1 个（四步全走完） | 1 | 1 | 1 | 1 个 |
| A 放入第 2 个 | 1 | 0 | 2 | 满 |
第 2 步：让 A 再来一次，卡在关键点上。
| 时刻 | 动作 | mutex | empty | A 的状态 |
|---|---|---|---|---|
| ① | A 执行 P(mutex)，成功 | 0 | 0 | 运行，持有 mutex |
| ② | A 执行 P(empty)，empty 已为 0 | 0 | −1 | 阻塞，仍持有 mutex |
第 3 步：让消费者来救场——它救不了。 要证明是死锁而不只是暂时等待，必须说明唯一能解开僵局的动作也被挡住了：能给 empty 加一的只有消费者的 V(empty)，而消费者卡在 P(mutex) 上，永远走不到那一句。
| 时刻 | 动作 | mutex | 结果 |
|---|---|---|---|
| ③ | 消费者 B 执行 P(mutex) | −1 | 阻塞（mutex 在 A 手里） |
| ④ | 消费者 C 执行 P(mutex) | −2 | 阻塞 |
| ⑤ | 生产者 D 执行 P(mutex) | −3 | 阻塞 |
第 4 步：判定。 四个进程全部阻塞，且各自等待的事件只能由其他阻塞进程触发 → 死锁。
第 5 步：穷举模型检验。 枚举全部可达状态，把"所有进程都阻塞"记为死锁态：
| 写法 | 可达状态数 | 死锁态 | 断言违反（缓冲计数越界 / 互斥失效） |
|---|---|---|---|
正确：P(empty); P(mutex); | 825 | 0 | 0 |
错误：P(mutex); P(empty); | 785 | 4 | 0 |
其中一个死锁态与手工走出的序列一致：一个生产者阻塞在 full／empty 上，其余三个进程全部阻塞在 mutex 上。
三、变形一：缓冲区只有一个格子（盘子问题）
桌上有一个盘子（缓冲区大小 = 1），父亲放苹果、母亲放橘子、女儿吃苹果、儿子吃橘子。
semaphore plate = 1; // 盘子里的空位数
semaphore apple = 0; // 盘中苹果数
semaphore orange = 0; // 盘中橘子数
father() { daughter() {
P(plate); P(apple);
放苹果; 取苹果;
V(apple); V(plate);
} }
mother() { son() {
P(plate); P(orange);
放橘子; 取橘子;
V(orange); V(plate);
} }plate 的初值恰好是 1，任何一方要动盘子都得先 P(plate)，于是同一时刻最多一个进程在操作盘子——plate 同时充当了资源计数和互斥两个角色，所以省掉了 mutex。穷举检验（4 个进程、盘子容量 1）：可达状态 84，死锁态 0，盘中产品数始终在 [0, 1] 内。
四、变形二：多生产者多消费者的一般写法
把盘子换成能放 N 个水果的果盘（N > 1），角色不变。此时"省掉 mutex"的前提没有了（empty 初值不再是 1），按"初值即初始可用份数、P 先同步后互斥、V 顺序任意"这三条重新设计：
semaphore mutex = 1; // 果盘的互斥访问
semaphore empty = N; // 空位数（两类产品共享）
semaphore apple = 0; // 盘中苹果数
semaphore orange = 0; // 盘中橘子数
father() { daughter() {
P(empty); P(apple);
P(mutex); P(mutex);
放苹果; 取苹果;
V(mutex); V(mutex);
V(apple); V(empty);
} }
mother() { son() {
P(empty); P(orange);
P(mutex); P(mutex);
放橘子; 取橘子;
V(mutex); V(mutex);
V(orange); V(empty);
} }每个进程仍是「先同步 P、后互斥 P；先互斥 V、后同步 V」这个固定骨架，只是同步信号量按产品类型分了叉。穷举检验（N = 2，四类角色各一个）：可达状态 1012，死锁态 0；把 P 顺序颠倒成先 P(mutex)，同样规模下出现 12 个死锁态——顺序约束在多类产品下同样成立。
实现层面的一个附带条件
果盘里混放两类水果时，缓冲池就不能再是"一个 in、一个 out"的严格环形队列了——女儿必须能定位到一个苹果，而 out 指向的可能是橘子。实现上通常给每类产品各维护一组位置，或给格子打上类型标记。这不影响信号量层面的设计，上面四个信号量的定义与 P/V 位置照样成立。
变形三：吸烟者问题（想看"多类消费者 + 容量为 1"这一族怎么写时展开）
卷一支烟需要烟草、纸、胶水三样。三个吸烟者各只拥有其中一样且数量无限；供应者每次把另外两样放到桌上，拥有第三样的那个吸烟者取走卷烟，抽完通知供应者再放一组。
它属于"多类产品、多类消费者"这一族（供应者 = 生产者，三个吸烟者 = 三类消费者），只是缓冲区容量为 1。
| 信号量 | 初值 | 代表什么 |
|---|---|---|
offer1 | 0 | 桌上放着「纸 + 胶水」（给有烟草的 1 号） |
offer2 | 0 | 桌上放着「烟草 + 胶水」（给有纸的 2 号） |
offer3 | 0 | 桌上放着「烟草 + 纸」（给有胶水的 3 号） |
🔴 finish | 1 | 桌子是空的、可以放新材料——一开始桌子确实空着，所以有 1 份 |
semaphore offer1 = 0, offer2 = 0, offer3 = 0;
semaphore finish = 1;
agent() { smoker_i() { // i = 1, 2, 3
while (TRUE) { while (TRUE) {
P(finish); // 等桌子空 P(offer_i); // 等属于我的那组材料
任选 i ∈ {1,2,3}; 取走两样材料; 卷烟;
把对应的两样材料放上桌; V(finish); // 告诉供应者桌子空了
V(offer_i); // 通知第 i 个吸烟者 抽烟; // 在临界区外
} }
} }三处设计判据都是前面那几条的实例：三个 offer 而非一个，因为同步信号量要把信号定向送给特定等待者，只设一个会唤醒错人；不需要 mutex，因为 finish 初值为 1，与盘子问题同理；抽烟 放在 V(finish) 之后，抽烟不占桌子，早点还回去可提高并发度。
finish 若误定成 0，供应者第一次就阻塞，而能给它 V 的吸烟者又永远等不到材料——系统一步也走不动。穷举检验（供应者 + 3 个吸烟者，供应者每轮的选择当作不确定分支全部展开）：可达状态 112，死锁态 0，任一时刻至多一人在卷烟。
考点速记
- 三个信号量：
mutex = 1（互斥）、empty = N（空格子数）、full = 0（产品数）。初值即初始可用份数。 ⚠️empty与full数的是同一批格子的两种状态，两者之和恒为。 - 骨架：生产者
P(empty) → P(mutex) → 放 → V(mutex) → V(full)，消费者对称（P(full) → P(mutex) → 取 → V(mutex) → V(empty)）。 - ⚠️P 必须先同步后互斥——写成
P(mutex) → P(empty)会让生产者抱着锁等空格子，而能腾格子的消费者进不来，当场死锁。 - V 的顺序任意，因为 V 永不阻塞。
- ⚠️能否省掉 mutex，由资源信号量的初值是否为 1 决定：缓冲区只有 1 个格子时
empty初值为 1，它本身已经保证了互斥，mutex可省；时不能省。 - 多类产品的一般写法：共享一个
empty、每类产品各配一个初值 0 的同步信号量，骨架不变。
这一节在真题里被考过的形式：
classic-sync-problems 这个标签下只有 3 道题、由三篇经典问题共享， 本页练习区渲染的题不全是本节内容，属正常。但生产者—消费者的骨架是 sync-mutex-concepts 与 ipc 下那一批 PV 大题的公共模板—— 2011-45（银行窗口与座位）、2015-45（双信箱辩论）、2017-46（三线程读写）、 2024-46、2025-45（三人植树）全都是它的变形。
这类大题的做法固定成三步：
- ① 找出有几种"资源"，每种配一个信号量，初值就是一开始有几份。 银行题里"座位"初值是 10、"窗口"初值是 1；植树题里每道工序的完成信号初值都是 0。
- ② 判断要不要 mutex：看有没有一份资源会被多个进程同时改。⚠️ 按速记第五条， 资源信号量初值为 1 时可省。
- ③ 摆 P 的顺序：同步的 P 在前、互斥的 P 在最后（速记第三条）。 几乎每道大题的失分点都在这一步。
复习优先级：必须拿满，这是 PV 大题的公共模板。 速记第一到三条 （三个信号量、骨架、P 的顺序）要练到不假思索；第五条（何时能省 mutex） 在"只有一个缓冲区"的变形题里会用到。第六条那个多类产品的写法在 2015-45 双信箱这类题里直接用得上。
易错：把
P(mutex)写在P(empty)前面。抱着锁等资源，当场死锁。
易错：认为 V 的顺序也要讲究。V 永不阻塞，顺序任意。
易错：把
empty和full当成两组独立资源。它们数的是同一批格子的两种状态，和恒为。
易错：缓冲区只有一个格子时还写 mutex。此时
empty初值为 1，它本身已保证互斥。
易错：多类产品时给每类各配一个
empty。共享一个empty，每类各配一个初值 0 的同步信号量。
教材出处
- 记录型信号量解生产者-消费者的完整代码：汤小丹《计算机操作系统》2.5.1 节，印刷 p60——
int in=0, out=0; item buffer[n]; semaphore mutex=1, empty=n, full=0;，生产者为wait(empty); wait(mutex); buffer[in]=nextp; in:=(in+1)%n; signal(mutex); signal(full);。同页说明"只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息"。 - AND 型信号量写法：同书印刷 p62——消费者写作
Swait(full, mutex); ... Signal(mutex, empty);，把两个 P 合成一次原子申请。