Sleeping Barber Sample Solution

The following is a sample solution for the sleeping barber problem. It is by no means the only correct solution.

//----------------------------------------------------------------------------
// BarberTest
//  sleeping barber problem
//----------------------------------------------------------------------------

/* only one customer can occupy the barber chair at a time */
Lock * barberchair = new Lock("barber chair");

/* the condition that the barber has a customer sitting in the barber chair -
   binary semaphore, so 1 = customer in chair and 0 = no customer in chair */
Semaphore * inchair = new Semaphore("customer in chair",0);

/* waiting thread is customer waiting for the barber to complete their
   haircut */
Semaphore * barber = new Semaphore("barber",0);

/* mutual exclusion for updating customer counts in waiting room */
Lock * waitingroom = new Lock("waiting room");

const int HAIRCUT_DELAY = 1000;
const int NUM_WAITING_CHAIRS = 5;

int numWaiting = 0;

void Barber ( void * ) {

    for ( ; true ; ) {
	/* wait until customer in chair */
	cout << kernel->currentThread->getName() << " waiting for customers" 
	     << endl;
	inchair->P();

	/* cut hair */
	cout << kernel->currentThread->getName() << " cutting hair" 
	     << endl;
	kernel->alarm->WaitUntil(HAIRCUT_DELAY);

	/* signal customer that haircut is done */
	cout << kernel->currentThread->getName() << " finished haircut" 
	     << endl;
	barber->V();
    }

}

void Customer ( void * ) {

    /* if no room in waiting room, then leave */
    /* else wait until barber chair is available and leave when hair is
       cut */
    waitingroom->Acquire();
    if ( numWaiting >= NUM_WAITING_CHAIRS ) {
	cout << kernel->currentThread->getName() 
	     << ": no room in waiting room; leaving without haircut" << endl;
	waitingroom->Release();
	return;
    } else {
	numWaiting++;
	waitingroom->Release();
    }

    /* attempt to occupy barber chair */
    cout << kernel->currentThread->getName() << " waiting in waiting room" 
	 << endl;
    barberchair->Acquire();

    /* in barber chair, so no longer in waiting room */
    cout << kernel->currentThread->getName() << " in barber chair" 
	 << endl;
    waitingroom->Acquire();
    numWaiting--;
    waitingroom->Release();
    cout << kernel->currentThread->getName() << " waking barber" << endl;
    inchair->V();      /* wake up barber as needed */

    /* wait for haircut to complete */
    cout << kernel->currentThread->getName() 
	 << " waiting for haircut to finish" << endl;
    barber->P();

    /* all done - time to leave */
    cout << kernel->currentThread->getName() << " haircut complete; leaving" 
	 << endl;
    barberchair->Release();
}

void BarberTest () {

    Thread * barber = new Thread("barber");
    barber->Fork((VoidFunctionPtr)Barber,NULL);

    /* create a bunch of customers */
    for ( int ctr = 0 ; ctr < 20 ; ctr++ ) {
	char * name = new char[12];
	sprintf(name,"customer %d",ctr);
	Thread * customer = new Thread(name);
	customer->Fork((VoidFunctionPtr)Customer,NULL);
	kernel->alarm->WaitUntil(rand()%500 + 100);
    }
    

}

Proof of correctness:

No two threads can be reading or writing the shared data numWaiting at a time. numWaiting is accessed only by customer threads, and the waitingRoom lock must be held in order to read or modify its value.

The waiting room cannot hold more than NUM_WAITING_CHAIRS customers. The waitingRoom lock must be held in order to examine the number of waiting customers, and the number waiting is incremented if the waiting room is not full before the lock is released. The number of waiting customers is decremented exactly once for every time it is incremented, so it is an accurate count of the number of waiting customers.

At most one customer can be in the barber chair at once. A mutex lock prevents more than one customer from possessing the chair at a time.

The following events are properly sequenced: customer waits in waiting room, customer sits in barber chair, barber cuts customer's hair, barber finishes haircut, customer leaves. The customer begins by waiting in the waiting room for the barber chair to become availabe. Only one customer at a time can acquire the barber chair lock, and the barber chair lock must be acquired before the customer can sit down. The customer now cannot proceed past waiting for the haircut to finish until the barber has finished the haircut. Meanwhile, the barber cannot proceed past the "waiting for customers" stage until signalled by the customer, which occurs after the customer has sat in the barber chair. The barber then cuts the hair and finishes the haircut, signalling the customer that the haircut is complete. The customer is then able to leave. The barber cannot proceed past the "waiting for customers" stage again until the next customer is seated in the barber's chair. Since only one customer at a time can make it past the "acquire barber chair lock" step, the right customer is signalled when the barber finishes the haircut. (This can also be demonstrated by lining up the customer and barber code side-by-side, pairing the signals and waits on the semaphores - the parts of the customer and barber which overlap between the signals and waits can safely be executed in any order, and using semaphores means that it is OK if one signals before the other waits.)

The barber doesn't oversleep and miss a customer sitting in the barber chair. Each customer signals the barber when they've sat down, and using semaphores means that the order in which the customer signals and the barber waits doesn't matter. (With a condition variable, if the customer signalled before the barber went back to sleep after the previous customer, the barber would miss the wakeup call.)

There is no deadlock. The only time that hold-and-wait occurs is when the customer is holding the barberchair lock and is attempting to acquire the waitingRoom lock. However, whenever the waitingRoom lock is held, there is nothing (other than the scheduling of the thread to run) to prevent the lock from being released.