The "Dining Philosophers", a classic problem involving concurrency and shared resources

In computer science, concurrency is a property of systems in which several computational processes are executing at the same time, and potentially interacting with each other.^[1] The study of concurrency encompasses a broad range of systems, from tightly-coupled, largely synchronous parallel computing systems, to loosely-coupled, largely asynchronous distributed systems.^[2] The concurrent processes may be executing truly simultaneously, in the case that they run on separate processors, or their execution steps may be interleaved to produce the appearance of concurrency, as in the case of separate processes running on a multitasking system. Because the processes in a concurrent system can interact with each other while they are executing, the number of possible execution paths in the system can be extremely large, and the resulting behavior can be very complex. The difficulties associated with concurrency have been tackled both through the construction of languages and concepts to make the complexity of concurrent execution manageable, and through the development of theories for reasoning about interacting concurrent processes.^[1] Download high resolution version (1130x1172, 1362 KB) Wikipedia does not have an article with this exact name. ... Download high resolution version (1130x1172, 1362 KB) Wikipedia does not have an article with this exact name. ... In computer science, the dining philosophers problem is an illustrative example of a common computing problem in concurrency. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... Look up computation in Wiktionary, the free dictionary. ... Parallel computing is the simultaneous execution of the same task (split up and specially adapted) on multiple processors in order to obtain results faster. ... This article or section should be merged with Distributed computing In computer science, a distributed system is an application that consists of components running on different computers concurrently. ... In computing, multitasking is a method by which multiple tasks, also known as processes, share common processing resources such as a CPU. In the case of a computer with a single CPU, only one task is said to be running at any point in time, meaning that the CPU is...

Issues

The difference between a sequential system and a concurrent system is the fact that the processes which make up a concurrent system can interact with each other.^[1] Concurrent use of shared resources is the source of many difficulties. Race conditions involving shared resources can result in unpredictable system behavior. The introduction of mutual exclusion can prevent race conditions, but can lead to problems such as deadlock, and starvation.^[2] A resource, also referred to as system resource, is any physical or virtual system component of a computer system with limited availability. ... A race condition or race hazard is a flaw in a system or process whereby the output of the process is unexpectedly and critically dependent on the sequence or timing of other events. ... Mutual exclusion (often abbreviated to mutex) algorithms are used in concurrent programming to avoid the simultaneous use of un-shareable resources by pieces of computer code called critical sections. ... It has been suggested that Circular wait be merged into this article or section. ... In computer science, starvation is a multitasking-related problem, where a process is perpetually denied necessary resources. ...

In addition to internal interactions, many concurrent systems, such as operating systems and databases, are intended to participate in an ongoing interaction with users, and with other systems. Traditional notions of program correctness, which are based on relating an initial input to the output expected to appear at program termination, are not really applicable. Alternative ways of defining what it means for the operation of a concurrent system to be correct are required.^[2] // An operating system (OS) is a set of computer programs that manage the hardware and software resources of a computer. ... This article does not cite any references or sources. ...

The design of concurrent systems often entails finding reliable techniques for coordinating their execution, data exchange, memory allocation, and execution scheduling to minimize response time and maximise throughput.^{[citation needed]}

Theory

Concurrency theory has been an active field of research in theoretical computer science since Carl Adam Petri's seminal work on Petri Nets in the early 1960s.^[3] In the years since, a wide variety of formalisms have been developed for modeling and reasoning about concurrency. Computer science (informally, CS or compsci) is, in its most general sense, the study of computation and information processing, both in hardware and in software. ... Carl Adam Petri is a honorary professor at the University of Hamburg. ... A Petri net is a mathematical representation of discrete distributed systems. ... The 1960s decade refers to the years from January 1, 1960 to December 31, 1969, inclusive. ...

Models

A number of formalisms for modeling and understanding concurrent systems have been developed, including:^[4]

• The Parallel Random Access Machine^{[citation needed]}
• The Actor model
• Petri nets
• Process calculi
• Tuple spaces^{[citation needed]}

Some of these models of concurrency are primarily intended to support reasoning and specification, while others can be used through the entire development cycle, including design, implementation, proof, testing and simulation of concurrent systems. PRAM stands for Parallel Random Access Machine, which is an abstract machine for designing the algorithms applicable to parallel computers. ... In computer science, the Actor model is a mathematical model of concurrent computation that treats actors as the universal primitives of concurrent digital computation: in response to a message that it receives, an actor can make local decisions, create more actors, send more messages, and determine how to respond to... A Petri net is a mathematical representation of discrete distributed systems. ... The process calculi (or process algebras) are a diverse family of related approaches to formally modelling concurrent systems. ... To meet Wikipedias quality standards, this article or section may require cleanup. ...

The proliferation of different models of concurrency has motivated some researchers to develop ways to unify these different theoretical models. For example, Lee and Sangiovanni-Vincentelli have demonstrated that a so-called "tagged-signal" model can be used to provide a common framework for defining the denotational semantics of a variety of different models of concurrency,^[5] while Nielsen, Sassone, and Winskel have demonstrated that category theory can be used to provide a similar unified understanding of different models.^[6] In computer science, denotational semantics is an approach to formalizing the semantics of computer systems by constructing mathematical objects (called denotations or meanings) which express the semantics of these systems. ... In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them. ...

Logics

Various types of temporal logic^[7] can be used to help reason about concurrent systems. Some of these logics, such as linear temporal logic and computational tree logic, allow assertions to be made about the sequences of states that a concurrent system can pass through. Others, such as action computational tree logic, Hennessy-Milner logic, and Lamport's temporal logic of actions, build their assertions from sequences of actions (changes in state). The principal application of these logics is in writing specifications for concurrent systems.^[2] In logic, the term temporal logic is used to describe any system of rules and symbolism for representing, and reasoning about, propositions qualified in terms of time. ... Linear temporal logic (LTL) is a modal temporal logic with modalities referring to time. ... Computational tree logic (CTL) is a branching-time logic, meaning that its model of time is a tree-like structure in which the future is not determined; there are different paths in the future, any one of which might be actual path that is realised. ... Leslie Lamport Dr. Leslie Lamport (born 1941) is an American computer scientist. ... A logic developed by Leslie Lamport, which combines Temporal Logic with a logic of actions. ...

Practice

Concurrent programming encompasses the programming languages and algorithms used to implement concurrent systems. Concurrent programming is usually considered to be more general than parallel programming because it can involve arbitrary and dynamic patterns of communication and interaction, whereas parallel systems generally have a predefined and well-structured communications pattern. The base goals of concurrent programming include correctness, performance and robustness. Concurrent systems such as operating systems are generally designed to operate indefinitely and not terminate unexpectedly. Some concurrent systems implement a form of transparent concurrency, in which concurrent computational entities may compete for and share a single resource, but the complexities of this competition and sharing are shielded from the programmer. Parallel programming (also concurrent programming), is a computer programming technique that provides for the execution of operations concurrently, either within a single computer, or across a number of systems. ... Parallel programming is a computer programming technique that provides for the execution of operations in parallel, either within a single computer, or across a number of systems. ... In human-computer interaction, computer transparency is an aspect of user friendliness which prevents the user from worrying about technical details (like installation, updating, downloading or device drivers). ...

Because they use shared resources, concurrent systems in general require the inclusion of some kind of arbiter somewhere in their implementation (often in the underlying hardware), to control access to those resources. The use of arbiters introduces the possibility of indeterminacy in concurrent computation which has major implications for practice including correctness and performance. For example arbitration introduces unbounded nondeterminism which raises issues with model checking because it causes explosion in the state space and can even cause models to have an infinite number of states. Arbiters are used in asynchronous circuits to order computational activities for shared resources to preventing concurrent incorrect operations. ... Indeterminacy in computation is concerned with the effects of indeterminacy in concurrent computation. ... In computer science, unbounded nondeterminism (sometimes called unbounded indeterminacy) is a property of concurrency by which the amount of delay in servicing a request can become unbounded as a result of arbitration of contention for shared resources while still guaranteeing that the request will eventually be serviced. ... Model checking is the process of checking whether a given model satisfies a given logical formula. ...

See also

• Client-server network nodes
• Cluster nodes
• Concurrency control
• Concurrent computing
• Concurrency pattern
• Distributed system nodes
• OpenMP
• Processes
• Ptolemy Project
• Threads

Client/Server is a network application architecture which separates the client (usually the graphical user interface) from the server. ... Linux Cluster at Purdue University A computer cluster is a group of locally connected computers that work together as a unit. ... In computer science -- more specifically, in the field of databases -- concurrency control is a method used to ensure that database transactions are executed in a safe manner (i. ... Concurrent computing is the concurrent (simultaneous) execution of multiple interacting computational tasks. ... In software engineering, concurrency patterns are one of the types of design patterns. ... Distributed computing is a method of computer processing in which different parts of a program run simultaneously on two or more computers that are communicating with each other over a network. ... OpenMP logo The OpenMP (Open Multi-Processing) is an application programming interface (API) that supports multi-platform shared memory multiprocessing programming in C/C++ and Fortran on many architectures, including Unix and Microsoft Windows platforms. ... In computing, a process is an instance of a computer program that is being executed. ... To meet Wikipedias quality standards, this article or section may require cleanup. ... For the form of code consisting entirely of subroutine calls, see Threaded code. ...

References

A. William Roscoe (Bill Roscoe) is director of the Computing Laboratory at the University of Oxford and a Professor of Computing Science. ... Pearson can mean Pearson PLC the media conglomerate. ... shelby was here 2004 (MMIV) was a leap year starting on Thursday of the Gregorian calendar. ... IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, often abbreviated IEEE TCAD or IEEE Transactions on CAD, is a technical journal devoted to the design, analysis, and use of computer programs that aid in the design of integrated circuits and systems. ...

Further reading

• Lynch, Nancy A. (1996). Distributed Algorithms. Morgan Kauffman. ISBN 1558603484. 
• Tanenbaum, Andrew S.; Van Steen, Maarten (2002). Distributed Systems: Principles and Paradigms. Prentice Hall. ISBN 0-13-088893-1. 
• Kurki-Suoni, Reino (2005). A Practical Theory of Reactive Systems. Springer. ISBN 3-540-23342-3. 

External links

• Concurrent Systems at The WWW Virtual Library