|
|
One considers three domains related to Loft. The first is the one
of threads which either appear as libraries or are incorporated in
existing languages. The second domain is the synchronous-reactive
approach from which Loft takes its major constructs. The third
domain contains approaches in which computations are decomposed into
small pieces that can be combined to build complex behaviors.
|
9.1 Thread Based Formalisms
|
Thread Libraries in C
Several thread libraries exist for C. Among them, the Pthreads library
[28] implements the POSIX standard for preemptive
threads. LinuxThreads [4] is an implementation
of Pthreads for Linux; it is based on native (kernel-level) threads.
Quick Threads [24] provides programmers with a
minimal support for multi-threading at user-space level. Basically,
it implements context-switching in assembly code, and is thus a
low-level solution to multi-threading.
Gnu Portable Threads [17] (GNU Pth) is a library of purely
cooperative threads which has portability as main objective. The Next
Generation POSIX Threading project [5] proposes to
extend GNU Pth to the M:N model (M user threads, N native threads),
with Linux SMP machines as target.
Java Threads
Java introduce threads at language level. Actually, threads are
generally heavily used in Java, for example when graphics or
networking is involved. No assumption is made on the way threads are
scheduled (cooperative or preemptive schedulings are both possible)
which makes Java multi-threaded systems difficult to program and to
port [22]. This difficulty is pointed out by the
suppression from the recent versions (1.2) of the language of the
primitives to gain fine control over threads [3].
These primitives actually corresponds to the stop, suspend, and resume of Loft.
The use of Java threads with multiprocessor architectures leads to
several difficulties which are actually under study in the Java
community. One of these difficulties is called the Double Check
Locking (DCL) which concerns the Java memory model (JMM) and is
rather tricky (see ??? for details). These studies should lead to
some changes of the Java thread model in the next versions (1.5) of
Java.
It should be mentioned that the initial version of FairThreads has been
proposed in the context of the Java language [12]
in order to simplify concurrent programming in Java; this version
was however limited to cooperative threads.
Threads in Functional Languages
Threads are used in several ML-based languages such as CML [30]. CML is preemptively scheduled and threads communication is
synchronous and based on channels. Threads are also introduced in
CAML [2]; they are implemented by time-sharing on a
single processor, and thus cannot benefit from multiprocessor
machines.
FairThreads has been recently introduced in the Bigloo [1]
implementation of Scheme. The present version does not support
unlinked threads, but special constructs are introduced to deal with
non-blocking cooperative I/Os.
FairThreads and Loft actually belong to the so-called reactive
approach [6] which is issued from synchronous
languages. One first compare synchronous languages and the reactive
approach before describing several reactive programming languages.
Synchronous Languages vs. Reactive Programming
To the family of synchronous languages [19] belong
several programming languages which all share the same notion of an
instant which is supposed to be of zero duration. In this context, the
output of a program at a given instant is synchronous with its
input; the synchronous characterization of these languages comes
from this hypothesis.
Lustre and Signal are two data-flow synchronous languages in which one
programs nets of operators, in a style very close to the one of
section Data-Flow Programming. At the basis of these
dataflow languages are the nets of processes of [23].
Following the StateCharts of D. Harel, several systems have been
proposed for synchronous graphical programming, among which are
SyncCharts and Argos.
The Esterel synchronous language [9] introduces
broadcast events, called signals, in an imperative
style. However, in Esterel, the absence of an event can be decided
immediately and consequences of this absence can take place in the
very same instant. This leads to "causality problems" as for example
in present S else emit S end. In this program, indeed, the
signal S is emitted if it is absent during the instant,
which is of course contradictory.
As opposite to Esterel, in reactive programming the absence of an
event during one instant cannot be decided before the end of this very
instant. As a consequence, the reaction to the absence of one event is
delayed to the next instant. This is a way to solve the causality
problems which are obstacles to modularity.
All synchronous languages are static in the sense that they
disallow the creation at run time of new parallel components and of
new events. Moreover, they do not give users any way to deal with
multiprocessor machines. However, synchronous languages generally put
the focus on hardware circuits in which dynamic creation does not
appear. This is a major difference with reactive programming which
limits to software systems.
A major claim of synchronous languages is that they make possible
proofs and validations of programs. This is a consequence of the
existence of a formal semantics and of the static characteristics of
these languages. Program proofs and validations have not yet be
considered in reactive programming.
Reactive-C
The Reactive-C [11] language was the first proposal
for reactive programming in C; in this respect, Loft can be
considered as a descendant of it. Reactive-C proposes instants and the
merge operator which implements deterministic parallelism. A
reaction of the instruction merge i1 i2
consists in a reaction of i1 followed in the same
instant by a reaction of i2. Thus, one has a
deterministic left-right operator with which parallelism can be
introduced at any level. Reactive-C does not define events, as they
are defined in Loft. Reactive-C is basically implemented as a
straightforward preprocessor of C.
Reactive-C introduces primitives for remote execution of reactive
programs over the network. Remote execution is based on the use of the
Remote Procedure Call (RPC) mechanism. Distribution is not yet
possible neither in Loft nor in FairThreads.
Reactive Programming in Java
The reactive approach has been implemented in Java in several ways.
The first one is the SugarCubes [13] framework
which is a set of classes for reactive programming in Java. Several
related formalisms have been designed, among which are Junior [21] and Rejo [7].
The definition of Rewrite and Replace in Implementations is strongly linked to the implementations with the
same names of the Java Junior framework [21]. The
use of waiting queues has appeared in the implementation of Junior,
called Simple5, which
has been proposed by Laurent Hazard to deal with large number
of parallel components and events. The Direct semantics is
strongly inspired from it.
Rejo is a language which is proposed for high-level reactive
programming in a Java based language. Rejo is implemented on top of
Junior and thus can benefit from the various implementations of it.
As opposite to SugarCubes and Junior, standard Java code can be freely
mixed with reactive code. Rejo also introduces primitives for
migration of reactive code, implemented using the serialization and
the RMI mechanisms of Java.
|
9.3 Approaches based on Decomposition
|
Chores and Filaments
Chores [16] and filaments [26] are small pieces of code that do not have private stack
and are never preempted. Chores and filaments are designed for
fine-grain parallelism programming on shared-memory machines. Chores
and filaments are completely executed and cannot be suspended nor
resumed. Generally, a pool of threads is devoted to execute them.
Chores and chunk-based techniques are described in details in the
context of the Java language in [15] and [22]. Automata in FairThreads are close to chores and filaments, but
give programmers more freedom for direct coding of states-based
algorithms. Automata are also related to mode automata [27] in which states capture the notion of a running
mode in the context of the synchronous language Lustre [19].
Cohorts and Staged Computation
Cohort scheduling [25] dynamically reorganizes series
of computations on items in an input stream, so that similar
computations on different items execute consecutively. Staged
computation intends to replace threads. In the staged model, a
program is constructed from a collection of stages and each stage has
scheduling autonomy to control the order in which operations are
executed. Stages are thus very close to instants of FairThreads and cohort
scheduling looks very much like cooperative scheduling. In the staged
model, emphasis is put on the way to exploit program locality by
grouping similar operations in cohorts that are executed at the same
stage; in this way, cohorts and staged computations fall in the
family of data-flow models.
5: this is an ironic name...
|