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]); // 放右 思考... } }