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 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.
Solution
Many example solutions are available. The key element of all is a mutex, which ensures that only one of the participants can change state at once. The barber must acquire this mutex before checking for customers (releasing it when he either begins to sleep or begins to cut hair), and a customer must acquire it before entering the shop (releasing it when he has sat in either a waiting room chair or the barber chair). This eliminates both of the problems mentioned above. A number of semaphores are also necessary to indicate the state of the system, for example, storing the number of people in the waiting room and the number of people the barber is cutting the hair of.
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
}
}
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.