Bridging Calls using Coroutines
Telephony Software Architecture Document
This paper discusses how coroutines, sometimes also referred to as user level threads or actors can be used to bridge telephone calls in order to increase the scalability of telephony servers and avoid problems associated with the non-deterministic behaviour of preemptive threads.
Document version: 1.0
Author: Benjamin Kowarsch
Copyright (c) 2006 Sunrise Telephone Systems Ltd., Tokyo, Japan
Permission is hereby granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, GFDL Version 1.2.
This Document is provided "as is" without any warranty of any kind.
Coroutines in a nutshell
A coroutine is a function which can be interrupted and resumed under user
control. The terminology widely used for a coroutine to suspend itself is
"to yield" as in "to yield control". Typically, coroutines will yield to
each other in a variety of cooperative arrangements, but coroutines can
also be used to implement round robin and priority based schedulers.
Each time a coroutine yields control to another, its state is preserved so
that it can continue where it has yielded control. Each time a coroutine is
resumed, it will continue at the point where it last yielded control.
Unlike preemptive scheduling, the transfer of control between coroutines
involves very little overhead. The computational cost of transfering control
to a coroutine is comparable to the cost of a function call.
Also unlike preemptive scheduling, coroutines cannot be interrupted
arbitrarily by other coroutines. Thus, they can be written such that they
always leave the data they are operating on in a well defined state before
they yield control to another coroutine. This in turn means that mutual
exclusion locks are not required and thus, there is no danger of deadlocks
or race conditions. This also simplifies the task of development.
Bridging channels and coroutines
The bridging of two channels is a classical producer-consumer problem and
coroutines are the classical solution to this problem.
Given two channels to be bridged, the originating channel can be considered
a producer, while the destination channel can be considered a consumer.
Two coroutines can then be used to bridge the two channels. One coroutine will
handle the originating channel, while the other coroutine will handle the
destination channel.
When the bridge is being requested, coroutine 1 will be called and start to
make all the necessary arrangements to prepare the originating channel for the
bridge. At various points where the originating channel is in a well defined
state, coroutine 1 may yield to coroutine 2 which will do likewise to prepare
the destination channel for the bridge. Again, coroutine 2 may yield back to
coroutine 1 at various points where the destination channel is in a well
defined state.
When the bridge has been established and audio is to be read from one channel
and to be transmitted on the other channel, the coroutines will take turns
reading from their own channel and writing to the other.
Pseudo code for this may look as follows ...
// originating channel
coroutine_1 {
...
loop {
read_audio_from(orig_chan);
write_audio_to(dest_chan);
yield();
} // end loop
...
} // end coroutine_1
// destination channel
coroutine_2 {
...
loop {
read_audio_from(dest_chan);
write_audio_to(orig_chan);
yield();
} // end loop
...
} // end coroutine_2
The above example makes no assumptions about how the coroutines are being
scheduled for the first time. There are several possibilities. In the present
producer-consumer scenario, coroutines may yield directy to each other. This
is very efficient and the code is very simple, thus easy to understand and to
maintain.
In scenarios where more than two coroutines are involved and the order in
which they are called is not always the same, then it is preferable to use
a main coroutine as a scheduler and let each other coroutine yield back to
the main coroutine which then decides which coroutine is next.
Pseudo code for this may look as follows ...
// scheduler
coroutine_0 {
...
repeat {
...
transfer_to(coroutine_1);
...
transfer_to(coroutine_2);
...
if (call_put_on_hold) {
...
transfer_to(coroutine_3);
...
} // end if
} until (call_ended);
...
} // end coroutine_0
Note the complete absence of any mutual exclusion locks in both examples.
Mutual exclusion locks are not required because coroutines cannot be
interrupted arbitrarily. They are only suspended when they yield.
The author of a coroutine is responsible to make sure that yield is only
called at a point where shared data is in a well defined state. This way,
every sequence of operations on the data before a yield can be considered
atomic and thus no mutual exclusion locks are needed to ensure that the
sequence does not get interrupted.
// END OF DOCUMENT
Click here to download this document.
Coroutines versus Pthreads — A Benchmark Example
The Swedish Institute of Computer Science has benchmarked the Apache webserver which is using Pthreads, against YAWS, a webserver written in Erlang and thus using Erlang's built-in coroutines for concurrency. The benchmark shows a scalability advantage for YAWS of at least a factor of 20. The full benchmark is published here.
Libraries
Further Reading on Coroutines
- The Problem with Threads [IEEE Computer] Edward A. Lee, Berkeley University
- Classes and Subclasses in Actor-Oriented Design [PDF] Edward A. Lee, Berkeley University
- Revisiting Coroutines [PDF] A. L. De Moura & R. Ierusalimschky, Rio de Janeiro University
- Why Events are a Bad Idea¹ [PDF] Von Behren et al, Berkeley University
¹ The Von Behren paper doesn't explicitly distinguish between premptive and non-premptive threads. The casual reader may therefore get the impression that it promotes the use of pthreads. At closer examination though, it will become apparent that the research presented is based on the authors' implementation of coroutines.
