理发师问题
匿名2023/07/31 19:49:40提问
    2018lecture18student
408

 理发师问题:理发店理有一位理发师、一把理发椅和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
回答(5
    推荐问答
      Simple Empty
      暂无数据