|
#2
fangdong652011-05-12 18:44
|
问题重述：
一家理发店有一间有n把椅子的等待室和一把理发椅的理发室。如果没有顾客，理发师就去睡觉。如果顾客来时所有的椅子都有人，那么顾客将会离去。如果理发师在忙，而又有空闲的椅子，那么顾客会坐在其中一个空闲的椅子上。如果理发师在睡觉，顾客会摇醒他。
我的分析如下：
1、“理发店有一间有n把椅子的等待室和一把理发椅的理发室”分析知，这n把等待室的椅子和一把理发室的椅子是临界资源。
2、“理发店有一间有n把椅子的等待室”，等待的椅子明显有限制，说明顾客之间有互斥关系。
“如果顾客来时所有的椅子都有人，那么顾客将会离去。”说明了顾客在竞争椅子时，若竞争失败，则放弃竞争。
3、“如果没有顾客，理发师就去睡觉。”&&“如果理发师在忙，而又有空闲的椅子，那么顾客会坐在其中一个空闲的椅子上。”说明理发师必须等有顾客才能开始理发，而顾客必须等理发师有空（相对的有空，比如理发师在睡觉那么理发师是真的有空，如果是正常排队轮到自己了，那么理发师是相对有空（自己相对其他等待的人来说）），由此可知，理发师与顾客之间还有一个同步问题。
先分析顾客之间互斥的实现，考虑到这是多个顾客等待多把椅子，即资源有限，顾客之间竞争。第一种方案可以类比生产者、消费者问题，利用一对信号量分别表示等待座位的满位和空位人数，但是“如果顾客来时所有的椅子都有人，那么顾客将会离去。”说明顾客竞争不到资源必须放弃竞争，而不能一直等待，显然利用生产者消费者模型，顾客一定会无限期等待直到等到资源，显然该方案应该被否定。在类比读写者问题，可以用一个全局变量来表明等待座位上的人数，这样的话，新顾客可以根据这个变量的值判断等待室的人是否已经满了，从而决定是否继续等待。从而根据全局变量的值实现顾客之间的互斥。另外，只要有全局变量，我们就应注意到这个全局变量是一种临界资源，所以就应该考虑到临界资源访问的互斥问题，所以这里需要一个信号量（设为mutex），用来实现全局变量访问间的互斥。
再来考虑理发师与顾客之间的同步问题。
理发师必须等待有顾客才开始工作，否则睡觉(此处睡觉，可以用理发师在等待一个信号量符合要求实现)，所以考虑为顾客的人数设置一个信号量，每次理发师提取顾客进行理发之前必须先对该信号量进行判断，只有该信号量符合要求（有顾客）时，才进行才进行从等待室提取顾客，理发操作。否则无限等待该信号成立，即睡觉。
再来分析顾客对理发师的操作，只有等待室的人没有坐满时，顾客才有可能对理发师有操作。若理发师在忙，则顾客等待（等待的人数变化），若理发师在睡觉，则唤醒理发师（由于上面理发师操作中实现理发师的睡觉操作是通过等待有顾客实现的，所以此处不用刻意去对没有等待顾客，理发师在睡觉的情况单独处理，只需使顾客人数信号量++，即可唤醒理发师（如果在睡眠的话））。
另外，为了方便用户看出内部运行的过程，采用了共享变量Is_Sleeping,根据理发师的不同状态选择不同的输出模式。
最后，设置信号量Wait_Leave用来使等待过程中的顾客不要离开，由理发师决定理完发的客户可以离开。
附源代码（linux下的实现）如下：
#include <sys/mman.h>
#include <sys/types.h>
#include <linux/sem.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdio.h>
#include <errno.h>
#include <time.h>
#define N 5 //表示等待室里面的椅子个数
#define M 20 //表示平均一天到达顾客数
//设置信号量，有如下
int Custom;//所有到达的顾客，包括正在被理发的顾客，所以一般情况下，Custom比Wait_Person大1
int Mutex;//用于实现全局变量Wait——preson访问的互斥
int Wait_Leave;//等待离开信号量，用来表示几个顾客等待离开，只要理发师为其理发完毕，他就可以离开了
//全局变量
int * Is_Sleeping;//当前理发师是否在睡觉
void print1(int Wait_person)
{
if(!Wait_person)//没有顾客
{
printf("临时没有顾客了，理发师开始睡觉\n");
*Is_Sleeping=1;
}
}
void print2(int ID)
{//虽然此处有全局变量Is_Sleeping的访问，但是不用在利用例外一个信号量将其包起来，因为print2的调用地方只有一个，已经用Mutex包起来了，与另一出Is_Sleeping的改变处对应的正好
if(*Is_Sleeping)
{
printf("新顾客%d到来，发现理发师正在睡觉，于是唤醒理发师\n",ID);//唤醒理发师
*Is_Sleeping=0;//说明已经被唤醒了
}
else
printf("新顾客%d到来，发现等待室仍然有座位，于是坐下等待\n",ID);//等待
}
int main()
{
struct sembuf P,V;
union semun arg;
int Pid,i=0;
//声明共享内存//临界区
int * Wait_Person;//在等待室等待的人数，初始值设为0，表示开始无人等待
//映射共享内存
Wait_Person=(int * )mmap(NULL,sizeof(int),PROT_READ|PROT_WRITE,MAP_SHARED|MAP_ANONYMOUS,-1,0);//在等待室等待的人数，初始值设为0，表示开始无人等待
*Wait_Person=0;
Is_Sleeping=(int * )mmap(NULL,sizeof(int),PROT_READ|PROT_WRITE,MAP_SHARED|MAP_ANONYMOUS,-1,0);//当前理发师是否在睡觉
*Is_Sleeping=0;
//创建信号量
Custom=semget(IPC_PRIVATE,1,IPC_CREAT|00666);
Mutex=semget(IPC_PRIVATE,1,IPC_CREAT|00666);
Wait_Leave=semget(IPC_PRIVATE,1,IPC_CREAT|00666);
//给对应的信号量设置初值
arg.val = 0;//开始时理发店里面没有顾客
if(semctl(Custom,0,SETVAL,arg)==-1)
perror("semctl semeval error");
arg.val = 1;//用于访问全局变量Wait——preson 的互斥
if(semctl(Mutex,0,SETVAL,arg)==-1)
perror("semctl semeval error");
arg.val = 0;//开始没有顾客，也就没有顾客等待离开
if(semctl(Wait_Leave,0,SETVAL,arg)==-1)
perror("semctl semeval error");
//初始化
V.sem_num=0; //semaphore number
V.sem_op=1; //semaphore operaion add 1
V.sem_flg=SEM_UNDO;
P.sem_num=0;
P.sem_op=-1;
P.sem_flg=SEM_UNDO;
Pid=fork();
if(Pid==0)
{//理发师进程
while(1)
{
semop(Mutex,&P,1);//P（Mutex）
print1(*Wait_Person);//进行一些输出工作，判断当前理发师是否有可能睡觉，如果睡觉的话输出理发师正在睡觉
semop(Mutex,&V,1);//V（Mutex）
semop(Custom,&P,1);//等待理发店里面来顾客，有顾客进行下面一系列的动作，如果没有操作则无限等待（睡觉）
//首先从等待室里面提取一个顾客
semop(Mutex,&P,1);//P（Mutex）
(*Wait_Person)--;//提取顾客
semop(Mutex,&V,1);//V（Mutex）
//给该顾客理发
printf("理发师开始理发 ！ \n");
sleep(3);//理发
//当前顾客可以离开了
printf("理发完毕，换下一位顾客 ！ \n");
semop(Wait_Leave,&V,1);//V（Wait_Leave）
}
printf("******************理发师为最后一位顾客理发完毕，理发店准备关门！**********************\n");
}
else
{//顾客进程
while(1)//假设一天最多来M 个顾客
{
if(Pid==0)
{//刚创建的新顾客
semop(Mutex,&P,1);//P（Mutex） 因为要访问全局变量
if((*Wait_Person)>=N)//新顾客到来，发现等待室人已经满了，顾客离开
{
semop(Mutex,&V,1);//V（Mutex）
printf("新顾客%d到来，发现等待室人已经满了，顾客离开\n",getpid());//直接离开
exit(0);//顾客离开
}
else
{//正常，理发店还有空位
print2(getpid());//跟据当前情况，选择不同的输出语句，方便直观的查看程序运行过程。 若原先没人（说明理发师在睡觉），则唤醒理发师，否则，等待
(*Wait_Person)++;//直接离开
semop(Mutex,&V,1);//V（Mutex）
semop(Custom,&V,1);//顾客人数++ 如果此时理发师正在Custom的等待队列，此操作会唤醒理发师
//等待离开的顾客会多1个人
semop(Wait_Leave,&P,1);
printf("顾客%d理发完毕，离开理发店\n",getpid());//直接离开
exit(0);//顾客离开
}
}
else
{
sleep(rand()%100/30.0);//每个两个顾客到达的时间间隔不一定
if(i<M)//假设一天最多来M 个顾客
{
Pid=fork();//在主进程里面不停的创建新的子进程
i++;
}
else
break;
}
}
if(i==M)
{
wait(NULL);//最后一次创建子进程后要在 所有其创建的子进程结束后输出程序终止提示……
}
}
return 0;
}
运行结果解图如下：
只有本站会员才能查看附件，请 登录
每次每个理发师总是莫名的为两个顾客同时理完发，不知为啥，我看过，由于平均两个顾客到达的时间差正好是理发师理发所用时间的一半，所以平均每次理发师有两个顾客到达，期间，第2n+1个顾客应该正常，但是第2n+2个顾客一到达就直接获得Wait_Leave信号，不再在P（Wait_Leave）处等待，直接离开，当然第2n+1个也离开了，这样的话平均理发师理10发，20个顾客离开。另外，第2n+2个顾客没有进行P（Custom）操作，导致最后理发师在P（Custom）处等待，但是由于Wait_Person为5，达到了最大容量，所以每次刚到的顾客都会直接离开，表示很困惑，所有对Custom和Wait_Person的操作都是同步的，最后两者的值竟然不一样了？
哪位大侠救救我啊……