## Wednesday, December 21, 2005

### 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."

Labels: