6

The Sleeping Barber Problem is a classical synchronization problem that many of you may be familiar with or at least heard of.

It's based on the premise that a barber (a thread) sleeps when there are no customers (each customer is a thread) in the waiting room (which is a semaphore). If there is someone, he cuts his hair (symbolizing some processing) and the costumer leaves. If, then, there is no one in the waiting room, the barber goes to sleep. When another customer arrives, he then must wake up the barber.

I have made a implementation of this using the following basic-idea (pseudo-code, only using sem_wait and sem_post1 for smooth reading)

Semaphore Customers = 0;
Semaphore Barber = 0;
Mutex accessSeats = 1;
int NumberOfFreeSeats = N; 

Barber {
    while(1) {
        sem_wait(Customers) // waits for a customer (sleeps)
        sem_wait(accessSeats) // mutex to protect the number of available seats
        NumberOfFreeSeats++ // a chair gets free
        sem_post(Barber) // bring customer for haircut
        sem_post(accessSeats) // release the mutex on the chair
        // barber is cutting hair
    }
}

Customer {
    while(1) {
        sem_wait(accessSeats) // protects seats so only 1 thread tries to sit in a chair if that's the case
        if(NumberOfFreeSeats > 0) {
            NumberOfFreeSeats-- // sitting down
            sem_post(Customers) // notify the barber
            sem_post(accessSeats) // release the lock
            sem_wait(Barber) // wait in the waiting room if barber is busy
            // customer is having hair cut
        } else {
            sem_post(accessSeats) // release the lock
            // customer leaves
        }
   }
}

However, now that I'll implement this problem with multiple barbers, my head got stuck. I went on Wikipedia to see if I could find something about it, but the only thing that I found there was this

A multiple sleeping barbers problem has the additional complexity of coordinating several barbers among the waiting customers.

and I couldn't figure this out by myself. In which case I'd have this complexity? By several barbers going to the waiting room to see if there is anyone there and then taking (more than one barber) a single customer? Would I need an extra semaphore here?

1sem_wait() locks the semaphore. sem_post() unlocks it

2

With one barber, you only need a message queue (the waiting room). Semaphores are embedded in it.

With multiple barbers, coordination aims at:

  • preventing several barbers from cutting hair of the same customer.

  • preventing from having only one busy barber while the others sleep all day long.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.