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_post
1 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
Best Answer
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.