Other Classic Synchronization Problems
The Sleeping Barber Problem
Read aloud is unavailable in this browser.
A Shop, A Barber, and the Art of Waiting
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
Formal Problem Statement
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:
- Single Barber: There is exactly one barber who can serve one customer at a time
- Barber Chair: There is exactly one barber chair where haircuts occur
- Waiting Room: There are exactly N waiting chairs (finite capacity)
- Barber Behavior: When no customers are waiting, the barber sleeps in the barber chair
- Customer Arrival: Customers arrive at random intervals, independent of each other
Customer Actions Upon Arrival:
- If the barber is sleeping, the customer wakes them up and sits in the barber chair for a haircut
- If the barber is busy but waiting chairs are available, the customer sits and waits
- If the barber is busy and all waiting chairs are full, the customer leaves immediately
The problem involves three distinct resources that must be coordinated:
- The barber's attention — only one customer can have it at a time
- The barber chair — exclusive access during haircut
- Waiting chairs — bounded capacity, first-come-first-served
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):
- Mutual Exclusion: Only one customer receives a haircut at a time
- Capacity Enforcement: No more than N customers wait at any time
- No Race Conditions: Customer count and state transitions are atomic
Liveness Properties (something good eventually happens):
- No Deadlock: The system never reaches a state where both the barber and customers are waiting forever
- No Unnecessary Blocking: Customers are served if the barber is available
- Progress: If customers are waiting, the barber eventually serves them
Fairness Properties (optional but desirable):
- Bounded Waiting: A waiting customer is eventually served
- FIFO Service: Customers are served in arrival order (not strictly required, but often desired)
| 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 |
Synchronization Challenges
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 barber waits for customers (consumes service requests)
- Customers signal availability (produce service requests)
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:
- Atomically check if space is available
- Only allow the customer to wait if space exists
- Ensure the count of waiting customers is always accurate
Challenge 3: Mutual Exclusion for State Transitions
Multiple state variables must be updated atomically:
- Number of waiting customers
- Barber's state (sleeping vs. cutting)
- Which customer is currently being served
Without proper mutual exclusion, concurrent updates create inconsistent states.
The Sleeping Barber combines three fundamental patterns:
- Producer-Consumer: Customers produce work; barber consumes it
- Bounded Buffer: Limited waiting capacity with rejection policy
- Rendezvous: Barber and customer must synchronize for service delivery
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:
- Customer signals "I'm ready for my haircut"
- Barber acknowledges and begins cutting
- Barber signals "haircut complete"
- Customer receives signal and leaves
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 |
Semaphore-Based Solution
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 capacity
The 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.
Detailed Correctness Analysis
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:
- Only one barber thread exists, and it executes
cut_hair()sequentially - A customer only proceeds to
get_haircut()after receivingsem_post(&barber)from the barber - The barber only issues
sem_post(&barber)once per iteration of its loop - Therefore, at most one customer can be past the
sem_wait(&barber)at any time ∎
Property 2: Bounded Waiting Room Capacity
Claim: At most CHAIRS customers are in the waiting state.
Proof:
waitingis only incremented inside the mutex-protected critical section- The increment only occurs if
waiting < CHAIRS waitingis decremented by the barber when a customer moves to service- The invariant
0 ≤ waiting ≤ CHAIRSis maintained ∎
Property 3: No Deadlock
Claim: The system is deadlock-free.
Proof by contradiction:
Assume deadlock occurs. In deadlock:
- The barber is blocked on
sem_wait(&customers)(waiting for customers) - At least one customer is blocked on
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:
- "Barber sleeps" means barber is blocked on
sem_wait(&customers)withcustomers == 0 - Customer arriving executes
sem_post(&customers)which increments to 1 sem_postwakes any thread blocked on that semaphore- Therefore, barber wakes up ∎
| 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.
Real-World System Mappings
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:
- Barber = Database connection handler thread
- Waiting room chairs = Pending request queue capacity
- Customers = Application threads requesting connections
- Haircut = Executing a database query
- Balking = Returning error when pool and queue are full
Connection pool libraries like HikariCP use these exact synchronization patterns to manage bounded pools with bounded queues.
- •Worker threads = Barbers
- •Task queue = Waiting room
- •Submitted tasks = Customers
- •Queue capacity = Number of chairs
- •Rejection policy = Balking behavior
- •Request handler = Barber
- •Listen queue backlog = Waiting room
- •Incoming requests = Customers
- •TCP backlog limit = Number of chairs
- •Connection refused = Balking
Printer Spooler Systems
Print spoolers implement the Sleeping Barber pattern:
- The printer device driver (barber) sleeps when no jobs are queued
- Print jobs (customers) arrive from applications
- The spooler queue (waiting room) has finite capacity
- When queue is full, new print requests are rejected
Message Broker Consumers
Message queue consumers follow this pattern:
- Consumer threads sleep waiting for messages
- Messages arrive from producers
- Queue has configurable capacity limits
- Backpressure mechanisms reject or slow producers when full
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.
Extension: Multiple Barbers
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:
- There are B barbers, each with their own barber chair
- There are N waiting chairs shared among all customers
- Each barber works independently but draws from the same waiting queue
- When all barbers are sleeping and a customer arrives, any one barber wakes up
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.
Common Pitfalls and Debugging
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;}- •Not initializing semaphores correctly:
customersmust start at 0, not atwaitingvalue - •Race between checking and decrementing
waiting: Barber must hold mutex when decrementing - •Customers incrementing
waitingoutside mutex: Creates race with capacity check - •Barber not decrementing
waiting: Leads to artificial capacity limits - •Using binary semaphore for
customers: Must be counting semaphore to handle multiple waiters
When debugging, add logging that shows:
- Thread ID and action (customer arriving, barber waking, etc.)
- Semaphore values before/after each operation
- Mutex state and waiting count
Traces help identify the exact interleaving that causes failures. Tools like ThreadSanitizer can detect races automatically.
KEEP LEARNING
Keep learning for free.
Read the complete lesson, save your notes and pick up where you left off with a free account. No card needed.