[NetBehaviour] The Cigarette Smokers Problem

[James Morris]

>From http://en.wikipedia.org/wiki/Cigarette_smokers_problem

The cigarette smokers problem is a concurrency problem in computer
science, originally described in 1971 by S. S. Patil.

Assume a cigarette requires three ingredients to smoke:

   1. Tobacco
   2. Paper
   3. A match

Assume there are also three chain smokers around a table, each of whom has
an infinite supply of one of the three ingredients - one smoker has an
infinite supply of tobacco, another has an infinite supply of paper, and
the third has an infinite supply of matches.

Assume there is also a non-smoking arbiter. The arbiter enables the
smokers to make their cigarettes by selecting two of the smokers
arbitrarily (nondeterministically), taking one item out of each of their
supplies, and placing the items on the table. He then notifies the third
smoker that he has done this. The third smoker removes the two items from
the table and uses them (along with his own supply) to make a cigarette,
which he smokes for a while. Meanwhile, the arbiter, seeing the table
empty, again chooses two smokers at random and places their items on the
table. This process continues forever.

The smokers do not hoard items from the table; a smoker only begins to
roll a new cigarette once he is finished smoking the last one. If the
arbiter places tobacco and paper on the table while the match man is
smoking, the tobacco and paper will remain untouched on the table until
the match man is finished with his cigarette and collects them.

The problem is to simulate all four roles as software programs, using only
a certain set of synchronization primitives. In Patil's original
formulation, the only synchronization primitive allowed was the semaphore,
and none of the four programs were allowed to contain conditional jumps -
only the conditional waits implied by the semaphores' wait operations.