|
|
Annex B: LOFT Reference Manual
|
|
Loft is an extension of C for concurrent and parallel programming.
Basic units of concurrency are threads which are created as instances
of modules and are run under the control of schedulers. Threads can
synchronize and communicate using broadcast events. Threads linked to
the same scheduler run in a cooperative way, leading to deterministic
systems. Threads can dynamically change their linking to
schedulers. Moreover, special native threads have the possibility to
stay unlinked from any scheduler, becoming then autonomous. Unlinked
threads can be executed in real parallelism.
Loft code is a mix of standard C code and of modules. Loft code
is first preprocessed (typically by the gcc -E command),
then translated into C, and finally compiled by the C compiler in
order to get executable code.
Modules are templates from which threads, called instances,
are defined. Module definitions start whith the keyword module and terminate with end module. The syntax of
modules is:
module_definition:
module kind module_name (params)
locals
inst
final
end module
A module is native when the keyword native follows
module. Native modules should only be used in programs run
by a preemptive operating system (Linux for example). Instances of a
native module must be implemented as kernel threads. Instances of
non-native module do not need specific kernel threads to execute (they
can use the one of the scheduler to which they are linked).
kind: native | /*empty*/
The module name is an identifier or the keyword main (this
case is considered in section Main Module).
module_name: identifier | main
Parameters in params and variables defined in locals
are considered in section Variables.
The body inst of the module is an instruction (usually, a
sequence of instructions) which is executed by the threads instances
of the module. Instructions are considered in section Instructions.
The finalizer is an optional atomic instruction which is executed in
case of forced termination; the executing thread of finalizers is
left unspecified.
finalizer: finalizer atomic | /*empty*/
12.1.1 Extern Modules
Modules defined in others files, or later in the same file, can be
declared using clauses of the form:
extern_modules: module identifier, ... , identifier ;
12.1.2 Main Module
A program containing a module named main can be directly
executed. The parameters of main must follow the argc/argv conventions of C. The translation of the main
module, first creates a new instance of the module and an implicit
scheduler, then adds the new thread in the implicit scheduler, and
finally makes the implicit scheduler react cyclically.
When no main module is defined, a function C with the name
main must be defined, as usual in C. In this case, it must
call the function loft_initialize in order to create the
implicit scheduler.
loft_initialize: loft_initialize () ;
There are 3 distinct kinds of variables:
- Global variables declared outside module
definitions. These variable are the standard global variables of C.
- Automatic variables declared in blocks of C instructions (of
the form
{...}). These variables can appear in declarations
of C functions, or in atomic instructions, in module
definitions. Automatic variables are allocated when the control enters
the block in which they are declared, and destroyed when the block is
left.
- Parameters and local variables declared in modules. Each
instance of a module has its own copy of these variables. Their values
are preserved during the passing of instants.
Thus, concerning memory management, Loft basically differs from C
by the presence of variables of kind 3, which are local to threads and
maintain their value between instants.
12.2.1 Types of Local Variables and Parameters
Types of parameters and local variables can be:
- Basic types (for example,
int).
- Named types (defined using
typedef).
- Pointer or double pointer types on the previous types.
params: defvar, ..., defvar | /*empty*/
defvar:
type identifier
| type * identifier
| type * * identifier
type: basic_type | identifier
locals: local defvar, ... , defvar | /*empty*/ ;
Remark: the restriction on the types of parameters and local variables
is introduced to simplify the implementation and should be removed in
future versions of the language.
12.2.2 Access to Local Variables and Parameters
Local variables and parameters must always be explicitly tagged by the
keyword local to distinguish them from global or automatic
variable with same names: all uses of a local variable or parameter
x must be of the form local(x).
Threads are concurrent entities created from modules and run by
schedulers. Threads are of the type thread_t.
12.3.1 Thread Creation
New threads instances of a module m are returned by the C
function m_create which has the same parameters as m. The new threads are linked to the implicit scheduler.
With the function m_create_in, new created threads are
linked to a scheduler given as first parameter (the other parameters
are passed to the thread in the standard way).
thread_creation:
identifier_create (exp, ... , exp)
| identifier_create_in (exp, exp, ... , exp)
Threads linked to a scheduler during one instant start running only at
the beginning of the next instant.
12.3.2 Thread State
The state of a thread is composed of two parts: the execution state
and the binding state. The possible values for the execution state of
a thread are:
- Ready to execute.
- Terminated. A thread becomes terminated when it has finished
to execute its body. A thread can also be forced to terminate when
it is stopped.
- Suspended. A suspended thread must be resumed before it can
continue to execute.
The possible values for the binding state are:
- Linked to a scheduler. When linked to a scheduler, a
thread must cooperate with the others threads linked to the same
scheduler, and its execution is under the control of the scheduler.
- Unlinked. This is only possible for instances of native
modules. Unlinked threads are autonomous and run at their own pace.
Initially, that is when created, a thread is ready to execute and
linked to the scheduler in which it is created.
12.3.3 Thread Execution
Unlinked threads are supposed to be executed by kernel threads. An
unlinked thread run autonomously, until it reaches a link
instruction which changes its linking state.
A linked thread resumes execution of its body when it receives the
control from the scheduler to which it is linked. As the scheduling is
cooperative, the resumption is always supposed to finish after a
finite delay. At the end of the resumption, the thread returns the
control back to the scheduler and signals it with one of the following
values:
- Terminated. The thread terminates when it completes the last
instructions it has to run.
- Blocked. The thread is blocked either because it is awaiting an
unknown event (
await), or because it tries to get an event
value which is not available (get_value).
- Cooperating. The thread is not terminated but has finished to
execute for the current instant.
12.3.4 Return Code and Self
Threads have a return code set during the execution of certain
non-atomic instructions (namely, await, join, and
get_value). The return code can be OK, ETIMEOUT, or
ENEXT. The return code of the executing thread, set by the last
executed non-atomic instruction, is returned by the return_code function:
thread_return_code: return_code ()
The executing thread is returned by the self function:
self: self ()
12.3.5 Thread Deallocation
The memory allocated to a thread can be recovered using the thread_deallocate function:
thread_deallocation: thread_deallocate (exp) ;
This is the programmers's responsability to perform correct
deallocation of threads.
A scheduler defines instants during which all ready threads linked to
it are run in a cooperative way. Schedulers are of type scheduler_t. New schedulers can be created with the function scheduler_create:
scheduler_creation: scheduler_create ()
An implicit scheduler should exist in all program. It is returned by
the function implicit_scheduler.
During execution, a linked thread can have access to the
current scheduler running it, with the function current_scheduler.
scheduler_access:
implicit_scheduler ()
| current_scheduler ()
12.4.1 Instants
A phase of a scheduler consists in giving the control in turn
to all the ready threads which are linked to it. The order in which
the threads receive the control is the order in which they have been
linked to the scheduler. During an instant, the scheduler executes
cyclically a serie of phases, up to a situation where no thread
remains blocked. Then, the scheduler decides that the current instant
is finished, and it can then proceed to the next instant. Thus, at the
end of each instant, all ready threads either have terminated or have
cooperated.
The scheduler decides that the current instant is finished when, at
the end of a phase, there is no possibility for any blocked thread to
progress: no awaited event has been generated, and no new value has
been produced which could unblock a thread trying to get it.
One instant of a scheduler is executed by the scheduler_react function.
scheduler_react: scheduler_react (exp) ;
In scheduler_react(exp), exp should evaluate to a
scheduler previously created by scheduler_create.
12.4.2 Scheduler Deallocation
The memory allocated to a scheduler can be recovered using the scheduler_deallocate function:
scheduler_deallocation: scheduler_deallocate (exp) ;
This is the programmers's responsability to perform correct
deallocation of schedulers.
Events are used by thread to synchronize and to communicate. Events
are of type event_t. An event is always created in a
specific scheduler which is in charge of it during all its
lifetime. The function event_create returns an event created
in the implicit scheduler. The function event_create_in
returns an event created in the scheduler in argument.
event_creation:
event_create ()
| event_create_in (exp)
At each instant, events have a presence status which can be present,
absent, or unknown. All events managed by a scheduler are
automatically reset to unknown at the beginning of each new instant
(thus, events are non-remanent data). All events which are unknown
become absent when the scheduler decides to terminate the current
instant (see Instants).
12.5.1 Generate
There are two ways for an event to be present during one instant:
- There were an order to generate it received by the
scheduler during execution of the previous instant and coming from a
thread which is not linked to the scheduler.
- It is generated during the current instant by one of the
threads linked to the scheduler.
One can associate values to generations of events. All values
associated to the generations of the same event during one instant are
collected in a list, as they are produced. They are available only
during the current instant, using the get_value instruction
(Get Value).
generate:
| generate (exp) ;
| generate_value (exp, exp) ;
The execution of generate(exp) starts by the evaluation of
exp which should return an event e. If the executing
thread is unlinked or if the scheduler sched in charge of e (the one in which e has been created) is different from
the one of the thread, then the order is sent to sched to
generate e at the beginning of its next instant. Otherwise,
e is immediately generated in sched.
The execution of generate(exp,exp) starts by the evaluation
of the two expressions in argument. The first one should return an
event e, and the second one a value v of a pointer
type (void*). The execution is the same as the one of the
previous call, except that v is added as last element to the
list of values associated to e at the instant where e
is generated.
12.5.2 Event Deallocation
The memory allocated to an event can be recovered using the event_deallocate function:
event_deallocation: event_deallocate (exp) ;
This is the programmers's responsability to perform correct
deallocation of events.
Instructions are binding instructions, atomic instructions, non-atomic
instruction, or sequences of instructions:
inst:
bind
| atomic
| non_atomic
| inst ... inst
A thread starts to execute a component of a sequence as soon as the
execution of the previous component is completed.
|
12.7 Binding Instructions
|
There are two binding instructions:
bind:
unlink ;
| link (exp) ;
12.7.1 Unlink
The unlink
instructions should only appear in native modules. It has no effect
if the executing thread is already unlinked. Otherwise, the thread
executing the instruction returns back the control to the scheduler,
signaling it that it cooperates. In this case, the thread is removed
from the scheduler which thus will never consider it again (except, of
course, if the thread re-links to it later).
As soon as the thread has returned the control back to the scheduler,
it starts running in an autonomous way.
12.7.2 Link
A thread executing
link(exp) first evaluate exp which should return a
scheduler sched. If the thread is already linked, it unlinks
from the scheduler to which it is linked, and then waits for sched to give it the control. If the thread is unlinked, it just
waits for the control from sched. In all cases, sched
will resume execution of the thread, as it does for new created
thread, at the beginning of the next instant.
Atomic instructions have the form of blocks of C code or of C function
calls. They can be executed by linked and unlinked threads, with the
same semantics, which is actually the one they have in standard
C. However, when executed by a linked thread, execution of an atomic
instruction is instantaneous, which means that it terminates in the
same instant it is started.
atomic:
{c-code}
| identifier (exp,..., exp) ;
| order
The previous calls of functions to create and manage threads,
schedulers, and events are considered as special cases of atomic
instructions.
Orders are given to schedulers to stop, suspend, or resume threads:
orders:
stop (exp) ;
| suspend (exp) ;
| resume (exp) ;
All orders received by a scheduler during one instant are
systematically processed at the beginning of the next instant (to
avoid interference with executing threads) in the order in which they
are issued.
12.8.1 Stop
The execution of
stop(exp) starts by the evaluation of exp which
should return a thread th. The effect of the call is undefined
if th is unlinked. Otherwise, the order to terminate th is sent to the scheduler to which it is linked.
12.8.2 Suspend
The execution of
suspend(exp) starts by the evaluation of exp which
should return a thread th. The effect of the call is undefined
if th is unlinked. Otherwise, the order to suspend th
is sent to the scheduler to which it is linked.
12.8.3 Resume
The execution of
suspend(exp) starts by the evaluation of exp which
should return a thread th. The effect of the call is undefined
if th is unlinked. Otherwise, the order to resume th
is sent to the scheduler to which it is linked. Resuming a thread
which is not suspended has no effect.
|
12.9 Non-atomic Instructions
|
Non-atomic instructions should only be executed by linked threads, and
their semantics is undefined when they are executed by unlinked
threads. Execution of non-atomic instructions can take several
instants to complete.
non_atomic:
cooperate;
| halt;
| return;
| await (exp);
| await (exp, exp);
| join (exp);
| join (exp, exp);
| get_value (exp, exp, variable);
| if (exp) then_branch else_branch end
| while (exp) do inst end
| repeat (exp) do inst end
| run identifier (exp, ..., exp);
then_branch: then inst | /*empty*/
else_branch: else inst | /*empty*/
12.9.1 Cooperate
A thread executing cooperate returns the control to the
scheduler, signaling it that it cooperates. If the thread regains
control in the future, it will resume execution in sequence of the
cooperate instruction.
12.9.2 Halt
A thread executing halt returns the control to the
scheduler, signaling it that it cooperates. If the thread regains
control in the future, it will re-execute the same halt
instruction. Thus, halt blocks the thread forever, without
never terminating it.
12.9.3 Return
A thread executing return returns the control to the
scheduler, signaling it that it terminates. Thus, it will never regain
control again from the scheduler.
12.9.4 Await
A thread executing await(exp) first evaluates exp.
The expression should evaluate to an event e. If e is
present, then the thread proceeds in sequence of the await
instruction. Otherwise, if the current instant is finished (which
means that e is absent), then the thread returns the control
to the scheduler, signaling it that it cooperates. If the thread
regains control in some future instant, execution will restart at the
same place, waiting for the same event e. If the current
instant is not finished, then the thread returns the control to the
scheduler, signaling it that it is blocked. When the thread will
regain the control, it will, as previously, continue to test the
presence of e.
A thread executing await(exp,exp) first evaluates the two
arguments. The first one should evaluate to an event e, and
the second one to an integer value k. Then, the thread behaves
as the previous instruction, but the waiting of e is limited
to at most k instants. If e is generated during the
next k next instants, then the return code of the thread is
set to OK. Otherwise, if e is still absent at the end of
the kth instant, then the thread returns the control to the
scheduler, signaling it that it cooperates ; moreover, the return
code of the thread is set to ETIMEOUT. In this case, the thread
will proceed in sequence when receiving the control back (just as the
cooperate instruction does).
12.9.5 Join
A thread executing join(exp) first evaluates exp.
The expression should evaluate to a thread th. If th
is terminated, then the thread proceeds in sequence of the join instruction. Otherwise, the thread behaves as if it was
awaiting a special event generated by the termination of th.
A thread executing join(exp,exp) first evaluates the two
arguments. The first one should evaluate to a thread th, and
the second one to an integer value k. Then, the thread behaves
as the previous instruction, but the waiting of the termination of
th is limited to at most k instants. The return code
of the thread is set to ETIMEOUT if the limit is reached, and it is
set to OK otherwise.
12.9.6 Get Value
A thread executing get_value(exp,exp,var) first evaluates
the two expressions in arguments. The first should return an event
e, and the second an integer k.
Then, the thread tests if there are at least k values
generated for e during the current instant. If it is the case,
the kth value is assigned to var, the return code of the
thread is set to OK, and the thread proceeds in sequence.
Otherwise, if the current instant is not finished, then the thread
returns the control to the scheduler, signaling it that it is
blocked. When the thread will regain the control, it will, as
previously, continue to test the existence of the kth value.
If the current instant is finished, then the return code of the thread
is set to ENEXT, and the thread returns the control to the scheduler,
signaling it that it cooperates. When the thread will regain control,
it will proceed in sequence (just as a cooperate instruction
would do).
12.9.7 If
A thread executing if(exp)then i else j end first evaluates
exp. If the evaluation returns true (a non-zero value) then
the thread switches to i, else it switches to j. If the chosen branch is empty, the thread proceeds in sequence
immediately.
12.9.8 While
A thread executing while(exp)do i end first evaluates exp. If the evaluation returns false (zero) then the thread
proceeds in sequence of the loop. Otherwise, the thread behaves as if
it was executing i, with one difference: when execution of
i terminates, then exp is re-evaluated and the
same process restarts: execution is left if evaluation returns false,
and otherwise i is re-executed. Thus, the thread cyclically
executes i while exp is true, exp being
evaluated at the first instant and, after that, only when i
terminates.
12.9.9 Repeat
thread executing repeat(exp)do i end first evaluates exp. The evaluation should return an integer value k. If
k is negative or equal to 0, then the thread proceeds in
sequence of the loop. Otherwise, the thread behaves as if it was
executing a sequence of k instructions i.
12.9.10 Run
A thread th executing run m(e1,...,en) first creates
a new instance of the module m with e1,...,en as
arguments, and then joins the new created thread. Moreover, the new
created thread is stopped if th is.
|