[1] The problem was originally proposed in 1965 by computer science pioneer Edsger Dijkstra,[2] who used it to make the point that general semaphores are often superfluous.
Specifically, a customer may arrive to find the barber cutting hair so they return to the waiting room to take a seat but while walking back to the waiting room the barber finishes the haircut and goes to the waiting room, which he finds empty (because the customer walks slowly or went to the restroom) and thus goes to sleep in the barber chair.
The barber must acquire the room status mutex before checking for customers and release it when they begin either to sleep or cut hair; a customer must acquire it before entering the shop and release it once they are sitting in a waiting room or barber chair, and also when they leave the shop because no seats were available.
The problem of starvation can be solved with a first-in first-out (FIFO) queue.
The semaphore would provide two functions: wait() and signal(), which in terms of C code would correspond to P() and V(), respectively.