 |
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]
| |
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]
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:
deftobacco_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.
Patil placed the following constraints on the cigarette smokers problem:
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]
A cigarette is a narrow cylinder containing a combustible material, typically tobacco, that is rolled into thin paper for smoking. The cigarette is ignited at one end, causing it to smolder; the resulting smoke is orally inhaled via the opposite end. Cigarette smoking is the most common method of tobacco consumption. The term cigarette, as commonly used, refers to a tobacco cigarette, but the word is sometimes used to refer to other substances, such as a cannabis cigarette or an herbal cigarette. A cigarette is distinguished from a cigar by its usually smaller size, use of processed leaf, and paper wrapping, which is typically white. Since the 1920s, cigarettes have been a major source of advertising revenue for the media, of traffic for small stores, and of tax revenue for governments.
Tobacco smoking is the practice of burning tobacco and ingesting the resulting smoke. The smoke may be inhaled, as is done with cigarettes, or simply released from the mouth, as is generally done with pipes and cigars. The practice is believed to have begun as early as 5000–3000 BC in Mesoamerica and South America. Tobacco was introduced to Eurasia in the late 17th century by European colonists, where it followed common trade routes. The practice encountered criticism from its first import into the Western world onwards but embedded itself in certain strata of a number of societies before becoming widespread upon the introduction of automated cigarette-rolling apparatus.
In computer science, a semaphore is a variable or abstract data type used to control access to a common resource by multiple threads and avoid critical section problems in a concurrent system such as a multitasking operating system. Semaphores are a type of synchronization primitive. A trivial semaphore is a plain variable that is changed depending on programmer-defined conditions.
In computer science, the dining philosophers problem is an example problem often used in concurrent algorithm design to illustrate synchronization issues and techniques for resolving them.
In computer science, the sleeping barber problem is a classic inter-process communication and synchronization problem that illustrates the complexities that arise when there are multiple operating system processes.
Smoking bans, or smoke-free laws, are public policies, including criminal laws and occupational safety and health regulations, that prohibit tobacco smoking in certain spaces. The spaces most commonly affected by smoking bans are indoor workplaces and buildings open to the public such as restaurants, bars, office buildings, schools, retail stores, hospitals, libraries, transport facilities, and government buildings, in addition to public transport vehicles such as aircraft, buses, watercraft, and trains. However, laws may also prohibit smoking in outdoor areas such as parks, beaches, pedestrian plazas, college and hospital campuses, and within a certain distance from the entrance to a building, and in some cases, private vehicles and multi-unit residences.
Rolling paper is a specialty paper used for making cigarettes. Rolling papers are packs of several cigarette-size sheets, often folded inside a cardboard wrapper. They are also known as 'blanks', which are used to encase tobacco or cannabis. It may be flavoured.
Kretek are unfiltered cigarettes of Indonesian origin, made with a blend of tobacco, cloves, and other flavors. The word "kretek" itself is an onomatopoetic term for the crackling sound of burning cloves.
Suhas S. Patil is an Indian-American entrepreneur, academic, and venture capitalist. He founded Cirrus Logic, a fabless semiconductor company. Patil's work has covered computer architecture, parallel processing computers, very-large-scale integration devices, and integrated circuit design automation software. He also serves on the boards of The Tech Museum and the World Affairs Council of Northern California. He is known for describing the "cigarette smokers problem" for concurrent computing in 1971.
Tobacco products, especially when smoked or used orally, have negative effects on human health, and concerns about these effects have existed for a long time. Research has focused primarily on cigarette smoking.
A cigarette filter, also known as a filter tip, is a component of a cigarette, along with cigarette paper, capsules and adhesives. Filters were introduced in the early 1950s.
Prevalence of tobacco use is reported by the World Health Organization (WHO), which focuses on cigarette smoking due to reported data limitations. Smoking has therefore been studied more extensively than any other form of consumption.
Smoking is a practice in which a substance is combusted and the resulting smoke is typically inhaled to be tasted and absorbed into the bloodstream of a person. Most commonly, the substance used is the dried leaves of the tobacco plant, which have been rolled with a small rectangle of paper into an elongated cylinder called a cigarette. Other forms of smoking include the use of a smoking pipe or a bong.
The use of tobacco for smoking in New Zealand has been subjected to government regulation for a number of decades. On 10 December 2004, New Zealand became the third country in the world to make all indoor workplaces including bars and restaurants smoke-free.
Tobacco control is a field of international public health science, policy and practice dedicated to addressing tobacco use and thereby reducing the morbidity and mortality it causes. Since most cigarettes and cigars and hookahs contain/use tobacco, tobacco control also concerns these. E-cigarettes do not contain tobacco itself, but (often) do contain nicotine. Tobacco control is a priority area for the World Health Organization (WHO), through the Framework Convention on Tobacco Control. References to a tobacco control movement may have either positive or negative connotations, depending upon the commentator.
The Family Smoking Prevention and Tobacco Control Act, is a federal statute in the United States that was signed into law by President Barack Obama on June 22, 2009. The Act gives the Food and Drug Administration the power to regulate the tobacco industry. A signature element of the law imposes new warnings and labels on tobacco packaging and their advertisements, with the goal of discouraging minors and young adults from smoking. The Act also bans flavored cigarettes, places limits on the advertising of tobacco products to minors and requires tobacco companies to seek FDA approval for new tobacco products.
Tobacco marketing targeting African-Americans refers to the practice of customizing tobacco products and advertising techniques specifically to African-American consumers. It is most commonly analyzed through the consumption of mentholated cigarettes, as it represents 47% of black adult smokers and 84% of adolescent black smokers.
Smoking in Syria is steadily increasing in popularity amongst the Syrian population, mainly in the forms of cigarettes or narghiles. In Syria, the General Organization of Tobacco manages the growth and exportation of tobacco products. Syrians collectively spend about $600 million per year on tobacco consumption. As of 2010, 20% of women and 60% of men smoke and 98% of the overall population is affected by passive smoking. Narghiles and cigarettes are the two main forms of tobacco consumption. Despite the assumption that smoking, specifically the narghile, is embedded in Syrian culture, this phenomenon has only recently become widespread. Health officials are currently working on smoking cessation programs and policies, to remove this idea that smoking in Syria is an essential part of the culture, to educate regarding health effects, and to prevent citizens from smoking in public places.
Animals are exposed to tobacco smoke and other cigarette by-products through their use as experimental subjects and through contact with smokers, as in the case of pets in houses where smoking takes place.
Tobacco smoking is popular in North Korea and culturally acceptable among men, but not for women. As of 2014, some 45% of men are reported to smoke daily, whilst in contrast only 2.5% of women smoke daily, with most of these being older women from rural areas. Smoking is a leading cause of death in North Korea, and as of 2010 mortality figures indicate that 34% of men and 22% of women die due to smoking-related causes, the highest mortality figures in the world. There are tobacco control programs in North Korea, and although smoking was not prohibited in all public spaces, the smoking rates have declined since their peak in the 2000s.
| General | |
|---|---|
| Process calculi | |
| Classic problems | |
