参考资料
计算机操作系统（汤小丹等）
前言
本文总结了操作系统课程中信号量机制（Semaphore）的经典 PV 操作题目，涵盖了前驱关系、生产者-消费者、读者-写者、哲学家就餐、理发师问题等经典同步互斥场景。通过这些题目，可以深入理解 wait()（P 操作）和 signal()（V 操作）在进程同步与互斥中的应用。
核心规则：
- 同步的信号量初始值为 0（表示”等待某个事件发生后才能继续”）
- 互斥的信号量初始值为 1（或资源数量，表示”临界区或资源的互斥访问”）
题目一：前驱关系（A、B → C → D、E）
分析
A 和 B 可以并发执行，C 必须等待 A 和 B 都完成后才能执行，D 可以和 C 并发（仅需 A、B 完成），E 必须等待 C 和 D 都完成后才能执行。
代码实现
semaphore a, b, c, d = 0, 0, 0, 0;
A() {
执行A;
signal(a); // 通知A已完成
}
B() {
执行B;
signal(b); // 通知B已完成
}
C() {
wait(a); // 等待A完成
wait(b); // 等待B完成
执行C;
signal(c); // 通知C已完成
}
D() {
执行D;
signal(d); // 通知D已完成
}
E() {
wait(c); // 等待C完成
wait(d); // 等待D完成
执行E;
}题目二：苹果橘子问题（单盘子版）
分析
父亲放苹果、母亲放橘子，儿子吃橘子、女儿吃苹果。盘子只能放一个水果，需要互斥访问。
代码实现
semaphore plate = 1, orange = 0, apple = 0;
// 父亲：放苹果
father() {
while (1) {
p(plate); // 申请盘子（互斥）
放苹果;
v(apple); // 通知女儿有苹果了
}
}
// 母亲：放橘子
mother() {
while (1) {
p(plate); // 申请盘子（互斥）
放橘子;
v(orange); // 通知儿子有橘子了
}
}
// 儿子：吃橘子
son() {
while (1) {
p(orange); // 等待有橘子
拿橘子;
v(plate); // 释放盘子
吃橘子;
}
}
// 女儿：吃苹果
daughter() {
while (1) {
p(apple); // 等待有苹果
拿苹果;
v(plate); // 释放盘子
吃苹果;
}
}题目三：苹果橘子问题（多盘子版）
分析
盘子容量为 10，父亲可以放苹果或橘子，儿子吃橘子，女儿吃苹果。需要记录盘子里水果数量，并互斥访问盘子。
代码实现
semaphore empty = 10, orange = 0, apple = 0, mutex = 1;
// 父亲：放水果
father() {
while (1) {
p(empty); // 等待空位
p(mutex); // 互斥访问盘子
放水果;
v(mutex); // 释放盘子
if (水果是苹果) {
v(apple); // 通知女儿
} else {
v(orange); // 通知儿子
}
}
}
// 儿子：吃橘子
son() {
while (1) {
p(orange); // 等待有橘子
p(mutex); // 互斥访问盘子
拿橘子;
v(mutex); // 释放盘子
v(empty); // 释放一个空位
吃橘子;
}
}
// 女儿：吃苹果
daughter() {
while (1) {
p(orange); // 等待有苹果（注意：原题此处应为 p(apple)，图片可能有误）
p(mutex); // 互斥访问盘子
拿苹果;
v(mutex); // 释放盘子
v(empty); // 释放一个空位
吃苹果;
}
}注意：女儿进程中的
p(orange)应为p(apple)，这可能是图片中的笔误。
题目四：司机与售票员问题
分析
司机和售票员需要协同工作：售票员关门后司机才能启动车辆，司机到站停车后售票员才能开门。
代码实现
semaphore close_door = 0, stop_bus = 0;
// 司机
driver() {
p(close_door); // 等待售票员关门
启动车辆;
正常行车;
到站停车;
v(stop_bus); // 通知售票员车已停
}
// 售票员
conductor() {
关车门;
v(close_door); // 通知司机可以开车
售票;
p(stop_bus); // 等待车停稳
开车门;
}题目五：生产者-消费者问题
分析
生产者向缓冲区放产品，消费者从缓冲区取产品。缓冲区大小为 n，需要同步空位和满位数量，并互斥访问缓冲区。
代码实现（简化版）
semaphore empty = n, full = 0, mutex = 1;
// 生产者
producer() {
while (1) {
生产产品;
wait(empty); // 等待空位
wait(mutex); // 互斥访问缓冲区
放产品;
signal(mutex); // 释放缓冲区
signal(full); // 通知消费者有产品
}
}
// 消费者
consumer() {
while (1) {
wait(full); // 等待有产品
wait(mutex); // 互斥访问缓冲区
拿产品;
signal(mutex); // 释放缓冲区
signal(empty); // 通知生产者有空位
消费产品;
}
}代码实现（标准版，带循环队列）
int in = 0, out = 0;
item buffer[n];
semaphore mutex = 1, empty = n, full = 0;
// 生产者
void producer() {
do {
producer an item nextp;
···
wait(empty); // 询问是否有空缓存区
wait(mutex); // 互斥访问
buffer[in] = nextp;
in = (in + 1) % n;
signal(mutex); // 解除互斥访问
signal(full); // 释放一个满缓存区，满缓存+1
} while (TRUE);
}
// 消费者
void consumer() {
do {
wait(full);
wait(mutex);
nextc = buffer[out];
out = (out + 1) % n;
signal(mutex);
signal(empty);
···
} while (TRUE);
}题目六：哲学家就餐问题
分析
5 位哲学家围坐在圆桌旁，每人左右各有一根筷子，需要同时拿起两根筷子才能就餐。如果不加限制，可能产生死锁（每位哲学家都拿起了左筷子，等待右筷子）。
原版代码（会产生死锁）
semaphore chopstick[5] = {1, 1, 1, 1, 1};
people(i) {
while (1) {
思考;
wait(chopstick[i]); // 拿左筷子
wait(chopstick[(i + 1) % 5]); // 拿右筷子
就餐;
signal(chopstick[i]); // 放左筷子
signal(chopstick[(i + 1) % 5]); // 放右筷子
思考;
}
}改进一：奇偶号哲学家不同顺序拿筷子
semaphore chopstick[5] = {1, 1, 1, 1, 1};
people(i) {
while (1) {
思考;
if (i % 2 == 0) {
wait(chopstick[i]); // 偶数号先拿左
wait(chopstick[(i + 1) % 5]);
} else {
wait(chopstick[(i + 1) % 5]); // 奇数号先拿右
wait(chopstick[i]);
}
就餐;
signal(chopstick[i]);
signal(chopstick[(i + 1) % 5]);
思考;
}
}改进二：限制同时就餐人数（最多4人）
semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore room = 4; // 最多允许4个哲学家同时就餐
people(i) {
while (1) {
思考;
wait(room); // 申请进入餐厅
wait(chopstick[i]);
wait(chopstick[(i + 1) % 5]);
就餐;
signal(chopstick[i]);
signal(chopstick[(i + 1) % 5]);
signal(room); // 离开餐厅
思考;
}
}题目七：读者-写者问题（公平版）
分析
允许多个读者同时读，但写者必须独占。使用排队信号量 w 保证公平性（先来先服务），wr 保证读写互斥。
代码实现
semaphore w = 1; // 排队信号量：读者和写者都先来后到
semaphore wr = 1; // 读写互斥：保证写者独占或读者群体独占
semaphore mutex = 1; // 保护 count
int count = 0;
// 写者
writer() {
while (1) {
wait(w); // 排队
wait(wr); // 申请独占
写文件;
signal(wr); // 释放独占
signal(w); // 出队（原代码这里错写成 wait）
}
}
// 读者
reader() {
while (1) {
wait(w); // 排队
wait(mutex); // 保护计数器
count++;
if (count == 1) // 第一个读者负责封锁写者
wait(wr);
signal(mutex);
signal(w); // 出队，让后面排队的人竞争
读文件;
wait(mutex);
count--;
if (count == 0) // 最后一个读者负责释放写者
signal(wr);
signal(mutex);
}
}注意：写者最后应该是
signal(w)而不是wait(w)，原图片中可能存在笔误。
题目八：苹果橘子问题（容量5版）
分析
盘子容量为 5，父亲随机放苹果或橘子，儿子吃橘子，女儿吃苹果。
代码实现
semaphore empty = 5, orange = 0, apple = 0, mutex = 1;
// 父亲：放水果
father() {
while (1) {
wait(empty); // 等待空位
wait(mutex); // 互斥访问盘子
放水果;
signal(mutex); // 释放盘子
if (放的是苹果) {
signal(apple); // 通知女儿
} else {
signal(orange); // 通知儿子
}
}
}
// 儿子：吃橘子
son() {
while (1) {
wait(orange); // 等待有橘子
wait(mutex); // 互斥访问盘子
拿橘子;
signal(mutex); // 释放盘子
signal(empty); // 释放一个空位
吃橘子;
}
}
// 女儿：吃苹果
daughter() {
while (1) {
wait(apple); // 等待有苹果
wait(mutex); // 互斥访问盘子
拿苹果;
signal(mutex); // 释放盘子
signal(empty); // 释放一个空位
吃苹果;
}
}题目九：理发师问题
分析
理发师在没有顾客时睡觉，有顾客来时叫醒理发师。顾客如果椅子满了就离开，否则坐下等待。
代码实现
semaphore customers = 0;
semaphore barbers = 0;
semaphore mutex = 1;
int waiting = 0;
const int N = 等候椅数;
// 理发师
barber() {
while (1) {
wait(customers); // 等待有顾客来（没有就睡觉）
wait(mutex); // 保护 waiting 计数
waiting--;
signal(barbers); // 通知顾客可以理发
signal(mutex);
cut_hair();
}
}
// 顾客
customer() {
wait(mutex);
if (waiting < N) { // 还有空椅子
waiting++;
signal(customers); // 叫醒理发师（或排队）
signal(mutex);
wait(barbers); // 等待理发师准备
get_haircut();
pay();
leave();
} else { // 椅子满了，离开
signal(mutex);
leave();
}
}题目十：过桥问题
分析
同一座桥，A 方向的人和 B 方向的人不能同时在桥上，但同一方向可以连续过桥。使用 rope 保证互斥，Aturn 和 Bturn 保证交替或同一方向连续通行。
代码实现
semaphore rope = 1;
semaphore Aturn = 1;
semaphore Bturn = 0;
// A 方向过桥
A() {
while (1) {
wait(Aturn); // 等待轮到 A 方向
wait(rope); // 申请过桥（互斥）
从A端走向B端();
signal(rope); // 释放桥
signal(Bturn); // 允许 B 方向过桥
}
}
// B 方向过桥
B() {
while (1) {
wait(Bturn); // 等待轮到 B 方向
wait(rope); // 申请过桥（互斥）
从B端走向A端();
signal(rope); // 释放桥
signal(Aturn); // 允许 A 方向过桥
}
}总结
| 题目类型 | 同步信号量初值 | 互斥信号量初值 | 关键思路 |
|---|---|---|---|
| 前驱关系 | 0 | 1 | 用信号量控制执行顺序 |
| 生产者-消费者 | full=0, empty=n |
mutex=1 |
空位和满位计数 + 互斥 |
| 读者-写者 | w=1, wr=1 |
mutex=1 |
排队公平 + 读写互斥 |
| 哲学家就餐 | — | chopstick[i]=1 |
破坏死锁必要条件 |
| 理发师问题 | customers=0, barbers=0 |
mutex=1 |
顾客叫醒理发师，计数等待人数 |
核心口诀：
- 同步的信号量一开始是 0（等待事件发生）
- 互斥的信号量是定值（通常是 1，或资源总数）
