Sleeping barber problem
|
|
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.
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, he 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.
The most common solution involves using three semaphores: one for any waiting customers, one for the barber (to see if he is idle), and a mutex. 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 a hair cut one at a time.
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 hair cut even though they have been waiting.
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.
References
- Modern Operating Systems (2nd Edition) by Andrew S. Tanenbaum (ISBN 0130313580)