concurrencyoperating-systemmutexsemaphore

Sleeping Barber problem: how to prevent the barber from cutting before the customer is ready?

Recently, I've been studying the classic Sleeping Barber problem and came across a possible solution from Wikipedia:

# The first two are mutexes (only 0 or 1 possible)
Semaphore barberReady = 0
Semaphore accessWRSeats = 1     # if 1, the number of seats in the waiting room can be incremented or decremented
Semaphore custReady = 0         # the number of customers currently in the waiting room, ready to be served
int numberOfFreeWRSeats = N     # total number of seats in the waiting room

def Barber():
  while true:                   # Run in an infinite loop.
    wait(custReady)             # Try to acquire a customer - if none is available, go to sleep.
    wait(accessWRSeats)         # Awake - try to get access to modify # of available seats, otherwise sleep.
    numberOfFreeWRSeats += 1    # One waiting room chair becomes free.
    signal(barberReady)         # I am ready to cut.
    signal(accessWRSeats)       # Don't need the lock on the chairs anymore.
    # (Cut hair here.)

def Customer():
  while true:                   # Run in an infinite loop to simulate multiple customers.
    wait(accessWRSeats)         # Try to get access to the waiting room chairs.
    if numberOfFreeWRSeats > 0: # If there are any free seats:
      numberOfFreeWRSeats -= 1  #   sit down in a chair
      signal(custReady)         #   notify the barber, who's waiting until there is a customer
      signal(accessWRSeats)     #   don't need to lock the chairs anymore
      wait(barberReady)         #   wait until the barber is ready
      # (Have hair cut here.)
    else:                       # otherwise, there are no free seats; tough luck --
      signal(accessWRSeats)     #   but don't forget to release the lock on the seats!
      # (Leave without a haircut.)

At first this looked fine, but then I noticed a possible loophole:

From my limited understanding of semaphores, a signal() can be executed before a corresponding wait().

Suppose the barber executes signal(barberReady) and immediately starts cutting hair before a customer executes wait(barberReady). Conceptually this feels strange, because the customer isn't actually ready yet.

How does the operating system (or semaphore semantics) prevent this mismatch?

Solution

  • My understanding of the question

    You’re worried about a “mismatch” if the barber does signal(barberReady) before a customer does wait(barberReady). Intuitively it feels wrong (“customer isn’t ready yet”), and you’re asking how the system avoids a lost or premature wake-up.

    The primitives

    1. custReady (counting semaphore, init 0): how many customers are waiting.

    2. barberReady (counting semaphore, init 0): chair/ticket to start a haircut.

    3. accessWRSeats (mutex, init 1): protects numberOfFreeWRSeats.

    4. numberOfFreeWRSeats = N: seats available in the waiting room.

    Barber (one cycle)

    1. wait(custReady) — sleep until a customer exists.

    2. wait(accessWRSeats) → numberOfFreeWRSeats += 1 → signal(accessWRSeats) — free one seat.

    3. signal(barberReady) — offer exactly one “start haircut” ticket.

    4. Cut hair.

    Customer (arrive once)

    Why “signal before wait” is OK