The Barber Problem

We have the following situation: a barbershop with one barber (one thread), one barber chair, N waiting chairs, and M clients (M threads).

In this problem, we have the following constraints:

• The barber sleeps when there are no clients.
• When a client arrives, they either wake up the barber or wait if the barber is busy.
• If all chairs are occupied, the client leaves.

Pseudocode:

int freeChairs = N;
semaphore clients(0);
semaphore barber_ready(0);
semaphore chairs(1); // or mutex

barber() {
    while(true) {
        clients.acquire(); // looking for a client; if one exists, call them
		
        chairs.acquire(); // a client is here, a chair is freed up, updating freeChairs
		
        freeChairs++; // chair is freed up

        barber_ready.release(); // barber is ready to cut
        chairs.release(); // freeChairs updated

        // barber is cutting hair
    }
}

client(int id) {
    while(true) {
        chairs.acquire(); // a client arrives and looks for an available chair
        if (freeChairs > 0) {
            freeChairs--; // client found a chair
			
            clients.release(); // barber is informed that a client has taken a chair
			
            chairs.release(); // freeChairs updated
			
            barber_ready.acquire(); // the client waits their turn for a haircut
        } else {
            // no available chairs
            chairs.release();
            // the client leaves without getting a haircut
        }
    }
}