Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

This is the documentation for an old version of Boost. Click here to view this page for the latest version.
PrevUpHomeNext

Introduction

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 [1]), are a generalization of routines (Donald Knuth [2]. 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).

How it works

Functions foo() and bar() are supposed to alternate their execution (leave and enter function body).

foo_bar

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 (boost::contexts::fcontext_t 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').

characteristics

Characteristics [3] of a coroutine are:

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.

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.

foo_bar_seq

Both concepts are equivalent and a fully-general coroutine library can provide either symmetric or asymmetric coroutines. For convenience, Boost.Coroutine provides both.

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.

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).



[1] Conway, Melvin E.. "Design of a Separable Transition-Diagram Compiler". Commun. ACM, Volume 6 Issue 7, July 1963, Article No. 7

[2] Knuth, Donald Ervin (1997). "Fundamental Algorithms. The Art of Computer Programming 1", (3rd ed.)

[3] Moura, Ana Lucia De and Ierusalimschy, Roberto. "Revisiting coroutines". ACM Trans. Program. Lang. Syst., Volume 31 Issue 2, February 2009, Article No. 6


PrevUpHomeNext