Java Concurrency with Barbershop Problem
Barbershop Problem aka. Sleeping Barber problem is another classical concurrency example used in operating system lectures. The original problem was proposed by Edsger Dijkstra.
Problem Definition
A barbershop consist of a waiting room with n chairs, and a barber room with one barber chair. Given the following constraints:
- If there are no customers to be served, the barber goes to sleep
- If a customer enters the barbershop and all chairs are occupied, then the customer leaves the shop.
- If the barber is busy, but chairs are available, then the customer sits in one of the free chairs.
- If the barber is sleeping, the customer wakes up the barber.
We need to write a program simulating the barbershop. Our goal is to provide coordination between customers and the barber by complying the above constraints. Our solution will use Rendezvous pattern.
Rendezvouses: It is a special barrier type. Barrier works for multiple parties but Rendezvous is done between 2 threads. Thread A has to wait for Thread B and vice versa. So it works both ways.
In other words, given this code
We want to guarantee that a1 happens before b2 and b1 happens before a2. So they do have a synchronisation to work at a specific parts of their codes at same time.
To provide this guarantee, the following solution is proposed:
So they both signal each other and wait for each other. And we make sure that the given condition is satisfied.
Overview
We can use the following variables for synchronisation and mutual exclusion.
limit=4 # limit for total number of customer
customers = 0 # customer counter
mutex = new ReenterantLock() # mutex to protect customer counter
customerReady = new Semaphore(0) # barber waits on customerReady
barberReady = new Semaphore(0) # customer waits on barberReady
customerDone = new Semaphore(0) # customer signals haircut is done
barberDone = new Semaphore(0) # barber signals haircut is donelimit is the total number of customers that can be in the shop. customers counts the number of customers in the shop; it will be protected by mutex.
The barber waits on customerReady until a customer enters the shop, then the customer waits on barberReady until the barber signals him that it is his turn.
After the haircut, the customer signals customerDone and waits on barberDone. These 2 semaphores will be used as rendezvous sync to make both customer and barber to arrive end of haircut part together.
Implementation
We will have the customer and barber individuals providing service or receiving service as follows:
public class Barber {
public void cutHair() {
System.out.println("Barber: Cutting Hair --- " + Thread.currentThread().getName());
}
}
public class Customer {
public void enter() {
System.out.println("Customer: Enters the shop --- " + Thread.currentThread().getName());
}
public void getHairCut() {
System.out.println("Customer: Getting Haircut --- " + Thread.currentThread().getName());
}
public void leave() {
System.out.println("Customer: Leaves the shop --- " + Thread.currentThread().getName());
}
}
Barbershop class is responsible for coordinating the synchronisation between customers and barber. Our implementation is going to have 2 methods:
The method startService does respectively:
- Waits for a customer to arrive (a signal that customer is ready)
- Signals that barber is read to start
- Give haircut
- Wait for customer to approve
- Signals that barber is done
The method receiveNewCustomer does respectively
- Accept customer unless the limit is reached
- Signal that customer is ready to be served
- Wait for barber to be available
- Get haircut
- Signal that customer is done
- Wait for barber to approve
public class Barbershop {
private final int limit;
public int customers;
private final Barber barber;
private final Semaphore customerReady;
private final Semaphore barberReady;
private final Semaphore customerDone;
private final Semaphore barberDone;
private final ReentrantLock mutex;
public Barbershop(int limit) {
this.limit = limit;
customers = 0;
customerReady = new Semaphore(0);
barberReady = new Semaphore(0);
customerDone = new Semaphore(0);
barberDone = new Semaphore(0);
mutex = new ReentrantLock();
barber = new Barber();
}
public Void startService() {
// wait for a customer to arrive
try {
customerReady.acquire();
} catch (InterruptedException e) {
System.out.println("Barber wait task is interrupted: " + e.getMessage());
}
// signal that barber is ready
barberReady.release();
// give a haircut
barber.cutHair();
// wait for a customer to approve done
try {
customerDone.acquire();
} catch (InterruptedException e) {
System.out.println("Barber wait task is interrupted: " + e.getMessage());
}
// signal the customer that barber is done
barberDone.release();
System.out.println("Haircut is done");
return null;
}
public Void receiveNewCustomer() {
Customer customer = new Customer();
customer.enter();
mutex.lock();
if (customers == limit) {
mutex.unlock();
customer.leave();
return null;
}
customers += 1;
mutex.unlock();
customerReady.release();
// wait for the barber to be available
try {
barberReady.acquire();
} catch (InterruptedException e) {
System.out.println("Customer wait task is interrupted: " + e.getMessage());
}
// get the haircut
customer.getHairCut();
// signal that customer is done
customerDone.release();
// wait for barber to approve done
try {
barberDone.acquire();
} catch (InterruptedException e) {
System.out.println("Customer wait task is interrupted: " + e.getMessage());
}
mutex.lock();
customers -= 1;
mutex.unlock();
return null;
}
}Our solution contains 2 Rendezvouses synchronisation pattern first one with customerReady and barberReady, second one with customerDone and barberDone semaphores. We could alternatively use a barrier here to justify that barber will not start to work on another customer before the current one will leave. So we try to make these 2 threads to finish at the same time.
Sample Output
In order to run the program in parallel thread we can use the following main method:
public class Simulator {
private static final int NUM_ITERATION = 8;
public static void main(String[] args) {
ExecutorService executor = Executors.newWorkStealingPool();
Barbershop barbershop = new Barbershop(4);
Callable<Void> barbershopTask = barbershop::startService;
Callable<Void> receiveCustomerTask = barbershop::receiveNewCustomer;
List <Future<Void>> barberFutures = new ArrayList<>();
List <Future<Void>> customerFutures = new ArrayList<>();
for (int i=0; i<NUM_ITERATION; i++) {
Future <Void> barberFuture = executor.submit(barbershopTask);
barberFutures.add(barberFuture);
Future <Void> customerFuture = executor.submit(receiveCustomerTask);
customerFutures.add(customerFuture);
}
barberFutures.forEach(future -> {
try {
future.get();
} catch (InterruptedException | ExecutionException e) {
e.printStackTrace();
}
});
customerFutures.forEach(future -> {
try {
future.get();
} catch (InterruptedException | ExecutionException e) {
e.printStackTrace();
}
});
}
}The output of the program:
Customer: Enters the shop --- ForkJoinPool-1-worker-9
Customer: Enters the shop --- ForkJoinPool-1-worker-5
Customer: Enters the shop --- ForkJoinPool-1-worker-13
Customer: Enters the shop --- ForkJoinPool-1-worker-17
Barber: Cutting Hair --- ForkJoinPool-1-worker-27
Customer: Getting Haircut --- ForkJoinPool-1-worker-13
Barber: Cutting Hair --- ForkJoinPool-1-worker-3
Barber: Cutting Hair --- ForkJoinPool-1-worker-23
Customer: Getting Haircut --- ForkJoinPool-1-worker-17
Customer: Getting Haircut --- ForkJoinPool-1-worker-9
Barber: Cutting Hair --- ForkJoinPool-1-worker-19
Haircut is done
Haircut is done
Customer: Enters the shop --- ForkJoinPool-1-worker-25
Customer: Enters the shop --- ForkJoinPool-1-worker-21
Customer: Getting Haircut --- ForkJoinPool-1-worker-25
Customer: Getting Haircut --- ForkJoinPool-1-worker-21
Haircut is done
Customer: Getting Haircut --- ForkJoinPool-1-worker-5
Haircut is done
Barber: Cutting Hair --- ForkJoinPool-1-worker-7
Barber: Cutting Hair --- ForkJoinPool-1-worker-31
Customer: Enters the shop --- ForkJoinPool-1-worker-23
Customer: Enters the shop --- ForkJoinPool-1-worker-17
Customer: Getting Haircut --- ForkJoinPool-1-worker-23
Customer: Getting Haircut --- ForkJoinPool-1-worker-17
Barber: Cutting Hair --- ForkJoinPool-1-worker-13
Haircut is done
Haircut is done
Haircut is done
Barber: Cutting Hair --- ForkJoinPool-1-worker-9
Haircut is doneReference
Allen B. Downey, The Little Book of Semaphores
