【实战3】理发师问题
理发店有一位理发师、一把理发椅及三把供等候理发的顾客坐的椅子。如果没有顾客,理发师就去睡觉。如果顾客来时所有的椅子都有人,那么顾客就离去。如果理发师在忙而有空闲的椅子,那么顾客就会坐在其中的一个空闲的椅子上。如果理发师在睡觉,顾客会唤醒他。请利用信号量(semaphores),写个程序来协调理发师和顾客进程。【浙江大学2007】
int count=0;
//记录理发店里的顾客数量
semaphore mutex=1;
//用于互斥访问count变量所用的信号量
semaphore barber_chair=0;
//
semaphore wait_chair=3;
//顾客等待时可坐的椅子
semaphore ready=0;
//坐在等候椅子上等待理发的顾客数量
Barber(){
//理发师进程
while(1){
wait(ready);
//是否有顾客在等待理发,没有则阻塞
signal(barber_chair);
//请等待时间最长的顾客坐到理发椅上
signal(wait_chair);
//坐到理发椅上的顾客让出一个等待时可坐的椅子
barbering
//给顾客理发
}
}
Customer(){
//顾客进程i
{
wait(mutex);
if(count>=4){
//如果理发店已经有四个顾客了
signal(mutex);
leave //走人
}
else{
//理发店里顾客不足4个
count++;
//更新顾客人数
signal(mutex);
}
wait(wait_chair);
//先请求坐等待时坐的椅子
signal(ready);
//告诉理发师又有一位顾客准好了,等待理发
wait(barber_chair);
//再请求坐理发椅
be barbered
wait(mutex);
count--;
//更新店里的顾客人数
signal(mutex);
}
}
【练习1】 如图所示,有多个PUT操作同时向BUFF1放数据,有一个MOVE操作不断地将BUFF1的数据移到BUFF2,有多个GET操作不断地从BUFF2中将数据取走。BUFF1的容量为m,BUFF2的容量是n,PUT、MOVE、GET每次操作一个数据,在操作的过程中要保证数据不丢失。试用P、V原语协调PUT、MOVE的操作,并说明每个信号量的含义和初值。
PUTMOVEGETBuff1Buff2
进程操作图
【分析】这里存在两个一般意义的“生产者—消费者”问题,PUT(生产者)与MOVE(消费者)之间,需要设置三个信号量;MOVE(生产者)与GET(消费者)之间,需要设置三个信号量。PUT进程套用生产者进程即可,MOVE进程只有在Buff1有新数据且Buff2有空闲区的时候才移动数据,GET进程套用消费者进程即可。
答案:设置6个信号量full1、empty1、B-M1、full2、empty2、B-M2,它们的含义和初值如下:
1) full1表示Buff1是否有数据,初值为0;
2) empty1表示Buff1有空间,初值为m;
3) B-M1表示Buff1是否可操作,初值为1;
4) Full2表示Buff2是否有数据,初值为0;
5) Empty2表示Buff2有空间,初值为n;
6) B-M2表示Buff2是否可操作,初值为1;
{ repeat P(empty1); /*判断Buff1是否有空间,没有则等待 */ P(B-M1); /*是否可操作Buff1*/ PUT; V(B-M1); /*设置Buff1可操作标志 */ V(full1); /*设置Buff1有数据的标志 */ until false } { repeat P(full1); P(empty2);P(B-M1);P(B-M2);MOVE; V(B-M1);V(B-M2);V(empty1);V(full2); until false /*判断Buff1是否有数据,没有则等待*/ /*判断Buff2是否有空间,没有则等待*/ /*是否可操作Buff1 */ /*是否可操作Buff2 */ /*设置Buff1可操作标志*/ /*设置Buff2可操作标志*/ /*设置Buff1有空间标志*/ /*设置Buff2有数据标志*/ } { repeat P(full2); /*判断Buff2是否有数据,没有则等待 */ P(B-M2); /*是否可操作Buff2*/ GET; V(B-M2); /*设置Buff2可操作标志 */ V(empty2); /*设置Buff2有空间的标志 */ until false 因篇幅问题不能全部显示,请点此查看更多更全内容