Sleeping barber problem
From Wikipedia, the free encyclopedia
In 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.
Contents |
[edit] The problem
The analogy is based upon a hypothetical barber shop with one barber, one barber chair, and a number of chairs for waiting customers. When there are no customers, the barber sits in his chair and sleeps. As soon as a customer arrives, he either awakens the barber or, if the barber is cutting someone else's hair, sits down in one of the vacant chairs. If all of the chairs are occupied, the newly arrived customer simply leaves.
The problem arises with attempting to coordinate this activity without bringing about any race conditions, and in this way is similar to many queueing problems. In fact, it is a classic example of a (double) rendezvous problem. Not implementing a proper solution can lead to the usual inter-process communication problems of starvation and deadlock. For example, the barber could end up waiting on a customer and a customer waiting on the barber, resulting in deadlock. Alternatively, customers may not decide to approach the barber in an orderly manner, leading to process starvation as some customers never get the chance for a haircut even though they have been waiting.
The Sleeping Barber Problem is often attributed to Edsger Dijkstra (1965), one of the pioneers in fundamental programming.
[edit] A solution
The most common 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.
[edit] 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 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
}
}
[edit] References
- Modern Operating Systems (2nd Edition) by Andrew S. Tanenbaum (ISBN 0-13-031358-0)
- The Little Book of Semaphores by Allen B. Downey, http://greenteapress.com/semaphores
- Cooperating sequential processes by E.W. Dijkstra. Technical Report EWD-123, 1965, Technological University, Eindhoven, The Netherlands.
