Sleeping Barber
A barber sleeps when no customers; a customer wakes the barber if asleep, otherwise sits in a finite waiting room (or leaves if full). Classic producer-consumer with a bounded buffer + signal-on-empty pattern. Two semaphores + a counted slot map onto it cleanly.
The setup
Dijkstra (1965) imagined a barbershop with one barber, one barber chair, and N waiting chairs. The barber's day is simple:
- If no one is in the shop, the barber sleeps in his chair.
- A customer wakes him up; he cuts that customer's hair.
- While he's cutting, more customers can sit in the waiting chairs.
- When he's done, he looks at the waiting chairs. If anyone is there, he calls the next one over. If not, he goes back to sleep.
A customer walking in handles three cases:
- Barber asleep → wake him up, sit in the barber chair, get a haircut.
- Barber busy, free seat → sit down, wait for your turn.
- Barber busy, all seats taken → walk out. Don't block the doorway.
The challenge: coordinate the barber and the customers using synchronization primitives so all three cases work without races, deadlocks, or busy-waiting.
A picture of what happens when a customer arrives
And the barber's loop, in plain English:
The pattern underneath
What this problem is really about It's a producer-consumer with a bounded buffer that rejects when full instead of blocking the producer.
- Customers are the producers (they produce "needs a haircut" requests).
- The barber is the single consumer (he processes them one at a time).
- The N waiting chairs are the bounded buffer.
- "Shop full → leave" is the rejection on overflow policy (vs. blocking the producer).
Once you see it that way, the design picks itself.
Three coordination concerns, three pieces
Map each rule of the problem to one primitive
- Barber sleeps when idle → a semaphore the barber blocks on (
customerSem). Customersrelease()it on arrival; the barberacquire()s it. - Customer waits its turn → a second semaphore (
barberSem). The customer waits for the barber to signal "your turn now." - Bounded waiting room → a counter protected by a mutex, OR a buffered channel of capacity N.
The Go solution collapses all three into a single buffered channel: the channel is the waiting room, receiving from it is the barber waking up, and a non-blocking send is the "leave if full" check. That's why channel-based languages make this problem disappear.
Where this pattern shows up in production
The barbershop is a toy, but the structure is everywhere a system has finite capacity and a "reject excess" policy:
- HTTP server with a bounded request queue — when full, return
503 Service Unavailableinstead of letting connections pile up. - Background job processor with a max-pending limit — drop excess work and log overflow rather than memory-bomb on a backlog.
- WebSocket connection limit — accept up to N, reject the rest with a clear error code.
- Database connection pool with a non-blocking acquire — fail fast when the pool is exhausted instead of stalling the request.
In each one, the question "what happens when the buffer is full?" has the same answer the barber's shop gives: turn the new arrival away cleanly.
What junior solutions get wrong
Using sleep() and polling the customer count in a loop. The barber should block on a semaphore, not periodically wake to check a flag. Busy-waiting is exactly what synchronization primitives are for avoiding.
Implementations
customerSem lets the barber sleep until customers arrive; barberSem makes customers wait their turn. mutex protects waitingCount. If room is full, customer leaves immediately.
1 import java.util.concurrent.Semaphore;
2
3 class BarberShop {
4 private final int CHAIRS = 5;
5 private int waiting = 0;
6 private final Semaphore customerSem = new Semaphore(0);
7 private final Semaphore barberSem = new Semaphore(0);
8 private final Semaphore mutex = new Semaphore(1);
9
10 public void barber() throws InterruptedException {
11 while (true) {
12 customerSem.acquire(); // sleep until customer
13 mutex.acquire(); waiting--; mutex.release();
14 barberSem.release(); // start haircut
15 cutHair();
16 }
17 }
18
19 public boolean customer() throws InterruptedException {
20 mutex.acquire();
21 if (waiting == CHAIRS) { mutex.release(); return false; } // shop full
22 waiting++;
23 customerSem.release(); // wake barber
24 mutex.release();
25 barberSem.acquire(); // wait for haircut
26 getHaircut();
27 return true;
28 }
29 }Key points
- •Three roles: barber, customer, finite waiting room
- •Two semaphores: customers (producer signals barber) + barber (signals next haircut starts)
- •Mutex protects the seat counter; bounded chairs reject if full
- •Producer-consumer with a bounded buffer in different clothes