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 */
}
else
{
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.
