Sleeping Barber Problem

Sleeping Barber Problem

The sleeping barber problem is a classic concurrency problem introduced by Edsger Dijkstra in 1965. It illustrates the challenges of coordinating multiple processes sharing limited resources.

The Scenario

A barbershop has:

• 1 barber with 1 barber chair
• A waiting room with N chairs
• Customers arriving at random intervals

The rules:

• If no customers are present, the barber sleeps in their chair
• When a customer arrives and the barber is asleep, they wake the barber up
• If the barber is busy and chairs are available, the customer sits and waits
• If all waiting chairs are full, the customer leaves

The Concurrency Challenges

This maps directly to real OS/threading problems:

• Race conditions — Without proper synchronization, a customer might check "is the barber free?" and get preempted before sitting down. The barber, seeing no one, goes to sleep. The customer then sits — and both wait forever (a deadlock).
• Starvation — If customers keep arriving continuously, some may never get served.
• Lost wakeups — A customer might signal the barber to wake up, but the signal is missed because the barber hasn't gone to sleep yet.

The Solution (using semaphores)

Three semaphores are typically used:
customers = 0 // counts waiting customers (signals barber to wake)
barber = 0 // signals a customer that barber is ready
mutex = 1 // protects the shared waiting count

• Barber's loop:

while true:
    wait(customers)    // sleep until a customer arrives
    wait(mutex)        // lock the waiting room count
    waiting -= 1       // one fewer customer waiting
    signal(barber)     // tell customer: I'm ready
    release(mutex)
    cut_hair()

Each customer:

wait(mutex)            // lock waiting room count
if waiting < N:
    waiting += 1
    signal(customers)  // wake the barber (or queue yourself)
    release(mutex)
    wait(barber)       // wait until barber is ready for me
    get_haircut()
else:
    release(mutex)     // no seats — leave

Why It Matters

The sleeping barber is a direct analogy for many real systems:
Barbershop
Real system
Barber
Worker thread / server
Waiting chairs
Thread pool / request queue
Customer
Incoming task / connection
Customer leaving
Request rejection (HTTP 503)
Barber sleeping
Thread blocking on a condition variable

It's essentially the foundation of thread pool design — every web server (nginx, Node.js worker threads, Java ExecutorService) solves a variant of this problem. The waiting room size becomes your queue capacity, and the number of barbers maps to your worker count.

Orderly Shutdown

Orderly shutdown is one of the trickier real-world concurrency problems because most textbook examples use a fixed loop count — but production systems run indefinitely until told to stop. Academic examples ignore this problem by establishing a fixed number if iterations a concurrent solution will execute, but real-world production solutions need a means to provide orderly shutdown based on an external influence or message.

The Core Problem

You need every thread to:

1. Finish what it's currently doing (don't corrupt state mid-operation)
2. Stop accepting new work
3. Drain any buffered/queued work (sometimes)
4. Release resources cleanly (locks, file handles, sockets)
5. Signal completion so the main thread knows it's safe to exit These goals can conflict. Draining the queue vs. stopping promptly is a genuine design tension.

Common Mechanisms

1. Poison Pill Insert a sentinel value into the work queue that means "stop when you see this." python

POISON = None

def worker(queue):
    while True:
        item = queue.get()
        if item is POISON:
            queue.put(POISON)  # re-post so other workers also see it
            break
        process(item)

Pros: Simple, respects queue ordering (drains work before stopping)
Cons: Queue must be FIFO; hard to use with priority queues; re-posting is fragile with multiple workers

1. Shared Stop Flag (with careful memory visibility) python

import threading

stop_event = threading.Event()

def worker(queue):
    while not stop_event.is_set():
        try:
            item = queue.get(timeout=0.1)  # must time out — not block forever
            process(item)
        except Empty:
            continue  # re-check the stop flag

# Shutdown:
stop_event.set()

The critical subtlety here is the timeout on the blocking call. A thread blocked indefinitely on queue.get() will never check the flag — so you must wake it up periodically. This introduces a latency vs. CPU burn tradeoff in the timeout value.

1. Interrupt / Cancellation Token (Go-style context) Go's context package makes this idiomatic: go

func worker(ctx context.Context, jobs <-chan Job) {
    for {
        select {
        case <-ctx.Done():
            return  // shutdown signal received
        case job, ok := <-jobs:
            if !ok {
                return  // channel closed
            }
            process(job)
        }
    }
}

// Shutdown:
cancel()  // derived from context.WithCancel

The select races both channels simultaneously — no polling, no timeout gymnastics. This is arguably the cleanest model because cancellation is a first-class value passed through the call graph, not a global side channel.

1. Two-Phase Shutdown Used when you need to distinguish "stop accepting new work" from "finish existing work": Phase 1 — Soft stop:
   • Close the intake gate (reject new submissions)
   • Let workers drain the queue naturally
   • Set a deadline

Phase 2 — Hard stop (if deadline exceeded):

• Interrupt blocked workers
• Abandon remaining queue items
• Force exit This is exactly what Java's ExecutorService provides: java

executor.shutdown();                          // phase 1: no new tasks
boolean clean = executor.awaitTermination(    // wait for drain
    30, TimeUnit.SECONDS
);
if (!clean) executor.shutdownNow();           // phase 2: interrupt workers

The Deeper Design Issues

Who owns the shutdown signal? If any thread can trigger shutdown, you need coordination so they don't race each other. Typically one designated thread (main, signal handler) owns it.
What about blocked I/O? A thread blocked on a socket read or a wait() won't notice a flag. You need to either close the underlying resource (causing an exception) or use interruptible blocking calls.
The TOCTOU trap on shutdown:
Thread A checks: is_shutting_down? → false
Main sets: is_shutting_down = true
Thread A submits new work ← work submitted after shutdown began
The intake gate must be closed atomically with the flag — usually requiring a mutex around both the check and the submission.
Signaling completion back up: join() / await on a barrier or latch is the standard pattern. The main thread must not exit until all workers confirm they're done, or destructors will fire under live threads.
main:

signal shutdown
    latch.await()    ← blocks here
    cleanup()
    exit

each worker:

 ... finish work ...
    latch.countDown()

The General Principle
The root difficulty is that blocking and polling are duals of each other — blocking is efficient but uninterruptible, polling is interruptible but wastes CPU. Every shutdown mechanism is essentially a negotiation between these two. The cleanest designs (Go's context, Java's Future.cancel) make cancellation a first-class concern from the start rather than retrofitting a flag onto blocking code.

A classical C implementation of the Sleeping Barber problem

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define NUM_CUSTOMERS 20
#define NUM_SEATS 5

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t barber_ready = PTHREAD_COND_INITIALIZER;
pthread_cond_t customer_ready = PTHREAD_COND_INITIALIZER;

int waiting = 0;          // number of customers waiting
int barber_sleeping = 1;  // barber initially asleep

void *barber(void *arg) {
    while (1) {
        pthread_mutex_lock(&mutex);

        // Sleep if no customers
        while (waiting == 0) {
            barber_sleeping = 1;
            printf("Barber: No customers, going to sleep.\n");
            pthread_cond_wait(&customer_ready, &mutex);
        }

        // A customer is ready
        waiting--;
        printf("Barber: Taking a customer. Waiting room count = %d\n", waiting);

        // Wake the customer
        pthread_cond_signal(&barber_ready);
        barber_sleeping = 0;

        pthread_mutex_unlock(&mutex);

        // Cut hair (simulate time)
        printf("Barber: Cutting hair...\n");
        usleep((rand() % 3000 + 500) * 1000);
    }
    return NULL;
}

void *customer(void *arg) {
    int id = *(int *)arg;

    pthread_mutex_lock(&mutex);

    if (waiting < NUM_SEATS) {
        waiting++;
        printf("Customer %d: Sitting in waiting room. Waiting = %d\n", id, waiting);

        // Wake the barber if needed
        if (barber_sleeping) {
            printf("Customer %d: Waking the barber.\n", id);
            pthread_cond_signal(&customer_ready);
        }

        // Wait until the barber is ready
        pthread_cond_wait(&barber_ready, &mutex);

        pthread_mutex_unlock(&mutex);

        // Get haircut
        printf("Customer %d: Getting a haircut.\n", id);
        usleep((rand() % 2000 + 500) * 1000);

    } else {
        // No seats available
        printf("Customer %d: No seats available, leaving.\n", id);
        pthread_mutex_unlock(&mutex);
    }

    return NULL;
}

int main() {
    srand(time(NULL));

    pthread_t barber_thread;
    pthread_t customer_threads[NUM_CUSTOMERS];

    pthread_create(&barber_thread, NULL, barber, NULL);

    int ids[NUM_CUSTOMERS];
    for (int i = 0; i < NUM_CUSTOMERS; i++) {
        ids[i] = i + 1;
        usleep((rand() % 2000 + 500) * 1000);  // random arrival
        pthread_create(&customer_threads[i], NULL, customer, &ids[i]);
    }

    for (int i = 0; i < NUM_CUSTOMERS; i++) {
        pthread_join(customer_threads[i], NULL);
    }

    // In classical C examples, the barber runs forever.
    // A real system would need a shutdown mechanism.

    pthread_cancel(barber_thread);
    pthread_join(barber_thread, NULL);

    return 0;
}

Fragility Analysis of the C Example

The classical C implementation of the Sleeping Barber problem works — but only because the programmer manually enforces every concurrency invariant the language itself does not understand. The code is correct only as long as the programmer maintains a delicate choreography of mutexes, condition variables, and shared‑state checks. Several categories of fragility are inherent to this approach.

Lost Wakeups

Condition variables do not store signals. If a customer signals the barber before the barber executes pthread_cond_wait, the signal is lost forever.
This is why the barber must use:

while (waiting == 0)
    pthread_cond_wait(&customer_ready, &mutex);

• The loop is not stylistic — it is a defensive pattern required to avoid a race the language cannot prevent.
• A single misplaced if instead of while reintroduces the lost‑wakeup bug.

Spurious Wake-ups

POSIX explicitly allows condition variables to wake up for no reason. This forces every wait to be wrapped in a loop that rechecks the predicate.
The programmer must remember:

• never trust a wake-up
• always recheck the condition
• always hold the mutex while checking

Manual Queue Invariants

The waiting room count (waiting) is a shared variable with a non‑trivial invariant:
0 ≤ waiting ≤ NUM_SEATS
In C, the programmer must:

• protect it with the correct mutex
• increment and decrement it in the right places
• ensure no path forgets to unlock the mutex
• ensure no early return violates the invariant A single missing unlock or misordered update can corrupt the state. Mutex Discipline Is Entirely Manual Every shared variable must be accessed only while holding the correct mutex. Nothing in C enforces this. If a future maintainer adds: if (waiting == 0) { ... }

outside the mutex, the program becomes subtly incorrect. The compiler cannot help. The runtime cannot help. The language cannot help.

Shutdown Is Not Structurally Supported

The classical C example typically runs forever because orderly shutdown is difficult:

• A worker may be blocked on pthread_cond_wait
• A customer may be blocked on pthread_cond_wait
• A shutdown flag must be checked, but blocked threads cannot check it
• pthread_cond_broadcast must be used carefully
• Threads may wake up and race to submit new work after shutdown begins

The programmer must manually coordinate:

• flag setting
• mutex locking
• condition broadcasts
• thread joins

Correctness Depends on Programmer Memory, Not Language Semantics
The C solution is correct only because the programmer:

• remembered to lock before checking
• remembered to re-check after waking
• remembered to signal in the right order
• remembered to guard every shared variable
• remembered to maintain the queue invariant
• remembered to avoid TOCTOU races

This is not a concurrency model. It is a set of conventions.

Why Ada Solves These Problems at the Language Level

The classical C solution demonstrates the essential difficulty: the language has no concurrency semantics. Threads, mutexes, and condition variables are merely library calls layered on top of a language that was never designed for concurrent execution.
Ada takes the opposite approach.
Concurrency is not a library. It is part of the language’s semantic identity.
Where C requires the programmer to manually maintain invariants, Ada provides:

• protected objects with implicit locking
• entries with built‑in FIFO queuing
• barrier conditions that eliminate lost wakeups
• select statements that express conditional synchronization directly
• rendezvous for structured synchronous communication
• task termination semantics that make shutdown orderly and predictable In C, the programmer must build a concurrency model. In Ada, the concurrency model is already there — and the programmer simply uses it. This is why the Sleeping Barber problem is such a powerful teaching example: it exposes the difference between a language that permits concurrency and a language that understands it.

Why This Matters

Now that we’ve seen the classical C solution and the fragility inherent in manual synchronization, we can examine how Ada expresses the same problem using language‑level concurrency constructs. Notice how the invariants that must be manually maintained in C become structural guarantees in Ada.

---

A Sleeping Barber Solution Written in Ada

Concurrency is implemented in Ada as a core language feature. Ada tasks are active units of concurrency often implemented as OS threads. Ada tasks have been part of the Ada language since its first standardized version in 1983.

Rendezvous

Ada tasks allow direct synchronous communication between tasks using a Rendezvous mechanism. A task may declare an entry. An entry may pass data to or from the task calling the entry or the entry may be designed as an event notification with no data being passed. The task declaring an entry calls an accept statement allowing the task to respond to the task entry. The task calling the accept suspends until the called task accepts the entry. If the called task reaches its accept statement before its entry is called the calling task suspends until another task calls the entry. As soon as the entry is completed both tasks resume their concurrent behaviors.

Select

Ada provides a select statement to conditionally accept an entry call. The select statement allows the called task to respond to any one of many entries it declares, or to wait a specified time for a task to call its entry, or to simply perform other behaviors if no task is suspended on its entry call. Entries are implicitly queued with a default First-In-First-Out (FIFO) queuing policy so that multiple calls to a task entry are processed in the order the entry is called.

Task Entry Issue

The Ada Rendezvous pattern is powerful and very general in its usage but it cannot implement asynchronous data sharing. Asynchronous data sharing can be modeled using an intermediate task as a queuing mechanism. This model is heavy weight. In the 1995 version of the Ada standard a new feature called protected objects was added to deal with this issue.

Protected Objects

An Ada protected object is a passive concurrency element. It is always called by and executed within a task. The “protected” part of a protected object comes from the fact the object implements a shared memory object that controls all necessary locking implicitly. A protected object contains only private data which is accessible through methods specified within the protected object definition. There are three kinds of protected methods.

Protected Procedures

A protected procedure has unconditional exclusive read-write access to the protected object. Calling a protected procedure implicitly locks the protected object at the beginning of the procedure and unlocks the protected object at the completion of the procedure.

Protected Entries

Protected entries provides conditional exclusive read-write access to a protected object. A call to a protected entry only begins when the protected entry's boundary condition evaluates to TRUE. Tasks calling the protected entry while the boundary condition evaluates to FALSE are suspended in an implicit entry queue and are executed when the boundary condition becomes TRUE.

Protected Functions

Protected functions provide read-only access to the data in the protected object. Protected functions implement a shared read-only lock on the protected object allowing multiple overlapping function calls to be executed by calls from multiple tasks. The read-only lock is released when no tasks are calling a protected function.

---

Ada Code Example

The primary unit of modularity in Ada is the package. An Ada package has two parts. The package specification defines the package interface while the package body contains the implementation of all the behaviors declared in the package specification.

package Barber_Shop is
   task Barber is
      entry Close_Shop;
   end Barber;
end Barber_Shop;

This package specification only specifies a single task named Barber. The Barber task declares one entry named Close_Shop.

with Ada.Text_IO;               use Ada.Text_IO;
with Ada.Numerics.Float_Random; use Ada.Numerics.Float_Random;

package body Barber_Shop is
   Seed : Generator;

   type Num_Seats is range 0 .. 5;
   protected Shop is
      function Is_Open return Boolean;
      function Shop_Empty return Boolean;
      entry Take_Seat;
      entry Serve_Customer;
      procedure Close_Shop;
   private
      Shop_Open      : Boolean   := True;
      Occupied_Seats : Num_Seats := 0;
   end Shop;

   protected body Shop is
      function Is_Open return Boolean is
      begin
         return Shop_Open;
      end Is_Open;

      function Shop_Empty return Boolean is
      begin
         return Occupied_Seats = 0;
      end Shop_Empty;

      entry Take_Seat when Shop_Open and then Occupied_Seats < Num_Seats'Last
      is
      begin
         Occupied_Seats := Occupied_Seats + 1;
      end Take_Seat;

      entry Serve_Customer when Occupied_Seats > 0 is
      begin
         Occupied_Seats := Occupied_Seats - 1;
      end Serve_Customer;

      procedure Close_Shop is
      begin
         Shop_Open := False;
      end Close_Shop;

   end Shop;

   ------------
   -- Barber --
   ------------

   task body Barber is
      procedure Cut_Hair is
      begin
         Put_Line ("Luigi is serving a customer.");
         delay Duration (Random (Seed) * 3.0);
      end Cut_Hair;

   begin
      loop
         select
            accept Close_Shop;
            Put_Line ("Luigi is closing the shop");
            Shop.Close_Shop;
         else
            if Shop.Is_Open then
               if Shop.Shop_Empty then
                  Put_Line ("Luigi is sleeping.");
               end if;
               Shop.Serve_Customer;
               Cut_Hair;
            else
               while not Shop.Shop_Empty loop
                  Shop.Serve_Customer;
                  Cut_Hair;
               end loop;
               exit;
            end if;
         end select;
      end loop;
   end Barber;

   ---------------
   -- Customers --
   ---------------

   task Customers;

   task body Customers is
   begin
      loop
         delay Duration (Random (Seed) * 2.5);
         select
            Shop.Take_Seat;
            Put_Line ("A customer took a seat");
         else
            if Shop.Is_Open then
               Put_Line ("A customer left because all the seats were taken.");
            else
               Put_Line ("A customer left because the shop is closed.");
               exit;
            end if;
         end select;
      end loop;
   end Customers;
begin
   Reset (Seed);
end Barber_Shop;

This package body does most of the work for the Sleeping Barber example. Above the top of the package you find a context clause. The context clause declares a dependency on two language-defined packages. The first context clause declares a dependency on the package Ada.Text_IO, which is the text input/output package for Ada. The second context clause defines a dependency on Ada.Numerics.Float_Random, which provides a random number generator producing a floating point value between 0.0 and 1.0.
Within the package body there is a declarative part and an executable part.
The declarative part first declares a variable named Seed which is an instance of type Generator. The Generator type is declared within the Ada.Numerics.Random_Float package and is the random number seed.

The type Num_Seats is declared to have valid values in the range of 0 through 5. It is a custom integer type.

Protected Specification

The specification for the protected object named Shop declares two functions, two entries and one procedure. The functions named Is_Open and Shop_Empty each return a Boolean value. The entries Tack_Seat and Serve_Customer are declared. The procedure Close_Shop is declared.
The private section of the protected object specification contains two data members. Shop_Open is a Boolean type initialized to True. Occupied_Seats is an instance of Num_Seats initialize to 0. The private data members are only accessible via the functions, entries and procedure.

Protected Body

The protected body implements the behaviors of the protected methods.

Function Is_Open simply returns the value of the Shop_Open data member.
Function Shop_Empty returns the result of the expression Occupied_Seats = 0. In Ada the '=' operator is the equality comparison operator.
Entry Take_Seat only executes when Shop_Open returns True and Occupied_Seats is less than the maximum value for the Num_Seats type. When those conditions are both true the entry increments the Occupied_Seats value.
Entry Serve_Customer only executes when Occupied_Seats is greater than 0. When that condition is true Occupied_Seats is decremented.
Procedure Close_Shop sets Shop_Open to False.
All locking and queuing behaviors are implicitly handled by the protected object.

Barber task body

The barber task body implements the behavior of the Barber task.
The task body contains a declarative part and an executable part. Within the declarative part the procedure Cut_Hair is declared. Cut_Hair outputs a message stating Luigi is serving a customer and then delays the task for a random number of seconds between 0.0 seconds and 3.0 seconds.
The executable part of the task contains a basic loop that continues until the shop is closed and all awaiting customers have been served. Each iteration of that loop the task entry Close_Shop is selectively accepted. If no task is suspended on that entry the loop executes the logic following the else statement. If a task is suspended on the Close_Shop entry then the program outputs “Luigi is closing the shop” and then calls the shop.close protected procedure.
If the shop is open then the task evaluates whether the shop is empty. If it is the task outputs “Luigi is sleeping” and then calls Shop.Serve_Customer. The task will suspend on that call until the protected object has a customer waiting in a seat. Barber then calls Cut_Hair.

If the shop is closed the Barber iterates through the customers waiting to be served and serves them all then exits the outer loop. At that point the Barber task terminates.

Customer Task

The customer task generates customers. The customer task has no task entry. The Customer task contains a simple loop that begins by delaying between 0.0 and 2.5 seconds. The Shop.Take_Seat protected entry is called within a select statement. If the select statement completes (the task is not queued) then the Customer task outputs “A customer took a seat”. If the Shop.Take_Seat boundary condition returns False then the Customer tasks calls Shop.Is_Open if that is true all the seats must be filled and Customer outputs “A customer left because all the seats were taken”. If Shop.Is_Open returns False then the Customer task outputs “A customer left because the shop is closed” and then exits the loop, which completes the Customer task.

Package executable part

The package executable part simply initializes the random seed based on a value returned by the system clock when the package is elaborated, before any other program execution happens.

with Barber_Shop; use Barber_Shop;
procedure Main is
begin
   delay 60.0;
   Barber.Close_Shop;
end Main;

Main

The main program declares a dependency on the Barber_Shop package, delays for 60.0 seconds and calls Barber.Close. The tasks in the Barber_Shop package implicitly begin executing when Main reaches its executable part. Main is the program entry point and is therefore also the environment task. As a task it is able to call Barber.Close_Shop. Main does not complete until all the tasks started withing main, namely Barber and Customer complete. There is no explicit join() call. Ada task coordination is based on calling scope.

Language Comparison

Concept	C (pthread)	Ada
Locking	Manual mutex discipline	Implicit in protected objects
Wakeups	Lost/spurious wakeups	Entry barriers eliminate them
Queuing	Must be implemented manually	FIFO queues built‑in
Shutdown	Flags + broadcasts	Structured via entries
Invariants	Programmer‑maintained	Compiler‑enforced

The Sleeping Barber problem is more than a concurrency puzzle — it is a lens through which we can see the philosophical difference between languages that permit concurrency and languages that understand it. C gives the programmer power and responsibility; Ada gives the programmer structure and guarantees. Both can solve the problem, but only one does so with concurrency as a first‑class semantic concept.