123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107 |
- [/
- 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]
|