Summary
A year ago I got an interview where the interviewer asked me to solve the well known Dijkstra’s Sleeping Barber Problem. I did it with blocking queue. The code is clean and simple. I hope you enjoy it as well.
GitHub Project Link
Sleeping Barber Problem
Each customer, when he arrives, looks to see what the barber is doing. If the barber is sleeping, then the customer wakes him up and sits in the chair. If the barber is cutting hair, then the customer goes to the waiting room. If there is a free chair in the waiting room, the customer sits in it and waits his turn. If there is no free chair, then the customer leaves. Based on a naïve analysis, the above description should ensure that the shop functions correctly, with the barber cutting the hair of anyone who arrives until there are no more customers, and then sleeping until the next customer arrives.
In practice, there are a number of problems that can occur that are illustrative of general scheduling problems.
The problems are all related to the fact that the actions by both the barber and the customer (checking the waiting room, entering the shop, taking a waiting room chair, etc.) all take an unknown amount of time. For example, a customer may arrive and observe that the barber is cutting hair, so he goes to the waiting room. While he is on his way, the barber finishes the haircut he is doing and goes to check the waiting room. Since there is no one there (the customer not having arrived yet), he goes back to his chair and sleeps. The barber is now waiting for a customer and the customer is waiting for the barber. In another example, two customers may arrive at the same time when there happens to be a single seat in the waiting room. They observe that the barber is cutting hair, go to the waiting room, and both attempt to occupy the single chair.
Blocking Queue Sleeping Barber GitHub Project Link
import java.util.concurrent.ArrayBlockingQueue; import java.util.concurrent.BlockingQueue; import java.util.concurrent.TimeUnit; public class BlockinQueueSleepingBarber extends Thread { public static final int CHAIRS = 5; public static final long BARBER_TIME = 5000; private static final long CUSTOMER_TIME = 2000; public static final long OFFICE_CLOSE = BARBER_TIME * 2; public static BlockingQueue queue = new ArrayBlockingQueue(CHAIRS); class Customer extends Thread { int iD; boolean notCut = true; BlockingQueue queue = null; public Customer(int i, BlockingQueue queue) { iD = i; this.queue = queue; } public void run() { while (true) { // as long as the customer is not cut he is in the queue or if not enough sits he is out try { this.queue.add(this.iD); this.getHaircut(); // take a sit } catch (IllegalStateException e) { System.out.println("There are no free seats. Customer " + this.iD + " has left the barbershop."); } break; } } // take a seat public void getHaircut() { System.out.println("Customer " + this.iD + " took a chair"); } } class Barber extends Thread { BlockingQueue queue = null; public Barber(BlockingQueue queue) { this.queue = queue; } public void run() { while (true) { // runs in an infinite loop try { Integer i = this.queue.poll(OFFICE_CLOSE, TimeUnit.MILLISECONDS); if (i==null) break; // barber slept for long time (OFFICE_CLOSE) no more clients in the queue - close office this.cutHair(i); // cutting... } catch (InterruptedException e) { } } } // simulate cutting hair public void cutHair(Integer i) { System.out.println("The barber is cutting hair for customer #" + i); try { sleep(BARBER_TIME); } catch (InterruptedException ex) { } } } public static void main(String args[]) { BlockinQueueSleepingBarber barberShop = new BlockinQueueSleepingBarber(); barberShop.start(); // Let the simulation begin } public void run() { Barber giovanni = new Barber(BlockinQueueSleepingBarber.queue); giovanni.start(); // create new customers for (int i = 1; i < 16; i++) { Customer aCustomer = new Customer(i, BlockinQueueSleepingBarber.queue); aCustomer.start(); try { sleep(CUSTOMER_TIME); } catch (InterruptedException ex) {}; } } } If you run code you get console report like below
Customer 1 took a chair The barber is cutting hair for customer #1 Customer 2 took a chair Customer 3 took a chair The barber is cutting hair for customer #2 Customer 4 took a chair Customer 5 took a chair Customer 6 took a chair The barber is cutting hair for customer #3 Customer 7 took a chair Customer 8 took a chair The barber is cutting hair for customer #4 Customer 9 took a chair There are no free seats. Customer 10 has left the barbershop. The barber is cutting hair for customer #5 Customer 11 took a chair 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 for customer #6 Customer 14 took a chair There are no free seats. Customer 15 has left the barbershop. The barber is cutting hair for customer #7 The barber is cutting hair for customer #8 The barber is cutting hair for customer #9 The barber is cutting hair for customer #11 The barber is cutting hair for customer #14
You can easily modify this code for example if you need to add new barber like this
Barber barber01 = new Barber(BlockinQueueSleepingBarber.queue, "01"); barber01.start(); Barber barber02 = new Barber(BlockinQueueSleepingBarber.queue, "02"); barber02.start();
New code will work with two barbers
Blocking Queue Sleeping Barbers GitHub Project Link
package com.threads;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.TimeUnit;
public class BlockinQueueSleepingBarber extends Thread {
public static final int CHAIRS = 5;
public static final long BARBER_TIME = 5000;
private static final long CUSTOMER_TIME = 1500;
public static final long OFFICE_CLOSE = BARBER_TIME * 2;
public static BlockingQueue<Integer> queue = new ArrayBlockingQueue<Integer>(CHAIRS);
class Customer extends Thread {
int iD;
boolean notCut = true;
// Constructor for the Customer
BlockingQueue<Integer> queue = null;
public Customer(int i, BlockingQueue<Integer> queue) {
iD = i;
this.queue = queue;
}
public void run() {
while (true) { // as long as the customer is not cut he is in the queue or if not enough sits he is out
try {
this.queue.add(this.iD);
this.getHaircut(); // take a sit
} catch (IllegalStateException e) {
System.out.println("There are no free seats. Customer "+ this.iD + " has left the barbershop.");
}
break;
}
}
// take a seat
public void getHaircut() {
System.out.println("Customer " + this.iD + " took a chair");
}
}
class Barber extends Thread {
BlockingQueue<Integer> queue = null;
private String name;
public Barber(BlockingQueue<Integer> queue, String name) {
this.name = name;
this.queue = queue;
}
public void run() {
while (true) { // runs in an infinite loop
try {
Integer i = this.queue.poll(OFFICE_CLOSE, TimeUnit.MILLISECONDS);
if (i==null) break; // barber slept for long time (OFFICE_CLOSE) no more clients in the queue - close office
this.cutHair(i); // cutting...
} catch (InterruptedException e) {
}
}
}
public void cutHair(Integer i) {
System.out.println("The barber " + this.name + " is cutting hair for customer #" + i);
try {
sleep(BARBER_TIME);
} catch (InterruptedException ex) {
}
}
}
public static void main(String args[]) {
BlockinQueueSleepingBarber barberShop = new BlockinQueueSleepingBarber();
barberShop.start(); // Let the simulation begin
}
public void run() {
Barber barber01 = new Barber(BlockinQueueSleepingBarber.queue, "01");
barber01.start();
Barber barber02 = new Barber(BlockinQueueSleepingBarber.queue, "02");
barber02.start();
// create new customers
for (int i = 1; i < 16; i++) {
Customer aCustomer = new Customer(i, BlockinQueueSleepingBarber.queue);
aCustomer.start();
try {
sleep(CUSTOMER_TIME);
} catch (InterruptedException ex) {};
}
}
}
Blocking Queue Sleeping Barbers Pool Executor GitHub Project Link
Express Notes by Sergey Vyatkin 
Hi, I am interested in this task and I would like to ask you to explain parts of your solution to me, if it is possible. My e-mail address is denitsa_yordanova@hotmail.com , Please write to me if you have the opportunity to help me.
Denny,
Please do not hesitate to ask your questions in the topic. I’m going to write much more detail explanation for the subject and expand for pool executor design pattern in this holiday season.
Thank you for your interest Dijkstra’s task.
Sergey
Hi SVyatkin,
I am sorry to say this program seems like only a producer consumer problem. The main flavour of Sleeping Barber is not addressed here. Here, customer can no way wake barber up. Please correct me if I am wrong.
I agree Anirban. You cannot use ready concurrent Array,Queues etc , or it will lead you co Consumer-Producer solution. This is wrong implementation above. Barber and Customer has to perform activity one towards each other, to consider problem solved. Apropos , most of the articles in the internet try to cheat Sleeping Barber problem by Producer-Consumer way.