sleeping_barber.c

/* In computer science, the sleeping barber problem is a classic inter-process communication and synchronization problem between multiple operating system processes. The problem is analogous to that of keeping a barber working when there are customers, resting when there are none, and doing so in an orderly manner.

The analogy is based upon a hypothetical barber shop with one barber. The barber has one barber's chair in a cutting room and a waiting room containing a number of chairs in it. When the barber finishes cutting a customer's hair, he dismisses the customer and goes to the waiting room to see if there are others waiting. If there are, he brings one of them back to the chair and cuts their hair. If there are none, he returns to the chair and sleeps in it.

Each customer, when they arrive, looks to see what the barber is doing. If the barber is sleeping, the customer wakes him up and sits in the cutting room chair. If the barber is cutting hair, the customer stays in the waiting room. If there is a free chair in the waiting room, the customer sits in it and waits their turn. If there is no free chair, the customer leaves.

Based on a naïve analysis, the above decisions should ensure that the shop functions correctly, with the barber cutting the hair of anyone who arrives until there are no more customers, and then sleeping until the next customer arrives. In practice, there are a number of problems that can occur that are illustrative of general scheduling problems.  See <https://en.wikipedia.org/wiki/Sleeping_barber_problem> for details. */

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <semaphore.h>
#include <time.h>
#include <sys/types.h>
#include <sys/time.h>

void *barber_function(void *idp);
void *customer_function(void *idp);
void serve_customer();
void *make_customer_function();
    
/* Mutex */
pthread_mutex_t srvCust;

/* Semaphores */
sem_t barber_ready; 
sem_t customer_ready;
sem_t modifySeats;

/* Inputs */
int chair_cnt;
int total_custs;

int available_seats;
int no_served_custs = 0;
time_t waiting_time_sum;

void *barber_function(void *idp)
{    
    int counter = 0;
    
    while (1)
    {
        /* Lock semaphore "customer_ready" - try to get a customer or sleep if there is none */
        sem_wait(&customer_ready);

        /* Lock semaphore "modifySeats" - try to get access to seats */
        sem_wait(&modifySeats);

        /* Increment by 1 the available seats */
        available_seats++;

        /* Unlock semaphore "modifySeats" */
        sem_post(&modifySeats);

        /* Unlock semaphore "barber_ready" - set barber ready to serve */
        sem_post(&barber_ready);        

        /* Lock mutex "srvCust" - protect service by the same barber from other threads */
        pthread_mutex_lock(&srvCust);

        /* Serve customer */
        serve_customer();    

        /* Unlock mutex "srvCust" - finished service */
        pthread_mutex_unlock(&srvCust);
        
        printf("Customer was served.\n");
	    
        counter++; 
        if (counter == (total_custs - no_served_custs))
            break;
    }
    pthread_exit(NULL);    
}

void *customer_function(void *idp)
{  
    struct timeval start, stop;
     
    /* Lock semaphore "modifySeats" */
    sem_wait(&modifySeats); 

    /* If there is available seat */
    if (available_seats >= 1)
    {
        /* Occupy a seat */
        available_seats--;

        printf("Customer[pid = %lu] is waiting.\n", pthread_self());
        printf("Available seats: %d\n", available_seats);
        
        /* Start waiting-time counter */
        gettimeofday(&start, NULL);
           
        /* Unlock semaphore "customer_ready" - set the customer ready to be served */
        sem_post(&customer_ready);

        /* Unlock semaphore "modifySeats" */
        sem_post(&modifySeats);         

        /* Lock semaphore "barber_ready" - wait for barber to get ready */
        sem_wait(&barber_ready); 

        /* Stop waiting-time counter */
        gettimeofday(&stop, NULL);
        
        double sec = (double)(stop.tv_usec - start.tv_usec) / 1000000 + (double)(stop.tv_sec - start.tv_sec);
        
        /* Assign the time spent to global variable (ms) */
        waiting_time_sum += 1000 * sec;
        printf("Customer[pid = %lu] is being served. \n", pthread_self());        
    }
    else
    {
        /* Unlock semaphore "modifySeats" */
        sem_post(&modifySeats);
        no_served_custs++;
        printf("A Customer left.\n");
    }
        
    pthread_exit(NULL);
}

void serve_customer() {
    /* Random number between 0 and 400 (miliseconds) */
    int s = rand() % 401; 
	
    /* Convert miliseconds to microseconds */
    s = s * 1000; 
    usleep(s);
}

void *make_customer_function() {
    int tmp;   
    int counter = 0;

    while (counter < total_custs)
    {
        /* Declare and create a customer thread */
        pthread_t customer_thread;
	
        tmp = pthread_create(&customer_thread, NULL, (void *)customer_function, NULL);  
	
        if (tmp)
            printf("Failed to create thread.");
        
        /* Increment the counter */
        counter++;
            
        /* Sleep for 100ms before creating another customer */
        usleep(100000);
    }
}

int main() {	
    /* Initialization, should only be called once */
    srand(time(NULL));   

    /* Barber 1 thread */
    pthread_t barber_1;

    /* Thread that creates customers */
    pthread_t customer_maker;

    int tmp;

    /* Initialize mutex */
    pthread_mutex_init(&srvCust, NULL);

    /* Initialize semaphores */
    sem_init(&customer_ready, 0, 0);
    sem_init(&barber_ready, 0, 0);
    sem_init(&modifySeats, 0, 1);
    
    printf("Please enter the number of seats: \n");
    scanf("%d", &chair_cnt);
    
    printf("Please enter the total customers: \n");
    scanf("%d", &total_custs);
    
    available_seats = chair_cnt; 
    
    /* Create barber thread */
    tmp = pthread_create(&barber_1, NULL, (void *)barber_function, NULL);  
	
    if (tmp)
        printf("Failed to create thread."); 
    
    /* Create customer_maker thread */
    tmp = pthread_create(&customer_maker, NULL, (void *)make_customer_function, NULL);  
	
    if (tmp)
        printf("Failed to create thread."); 
     
    /* Wait for threads to finish */
    pthread_join(barber_1, NULL);
    pthread_join(customer_maker, NULL);
        
    printf("\n------------------------------------------------\n");
    printf("Average customers' waiting time: %f ms.\n", (waiting_time_sum / (double) (total_custs - no_served_custs)));
    printf("Number of customers that were forced to leave: %d\n", no_served_custs);    	
}