Sleeping Barber algorithm (with multiple barbers)

Question

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

_{(although the actual code is in C, I wrote the following pseudo-code without much care for the syntax for sake of problem-understading, only using sem_wait and sem_post¹ for smoother 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 ².

What changes would I have to do in my code? Where would I need an extra semaphore here?

¹_{sem_wait() locks the semaphore. sem_post() unlocks it}
²_{Disclaimer: Although I have asked this in programmers.stackexchange aswell, I did not have reached a desired answer and my question still persists.}

Answer 1

The code as written will manage any number of barbers without any additional semaphores. Simply start a Barber{} thread for each barber in the shop.

The problem referenced in the Wikipedia remark is this: just because you have M barbers in the "barber is cutting hair" state and M customers in the "customer is having hair cut" state, there's no guarantee that some barber isn't trying to clip more than one customer, or that some customer doesn't have several barbers in his hair.

In other words, once the proper number of customers have been allowed into the cutting room, how do the barbers and customers pair off? You can no longer say "barber is cutting hair" and "customer is having hair cut"; you have to say "barber is cutting hair of customer C" and "customer is having hair cut by barber B".

// Assumptions about the meaning of 'haircut':
// each thread has a unique PID
// each thread can get its own PID via system.info.PID
// a barber uses a customer's PID to cut that custmer's hair
// a customer uses a barber's PID to get his hair cut by that barber
// Assumptions about the operating environment:
// a semaphore releases threads in the order that they were queued

Semaphore Customers = 0;
Semaphore Barbers = 0;
Mutex AccessSeats = 1;
int NumberOfFreeSeats = N;
int SeatPocket[N];  // (or 'PID SeatPocket[N];' if PID is a data type)
int SitHereNext = 0;
int ServeMeNext = 0;

// main program must start a copy of this thread for each barber in the shop
Barber {
    int mynext, C;
    while(1) {
        sem_wait(Barbers);  // join queue of sleeping barbers
        sem_wait(AccessSeats);  // mutex to protect seat changes
        ServeMeNext = (ServeMeNext++) mod N;  // select next customer
        mynext = ServeMeNext;
        C = SeatPocket[mynext];  // get selected customer's PID
        SeatPocket[mynext] = system.info.PID;  // leave own PID for customer
        sem_post(AccessSeats);  // release the seat change mutex
        sem_post(Customers);  // wake up selected customer
        //
        // barber is cutting hair of customer 'C'
        //
    }
}

// main program must start a copy of this thread at random intervals
// to represent the arrival of a continual stream of customers
Customer {
    int myseat, B;
    sem_wait(AccessSeats);  // mutex to protect seat changes
    if(NumberOfFreeSeats > 0) {
        NumberOfFreeSeats--;  // sit down in one of the seats
        SitHereNext = (SitHereNext++) mod N;
        myseat = SitHereNext;
        SeatPocket[myseat] = system.info.PID;
        sem_post(AccessSeats);  // release the seat change mutex
        sem_post(Barbers);  // wake up one barber
        sem_wait(Customers);  // join queue of sleeping customers
        sem_wait(AccessSeats);  // mutex to protect seat changes
        B = SeatPocket[myseat];  // barber replaced my PID with his own
        NumberOfFreeSeats++;  // stand up
        sem_post(AccessSeats);  // release the seat change mutex
        //
        // customer is having hair cut by barber 'B'
        //
    } else {
        sem_post(AccessSeats);  // release the seat change mutex
        // customer leaves without haircut
    }
    system.thread.exit;  // (or signal main program to kill this thread)
}