Sleeping Barber Problem

Introduction

The Sleeping Barber Problem is a classic synchronization problem that models coordination between a service worker and arriving customers. It is often used to explain semaphores, mutexes, blocking, and bounded waiting.

The setup has one barber, one barber chair, and a waiting room with limited chairs. If no customers are present, the barber sleeps; if customers arrive, they either wake the barber, wait, or leave.

Problem Setup

The barber shop has a few simple parts:

• One barber: The worker who gives haircuts.

• One barber chair: Only one customer can be served at a time.

• Waiting room: A limited number of chairs for customers waiting their turn.

• Customers: They arrive over time and either get service, wait, or leave.

The important constraint is capacity. The waiting room cannot hold unlimited customers, so the synchronization logic must handle both waiting and rejection.

Problem Rules

The rules are straightforward:

• No customers: The barber sleeps.

• Customer arrives while barber sleeps: The customer wakes the barber.

• Barber busy and chair available: The customer waits in the waiting room.

• Barber busy and no chair available: The customer leaves.

• Barber chair: Only one customer receives service at a time.

This makes the problem more than simple mutual exclusion. It also needs capacity control and proper wakeup behavior.

Why Coordination Matters

The shared state is the number of waiting customers. Both the barber and customers use this value, so it must be updated safely.

Correct synchronization prevents:

• Lost wakeups: A customer arrives, but the barber is not woken correctly.

• Overflow: More customers enter the waiting room than available chairs.

• Race conditions: Multiple customers update the waiting count incorrectly.

• Wrong blocking: A customer or barber waits even though progress should be possible.

The problem combines counting, signaling, and mutual exclusion.

Semaphore Setup

A common semaphore solution uses one shared count and three synchronization tools.

• chairs : Total waiting-room capacity

• waiting : Number of customers currently waiting

• mutex : Protects updates to waiting

• customers : Counts waiting customers and wakes the barber

• barbers : Signals that the barber is ready for one customer

chairs is fixed, so it does not need protection. waiting changes, so it must be protected by mutex.

Barber Flow

The barber repeatedly waits for a customer, takes one waiting customer, signals readiness, and cuts hair.

The meaning is:

• wait(customers): Sleep if no customer is waiting.

• wait(mutex): Safely access the waiting count.

• Decrease waiting: One customer leaves the waiting room for service.

• signal(barbers): Tell one customer the barber is ready.

• signal(mutex): Release the waiting-count protection.

• cut_hair(): Serve the customer.

Customer Flow

A customer first checks whether there is space in the waiting room. That check must be protected because many customers may arrive close together.

If a chair is available, the customer increments waiting, signals that a customer exists, releases the mutex, and waits for the barber. If no chair is available, the customer releases the mutex and leaves.

How the Coordination Works

Suppose the waiting room has three chairs and no customers are present. The barber calls wait(customers) and sleeps.

When the first customer arrives, the customer safely increments waiting, signals customers, and then waits on barbers. The barber wakes, decreases waiting, signals barbers, and starts the haircut.

If more customers arrive while the barber is busy, they can wait only while chairs are available. Once all waiting chairs are full, later customers leave instead of entering an already full waiting room.

Practical Connection

The Sleeping Barber Problem resembles many bounded-service systems. A worker sleeps when there is no work, wakes when work arrives, and rejects new work when the queue is full.

This is similar to thread pools, backend request queues, logging systems, and worker-based services. The story is about haircuts, but the synchronization pattern is really bounded capacity plus worker wakeup.

Summary

The Sleeping Barber Problem models one barber, one barber chair, and a limited waiting room. Customers wake the barber when work exists, wait if chairs are available, and leave if the waiting room is full.

The common semaphore solution uses waiting as shared state, mutex to protect it, customers to wake the barber, and barbers to signal that the barber is ready. The main idea is bounded waiting with safe sleep-and-wakeup coordination.