101
0/240
Loading content...
Imagine a small barbershop with a single barber, one barber chair, and a waiting room containing a fixed number of chairs. When no customers are present, the barber sits in his chair and falls asleep. When a customer arrives, they must wake the barber if he is sleeping, or sit in one of the waiting chairs if the barber is busy. If all waiting chairs are occupied, the customer must leave without getting a haircut.
This seemingly simple scenario encapsulates one of the most elegant and instructive synchronization problems in computer science: The Sleeping Barber Problem, introduced by Edsger W. Dijkstra in 1965. What makes this problem profound is not its complexity, but how naturally it maps to real-world concurrent programming challenges—server connection pools, thread pools, request queues with bounded capacity, and any system where consumers must coordinate access to limited service capacity with finite waiting space.
By the end of this page, you will:
• Deeply understand the Sleeping Barber problem and its variants • Recognize the synchronization challenges: mutual exclusion, conditional waiting, and signaling • Implement correct solutions using semaphores • Identify how this problem maps to real-world systems (connection pools, thread pools, service queues) • Analyze why naive solutions fail and how to avoid common pitfalls
Before diving into solutions, we must precisely define the problem. Imprecise problem statements lead to incomplete solutions.
The Scenario:
A barbershop operates under the following constraints:
Customer Actions Upon Arrival:
The problem involves three distinct resources that must be coordinated:
Additionally, we must coordinate two asymmetric roles: the barber (service provider) and customers (service consumers).
Correctness Requirements:
A correct solution must satisfy these properties:
Safety Properties (nothing bad happens):
Liveness Properties (something good eventually happens):
Fairness Properties (optional but desirable):
| Barber State | Waiting Customers | System Behavior | Next Customer Action |
|---|---|---|---|
| Sleeping | 0 | Barber idle, waiting room empty | Wake barber, get haircut immediately |
| Cutting hair | 0 | Serving one, none waiting | Sit in waiting room (if space) |
| Cutting hair | 1 to N-1 | Serving one, some waiting | Sit in waiting room (if space) |
| Cutting hair | N | Serving one, waiting room full | Leave immediately (balk) |
| Done cutting | 0 | Transitioning to next customer | System invokes next waiter |
The Sleeping Barber problem elegantly combines multiple synchronization challenges that must be solved simultaneously. Understanding these challenges individually clarifies why naive solutions fail.
Challenge 1: The Wakeup Coordination Problem
When the barber sleeps, a customer must wake them. This involves a classic producer-consumer coordination where:
The danger is a lost wakeup: if the barber checks for customers and finds none, then a customer arrives and signals before the barber goes to sleep, the signal is lost. The barber sleeps forever while a customer waits forever—deadlock.
123456789101112131415161718192021222324
// BROKEN: Demonstrates the lost wakeup race condition // Shared state (unprotected)int waiting_customers = 0; void barber() { while (true) { // RACE CONDITION WINDOW OPENS HERE if (waiting_customers == 0) { // Suppose a customer arrives RIGHT HERE // Customer increments waiting_customers to 1 // Customer signals wakeup (but barber not sleeping yet!) sleep(); // Barber goes to sleep AFTER signal was sent // DEADLOCK: Signal was lost, barber sleeps forever } // Cut hair... }} void customer() { waiting_customers++; // Might happen during barber's check wakeup_barber(); // Signal lost if barber not sleeping yet // Wait for haircut...}Challenge 2: The Bounded Buffer Constraint
The waiting room has finite capacity. When full, arriving customers must be turned away. This is a bounded buffer scenario, but with a twist: customers who can't wait must balk (leave immediately) rather than block.
This introduces the need to:
Challenge 3: Mutual Exclusion for State Transitions
Multiple state variables must be updated atomically:
Without proper mutual exclusion, concurrent updates create inconsistent states.
The Sleeping Barber combines three fundamental patterns:
Recognizing these patterns helps decompose the problem into manageable parts.
Challenge 4: The Rendezvous Problem
When a customer wakes the barber, they must coordinate to actually perform the haircut. The customer can't leave before the haircut completes, and the barber can't serve the next customer until the current one vacates the chair.
This requires a barrier-like synchronization where:
Without this coordination, customers might leave before their haircut, or the barber might try to serve the same customer twice.
| Challenge | Incorrect Handling | Consequence |
|---|---|---|
| Lost Wakeup | Signal before sleep | Deadlock: barber and customer wait forever |
| Race on Count | Non-atomic check-then-act | Too many customers admitted; capacity violated |
| Multiple Barber Chairs | No exclusion on chair access | Multiple customers served simultaneously |
| Premature Customer Departure | No completion handshake | Customer leaves mid-haircut |
| Barber Double-Serves | No rendezvous protocol | Same customer served twice, other starves |
Now we develop a correct solution using semaphores. We use three semaphores and a mutex to coordinate the barber and customers:
Semaphores:
customers: Counts customers waiting (including one in barber chair). The barber waits on this.barber: Signals that the barber is ready for the next customer. Customers wait on this.mutex: Provides mutual exclusion for accessing shared state.Shared Variables:
waiting: Number of customers in waiting room (not including the one being served)CHAIRS: Constant defining waiting room capacityThe key insight is using semaphores both for signaling (wakeup coordination) and counting (bounded buffer).
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177
/* * The Sleeping Barber Problem - Correct Semaphore Solution * * This solution uses Dijkstra's original approach with three semaphores: * - customers: signals presence of waiting customers (count) * - barber: signals barber readiness (binary-like behavior) * - mutex: protects the waiting count variable */ #include <semaphore.h>#include <pthread.h>#include <stdio.h>#include <unistd.h> #define CHAIRS 5 // Number of waiting room chairs sem_t customers; // Counts waiting customers (semaphore value = waiting count)sem_t barber; // Signals barber is ready for next customerpthread_mutex_t mutex; // Protects 'waiting' variable int waiting = 0; // Customers currently in waiting room /* ============================================ * BARBER THREAD * ============================================ */void* barber_thread(void* arg) { while (1) { /* * Step 1: Wait for a customer to arrive * * sem_wait decrements 'customers' semaphore. * If customers == 0, barber blocks (sleeps) here. * When a customer arrives and posts to 'customers', * the barber wakes up. */ sem_wait(&customers); /* * Step 2: Acquire mutex to safely decrement waiting count * * We must hold the mutex while modifying 'waiting' to prevent * race conditions with arriving customers. */ pthread_mutex_lock(&mutex); waiting--; // Customer moved from waiting room to barber chair /* * Step 3: Signal that barber is ready * * This wakes up the customer who is waiting for service. * The customer was blocked on sem_wait(&barber). */ sem_post(&barber); pthread_mutex_unlock(&mutex); /* * Step 4: Cut hair (critical section - service delivery) * * The actual work happens here. In a real system, * this could be processing a request, handling a connection, etc. */ cut_hair(); } return NULL;} /* ============================================ * CUSTOMER THREAD * ============================================ */void* customer_thread(void* arg) { int customer_id = *(int*)arg; /* * Step 1: Acquire mutex to check and modify waiting count * * We need mutual exclusion because we're doing a compound operation: * checking if space is available AND reserving a spot. */ pthread_mutex_lock(&mutex); /* * Step 2: Check if waiting room has space (bounded buffer check) */ if (waiting < CHAIRS) { /* * Step 3a: Space available - join the queue */ waiting++; // Reserve a spot in waiting room /* * Step 4: Signal barber that a customer is waiting * * sem_post increments 'customers' semaphore. * If barber was sleeping (blocked on sem_wait), this wakes him. * If barber was busy, this just increments the count. */ sem_post(&customers); pthread_mutex_unlock(&mutex); // Release mutex before blocking /* * Step 5: Wait for barber to be ready * * Block until barber signals readiness with sem_post(&barber). * This ensures proper handoff between barber and customer. */ sem_wait(&barber); /* * Step 6: Get haircut * * Customer is now in barber chair receiving service. */ get_haircut(); printf("Customer %d: haircut complete, leaving satisfied", customer_id); } else { /* * Step 3b: No space - leave immediately (balk) * * Customer cannot wait, must leave without service. * This is the "balk" behavior in queueing theory. */ pthread_mutex_unlock(&mutex); printf("Customer %d: no space, leaving without haircut", customer_id); } return NULL;} /* ============================================ * SERVICE FUNCTIONS * ============================================ */void cut_hair() { printf("Barber: cutting hair..."); sleep(3); // Simulate haircut duration printf("Barber: done with this customer");} void get_haircut() { printf("Customer: getting haircut..."); // Duration controlled by cut_hair() - customer just waits} /* ============================================ * INITIALIZATION AND MAIN * ============================================ */int main() { // Initialize semaphores sem_init(&customers, 0, 0); // Initially no customers waiting sem_init(&barber, 0, 0); // Barber not ready initially pthread_mutex_init(&mutex, NULL); // Create barber thread pthread_t barber_tid; pthread_create(&barber_tid, NULL, barber_thread, NULL); // Simulate customer arrivals for (int i = 0; i < 20; i++) { pthread_t customer_tid; int* id = malloc(sizeof(int)); *id = i; pthread_create(&customer_tid, NULL, customer_thread, id); // Random arrival interval usleep((rand() % 1000) * 1000); // 0-1000ms } // In practice, would join threads and cleanup pthread_join(barber_tid, NULL); return 0;}Lost Wakeup Prevention: The customer posts to 'customers' semaphore BEFORE blocking on 'barber'. The barber waits on 'customers', so the signal is never lost.
Atomic Capacity Check: The mutex protects the check-then-increment of 'waiting', preventing over-admission.
Bounded Waiting: Customers block on 'barber' with FIFO ordering (if semaphore is FIFO), ensuring bounded waiting.
No Deadlock: Mutex is always released before any blocking wait on semaphores.
Let's rigorously verify that our solution satisfies all correctness properties. This type of analysis is essential for concurrent programs where intuition often fails.
Property 1: Mutual Exclusion on Barber Chair
Claim: At most one customer is being served at any time.
Proof:
cut_hair() sequentiallyget_haircut() after receiving sem_post(&barber) from the barbersem_post(&barber) once per iteration of its loopsem_wait(&barber) at any time ∎Property 2: Bounded Waiting Room Capacity
Claim: At most CHAIRS customers are in the waiting state.
Proof:
waiting is only incremented inside the mutex-protected critical sectionwaiting < CHAIRSwaiting is decremented by the barber when a customer moves to service0 ≤ waiting ≤ CHAIRS is maintained ∎Property 3: No Deadlock
Claim: The system is deadlock-free.
Proof by contradiction:
Assume deadlock occurs. In deadlock:
sem_wait(&customers) (waiting for customers)sem_wait(&barber) (waiting for barber)But if a customer is blocked on sem_wait(&barber), they already executed sem_post(&customers) (line order in code). This means the customers semaphore was incremented, so the barber cannot be blocked—contradiction.
Alternatively, if customers are blocked on mutex, no thread holds it indefinitely (mutex is always released before blocking waits). ∎
Property 4: No Lost Wakeups
Claim: If a customer arrives while the barber sleeps, the barber wakes up.
Proof:
sem_wait(&customers) with customers == 0sem_post(&customers) which increments to 1sem_post wakes any thread blocked on that semaphore| State | customers value | barber value | waiting value |
|---|---|---|---|
| Barber sleeping, none waiting | 0 | 0 | 0 |
| Customer arrives, wakes barber | 1 → 0 | 0 → 1 | 1 → 0 |
| Barber cutting, 2 waiting | 2 | 0 | 2 |
| Barber finishes, signals next | 2 → 1 | 0 → 1 | 2 → 1 |
| Customer gets signal, enters chair | 1 | 1 → 0 | 1 |
At all times: customers.value == waiting (number of customers who have signaled arrival but not yet been served). This invariant is key to understanding why the solution works. The mutex ensures atomic updates to 'waiting' that correspond to semaphore operations.
The Sleeping Barber problem is not merely academic—it directly models many real-world systems. Understanding these mappings helps recognize when to apply this pattern.
Connection Pool Management
Database connection pools exactly mirror the Sleeping Barber:
Connection pool libraries like HikariCP use these exact synchronization patterns to manage bounded pools with bounded queues.
Printer Spooler Systems
Print spoolers implement the Sleeping Barber pattern:
Message Broker Consumers
Message queue consumers follow this pattern:
Apache Kafka consumers, RabbitMQ channel consumers, and AWS SQS pollers all implement variations of this synchronization pattern.
Anytime you encounter a system with these characteristics, think Sleeping Barber:
• Single or few servers handling work • Bounded queue for pending work • Bursty arrival of work items • Server sleeps when queue empty • Rejection policy when queue full
The semaphore solution translates directly to condition variables, channels, or async/await constructs depending on your platform.
A natural extension is the Multiple Barbers variant, which models systems with multiple equivalent service providers (thread pools with multiple workers, multi-core request handlers, etc.).
Extended Problem Statement:
Key Insight: The solution generalizes naturally because the customers semaphore already acts as a counting mechanism. Multiple barber threads can all wait on it, and customers signal it. The semaphore's internal queue handles waking exactly one barber per customer.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
/* * Multiple Barbers Extension * * The key insight is that multiple barber threads can share * the same semaphores. The 'customers' semaphore naturally * handles waking one barber per customer. */ #define NUM_BARBERS 3#define CHAIRS 10 sem_t customers;sem_t barber_ready[NUM_BARBERS]; // One per barber for debuggingpthread_mutex_t mutex;int waiting = 0; void* barber_thread(void* arg) { int barber_id = *(int*)arg; while (1) { printf("Barber %d: checking for customers...", barber_id); // Wait for any customer - multiple barbers compete here sem_wait(&customers); pthread_mutex_lock(&mutex); waiting--; printf("Barber %d: serving customer, %d still waiting", barber_id, waiting); pthread_mutex_unlock(&mutex); // Signal ready (for this barber's customer) sem_post(&barber_ready[barber_id]); // Perform haircut cut_hair(barber_id); } return NULL;} void* customer_thread(void* arg) { int customer_id = *(int*)arg; pthread_mutex_lock(&mutex); if (waiting < CHAIRS) { waiting++; int my_position = waiting; printf("Customer %d: waiting in position %d", customer_id, my_position); sem_post(&customers); // Wake up any sleeping barber pthread_mutex_unlock(&mutex); // In a fair variant, would need assignment to specific barber // Simplified: assume any barber_ready signal works for us // Real implementation needs more sophisticated matching get_haircut(); printf("Customer %d: haircut complete", customer_id); } else { pthread_mutex_unlock(&mutex); printf("Customer %d: shop full, leaving", customer_id); } return NULL;} /* * Note: This simplified version has a subtle fairness issue. * The sem_post(&barber_ready[barber_id]) may not go to the * customer that originally woke this barber. In practice, * you'd use a single barber semaphore or explicit queuing. */With multiple barbers, preserving FIFO ordering becomes more complex. The simple solution above doesn't guarantee the first waiting customer gets served first. For strict FIFO, you need an explicit queue data structure protected by the mutex, where each barber dequeues the next customer.
Implementing the Sleeping Barber correctly requires avoiding several subtle bugs. Here are the most common pitfalls:
Pitfall 1: Mutex Held During Blocking Wait
If the customer holds the mutex while waiting on barber semaphore, deadlock occurs:
12345678910111213141516171819202122232425262728293031323334353637
// WRONG: Holding mutex during semaphore waitvoid* customer_wrong(void* arg) { pthread_mutex_lock(&mutex); if (waiting < CHAIRS) { waiting++; sem_post(&customers); // BUG: Still holding mutex! sem_wait(&barber); // Blocks while holding mutex // Barber can't acquire mutex to signal // DEADLOCK! pthread_mutex_unlock(&mutex); get_haircut(); } else { pthread_mutex_unlock(&mutex); } return NULL;} // CORRECT: Release mutex before blockingvoid* customer_correct(void* arg) { pthread_mutex_lock(&mutex); if (waiting < CHAIRS) { waiting++; sem_post(&customers); pthread_mutex_unlock(&mutex); // Release BEFORE waiting sem_wait(&barber); // Safe to block now get_haircut(); } else { pthread_mutex_unlock(&mutex); } return NULL;}Pitfall 2: Incorrect Semaphore Order
If the barber signals barber before waiting on customers, customers can proceed without actual service:
12345678910111213141516171819202122232425262728293031
// WRONG: Signaling before waitingvoid* barber_wrong(void* arg) { while (1) { pthread_mutex_lock(&mutex); // BUG: Post barber signal before actually ready sem_post(&barber); // Customer can proceed immediately sem_wait(&customers); // Now waiting, but customer already gone! // Customer thinks they got a haircut but barber hasn't done anything pthread_mutex_unlock(&mutex); cut_hair(); // Cutting hair for nobody } return NULL;} // CORRECT: Wait for customer first, then signal readyvoid* barber_correct(void* arg) { while (1) { sem_wait(&customers); // Wait for customer first pthread_mutex_lock(&mutex); waiting--; sem_post(&barber); // Then signal barber is ready pthread_mutex_unlock(&mutex); cut_hair(); // Actually cut the waiting customer's hair } return NULL;}customers must start at 0, not at waiting valuewaiting: Barber must hold mutex when decrementingwaiting outside mutex: Creates race with capacity checkwaiting: Leads to artificial capacity limitscustomers: Must be counting semaphore to handle multiple waitersWhen debugging, add logging that shows:
Traces help identify the exact interleaving that causes failures. Tools like ThreadSanitizer can detect races automatically.
The Sleeping Barber problem teaches essential synchronization concepts that recur throughout systems programming. Let's consolidate what we've learned:
You now deeply understand the Sleeping Barber problem—its challenges, correct solution, and real-world applications. This foundation prepares you for the next classic problem: the Cigarette Smokers Problem, which introduces the challenge of matching producers with specific resource combinations.