[ Previous: 2.1 Implementation of Semaphores | Up: 2.2 Classical Problems | Next: 2.2.2 Cigarette Smokers ]

2.2.1 Sleeping Barber

Scenario

Consider a barber’s shop where there is only one barber, one barber chair and a number of waiting chairs for the customers. When there are no customers the barber sits on the barber chair and sleeps. When a customer arrives he awakes the barber or waits in one of the vacant chairs if the barber is cutting someone else’s hair. When all the chairs are full, the newly arrived customer simply leaves.

Problems

There might be a scenario in which the customer ends up waiting on a barber and a barber waiting on the customer, which would result to a deadlock.
Then there might also be a case of starvation when the customers don’t follow an order to cut hair, as some people won’t get a hair cut even though they had been waiting long.

Use of Semaphores

The solution to these problems involves the use of three semaphores out of which one is a mutex (binary semaphore). They are:

Customers: Helps count the waiting customers.
Barber: To check the status of the barber, if he is idle or not.
accessSeats: A mutex which allows the customers to get exclusive access to the number of free seats and allows them to increase or decrease the number.
NumberOfFreeSeats: To keep the count of the available seats, so that the customer can either decide to wait if there is a seat free or leave if there are none.

The Procedure

When the barber first comes to the shop, he looks out for any customers i.e. calls P(Customers), if there are none he goes to sleep.
Now when a customer arrives, the customer tries to get access to the accessSeats mutex i.e. he calls P(accessSeats), thereby setting a lock.
If no free seat (barber chair and waiting chairs) is available he releases the lock i.e. does a V(accessSeats) and leaves the shop.
If there is a free seat he first decreases the number of free seats by one and he calls V(Customers) to notify the barber that he wants to cut.
Then the customer releases the lock on the accessSeats mutex by calling V(accessSeats).
Meanwhile when V(Customers) was called the barber awakes.
The barber locks the accessSeats mutex as he wants to increase the number of free seats available, as the just arrived customer may sit on the barber’s chair if that is free.
Now the barber releases the lock on the accessSeats mutex so that other customers can access it to the see the status of the free seats.
The barber now calls a V(Barber), i.e. he tells the customer that he is available to cut.
The customer now calls a P(Barber), i.e. he tries to get exclusive access of the barber to cut his hair.
The customer gets a haircut from the barber and as soon as he is done, the barber goes back to sleep if there are no customers or waits for the next customer to alert him.
When another customer arrives, he repeats the above procedure again.
If the barber is busy then the customer decides to wait on one of the free waiting seats.
If there are no customers, then the barber goes back to sleep.

Implementation

The following pseudo-code guarantees synchronization between barber and customer and is deadlock free, but may lead to starvation of a customer.

		Customers = init(0)

		Barber = init(0)

		accessSeats = init(1) // mutex

		NumberOfFreeSeats = N //total number of seats

The Barber (Thread/Process)

		while (true) { // runs in an infinite loop

		    P(Customers) // tries to acquire a customer - if none is available

		                    he goes to sleep

		    P(accessSeats) // at this time he has been awaken - want to modify

		                      the number of available seats

		    NumberOfFreeSeats++ // one chair gets free

		    V(Barber) // the barber is ready to cut

		    V(accessSeats) // we don't need the lock on the chairs anymore

                           // here the barber is cutting hair

		}

The Customer (Thread/Process)

		P(accessSeats) // tries to get access to the chairs

		if (NumberOfFreeSeats > 0) { // if there are any free seats

		    NumberOfFreeSeats-- // sitting down on a chair

		    V(Customers) // notify the barber, that there is a customer waiting

		    V(accessSeats) // don't need to lock the chairs anymore

		    P(Barber) // now it's this customers turn, but wait if the barber is busy

                      // here the customer is having his hair cut

		} else { // there are no free seats

		    // tough luck

		    V(accessSeats) // but don't forget to release the lock on the seats

		                   // customer leaves without a haircut

		}

Note: The solution can be modified so that the customers are made to form a queue as they arrive so that the barber can service these customers on a first come first served basis. This solves the problem of starvation where in a customer might have to wait long for his turn to come.

Animation

Please click START to begin.

References
1. Sleeping Barber Problem (Wikipedia)

[ Previous: 2.1 Implementation of Semaphores | Up: 2.2 Classical Problems | Next: 2.2.2 Cigarette Smokers ]