|
|
One has defined Loft, a language which extends C to concurrent
and parallel programming in a shared memory context. The main
questions to which Loft proposes answers can be listed as follows:
how synchronous and asynchronous executions can be mixed together in
an unified framework? How system architectures which are basically
cooperative can benefit from parallelism offered by multiprocessor
machines? How to conciliate concurrency and determinism? What
compromises should be accepted in order to get a powerful enough
programming, while staying in a simple and relatively safe context?
The answers in Loft rely on several aspects related to the underlying
programming model, to semantics concerns, to implementation issues, and to
design choices.
Programming Model
In Loft, the units of concurrency are threads which are defined as
instances of modules. There are basically two kinds of threads:
threads which are linked to a scheduler and threads which are
unlinked. A thread cannot be linked simultaneously to several
schedulers, but it can link to distinct schedulers during its
execution.
All the threads linked to a same scheduler are run in a cooperative
mode under the supervision of the scheduler. Moreover, they are
sharing events. The threads are run cyclically until all have either
cooperated or have reacted to events which are present. The current
instant is finished when a stable situation is found in which all the
events which are not present can be safely considered as absent. The
scheduler can then proceed to the next instant after having
incorporated in the system orders sent to it during the instant. These
orders can be orders to stop, suspend or resume threads, or to add new
created threads.
Several schedulers can be simultaneously present in the same Loft
program. Each scheduler defines a synchronous area in which threads
run at the same pace, because they share the same instants, and in
which events are broadcast, because all threads have exactly the same
information on the presence and the absence of events.
It is possible for some threads instances of native modules to run
autonomously, unlinked from any scheduler. When it is the case, these
threads behave exactly as standard native threads scheduled by the
preemptive operating system. However, unlinked threads still have the
possibility to link to a scheduler, and then to behave as a
cooperative thread. Of course, they can later on return in the
unlinked state if they want.
Several advantages of the programming model of Loft are to be
pointed out:
- Loft offers an unified framework in which both
cooperative and preemptive approaches can be used jointly. Actually,
in Loft, users have control on the way threads are scheduled.
Loft provides users with programming primitives allowing threads to
dynamically link to schedulers and to dynamically unlink from them.
This framework is flexible as the structure of schedulers can evolve
dynamically. It actually proposes N:M architectures, with the
advantage that there exist a syntax to deal with them (as opposite for
example with the threads of the Solaris system of Sun).
- Cooperative systems can be coded in a simple way, without the
need of locks to protect data. Moreover, instants give automatic
synchronizations that can greatly simplify programming in certain
situations. Linked threads have a precise and clear semantics. The
point is that systems exclusively made of threads linked to one unique
scheduler are completely deterministic. This simplifies reasonning
about program. It also makes debugging easier. Thus, in the
cooperative context, one gets a simple language for concurrent
programming which is deterministic and have a precise semantics.
- When a thread unlinks from a scheduler, it becomes an
autonomous native thread which can be run in real parallelism, on a
distinct processor. Schedulers can also be executed by native threads,
on distinct processors. Thus, Loft give the user access to
multiprocessing in a very simple way.
Semantics
Loft has a formal semantics. Actually the semantics is an
operational one which describes the steps that should be executed to
reach a result. The presence of a formal semantics is not anecdoctical
and is useful for at least two reasons: first, it give the exact
meaning of programs which can be much more complex than in traditional
programming, as a result of concurrency and of the new dimension
introduced by instants. The purpose of the semantics is to exactly
define what should be the execution of a program made of several
concurrent threads along the passing of instants. Second, variants of
the semantics are defined in order to model various aspects of the
execution. More precisely, a series of semantics variants defines
relatively small steps starting from the basic Rewrite semantics
and reaching the Direct semantics which is designed to be extremely
efficient. One can get strong confidence in each of these
steps, and thus see this whole process as a way to validate the
implementation. The presence of a formal semantics is in this respect
a means for a safer programming.
Implementation
The language has several implementations. The first one is a direct
translation in FairThreads which is an API of threads closely related to
Loft. The second implementation Rewrite, which serves as a
reference for the cooperative part of the language, is a direct
translation of the rewriting rules of the semantics. The Replace
implementation optimises the memory use, while the Optim
implementation optimizes the waiting of events, to avoid busy-waiting,
and can be used for embedded systems with few ressources.
To sum-up, the main characteristics of Loft are:
- Concurrent language based on C.
- Both cooperative and preemptive approaches mixable in the same
framework.
- Possibility of real parallelism (use of multiprocessors).
- Determinism of programs belonging to the cooperative part of
the language.
- Precise (formal) semantics defined for the cooperative part.
- Efficient implementation, usable for embedded systems.
Finally, one would say that the external syntax of Loft could be
subject to change in the future. This should not be shocking as, after
all, syntax is rather secondary compared to the programming model and to
the semantics.
One now considers possible topics for future work.
Reactive Instructions
In Loft, as in FairThreads, parallelism is only at top-level. Indeed,
there is no parallel construct which can be used at any level, as in
Esterel for example. Consider for example a statement of the form
(A || B);C, where || is the parallel operator. In
it, the parallel operator is not at the root of the syntax tree, but
on the left branch of a sequence instruction. In Loft one must use
indirect constructions for expressing parallelism at arbitrary levels
of nesting. The previous example could be for instance coded using a
join instruction to wait for the termination of both A and B. A possible extension of Loft would be to
introduce a deterministic parallel operator, as for example the one of
Reactive-C. Others constructs could also be added to the language;
for example, the until module of section Run could be directly introduced in the language as a preemption
instruction. One could also consider local events whose extend is
defined syntaxically by a language construct, as it is the case in
standard reactive programming, such as Junior.
Networking
A rather natural extension of Loft would be to interface it with
the network. Thus, distributed synchronous areas could be defined,
running on distinct machines. The difficulty is to give a way for a
thread to link to a distant machine. This is a kind of thread
migration that would open programming to systems based on agents.
Some open problems are raised by such an approach: what
exactly are the threads that can migrate and how are they dealing with
the memory? What is the syntax for migration? How migrating threads
can dynamically use the resources of a distant site? How can a site be
protected from dangerous migrating threads (for example, not
cooperating ones)?
Others Languages
Loft could be rather easily extended to C++. This would simplify
the code produced by the Loft translator as classes encapsulating
the local data of threads could be generated. Of course, other target
languages could also be considered.
As the others formalisms for reactive programming, Loft and FairThreads
are available under the Gnu public licence on the site http://www.inria.fr/mimosa/rp.
|