问题 问答题

考虑有三个吸烟者进程和一个经销商进程的系统中,每个吸烟者连续不断地制作烟卷并将其做好的烟卷消费掉(即吸烟)。制烟和吸烟过程需要烟草、烟纸和火柴三种原料。这三个吸烟者自己分别掌握有烟草、烟纸和火柴中的一种。经销商能源源不断地提供上述三种原料,每次经销商会提供上述三种原料中的任意两种,当某个吸烟者发现经销商提供的原料恰好是自己所需的时候,该吸烟者会取走那两种原料,与他自己拥有的原料一起,开始制烟和吸烟。经销商发现原料被取走了就会继续提供任意两种原料,如此反复。试设计一个使经销商和吸烟者同步的算法,并用C语言编写程序。

答案

参考答案:

semaphore Stp = 0; //烟草和纸的组合信号量
semaphore Spm = 0; //烟纸和火柴的组合信号量
semaphore Stm = 0; //烟草和火柴的组合信号量
semaphore buffer = 1; //经销商用于放置原料的缓冲区信号量
main() //主程序开始
cobegin { //并发进程示意(不要遗忘)
smokert(void) //第一个拥有烟草的吸烟者的进程
while(true){ //进程被调度
P(Spm); //有烟纸和火柴吗
fatch_paper_match(); //取烟纸和火柴
V(buffer); //缓冲区可以用了
make_smoke(); } //制烟和吸烟
smokerp(void) //第二个拥有烟纸的吸烟者的进程
while(true){ //进程被调度
P(Stm); //有烟草和火柴吗
fatch_tobacco_match(); //取烟草和火柴
V(buffer); //缓冲区可以用了
make_smoke(); } //制烟和吸烟
smokerm(void) //第三个拥有火柴的吸烟者的进程
while(true){ //进程被调度
P(Stp); //有烟草和烟纸吗
fatch_tobacco_paper(); //取烟草和烟纸
V(buffer); //缓冲区可以用了
make_smoke(); } //制烟和吸烟
agency(void) //经销商供货的进程
while(true){ //进程被调度
int item; //局部变量,用于供货时货物识别
P(buffer); //缓冲区空闲吗
item = put_material(); //放置原料,item为其标识
if(item = = p_m) //如果放置的是烟纸和火柴两种原料
V(Spm); //置烟纸和火柴的组合信号量
else //然而
if(item = = t_m) //如果放置的是烟草和火柴两种原料
V(Stm); //置烟草和火柴的组合信号量
else //然而
V(Stp); //置烟草和烟纸的组合信号量
}coend //并发结束

解析: 吸烟者问题也是经典的进程同步问题,其特点在于信号量的设置,本题的关键问题是判断有几个临界资源。烟草、烟纸和火柴三种原料并不能简单地看成是三种临界资源,因为它们并不是以单独的形式被三个吸烟者进程所竞争,而是以固定的组合被三个进程所申请,因此可以考虑如下设置:
三个信号量Stp、Spm和Stm分别代表三种原料组合,即,Stp表示烟草和纸的组合信号量,Spm表示纸和火柴的组合信号量,Stm表示烟草和火柴的组合信号量,初值均为0。
经销商一次只能提供一种组合,可以看作是放一个产品的缓冲区,资源量为一个组合,于是我们设置缓冲区的资源信号量为buffer,初值为1。由于该资源量为1,故可以同时作为互斥量来使用,可以省略对缓冲区操作的互斥信号量。
本题还有一个特点就是经销商在提供原料时是随机的,预先并不知道经销商会放什么原料,只有在提供以后才知道。所以在对信号量操作时必须预先搞清楚到底是放了什么原料的组合,再对相应的信号量操作。这在经销商进程中有所体现。
吸烟者问题可能出现的错误是将每一个资源定义一个信号量,然后再来编写代码。例如:
semaphore St = 0; //烟草的信号量
semaphore Sp = 0; //烟纸的信号量
semaphore Sm = 0; //火柴的信号量
semaphore buffer=1; //经销商用于放置原料的缓冲区信号量
main() //主程序开始
cobegin { //并发进程示意(不要遗忘)
smokert(void) //第一个拥有烟草的吸烟者的进程
while(true){ //进程被调度
P(Sp); //有烟纸吗①
P(Sm); //有火柴吗②
fatch_paper_match(); //取烟纸和火柴
V(buffer); //缓冲区可以用了
make_smoke(); } //制烟和吸烟
smokerp(void) //第二个拥有烟纸的吸烟者的进程
while(true){ //进程被调度
P(St); //有烟草吗
P(Sm); //有火柴吗③
fatch_tobacco_match(); //取烟草和火柴
V(buffer); //缓冲区可以用了
make_smoke(); } //制烟和吸烟
smokerm(void) //第三个拥有火柴的吸烟者的进程
while(true){ //进程被调度
P(St); //有烟草吗
P(Sp); //有烟纸吗④
fatch_tobacco_paper(); //取烟草和烟纸
V(buffer); //缓冲区可以用了
make_smoke(); } //制烟和吸烟
agency(void) //经销商供货的进程
while(true){ //进程被调度
int m1, m2; //局部变量,用于供货时货物识别
P(buffer); //缓冲区空闲吗
put_material(m1, m2); //放置二种原料,m1,m2为原料标识
if(m1 = = paper) //如果其中之一放置的是烟纸
V(Sp); //置烟纸的信号量
else //然而
if(m1 = = tobacco) //如果放置的是烟草
V(St); //置烟草的信号量
else //然而
V(Sm); //置火柴的信号量
if(m2 = = paper) //如果另一种放置的是烟纸
V(Sp); //置烟纸的信号量
else //然而
if(m2 = = tobacco) //如果放置的是烟草
V(st); //置烟草的信号量
else //然而
V(sm); //置火柴的信号量
}coend //并发结束
这种做法的错误在于:由于对信号量的操作分为两步,所以,本来的一次原子操作的特性就被破坏了。例如在上例中,若经销商在缓冲区放置的是烟纸和烟草,那么信号量Sp和St就为1,若此时拥有烟草的吸烟者进程被调度,那么当它执行到语句①时可以顺利推进,此时信号量Sp变为0。继续执行下一条语句②时,由于不满足要求而阻塞。
经过轮转,进程切换到拥有火柴或者拥有烟纸的吸烟者进程,它们均由于信号量不满足要求而阻塞,因为此时只有St为1,Sp和Sm均为0,不能满足上述两个进程需要两次P操作的要求,它们均会阻塞在③或④的语句上,此时,尽管缓冲区里有两种原材料,但是,三个吸烟者和经销商均不能向前推进,进程死锁。

单项选择题
单项选择题