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 1 The problem 2 A solution 3 Implementation 4 References 5 See also

[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.

[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 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 their 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.

[edit] Implementation

• p() means acquire
• v() means release

• You need (as mentioned above):

 + Semaphore Customers
 + Semaphore Barber 
 + Semaphore accessSeats (mutex)
 + int NumberOfFreeSeats

• The Barber (Thread):

 while(true) //runs in an infinite loop
 {
   Customers.p() //tries to acquire a customer - if none is available he goes to sleep
     accessSeats.p() //at this time he has been awaken -> want to modify the number of available seats
       NumberOfFreeSeats++ //one chair gets free
       Barber.v()  // the barber is ready to cut
     accessSeats.v() //we don't need the lock on the chairs anymore
     //here the barber is cutting hair         
 } 

• The Customer (Thread):

 while (notCut) //as long as the customer is not cut
 {
   accessSeats.p() //tries to get access to the chairs
     if NumberOfFreeSeats>0 //if there are any free seats
       NumberOfFreeSeats -- //sitting down on a chair
       Customers.v() //notify the barber, who's waiting that there is a customer
       accessSeats.v() // don't need to lock the chairs anymore  
       Barber.p() // now it's this customers turn, but wait if the barber is busy
       notCut = false 
        
     else // there are no free seats
       //tough luck
       accessSeats.v() //but don't forget to release the lock on the seats
 }

[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

[edit] See also

• Producers-consumers problem
• Dining philosophers problem
• Cigarette smokers problem
• Readers-writers problem