5. Sleeping Barber - Tanenbaum's informal description

I include here some quotations from Tanenbaum's book Modern Operating Systems, second edition, Prentice Hall, 2001, since without these it is difficult to discuss the correctness or otherwise of his solution.

page 129. "The barber shop has one barber [the program described previously had 3 barbers], one barber chair, and n chairs for waiting customers, if any, to sit on. If there are no customers present, the barber sits down in the barber chair and falls asleep, as illustrated in Fig. 2-35. When a customer arrives, he has to wake up the sleeping barber. If additional customers arrive while the barber is cutting a customer's hair , they either sit down (if there are empty chairs) or leave the shop (if the chairs are full)."

page 130. "Our solution uses three semaphores: customers, which counts waiting customers (excluding the customer who is in the barber chair, who is not waiting) , barbers, the number of barbers (0 or 1) who are idle, waiting for customers, and mutex, which is used for mutual exclusion. We need also a variable, waiting, which also counts the waiting customers."

pages 130-132. "When the barber shows up for work in the morning, he executes the procedure barber, causing him to block on the semaphore customers because it is initially 0. The barber then goes to sleep, as shown in Fig. 2-35. He stays asleep until the first customer shows up.
When a customer arrives, he executes customer, starting by acquiring mutex to enter a critical region."
"The customer then checks to see if the number of waiting customers is less than the number of chairs. If not, he releases mutex and leaves without a haircut.
If there is an available chair, the customer increments the integer variable, waiting. Then he does an up on the semaphore customers, thus waking up the barber. At this point, the customer and barber are both awake. When the customer releases mutex, the barber grabs it, does some housekeeping, and begins the haircut.
When the haircut is over, the customer exits the procedure and leaves the shop."

4. Sleeping Barber - update

The Sleeping Barber example has been removed from the new edition of Modern Operating Systems (A. Tanenbaum) due to lack of space (personal communication).

1. The Sleeping Barber

It is well known that it is difficult to program concurrent processes. Andy Tanenbaum's book "Modern Operating Systems" describes four classical problems, the Producer Consumer, the Dining Philosophers, the Reader-Writer, and the Sleeping Barber. It is Tanenbaum's solution to the last of these I would like to discuss here.

The problem is specified in natural language: there is a barber shop with a fixed number of barbers, serving an arbitrary number of customers as they arrive. However only a fixed number of customers may enter the shop, determined by the number of chairs in the waiting room. The barbers sleep until customers arrive. They then cut hair.

The two principal elements of the problem seem to me to be
(i) the synchronization of the customers with barbers - ie customers get their hair cut at approximately the same time that barber cuts their hair, and
(ii) the restriction of the number of customers connected to the shop. A solution to the problem should not make any assumptions about the timing of actions; arbitrary delays may occur at any point in any process.

Tanenbaum proposes a solution using semaphores; further, on the site for his book there are java programs with threads implementing the solution, so that it possible to be clear at least about the proposed solution.

Unfortunately Tanenbaum's solution, which is widely quoted, fails to satisfy either (i) or (ii). The program supplied appears to satisfy these requirements when executed, but varying the program by introducing a delay at one point in the customers' protocol shows that it fails both criteria: the number of customers still attached to the shop grows arbitrarily, and there is no synchronization between the barbers and the customers. The critical point is that customers may delay before doing the action down(barber).

In following posts I will give details.

2. Sleeping Barber - traces

This is a follow-on from the post above.

Here some details about the program supplied by Tanenbaum, as well as the modification I made.

I'll put the executions, but you can find the programs in the next post.

The program unmodified - SleepingBarber.java.
In this example there are three barbers, five chairs, and the output is exactly as you would like.
A sample output:
Barber 0 is cutting hair
Customer 0 is getting his hair cut
Barber 1 is cutting hair
Customer 1 is getting his hair cut
Barber 2 is cutting hair
Customer 2 is getting his hair cut
Barber 0 is cutting hair
Customer 3 is getting his hair cut
Barber 1 is cutting hair
Customer 4 is getting his hair cut
Barber 2 is cutting hair
Customer 5 is getting his hair cut
Barber 0 is cutting hair
Customer 6 is getting his hair cut
and so on.

Now the program with the only change being that the customers delay before executing down(barber) - SleepingBarberD.java.
Sample output in which the lack of synchronization between customer and client is clear. What is less clear is that very early there are 12 customers in the shop but only 5 chairs and 3 barber's chairs - overcrowding! This would be a problem if the barbers were web server processes, particularly because the excess of customers may be unbounded:
Barber 0 is cutting hair
Barber 1 is cutting hair
Barber 2 is cutting hair
Barber 0 is cutting hair
Barber 1 is cutting hair
Barber 2 is cutting hair
Barber 0 is cutting hair
Barber 1 is cutting hair
Barber 2 is cutting hair
Barber 0 is cutting hair
Barber 1 is cutting hair
Barber 2 is cutting hair
Customer 0 is getting his hair cut
Barber 0 is cutting hair
Customer 1 is getting his hair cut
Barber 1 is cutting hair
Customer 2 is getting his hair cut
Barber 2 is cutting hair
Customer 3 is getting his hair cut
Customer 4 is getting his hair cut
Customer 5 is getting his hair cut
Customer 6 is getting his hair cut
Customer 7 is getting his hair cut
Barber 0 is cutting hair
Customer 8 is getting his hair cut
Barber 1 is cutting hair
Customer 9 is getting his hair cut
Barber 2 is cutting hair
Customer 10 is getting his hair cut

3. Sleeping Barber - code

Here are the programs for Semaphore, SleepingBarber and SleepingBarberD described before.
SleepingBarberD differs only by the addition of delay to the customers.



Semaphore.java-----------------------------------
// This count implements a classic counting Semaphore
// It has two synchronized operations which it can perform
// up - increments the count of the semaphore and wakes up
// waiting threads
// down - decrements the count of the semaphore or if zero
// suspends the thread


class Semaphore extends Object
{
private int count;

public Semaphore(int startingCount){
count = startingCount;
}

public void down(){
synchronized (this) {
while (count ‹= 0) {
// We must wait
try {
wait();
} catch (InterruptedException ex) {
// I was interupted, continue onwards
}
}

// We can decrement the count
count--;
}

}

public void up(){
synchronized (this) {
count++;
//notify a waiting thread to wakeup
if (count == 1 ) {
notify();
}
}
}
}
End of Semaphore.java





SleepingBarber.java-------------------------
//Figure 2-36

import Semaphore;

public class SleepingBarber extends Thread {

// Shared objects
// Number of customers waiting for service
public static Semaphore customers = new Semaphore(0);

// Number of barbers waiting for customers
public static Semaphore barbers = new Semaphore(0);

// For mutual exclusion
public static Semaphore mutex = new Semaphore(1);

// Customers are waiting (not being cut)
public static int waiting = 0;

// Chairs for waiting customers
public static final int CHAIRS = 5;

class Barber extends Thread {
private int myNumber; // Id for the Barber

public Barber(int i) { // Constructor for the Barber
myNumber = i;
}

public void run(){ // What a barber does
while(true) {
customers.down(); // Go to sleep if no customers
mutex.down(); // Acquire access to waiting
waiting = waiting - 1; // Decrement count of waiting
// customers
barbers.up(); // One barber is now ready to cut
// hair
mutex.up(); // Release waiting
cut_hair(); // Noncritical region
}
}

public void cut_hair(){
System.out.println("Barber " + myNumber + " is cutting hair");
try {
sleep(7500);
} catch (InterruptedException ex){ }
}
} //end of Barber Class

private class Customer extends Thread {
private int myNumber; // Id for the Customer

public Customer(int i) { // Constructor for the Customer
myNumber = i;
}

public void run(){ // What a customer does
mutex.down(); // Acquire access to waiting
if(waiting ‹ CHAIRS){
waiting = waiting + 1; // Increment count of waiting
// customers
customers.up(); // Wake up barber if needed
mutex.up(); // Release waiting
barbers.down(); // Go to sleep if number of free
// barbers is 0
get_haircut(); // Noncritical region
} else {
mutex.up(); // Shop is full do not wait
}
}


public void get_haircut(){
System.out.println("Customer " + myNumber
+ " is getting his hair cut");
try {
sleep(10000);
} catch (InterruptedException ex){ }
}
} //end of Customer Class


public static void main(String args[]) {

SleepingBarber holder = new SleepingBarber();

holder.start();

}

// This thread spins off a number of customers
public void run(){

final int BARBERS = 3;

Barber aBarber;
Customer aCustomer;

for(int i=0; i‹BARBERS; i++) {
// Create the barbers
aBarber = new Barber(i);

// Start the threads running
aBarber.start();
}

int customerNumber = 0;
while(true){
aCustomer = new Customer(customerNumber++);

// Start the customer running
aCustomer.start();

// Wait a bit and make another customer
try {
sleep(1000);
} catch(InterruptedException ex) {};
}
} //end of run method for SleepingBarber

}
End of SleepingBarber.java---------------------------------------






SleepingBarberD.java---------------------------------------------
//Figure 2-36

import Semaphore;

public class SleepingBarberD extends Thread {

// Shared objects
// Number of customers waiting for service
public static Semaphore customers = new Semaphore(0);

// Number of barbers waiting for customers
public static Semaphore barbers = new Semaphore(0);

// For mutual exclusion
public static Semaphore mutex = new Semaphore(1);

// Customers are waiting (not being cut)
public static int waiting = 0;

// Chairs for waiting customers
public static final int CHAIRS = 5;

class Barber extends Thread {
private int myNumber; // Id for the Barber

public Barber(int i) { // Constructor for the Barber
myNumber = i;
}

public void run(){ // What a barber does
while(true) {
customers.down(); // Go to sleep if no customers
mutex.down(); // Acquire access to waiting
waiting = waiting - 1; // Decrement count of waiting
// customers
barbers.up(); // One barber is now ready to cut
// hair
mutex.up(); // Release waiting
cut_hair(); // Noncritical region
}
}

public void cut_hair(){
System.out.println("Barber " + myNumber + " is cutting hair");
try {
sleep(7500);
} catch (InterruptedException ex){ }
}
} //end of Barber Class

private class Customer extends Thread {
private int myNumber; // Id for the Customer

public Customer(int i) { // Constructor for the Customer
myNumber = i;
}

public void run(){
// What a customer does
mutex.down(); // Acquire access to waiting
if(waiting ‹ CHAIRS){
waiting = waiting + 1; // Increment count of waiting
// customers
customers.up(); // Wake up barber if needed
mutex.up(); // Release waiting

//added section RFC Walters 9 December 2005
try { //random sleep
sleep(10000); //
} catch (InterruptedException e) {} //
try { //random sleep
sleep(10000); //
} catch (InterruptedException e) {} //
try { //random sleep
sleep(10000); //
} catch (InterruptedException e) {} //
//end of added section RFC Walters 9 December 2005




barbers.down(); // Go to sleep if number of free
// barbers is 0
get_haircut(); // Noncritical region
} else {
mutex.up(); // Shop is full do not wait
}
}


public void get_haircut(){
System.out.println("Customer " + myNumber
+ " is getting his hair cut");
try {
sleep(10000);
} catch (InterruptedException ex){ }
}
} //end of Customer Class


public static void main(String args[]) {

SleepingBarberD holder = new SleepingBarberD();

holder.start();

}

// This thread spins off a number of customers
public void run(){

final int BARBERS = 3;

Barber aBarber;
Customer aCustomer;

for(int i=0; i // Create the barbers
aBarber = new Barber(i);

// Start the threads running
aBarber.start();
}

int customerNumber = 0;
while(true){
aCustomer = new Customer(customerNumber++);

// Start the customer running
aCustomer.start();

// Wait a bit and make another customer
try {
sleep(1000);
} catch(InterruptedException ex) {};
}
} //end of run method for SleepingBarber

}

End of SleepingBarberD.java