The Sleeping Barber Problem

The barber shop has one barber, one barber chair, and N chairs for waiting customers, if
any, to sit in. If there is no customer at present, the barber sits down in the barber chair and
falls asleep. When a customer arrives, he has to wake up the sleeping barber. If additional
customers arrive while the barber is cutting a customer’s hair, they either sit down (if there is
an empty chair) or leave the shop (if all chairs are full). The problem is to program the barber
and the customers without getting into race conditions.

#define CHAIRS 5 /* number of chairs for waiting customers */
typedef int semaphore;
semaphore customers = 0; /* number of waiting customers */
semaphore barbers = 0; /* number of barbers waiting for customers */
semaphore mutex = 1; /* for mutual exclusion */
int waiting = 0; /* customers are waiting not being haircut */
void Barber(void)
 while (TRUE)
 down(customers); /* go to sleep if number of customers is 0 */
 down(mutex); /* acquire access to ‘waiting’ */
 waiting = waiting – 1; /* decrement count of waiting customers */
 up(barbers); /* one barber is now ready to cut hair */
 up(mutex); /* release ‘waiting’ */
 cut_hair(); /* cut hair, non-CS */
void customer(void)
 down(mutex); /* enter CS */
 if (waiting < CHAIRS)
 waiting = waiting + 1; /* increment count of waiting customers */
 up(customers); /* wake up barber if necessary */
 up(mutex); /* release access to ‘waiting’ */
 down(barbers); /* wait if no free barbers */
 get_haircut(); /* non-CS */
 up(mutex); /* shop is full, do not wait */

Our solution uses three semaphores: customers, which counts waiting customers (excluding
the one being served), barbers, the number of idle barbers (0 or 1), and mutex for mutual
exclusion. The variable waiting is essentially a copy of customers and it is required since
there is no way to read the current value of a semaphore.

Try Now – Operating Systems MCQs
Practice Now – Operating System Online Test