Cigarette smokers problem
Encyclopedia
The cigarette smokers problem is a concurrency problem in computer science
, originally described in 1971 by S. S. Patil
.
requires three ingredients to smoke:
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
(nondeterministically) 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 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.
'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:
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:
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
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, originally described in 1971 by S. S. Patil
Suhas Patil
Dr. Suhas S. Patil, born 1944 in Jamshedpur, Jharkhand, India, is a Silicon Valley entrepreneur, venture capitalist and philanthropist. He founded the company Cirrus Logic a fabless semiconductor company....
.
Problem description
Assume a cigaretteCigarette
A cigarette is a small roll of finely cut tobacco leaves wrapped in a cylinder of thin paper for smoking. The cigarette is ignited at one end and allowed to smoulder; its smoke is inhaled from the other end, which is held in or to the mouth and in some cases a cigarette holder may be used as well...
requires three ingredients to smoke:
- TobaccoTobaccoTobacco is an agricultural product processed from the leaves of plants in the genus Nicotiana. It can be consumed, used as a pesticide and, in the form of nicotine tartrate, used in some medicines...
- PaperPaperPaper is a thin material mainly used for writing upon, printing upon, drawing or for packaging. It is produced by pressing together moist fibers, typically cellulose pulp derived from wood, rags or grasses, and drying them into flexible sheets....
- A matchMatchA match is a tool for starting a fire under controlled conditions. A typical modern match is made of a small wooden stick or stiff paper. One end is coated with a material that can be ignited by frictional heat generated by striking the match against a suitable surface...
Assume there are also three chain smokers
Chain smoking
Chain smoking is the practice of lighting a new cigarette for personal consumption immediately after one that is finished, sometimes using the finished cigarette to light the next one. It is a common form of addiction.-Causes:...
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
Arbitrary
Arbitrariness is a term given to choices and actions subject to individual will, judgment or preference, based solely upon an individual's opinion or discretion.Arbitrary decisions are not necessarily the same as random decisions...
(nondeterministically) 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 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.
Argument
PatilSuhas Patil
Dr. Suhas S. Patil, born 1944 in Jamshedpur, Jharkhand, India, is a Silicon Valley entrepreneur, venture capitalist and philanthropist. He founded the company Cirrus Logic a fabless semiconductor company....
's argument was that Edsger Dijkstra
Edsger Dijkstra
Edsger Wybe Dijkstra ; ) was a Dutch computer scientist. He received the 1972 Turing Award for fundamental contributions to developing programming languages, and was the Schlumberger Centennial Chair of Computer Sciences at The University of Texas at Austin from 1984 until 2000.Shortly before his...
's semaphore
Semaphore (programming)
In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment....
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:
- The agent code is not modifiable.
- 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
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
, it would be unreasonable or impossible to modify it every time a new application came along. However, as David Parnas
David Parnas
David Lorge Parnas is a Canadian early pioneer of software engineering, who developed the concept of information hiding in modular programming, which is an important element of object-oriented programming today. He is also noted for his advocacy of precise documentation.- Biography :Parnas earned...
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 waitingBusy waitingIn software engineering, busy-waiting or spinning is a technique in which a process repeatedly checks to see if a condition is true, such as whether keyboard input is available, or if a lock is available. Spinning can also be used to generate an arbitrary time delay, a technique that was necessary...
" 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 istime
Semaphore (programming)
In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment....
.sleep
Semaphore (programming)
In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment....
(T)
# choose smokers i and j nondeterministically,
# making the third smoker k
signal
Semaphore (programming)
In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment....
(A[k])
and the code for smoker i is
while true:
time
Semaphore (programming)
In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment....
.sleep
Semaphore (programming)
In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment....
(A[i])
# make a cigarette
signal
Semaphore (programming)
In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment....
(T)
# smoke the cigarette