目录
吸烟者问题
假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉,但是要卷起并抽掉一支烟,抽烟者需要三种材料:烟草、纸和胶水。三个抽烟者中,第一个拥有烟草,第二个拥有纸,第三个拥有胶水。供应者无限地提供三种材料,供应者每次将两种材料放在桌子上,拥有剩下那种材料的卷烟者卷一根烟并抽掉它,并给供应者一个告诉完成信号,供应者就会放另外两种材料在桌上,这种过程一直重复。
解题步骤
该问题的本质依然是“生产者-消费者”问题,可以用“生产者-消费者”问题的思路去解决。
Step 1. 有几类进程
生产者(){
while(1){
}
}
吸烟者1(烟草){
while(1){
}
}
吸烟者2(纸){
while(1){
}
}
吸烟者3(胶水){
while(1){
}
}
Step 2. 用中文描述动作
生产者(){
while(1){
收到从吸烟者3发来的信号;
在桌上提供纸和胶水;
收到从吸烟者1发来的信号;
在桌上提供烟草和胶水;
收到从吸烟者2发来的信号;
在桌上提供烟草和纸;
}
}
吸烟者1(烟草){
while(1){
从桌子上取走纸和胶水;
吸烟;
向生产者发送一个信号;
}
}
吸烟者2(纸){
while(1){
从桌子上取走烟草和胶水;
吸烟;
向生产者发送一个信号;
}
}
吸烟者3(胶水){
while(1){
从桌子上取走烟草和纸;
吸烟;
向生产者发送一个信号;
}
}
Step 3. 添加 PV 操作,用中文描述里面的操作
【注】
//
表示新加入的代码。
(1)生产者
生产者(){
while(1){
P(从吸烟者3发来的信号); //
在桌上提供纸和胶水;
P(从吸烟者1发来的信号); //
在桌上提供烟草和胶水;
P(从吸烟者2发来的信号); //
在桌上提供烟草和纸;
}
}
吸烟者1(烟草){
while(1){
从桌子上取走纸和胶水;
吸烟;
V(吸烟者1向生产者发送信号); //
}
}
吸烟者2(纸){
while(1){
从桌子上取走烟草和胶水;
吸烟;
V(吸烟者2向生产者发送信号); //
}
}
吸烟者3(胶水){
while(1){
从桌子上取走烟草和纸;
吸烟;
V(吸烟者3向生产者发送信号); //
}
}
(2)吸烟者 1
生产者(){
while(1){
P(从吸烟者3发来的信号);
在桌上提供纸和胶水;
V(桌子上有纸和胶水); //
P(从吸烟者1发来的信号);
在桌上提供烟草和胶水;
P(从吸烟者2发来的信号);
在桌上提供烟草和纸;
}
}
吸烟者1(烟草){
while(1){
P(桌子上有纸和胶水吗?有-1,没有阻塞); //
从桌子上取走纸和胶水;
吸烟;
V(吸烟者1向生产者发送信号);
}
}
吸烟者2(纸){
while(1){
从桌子上取走烟草和胶水;
吸烟;
V(吸烟者2向生产者发送信号);
}
}
吸烟者3(胶水){
while(1){
从桌子上取走烟草和纸;
吸烟;
V(吸烟者3向生产者发送信号);
}
}
(3)吸烟者 2、吸烟者 3
跟上面是类似的:
生产者(){
while(1){
P(从吸烟者3发来的信号);
在桌上提供纸和胶水;
V(桌子上有纸和胶水+1); //
P(从吸烟者1发来的信号);
在桌上提供烟草和胶水;
V(桌子上有烟草和胶水+1); //
P(从吸烟者2发来的信号);
在桌上提供烟草和纸;
V(桌子上有烟草和纸+1); //
}
}
吸烟者1(烟草){
while(1){
P(桌子上有纸和胶水吗?有-1,没有阻塞); //
从桌子上取走纸和胶水;
吸烟;
V(吸烟者1向生产者发送信号);
}
}
吸烟者2(纸){
while(1){
P(桌子上有烟草和胶水吗?有-1,没有阻塞); //
从桌子上取走烟草和胶水;
吸烟;
V(吸烟者2向生产者发送信号);
}
}
吸烟者3(胶水){
while(1){
P(桌子上有烟草和纸吗?有-1,没有阻塞); //
从桌子上取走烟草和纸;
吸烟;
V(吸烟者3向生产者发送信号);
}
}
(4)缓冲区
每次桌子上只放一件组合,不需要互斥锁。
Step 4. 检查是否出现死锁
不会发生死锁。
Step 5. 定义信号量
offer
信号量均表示产品(材料组合)的数量,初始值设为 0。
finish
信号量均为前驱后继的关系,因此初始值设为 0。
信号量 offer1 = 0;
信号量 offer2 = 0;
信号量 offer3 = 0;
信号量 finish1 = 0;
信号量 finish2 = 0;
信号量 finish3 = 0;
生产者(){
while(1){
P(finish3);
在桌上提供纸和胶水;
V(offer1);
P(finish1);
在桌上提供烟草和胶水;
V(offer2);
P(finish2);
在桌上提供烟草和纸;
V(offer3);
}
}
吸烟者1(烟草){
while(1){
P(offer1);
从桌子上取走纸和胶水;
吸烟;
V(finish1);
}
}
吸烟者2(纸){
while(1){
P(offer2);
从桌子上取走烟草和胶水;
吸烟;
V(finish2);
}
}
吸烟者3(胶水){
while(1){
P(offer3);
从桌子上取走烟草和纸;
吸烟;
V(finish3);
}
}
网上的代码(与王道的类似)
网上的代码是随机放材料,我写的代码是按顺序依次放材料。
-
关系分析。供应者与三个抽烟者分别是同步关系。由于供应者无法同时满足两个或 以上的抽烟者,三个抽烟者对抽烟这个动作互斥。
-
整理思路。这里有四个进程。供应者作为生产者向三个抽烟者提供材料。
-
信号量设置。信号量 offer1、offer2、offer3 分别表示烟草和纸组合的资源、烟草和 胶水组合的资源、纸和胶水组合的资源。信号量 finish 用于互斥进行抽烟动作。
int random; //存储随机数
semaphore offer1 = 0; //定义信号量对应烟草和纸组合的资源
semaphore offer2 = 0; //定义信号量对应烟草和胶水组合的资源
semaphore offer3 = 0; //定义信号量对应纸和胶水组合的资源
semaphore finish = 0; //定义信号量表示抽烟是否完成
//供应者
while(1){
random = 任意一个整数随机数;
random = random % 3;
if (random == 0)
V(offerl) ; //提供烟草和纸
else if (random == 1)
V(offer2); //提供烟草和胶水
else
V(offer3) //提供纸和胶水
// 任意两种材料放在桌子上,并等待抽烟者抽烟后将 finish 设置为 1
P(finish);//抽烟者已经使用完材料,需要继续提供材料
}
//拥有烟草者
while(1){
P (offer3);
// 拿纸和胶水,卷成烟,抽掉;
V(finish);
}
//拥有纸者
while(1){
P(offer2);
// 烟草和胶水,卷成烟,抽掉;
V(finish);
}
//拥有胶水者
while(1){
P(offer1);
// 拿烟草和纸,卷成烟,抽掉;
v(finish);
}
标签:吸烟者,PV,操作系统,桌子,信号量,while,胶水,烟草
From: https://www.cnblogs.com/Mount256/p/16837782.html