Sleeping barber problem

computer science, the sleeping barber problem is a classic inter-process communication and synchronization problem between multiple operating system processes. The problem is analogous to that of keeping a barber working when there are customers, resting when there are none and doing so in an orderly manner. The barber and his customers represent aforementioned processes.
The problem

The analogy is based upon a hypothetical barber shop with one barber. The barber has one barber chair and a waiting room with a number of chairs in it. When the barber finishes cutting a customer's hair he dismisses the customer and then goes to the waiting room to see if there are other customers waiting. If there are he brings one of them back to the chair and cuts his or her hair. If there are no other customers waiting he returns to his chair and sleeps in it.
Each customer when he arrives looks to see what the barber is doing. If the barber is sleeping then he wakes him up and sits in the chair. If the barber is cutting hair then he goes to the waiting room. If there is a free chair in the waiting room he sits in it and waits his turn. If there is no free chair then the customer leaves. On a naive analysis the above description should ensure that the shop functions correctly, with the barber cutting hair of anyone who arrives until there are no more customers, and then sleeping until the next customer arrives. In practice there are a number of problems that can occur, which are illustrative of general scheduling problems.
The problems are all related to the fact that the actions by both the barber and the customer (checking the waiting room, entering the shop, taking a waiting room chair etc.) all take an unknown amount of time. For example, a customer may arrive and observe that the barber is cutting hair, so he goes to the waiting room. While he is on his way the barber finishes the haircut he is doing and goes to check the waiting room. Since there is no-one there (the customer hasn't arrived yet) he goes back to his chair and sleeps. The barber is now waiting for a customer and the customer is waiting for the barber. In another example two customers may arrive at the same time, observe that the barber is cutting hair and there is a single seat in the waiting room, and go to the waiting room. They will both then attempt to occupy the single chair.

The Sleeping Barber Problem is often attributed to Edsger Dijkstra (1965), one of the pioneers in fundamental programming.

[edit] A solution

This article does not cite any references or sources.

Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (February 2010)

A possible solution involves using three semaphores: one for any waiting customers, one for the barber (to see if he is idle), and the third ensures mutual exclusion. When a customer arrives, he attempts to acquire the mutex, and waits until he has succeeded. The customer then checks to see if there is an empty chair for him (either one in the waiting room or the barber chair), and if none of these are empty, leaves. Otherwise the customer takes a seat – thus reducing the number available (a critical section). The customer then signals the barber to awaken through his semaphore, and the mutex is released to allow other customers (or the barber) the ability to acquire it. If the barber is not free, the customer then waits. The barber sits in a perpetual waiting loop, being awakened by any waiting customers. Once he is awoken, he signals the waiting customers through their semaphore, allowing them to get their haircut one at a time.
This problem involves only one barber, and it is therefore also called the single sleeping barber problem. A multiple sleeping barbers problem is similar in the nature of implementation and pitfalls, but has the additional complexity of coordinating several barbers among the waiting customers.

Implementation

* The following pseudo-code guarantees synchronization between barber and customer and is deadlock free, but may lead to starvation of a customer. P and V are functions provided by the semaphores.

* You need (as mentioned above):

+ Semaphore Customers = 0

+ Semaphore Barber = 0

+ Semaphore accessSeats (mutex) = 1

+ int 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 awakened - 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):
while(true) { //runs in an infinite loop

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, who's waiting that there is a customer

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

P(Barber) //now it's this customer's 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

}

}