生产者-消费者问题
- 系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用；
- 生产者、消费者共享一个初始为空、大小为n的缓冲区；
- 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待；
- 只有缓冲区不空时，消费者才能从中取出产品，否则必须等待；
- 缓冲区是临界资源，各进程必须互斥地访问。
分析关系
视频讲解
- 生产者和消费者访问缓冲区是互斥的；
- 生产者和消费者的工作需要同步，即生产完成之后才能消费。
生产者-消费者同步关系
设置信号量
1
2
3
| semaphore mutex = 1; //互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n; //同步信号量，表示空闲缓冲区的数量
semaphore full = 0; //同步信号量，表示产品（非空缓冲区）的数量
|
实际代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 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操作可以交换顺序
多生产者-多消费者问题
视频讲解
有父亲、母亲、儿子、女儿四人，其中：
- 父亲往盘子中放苹果；
- 母亲往盘子中放橘子；
- 女儿从盘子中拿苹果；
- 儿子从盘子中拿橘子；
- 只有盘子空时才能放水果；
- 只有有需要的水果时才能拿水果。
分析关系
视频讲解：分析关系时图的画法
- 互斥
- 同步
- 父亲放入苹果后，女儿才能拿苹果
- 母亲放入橘子后，儿子才能拿橘子
- 盘子为空时才能放水果
设置信号量
1
2
3
4
| semaphore mutex = 1; //互斥信号量，实现盘子的互斥访问
semaphore plate = 1; //同步信号量，代表盘子的剩余空位
semaphore apple = 0; //同步信号量，代表苹果数量
semaphore orange = 0; //同步信号量，代表橘子数量
|
实际代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| 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(plate); //释放盘子资源
恰苹果
}
}
son(){
while(1){
P(orange); //申请橘子资源
P(mutex);
拿出橘子
V(mutex);
V(plate); //释放盘子资源
恰橘子
}
}
|
由于本问题缓冲区为1，可以考虑不设置信号量。
吸烟者问题
视频讲解：吸烟者问题
系统中有一个供应者和三个吸烟者，吸烟者吸烟需要自己卷烟，其中
- 卷烟需要烟草、纸、胶水三种材料
- 每个吸烟者各有其中的一种材料
- 供应者每次会提供其中两种材料，并由缺少该材料的吸烟者拿取
- 吸烟者制作完烟并抽掉后，发出信号，供应者放下一组物品
分析关系
可以将桌子视为容量为1的缓冲区，并且将两种材料分别视为三种组合：
- 组合一：纸+胶水
- 组合二：烟草+胶水
- 组合三：烟草+纸
- 互斥
- 同步
- 桌上有组合一，第一个抽烟者取走物品
- 桌上有组合二，第二个抽烟者取走物品
- 桌上有组合三，第三个抽烟者取走物品
- 发出完成信号后，供应者将下一个组合放到桌上
信号量设置
1
2
3
4
5
| semaphore offer1 = 0; //同步信号量，桌上组合一的数量
semaphore offer1 = 0; //同步信号量，桌上组合二的数量
semaphore offer1 = 0; //同步信号量，桌上组合三的数量
semaphore finish = 0; //同步信号量，抽烟是否完成
int i = 0; //实现轮流提供材料
|
实际代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| provider(){
while(1){
if (i==0){
将组合一放在桌上
V(offer1); //提供材料
}else if (i==1){
将组合二放在桌上
V(offer2);
}else 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
2
3
| semaphore rw = 1; //互斥信号量，实现读、写对文件的互斥访问
int count = 0; //同时在读文件的读进程数量
semaphore mutex = 1; //互斥信号量，实现读进程对count的互斥访问
|
然而，以上信号量设置有可能导致饿死，具体如下代码一所示，因此，增加一个信号量
1
| semaphore w = 1; //同步信号量，用于实现“写优先”
|
实际代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| writer(){
while(1){
P(rw);
写文件
V(rw);
}
}
reader(){
while(1){
P(mutex);
if (count == 0){
P(rw); //由第一个读进程负责上锁
}
V(mutex);
读文件
P(mutex);
count--;
if (count == 0){
V(rw); //由最后一个读进程负责解锁
}
V(mutex);
}
}
|
以上代码存在饿死现象，即一直有读进程占用，写进程始终无法运行
因此，引入了“写优先”的信号量：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| writer(){
while(1){
P(w);
P(rw);
写文件
V(rw);
V(w);
}
}
reader(){
while(1){
P(w); //对每一个读和写进程之间做互斥处理
P(mutex);
if (count == 0){
P(rw); //由第一个读进程负责上锁
}
V(mutex);
V(w);
读文件
P(mutex);
count--;
if (count == 0){
V(rw); //由最后一个读进程负责解锁
}
V(mutex);
}
}
|
当然，这种实际上是各个读、写进程之间公平运行，并不是准确的写优先。
通过设置count实现读进程之间不互斥
哲学家进餐问题
视频讲解：哲学家进餐问题
在一个桌子上，有5位哲学家，其中
- 每位哲学家之间摆着一根筷子，共计5根
- 哲学家平时在思考人生，饿了就会尝试拿起左右手的筷子（一根一根的拿）
- 如果筷子在别人手上，则等待
- 拿起了两根筷子时，哲学家开始进食
- 用餐完毕后放下筷子继续思考
关系分析
设计有三种思路来防止死锁：
- 将拿左右筷子的动作整体设为互斥操作
- 最多只允许四个人拿筷子
- 只允许奇数号的哲学家拿起左边的筷子；偶数号的哲学家拿起右边的筷子
信号量设置
1
2
| semaphore chopstick[5] = {1, 1, 1, 1, 1}; //代表五根筷子的资源
semaphore mutex = 1; //对左右筷子整体资源互斥访问
|
实际代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| Pi(){
while (1){
P(mutex);
P(chopstick[i]); //拿左
P(chopstick[ (i+1) % 5]); //拿右
V(mutex);
吃饭
V(chopstick[i]);
V(chopstick[ (i+1) % 5]);
思考
}
}
|
实现了只有当左右手筷子都可用时才拿起筷子