]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | [/ |
2 | Copyright Oliver Kowalke 2009. | |
3 | Distributed under the Boost Software License, Version 1.0. | |
4 | (See accompanying file LICENSE_1_0.txt or copy at | |
5 | http://www.boost.org/LICENSE_1_0.txt | |
6 | ] | |
7 | ||
8 | [section:intro Introduction] | |
9 | ||
10 | [heading Definition] | |
11 | ||
12 | In computer science routines are defined as a sequence of operations. The | |
13 | execution of routines forms a parent-child relationship and the child terminates | |
14 | always before the parent. Coroutines (the term was introduced by Melvin | |
15 | Conway [footnote Conway, Melvin E.. "Design of a Separable Transition-Diagram Compiler". | |
16 | Commun. ACM, Volume 6 Issue 7, July 1963, Article No. 7]), | |
17 | are a generalization of routines (Donald Knuth [footnote Knuth, Donald Ervin (1997). | |
18 | "Fundamental Algorithms. The Art of Computer Programming 1", (3rd ed.)]. | |
19 | The principal difference between coroutines and routines | |
20 | is that a coroutine enables explicit suspend and resume of its progress via | |
21 | additional operations by preserving execution state and thus provides an | |
22 | [*enhanced control flow] (maintaining the execution context). | |
23 | ||
24 | ||
25 | [heading How it works] | |
26 | ||
27 | Functions foo() and bar() are supposed to alternate their execution (leave and | |
28 | enter function body). | |
29 | ||
30 | [$../../../../libs/coroutine/doc/images/foo_bar.png [align center]] | |
31 | ||
32 | If coroutines were called exactly like routines, the stack would grow with | |
33 | every call and would never be popped. A jump into the middle of a coroutine | |
34 | would not be possible, because the return address would be on top of | |
35 | stack entries. | |
36 | ||
37 | The solution is that each coroutine has its own stack and control-block | |
38 | (__fcontext__ from __boost_context__). | |
39 | Before the coroutine gets suspended, the non-volatile registers (including stack | |
40 | and instruction/program pointer) of the currently active coroutine are stored in | |
41 | the coroutine's control-block. | |
42 | The registers of the newly activated coroutine must be restored from its | |
43 | associated control-block before it is resumed. | |
44 | ||
45 | The context switch requires no system privileges and provides cooperative | |
46 | multitasking convenient to C++. Coroutines provide quasi parallelism. | |
47 | When a program is supposed to do several things at the same time, coroutines | |
48 | help to do this much more simply and elegantly than with only a single flow of | |
49 | control. | |
50 | The advantages can be seen particularly clearly with the use of a recursive | |
51 | function, such as traversal of binary trees (see example 'same fringe'). | |
52 | ||
53 | ||
54 | [heading characteristics] | |
55 | Characteristics [footnote Moura, Ana Lucia De and Ierusalimschy, Roberto. | |
56 | "Revisiting coroutines". ACM Trans. Program. Lang. Syst., Volume 31 Issue 2, | |
57 | February 2009, Article No. 6] of a coroutine are: | |
58 | ||
59 | * values of local data persist between successive calls (context switches) | |
60 | * execution is suspended as control leaves coroutine and is resumed at certain time later | |
61 | * symmetric or asymmetric control-transfer mechanism; see below | |
62 | * first-class object (can be passed as argument, returned by procedures, | |
63 | stored in a data structure to be used later or freely manipulated by | |
64 | the developer) | |
65 | * stackful or stackless | |
66 | ||
67 | Coroutines are useful in simulation, artificial intelligence, concurrent | |
68 | programming, text processing and data manipulation, supporting | |
69 | the implementation of components such as cooperative tasks (fibers), iterators, | |
70 | generators, infinite lists, pipes etc. | |
71 | ||
72 | ||
73 | [heading execution-transfer mechanism] | |
74 | Two categories of coroutines exist: symmetric and asymmetric coroutines. | |
75 | ||
76 | An asymmetric coroutine knows its invoker, using a special operation to | |
77 | implicitly yield control specifically to its invoker. By contrast, all symmetric | |
78 | coroutines are equivalent; one symmetric coroutine may pass control to any | |
79 | other symmetric coroutine. Because of this, a symmetric coroutine ['must] | |
80 | specify the coroutine to which it intends to yield control. | |
81 | ||
82 | [$../../../../libs/coroutine/doc/images/foo_bar_seq.png [align center]] | |
83 | ||
84 | Both concepts are equivalent and a fully-general coroutine library can provide | |
85 | either symmetric or asymmetric coroutines. For convenience, Boost.Coroutine | |
86 | provides both. | |
87 | ||
88 | ||
89 | [heading stackfulness] | |
90 | In contrast to a stackless coroutine a stackful coroutine can be suspended | |
91 | from within a nested stackframe. Execution resumes at exactly the same point | |
92 | in the code where it was suspended before. | |
93 | With a stackless coroutine, only the top-level routine may be suspended. Any | |
94 | routine called by that top-level routine may not itself suspend. This prohibits | |
95 | providing suspend/resume operations in routines within a general-purpose library. | |
96 | ||
97 | [heading first-class continuation] | |
98 | A first-class continuation can be passed as an argument, returned by a | |
99 | function and stored in a data structure to be used later. | |
100 | In some implementations (for instance C# ['yield]) the continuation can | |
101 | not be directly accessed or directly manipulated. | |
102 | ||
103 | Without stackfulness and first-class semantics, some useful execution control | |
104 | flows cannot be supported (for instance cooperative multitasking or | |
105 | checkpointing). | |
106 | ||
107 | [endsect] |