理发师问题:理发店理有一位理发师、一把理发椅和5把供等候理发的顾客坐的椅子。如果没有顾客,理发师便在理发椅上睡觉。一个顾客到来时,它必须叫醒理发师,如果理发师正在理发时又有顾客来到,则如果有空椅子可坐,就坐下来等待,否则就离开。
之前的解法存在问题,因为试图获得一个信号量的等待队列在linux中是不太理智的行为,麻烦很大,所以我放弃了这一尝试。
目前解法,设置顾客15名,在15秒内分散来到,理发时间3秒,测试用例已完善。
#include <pthread.h> #include <stdio.h> #include <unistd.h> #include <stdlib.h> #include <semaphore.h> #include <fcntl.h> #include <assert.h> #define N 15 typedef struct{ int num; int time; }arg; int b[]={1,10,3,9,4,8,5,6,7,6,4,6,7,8}; //信号量和控制量定义 sem_t barbeready;//为0表示理发师未准备好,顾客需等待;为1表示可以服务 sem_t accessseats;//每一个线程都需要在开头申请,在结尾释放,与临界区类似,为1表示可以申请 sem_t custready;//为0表示没有顾客,理发师睡觉;不为0表示有顾客 sem_t mutex; int current=-1; int numofseats=5;//共5个空位 //理发师线程 void*barber(){ while(1){ sem_wait(&custready);//等待顾客到来 sem_wait(&accessseats);//进入临界区 numofseats+=1;//座位增加 sem_post(&barbeready);//理发师做好准备 sem_post(&accessseats);//离开临界区 sem_wait(&mutex); printf("barber is serving %d\n",current);//一个顾客接受服务 sleep(3);//3秒钟理发时间 printf("%d over\n",current); } return NULL; } void*customer(void*args){ int*arg=(int*)args; if(arg[0]%3==0)sleep(0); else if(arg[0]%3==1)sleep(10); else sleep(arg[1]); sem_wait(&accessseats);//进入临界区 for(int i=0;i<=arg[0];i++)printf("\t"); printf("come\n",arg[0]);//宣告到来 if(numofseats>0){//判断是否有空位 numofseats-=1; sem_post(&custready);//宣告顾客到来 sem_post(&accessseats);//离开临界区 for(int i=0;i<=arg[0];i++)printf("\t"); printf("waiting\n",arg[0]); sem_wait(&barbeready);//等待理发师准备 current=arg[0]; for(int i=0;i<=arg[0];i++)printf("\t"); printf("served\n",arg[0]); sem_post(&mutex); } else{ sem_post(&accessseats);//没有座位,直接离开临界区 for(int i=0;i<=arg[0];i++)printf("\t"); printf("leave\n",arg[0]); } return NULL; } int main(){ //以下对信号量进行初始化 sem_init(&barbeready,0,0); sem_init(&accessseats,0,1); sem_init(&custready,0,0); sem_init(&mutex,0,0); printf("barber\t"); for(int i=0;i<N;i++)printf("%d\t",i); printf("\n"); //创建1个理发师和N个顾客线程 pthread_t*barberid=malloc(sizeof(pthread_t)); pthread_create(barberid,NULL,barber,NULL); arg*a=malloc(N*sizeof(arg)); for(int i=0;i<N;i++){ a[i].num=i; a[i].time=b[i]; } pthread_t*customerid=malloc(N*sizeof(pthread_t)); for(int i=0;i<N;i++)pthread_create(&customerid[i],NULL,customer,&(a[i])); sleep(36); return 0; }
参考了https://en.wikipedia.org/wiki/Sleeping_barber_problem。部分输出如下:
barber 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 come waiting come waiting served barber is serving 0 come waiting come waiting come waiting come waiting 0 over served barber is serving 3 come waiting 3 over served barber is serving 6 come waiting come leave 6 over served barber is serving 9 come waiting come leave come leave come leave come leave 9 over served barber is serving 12 12 over served barber is serving 2 2 over served barber is serving 11 11 over served barber is serving 8 8 over served barber is serving 4 4 over