After understanding the Sleeping Barber Problem and the core concepts behind the real problems of running asynchronous operations on shared data, we can start to work out a solution.
As in many other problems in various domains of computing, there are more than one possible solutions to the problem. We will be analyzing one that involves two thread synchronization mechanisms: semaphores and mutexes.
A type of variable that counts the number of wakeups saved for future use.
Dijkstra proposed that semaphores have two operations: down and up.
The down operation checks if the value of a semaphore is greater than 0. If it is, one wakeup saved in the semaphore is used and the process or thread proceeds. However, if the value is 0, the process or thread is put to sleep without completing the down operation. Checking the value on a semaphore and changing it or going to sleep is a single atomic action.
Indivisible group of operations that are either all performed without interruptions or are not performed at all.
The up operation adds one wakeup to the semaphore. If one or more processes or threads were sleeping due to a down operation on that semaphore, one will be chosen arbitrarily by the system and will complete its down operation and proceed. This is also an atomic action.
A simplified version of a semaphore used when the semaphores' ability to count and save wakeups is not needed. Mutexes are generally used to manage mutual exclusion, having only two states: locked or unlocked.
Now that we have covered all concepts necessary to understand one of the possible solutions to the Sleeping Barber Problem, we can start by defining how we will be applying these concepts.
For our implementation, we will be using two semaphores and one mutex. One of the semaphores will be for the customers in the waiting room and the other one will be for the barber. The mutex will be used for mutual exclusion.
Aside from that, we will need to define the number of chairs in the waiting room, which will be our limit on the number of customers and keep a control variable of the number of customers currently waiting.
From the description of the problem, we have that the customer will either get a haircut or leave the barbershop; the barber can only cut hair. Those three actions will be our functions.
The barber has only three actions, repeated until he closes the shop. Let's analyze each one.
To check for a client, sleep if no one's waiting and wake up when a customer arrives, we run a down operation on the customers semaphore. When a customer arrives, the barber brings them to the barber's chair, and then there is one less customer in the waiting room. Now the barber is ready to work. After the hair cut, the barber checks for a client and the cycle repeats.
The customer also has three actions but, unlike the barber, the customer only performs his actions once.
When a customer arrives, he checks to see if there's a chair available in the waiting room. If there isn't, the customer leaves. Otherwise the customer waits, and the number of customers in the waiting room increases. To wakeup the sleeping barber, the customer runs an up on the customers semaphore, and then a down on the barber semaphore, waiting to be brought to the barber's chair.
That is the main part of our solution, but we didn't deal with the mutex for the possible race condition. The critical region is the highlighted part in both role descriptions, where they read and write from the variable that keeps count of the number of customers waiting.
After wrapping the highlighted parts in both the customer and the barber with the mutex, the problem is solved!