1. Introduction

The Sleeping Barber Problem is a classic synchronization problem in Operating Systems that models a service system with limited waiting capacity. It was proposed to demonstrate how processes can coordinate efficiently while sharing limited resources.

The problem combines several important synchronization concepts:

• Mutual Exclusion

• Process Synchronization

• Resource Allocation

• Queue Management

• Blocking and Wake-Up Mechanisms

Unlike the Producer–Consumer Problem, which focuses on data exchange through a buffer, the Sleeping Barber Problem models a service-oriented system where customers compete for service from a single provider.

The objective is to ensure efficient coordination between customers and the barber while avoiding race conditions, lost wake-ups, deadlocks, and resource wastage.

Formally:

The Sleeping Barber Problem models a service system in which customers arrive randomly and must coordinate with a service provider while sharing limited waiting resources.

This problem closely resembles many real-world systems such as:

• Customer service centers

• Printer queues

• Web server request handling

• Ticket booking systems

• Call centers

2. Problem Description

Consider a barber shop containing:

1 Barber

1 Barber Chair

N Waiting Chairs

Customers arrive at random times.

Each arriving customer must determine whether:

Get Haircut

or

Leave Shop

depending on resource availability.

The barber serves customers one at a time.

3. Rules of the System

The system operates according to the following rules.

Rule 1: No Customers

If there are no customers:

Barber Sleeps

to avoid wasting resources.

Rule 2: Customer Arrives While Barber Sleeping

If a customer arrives and the barber is sleeping:

Wake Barber

and receive service.

Rule 3: Customer Arrives While Barber Busy

If the barber is currently cutting hair:

Customer Checks
Waiting Chairs

Chair Available

Customer Waits

in a waiting chair.

No Chair Available

Customer Leaves

the shop immediately.

Rule 4: Barber Finishes Haircut

After completing service:

Next Waiting Customer

is selected.

If nobody is waiting:

Barber Sleeps Again

4. Conceptual Visualization

The barber shop can be represented as:

Customers Arrive
        ↓

+----------------+
| Waiting Chairs |
+----------------+
        ↓

+----------------+
| Barber Chair   |
+----------------+
        ↓

      Barber

Customers either:

Wait

or

Leave

depending on availability.

5. Core Problems

The Sleeping Barber Problem introduces several synchronization challenges.

5.1 Race Conditions

Multiple customers may arrive simultaneously.

Example:

Customer A

and

Customer B

attempt to occupy the same waiting chair.

Without synchronization:

Inconsistent Waiting Count

may occur.

5.2 Synchronization

Customers and barber must coordinate properly.

Example:

Customer Arrives

must correctly wake:

Sleeping Barber

5.3 Resource Management

The shop contains only:

Limited Chairs

Therefore:

Customers Compete
For Resources

6. Key Challenges

A correct solution must address several critical issues.

6.1 Avoid Lost Wake-Up

Customer should not wake barber before barber actually waits.

Otherwise:

Wake-Up Lost

and barber may sleep forever.

6.2 Proper Queue Handling

Waiting chairs must be allocated correctly.

No Duplicate Occupancy

should occur.

6.3 Prevent Deadlock

Both barber and customers must always make progress.

No Permanent Waiting

should occur.

7. Semaphore-Based Solution

The classical solution uses semaphores.

7.1 Semaphores Used

Three synchronization variables are required.

customers

Counts waiting customers.

Waiting Customer Count

barber

Represents barber availability.

Barber Ready Signal

mutex

Provides mutual exclusion.

Protect Shared Variables

7.2 Initialization

customers = 0;

barber = 0;

mutex = 1;

int waiting = 0;

int chairs = N;

Meaning

customers = 0

Initially:

No Waiting Customers

barber = 0

Initially:

Barber Sleeping

mutex = 1

Shared data available.

Critical Section Free

waiting = 0

No occupied chairs.

8. Customer Process

Step-by-Step Explanation

Enter Critical Section

wait(mutex)

protects shared variables.

Check Chair Availability

If:

waiting < chairs

a chair exists.

Occupy Chair

waiting++

updates queue count.

Notify Barber

signal(customers)

indicates a customer is waiting.

Release Mutex

signal(mutex)

allows others to access data.

Wait For Service

wait(barber)

blocks until barber is ready.

No Chair Available

Customer leaves.

Shop Full

Customer Flow

Arrive
   ↓
Check Chair
   ↓
Wait Or Leave
   ↓
Get Haircut

9. Barber Process

Step-by-Step Explanation

Wait For Customer

wait(customers)

If no customer exists:

Barber Sleeps

Customer Arrives

Customer executes:

signal(customers)

which wakes barber.

Enter Critical Section

wait(mutex)

ensures safe queue updates.

Remove Customer From Queue

waiting--

updates waiting count.

Signal Customer

signal(barber)

invites customer for service.

Release Mutex

signal(mutex)

allows others to proceed.

Perform Haircut

Cut Hair

Barber Flow

Sleep
  ↓
Customer Arrives
  ↓
Wake Up
  ↓
Select Customer
  ↓
Cut Hair
  ↓
Repeat

10. Working Mechanism

The complete interaction is:

No Customers
      ↓
Barber Sleeps

Customer arrives:

Customer Signals

Barber wakes:

Wake Up

Customer receives service:

Haircut

If barber busy:

Customer Waits

in queue.

If queue full:

Customer Leaves

11. Key Insight

The most important observation is:

The Sleeping Barber Problem is fundamentally about efficient coordination between service providers and service requesters under limited resource constraints.

The solution ensures:

No Busy Waiting

No Resource Conflict

Efficient Utilization

of the barber and waiting chairs.

12. Important Concept: Lost Wake-Up Problem

One of the most critical synchronization issues is:

Lost Wake-Up

What Is It?

Suppose:

Customer Signals

before:

Barber Waits

If the signal is lost:

Barber Sleeps Forever

even though customers exist.

Why Semaphores Prevent It

Semaphores maintain state.

Example:

signal(customers)

increments the semaphore count.

The information is not lost.

Therefore:

Future wait(customers)

succeeds correctly.

13. Advantages of the Semaphore Solution

13.1 Prevents Race Conditions

Mutex protects shared variables.

Safe Chair Allocation

13.2 Ensures Mutual Exclusion

Only one process updates waiting count at a time.

13.3 Efficient Synchronization

Barber sleeps instead of busy waiting.

CPU Not Wasted

13.4 Prevents Lost Wake-Up

Semaphore state preserves signals.

13.5 Scalable

Works for arbitrary values of:

N Waiting Chairs

14. Disadvantages

14.1 Complexity

Synchronization logic can be difficult to design correctly.

Small mistakes may cause:

• Deadlocks

• Starvation

• Lost signals

14.2 Queue Management Overhead

The system must maintain:

Waiting Count

accurately.

14.3 Limited Capacity

Customers may be rejected.

No Free Chair

results in lost service opportunities.

15. Real-World Analogy

The barber shop corresponds to many real systems.

Barber

Service Provider

Examples:

• CPU

• Printer

• Server

Customers

Service Requests

Examples:

• Processes

• Print jobs

• Network requests

Waiting Chairs

Request Queue

Examples:

• Ready Queue

• Buffer

• Job Queue

The synchronization problem remains identical.

16. Comparison with Producer–Consumer Problem

Key Difference

Producer–Consumer focuses on:

Data Movement

Sleeping Barber focuses on:

Service Coordination