Sleeping Barber Problem in Operating Systems | OS Tutorials

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 the aforementioned processes.

Sleeping Barber Problem

• The analogy is based on a hypothetical barbershop 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 other customers are waiting.
• If there are, he brings one of them back to the chair and cuts his or her hair.
• If no other customers are 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.
• 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.
• Figure 1 illustrates the sleeping barber problem.

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.

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 exclusion 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. Several 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 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.

Semaphore Customers = 0
Semaphore Barber = 0
Semaphore accessSeats = 1      #mutex
int NumberOfFreeSeats = N      #total number of seats

def Barber():
  while true:     #Run in an infinite loop.
    P(Customers)  #Try to acquire a customer - if none is available
go to sleep.
    P(accessSeats)   #I have been awakened - modify the number of
available seats.
    NumberOfFreeSeats++  #One chair gets free.
    V(Barber)            #I am ready to cut.
    V(accessSeats)       #Don't need the lock on the chairs anymore.
                         #(Cut hair here.)

def Customer():
  while true:     #Run in an infinite loop.
   P(accessSeats)  #Try to get access to the chairs.
   if NumberOfFreeSeats > 0:  #If there are any free seats:
     NumberOfFreeSeats-       # sit down on a chair
     V(Customers)           #notify the barber, who's waiting until 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.
                      # (Have hair cut here.)
 else:    #otherwise, there are no free seats; tough luck -
  V(accessSeats)  #but don't forget to release the lock on the seats!
                  #(Leave without a haircut.)