Concurrent computing: Difference between revisions

Revision as of 11:05, 12 November 2023

Latest revision as of 06:48, 3 August 2025

(20 intermediate revisions by 15 users not shown)

Line 2:

{{for multi|the American computer company|Concurrent Computer Corporation|a more theoretical discussion|Concurrency (computer science)}}

{{more citations needed|date=February 2014}}

{{Programming paradigms}}

'''Concurrent computing''' is a form of [[computing]] in which several [[computation]]s are executed ''[[Concurrency (computer science)|concurrently]]''—during overlapping time periods—instead of ''sequentially—''with one completing before the next starts.

Line 20 ⟶ 19:

|title=Parallelism vs. Concurrency

|work=Haskell Wiki

}}</ref> although both can be described as "multiple processes executing ''during the same period of time''". In parallel computing, execution occurs at the same physical instant: for example, on separate [[central processing unit|processors]] of a [[multi-processor]] machine, with the goal of speeding up computations—parallel computing is impossible on a ([[Multi-core processor|one-core]]) single processor, as only one computation can occur at any instant (during any single clock cycle).{{efn|This is discounting parallelism internal to a processor core, such as pipelining or vectorized instructions. A one-core, one-processor ''machine'' may be capable of some parallelism, such as with a [[coprocessor]], but the processor alone is not.}} By contrast, concurrent computing consists of process ''lifetimes'' overlapping, but execution needdoes not happen at the same instant. The goal here is to model processes in the outside world that happen concurrently, such aslike multiple clients accessing a server at the same time. Structuring software systems as composed of multiple concurrent, communicating parts can be useful for tackling complexity, regardless of whether the parts can be executed in parallel.<ref>{{cite book |last=Schneider |first=Fred B. |url=https://archive.org/details/onconcurrentprog0000schn |title=On Concurrent Programming |date=1997-05-06 |publisher=Springer |isbn=9780387949420 |url-access=registration}}</ref>{{rp|1}}

For example, concurrent processes can be executed on one core by interleaving the execution steps of each process via [[time-sharing]] slices: only one process runs at a time, and if it does not complete during its time slice, it is ''paused'', another process begins or resumes, and then later the original process is resumed. In this way, multiple processes are part-way through execution at a single instant, but only one process is being executed at that instant.{{citation needed|date=December 2016}}

Concurrent computations ''may'' be executed in parallel,<ref name=waza/><ref name="benari2006">{{cite book|last=Ben-Ari|first=Mordechai|title=Principles of Concurrent and Distributed Programming|publisher=Addison-Wesley|year=2006|edition=2nd|isbn=978-0-321-31283-9}}</ref> for example, by assigning each process to a separate processor or processor core, or [[Distributed computing|distributing]] a computation across a network. In general, however, the languages, tools, and techniques for parallel programming might not be suitable for concurrent programming, and vice versa.{{citation needed|date=December 2016}}

The exact timing of when tasks in a concurrent system are executed depends on the [[Scheduling (computing)|scheduling]], and tasks need not always be executed concurrently. For example, given two tasks, T1 and T2:{{citation needed|date=December 2016}}

Line 35 ⟶ 34:

===Coordinating access to shared resources===

The main challenge in designing concurrent programs is [[concurrency control]]: ensuring the correct sequencing of the interactions or communications between different computational executions, and coordinating access to resources that are shared among executions.<ref name=benari2006/> Potential problems include [[Race condition#Software|race conditions]], [[Deadlock (computer science)|deadlock]]s, and [[resource starvation]]. For example, consider the following algorithm to make withdrawals from a checking account represented by the shared resource <code>balance</code>:

<syntaxhighlight lang="cpp" line highlight="3,5">

Line 53 ⟶ 52:

===Advantages===

{{Unreferenced section|date=December 2006}}

TheThere are advantages of concurrent computing include:

* Increased program throughput—parallel execution of a concurrent programalgorithm allows the number of tasks completed in a given time to increase proportionally to the number of processors according to [[Gustafson's law]].<ref>{{Cite book |last=Padua |first=David |title=Encyclopedia of Parallel Computing |publisher=Springer New York, NY |year=2011 |isbn=978-0-387-09765-7 |publication-date=September 8, 2011 |pages=819–825 |language=en}}</ref>

* High responsiveness for input/output—input/output-intensive programs mostly wait for input or output operations to complete. Concurrent programming allows the time that would be spent waiting to be used for another task.<ref>{{citationCitation |title=Asynchronous I/O needed|date=December2024-12-20 2016|work=Wikipedia |url=https://en.wikipedia.org/wiki/Asynchronous_I/O |access-date=2024-12-27 |language=en}}</ref>

* More appropriate program structure—some problems and problem domains are well-suited to representation as concurrent tasks or processes.{{citation needed|date=DecemberFor 2016}}example [[Multiversion concurrency control|MVCC]].

==Models==

Line 86 ⟶ 85:

;Shared memory communication: Concurrent components communicate by altering the contents of [[shared memory (interprocess communication)|shared memory]] locations (exemplified by [[Java (programming language)|Java]] and [[C Sharp (programming language)|C#]]). This style of concurrent programming usually needs the use of some form of locking (e.g., [[Mutual exclusion|mutexes]], [[Semaphore (programming)|semaphores]], or [[Monitor (synchronization)|monitors]]) to coordinate between threads. A program that properly implements any of these is said to be [[Thread safety|thread-safe]].

;Message passing communication: Concurrent components communicate by [[message passing|exchanging messages]] (exchanging messages, exemplified by [[Open MPI|MPI]], [[Go (programming language)|Go]], [[Scala (programming language)|Scala]], [[Erlang (programming language)|Erlang]] and [[occam (programming language)|occam]]). The exchange of messages may be carried out asynchronously, or may use a synchronous "rendezvous" style in which the sender blocks until the message is received. Asynchronous message passing may be reliable or unreliable (sometimes referred to as "send and pray"). Message-passing concurrency tends to be far easier to reason about than shared-memory concurrency, and is typically considered a more robust form of concurrent programming.{{Citation needed|date=May 2013}} A wide variety of mathematical theories to understand and analyze message-passing systems are available, including the [[actor model]], and various [[process calculi]]. Message passing can be efficiently implemented via [[symmetric multiprocessing]], with or without shared memory [[cache coherence]].

Shared memory and message passing concurrency have different performance characteristics. Typically (although not always), the per-process memory overhead and task switching overhead is lower in a message passing system, but the overhead of message passing is greater than for a procedure call. These differences are often overwhelmed by other performance factors.

Line 93 ⟶ 92:

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, such as semaphores. These arose to address the question of how to handle multiple trains on the same railroad system (avoiding collisions and maximizing efficiency) and how to handle multiple transmissions over a given set of wires (improving efficiency), such as via [[time-division multiplexing]] (1870s).

The academic study of concurrent algorithms started in the 1960s, with {{Harvtxt|Dijkstra|1965}} credited with being the first paper in this field, identifying and solving [[mutual exclusion]].<ref>{{CitationCite |report |url=http://www.podc.org/influential/2002.html | title=PODC Influential Paper Award: 2002 | work=ACM Symposium on Principles of Distributed Computing | access-date=2009-08-24}}</ref>

==Prevalence==

Line 112 ⟶ 111:

=={{anchor|Concurrent programming languages|Languages supporting concurrent programming}}Languages supporting concurrent programming==

<!-- This section is linked from [[occam (programming language)]] and [[COPL]] -->

[[List of concurrent programming languages|Concurrent programming languages]] are programming languages that use language constructs for [[concurrency (computer science)|concurrency]]. These constructs may involve [[Thread (computer science)|multi-threading]], support for [[distributed computing]], [[message passing programming|message passing]], [[sharing|shared resources]] (including [[Parallel Random Access Machine|shared memory]]) or [[futures and promises]]. Such languages are sometimes described as ''concurrency-oriented languages'' or ''concurrency-oriented programming languages'' (COPL).<ref name="armstrong2003">{{cite web|title=Making reliable distributed systems in the presence of software errors|last1=Armstrong|first1=Joe|year=2003|url=http://www.diva-portal.org/smash/get/diva2:9492/FULLTEXT01.pdf}}</ref>

* <!-- This section is linked from [[occam (programming language)]] and [[COPL]] -->

Today, the most commonly used programming languages that have specific constructs for concurrency are [[Java (programming language)|Java]] and [[C Sharp (programming language)|C#]]. Both of these languages fundamentally use a shared-memory concurrency model, with locking provided by [[Monitor (synchronization)|monitors]] (although message-passing models can and have been implemented on top of the underlying shared-memory model). Of the languages that use a message-passing concurrency model, [[Erlang (programming language)|Erlang]] is probably the most widely used in industry at present.{{Citation needed|date=August 2010}}

[[List of concurrent programming languages|Concurrent programming languages]] are programming languages that use language constructs for [[concurrency (computer science)|concurrency]]. These constructs may involve [[Thread (computer science)|multi-threading]], support for [[distributed computing]], [[message passing programming|message passing]], [[sharing|shared resources]] (including [[Parallel Random Access Machine|shared memory]]) or [[futures and promises]]. Such languages are sometimes described as ''concurrency-oriented languages'' or ''concurrency-oriented programming languages'' (COPL).<ref name="armstrong2003">{{cite web |last1=Armstrong |first1=Joe |year=2003 |title=Making reliable distributed systems in the presence of software errors |last1url=Armstrong|first1=Joe|year=2003http://www.diva-portal.org/smash/get/diva2:9492/FULLTEXT01.pdf |archive-url=https://web.archive.org/web/20160415213739/http://www.diva-portal.org/smash/get/diva2:9492/FULLTEXT01.pdf |archive-date=2016-04-15}}</ref>

Many concurrent programming languages have been developed more as research languages (e.g. [[Pict (programming language)|Pict]]) rather than as languages for production use. However, languages such as [[Erlang (programming language)|Erlang]], [[Limbo (programming language)|Limbo]], and [[occam (programming language)|occam]] have seen industrial use at various times in the last 20 years. A non-exhaustive list of languages which use or provide concurrent programming facilities:

Today, the most commonly used programming languages that have specific constructs for concurrency are [[Java (programming language)|Java]] and [[C Sharp (programming language)|C#]]. Both of these languages fundamentally use a shared-memory concurrency model, with locking provided by [[Monitor (synchronization)|monitors]] (although message-passing models can and have been implemented on top of the underlying shared-memory model). Of the languages that use a message-passing concurrency model, [[Erlang (programming language)|Erlang]] iswas probably the most widely used in industry atas presentof 2010.{{Citation needed|date=August 2010}}

Many concurrent programming languages have been developed more as research languages (e.g., [[Pict (programming language)|Pict]]) rather than as languages for production use. However, languages such as [[Erlang (programming language)|Erlang]], [[Limbo (programming language)|Limbo]], and [[occam (programming language)|occam]] have seen industrial use at various times in the last 20 years. A non-exhaustive list of languages which use or provide concurrent programming facilities:

* [[Ada (programming language)|Ada]]—general purpose, with native support for message passing and monitor based concurrency

Line 125 ⟶ 126:

* [[Axum (programming language)|Axum]]—___domain specific, concurrent, based on actor model and .NET Common Language Runtime using a C-like syntax

* [[BMDFM]]—Binary Modular DataFlow Machine

* [[C++]]—thread and coroutine support libraries<ref>{{Cite web |title=Standard library header <thread> (C++11) |url=https://en.cppreference.com/w/cpp/header/thread |access-date=2024-10-03 |website=en.cppreference.com}}</ref><ref>{{Cite web |title=Standard library header <coroutine> (C++20) |url=https://en.cppreference.com/w/cpp/header/coroutine |access-date=2024-10-03 |website=en.cppreference.com}}</ref>

* [[C++]]—std::thread

* [[Cω]] (C omega)—for research, extends C#, uses asynchronous communication

* [[C Sharp (programming language)|C#]]—supports concurrent computing using {{Mono|lock}}, {{Mono|yield}}, also since version 5.0 {{Mono|async}} and {{Mono|await}} keywords introduced

* [[Clojure]]—modern, [[Functionalfunctional programming|functional]] dialect of [[Lisp (programming language)|Lisp]] on the [[Java (software platform)|Java]] platform

* [[Concurrent Clean]]—functional programming, similar to [[Haskell (programming language)|Haskell]]

* [[Concurrent Collections]] (CnC)—Achieves implicit parallelism independent of memory model by explicitly defining flow of data and control

* [[Concurrent Haskell]]—lazy, pure functional language operating concurrent processes on shared memory

Line 144 ⟶ 145:

* [[Fortran]]—[[Coarray Fortran|coarrays]] and ''do concurrent'' are part of Fortran 2008 standard

* [[Go (programming language)|Go]]—for system programming, with a concurrent programming model based on [[Communicating sequential processes|CSP]]

* [[Haskell programming language|Haskell]]—concurrent, and parallel functional programming language<ref> Marlow, Simon (2013) Parallel and Concurrent Programming in Haskell : Techniques for Multicore and Multithreaded Programming {{ISBN|9781449335946}}</ref>

* [[Hume (programming language)|Hume]]—functional, concurrent, for bounded space and time environments where automata processes are described by synchronous channels patterns and message passing

* [[Io (programming language)|Io]]—actor-based concurrency

Line 150 ⟶ 151:

* [[Java (programming language)|Java]]—thread class or Runnable interface

* [[Julia (programming language)|Julia]]—"concurrent programming primitives: Tasks, async-wait, Channels."<!--parallel programming primitives: adding physical processes, remote call, spawn, @parallel macro and pmap

Parallelism provided in library land such as MPI.jl--><ref>{{Cite web |date= |title=Concurrent and Parallel programming in Julia — JuliaCon India 2015 — HasGeek Talkfunnel |url=https://juliacon.talkfunnel.com/2015/21-concurrent-and-parallel-programming-in-julia Concurrent |archive-url=https://web.archive.org/web/20161018061906/https://juliacon.talkfunnel.com/2015/21-concurrent-and Parallel -parallel-programming -in-julia Julia|archive-date=2016-10-18 |access-date= |website=juliacon.talkfunnel.com}}</ref>

* [[JavaScript]]—via [[web worker]]s, in a browser environment, [[Futures and promises|promises]], and [[Callback (computer programming)|callbacks]].

* [[JoCaml]]—concurrent and distributed channel based, extension of [[OCaml]], implements the [[join-calculus]] of processes

Line 165 ⟶ 166:

* [[occam (programming language)|occam]]—influenced heavily by [[communicating sequential processes]] (CSP)

** [[occam-π]]—a modern variant of [[occam (programming language)|occam]], which incorporates ideas from Milner's [[π-calculus]]

* [[Object REXX|ooRexx]]—object-based, message exchange for communication and synchronization

* [[Orc (programming language)|Orc]]—heavily concurrent, nondeterministic, based on [[Kleene algebra]]

* [[Oz (programming language)|Oz-Mozart]]—multiparadigm, supports shared-state and message-passing concurrency, and futures

* [[ParaSail (programming language)|ParaSail]]—object-oriented, parallel, free of pointers, race conditions

* [[PHP]]—multithreading support with parallel extension implementing message passing inspired from [[Go (programming language)|Go]]<ref>{{Cite web |title=PHP: parallel - Manual |url=https://www.php.net/manual/en/book.parallel.php |access-date=2024-10-03 |website=www.php.net |language=en}}</ref>

* [[Pict (programming language)|Pict]]—essentially an executable implementation of Milner's [[π-calculus]]

*[[Raku (programming language)|Raku]] includes classes for threads, promises and channels by default<ref>{{Cite web|url=https://docs.perl6.org/language/concurrency|title=Concurrency|website=docs.perl6.org|language=en|access-date=2017-12-24}}</ref>

* [[Python (programming language)|Python]] — uses thread-based parallelism and process-based parallelism <ref>[https://docs.python.org/3/library/concurrency.html Documentation » The Python Standard Library » Concurrent Execution]</ref>

*[[Raku (programming language)|Raku]] includes classes for threads, promises and channels by default<ref>{{Cite web|url=https://docs.perl6.org/language/concurrency|title=Concurrency|website=docs.perl6.org|language=en|access-date=2017-12-24}}</ref>

* [[Reia (programming language)|Reia]]—uses asynchronous message passing between shared-nothing objects

* [[Red (programming language)|Red/System]]—for system programming, based on [[Rebol]]

Line 193 ⟶ 196:

* [[Ptolemy Project]]

* {{Section link|Race condition|Computing}}

* [[Sheaf (mathematics)]]

* [[Structured concurrency]]

* [[Transaction processing]]

Line 213 ⟶ 215:

* {{cite book |last=Downey |first=Allen B. |title=The Little Book of Semaphores |year=2005 |orig-year=2005 |url=http://www.greenteapress.com/semaphores/downey08semaphores.pdf |publisher=Green Tea Press |isbn=978-1-4414-1868-5 |access-date=2009-11-21 |archive-url=https://web.archive.org/web/20160304031330/http://www.greenteapress.com/semaphores/downey08semaphores.pdf |archive-date=2016-03-04 |url-status=dead }}

* {{cite book |last=Filman |first=Robert E. |author2=Daniel P. Friedman |title=Coordinated Computing: Tools and Techniques for Distributed Software |publisher=McGraw-Hill |___location=New York |isbn=978-0-07-022439-1 |page=[https://archive.org/details/coordinatedcompu0000film/page/370 370] |year=1984 |url=https://archive.org/details/coordinatedcompu0000film/page/370 }}

* {{cite book |last=Leppäjärvi |first=Jouni |title=A pragmatic, historically oriented survey on the universality of synchronization primitives |year=2008 | url=http://www.enseignement.polytechnique.fr/informatique/INF431/X09-2010-2011/AmphiTHC/SynchronizationPrimitives.pdf |publisher=University of Oulu |access-date=2012-09-13 |archive-date=2017-08-30 |archive-url=https://web.archive.org/web/20170830062719/http://www.enseignement.polytechnique.fr/informatique/INF431/X09-2010-2011/AmphiTHC/SynchronizationPrimitives.pdf |url-status=dead }}

* {{cite book |last=Taubenfeld |first=Gadi |title=Synchronization Algorithms and Concurrent Programming |url=http://www.faculty.idc.ac.il/gadi/book.htm |publisher=Pearson / Prentice Hall |isbn=978-0-13-197259-9 |year=2006 |page=433}}

Line 221 ⟶ 223:

{{Concurrent computing}}

{{Programming paradigms navbox}}

{{Types of programming languages}}