Sleeping barber problem

description:

The sleeping_barber Problem:

• A barbershop consists of a waiting room with n chairs and the barber room containing the barber chair.
• if there are no customers to be served, the barber goes to sleep.
• if a customer enters the barbershop and all chairs are occupied, then the customer leaves the shop.
• if the barber is busy but chairs are available,then the customer sits in a free chair.
• if the barber is asleep,the customer wakes up the barber.

Solution Method:

Semaphore:

Semaphore name	Init numbers	Target
mutex	1	For mutually exclusive maintenance seat The value of the variable
barber_ready	0	Used to guarantee barber And customer Before and after
customer_ready	0	Used to guarantee barber And customer Before and after
seat(not semaphore)	n	The number of chairs left in the store
arrive	0	Judge whether the customer has gone to the barber

Relation:

Because if there are no chairs in the store , Customers will no longer wait , So we don't set chairs as semaphores .

But chairs are also a resource , You need mutually exclusive allocations , So we used mutex To realize the mutually exclusive access of chairs .

Customer process:

• For customer process , We basically use the logic of temptation and inquiry .
• After entering the store , First try to explore to see if there are any remaining chairs , If you have one, go into the store and sit down , If not, then leave .
• After sitting in a chair , Just send it to the barber customer_ready The signal of , Show that you have been waiting .
• Wait for the barber to send ready The signal of , After receiving the signal, leave your position and go to the barber , Modify location information .

Barber process:

• For the barber process , We basically use to get - Logic of answer .
• The barber has been waiting for the customer to send ready The signal of , If you hear ready And nothing happens at this time , Just respond barber_ready The signal . That is to say, I heard someone say I'm ok , Just call someone over .

Update:

But there's a problem , If the barber cuts very, very fast , When the cutting process is over , If the process is still processing at this time seat The operation of , It will let the next process come directly , There is a problem .

So we introduced arrive Variable , Only after the customer arrives at the location , Will start cutting .

Source Code:

//
// Created by Zza on 2022/4/3.
//

#ifndef DATASTRUCTUREIMPLEMENTINGC_SLEEPING_BARBER_H
#define DATASTRUCTUREIMPLEMENTINGC_SLEEPING_BARBER_H

#include <stdio.h>
#include <unistd.h>
#include <time.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#define CUSTOMER_NUMBER 20
void *customer(void *param);

_Noreturn void *barber(void *param);

int seat_num = 5;

int cus_process_alive = CUSTOMER_NUMBER;
int interval[CUSTOMER_NUMBER] = {
    100, 100, 200, 100, 250, 400, 200,
                                 100, 200, 700, 100, 200, 600, 100,
                                 250, 400, 200, 100, 200, 700};

sem_t customer_ready;
sem_t barber_ready;
sem_t arrived;
sem_t mutex;

int main_barber_problem(int argc, char *argv[]) {
    
    pthread_t barber_id;
    pthread_t client_ids[CUSTOMER_NUMBER];
    sem_init(&mutex,0,1);
    sem_init(&barber_ready,0,0);
    sem_init(&customer_ready,0,0);
    sem_init(&arrived,0,0);
    pthread_create(&barber_id, NULL, barber, NULL);
    for (int i = 0; i < CUSTOMER_NUMBER; i++){
    
        usleep(interval[i]*1000);
        printf("%d: One customer comes, see %d seats left now\n",
               time(NULL), seat_num);
        pthread_create(&client_ids[i], NULL, customer, NULL);
    }
    while(cus_process_alive);
    return 0;
}

int iter=0;
_Noreturn void *barber(void *param) {
    
    int worktime = 500;
    time_t t;
    while(1) {
    
        sem_wait(&customer_ready);
        sem_post(&barber_ready);

        sem_wait(&arrived);
        iter++;
        t = time(NULL);
        printf("%d: Barber start cut the %d hair\n",t,iter);
        usleep(worktime*1000);
        t = time(NULL);
        printf("%d: Barber end cut the %d hair\n",t,iter);

    }
}

void *customer(void *param) {
    
    sem_wait(&mutex);
    if(seat_num > 0){
    
        seat_num --;
        printf("%d: One customer ready, make %d seats left now\n",
               time(NULL), seat_num);
//  Sit down and shout at once 
        sem_post(&customer_ready);
        sem_post(&mutex);

        sem_wait(&barber_ready);
//  After hearing the news, I left my position 
        sem_wait(&mutex);
        seat_num++;
        printf("%d: One customer is to cut, make %d seats left now\n",
               time(NULL), seat_num);
        sem_post(&mutex);
        sem_post(&arrived);

    } else {
    
        printf("%d: One customer leaves with no haircut\n", time(NULL));
        sem_post(&mutex);
    }
    cus_process_alive--;
}

#endif //DATASTRUCTUREIMPLEMENTINGC_SLEEPING_BARBER_H