CREATE OWN LIBRARY

Sleeping Barber

Dijkstra introduced the Sleeping Barber Problem (Dijkstra, 1965): A barbershop is divided into two rooms. The waiting room has n chairs and the workroom only has the barber chair. When the waiting room is empty, the barber goes to sleep in the barber chair. If a customer comes in and the barber is asleep, he knows it’s his turn to get his hair cut. So he wakes up the barber and takes his turn in the barber chair. But if the waiting room is not empty, the customer must take a seat in the waiting room and wait his turn. 

This sleeping barber problem may lead to a race condition.

The problem has occurred from the actions of both the barber and customer. For example, a customer arrives and notices that the barber is busy cutting the hair of another person. So, he goes to the waiting room. While he is on the way to the waiting room, the barber just finished his job and sees the waiting room. But the barber finds no one in the waiting room (customer yet not arrive at the waiting room), he sits down to the chair and sleeps. So, the barber waiting for a new customer who wakes up the barber and the customer thinks that the barber is busy so, he also waits for the barber. 

Both are waiting forever which leads to a race condition.

This solution uses three semaphores, one for customers (counts waiting customers), one for the barber (idle - 0 or busy - 1), and a mutual exclusion semaphore, mutex. 

Analysis

When the barber arrives for work, the barber procedure is executed and he sees any customer is ready or not. If anyone is ready then pick up the customer for a hair-cut and block the customer's semaphore. If no one is ready for a hair-cut, the barber goes to sleep. 

When the customer arrives, the customer procedure is executed which down mutex and enter the critical section. But the customer must be waiting until the first customer leaves the critical section and down the mutex. Now if the customer gets the mutex then he checks there is any waiting chair vacant or not. If it is no, then release the mutex and customer leave without hair-cut. 

If there is an available chair, the waiting counter is incremented, the barber is wake up, and the customer releases the mutex. Then the barber gets the mutex, enters into the critical section, and starts hair-cut. 

After completion of the hair-cut, the customer leaves. Now barber checks at the waiting room, there is any other customer waiting for a hair-cut or not. If it is no, the barber going to sleep.