问题模型

生产者-消费者问题描述的是一组生产者进程和一组消费者进程通过共享缓冲区交换数据：

生产者每次生产一个产品，并把产品放入缓冲区。
消费者每次从缓冲区取出一个产品，并使用这个产品。
缓冲区初始为空，容量为 $n$。
缓冲区满时，生产者不能继续放入产品。
缓冲区空时，消费者不能继续取出产品。
缓冲区是临界资源，放入和取出都必须互斥执行。

900

三个信号量

生产者-消费者问题同时包含互斥和同步。不只一个 mutex，还得有 empty、full

信号量	初值	含义	谁 P	谁 V
`mutex`	`1`	缓冲区访问权，同一时刻只允许一个进程放入或取出	生产者/消费者进入缓冲区前	生产者/消费者离开缓冲区后
`empty`	`n`	空闲缓冲区数量	生产者放入前	消费者取出后
`full`	`0`	已有产品数量，也就是非空缓冲区数量	消费者取出前	生产者放入后

empty 和 full 是两个方向的同步关系：

生产者需要空位。若 empty == 0，说明缓冲区满，生产者等待消费者释放空位。
消费者需要产品。若 full == 0，说明缓冲区空，消费者等待生产者放入产品。

mutex 只保护“实际访问缓冲区”的短区间。生产产品和使用产品都不访问共享缓冲区，不应放进互斥保护内。

伪代码

semaphore mutex = 1;    // 互斥访问缓冲区
semaphore empty = n;    // 空闲缓冲区数量
semaphore full = 0;     // 产品数量

producer 进程：
	while (1) {
	    生产一个产品;
	    P(empty);
	    P(mutex);
	    {
		    把产品放入缓冲区;
	    }
	    V(mutex);
	    V(full);
	}

consumer 进程：
	while (1) {
	    P(full);
	    P(mutex);
	    {
		    从缓冲区取出一个产品;
		}
	    V(mutex);
	    V(empty);
	    使用产品;
	}

生产者的核心顺序是：先申请空位，再申请缓冲区访问权；放入产品后，先释放缓冲区访问权，再增加产品数量。

消费者的核心顺序是：先申请产品，再申请缓冲区访问权；取出产品后，先释放缓冲区访问权，再增加空位数量。

为什么同步 P 要在互斥 P 前

`P(mutex)` 保护的是缓冲区访问权。若进程先拿到 `mutex`，再因为 `empty` 或 `full` 不满足而阻塞，就会带着缓冲区访问权睡眠，其他进程也无法进入缓冲区改变条件。 > >

> > 以缓冲区已满为例，若生产者错误地先执行 `P(mutex)`，再执行 `P(empty)`： > >1. 生产者执行 `P(mutex)`，占有缓冲区访问权。 >2. 生产者执行 `P(empty)`，发现没有空位，于是阻塞。 >3. 消费者本来可以取走产品并执行 `V(empty)`，但它执行 `P(mutex)` 时发现 `mutex == 0`，也阻塞。 >4. 生产者等待消费者释放空位，消费者等待生产者释放 `mutex`，形成死锁。 > > 缓冲区为空时也有对称错误：消费者若先持有 `mutex`，再因 `P(full)` 阻塞，生产者就无法进入缓冲区放入产品。 > > 因此，可能因为条件不满足而阻塞的同步 P 操作，应放在互斥 P 操作之前。 > V 操作不会使当前进程阻塞，所以两个 V 操作的相对顺序通常不如两个 P 操作敏感。

Note

也可以借助最小作用范围的思想: mutex的职责是互斥访问缓冲区，应使得它作用范围最小，即紧挨着临界区。

# 多生产者与多消费者

多个生产者共用同一个 empty 和 mutex：

empty 限制所有生产者合计不能超过缓冲区容量。
mutex 保证任意时刻只有一个生产者或消费者访问缓冲区。

多个消费者共用同一个 full 和 mutex：

full 限制所有消费者合计不能取出超过已有产品数量。
mutex 保证两个消费者不会同时取走同一个缓冲区单元。

生产者数量、消费者数量增加时，信号量含义不变；变化的是等待队列中可能有多个同类进程。

容量为 1 的特殊情况

当缓冲区容量为 1 时，有些具体题目可以不额外设置 mutex。原因是 empty 与 full 的取值互补：缓冲区要么空，要么满，同一时刻通常只会有生产者或消费者一侧能通过同步 P 操作。

但这不是通用结论。只要缓冲区容量大于 1，多个生产者可能同时通过 P(empty)，多个消费者也可能同时通过 P(full)；如果没有 mutex，它们就可能同时访问缓冲区并破坏数据结构。

因此默认写法仍然保留 mutex。只有在能严格证明同步信号量已经排除了并发访问时，才考虑省略互斥信号量。

判断步骤

看到缓冲区类同步互斥问题时，可以按这个顺序分析：

找临界资源：谁会共同访问同一个缓冲区或共享数据结构。
找容量资源：生产者消耗什么资源，消费者释放什么资源。
找产品资源：消费者消耗什么资源，生产者释放什么资源。
先写同步 P，再写互斥 P。
临界区结束后先释放互斥，再用 V 通知另一类资源变化。

三个信号量对应的资源：mutex 是访问权，empty 是空位，full 是产品。

若题目不是生产同一种产品，而是每次生产不同类型的组合，就要进一步区分产品类型。典型例子是 Cigarette-Smokers-Problem。