Programming classics: The Sleeping Barber Problem

One of the classic problems for parallel computing is the sleeping barber. According to the story, we have a barber shop, with a single chair and a single barber, which must attend to all the clients who arrive. The barber always falls asleep when there are no waiting clients, who upon arrival sit in a row of chairs. If a client arrives and the barber is sleeping, the client wakes him up and starts shaving him, but if he is attending to another client, he stays in his chair until the barber vacates.

In parallel programming, the critical zone is that shared resource that should only be accessed by a single thread at a time, to avoid competition for the resource, and for this the sleeping barber has been one of the classic problems that uses exclusion mechanisms mutual to solve the problem of competition for a resource within the critical region. For this, semaphores are used to protect the shared variable and thus prevent it from being overwritten, producing unwanted results in the rest of the threads.

C code for the sleeping barber problem

Below is the code for how a concurrency problem could be solved using the sleeping barber method. For this example of concurrency we make use of the C language and the pthreads thread handling library, in addition to the semaphore library. Efforts have been made to show the proper documentation for the code to help the reader understand each part of the code.

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h> 
// Clients
#define MAX_CLIENTS 25 

void *client(void *num);
void *barber(void *num); 
sem_t ChairWait;
sem_t chairbarber; 
sem_t sleepbarber; 
sem_t haircut; 
int AllFinished = 0; 
int main(int argc, char *argv[]) {    
  pthread_t btid;    
  pthread_t tid[MAX_CLIENTS];    
  int i, numclients, numchairs;
  int Number[MAX_CLIENTS];        
  if (argc != 3) {
        printf("Use: barber <Num clients> <Num chairs>\n");
        exit(-1);    
  }
  numclients = atoi(argv[1]);
  numchairs = atoi(argv[2]);    
  if (numclients > MAX_CLIENTS) {
        printf("Max clients are %d.\n", MAX_CLIENTS);
        exit(-1);    
  }
  for (i=0; i<MAX_CLIENTS; i++) {
        Number[i] = i;    
  }        
  sem_init(&ChairWait, 0, numchairs);    
  sem_init(&barberchair, 0, 1);    
  sem_init(&barbersleep, 0, 0);    
  sem_init(&CorteCabello, 0, 0);        
  pthread_create(&btid, NULL, barber,  NULL);
  for (i=0; i<numclients; i++) {
        pthread_create(&tid[i], NULL, client, (void *)&Number[i]);    
  }
  for (i=0; i<numclients; i++) 
  {
        pthread_join(tid[i],NULL);
  }
  AllFinished = 1;    
  sem_post(&barbersleep);
  pthread_join(btid,NULL);
} 

void *client(void *number) {
    int num = *(int *)number;
    printf("Client %d begins\n", num+1);
    sem_wait(&ChairWait);
    printf("Client %d waits\n", num+1);
    sem_wait(&barberchair);
    sem_post(&ChairWait);
    printf("Client %d awake barber\n", num+1);    
    sem_post(&barbersleep);
    sem_wait(&haircut);
    sem_post(&barberchair);
    printf("Client %d ends\n", num+1);
    return 0;
}
 
void *barber(void *num) {
    while (!AllFinished) {        
       printf("Barber sleeping\n");        
       sem_wait(&barbersleep);
       if (!AllFinished) {            
           printf("Barber cuts hair\n");
           sem_post(&haircut);
           printf("Finish haircut\n");        
       }  
  }
  printf("Bye bye\n");    
  return 0;
}

Compilation and proofs

We use the pthread library, also we use GCC with the options for such a compilation, as shown in the following command:

gcc barbero.c -o barbero -lpthread -lm

At the end of the program execution is given by including the number of clients who are going to enter the barber shop and the number of existing chairs, the code will emulate the problem of the sleeping barber.

./barber [number of clients] [number of chairs]

Also this problem can be implemented on C++ and Objective-C