the sleeping barber problem
/ Dijkstra -> DYKE-struh /
A small barbershop has one barber, one barber's chair, and a waiting room with a fixed number of chairs. When no customers are around, the barber sleeps in the chair. A customer who walks in wakes the barber if he is asleep; if the barber is busy, the customer sits in a waiting-room chair — unless they are all taken, in which case the customer simply leaves. When the barber finishes a haircut, he checks the waiting room: if someone is there he calls the next customer, otherwise he goes back to sleep. This little shop, another puzzle from Dijkstra, models a server that handles requests one at a time with a bounded queue, and it shines a light on the subtle races between 'a worker going to sleep' and 'a customer arriving.'
The danger is a lost wakeup. Suppose a customer checks and sees the barber is cutting hair, so they decide to take a waiting-room seat — but in the instant between checking and sitting, the barber finishes, looks at the (still apparently empty) waiting room, and dozes off. Now the customer is seated waiting for a barber who is asleep waiting for a customer: both wait forever. The standard solution uses three semaphores: a counting semaphore customers (how many are waiting, the barber waits on it), a binary semaphore barbers (whether the barber is free), and a mutex to protect the shared count of waiting customers so that 'check and sit' and 'finish and check' never interleave badly.
The reason it earns a place beside the dining philosophers is that it isolates a different family of bug — not deadlock from a cycle of held resources, but the lost-wakeup race that haunts any blocking queue. It is, at heart, a single-server, finite-capacity producer-consumer problem (customers produce work, the barber consumes it), and the barber-shop story makes vivid why you must atomically test the condition and go to sleep, never test first and sleep second. That exact lesson is why condition variables exist and why their wait operation atomically releases the lock and blocks.
Customer: lock(mutex); if (waiting < chairs) { waiting++; signal(customers); unlock(mutex); wait(barbers); getHaircut(); } else { unlock(mutex); leave(); }. Barber: wait(customers); lock(mutex); waiting--; signal(barbers); unlock(mutex); cutHair().
Three semaphores plus a mutex. The mutex makes the check-and-update of 'waiting' atomic, which is exactly what prevents the lost-wakeup race.
The whole point is the atomicity of 'test the condition, then block.' If those are two separate steps, a wakeup that fires in the gap is lost forever — which is why you wait on a condition variable inside a while loop, never an if.