Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction  
2.
Example of Sleeping Barber Problem
3.
Solution of Sleeping Barber Problem
3.1.
Algorithm
4.
Analysis
5.
Implementation of the Sleeping Barber Problem using semaphores
5.1.
Implementation:
5.2.
Java
5.2.1.
Output:
6.
Advantages of Sleeping Barber Problem
7.
Disadvantages of Sleeping Barber Problem
8.
Frequently Asked Questions
8.1.
What is the sleeping barber problem in OS?
8.2.
What is an example of a sleeping barber algorithm?
8.3.
What is a semaphore?
8.4.
How do you solve the sleeping barber problem semaphore?
8.5.
What is a binary semaphore?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

Sleeping Barber Problem in OS

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction  

The Sleeping Barber problem is a classic illustration of synchronization challenges in concurrent systems, often used to demonstrate process synchronization in operating systems.

Dijkstra introduced the sleeping barber problem in 1965. This problem is based on a hypothetical scenario where there is a barbershop with one barber.

The barbershop is divided into two rooms, the waiting room, and the workroom. The waiting room has n chairs for waiting customers, and the workroom only has a barber chair.

simplification of cfg

Now, if there is no customer, then the barber sleeps in his own chair(barber chair). Whenever a customer arrives, he has to wake up the barber to get his haircut. If there are multiple customers and the barber is cutting a customer's hair, then the remaining customers wait in the waiting room with "n" chairs(if there are empty chairs), or they leave if there are no empty chairs in the waiting room.

The sleeping barber problem may lead to a race condition. This problem has occurred because of the actions of both barber and customer.

Example of Sleeping Barber Problem

Suppose a customer arrives and notices that the barber is busy cutting the hair of another customer, so he goes to the waiting room. While he is on his way to the waiting room, the barber finishes his job and sees the waiting room for other customers. But he(the barber) finds no one in the waiting room (as the customer has yet not arrived in the waiting room), so he sits down in his chair(barber chair) and sleeps. Now the barber is waiting for new customers to wake him up, and the customer is waiting as he thinks the barber is busy.

Here, both of them are waiting for each other, which leads to race conditions.

Illustration Image
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

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();
}
}
}
}

 

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:

Also check out the Interview guide for Product Based Companies as well as some of the Popular interview problems from top tech companies like Amazon, Adobe, Google, Uber, Microsoft, etc.

Refer to our guided pathways on Code studio to learn more about DSACompetitive ProgrammingJavaScriptSystem Design, etc. Enroll in our courses, and use the accessible sample exams and questions as a guide. For placement preparations, look at the interview experiences and interview package.

Previous article
Readers-Writers Problem
Next article
Lock Variable Synchronization
Live masterclass