The Sleeping Barber Problem
Proposed by Edsger Dijkstra in 1965, the Sleeping Barber Problem models a situation that shows up constantly in real systems: a service provider with limited capacity handling an unpredictable stream of requests. Think of a web server with a fixed thread pool, a call center with a limited number of operators, or a printer queue with a finite number of slots.
The Setup
A barbershop has three components:
- One barber who can serve one customer at a time.
- One barber chair where the actual haircut happens.
- A waiting room with N chairs for customers who arrive while the barber is busy.
The rules are simple:
- If no customers are present, the barber sleeps in the barber chair.
- When a customer arrives and the barber is sleeping, the customer wakes the barber up.
- When a customer arrives and the barber is busy, the customer sits in the waiting room if a chair is available.
- If all waiting room chairs are taken, the customer leaves the shop entirely.
Sleeping Barber Problem: barber, barber chair, and a waiting room with limited seats.
What Goes Wrong Without Synchronization
Several race conditions can occur if the barber and customers are not properly synchronized:
| Race Condition | What Happens |
|---|---|
| Lost Wakeup | A customer arrives and tries to wake the barber, but the barber has not quite fallen asleep yet. The wakeup signal is lost. The barber sleeps forever even though a customer is waiting. |
| Seat Count Race | Two customers check the waiting room count simultaneously, both see one chair available, and both sit down. The waiting room is now over capacity. |
| Double Service | The barber finishes a haircut and checks for waiting customers. At the same moment, a new customer arrives and sits down. The barber might skip this customer or try to serve two at once. |
| Phantom Departure | A customer decides to leave (no seats), but at the same moment a seat opens up. The customer leaves unnecessarily. |
The Semaphore Solution
The classic solution uses three semaphores and one shared variable:
| Primitive | Initial Value | Purpose |
|---|---|---|
| customers (semaphore) | 0 | Counts customers waiting for service. The barber sleeps on this when there are none. |
| barber (semaphore) | 0 | Signals that the barber is ready to cut hair. Customers wait on this. |
| mutex (semaphore) | 1 | Protects the waiting variable from concurrent access. |
| waiting (integer) | 0 | Tracks the number of customers currently in the waiting room. Needed because semaphore values cannot be read directly. |
Barber Logic
text
Barber:
while (true) {
wait(customers) // Sleep if no customers waiting
wait(mutex) // Lock access to waiting count
waiting-- // Customer moves from waiting room to chair
signal(barber) // Signal: barber is ready
signal(mutex) // Unlock
cut_hair() // Do the work
}Customer Logic
text
Customer:
wait(mutex) // Lock access to waiting count
if (waiting < N) { // Is there a free chair?
waiting++ // Take a seat
signal(customers) // Wake the barber (or add to queue)
signal(mutex) // Unlock
wait(barber) // Wait for the barber to be ready
get_haircut() // Sit in barber chair
} else {
signal(mutex) // No seats. Leave the shop.
}Why a Separate 'waiting' Variable?
Semaphore values cannot be inspected without modifying them (you can only wait or signal). The customer needs to CHECK whether there is space without actually committing to wait. The waiting integer variable solves this by providing a readable count of customers in the waiting room, protected by the mutex.
Full Implementation in C++
cpp
#include <iostream>
#include <thread>
#include <mutex>
#include <semaphore>
#include <chrono>
#include <vector>
#include <random>
const int NUM_CHAIRS = 3; // Waiting room capacity
const int NUM_CUSTOMERS = 8; // Total customers
std::counting_semaphore<NUM_CUSTOMERS> customers_sem(0);
std::counting_semaphore<1> barber_sem(0);
std::mutex mtx;
int waiting = 0; // Customers in waiting room
std::mt19937 rng(std::random_device{}());
std::uniform_int_distribution<int> delay(200, 800);
void barber() {
for (int i = 0; i < NUM_CUSTOMERS; i++) {
std::cout << "Barber is sleeping..." << std::endl;
customers_sem.acquire(); // Sleep until a customer arrives
mtx.lock();
waiting--;
std::cout << "Barber woke up. Waiting room: " << waiting << std::endl;
barber_sem.release(); // Signal: ready to cut
mtx.unlock();
// Cutting hair
std::cout << "Barber is cutting hair." << std::endl;
std::this_thread::sleep_for(std::chrono::milliseconds(500));
std::cout << "Barber finished cutting." << std::endl;
}
}
void customer(int id) {
std::this_thread::sleep_for(std::chrono::milliseconds(delay(rng)));
std::cout << "Customer " << id << " arrived." << std::endl;
mtx.lock();
if (waiting < NUM_CHAIRS) {
waiting++;
std::cout << "Customer " << id << " sits in waiting room. Waiting: "
<< waiting << std::endl;
customers_sem.release(); // Wake the barber
mtx.unlock();
barber_sem.acquire(); // Wait for the barber
std::cout << "Customer " << id << " is getting a haircut." << std::endl;
} else {
mtx.unlock();
std::cout << "Customer " << id << " left (no seats)." << std::endl;
}
}
int main() {
std::cout << "Sleeping Barber Simulation" << std::endl;
std::cout << "Waiting room chairs: " << NUM_CHAIRS << std::endl;
std::cout << "---------------------------" << std::endl;
std::thread barber_thread(barber);
std::vector<std::thread> customer_threads;
for (int i = 1; i <= NUM_CUSTOMERS; i++)
customer_threads.emplace_back(customer, i);
for (auto& t : customer_threads)
t.join();
barber_thread.join();
std::cout << "---------------------------" << std::endl;
std::cout << "Shop closed." << std::endl;
return 0;
}Output:
text
Sleeping Barber Simulation
Waiting room chairs: 3
---------------------------
Barber is sleeping...
Customer 1 arrived.
Customer 1 sits in waiting room. Waiting: 1
Barber woke up. Waiting room: 0
Barber is cutting hair.
Customer 1 is getting a haircut.
Customer 3 arrived.
Customer 3 sits in waiting room. Waiting: 1
Customer 2 arrived.
Customer 2 sits in waiting room. Waiting: 2
Barber finished cutting.
Barber woke up. Waiting room: 1
Barber is cutting hair.
Customer 3 is getting a haircut.
Customer 5 arrived.
Customer 5 sits in waiting room. Waiting: 2
Customer 4 arrived.
Customer 4 sits in waiting room. Waiting: 3
Customer 6 arrived.
Customer 6 left (no seats).
...Customer 6 arrives when all 3 waiting chairs are occupied and leaves immediately. Other customers are served in order as the barber becomes available.
Real-World Parallels
| System | Barber | Waiting Room | Customer Leaving |
|---|---|---|---|
| Thread Pool | Worker thread | Task queue (bounded) | Task rejected (queue full) |
| Web Server | Request handler | Connection backlog (listen queue) | Connection refused (503 error) |
| Call Center | Operator | Hold queue (limited lines) | Caller hears busy signal |
| Printer Queue | Printer hardware | Print job queue | Job rejected (queue full) |
| Hospital ER | Doctor on duty | ER waiting room (finite capacity) | Patient redirected to another facility |
Variations of the Problem
| Variation | What Changes |
|---|---|
| Multiple Barbers | More than one barber serves customers. Requires an additional semaphore to track available barbers. Models multi-threaded server pools. |
| Infinite Waiting Room | No customer ever leaves. The waiting variable grows without bound. Models unbounded queues (risk of memory exhaustion). |
| Priority Customers | Some customers have higher priority and skip ahead in the queue. Requires a priority queue instead of a simple counter. |
| Timed Waiting | Customers wait for a fixed time then leave if not served. Models timeout-based request handling in web servers. |
The Sleeping Barber Problem captures a pattern that appears everywhere in systems design: a service with finite capacity handling an unpredictable arrival rate. The semaphore solution ensures the barber sleeps when idle (no CPU waste), customers are served in order, and arrivals beyond capacity are handled gracefully rather than causing corruption or crashes.
Sleeping Barber Scenario
Question 1 of 1Test your understanding of the waiting room logic.