Structured concurrency

Last updated

Structured concurrency is a programming paradigm aimed at improving the clarity, quality, and development time of a computer program by using a structured approach to concurrent programming.

Contents

The core concept is the encapsulation of concurrent threads of execution (here encompassing kernel and userland threads and processes) by way of control flow constructs that have clear entry and exit points and that ensure all spawned threads have completed before exit. Such encapsulation allows errors in concurrent threads to be propagated to the control structure's parent scope and managed by the native error handling mechanisms of each particular computer language. It allows control flow to remain readily evident by the structure of the source code despite the presence of concurrency. To be effective, this model must be applied consistently throughout all levels of the program otherwise concurrent threads may leak out, become orphaned, or fail to have runtime errors correctly propagated.

Structured concurrency is analogous to structured programming, which uses control flow constructs that encapsulate sequential statements and subroutines.

History

The fork–join model from the 1960s, embodied by multiprocessing tools like OpenMP, is an early example of a system ensuring all threads have completed before exit. However, Smith argues that this model is not true structured concurrency as the programming language is unaware of the joining behavior, and is thus unable to enforce safety. [1]

The concept was formulated in 2016 by Martin Sústrik (a developer of ZeroMQ) with his C library libdill, with goroutines as a starting point. [2] It was further refined in 2017 by Nathaniel J. Smith, who introduced a "nursery pattern" in his Python implementation called Trio. [3] Meanwhile, Roman Elizarov independently came upon the same ideas while developing an experimental coroutine library for the Kotlin language, [4] [5] which later became a standard library. [6]

In 2021, Swift adopted structured concurrency. [7] Later that year, a draft proposal was published to add structured concurrency to Java. [8]

Variations

A major point of variation is how an error in one member of a concurrent thread tree is handled. Simple implementations will merely wait until the children and siblings of the failing thread run to completion before propagating the error to the parent scope. However, that could take an indefinite amount of time. The alternative is to employ a general cancellation mechanism (typically a cooperative scheme allowing program invariants to be honored) to terminate the children and sibling threads in an expedient manner.

See also

Related Research Articles

Structured programming is a programming paradigm aimed at improving the clarity, quality, and development time of a computer program by making extensive use of the structured control flow constructs of selection (if/then/else) and repetition, block structures, and subroutines.

<span class="mw-page-title-main">Simula</span> Early object-oriented programming language

Simula is the name of two simulation programming languages, Simula I and Simula 67, developed in the 1960s at the Norwegian Computing Center in Oslo, by Ole-Johan Dahl and Kristen Nygaard. Syntactically, it is an approximate superset of ALGOL 60, and was also influenced by the design of Simscript.

<span class="mw-page-title-main">Thread (computing)</span> Smallest sequence of programmed instructions that can be managed independently by a scheduler

In computer science, a thread of execution is the smallest sequence of programmed instructions that can be managed independently by a scheduler, which is typically a part of the operating system. In many cases, a thread is a component of a process.

In computer science, control flow is the order in which individual statements, instructions or function calls of an imperative program are executed or evaluated. The emphasis on explicit control flow distinguishes an imperative programming language from a declarative programming language.

Coroutines are computer program components that allow execution to be suspended and resumed, generalizing subroutines for cooperative multitasking. Coroutines are well-suited for implementing familiar program components such as cooperative tasks, exceptions, event loops, iterators, infinite lists and pipes.

In computer science, a continuation is an abstract representation of the control state of a computer program. A continuation implements (reifies) the program control state, i.e. the continuation is a data structure that represents the computational process at a given point in the process's execution; the created data structure can be accessed by the programming language, instead of being hidden in the runtime environment. Continuations are useful for encoding other control mechanisms in programming languages such as exceptions, generators, coroutines, and so on.

In software engineering, a pipeline consists of a chain of processing elements, arranged so that the output of each element is the input of the next. The concept is analogous to a physical pipeline. Usually some amount of buffering is provided between consecutive elements. The information that flows in these pipelines is often a stream of records, bytes, or bits, and the elements of a pipeline may be called filters. This is also called the pipe(s) and filters design pattern which is monolithic. Its advantages are simplicity and low cost while its disadvantages are lack of elasticity, fault tolerance and scalability. Connecting elements into a pipeline is analogous to function composition.

In computer science, future, promise, delay, and deferred refer to constructs used for synchronizing program execution in some concurrent programming languages. They describe an object that acts as a proxy for a result that is initially unknown, usually because the computation of its value is not yet complete.

Concurrent computing is a form of computing in which several computations are executed concurrently—during overlapping time periods—instead of sequentially—with one completing before the next starts.

A protothread is a low-overhead mechanism for concurrent programming.

In computer science, a fiber is a particularly lightweight thread of execution.

In computer programming, flow-based programming (FBP) is a programming paradigm that defines applications as networks of black box processes, which exchange data across predefined connections by message passing, where the connections are specified externally to the processes. These black box processes can be reconnected endlessly to form different applications without having to be changed internally. FBP is thus naturally component-oriented.

The following outline is provided as an overview of and topical guide to computer programming:

In computer programming, a green thread is a thread that is scheduled by a runtime library or virtual machine (VM) instead of natively by the underlying operating system (OS). Green threads emulate multithreaded environments without relying on any native OS abilities, and they are managed in user space instead of kernel space, enabling them to work in environments that do not have native thread support.

<span class="mw-page-title-main">Goto</span> One-way control statement in computer programming

Goto is a statement found in many computer programming languages. It performs a one-way transfer of control to another line of code; in contrast a function call normally returns control. The jumped-to locations are usually identified using labels, though some languages use line numbers. At the machine code level, a goto is a form of branch or jump statement, in some cases combined with a stack adjustment. Many languages support the goto statement, and many do not.

In computer programming, the async/await pattern is a syntactic feature of many programming languages that allows an asynchronous, non-blocking function to be structured in a way similar to an ordinary synchronous function. It is semantically related to the concept of a coroutine and is often implemented using similar techniques, and is primarily intended to provide opportunities for the program to execute other code while waiting for a long-running, asynchronous task to complete, usually represented by promises or similar data structures. The feature is found in C#, C++, Python, F#, Hack, Julia, Dart, Kotlin, Rust, Nim, JavaScript, Swift and Zig.

Kotlin is a cross-platform, statically typed, general-purpose high-level programming language with type inference. Kotlin is designed to interoperate fully with Java, and the JVM version of Kotlin's standard library depends on the Java Class Library, but type inference allows its syntax to be more concise. Kotlin mainly targets the JVM, but also compiles to JavaScript or native code via LLVM. Language development costs are borne by JetBrains, while the Kotlin Foundation protects the Kotlin trademark.

Swift is a high-level general-purpose, multi-paradigm, compiled programming language created by Chris Lattner in 2010 for Apple Inc. and maintained by the open-source community. Swift compiles to machine code, as it is an LLVM-based compiler. Swift was first released in June 2014, and the Swift toolchain has shipped in Xcode since version 6, released in 2014.

In computer science, yield is an action that occurs in a computer program during multithreading, of forcing a processor to relinquish control of the current running thread, and sending it to the end of the running queue, of the same scheduling priority.

References

  1. Smith, Nathaniel J. (25 April 2018). "Notes on structured concurrency, or: Go statement considered harmful" . Retrieved 1 August 2019.
  2. Sústrik, Martin (7 February 2016). "Structured Concurrency" . Retrieved 1 August 2019.
  3. Smith, Nathaniel J. (10 March 2017). "Announcing Trio" . Retrieved 23 September 2022.
  4. Elizarov, Roman (12 September 2018). "Structured concurrency" . Retrieved 21 September 2019.
  5. Elizarov, Roman (11 July 2019). Structured concurrency (Video). Hydra Distributed computing conference. 42 minutes in. Retrieved 21 September 2019. We needed a name and we needed to finalize this whole concept [...] and we stumble onto this blog post [...] by Nathaniel J. Smith.
  6. "Coroutines basics: Structured concurrency". Kotlin. JetBrains. Retrieved 3 March 2022.
  7. McCall, John; Groff, Joe; Gregor, Doug; Malawski, Konrad. "Swift Structured Concurrency Proposal". Apple's Swift Evolution repo. GitHub. Retrieved 3 March 2022.
  8. Pressler, Ron. "JEP draft: Structured Concurrency (Incubator)". OpenJDK . Oracle. Retrieved 3 March 2022.