THE SLEEPING BARBER PROBLEM
1.Introduction
The Sleeping Barber Problem is a classic synchronization problem first proposed by Edsger Dijkstra. It
models a barbershop where synchronization is needed between the barber and customers. This
scenario illustrates the coordination challenges between processes in a concurrent system.
2.Problem Definition
A barbershop consists of:
One barber
One barber chair
A waiting room with n chairs
Rules:
If there are no customers, the barber sleeps.
If a customer arrives and the barber is sleeping, they wake him up.
If the barber is busy and a chair is available, the customer waits.
If all chairs are full, the customer leaves.
Goal: Proper synchronization ensuring no race conditions, deadlocks, or starvation.
3.Use Cases in OS
Thread Scheduling
Producer-Consumer Problem
Resource Allocation (e.g., printer, CPU)
Process Synchronization
Bounded Buffer Problem
4.Synchronization Mechanisms
Semaphores: Counting and Binary
Mutex Locks
Condition Variables
Monitors
Message Passing
Channels
Petri Nets (modeling)
RTOS Synchronization Tools
5.Possible Solutions
1. Using Semaphores (Classic OS Approach)
semaphore customers = 0;
semaphore barber = 0;
semaphore mutex = 1;
int waiting = 0;
barber()
{ while(true) {
wait(customers);
wait(mutex);
waiting--;
signal(barber);
signal(mutex);
cutHair();
}
}
customer() {
wait(mutex);
if (waiting < CHAIRS) {
waiting++;
signal(customers);
signal(mutex);
wait(barber);
getHaircut();
} else {
signal(mutex);
leaveShop();
}
}
2. Using Monitors (High-Level Java/Python Style)
class BarberShop
{ int waiting =
0;
final int CHAIRS = 5;
Condition customers, barber;
synchronized void customerArrives() {
if (waiting < CHAIRS) {
waiting++;
customers.signal();
barber.await();
getHaircut();
} else {
leaveShop();
}
}
synchronized void barberReady()
{ while (true) {
if (waiting == 0)
customers.await();
waiting--;
barber.signal();
cutHair();
}
}
}
3. Using Condition Variables (POSIX Pthreads)
pthread_mutex_t mutex;
pthread_cond_t cond_customer, cond_barber;
int waiting = 0;
void* barber(void*)
{ while (1) {
pthread_mutex_lock(&mutex);
while (waiting == 0)
pthread_cond_wait(&cond_customer, &mutex);
waiting--;
pthread_cond_signal(&cond_barber);
pthread_mutex_unlock(&mutex);
cutHair();
}
}
void* customer(void*) {
pthread_mutex_lock(&mutex);
if (waiting < CHAIRS) {
waiting++;
pthread_cond_signal(&cond_customer);
pthread_cond_wait(&cond_barber, &mutex);
pthread_mutex_unlock(&mutex);
getHaircut();
} else {
pthread_mutex_unlock(&mutex);
leave();
}
}
5. Using Python Locks & Condition Variables
from threading import Thread, Lock, Condition
mutex = Lock()
cond_customers = Condition(mutex)
cond_barber = Condition(mutex)
waiting = 0
CHAIRS = 3
def customer():
global waiting
with mutex:
if waiting < CHAIRS:
waiting += 1
cond_customers.notify()
cond_barber.wait()
else:
print("Customer leaves")
def barber():
global waiting
while True:
with mutex:
if waiting == 0:
cond_customers.wait()
waiting -= 1
cond_barber.notify()
cutHair()
6.Properties Achieved
Mutual Exclusion: One haircut at a time
No Deadlock: Proper wait/signal discipline
No Starvation: FIFO fairness possible
Concurrency: Waiting area handles multiple customers
7.Variants
Multiple barbers
VIP customers (priority queues)
Time-bound waiting customers
Appointment-based vs. walk-ins
8.Real-Time Examples
Call centers
Doctor clinics
Customer service queues
ATM machine queues
Ticket counter operations
9.Conceptual Links to OS
CPU = Barber, Processes = Customers
Semaphores/Mutex = Synchronization tools
Scheduling = Queue handling
Deadlock/Starvation prevention = Goal of proper sync
10. Conclusion
The Barber Problem serves as a foundational synchronization scenario in OS design. It introduces
semaphores, condition variables, and monitors in an intuitive setting, helping learners understand
mutual exclusion, deadlocks, and starvation. Its versatility makes it a great learning model for
concurrent programming.
