Cigarette smokers problem

From Wikipedia, the free encyclopedia

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

Contents

[edit] Problem description

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 at random (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.

[edit] Argument

Patil's argument was that Edsger Dijkstra's semaphore primitives were limited. He used the cigarette smokers problem to illustrate this point by saying that it cannot be solved with semaphores. However, Patil placed heavy constraints on his argument:

  1. The agent code is not modifiable.
  2. The solution is not allowed to use conditional statements or an array of semaphores.

With these two constraints, a solution to the cigarette smokers problem is impossible.

The first restriction makes sense, as Downey says in The Little Book of Semaphores, because if the agent represents an operating system, it would be intractable to modify it every time a new application came along. However, as David Parnas points out, the second restriction makes almost any nontrivial problem impossible to solve:

It is important, however, that such an investigation [of Dijkstra primitives] not investigate the power of these primitives under artificial restrictions. By artificial we mean restrictions which cannot be justified by practical considerations. In this author's opinion, restrictions prohibiting either conditionals or semaphore arrays are artificial. On the other hand, prohibition of "busy waiting" is quite realistic.

[edit] Solution

If we remove the second of Patil's constraints, the cigarette smokers problem becomes solvable using binary semaphores, or mutexes. Let us define an array of binary semaphores A, one for each smoker; and a binary semaphore for the table, T. Initialize the smokers' semaphores to zero and the table's semaphore to 1. Then the arbiter's code is

while true {
    wait(T);
    choose smokers i and j nondeterministically
    , making the third smoker k
    signal(A[k]);
}

and the code for smoker i is

while true {
    wait(A[i]);
    make a cigarette
    signal(T);
    smoke the cigarette
}

[edit] References

[edit] See also

A solution using C & POSIX threads

Languages