What is the Sleeping Barber Problem?
Learn the sleeping barber problem — bounded waiting chairs, mutex plus semaphores, and no lost wakeups — with an OS interview walkthrough.
Expected Interview Answer
The sleeping barber problem is a classic synchronization exercise where a barber sleeps when there are no customers and must be woken when one arrives, while a limited number of waiting chairs force arriving customers to leave if the shop is full, modeling bounded-buffer producer-consumer coordination with mutual exclusion.
The barber shop has one barber, one barber chair, and a fixed number of waiting chairs. If no customers are present the barber sleeps; a customer who arrives either wakes the barber if he is asleep, takes a free waiting chair if the barber is busy, or leaves immediately if all waiting chairs are full. The classic solution uses a mutex to protect the shared count of waiting customers, a semaphore that signals the barber a customer is ready, and a semaphore that signals a customer that the barber is ready, so the two never busy-wait on each other. This is a bounded-buffer variant of producer-consumer with an added twist: unlike a typical queue, arriving producers (customers) that find the buffer full simply abandon the transaction instead of blocking indefinitely. The key correctness properties are no lost wakeups, no busy waiting, and no customer being served twice or losing their seat to another customer.
- Models bounded-buffer producer-consumer with a reneging producer
- Teaches correct use of semaphores plus a mutex together
- Demonstrates avoiding busy-waiting via blocking signals
- Foundation for thread-pool and connection-pool coordination
AI Mentor Explanation
The sleeping barber is like a single throwdown coach who naps in the nets when no batter is waiting, and a bell rope one batter can pull to wake him. Only three batters can queue on the bench (bounded chairs); a fourth arriving batter sees the bench full and walks off to practice elsewhere instead of waiting. The coach and the queue counter are protected so two batters cannot both grab the last bench seat at once, and no wakeup pull is ever lost mid-nap.
Step-by-Step Explanation
Step 1
Customer arrives
A customer thread checks the waiting-room count, protected by a mutex, before acting.
Step 2
Wake or wait or leave
If the barber is asleep, signal him directly; if he is busy and a chair is free, take it and wait; if no chairs are free, leave.
Step 3
Barber sleeps or serves
The barber blocks on a semaphore until a customer signals; on wake, he serves the next waiting customer.
Step 4
Synchronization guarantee
The mutex plus two semaphores ensure no lost wakeups, no busy-waiting, and no chair is double-occupied.
What Interviewer Expects
- A precise statement of the bounded-waiting-room constraint
- Correct use of a mutex for the shared counter plus semaphores for signaling
- Recognizing customers that find the shop full simply leave (reneging)
- Awareness this generalizes to bounded producer-consumer patterns
Common Mistakes
- Forgetting the waiting room is bounded and treating it as an unbounded queue
- Using a single semaphore instead of a mutex plus two signaling semaphores
- Allowing a lost wakeup when the barber checks and sleeps in separate steps
- Not handling the case where a customer leaves because the shop is full
Best Answer (HR Friendly)
“The sleeping barber problem describes one barber who naps when the shop is empty and must be reliably woken by the next customer, with only a few waiting chairs so extra customers simply leave if it is full. It is a classic exercise for making sure a producer and consumer coordinate correctly with locks and signals, without busy-waiting or missing a wakeup.”
Code Example
#define CHAIRS 3
int waiting = 0;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
sem_t barber_ready; /* signals: barber is ready to cut hair */
sem_t customer_ready; /* signals: a customer is ready to be served */
void *barber(void *arg) {
for (;;) {
sem_wait(&customer_ready); /* sleep until a customer arrives */
pthread_mutex_lock(&mutex);
waiting--;
pthread_mutex_unlock(&mutex);
sem_post(&barber_ready); /* tell the waiting customer to sit */
cut_hair();
}
}
void *customer(void *arg) {
pthread_mutex_lock(&mutex);
if (waiting < CHAIRS) {
waiting++;
sem_post(&customer_ready); /* wake the barber or take a seat */
pthread_mutex_unlock(&mutex);
sem_wait(&barber_ready); /* wait for the barber to be free */
get_haircut();
} else {
pthread_mutex_unlock(&mutex); /* shop full, leave immediately */
}
return NULL;
}Follow-up Questions
- How is the sleeping barber problem different from the classic producer-consumer problem?
- What would happen if the mutex were removed from around the waiting counter?
- How would you extend this to multiple barbers?
- Why does the solution use two separate semaphores instead of one?
MCQ Practice
1. What happens when a customer arrives and all waiting chairs are occupied?
With a bounded number of waiting chairs, an arriving customer who finds them all full simply leaves.
2. What is the role of the mutex in the classic solution?
The mutex ensures increments and decrements of the waiting count are atomic, preventing race conditions between customer threads.
3. The sleeping barber problem is a variant of which broader synchronization pattern?
It models a bounded buffer (the waiting chairs) between customer producers and a barber consumer, with reneging when the buffer is full.
Flash Cards
What is the sleeping barber problem? — A synchronization exercise with one barber, one chair, and bounded waiting chairs, modeling producer-consumer coordination.
What happens if the waiting room is full? — The arriving customer leaves without waiting or getting served.
What primitives does the classic solution use? — A mutex for the shared counter plus two semaphores for barber-ready and customer-ready signaling.
What must the solution avoid? — Busy-waiting and lost wakeups between the barber and customers.