登录
理发师问题：理发店理有一位理发师、一把理发椅和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
