Sleeping Barber Problem in Java
The barbershop in this issue has one barber, one barber chair, and N chairs for customers in the waiting area. We may demonstrate the issue by keeping with the original idea, as shown in the image below.
Let us examine the problem's characteristics:
- When there are no customers in the waiting area, the barber rests. As a result, when a customer arrives, he must awaken the barber.
- As shown in the diagram, customers can enter the waiting area and wait to see if the barber is available.
- Other clients who arrive while the barber is cutting a customer's hair are seated in the waiting area.
- If there are no empty chairs in the waiting area, customers leave the barbershop.
We must synchronise the barber and the clients so that there are no race circumstances. Because we have limited resources and waiting activities, this challenge is quite similar to other queueing situations.
The diagram below depicts the problem's primary characteristics:
Three semaphores are used in the solution:
- One for customers, which counts the number of clients who are waiting but eliminates the customer in the barber chair because he is not waiting.
- Another consideration is the barber's condition, whether he's waiting or busy.
- The last one is for mutual exclusion, because there are some essential areas that must be thread-safe.
When the barber comes for work, he follows the barber routine and checks to see whether any customers are ready. Pick up the customer for a haircut and block the customer's semaphore if anybody is available. The barber sleeps if no one is ready for a haircut.
If a chair becomes available, the waiting counter is increased, the barber awakens, and the customer releases the mutex. The barber then obtains the mutex, enters the crucial region, and begins the haircut.
The customer leaves once the haircut is completed. Now the barber looks to see whether there are any other clients waiting for a haircut. If it isn't, the barber will go to bed.
Let's move on to the solution's pseudocode. We may begin with semaphores and constants such as the number of chairs in the waiting room:
Algorithm 1
Some Synchronization Primitives and Constants
CHAIRS ← 5
Customers ← 0
barbers ← 0
mutex ←1
num_waiting ← 0
When the barber arrives at the barbershop, he follows the barber protocol outlined below. He must wait till a customer appears because there are no customers. That's why he falls asleep and doesn't wake up until the first client arrives. We wait for the barber and supply one of the main synchronisation criteria by using the customers' semaphore:
Algorithm:
Barber Routine
while True do
sem_wait(customers)
sem_wait(mutex)
waiting ← waiting - 1
sem_post(barbers)
sem_post(mutex)
cut_hair()
end
So, we've synchronised the barber routine, but we still need to organise the client routine to supply the barbershop with a perfect concurrent system. When a client comes in, he runs the customer() routine. The method begins by getting a mutex in order to reach the crucial zone. First, when he comes at the barbershop, he should see whether there is a chair available for him. If there isn't, he walks out of the business. Otherwise, he might wait for the barber, and then receive a haircut when the barber is available:
Algorithm:
Customer Routine
sem_wait(mutex)
if waiting <CHAIRS then
waiting ← waiting + 1
sem_post(customers)
sem_post(mutex) s
em_wait(barbers)
get_haircut()
end
sem_post(mutex)
When the haircut is finished, the consumer exits the business using the protocol. Because each client only receives one haircut at a time, there is no while loop in the customer routine. However, the barber continues to do so in order to gain a new customer. When a customer walks into the business, he offers him a haircut. Otherwise, he falls asleep.
Filename: SleepingBarberProblem.java
import java.util.concurrent.*;
public class SleepingBarberProblem extends Thread {
/* PREREQUISITES */
/* We design the semaphores. Because there are no customers and the barber is sleeping, we run the constructor with argument 0, resulting in semaphores with zero initial permissions. Semaphore(1) creates a binary semaphore as needed.*/
public static Semaphore customers = new Semaphore(0);
public static Semaphore barber = new Semaphore(0);
public static Semaphore Access = new Semaphore(1);
/* We indicate that there are 5 chairs in this barbershop. */
public static final int CHAIRS = 5;
/* We generate the number NumberOfEmptySeats so that consumers can sit on a Empty seat or leave the barbershop if no chairs are available. */
public static int NumberOfEmptySeats = CHAIRS;
/* THE CUSTOMER THREAD */
class Customer extends Thread {
/* In the Client waiting loop, we generate the integer A, which is a unique ID number for each customer, and the boolean notCut. */
int A;
boolean notCut=true;
/* Customer Constructor */
public Customer(int u) {
A = u;
}
public void run() {
while (notCut) { // As long as the client is not cut
try {
Access.acquire(); // attempts to get access to the seats
if (NumberOfEmptySeats > 0) { // if there are any empty seats
System.out.println("Customer " + this.A + " simply took a seat.");
NumberOfEmptySeats--; // sitting down in a chair
customers.release(); // Inform the barber that a customer has arrived.
Access.release(); // It is no longer necessary to lock the seats.
try {
barber.acquire(); // Now it is this customer's time, but if the barber is busy, we'll have to wait.
notCut = false; // This customer will now go through the following protocol.
this.get_haircut(); //cutting
} catch (InterruptedException ex) {}
}
else { // There are no available seats.
System.out.println("There are no free seats. Customer " + this.A + " has left the barbershop.");
Access.release(); // release the seat locks
notCut=false; // The client will leave since there are no more open seats in the queue.
}
}
catch (InterruptedException ex) {}
}
}
/* This procedure will simulate having your hair cut. */
public void get_haircut(){
System.out.println("Customer " + this.A + " is getting his hair cut");
try {
sleep(5050);
} catch (InterruptedException ex) {}
}
}
/* THE BARBER THREAD */
class SleepingBarber extends Thread {
public SleepingBarber() {}
public void run() {
while(true) { // runs in an endless loop
try {
customers.acquire(); // attempts to get a customer; if none is available, he returns to sleep Access.release(); // He has been awakened at this moment -> wish to change the number of available seats
NumberOfEmptySeats++; // One chair is free.
barber.release(); // The barber is all set to cut
Access.release(); // We no longer require the chair locks.
this.cutHair(); //cutting
} catch (InterruptedException ex) {}
}
}
/* This procedure will simulate hair cutting. */
public void cutHair(){
System.out.println("The barber is cutting hair");
try {
sleep(5000);
} catch (InterruptedException ex){ }
}
}
/* main method */
public static void main(String args[]) {
SleepingBarberProblem barberShop = new SleepingBarberProblem(); // opens a new barbershop
barberShop.start(); // Allow the simulation to begin.
}
public void run(){
SleepingBarber Shiva = new SleepingBarber(); //Shiva is the best barber ever
Shiva.start(); // Prepared for another day at wor
/* For the time being, this strategy will generate new clients. */
for (int u=1; u<16; u++) {
Customer aCustomer = new Customer(u);
aCustomer.start();
try {
sleep(2000);
} catch(InterruptedException ex) {};
}
}
}
Output:
Customer 1 simply took a seat.
The barber is cutting hair
Customer 1 is getting his hair cut
Customer 2 simply took a seat.
Customer 3 simply took a seat.
The barber is cutting hair
Customer 2 is getting his hair cut
Customer 4 simply took a seat.
Customer 5 simply took a seat.
The barber is cutting hair
Customer 3 is getting his hair cut
Customer 6 simply took a seat.
Customer 7 simply took a seat.
Customer 8 simply took a seat.
The barber is cutting hair
Customer 4 is getting his hair cut
Customer 9 simply took a seat.
There are no free seats.
Customer 10 has left the barbershop.
The barber is cutting hair
Customer 5 is getting his hair cut
Customer 11 simply took a seat.
There are no free seats.
Customer 12 has left the barbershop.
There are no free seats.
Customer 13 has left the barbershop.
The barber is cutting hair
Customer 6 is getting his hair cut
Customer 14 simply took a seat.
There are no free seats.
Customer 15 has left the barbershop.
The barber is cutting hair
Customer 7 is getting his hair cut
The barber is cutting hair
Customer 8 is getting his hair cut
The barber is cutting hair
Customer 9 is getting his hair cut
The barber is cutting hair
Customer 11 is getting his hair cut
The barber is cutting hair
Customer 14 is getting his hair