Concurrent programming

Lore & Background

Concurrent computing developed out of earlier work on railroads and telegraphy from the 19th and early 20th century, and some terms date to this period. Introduced in 1962, Petri nets were an early attempt to codify the rules of concurrent execution. Dataflow theory later built upon these, and Dataflow architectures were created to physically implement the ideas of dataflow theory. Beginning in the late 1970s, process calculi such as Calculus of Communicating Systems (CCS) and Communicating Sequential Processes (CSP) were developed to permit algebraic reasoning about systems composed of interacting components. The π-calculus added the capability for reasoning about dynamic topologies. Input/output automata were introduced in 1987. Logics such as Lamport's TLA+, and mathematical models such as traces and Actor event diagrams, have also been developed to describe the behavior of concurrent systems. Software transactional memory borrows from database theory the concept of atomic transactions and applies them to memory accesses.

Reader's Guide

Concurrent programming is significant because it enables modeling of processes that happen concurrently, such as multiple clients accessing a server at the same time, and structuring software systems as composed of multiple concurrent, communicating parts can be useful for tackling complexity. The main challenge in designing concurrent programs is concurrency control: ensuring correct sequencing of interactions and coordinating access to shared resources. Potential problems include race conditions, deadlocks, and resource starvation. Advantages include increased program throughput via parallel execution according to Gustafson's law, high responsiveness for input/output-intensive programs, and more appropriate program structure for certain problem domains. Concurrent programming languages and multiprocessor programs must have a consistency model, such as Leslie Lamport's sequential consistency model. Implementation methods include using operating system processes or threads. Communication between concurrent components can be via shared memory (requiring locking mechanisms like mutexes, semaphores, or monitors) or message passing (exemplified by MPI, Go, Scala, Erlang, and occam), with message-passing concurrency typically considered more robust and easier to reason about.

Did You Know?

• Concurrent computing is frequently confused with parallel computing, but in concurrent computing execution does not happen at the same instant, while in parallel computing execution occurs at the same physical instant.
• Concurrent processes can be executed on one core by interleaving execution steps via time-sharing slices, where only one process runs at a time.
• The main challenge in concurrent programming is concurrency control, which addresses race conditions, deadlocks, and resource starvation.
• One of the first consistency models was Leslie Lamport's sequential consistency model.