Solution of Sleeping Barber Problem
The following solution uses three semaphores, one for customers(for counts of waiting for customers), one for barber(a binary semaphore denoting the state of the barber, i.e., 0 for idle and 1 for busy), and a mutual exclusion semaphore, mutex for seats.
Also read about - Semaphores v/s Mutex
Algorithm
Algo for the solution of sleeping barber problem
Semaphore Customers = 0; // semaphore for count of customers
Semaphore Barber = 0; // semaphore denoting the status of barber - 0 for idle and 1 for busy
Mutex Seats = 1; // a mutual exclusion semaphore
int FreeSeats = N;
Barber {
while(true) {
// waits for a customer (while barber is asleep).
down(Customers);
//mutex semaphore to protect the number of available seats.
down(Seats);
//a chair gets free.
FreeSeats++;
// this will bring customers for a haircut.
up(Barber);
// releasing the mutex(semaphore) on the chair.
up(Seats);
//now barber is cutting the hairs
}
}
Customer {
while(true) {
// protects seats so that only 1 customer tries to sit in a chair if that's the case.
down(Seats); //This line should not be here.
if(FreeSeats > 0) {
// sitting down
FreeSeats--;
// notifying the barber.
up(Customers);
// releasing the lock.
up(Seats);
// customer wait in the waiting room if the barber is busy.
down(Barber);
// customer is having hair cut
} else {
// releasing the lock .
up(Seats);
// now customer leaves
}
}
}
Analysis
When the barber arrives for work, the barber procedure is executed, and he sees if any customer is ready or not. If anyone is ready, pick up the customer for a haircut and block the customer's semaphore. If no one is ready for a haircut, the barber sleeps.
If there is an available chair, the waiting counter is incremented, the barber wakes up, and the customer releases the mutex. Then the barber gets the mutex, enters the critical section, and starts haircut.
After completion of the haircut, the customer leaves. Now the barber checks at the waiting room, any other customers are waiting for a haircut or not. If it is not, the barber is going to sleep.
Also Read, FCFS Scheduling Algorithm, Multiprogramming vs Multitasking
Implementation of the Sleeping Barber Problem using semaphores
Implementation:
Java
import java.util.concurrent.Semaphore;
class BarberShop {
private Semaphore barberSemaphore = new Semaphore(1);
private Semaphore customerSemaphore = new Semaphore(0);
private int waitingCustomers = 0;
public void barber() {
try {
while (true) {
System.out.println("Barber is sleeping...");
customerSemaphore.acquire();
barberSemaphore.release();
System.out.println("Barber is cutting hair.");
Thread.sleep(1000);
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
public void customer(int id) {
try {
if (waitingCustomers < 3) {
System.out.println("Customer " + id + " enters the barber shop.");
waitingCustomers++;
customerSemaphore.release();
barberSemaphore.acquire();
System.out.println("Customer " + id + " is getting a haircut.");
Thread.sleep(1000);
waitingCustomers--;
System.out.println("Customer " + id + " leaves the barber shop.");
} else {
System.out.println("Customer " + id + " leaves because the barber shop is full.");
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
public class Main {
public static void main(String[] args) {
BarberShop barberShop = new BarberShop();
Thread barberThread = new Thread(() -> barberShop.barber());
barberThread.start();
for (int i = 1; i <= 10; i++) {
final int id = i;
Thread customerThread = new Thread(() -> barberShop.customer(id));
customerThread.start();
try {
Thread.sleep(500);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}

You can also try this code with Online Java Compiler
Run Code
Output:
Barber is sleeping...
Customer 1 enters the barber shop.
Customer 1 is getting a haircut.
Barber is cutting hair.
Customer 2 enters the barber shop.
Customer 2 is getting a haircut.
Barber is sleeping...
Barber is cutting hair.
Customer 1 leaves the barber shop.
Customer 3 enters the barber shop.
Customer 3 is getting a haircut.
Customer 2 leaves the barber shop.
Customer 4 enters the barber shop.
Barber is sleeping...
Customer 4 is getting a haircut.
Barber is cutting hair.
Customer 3 leaves the barber shop.
Customer 5 enters the barber shop.
Customer 6 enters the barber shop.
Customer 4 leaves the barber shop.
Barber is sleeping...
Barber is cutting hair.
Customer 5 is getting a haircut.
Customer 7 enters the barber shop.
Customer 8 leaves because the barber shop is full.
Customer 5 leaves the barber shop.
Barber is sleeping...
Barber is cutting hair.
Customer 6 is getting a haircut.
Customer 9 enters the barber shop.
Customer 10 leaves because the barber shop is full.
Customer 6 leaves the barber shop.
Barber is sleeping...
Barber is cutting hair.
Customer 7 is getting a haircut.
Barber is sleeping...
Customer 9 is getting a haircut.
Barber is cutting hair.
Customer 7 leaves the barber shop.
Barber is sleeping...
Customer 9 leaves the barber shop.
Barber is cutting hair.
Barber is sleeping...
Advantages of Sleeping Barber Problem
- Models resource allocation and synchronization in concurrent systems.
- Illustrates inter-process communication and coordination mechanisms.
- Provides a simple yet effective scenario for studying synchronization problems in computer science.
- Demonstrates the concept of mutual exclusion in concurrent systems.
- Offers insights into thread synchronization techniques like mutexes and semaphores.
- Facilitates understanding of producer-consumer synchronization patterns.
Disadvantages of Sleeping Barber Problem
- Oversimplification may lead to unrealistic assumptions about real-world scenarios.
- Lack of consideration for dynamic changes in system load or client arrival rates.
- Limited applicability to scenarios with complex resource allocation and scheduling requirements.
- Simplistic representation may not accurately reflect real-world scenarios.
- Does not account for complexities like deadlock, starvation, or priority scheduling.
- Limited scope for addressing advanced synchronization challenges found in complex systems.
Frequently Asked Questions
What is the sleeping barber problem in OS?
The Sleeping Barber Problem is a classic synchronization and concurrency problem in operating systems, illustrating issues like thread management and resource sharing.
What is an example of a sleeping barber algorithm?
In a barbershop, a limited number of chairs for customers and a barber's chair are available. Customers arrive, wait in chairs, and the barber serves one at a time.
What is a semaphore?
A Semaphore is a variable that is non-negative and shared between threads. A semaphore either allows or disallows access to the resource, depending on how it is set up.
How do you solve the sleeping barber problem semaphore?
We can solve the sleeping barber problem with semaphores by using mutual exclusion to control access to shared resources, ensuring only one process can modify state at a time.
What is a binary semaphore?
A binary semaphore is a type of semaphore that can have only two integer values: either 0 or 1. It’s simpler to implement and also provides mutual exclusion.
Conclusion
In this blog, we learned about one of the famous problems discovered by Dijkstra - The sleeping barber problem. We learned about the problem statement and an example that perfectly explains the problem and how the race condition occurs. Then we study the algo to solve this problem using three semaphores and analyze that algorithm.
Recommended Readings: