Cigarette smokers problem

This article is about the computer science problem. For problems that may affect cigarette smokers, see Health effects of tobacco.

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

Problem description

Assume a cigarette requires three ingredients to smoke:

1. Tobacco
2. Smoking 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 arbitrarily (non deterministically) selecting two of the smokers, 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 her own supply) to make a cigarette, which she 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 or she is finished smoking the last one. If the arbiter places tobacco and paper on the table while the match-supply smoker is smoking, the tobacco and paper will remain untouched on the table until the match-supply smoker is finished with her cigarette and collects them.

How A Problem Develops From The Initial Conditions and Assumptions

There, finally she is done. The gentleman to her left, is the smoker in charge of the

infinite supply of tobacco.  He saw the arbiter place tobacco and paper on the 
table.  No cigarette in his immediate future then.  He shrugs.  Glances to his
 left and across the table.  There, the gentleman who nominatively has an 
 infinite supply of papers for rolling smokes, sits bemused, admiring the l
 ady in the red dress as she finishes her cigarette.

Now they watch her roll another cigarette, and light it up. She was able to have another cigarette because the arbiter had you will recall, placed tobacco and paper on the table, during the time she was enjoying her previous cigarette.

Soon after she uses an item from her infinite supply of matches, although she 
could just as well simply light her smoke by bringing it near her red dress, 
yes, she is that hot, the arbiter places from her match-supply, a match on
 the table then adds a cigarette-rolling-paper from the supply of the 
 fellow to her right.

The arbiter and the two waiting gentlemen may or not make small talk as they wait for her to smoke her current cigarette and as she finishes up, the gentleman to her left takes his turn, using the paper he can access, placed there on the table in front of them, and the match the arbiter placed in the middle of the table as well, and the smoker uses from his supply of tobacco, an amount he is comfortable with and rolls a nice cigarette and begins to smoke it.

Now, you may ask, okay, so other than the admirable patience of all these smokers and the valient and one hopes entirely altruistic efforts of the arbiter in attending this most strange session of smoking for the good of computer science furtherance, what else is there to see?

The smokers continue smoking and the PROBLEM lurks in the shadows never to be stated, named; never to be fleshed out nor described, all because God Forbid somebody somewhere asks a question and that question remain in

plain view, in the light of day.

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 unreasonable or impossible 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.

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

time.sleep(T)
# choose smokers i and j nondeterministically,
# making the third smoker k
signal(A[k])

and the code for smoker i is

while true:
    time.sleep(A[i])
    # make a cigarette
    signal(T)
    # smoke the cigarette

References

• Modern Operating Systems (2nd Edition), by Andrew S. Tanenbaum (ISBN 0-13-031358-0)
• The Little Book of Semaphores, by Allen B. Downey, http://greenteapress.com/semaphores
• On a solution to the cigarette smokers' problem without conditional statements, by David Parnas, Communications of the ACM, 18:181-183, March 1975
• Limitations and capabilities of Dijkstra's semaphore primitives for coordination among processes, by Suhas Patil, technical report, MIT, 1971