The Sleeping Barber Problem (see Fig. 2.20)

Figure 2.20: A solution to the sleeping barber problem.

• This problem is similar to various queueing situations
• The problem is to program the barber and the customers without getting into race conditions
  • Solution uses three semaphores:
    • customers; counts the waiting customers
    • barbers; the number of barbers (0 or 1)
    • mutex; used for mutual exclusion
    • also need a variable waiting; also counts the waiting customers (reason; no way to read the current value of semaphore)
  • The barber executes the procedure barber, causing him to block on the semaphore customers (initially 0)
  • The barber then goes to sleep
  • When a customer arrives, he executes customer, starting by acquiring mutex to enter a critical region
  • if another customer enters, shortly thereafter, the second one will not be able to do anything until the first one has released mutex
  • The customer then checks to see if the number of waiting customers is less than the number of chairs
  • if not, he releases mutex and leaves without a haircut
  • if there is an available chair, the customer increments the integer variable, waiting
  • Then he does an up on the semaphore customers
  • When the customer releases mutex, the barber begins the haircut