108 lines
4.8 KiB
Plaintext
108 lines
4.8 KiB
Plaintext
[/
|
|
Copyright Oliver Kowalke 2009.
|
|
Distributed under the Boost Software License, Version 1.0.
|
|
(See accompanying file LICENSE_1_0.txt or copy at
|
|
http://www.boost.org/LICENSE_1_0.txt
|
|
]
|
|
|
|
[section:intro Introduction]
|
|
|
|
[heading Definition]
|
|
|
|
In computer science routines are defined as a sequence of operations. The
|
|
execution of routines forms a parent-child relationship and the child terminates
|
|
always before the parent. Coroutines (the term was introduced by Melvin
|
|
Conway [footnote Conway, Melvin E.. "Design of a Separable Transition-Diagram Compiler".
|
|
Commun. ACM, Volume 6 Issue 7, July 1963, Article No. 7]),
|
|
are a generalization of routines (Donald Knuth [footnote Knuth, Donald Ervin (1997).
|
|
"Fundamental Algorithms. The Art of Computer Programming 1", (3rd ed.)].
|
|
The principal difference between coroutines and routines
|
|
is that a coroutine enables explicit suspend and resume of its progress via
|
|
additional operations by preserving execution state and thus provides an
|
|
[*enhanced control flow] (maintaining the execution context).
|
|
|
|
|
|
[heading How it works]
|
|
|
|
Functions foo() and bar() are supposed to alternate their execution (leave and
|
|
enter function body).
|
|
|
|
[$../../../../libs/coroutine/doc/images/foo_bar.png [align center]]
|
|
|
|
If coroutines were called exactly like routines, the stack would grow with
|
|
every call and would never be popped. A jump into the middle of a coroutine
|
|
would not be possible, because the return address would be on top of
|
|
stack entries.
|
|
|
|
The solution is that each coroutine has its own stack and control-block
|
|
(__fcontext__ from __boost_context__).
|
|
Before the coroutine gets suspended, the non-volatile registers (including stack
|
|
and instruction/program pointer) of the currently active coroutine are stored in
|
|
the coroutine's control-block.
|
|
The registers of the newly activated coroutine must be restored from its
|
|
associated control-block before it is resumed.
|
|
|
|
The context switch requires no system privileges and provides cooperative
|
|
multitasking convenient to C++. Coroutines provide quasi parallelism.
|
|
When a program is supposed to do several things at the same time, coroutines
|
|
help to do this much more simply and elegantly than with only a single flow of
|
|
control.
|
|
The advantages can be seen particularly clearly with the use of a recursive
|
|
function, such as traversal of binary trees (see example 'same fringe').
|
|
|
|
|
|
[heading characteristics]
|
|
Characteristics [footnote Moura, Ana Lucia De and Ierusalimschy, Roberto.
|
|
"Revisiting coroutines". ACM Trans. Program. Lang. Syst., Volume 31 Issue 2,
|
|
February 2009, Article No. 6] of a coroutine are:
|
|
|
|
* values of local data persist between successive calls (context switches)
|
|
* execution is suspended as control leaves coroutine and is resumed at certain time later
|
|
* symmetric or asymmetric control-transfer mechanism; see below
|
|
* first-class object (can be passed as argument, returned by procedures,
|
|
stored in a data structure to be used later or freely manipulated by
|
|
the developer)
|
|
* stackful or stackless
|
|
|
|
Coroutines are useful in simulation, artificial intelligence, concurrent
|
|
programming, text processing and data manipulation, supporting
|
|
the implementation of components such as cooperative tasks (fibers), iterators,
|
|
generators, infinite lists, pipes etc.
|
|
|
|
|
|
[heading execution-transfer mechanism]
|
|
Two categories of coroutines exist: symmetric and asymmetric coroutines.
|
|
|
|
An asymmetric coroutine knows its invoker, using a special operation to
|
|
implicitly yield control specifically to its invoker. By contrast, all symmetric
|
|
coroutines are equivalent; one symmetric coroutine may pass control to any
|
|
other symmetric coroutine. Because of this, a symmetric coroutine ['must]
|
|
specify the coroutine to which it intends to yield control.
|
|
|
|
[$../../../../libs/coroutine/doc/images/foo_bar_seq.png [align center]]
|
|
|
|
Both concepts are equivalent and a fully-general coroutine library can provide
|
|
either symmetric or asymmetric coroutines. For convenience, Boost.Coroutine
|
|
provides both.
|
|
|
|
|
|
[heading stackfulness]
|
|
In contrast to a stackless coroutine a stackful coroutine can be suspended
|
|
from within a nested stackframe. Execution resumes at exactly the same point
|
|
in the code where it was suspended before.
|
|
With a stackless coroutine, only the top-level routine may be suspended. Any
|
|
routine called by that top-level routine may not itself suspend. This prohibits
|
|
providing suspend/resume operations in routines within a general-purpose library.
|
|
|
|
[heading first-class continuation]
|
|
A first-class continuation can be passed as an argument, returned by a
|
|
function and stored in a data structure to be used later.
|
|
In some implementations (for instance C# ['yield]) the continuation can
|
|
not be directly accessed or directly manipulated.
|
|
|
|
Without stackfulness and first-class semantics, some useful execution control
|
|
flows cannot be supported (for instance cooperative multitasking or
|
|
checkpointing).
|
|
|
|
[endsect]
|