Cigarette Smokers Problem
   HOME





Cigarette Smokers Problem
The cigarette smokers problem is a classic concurrency problem in computer science, introduced by Suhas Patil in 1971. It illustrates synchronization challenges in multi-process systems, where multiple processes (smokers) compete for limited resources (ingredients) provided by a single agent. The problem is notable for its constraints, such as the immutability of the agent's behavior and the prohibition of conditional statements in solutions, which have been subjects of criticism. Problem description Patil's problem includes a "quite arbitrary" "restriction that the process which supplies the ingredients cannot be changed and that no conditional statements may be used." 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. Ther ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Concurrency (computer Science)
Concurrency refers to the ability of a system to execute multiple tasks through simultaneous execution or time-sharing (context switching), sharing resources and managing interactions. Concurrency improves responsiveness, throughput, and scalability in modern computing, including: * Operating systems and embedded systems * Distributed systems, parallel computing, and high-performance computing * Database systems, web applications, and cloud computing Related concepts Concurrency is a broader concept that encompasses several related ideas, including: * Parallelism (simultaneous execution on multiple processing units). Parallelism executes tasks independently on multiple CPU cores. Concurrency allows for multiple ''threads of control'' at the program level, which can use parallelism or time-slicing to perform these tasks. Programs may exhibit parallelism only, concurrency only, both parallelism and concurrency, neither. * Multi-threading and multi-processing (shared ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Project MAC
Computer Science and Artificial Intelligence Laboratory (CSAIL) is a research institute at the Massachusetts Institute of Technology The Massachusetts Institute of Technology (MIT) is a Private university, private research university in Cambridge, Massachusetts, United States. Established in 1861, MIT has played a significant role in the development of many areas of moder ... (MIT) formed by the 2003 merger of the Laboratory for Computer Science (LCS) and the Artificial Intelligence Laboratory (AI Lab). Housed within the Ray and Maria Stata Center, CSAIL is the largest on-campus laboratory as measured by research scope and membership. It is part of the Schwarzman College of Computing but is also overseen by the MIT Vice President of Research. Research activities CSAIL's research activities are organized around a number of semi-autonomous research groups, each of which is headed by one or more professors or research scientists. These groups are divided up into seven gene ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Sleeping Barbers Problem
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. The problem was originally proposed in 1965 by computer science pioneer Edsger Dijkstra, who used it to make the point that general semaphores are often superfluous. Problem statement Imagine a hypothetical barbershop with one barber, one barber chair, and a waiting room with ''n'' chairs (''n'' may be 0) for waiting customers. The following rules apply: * If there are no customers, the barber falls asleep in the chair * A customer must wake the barber if he is asleep * If a customer arrives while the barber is working, the customer leaves if all chairs are occupied and sits in an empty chair if it's available * When the barber finishes a haircut, he inspects the waiting room to see if there are any waiting customers and falls asleep if there are none There are two ma ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Readers–writers Problem
In computer science, the readers–writers problems are examples of a common computing problem in concurrency. There are at least three variations of the problems, which deal with situations in which many concurrent threads of execution try to access the same shared resource at one time. Some threads may read and some may write, with the constraint that no thread may access the shared resource for either reading or writing while another thread is in the act of writing to it. (In particular, we want to prevent more than one thread modifying the shared resource simultaneously and allow for two or more readers to access the shared resource at the same time). A readers–writer lock is a data structure that solves one or more of the readers–writers problems. The basic reader–writers problem was first formulated and solved by Courtois ''et al.'' First readers–writers problem Suppose we have a shared memory area (critical section) with the basic constraints detailed above. It i ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Dining Philosophers Problem
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. It was originally formulated in 1965 by Edsger Dijkstra as a student exam exercise, presented in terms of computers competing for access to tape drive peripherals. Soon after, Tony Hoare gave the problem its present form. Problem statement Five philosophers dine together at the same table. Each philosopher has their own plate at the table. There is a fork between each plate. The dish served is a kind of spaghetti which has to be eaten with two forks. Each philosopher can only alternately think and eat. Moreover, a philosopher can only eat their spaghetti when they have both a left and right fork. Thus two forks will only be available when their two nearest neighbors are thinking, not eating. After an individual philosopher finishes eating, they will put down both forks. The problem is how to ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Operating System
An operating system (OS) is system software that manages computer hardware and software resources, and provides common daemon (computing), services for computer programs. Time-sharing operating systems scheduler (computing), schedule tasks for efficient use of the system and may also include accounting software for cost allocation of Scheduling (computing), processor time, mass storage, peripherals, and other resources. For hardware functions such as input and output and memory allocation, the operating system acts as an intermediary between programs and the computer hardware, although the application code is usually executed directly by the hardware and frequently makes system calls to an OS function or is interrupted by it. Operating systems are found on many devices that contain a computerfrom cellular phones and video game consoles to web servers and supercomputers. , Android (operating system), Android is the most popular operating system with a 46% market share, followed ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  




Allen B
Allen, Allen's or Allens may refer to: Buildings * Allen Arena, an indoor arena at Lipscomb University in Nashville, Tennessee * Allen Center, a skyscraper complex in downtown Houston, Texas * Allen Fieldhouse, an indoor sports arena on the University of Kansas campus in Lawrence * Allen House (other) * Allen Power Plant (other) Businesses *Allen (brand), an American tool company *Allen's, an Australian brand of confectionery *Allens (law firm), an Australian law firm formerly known as Allens Arthur Robinson *Allen's (restaurant), a former hamburger joint and nightclub in Athens, Georgia, United States *Allen & Company LLC, a small, privately held investment bank * Allens of Mayfair, a butcher shop in London from 1830 to 2015 * Allens Boots, a retail store in Austin, Texas * Allens, Inc., a brand of canned vegetables based in Arkansas, US, now owned by Del Monte Foods * Allen's department store, a.k.a. Allen's, George Allen, Inc., Philadelphia, USA People * Alle ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


David Parnas
David Lorge Parnas (born February 10, 1941) 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. Life Parnas earned his PhD at Carnegie Mellon University in electrical engineering. Parnas also earned a professional engineering license in Canada and was one of the first to apply traditional engineering principles to software design. He worked there as a professor for many years. He also taught at the University of North Carolina at Chapel Hill (U.S.), at the Department of Computer Science of the Technische Universität Darmstadt (Germany), the University of Victoria (British Columbia, Canada), Queen's University in Kingston, Ontario, McMaster University in Hamilton, Ontario, and University of Limerick (Ireland). David Parnas received a number of awards and honors: * ACM "Best ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Massachusetts Institute Of Technology
The Massachusetts Institute of Technology (MIT) is a Private university, private research university in Cambridge, Massachusetts, United States. Established in 1861, MIT has played a significant role in the development of many areas of modern technology and science. In response to the increasing Technological and industrial history of the United States, industrialization of the United States, William Barton Rogers organized a school in Boston to create "useful knowledge." Initially funded by a land-grant universities, federal land grant, the institute adopted a Polytechnic, polytechnic model that stressed laboratory instruction in applied science and engineering. MIT moved from Boston to Cambridge in 1916 and grew rapidly through collaboration with private industry, military branches, and new federal basic research agencies, the formation of which was influenced by MIT faculty like Vannevar Bush. In the late twentieth century, MIT became a leading center for research in compu ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Suhas Patil
Suhas S. Patil (born 1944) 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. Early life and education Patil grew up in Jamshedpur, India. His father was the first person in the family to go to a university and get an engineering degree and worked at Tata Steel while Patil was growing up. Patil went to study intermediate science at St. Xavier's College, Kolkata and then to the Indian Institute of Technology Kharagpur for his bachelor's degree in electrical engineering. He attended the Massachusetts Institute of Technology for his masters an ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Edsger Dijkstra
Edsger Wybe Dijkstra ( ; ; 11 May 1930 – 6 August 2002) was a Dutch computer scientist, programmer, software engineer, mathematician, and science essayist. Born in Rotterdam in the Netherlands, Dijkstra studied mathematics and physics and then theoretical physics at the University of Leiden. Adriaan van Wijngaarden offered him a job as the first computer programmer in the Netherlands at the Mathematical Centre in Amsterdam, where he worked from 1952 until 1962. He formulated and solved the shortest path problem in 1956, and in 1960 developed the first compiler for the programming language ALGOL 60 in conjunction with colleague Jaap A. Zonneveld. In 1962 he moved to Eindhoven, and later to Nuenen, where he became a professor in the Mathematics Department at the Technische Hogeschool Eindhoven. In the late 1960s he built the THE multiprogramming system, which influenced the designs of subsequent systems through its use of software-based paged virtual memory. Dijkstra joined ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Petri Net
A Petri net, also known as a place/transition net (PT net), is one of several mathematical modeling languages for the description of distributed systems. It is a class of discrete event dynamic system. A Petri net is a directed bipartite graph that has two types of elements: places and transitions. Place elements are depicted as white circles and transition elements are depicted as rectangles. A place can contain any number of tokens, depicted as black circles. A transition is enabled if all places connected to it as inputs contain at least one token. Some sources state that Petri nets were invented in August 1939 by Carl Adam Petri — at the age of 13 — for the purpose of describing chemical processes. Like industry standards such as UML activity diagrams, Business Process Model and Notation, and event-driven process chains, Petri nets offer a graphical notation for stepwise processes that include choice, iteration, and concurrent execution. Unlike these standards, Pet ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]