In computer science, concurrency is a property of systems in which several computations are
executing simultaneously, and potentially interacting with each other. The computations
may be executing on multiple cores in the same chip, preemptively time-shared threads
on the same processor, or executed on physically separated processors. A number of mathematical
models have been developed for general concurrent computation including Petri nets, process
calculi, the Parallel Random Access Machine model, the Actor model and the Reo Coordination
Language.
Issues Because computations 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 outcome can be indeterminate.
Concurrent use of shared resources can be a source of indeterminacy leading to issues
such as deadlock, and starvation. 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 maximize throughput.
Theory Concurrency theory has been an active field
of research in theoretical computer science. One of the first proposals was Carl Adam Petri's
seminal work on Petri Nets in the early 1960s. In the years since, a wide variety of formalisms
have been developed for modeling and reasoning about concurrency.
Models A number of formalisms for modeling and understanding
concurrent systems have been developed, including: The Parallel Random Access Machine
The Actor model Computational bridging models such as the
BSP model Petri nets
Process calculi CSP model
Tuple spaces, e.g., Linda SCOOP
Reo Coordination Language 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. Some of these are based on message passing, while others have different mechanisms
for concurrency. 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, while Nielsen, Sassone, and Winskel have demonstrated
that category theory can be used to provide a similar unified understanding of different
models. The Concurrency Representation Theorem in
the Actor model provides a fairly general way to represent concurrent systems that are
closed in the sense that they do not receive communications from outside. The mathematical
denotation denoted by a closed system S is constructed increasingly better approximations
from an initial behavior called ⊥S using a behavior approximating function progressionS
to construct a denotation for S as follows:
DenoteS ≡ ⊔i∈ω progressionSi(⊥S)
In this way, S can be mathematically characterized in terms of all its possible behaviors.
Logics Various types of temporal logic 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.
The principal application of these logics is in writing specifications for concurrent
systems. Practice
Concurrent programming encompasses 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 and Database management
systems are generally designed to operate indefinitely, including automatic recovery
from failure, 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. Because they use shared resources, concurrent
systems in general require the inclusion of some kind of arbiter somewhere in their implementation,
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.
Some concurrent programming models include coprocesses and deterministic concurrency.
In these models, threads of control explicitly yield their timeslices, either to the system
or to another process. See also
Client–server network nodes Cluster nodes
Concurrency control Concurrent computing
Concurrent object-oriented programming Concurrency pattern
Chu space Distributed systemnodes
Go Gordon Pask
OpenMP Parallel Computing
Partitioned global address space Processes
Ptolemy Project Sheaf
Threads X10
References
Further reading Lynch, Nancy A.. Distributed Algorithms. Morgan
Kauffman. ISBN 1-55860-348-4. Tanenbaum, Andrew S.; Van Steen, Maarten.
Distributed Systems: Principles and Paradigms. Prentice Hall. ISBN 0-13-088893-1.
Kurki-Suonio, Reino. A Practical Theory of Reactive Systems. Springer. ISBN 3-540-23342-3.
Garg, Vijay K.. Elements of Distributed Computing. Wiley-IEEE Press. ISBN 0-471-03600-5.
Magee, Jeff; Kramer, Jeff. Concurrency: State Models and Java Programming. Wiley. ISBN 0-470-09355-2.
External links Concurrent Systems at The WWW Virtual Library