1. 生产者-消费者问题
1.1问题描述
系统中有一组生产者进程和消费者进程,生产者进程每次生产一个产品放入缓冲区,消费者进程每次从缓冲区中取出一个产品使用。
- 生产者、消费者共享一个初始为空、大小为n的缓冲区。
- 只有缓冲区没满时,生产者才能把产品放入缓冲区,否则必须等待。
- 只有缓冲区不空时,消费者才能从中取产品,否则必须等待。
- 缓冲区是临界资源,各进程必须互斥访问。

1.2问题分析
PV操作题目分析步骤:
关系分析
找出题目中描述各个进程,分析他们之间的同步、互斥关系。
- 缓冲区没空 ----> 消费者消费
- 缓冲区没满 <---- 生产者生产
整理思路
根据各进程的操作流程确定P、V操作的大致顺序。
- 缓冲区没空(V)---full---> (P) 消费者消费
- 缓冲区没满(P)<---empty----(V)生产者生产
设置信号量
设置需要的信号量,并根据题目条件确定信号量初值。
- 互斥信号量初值一般为1
- 同步信号量的初值看对应资源的初值
1.3实现
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操作之后;若互换,会导致进程阻塞。
- V操作互换不会导致进程阻塞;
2. 多生产者 - 多消费者问题
2.1问题描述
桌子上有一只盘子,每次只能向其中放入一个水果。爸爸专向盘子中放苹果,妈妈专向盘子中放橘子,儿子专等着吃盘子中的橘子,女儿专等着吃盘子中的苹果。只有盘子空时,爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时,儿子或女儿可以从盘子中取出水果。
2.2问题分析
关系分析
找出题目中描述各个进程,分析他们之间的同步、互斥关系。
- 互斥关系:对缓冲区(盘子)的访问要互斥的进行
- 同步关系(一前一后)
- 父亲将苹果放入盘子后,女儿才能取苹果
- 母亲将橘子放入盘子后,儿子才能取橘子
- 只有盘子为空时(儿子或女儿触发),父亲或母亲才能放入苹果
整理思路
根据各进程的操作流程确定P、V操作的大致顺序。
- 互斥:在临界区前后分别PV
- 同步:前V后P
设置信号量初始值

2.3实现
semaphore mutex = 1; // 实现互斥的访问盘子(缓冲区) semaphore apple = 0; // 盘子中有几个苹果 semaphore orange = 0; // 盘子中有几个橘子 semaphore plate = 1; // 盘子中还可以放多少个水果
dad() { while(1) { 准备一个苹果; P(plate); P(mutex); 把苹果放入盘子; V(mutex); V(apple); } }
mom() { while(1) { 准备一个橘子; P(plate); P(mutex); 把橘子放入盘子; V(mutex); V(orange); } }
daughter() { while(1) { P(apple); P(mutex); 从盘子中取出苹果; V(mutex); V(palte); 吃掉苹果; } }
son() { while(1) { P(orange); P(mutex); 从盘子中取出橘子; V(mutex); V(palte); 吃掉橘子; } }
注意:
- 如果缓冲区大小为1,那么可能不需要设置互斥信号量就可以实现互斥访问的功能;但是,缓冲区如果大于1,不加互斥信号量,可能会资源覆盖。
- 实现互斥的P操作一定要在实现同步的P操作之后,否则会引起“死锁”。
3. 吸烟者问题
3.1问题描述
假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它,但要卷起并抽调一直烟,抽烟者需要有三种材料:烟草、纸和胶水。三个抽烟者中,第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限提供三种材料,供应者每次将两种材料放桌上,拥有剩下那种材料的抽烟者卷一根烟并抽掉它,并给供应者进程一个信号告诉完成了,供应者就会放另外两种材料到桌上,这个过程一直重复。
3.2问题分析
关系分析- 互斥关系:桌子,容量为1的缓冲区
- 同步关系:
- 第i各抽烟者需要的材料 ---> 第i各抽烟者取走材料
- 发出完成信号 ----> 下一组材料
- 第i各抽烟者需要的材料 ---> 第i各抽烟者取走材料
- 发出完成信号 ----> 下一组材料
整理思路
设置信号量

3.3实现
semaphore offer1 = 0; // 桌上组合一的数量 semaphore offer2 = 0; // 桌上组合二的数量 semaphore offer3 = 0; // 桌上组合三的数量 semaphore finish = 0; // 抽烟是否完成 int i = 0; // 用于实现“三个抽烟者轮流吸烟”
provider() { while(1) { if(i == 0) { 将组合一放桌上; V(offer1); } if(i == 1) { 将组合二放桌上; V(offer2); } if(i == 2) { 将组合三放桌上; V(offer3); } i = (i + 1) % 3; P(finish); } }
smoker1() { while(1) { P(offer1); 从桌上拿走组合一;卷烟;抽掉; V(finish); } }
smoker2() { while(1) { P(offer2); 从桌上拿走组合二;卷烟;抽掉; V(finish); } }
smoker3() { while(1) { P(offer3); 从桌上拿走组合三;卷烟;抽掉; V(finish); } }
注意:
- 因缓冲区大小为1,可以不需要设置互斥量。
4. 读写者问题
4.1问题描述
有读者和写者两组并发进程,共享一个文件,当两个或两个以上的读进程同时访问共享数据时不会产生副作用,但若某个写进程和其他进程(读进程或写进程)同时访问共享数据时,则可能导致数据不一致的错误。因此要求:
(1)允许多个读者可以同时对文件执行读操作;
(2)只允许一个写者往文件中写信息;
(3)任一写者在完成操作之前不允许其他读者或写着工作;
(4)写着执行写操作前,应让已有的读者和写着全部退出。
4.2问题分析
关系分析
- 两类进程:写进程、读进程
- 互斥关系:
- 写进程 — 写进程
- 写进程 — 读进程
- 读进程与读进程不存在互斥关系
整理思路
设置信号量
3.3实现
读优先,写进程可能饿死
semaphore rw = 1; // 用于实现对共享文件的互斥访问 int count = 0; // 记录当前有几个读进程在访问文件 semaphore mutex = 1; // 用于保证对count变量的互斥访问
writer() { while(1) { P(rw); // 写之前加锁 写文件... V(rw); // 写完了解锁 } }
reader() { while(1) { P(mutex); // 各读进程互斥访问count if(count == 0) // 由第一个读进程负责 P(rw); // 读之前加锁 count++; // 访问文件的读进程数+1 V(mutex); 读文件... P(mutex); // 各读进程互斥访问count count--; // 访问文件的读进程-1 if(count == 0) // 由最后一个读进程负责 V(rw); // 读完了“解锁” V(mutex); } }
写优先,读写公平法。
semaphore rw = 1; // 用于实现对共享文件的互斥访问 int count = 0; // 记录当前有几个读进程在访问文件 semaphore mutex = 1; // 用于保证对count变量的互斥访问 semaphore w = 1; // 用于实现“写优先”
writer() { while(1) { P(w); P(rw); // 写之前加锁 写文件... V(rw); // 写完了解锁 V(w); } }
reader() { while(1) { P(w); P(mutex); // 各读进程互斥访问count if(count == 0) // 由第一个读进程负责 P(rw); // 读之前加锁 count++; // 访问文件的读进程数+1 V(mutex); V(w); 读文件... P(mutex); // 各读进程互斥访问count count--; // 访问文件的读进程-1 if(count == 0) // 由最后一个读进程负责 V(rw); // 读完了“解锁” V(mutex); } }
5. 哲学家进餐问题
5.1问题描述
一张圆桌上坐着5位哲学家,每两个哲学家之间的桌子上摆一根筷子,桌子的中间是一碗米饭。哲学家们主要做两件事:思考和进餐,哲学家在思考时,并不影响他人。只有当哲学家饥饿时,才试图拿起左、右两根筷子(一根一根的拿起)。如果筷子已在他人手上,则需要等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐,当进餐完毕后,放下筷子继续撕开
5.2问题分析
关系分析
5个哲学家进餐,5个哲学家与左右邻居对其中间筷子的访问时互斥的
整理思路
每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免邻接资源分配不当造成的死锁现象,是哲学家问题的精髓。
信号量设置
定义互斥信号量数组
chopstick[5]={1,1,1,1,1}
用于实现对5个筷子的互斥访问。并对哲学家按0~4
编号,哲学家i左边的筷子编号位i,右边的筷子编号为 (i+1)%5
.
5.3实现
如何避免死锁的发生?
- 可以对哲学家进程增加一些限制条件,比如最多允许四个哲学家同时进餐。
- 要求奇数号哲学家先拿左边的筷子然后再拿右边的筷子,而偶数号的刚好相反。
- 仅当一个哲学家左右两支筷子都可使用时才允许他拿起筷子
// 各哲学家拿筷子必须互斥的执行。 semaphore chopstick[5] = {1,1,1,1,1}; semaphore mutex = 1; // 互斥的取筷子 Pi() { while(1) { P(mutex); P(chopstick[i]); // 拿左面的筷子 P(chopstick[(i+1)%5]); // 拿右面的筷子 V(mutex); 吃饭... V(chopstick[i]); // 放左 V(chopstick[(i+1)%5]); // 放右 思考... } }