CPSC 331 Sleeping Barber Solution

CPSC 331 Sleeping Barber Solution

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.

Read full article from CPSC 331 Sleeping Barber Solution