Operating SystemsClassic OS Problems

Classic Operating System Problems

LevelAdvanced

Duration120 mins

TopicClassic OS Problems

4 / 5

Sleeping Barber Problem

The Shop That Never Closes

Imagine a barbershop with one barber, one barber chair, and a waiting room with N chairs. The barber's life is simple:

If there are customers waiting, serve one
If no customers are waiting, sleep in the barber chair

Customers' lives are equally simple:

If the barber is sleeping, wake them up and get a haircut
If the barber is busy but waiting room has space, sit and wait
If the waiting room is full, leave

This deceptively simple scenario, formulated by Edsger Dijkstra, captures a fundamental pattern in computing: bounded capacity service with sleeping servers. The Sleeping Barber Problem models connection pooling, thread pools, web servers, ticket counters, and any system where service providers idle when no work exists but must be awakened by arriving requests.

What You Will Learn

By the end of this page, you will understand the sleeping barber problem comprehensively: its formal specification, race conditions in naive approaches, correct semaphore and monitor solutions, variations (multiple barbers, FIFO ordering, priority), and mapping to real-world systems like connection pools, thread pools, and request handlers.

Formal Problem Definition

The sleeping barber problem involves:

Barber (Server): A single service provider who:

Cuts hair (serves requests) when customers are present
Sleeps when no customers are waiting
Must be awakened by arriving customers when sleeping

Customers (Clients): Processes that arrive seeking service:

If barber is free, get immediate service
If barber is busy but waiting room has space, join queue
If waiting room is full, leave (balking)

Waiting Room (Bounded Buffer): N chairs for waiting customers

Correctness Requirements

Mutual Exclusion: Only one customer in the barber chair at a time.
No Lost Wakeups: If a customer arrives while the barber sleeps, the barber must wake up.
Bounded Waiting Room: At most N customers wait; excess customers leave.
No Deadlock: Neither barber nor customers block indefinitely.
FIFO Fairness (optional but desirable): Customers served in arrival order.

Sleeping Barber System States
State	Barber Activity	Waiting Room	Arriving Customer Action
Idle	Sleeping	Empty (0)	Wake barber, get haircut
Busy, Room Available	Cutting hair	1 to N-1 customers	Join waiting room
Busy, Room Full	Cutting hair	N customers	Leave immediately (balking)

Producer-Consumer Connection

The sleeping barber is closely related to producer-consumer with a twist: there's asymmetry between producers (customers) and the consumer (barber). Unlike classical producer-consumer where both sides are symmetric threads, the barber is a distinguished server that sleeps when idle and must be explicitly awakened.

Race Conditions in Naive Solutions

The sleeping barber has a subtle race condition that makes naive implementations incorrect. Let's examine the problem:

The Wakeup Problem

Consider this sequence without proper synchronization:

Barber checks if customers waiting → none → prepares to sleep
Customer arrives, sees barber's chair (appears empty), tries to wake barber
Barber goes to sleep (after customer's wakeup already sent!)
Customer waits for haircut that never comes
Barber sleeps forever → DEADLOCK

The problem is a lost wakeup: the customer's wakeup signal is lost because the barber wasn't yet sleeping when it arrived.

broken-barber.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// BROKEN: Lost wakeup race condition
#define N 5  // Waiting room chairs
int waiting = 0;  // Customers in waiting room
bool barber_sleeping = false;
 
void barber(void) {
    while (true) {
        if (waiting == 0) {
            barber_sleeping = true;  // RACE: Gap before actually sleeping!
            sleep();                  // May miss wakeup sent in the gap
            barber_sleeping = false;
        }
        
        // Cut hair
        waiting--;
        cut_hair();
    }
}
 
void customer(void) {
    if (waiting == N) {
        leave();  // Waiting room full
        return;
    }
    
    waiting++;
    
    if (barber_sleeping) {
        wakeup_barber();  // May execute BEFORE barber actually sleeps!
    }
    
    wait_for_haircut();
    get_haircut();
}
 
/*
 * RACE CONDITION SCENARIO:
 * 
 * Time T0: Barber sees waiting == 0
 * Time T1: Customer arrives, increments waiting to 1
 * Time T2: Customer sees barber_sleeping == false (not yet!)
 * Time T3: Customer doesn't call wakeup (thinks barber is awake)
 * Time T4: Barber sets barber_sleeping = true and sleeps
 * 
 * Result: Barber sleeps forever with 1 customer waiting!
 */

The Fundamental Issue

The race occurs because checking the condition and acting on it are not atomic. Both the barber (check waiting → sleep) and customer (check sleeping → wakeup) have a gap between checking and acting.

This is the same lost wakeup problem that plagues any sleep/wakeup mechanism. The solution requires:

Atomic check-and-sleep: The barber must atomically verify no customers AND go to sleep
Atomic check-and-wakeup: The customer must atomically signal arrival AND wakeup the barber if needed

Semaphores provide exactly this guarantee: wait() atomically decrements and blocks if zero; signal() atomically increments and wakes waiters.

Never Check-Then-Act Without Atomicity

The check-then-act pattern without synchronization is the root cause of countless concurrency bugs. Any time you see 'if (condition) then action' where both condition and action involve shared state, you must ensure atomicity—either through locks, semaphores, or atomic operations.

The Correct Semaphore Solution

The correct solution uses three semaphores:

customers (init = 0): Counting semaphore. Represents waiting customers. Barber waits on this when idle.

barber (init = 0): Binary semaphore. Signals that barber is ready to cut. Customers wait on this for service.

mutex (init = 1): Binary semaphore. Protects the waiting counter from race conditions.

semaphore-barber.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <semaphore.h>
 
#define N 5  // Waiting room chairs
 
sem_t customers;  // Number of customers waiting (init = 0)
sem_t barber;     // Barber ready to cut (init = 0)
sem_t mutex;      // Protects 'waiting' counter (init = 1)
int waiting = 0;  // Customers in waiting room
 
void barber_thread(void) {
    while (true) {
        // Wait for a customer (blocks if none)
        sem_wait(&customers);
        
        // Decrement waiting count (protected)
        sem_wait(&mutex);
        waiting--;
        sem_post(&mutex);
        
        // Signal that barber is ready for this customer
        sem_post(&barber);
        
        // Cut hair (outside critical section)
        cut_hair();
    }
}
 
void customer_thread(void) {
    sem_wait(&mutex);
    
    if (waiting < N) {
        // Room available: join waiting room
        waiting++;
        
        // Signal barber that a customer is waiting
        sem_post(&customers);
        
        sem_post(&mutex);
        
        // Wait for barber to be ready
        sem_wait(&barber);
        
        // Get haircut (barber is ready)
        get_haircut();
    } else {
        // Waiting room full: leave
        sem_post(&mutex);
        leave_shop();
    }
}

Why This Works

No Lost Wakeups:

Barber's sem_wait(&customers) atomically blocks if no customers
Customer's sem_post(&customers) atomically wakes barber if blocked
No gap between checking and sleeping/waking

Mutual Exclusion:

mutex ensures only one thread modifies waiting at a time
This prevents races on the counter

Bounded Waiting Room:

Customer checks waiting < N while holding mutex
If full, customer leaves without modifying state

Correct Handoff:

Customer signals arrival via customers
Customer then waits on barber for actual service
Barber signals barber after committing to serve
This two-signal rendezvous ensures proper coordination

Semaphore Values During Execution
Event	customers	barber	waiting	Description
Initial state	0	0	0	Barber blocked on customers
Customer 1 arrives	1→0	0	1→0	Barber wakes, customer waits on barber
Barber starts cutting	0	1→0	0	Customer unblocked, getting haircut
Customer 2, 3 arrive	2	0	2	Barber busy, both wait on barber
Barber finishes C1	2→1	1→0	2→1	C2 gets its turn

FIFO Not Guaranteed

This solution doesn't guarantee FIFO service. When multiple customers wait on the barber semaphore, the wake order depends on the semaphore implementation (often unspecified). For strict FIFO, use a queue with condition variables as shown in the monitor solution.

The Monitor Solution with FIFO Guarantee

For guaranteed FIFO service order, we use a monitor with an explicit queue. This is the typical implementation in high-level languages.

monitor-barber.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.locks.*;
 
public class BarberShop {
    private final int waitingRoomCapacity;
    private final Queue<CustomerCallback> waitingCustomers;
    private boolean barberSleeping;
    
    private final Lock lock = new ReentrantLock();
    private final Condition customerArrived = lock.newCondition();
    
    public BarberShop(int capacity) {
        this.waitingRoomCapacity = capacity;
        this.waitingCustomers = new LinkedList<>();
        this.barberSleeping = true;  // Barber starts asleep
    }
    
    // Called by barber thread
    public void barberWork() throws InterruptedException {
        while (true) {
            CustomerCallback customer = waitForCustomer();
            
            // Cut hair (outside lock - allows customers to queue)
            cutHair();
            
            // Signal this specific customer that haircut is done
            customer.haircutComplete();
        }
    }
    
    private CustomerCallback waitForCustomer() throws InterruptedException {
        lock.lock();
        try {
            while (waitingCustomers.isEmpty()) {
                barberSleeping = true;
                customerArrived.await();  // Sleep until signaled
            }
            barberSleeping = false;
            return waitingCustomers.poll();  // FIFO: first in queue
        } finally {
            lock.unlock();
        }
    }
    
    // Called by customer threads
    public boolean getHaircut(CustomerCallback callback) throws InterruptedException {
        lock.lock();
        try {
            if (waitingCustomers.size() >= waitingRoomCapacity) {
                // Waiting room full
                return false;  // Customer leaves
            }
            
            // Add to queue (FIFO order maintained)
            waitingCustomers.offer(callback);
            
            // Wake barber if sleeping
            if (barberSleeping) {
                customerArrived.signal();
            }
        } finally {
            lock.unlock();
        }
        
        // Wait for haircut completion (outside lock)
        callback.awaitHaircut();
        return true;
    }
    
    private void cutHair() {
        // Simulate haircut duration
        try { Thread.sleep(100); } catch (InterruptedException e) {}
    }
}
 
// Callback for customer to await individual completion
class CustomerCallback {
    private final Lock lock = new ReentrantLock();
    private final Condition done = lock.newCondition();
    private boolean complete = false;
    
    public void awaitHaircut() throws InterruptedException {
        lock.lock();
        try {
            while (!complete) {
                done.await();
            }
        } finally {
            lock.unlock();
        }
    }
    
    public void haircutComplete() {
        lock.lock();
        try {
            complete = true;
            done.signal();
        } finally {
            lock.unlock();
        }
    }
}

Key Design Decisions

Explicit Queue: Using LinkedList<CustomerCallback> ensures exact FIFO order, unlike semaphores where wakeup order is implementation-defined.

Individual Callbacks: Each customer has its own callback for haircut completion. This allows the barber to signal the specific customer being served, not just wake any waiter.

Lock Discipline: The main lock protects the queue and barber state. Actual haircut happens outside the lock to maximize concurrency.

Rejection Semantics: When full, getHaircut() returns false immediately. The customer can retry or give up—application decides.

Java Executor Service

Java's ThreadPoolExecutor implements the sleeping barber pattern internally. Worker threads sleep when the work queue is empty, wake when tasks arrive, and the queue is bounded (causing rejection when full). The implementation uses ReentrantLock and Condition, exactly as shown here.

Multiple Barbers Variation

Real barbershops (and real servers) often have multiple barbers. Extending the solution to M barbers requires careful consideration.

Approach 1: Single Queue, Multiple Workers

The simplest extension: multiple barbers share a single customer queue. This naturally load-balances—whichever barber finishes first takes the next customer.

multi-barber.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <semaphore.h>
 
#define M 3   // Number of barbers
#define N 10  // Waiting room capacity
 
sem_t customers;      // Customers waiting (init = 0)
sem_t barber_ready;   // Available barbers (init = M)
sem_t mutex;          // Protects waiting counter
 
int waiting = 0;
 
// Each barber runs this
void barber_thread(int barber_id) {
    while (true) {
        // Wait for a customer
        sem_wait(&customers);
        
        // Get exclusive access to waiting count
        sem_wait(&mutex);
        waiting--;
        sem_post(&mutex);
        
        // Signal that this barber is handling a customer
        sem_post(&barber_ready);
        
        printf("Barber %d cutting hair
", barber_id);
        cut_hair();
    }
}
 
void customer_thread(int customer_id) {
    sem_wait(&mutex);
    
    if (waiting < N) {
        waiting++;
        sem_post(&customers);  // Signal barbers
        sem_post(&mutex);
        
        sem_wait(&barber_ready);  // Wait for any available barber
        printf("Customer %d getting haircut
", customer_id);
        get_haircut();
    } else {
        sem_post(&mutex);
        printf("Customer %d leaving - shop full
", customer_id);
    }
}

Approach 2: Dedicated Queues per Barber

Alternatively, each barber can have their own queue. Customers choose a barber (perhaps the one with the shortest queue). This provides:

Predictable wait times: Customer knows their position in a specific queue
Barber affinity: Repeat customers can choose their preferred barber
Isolation: One slow barber doesn't block customers in other queues

Trade-off: Potential load imbalance if customers guess wrong about queue lengths.

Approach 3: Work-Stealing

Advanced implementations allow idle barbers to "steal" customers from busy queues:

Barber first checks their own queue
If empty, checks neighbors' queues
Steals from longest queue

This combines the benefits of dedicated queues (locality) with automatic load balancing.

Multi-Barber Queue Strategies
Strategy	Load Balance	Latency Predictability	Implementation
Single Shared Queue	Excellent	Variable (FIFO)	Simple
Dedicated Queues	Customer-dependent	Predictable	Moderate
Work-Stealing	Good	Mostly predictable	Complex

Thread Pool Connection

Java's ForkJoinPool uses work-stealing. Each worker thread has a deque (double-ended queue). Workers push/pop from their own end (LIFO for cache locality) but steal from others' ends (FIFO for fairness). This balances locality with load distribution.

Priority and VIP Variations

Real-world services often have priority customers (first class, premium members, urgent requests). Extending sleeping barber for priorities introduces interesting challenges.

Priority Queue Implementation

priority-barber.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.concurrent.locks.*;
 
public class PriorityBarberShop {
    private final int capacity;
    private final PriorityQueue<PriorityCustomer> queue;
    private boolean barberSleeping = true;
    
    private final Lock lock = new ReentrantLock();
    private final Condition customerArrived = lock.newCondition();
    
    public PriorityBarberShop(int capacity) {
        this.capacity = capacity;
        // Higher priority number = more important = served first
        this.queue = new PriorityQueue<>(
            Comparator.comparingInt(PriorityCustomer::getPriority).reversed()
                      .thenComparing(PriorityCustomer::getArrivalTime)
        );
    }
    
    public boolean enterShop(int customerId, int priority) throws InterruptedException {
        lock.lock();
        try {
            if (queue.size() >= capacity) {
                return false;  // Full, even VIP must leave
            }
            
            PriorityCustomer customer = new PriorityCustomer(
                customerId, 
                priority, 
                System.nanoTime()
            );
            queue.offer(customer);
            
            if (barberSleeping) {
                customerArrived.signal();
            }
        } finally {
            lock.unlock();
        }
        
        // Await service...
        return true;
    }
    
    public void barberServe() throws InterruptedException {
        while (true) {
            PriorityCustomer next;
            
            lock.lock();
            try {
                while (queue.isEmpty()) {
                    barberSleeping = true;
                    customerArrived.await();
                }
                barberSleeping = false;
                next = queue.poll();  // Highest priority first
            } finally {
                lock.unlock();
            }
            
            System.out.printf("Serving customer %d (priority %d)%n", 
                             next.getId(), next.getPriority());
            cutHair();
        }
    }
}
 
class PriorityCustomer {
    private final int id;
    private final int priority;
    private final long arrivalTime;
    
    // Constructor and getters...
}

Starvation Risk with Priorities

Priority systems risk starving low-priority customers under high load:

Time	Arrivals	Queue State	Served
T0	P1 (priority=1)	[P1]
T1	V1 (priority=5)	[V1, P1]
T2		[P1]	V1
T3	V2 (priority=5)	[V2, P1]
T4		[P1]	V2
T5	V3 (priority=5)	[V3, P1]
...	VIPs keep coming	[Vn, P1]	P1 starves!

Anti-Starvation Mechanisms

Aging: Gradually increase priority of waiting customers. Eventually, a waiting regular customer's boosted priority exceeds VIPs.
Quota per Priority: "Serve at most 3 VIPs before one regular customer"
Maximum Wait Time: If a customer waits beyond threshold, promote to highest priority.
Weighted Fair Queuing: Each priority level gets proportional share of service (e.g., VIPs get 70%, regular 30%).

Priority Inversion

In systems where customers can hold resources while waiting, priority schemes can cause priority inversion: a high-priority customer waits for a resource held by a low-priority customer who can't proceed because medium-priority customers keep preempting them. This is exactly the problem that crashed Mars Pathfinder!

Real-World Applications

The sleeping barber pattern is ubiquitous in systems software. Every bounded-capacity server with idle waiting exhibits this pattern.

Sleeping Barber in Production Systems

•Thread Pools (ExecutorService): Worker threads sleep when no tasks queued. Tasks wake workers. Queue has bounded capacity; excess tasks are rejected or block producers.
•Connection Pools (HikariCP, c3p0): Connections idle when unused. Requests wake and acquire connections. Pool size is bounded; excess requests wait or are rejected.
•Web Server Workers (nginx, Apache): Worker processes/threads sleep when no requests. New requests wake workers. Accept queue is bounded; excess connections are dropped.
•Database Query Executors: Query threads sleep awaiting queries. New queries wake threads. Admission control limits concurrent queries.
•Message Queue Consumers (Kafka, RabbitMQ): Consumers poll/block waiting for messages. New messages wake consumers. Consumer groups share work.
•Print Spoolers: Print daemon sleeps when queue empty. Print jobs wake daemon. Queue has maximum size.
•Call Centers: Agents idle between calls. Incoming calls wake agents. Hold queue has limited capacity; excess callers get busy signal.

Case Study: Java ThreadPoolExecutor

thread-pool-as-barber.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.concurrent.*;
 
public class ThreadPoolAsBarberShop {
    public static void main(String[] args) {
        // Create a "barbershop" with:
        // - 3 barbers (core pool size)
        // - Max 5 barbers if overwhelmed (max pool size)
        // - 10-seat waiting room (queue capacity)
        
        BlockingQueue<Runnable> waitingRoom = 
            new ArrayBlockingQueue<>(10);  // Bounded capacity!
        
        ThreadPoolExecutor shop = new ThreadPoolExecutor(
            3,                  // Core barbers
            5,                  // Max barbers
            60, TimeUnit.SECONDS,  // Idle barber goes home after 60s
            waitingRoom,
            new ThreadPoolExecutor.AbortPolicy()  // Reject when full
        );
        
        // Customers (tasks) arrive
        for (int i = 0; i < 20; i++) {
            final int customerId = i;
            try {
                shop.execute(() -> {
                    System.out.println("Cutting hair: " + customerId);
                    try { Thread.sleep(200); } catch (InterruptedException e) {}
                });
                System.out.println("Customer " + customerId + " admitted");
            } catch (RejectedExecutionException e) {
                System.out.println("Customer " + customerId + " rejected - shop full!");
            }
        }
        
        shop.shutdown();
    }
}

The Pattern Everywhere

Once you recognize the sleeping barber pattern—servers that sleep when idle, bounded queues for waiting, wakeup on arrival, rejection when full—you'll see it everywhere. Thread pools, connection pools, web servers, and message queues are all variations of this fundamental abstraction.

Common Pitfalls and Debugging

Implementation of sleeping barber systems often encounters these issues:

Common Implementation Pitfalls

•Lost Wakeups: Check-then-sleep without atomicity. Fix: Use semaphores or condition variables correctly; never check and sleep in separate operations.
•Spurious Wakeups: Thread wakes without corresponding signal. Fix: Always wait in a while loop that rechecks the condition.
•Thundering Herd: Many blocked threads wake simultaneously when one slot frees. Fix: Use signal() not signalAll() when only one can proceed; or use sem_post() which wakes just one.
•Queue Sizing Mistakes: Queue too small causes excessive rejections; too large wastes memory and increases latency. Fix: Profile under realistic load; consider adaptive sizing.
•Missing Rejection Handling: Callers don't handle RejectedExecutionException. Fix: Always check return values or catch exceptions; implement retry logic or backpressure.
•Poison Pills: Need a way to shut down sleeping workers. Fix: Use a sentinel value in queue, or interrupt mechanism to wake sleeping threads during shutdown.

Debugging Techniques

Thread Dumps: When workers appear stuck, a thread dump (jstack in Java, gdb in C) shows what each thread is waiting on.

Queue Metrics: Monitor queue size over time. Constantly near capacity indicates under-provisioned workers or slow processing.

Latency Histograms: Track time from queue entry to service start. Bimodal distribution suggests priority inversion or lock contention.

Rejection Logging: Log every rejection with timestamp and queue state. Cluster analysis reveals traffic patterns causing rejections.

shutdown-pattern.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Poison pill pattern for graceful shutdown
public class ShutdownableBarberShop {
    private final BlockingQueue<Task> queue;
    private static final Task POISON_PILL = new Task(null);
    
    public void shutdown() {
        queue.offer(POISON_PILL);
    }
    
    void barberLoop() throws InterruptedException {
        while (true) {
            Task task = queue.take();
            if (task == POISON_PILL) {
                queue.offer(POISON_PILL);  // Pass poison to next barber
                break;
            }
            process(task);
        }
    }
}

Summary: Sleeping Barber Mastery

The sleeping barber problem captures the essence of bounded-capacity services with sleeping workers. Let's consolidate the key insights:

Key Takeaways

•The Pattern: Servers sleep when idle, wake on customer arrival, serve from bounded queue, reject when full.
•The Race Condition: Lost wakeups occur when check-and-sleep isn't atomic. Semaphores and condition variables provide correct primitives.
•Semaphore Solution: Three semaphores (customers, barber, mutex) coordinate wakeup, handoff, and counter protection.
•Monitor Solution: Lock + condition variable with explicit queue for FIFO guarantees and easier reasoning.
•Multiple Barbers: Single shared queue (simple, balanced), per-barber queues (predictable), or work-stealing (balanced + locality).
•Priority Handling: Priority queues risk starvation; mitigate with aging, quotas, or weighted fair queuing.
•Ubiquitous Pattern: Thread pools, connection pools, web servers, message consumers—all implement sleeping barber variants.
•Debugging Focus: Lost wakeups, thundering herd, queue sizing, and graceful shutdown are common failure modes.

What's Next:

We've now covered four classic OS synchronization problems: producer-consumer, readers-writers, dining philosophers, and sleeping barber. In the final page of this module, we'll step back and examine Problem-Solving Strategies—systematic approaches for analyzing new synchronization problems and designing correct solutions from first principles.

Page Complete

You now possess comprehensive understanding of the sleeping barber problem: the wakeup race condition, correct semaphore and monitor solutions, variations for multiple workers and priorities, and how the pattern manifests in thread pools, connection pools, and servers throughout systems software. This knowledge enables you to design and debug any bounded-capacity service system.

4 / 5

Loading learning content...

Operating SystemsClassic OS Problems

Classic Operating System Problems

LevelAdvanced

Duration120 mins

TopicClassic OS Problems

4 / 5

Sleeping Barber Problem

The Shop That Never Closes

Imagine a barbershop with one barber, one barber chair, and a waiting room with N chairs. The barber's life is simple:

If there are customers waiting, serve one
If no customers are waiting, sleep in the barber chair

Customers' lives are equally simple:

If the barber is sleeping, wake them up and get a haircut
If the barber is busy but waiting room has space, sit and wait
If the waiting room is full, leave

What You Will Learn

Formal Problem Definition

The sleeping barber problem involves:

Barber (Server): A single service provider who:

Cuts hair (serves requests) when customers are present
Sleeps when no customers are waiting
Must be awakened by arriving customers when sleeping

Customers (Clients): Processes that arrive seeking service:

If barber is free, get immediate service
If barber is busy but waiting room has space, join queue
If waiting room is full, leave (balking)

Waiting Room (Bounded Buffer): N chairs for waiting customers

Correctness Requirements

Mutual Exclusion: Only one customer in the barber chair at a time.
No Lost Wakeups: If a customer arrives while the barber sleeps, the barber must wake up.
Bounded Waiting Room: At most N customers wait; excess customers leave.
No Deadlock: Neither barber nor customers block indefinitely.
FIFO Fairness (optional but desirable): Customers served in arrival order.

Sleeping Barber System States
State	Barber Activity	Waiting Room	Arriving Customer Action
Idle	Sleeping	Empty (0)	Wake barber, get haircut
Busy, Room Available	Cutting hair	1 to N-1 customers	Join waiting room
Busy, Room Full	Cutting hair	N customers	Leave immediately (balking)

Producer-Consumer Connection

Race Conditions in Naive Solutions

The sleeping barber has a subtle race condition that makes naive implementations incorrect. Let's examine the problem:

The Wakeup Problem

Consider this sequence without proper synchronization:

Barber checks if customers waiting → none → prepares to sleep
Customer arrives, sees barber's chair (appears empty), tries to wake barber
Barber goes to sleep (after customer's wakeup already sent!)
Customer waits for haircut that never comes
Barber sleeps forever → DEADLOCK

The problem is a lost wakeup: the customer's wakeup signal is lost because the barber wasn't yet sleeping when it arrived.

broken-barber.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// BROKEN: Lost wakeup race condition
#define N 5  // Waiting room chairs
int waiting = 0;  // Customers in waiting room
bool barber_sleeping = false;
 
void barber(void) {
    while (true) {
        if (waiting == 0) {
            barber_sleeping = true;  // RACE: Gap before actually sleeping!
            sleep();                  // May miss wakeup sent in the gap
            barber_sleeping = false;
        }
        
        // Cut hair
        waiting--;
        cut_hair();
    }
}
 
void customer(void) {
    if (waiting == N) {
        leave();  // Waiting room full
        return;
    }
    
    waiting++;
    
    if (barber_sleeping) {
        wakeup_barber();  // May execute BEFORE barber actually sleeps!
    }
    
    wait_for_haircut();
    get_haircut();
}
 
/*
 * RACE CONDITION SCENARIO:
 * 
 * Time T0: Barber sees waiting == 0
 * Time T1: Customer arrives, increments waiting to 1
 * Time T2: Customer sees barber_sleeping == false (not yet!)
 * Time T3: Customer doesn't call wakeup (thinks barber is awake)
 * Time T4: Barber sets barber_sleeping = true and sleeps
 * 
 * Result: Barber sleeps forever with 1 customer waiting!
 */

The Fundamental Issue

This is the same lost wakeup problem that plagues any sleep/wakeup mechanism. The solution requires:

Atomic check-and-sleep: The barber must atomically verify no customers AND go to sleep
Atomic check-and-wakeup: The customer must atomically signal arrival AND wakeup the barber if needed

Semaphores provide exactly this guarantee: wait() atomically decrements and blocks if zero; signal() atomically increments and wakes waiters.

Never Check-Then-Act Without Atomicity

The Correct Semaphore Solution

The correct solution uses three semaphores:

customers (init = 0): Counting semaphore. Represents waiting customers. Barber waits on this when idle.

barber (init = 0): Binary semaphore. Signals that barber is ready to cut. Customers wait on this for service.

mutex (init = 1): Binary semaphore. Protects the waiting counter from race conditions.

semaphore-barber.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <semaphore.h>
 
#define N 5  // Waiting room chairs
 
sem_t customers;  // Number of customers waiting (init = 0)
sem_t barber;     // Barber ready to cut (init = 0)
sem_t mutex;      // Protects 'waiting' counter (init = 1)
int waiting = 0;  // Customers in waiting room
 
void barber_thread(void) {
    while (true) {
        // Wait for a customer (blocks if none)
        sem_wait(&customers);
        
        // Decrement waiting count (protected)
        sem_wait(&mutex);
        waiting--;
        sem_post(&mutex);
        
        // Signal that barber is ready for this customer
        sem_post(&barber);
        
        // Cut hair (outside critical section)
        cut_hair();
    }
}
 
void customer_thread(void) {
    sem_wait(&mutex);
    
    if (waiting < N) {
        // Room available: join waiting room
        waiting++;
        
        // Signal barber that a customer is waiting
        sem_post(&customers);
        
        sem_post(&mutex);
        
        // Wait for barber to be ready
        sem_wait(&barber);
        
        // Get haircut (barber is ready)
        get_haircut();
    } else {
        // Waiting room full: leave
        sem_post(&mutex);
        leave_shop();
    }
}

Why This Works

No Lost Wakeups:

Barber's sem_wait(&customers) atomically blocks if no customers
Customer's sem_post(&customers) atomically wakes barber if blocked
No gap between checking and sleeping/waking

Mutual Exclusion:

mutex ensures only one thread modifies waiting at a time
This prevents races on the counter

Bounded Waiting Room:

Customer checks waiting < N while holding mutex
If full, customer leaves without modifying state

Correct Handoff:

Customer signals arrival via customers
Customer then waits on barber for actual service
Barber signals barber after committing to serve
This two-signal rendezvous ensures proper coordination

Semaphore Values During Execution
Event	customers	barber	waiting	Description
Initial state	0	0	0	Barber blocked on customers
Customer 1 arrives	1→0	0	1→0	Barber wakes, customer waits on barber
Barber starts cutting	0	1→0	0	Customer unblocked, getting haircut
Customer 2, 3 arrive	2	0	2	Barber busy, both wait on barber
Barber finishes C1	2→1	1→0	2→1	C2 gets its turn

FIFO Not Guaranteed

The Monitor Solution with FIFO Guarantee

For guaranteed FIFO service order, we use a monitor with an explicit queue. This is the typical implementation in high-level languages.

monitor-barber.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.locks.*;
 
public class BarberShop {
    private final int waitingRoomCapacity;
    private final Queue<CustomerCallback> waitingCustomers;
    private boolean barberSleeping;
    
    private final Lock lock = new ReentrantLock();
    private final Condition customerArrived = lock.newCondition();
    
    public BarberShop(int capacity) {
        this.waitingRoomCapacity = capacity;
        this.waitingCustomers = new LinkedList<>();
        this.barberSleeping = true;  // Barber starts asleep
    }
    
    // Called by barber thread
    public void barberWork() throws InterruptedException {
        while (true) {
            CustomerCallback customer = waitForCustomer();
            
            // Cut hair (outside lock - allows customers to queue)
            cutHair();
            
            // Signal this specific customer that haircut is done
            customer.haircutComplete();
        }
    }
    
    private CustomerCallback waitForCustomer() throws InterruptedException {
        lock.lock();
        try {
            while (waitingCustomers.isEmpty()) {
                barberSleeping = true;
                customerArrived.await();  // Sleep until signaled
            }
            barberSleeping = false;
            return waitingCustomers.poll();  // FIFO: first in queue
        } finally {
            lock.unlock();
        }
    }
    
    // Called by customer threads
    public boolean getHaircut(CustomerCallback callback) throws InterruptedException {
        lock.lock();
        try {
            if (waitingCustomers.size() >= waitingRoomCapacity) {
                // Waiting room full
                return false;  // Customer leaves
            }
            
            // Add to queue (FIFO order maintained)
            waitingCustomers.offer(callback);
            
            // Wake barber if sleeping
            if (barberSleeping) {
                customerArrived.signal();
            }
        } finally {
            lock.unlock();
        }
        
        // Wait for haircut completion (outside lock)
        callback.awaitHaircut();
        return true;
    }
    
    private void cutHair() {
        // Simulate haircut duration
        try { Thread.sleep(100); } catch (InterruptedException e) {}
    }
}
 
// Callback for customer to await individual completion
class CustomerCallback {
    private final Lock lock = new ReentrantLock();
    private final Condition done = lock.newCondition();
    private boolean complete = false;
    
    public void awaitHaircut() throws InterruptedException {
        lock.lock();
        try {
            while (!complete) {
                done.await();
            }
        } finally {
            lock.unlock();
        }
    }
    
    public void haircutComplete() {
        lock.lock();
        try {
            complete = true;
            done.signal();
        } finally {
            lock.unlock();
        }
    }
}

Key Design Decisions

Explicit Queue: Using LinkedList<CustomerCallback> ensures exact FIFO order, unlike semaphores where wakeup order is implementation-defined.

Individual Callbacks: Each customer has its own callback for haircut completion. This allows the barber to signal the specific customer being served, not just wake any waiter.

Lock Discipline: The main lock protects the queue and barber state. Actual haircut happens outside the lock to maximize concurrency.

Rejection Semantics: When full, getHaircut() returns false immediately. The customer can retry or give up—application decides.

Java Executor Service

Multiple Barbers Variation

Real barbershops (and real servers) often have multiple barbers. Extending the solution to M barbers requires careful consideration.

Approach 1: Single Queue, Multiple Workers

The simplest extension: multiple barbers share a single customer queue. This naturally load-balances—whichever barber finishes first takes the next customer.

multi-barber.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <semaphore.h>
 
#define M 3   // Number of barbers
#define N 10  // Waiting room capacity
 
sem_t customers;      // Customers waiting (init = 0)
sem_t barber_ready;   // Available barbers (init = M)
sem_t mutex;          // Protects waiting counter
 
int waiting = 0;
 
// Each barber runs this
void barber_thread(int barber_id) {
    while (true) {
        // Wait for a customer
        sem_wait(&customers);
        
        // Get exclusive access to waiting count
        sem_wait(&mutex);
        waiting--;
        sem_post(&mutex);
        
        // Signal that this barber is handling a customer
        sem_post(&barber_ready);
        
        printf("Barber %d cutting hair
", barber_id);
        cut_hair();
    }
}
 
void customer_thread(int customer_id) {
    sem_wait(&mutex);
    
    if (waiting < N) {
        waiting++;
        sem_post(&customers);  // Signal barbers
        sem_post(&mutex);
        
        sem_wait(&barber_ready);  // Wait for any available barber
        printf("Customer %d getting haircut
", customer_id);
        get_haircut();
    } else {
        sem_post(&mutex);
        printf("Customer %d leaving - shop full
", customer_id);
    }
}

Approach 2: Dedicated Queues per Barber

Alternatively, each barber can have their own queue. Customers choose a barber (perhaps the one with the shortest queue). This provides:

Predictable wait times: Customer knows their position in a specific queue
Barber affinity: Repeat customers can choose their preferred barber
Isolation: One slow barber doesn't block customers in other queues

Trade-off: Potential load imbalance if customers guess wrong about queue lengths.

Approach 3: Work-Stealing

Advanced implementations allow idle barbers to "steal" customers from busy queues:

Barber first checks their own queue
If empty, checks neighbors' queues
Steals from longest queue

This combines the benefits of dedicated queues (locality) with automatic load balancing.

Multi-Barber Queue Strategies
Strategy	Load Balance	Latency Predictability	Implementation
Single Shared Queue	Excellent	Variable (FIFO)	Simple
Dedicated Queues	Customer-dependent	Predictable	Moderate
Work-Stealing	Good	Mostly predictable	Complex

Thread Pool Connection

Priority and VIP Variations

Real-world services often have priority customers (first class, premium members, urgent requests). Extending sleeping barber for priorities introduces interesting challenges.

Priority Queue Implementation

priority-barber.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.concurrent.locks.*;
 
public class PriorityBarberShop {
    private final int capacity;
    private final PriorityQueue<PriorityCustomer> queue;
    private boolean barberSleeping = true;
    
    private final Lock lock = new ReentrantLock();
    private final Condition customerArrived = lock.newCondition();
    
    public PriorityBarberShop(int capacity) {
        this.capacity = capacity;
        // Higher priority number = more important = served first
        this.queue = new PriorityQueue<>(
            Comparator.comparingInt(PriorityCustomer::getPriority).reversed()
                      .thenComparing(PriorityCustomer::getArrivalTime)
        );
    }
    
    public boolean enterShop(int customerId, int priority) throws InterruptedException {
        lock.lock();
        try {
            if (queue.size() >= capacity) {
                return false;  // Full, even VIP must leave
            }
            
            PriorityCustomer customer = new PriorityCustomer(
                customerId, 
                priority, 
                System.nanoTime()
            );
            queue.offer(customer);
            
            if (barberSleeping) {
                customerArrived.signal();
            }
        } finally {
            lock.unlock();
        }
        
        // Await service...
        return true;
    }
    
    public void barberServe() throws InterruptedException {
        while (true) {
            PriorityCustomer next;
            
            lock.lock();
            try {
                while (queue.isEmpty()) {
                    barberSleeping = true;
                    customerArrived.await();
                }
                barberSleeping = false;
                next = queue.poll();  // Highest priority first
            } finally {
                lock.unlock();
            }
            
            System.out.printf("Serving customer %d (priority %d)%n", 
                             next.getId(), next.getPriority());
            cutHair();
        }
    }
}
 
class PriorityCustomer {
    private final int id;
    private final int priority;
    private final long arrivalTime;
    
    // Constructor and getters...
}

Starvation Risk with Priorities

Priority systems risk starving low-priority customers under high load:

Time	Arrivals	Queue State	Served
T0	P1 (priority=1)	[P1]
T1	V1 (priority=5)	[V1, P1]
T2		[P1]	V1
T3	V2 (priority=5)	[V2, P1]
T4		[P1]	V2
T5	V3 (priority=5)	[V3, P1]
...	VIPs keep coming	[Vn, P1]	P1 starves!

Anti-Starvation Mechanisms

Aging: Gradually increase priority of waiting customers. Eventually, a waiting regular customer's boosted priority exceeds VIPs.
Quota per Priority: "Serve at most 3 VIPs before one regular customer"
Maximum Wait Time: If a customer waits beyond threshold, promote to highest priority.
Weighted Fair Queuing: Each priority level gets proportional share of service (e.g., VIPs get 70%, regular 30%).

Priority Inversion

Real-World Applications

The sleeping barber pattern is ubiquitous in systems software. Every bounded-capacity server with idle waiting exhibits this pattern.

Sleeping Barber in Production Systems

•Thread Pools (ExecutorService): Worker threads sleep when no tasks queued. Tasks wake workers. Queue has bounded capacity; excess tasks are rejected or block producers.
•Connection Pools (HikariCP, c3p0): Connections idle when unused. Requests wake and acquire connections. Pool size is bounded; excess requests wait or are rejected.
•Web Server Workers (nginx, Apache): Worker processes/threads sleep when no requests. New requests wake workers. Accept queue is bounded; excess connections are dropped.
•Database Query Executors: Query threads sleep awaiting queries. New queries wake threads. Admission control limits concurrent queries.
•Message Queue Consumers (Kafka, RabbitMQ): Consumers poll/block waiting for messages. New messages wake consumers. Consumer groups share work.
•Print Spoolers: Print daemon sleeps when queue empty. Print jobs wake daemon. Queue has maximum size.
•Call Centers: Agents idle between calls. Incoming calls wake agents. Hold queue has limited capacity; excess callers get busy signal.

Case Study: Java ThreadPoolExecutor

thread-pool-as-barber.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.concurrent.*;
 
public class ThreadPoolAsBarberShop {
    public static void main(String[] args) {
        // Create a "barbershop" with:
        // - 3 barbers (core pool size)
        // - Max 5 barbers if overwhelmed (max pool size)
        // - 10-seat waiting room (queue capacity)
        
        BlockingQueue<Runnable> waitingRoom = 
            new ArrayBlockingQueue<>(10);  // Bounded capacity!
        
        ThreadPoolExecutor shop = new ThreadPoolExecutor(
            3,                  // Core barbers
            5,                  // Max barbers
            60, TimeUnit.SECONDS,  // Idle barber goes home after 60s
            waitingRoom,
            new ThreadPoolExecutor.AbortPolicy()  // Reject when full
        );
        
        // Customers (tasks) arrive
        for (int i = 0; i < 20; i++) {
            final int customerId = i;
            try {
                shop.execute(() -> {
                    System.out.println("Cutting hair: " + customerId);
                    try { Thread.sleep(200); } catch (InterruptedException e) {}
                });
                System.out.println("Customer " + customerId + " admitted");
            } catch (RejectedExecutionException e) {
                System.out.println("Customer " + customerId + " rejected - shop full!");
            }
        }
        
        shop.shutdown();
    }
}

The Pattern Everywhere

Common Pitfalls and Debugging

Implementation of sleeping barber systems often encounters these issues:

Common Implementation Pitfalls

•Lost Wakeups: Check-then-sleep without atomicity. Fix: Use semaphores or condition variables correctly; never check and sleep in separate operations.
•Spurious Wakeups: Thread wakes without corresponding signal. Fix: Always wait in a while loop that rechecks the condition.
•Thundering Herd: Many blocked threads wake simultaneously when one slot frees. Fix: Use signal() not signalAll() when only one can proceed; or use sem_post() which wakes just one.
•Queue Sizing Mistakes: Queue too small causes excessive rejections; too large wastes memory and increases latency. Fix: Profile under realistic load; consider adaptive sizing.
•Missing Rejection Handling: Callers don't handle RejectedExecutionException. Fix: Always check return values or catch exceptions; implement retry logic or backpressure.
•Poison Pills: Need a way to shut down sleeping workers. Fix: Use a sentinel value in queue, or interrupt mechanism to wake sleeping threads during shutdown.

Debugging Techniques

Thread Dumps: When workers appear stuck, a thread dump (jstack in Java, gdb in C) shows what each thread is waiting on.

Queue Metrics: Monitor queue size over time. Constantly near capacity indicates under-provisioned workers or slow processing.

Latency Histograms: Track time from queue entry to service start. Bimodal distribution suggests priority inversion or lock contention.

Rejection Logging: Log every rejection with timestamp and queue state. Cluster analysis reveals traffic patterns causing rejections.

shutdown-pattern.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Poison pill pattern for graceful shutdown
public class ShutdownableBarberShop {
    private final BlockingQueue<Task> queue;
    private static final Task POISON_PILL = new Task(null);
    
    public void shutdown() {
        queue.offer(POISON_PILL);
    }
    
    void barberLoop() throws InterruptedException {
        while (true) {
            Task task = queue.take();
            if (task == POISON_PILL) {
                queue.offer(POISON_PILL);  // Pass poison to next barber
                break;
            }
            process(task);
        }
    }
}

Summary: Sleeping Barber Mastery

The sleeping barber problem captures the essence of bounded-capacity services with sleeping workers. Let's consolidate the key insights:

Key Takeaways

•The Pattern: Servers sleep when idle, wake on customer arrival, serve from bounded queue, reject when full.
•The Race Condition: Lost wakeups occur when check-and-sleep isn't atomic. Semaphores and condition variables provide correct primitives.
•Semaphore Solution: Three semaphores (customers, barber, mutex) coordinate wakeup, handoff, and counter protection.
•Monitor Solution: Lock + condition variable with explicit queue for FIFO guarantees and easier reasoning.
•Multiple Barbers: Single shared queue (simple, balanced), per-barber queues (predictable), or work-stealing (balanced + locality).
•Priority Handling: Priority queues risk starvation; mitigate with aging, quotas, or weighted fair queuing.
•Ubiquitous Pattern: Thread pools, connection pools, web servers, message consumers—all implement sleeping barber variants.
•Debugging Focus: Lost wakeups, thundering herd, queue sizing, and graceful shutdown are common failure modes.

What's Next:

Page Complete

4 / 5