Cigarette smokers problem

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

Problem description

Assume a cigarette requires three ingredients to make and smoke: tobacco, paper, and matches. There are three 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 paper, and the third has matches.

There is also a non-smoking agent who enables the smokers to make their cigarettes by arbitrarily (non-deterministically) selecting two of the supplies to place on the table. The smoker who has the third supply should remove the two items from the table, using them (along with their own supply) to make a cigarette, which they smoke for a while. Once the smoker has finished his cigarette, the agent places two new random items on the table. This process continues forever.

Three semaphores are used to represent the items on the table; the agent increases the appropriate semaphore to signal that an item has been placed on the table, and smokers decrement the semaphore when removing items. Also, each smoker has an associated semaphore that they use to signal to the agent that they are done smoking; the agent has a process that waits on each smoker's semaphore to let it know that it can place the new items on the table.

A simple pseudocode implementation of the smoker who has the supply of tobacco might look like the following:

def tobacco_smoker():
    repeat:
        paper.wait()
        matches.wait()
        smoke()
        tobacco_smoker_done.signal()

However, this can lead to deadlock; if the agent places paper and tobacco on the table, the smoker with tobacco may remove the paper, leaving the smoker with matches unable to make their cigarette. The problem is to define additional processes and semaphores that prevent deadlock, without modifying the agent.

Argument

Patil placed the following constraints on the cigarette smokers problem:

1. The agent code is not modifiable.
2. The solution is not allowed to use conditional statements.

Patil used a proof in terms of Petri nets to claim that a solution to the cigarette smokers problem using Edsger Dijkstra's semaphore primitives is impossible, and to suggest that a more powerful primitive is necessary.^[1] However, David Parnas demonstrated that Patil's proof is inadequate if arrays of semaphore are used, offering a solution that uses helper processes that do arithmetic to signal the appropriate smoker to proceed.^[2]

According to Allen B. Downey, the first restriction makes sense, because if the agent represents an operating system, it would be unreasonable or impossible to modify it every time a new application came along.^[3] However, Parnas argues that the second restriction is unjustified:

The limitations reported by Patil are limitations of his primitives, but they are not limitations on the primitives described by Dijkstra. … 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.^[2]

References

1. Patil, Suhas S. (February 1971). Limitations and Capabilities of Dijkstra's Semaphore Primitives for Coordination among Processes (Technical report). MIT, Project MAC, Computation Structures Group. Memo 57.
2. Parnas, David L. (March 1975). "On a solution to the cigarette smokers' problem (without conditional statements)" (PDF). Communications of the ACM 18 (3): 181–183. doi:10.1145/360680.360709.
3. Downey, Allen B. The Little Book of Semaphores (2nd ed.). Retrieved 29 June 2015.