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.