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 Suhas Patil. The problem has been criticized for having "restrictions which cannot be justified by practical considerations."^[1]

Problem description

Patil's problem includes a "quite arbitrary"^[1] "restriction that the process which supplies the ingredients cannot be changed and that no conditional statements may be used."^[2]

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 the particular smoker is done smoking; the agent has a process that waits on each smoker's semaphore to let the agent 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 and the smoker with matches may take the tobacco, leaving both unable to make their cigarette. The solution is to define additional processes and semaphores that prevent deadlock, without modifying the agent.

Criticism

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.^[3][2] However, David Parnas demonstrated that Patil's proof is inadequate if arrays of semaphores are used, offering a solution that uses helper processes that do arithmetic to signal the appropriate smoker to proceed.^[1]

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.^[4] 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.^[1]

See also

• Dining philosophers problem
• Readers–writers problem
• Sleeping barbers problem

References

1. 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. S2CID 24066507.
2. Patil, Suhas. "Limitations and Capabilities of Dijkstra's Semaphore Primitives for Coordination among Processes" (PDF). Retrieved 20 February 2022.
3. 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.
4. Downey, Allen B. The Little Book of Semaphores (2nd ed.). Retrieved 29 June 2015.