|
|
One first gives an overview of the language. Then, the basic
notions of modules, threads, schedulers, events, and atomic and non-atomic
instructions are presented. Finally, native modules are considered.
|
2.1 Overview of the Language
|
Modules and Threads
Modules are the basic units of the language. The syntax is based on C
and modules are defined in files that can also contain C code.
Threads are created from modules. A thread created from a module is
called an instance of it. A module can have parameters which
define corresponding parameters of its instances. Arguments provided
when an instance is created are associated to these parameters. A
module can also have local variables, new fresh instances of which are
automatically created for each thread created from it.
Instructions
The body of a module is basically a sequence of instructions executed
by its instances. There are two types of instructions: atomic
instructions and non-atomic ones. Atomic instructions are run
in one single step by the same processor. Usual terminating C code
belongs to this kind of instructions. Another example of atomic
instruction is the generation of an event, described later, which is
broadcast to all the threads.
Execution of non-atomic instructions may need several steps up to
completion. This is typically the case of the instruction which waits
for an event to be generated. Execution steps of non-atomic
instructions are interleaved, and can thus interfere during
execution. Note that all the execution steps of a non-atomic
instruction may not be necessarily executed by the same processor.
Schedulers
The basic task of a scheduler is to control execution of the threads
that are linked to it. The scheduling is basically
cooperative: linked threads have to return the control to the
scheduler to which they are linked, in order to let other threads
execute. Leaving the control can be either explicit, with the
instruction cooperate, or implicit, by waiting for an event
which is not present.
All linked threads are cyclically considered in turn by the scheduler
until all of them have reached a cooperation point (cooperate, or waiting instructions). Then, and only then, a new
cycle can start. Cycles are called instants. Note that the
same thread can receive the control from the scheduler several times
during the same instant; this is for example the case when the
thread waits for a first event which is generated by another
thread, later in the same instant. In this case, the thread receives
the control a first time and then blocks, waiting for the
event. The control goes to the others threads, and returns back to
the first thread after the generation of the event.
A schedulers define some kind of automatic synchronization which
forces the threads linked to it to run at the same pace: all the
threads must have finished their execution for the current instant,
before the next instant can start.
The order in which threads are cyclically considered is always the
same: it is the order in which they have been linked to the
scheduler. This leads to deterministic executions, which are
reproducible. Determinism is of course an important point for
debugging.
At creation, each thread is linked to one scheduler. There exists an
implicit scheduler to which threads are linked by default when no
specific scheduler is specified. Several schedulers can be defined
and actually running in the same program. Schedulers thus define synchronized areas in which threads execute in cooperation.
Schedulers can run autonomously, in a preemptive way under the
supervision of the OS.
During their execution, threads created from special modules, called
native modules, can unlink from the scheduler to which they
are currently linked, and become free from any scheduler
synchronization. Such free threads are run by kernel threads of the
system. Of course, native modules and native threads have a meaning
only in the context of a preemptive OS.
Memory Mapping
Three kinds of variables exist in Loft:
- Global variables that are C global variables shared by all the
threads. These variables are placed in the shared memory in which the
program executes.
- Local variables that are instances of local variables of
modules. These variables are local to threads. Their specific
characteristic is that their value is preserved across instants: they
have thus to be stored in the heap.
- Automatic variables which are defined in atomic instructions,
and which are automatically destroyed when the atomic instruction in
which they appear is left. The value of an automatic variable is
not preserved from one instant to the next. As in C, automatic
variables can be stored in registers or in the stack.
Note that non-native threads need a stack only for execution of their
atomic instructions. Indeed, atomic instructions cannot be preempted
during execution, by definition. Thus, in this case, the stack is
always in the same state at the beginning and at the end of the
execution of each atomic instruction. Thus, the content of the stack
needs not to be saved when a context switch occurs. The situation is
of course different for native threads: because they can be preempted
arbitrarily by the OS, they need a specific stack, provided by the
native thread in charge of running them.
Communication
The simpler way for threads to communicate is of course to use shared
variables. For example, a thread can set a boolean variable to
indicate that a condition is set, and others threads can test the
variable to know the status of the condition. This basic pattern works
if all threads accessing the variable are linked to the same
scheduler. Indeed, in this case atomicity of the accesses to the
variable is guaranteed by the cooperativeness of the scheduler. A
general way to protect a data from concurrent accesses is thus to
associate it with one unique scheduler to which threads willing to
access the data should first link to.
However, this solution does not work if some of the threads are
non-native and belong to different schedulers or are unlinked. This is
actually the standard situation in concurrent programming, where
protection is basically obtained with locks. Standard POSIX mutexes
can be used for this purpose.
Events, described in the next section, give threads an other different
means of communication.
Events
Events are synchronizing data basically used by threads to avoid
busy-waiting on conditions. An event is created in a scheduler which
is in charge of it during all its lifetime. An event is either present
or absent during each instant of the scheduler which manages it. It is
present if it is generated by the scheduler at the beginning of the
instant, or if it is generated by one of the thread executed by the
scheduler during the instant; it is absent otherwise. The presence
or the absence of an event can change from an instant to another, but
it cannot change during the course of an instant: all the threads
always "see" the presence or the absence of an event in the same way,
independently on the order in which they are scheduled. This is what
is meant by saying that events are broadcast.
Values can be associated to event generations; they are collected
during each instant and are available only during it.
Implementation
The basic implementation of Loft is build on top of a C library of
native threads. Each scheduler and each instance of a native module is
implemented as a native thread. Threads which are instances of
non-native modules do no need the full power of a native thread to
execute. Actually, they don't need any specific stack as they can use
the one of the native thread of the scheduler to which they are
linked. In this way, the number of native threads can be limited to a
minimum. This is important when a large number of concurrent
activities is needed, as the number of native threads that can be
created in systems is usually rather low.
Unlinked threads and schedulers can be run in full parallelism, by
distinct processors. Programs can thus take benefit of SMP
architectures, and be speed-up by multiprocessors.
Note that one gets program structures that conform to the so-called
M:N architectures: M linked threads and N schedulers running them. An
important point is that these architectures become programmable directly at language level, and not through the use of
a library (as for example in the Solaris system of Sun).
Modules are templates from which threads are created. A thread created
from a module is called an instance of it. A thread is always created
in a scheduler which is initially in charge of executing it. Modules
are made from atomic and non-atomic instructions that are defined in
the next sections.
A module can have parameters which define corresponding parameters of
its instances. Arguments provided when an instance is created are
associated to these parameters. A module can also have local
variables, new fresh instances of which are automatically created for
each thread created from it.
The syntax of Loft is based on C and modules are defined in files
that can also contain C code. The syntax of modules is:
module <kind> <name> ( <params> )
<locals>
<body>
<finalizer>
end module
- <kind> is the optional
native keyword. The case of
native modules is considered in section Native Modules.
- <name> is the module name; it can be any C identifier.
- <params> is the list of parameters; it is empty if
there is no parameter at all.
- <locals> is the optional list of local variables
declarations. This list begins with the keyword
local.
- <body> is a sequence of instructions defining the module
body.
- <finalizer> is an optional atomic instruction executed
in case of forced termination (instruction
stop). This part
begins with the keyword finalize.
As example, consider the module trace defined by:
module trace (char *s)
while (1) do
printf ("%s\n",local(s));
cooperate;
end
end module
This module is a non-native one and it has a parameter which is a
character string. The body is reduced to a single while
loop (actually, an infinite one) considered in section Loops. At each instant, the loop prints the message in
argument and cooperates. Note the presence of the do and
end keywords around the loop body; indeed, as in Loft
"{" and "}" are used to delimit atomic
instructions (see C Statements), one needs a
different notation for loop bodies.
The parameter s is actually a local variable which is passed
at creation to the instances of trace. In Loft, all
accesses to local variables, and thus also to parameters, must be of
the form local(...) (local is actually a macro).
2.2.1 Local variables
Threads can have local variables which keep their values across
instants. These are to be distinguished from static variable which are
global to all the threads, and from automatic variables which loose
their values across instants.
Let us return to the previous module trace and suppose that
one wants to also print the instant number. A first idea would be to
define a variable inside the atomic instruction:
module trace (char *s)
while (1) do
{
int i = 0;
printf ("%s (%d)\n",local(s),i++);
}
cooperate;
end
end module
This is not correct because the variable i is allocated in
the stack at the beginning of the atomic instruction, and vanishes at
the end of it. Thus, a new instance of the variable is used at each
instant.
A solution would be to declare a global C variable to store the
instant number:
int i = 0;
module trace (char *s)
while (1) do
printf ("%s (%d)\n",local(s),i++);
cooperate;
end
end module
This solution produces a correct output. However, i is a
global variable shared by all instances of trace. A local
variable should be used if one wishes that each instance owns a
distinct variable:
module trace (char *s)
local int i;
{local(i) = 0;}
while (1) do
printf ("%s (%d)\n",local(s),local(i)++);
cooperate;
end
end module
Note that local variables must always be accessed using the form
local(...). This allows one to access in the same context a
local variable and a global or automatic one having the same name.
2.2.2 Threads
Threads are instances of modules. Threads which are instances of a
module m are created using the function m_create
which returns a new thread. Threads are of the pointer type thread_t. Note that, as in many C APIs, all types defined in
Loft have their name terminated by "_t". Arguments given
to m_create are passed to the created instance (as in C,
arguments are passed by value).
For example, the following atomic instruction creates two instances of
the previous module trace:
{
trace_create ("first thread");
trace_create ("second thread");
}
The output is:
first thread (0)
second thread (0)
first thread (1)
second thread (1)
first thread (2)
second thread (2)
...
Several points are important:
- Threads are created in the implicit scheduler which
is automatically created and started in all program (see Schedulers).
- Threads are automatically started. This is a difference with
Java in which threads have to be explicitly started.
- Threads are always executed in the same order, which is the
order of their creation. Thus, the previous output is the only one
possible.
It is possible to create a thread in a specific scheduler using a
creation function of the form create_in. For example, an
instance of trace is created in the scheduler sched by:
trace_create_in (sched,"a thread");
Threads are always incorporated in the scheduler at the beginning of
an instant, in order to avoid interferences with already running
threads. Moreover, if the current scheduler and the one in which the
thread is created are the same, then this instant is the next one.
The running thread is returned by the function self().
2.2.3 Finalizer
The finalizer of a module is an atom executed when an instance of the
module is forced to terminate by a stop instruction (defined
in Control over Threads). The finalizer is only
executed if the stopped thread is not already terminated. A typical use
of finalizer is for deallocation purposes, as in:
module m (...)
local resource_type resource;
{local(resource) = allocate ();}
...
{deallocate (local(resource));}
finalization
{deallocate (local(resource));}
end module
The allocated resource is deallocated in case of normal termination,
at the end of the module body. It is also deallocated if termination
is forced, as in this case the finalizer is executed.
An important point to note is that the thread executing a finalizer
is unspecified, as the instance considered is stopped. This means that
self cannot be safely used in finalizers.
2.2.4 Main Module
The entry point of a program is a module with name main. An
instance of it is automatically created in the implicit scheduler.
For example, the previous output could be produced by the execution of a
program with the following module main:
module main ()
trace_create ("first thread");
trace_create ("second thread");
end module
As in C, arguments can be given to the module main,
following the standard argc/argv convention.
The global program does not terminate when the main thread terminates:
it is the programmer's responsibility to end the program (typically,
by calling the exit function of C).
In this section, one considers the atomic instructions which terminate
at the same instant they start. We have already seen two examples in
previous sections: call to the C function printf, and
creation of instances of a module m with the m_create and m_create_in functions.
2.3.1 Schedulers
Creation
Schedulers can be created arbitrarily with the scheduler_create atomic instruction. They are of the type scheduler_t.
scheduler_t sched = scheduler_create ();
One instant of a scheduler is got by executing the acheduler_react atomic instruction.
scheduler_react (sched);
The scheduler_react function allows user to build
hierarchies of schedulers and to make them react following arbitrary
strategies.
Implicit and Current Schedulers
A scheduler, called the implicit scheduler, always exists
in every program. Two atomic instructions are available to get the
implicit scheduler and also the current scheduler, which is
the one to which the executing thread is linked (the NULL
value is returned if the thread is not linked to any scheduler).
scheduler_t implicit = implicit_scheduler ();
scheduler_t current = current_scheduler ();
2.3.2 Events
Events are basically variables with 3 possible values: present,
absent, or unknown. An event is created in a scheduler and managed by
it during all its lifetime. The value of an event is automatically
set to unknown at the beginning of each instant. There is a way for
the programmer to set an event to present (namely, to generate
it), but there is no way to set it to absent: only the system is able
to decide that an event is absent. Actually, the system automatically
decides that unknown events are absent when all threads have reached a
cooperation point and when there is no thread waiting for an event
which has been previously generated. The language definition assures
that, once unknown events are declared absent, all is finished for the
current instant (in particular, no event can be generated anymore
during the same instant). As consequence, one can consider that:
- Events are non-persistent data which lose their
presence status at the beginning of each instant.
- Events are broadcast: all threads always "see" their
presence/absence status in the same way, independently on the order in
which they are scheduled.
- Reaction to the absence of an event is always postponed to the
next instant.
The last point is a major difference with the synchronous approach, in
particular with the Esterel [9] language (see
Related Work for details).
Creation
A event is created in a scheduler whose instants determine its
presence/absence status. event_create creates an event in
the implicit scheduler. event_create_in creates an event in
the scheduler given as argument. Events are of the type event_t.
event_t evt1 = event_create ();
event_t evt2 = event_create_in (sched);
The first event is created in the implicit scheduler while the second one
is created in the scheduler sched.
Generation
Generation of an event makes it present in the scheduler in charge of
it (the one in which the event has been created). If the thread
running the generation is linked to the scheduler of the event, then
the generation becomes immediately effective. In this case, all the
threads waiting for the event will be re-scheduled during the same
instant, and thus will see the event as present. If the scheduler of
the event and the one of the thread are different, then the order to generate the event is sent to the scheduler of the
event. In this case, the event will be generated later, at the beginning of
the next instant of the target scheduler. Note that this can occur at
an aritrary moment if the target scheduler is run asynchronously by a
dedicated native thread.
A value can be associated to an event generation; in this case one
speaks on a valued generation of the event; in the other
case, the generation is said to be pure. The value must be of
a pointer type, or of a type that can be cast to such a type. All the
values generated for a same event are collected during the instant and
are available during this instant using the get_value
non-atomic instruction (see section Generated Values).
A pure generation of a present (that is, already generated) event has
no effect. This is of course different for a valued generation: then,
the value is appended to the list of values of the event. Note that,
as for the presence/absence status, the list of values of an event is
automatically reset to the empty list at the beginning of each
instant.
generate (evt);
generate_value (evt,val);
The first call is the pure generation of the event evt. The
second call generates the same event, but with the value val. Note that a valued generation with a null value is not
equivalent to a generation without any value.
2.3.3 Control over Threads
Three means for controlling threads execution are provided: the way to
stop the execution of a thread which is thus forced to
terminate definitively; the way to suspend and resume the execution
of a thread. With these means, the user can design its own scheduling
strategies for controlling threads.
Stop
Execution of a thread is stopped with a call to the stop
instruction. To stop a thread means that its execution is definitively
abandoned. The effect of the stop instruction is to send to the
scheduler of the thread in argument the order to stop the thread. The
order will always be processed at the beginning of a new instant, in
order to avoid interferences with the other threads. If the executing
thread and the stopped threads are both linked to the same scheduler,
then the thread will be stopped at the beginning of the next
instant. As example, a thread can stop itself by:
stop (self ());
Note that the thread terminates its execution for the current instant
and is only effectively stopped at the next instant; the
preemption is actually a "weak" one.
Suspend and Resume
Threads can be suspended and resumed using the two atomic instructions
suspend and resume. Suspension of a thread means
that its execution is suspended until it is resumed. Suspension and
resuming are orders given to the scheduler running the considered
thread, and are always processed at the beginning of new
instants. Like for stop, if the executing thread and the
concerned threads are both linked to the same scheduler, then the
thread execution status will be changed at the beginning of the next
instant.
suspend (main_thread);
resume (other_thread);
Orders are processed in turn. For example, the following sequence
of instruction has no effect as thread is immediately
resumed after being suspended:
suspend (thread);
resume (thread);
2.3.4 C Statements
Basic atomic instructions are standard C blocks, made of C statements
enclosed by "{" and "}". Of course, the C
statement must terminate and one must keep in mind that it should not
take too much time to execute it. Indeed, the others threads belonging
to the same scheduler cannot execute while the current thread has not
finish to execute it (see the discussion on this point in Necessity of Cooperation).
Almost any C code can syntactically appear in atomic instructions,
between "{" and "}". It is of the programmer's
responsibility to avoid the use of any statement that would prevent
the complete execution of an atomic instruction. For example, setjump/longjump should absolutely be avoided. However, some
forbidden statements are detected, and lead to program rejection. This
is the case of the C return statement. break
statements not enclosed in a C bloc are also forbidden, as well as
goto statements.
Procedure calls are considered as atomic instructions and can thus be
used directly without being put inside a C block. This is however just
a syntactic facility and the semantics of an atomic action made of a C
procedure call is exactly the one of the block containing it. For
example, the module main of Main Module
could be equivalently written:
module main ()
{
trace_create ("first thread");
trace_create ("second thread");
}
end module
|
2.4 Non-atomic Instructions
|
In this section, one considers the non-atomic instructions. As
opposite to atomic instructions, execution of non-atomic instructions
can last several instants.
2.4.1 Cooperate
The basic non-atomic instruction is the cooperate
instruction which returns the control back to the scheduler. When
receiving the control after a cooperate instruction, the
scheduler knows that the executing thread has finished its execution
for the current instant, and thus that is is not necessary to give it
back the control another time during the instant. When the thread
will receive the control in a future instant, the cooperate
instruction terminates and passes the control in sequence. Execution
of a cooperate instruction thus needs two instants to
complete.
2.4.2 Await
Execution of an await instruction suspends the executing
thread until the event is generated. There is of course no waiting at
all if the event is already present. Otherwise, the waiting can just
take a portion of the current instant, if the awaited event is
generated later in the same instant, by a thread scheduled later;
the waiting can also last several instants, or can even be infinite,
if the awaited event is never generated.
await (event);
There is a way to limit the time during which the thread is suspended
waiting for an event. The limitation is expressed as a number of
instants. The thread is resumed when the limit is reached. Of course,
the waiting ends, as previously, as soon as the event is generated
before reaching the limit. For example, the following instruction
suspends the executing thread at most 10 instant, waiting for the
event e.
await (e,10);
After resuming, one can know if the limit was exceeded or if the event
has been generated before the limit was reached, by examining the
value returned by the predefined function return_code ():
ETIMEOUT means that the limit has been
reached.
OK means normal termination because the awaited event
is generated.
For example, the following code tests the presence of an event during
one instant:
await (e,1);
{
if (return_code () == ETIMEOUT)
printf ("was absent");
else
printf ("is present");
}
Note that the message "was absent" is printed at the instant
that follows the starting of the waiting, while "is present"
is printed at the same instant. Reaction to the absence of an event
(here, the printing action) cannot be immediate, but is always
postponed to the next instant.
The value returned by return_code () concerns the last
non-atomic instruction executed. For example, in the following code,
the printed messages concern f, not e:
await (e,1);
await (f,1);
{
if (return_code () == ETIMEOUT)
printf ("f was absent");
else
printf ("f is present");
}
2.4.3 Join
The join instruction suspends the executing thread until
another one, given as argument, has terminated; this is called
joining the thread. Note that there are actually two ways for
a thread to terminate: either because execution has returned, or
because the thread has been stopped.
As for await, there is a possibility to limit the time
during which the thread is suspended, and the return_code
function is used in the same way to detect if the limit was reached.
join (th1);
join (th2,10);
The first instruction waits unconditionally for the termination of th1,
while the second waits at most 10 instants to join th2.
2.4.4 Loops
There are two kinds of loops: while loops, that cycle while
a boolean condition is true, and repeat loops that cycle a
fixed number of times. There is no equivalent of a for loop,
as such loops would need in most cases an associated local
variable; for loops are thus, when needed, to be
explicitly coded.
While
While loops are executing their bodies while a boolean condition is true.
while (1) do
printf ("loop!");
cooperate;
end
The value of the condition is only considered at the first instant and
when the body terminates. For example, the following loop never
terminates, despite the fact that the condition is false at some
instants:
{local(i) = 1;}
while (local(i)) do
{local(i) = 0;}
cooperate;
printf ("loop!");
cooperate;
{local(i) = 1;}
end
Instantaneous loops are loops with a non-cooperating body. This is for
example the case of:
while (1) do
printf ("loop!");
end
Instantaneous loops should generally be avoided as they forbid
execution of the others threads (see
Necessity of Cooperation).
Nevertheless, they can be useful in unlinked threads,
or when the executing thread is the only one run by the scheduler
(which is a rather special situation, indeed).
Repeat
A repeat loop executes its body a fixed number of times. It
could be coded with a while loop and a counter implemented
as a local variable; the repeat instruction avoids
the use of such a local variable.
repeat (10) do
printf ("loop!");
cooperate
end
The expression defining the number of cycles is evaluated when the
control reaches the loop for the first time.
2.4.5 If
The if statement can be used in atomic instructions as other
standard C statements. However, when it is used in this context, both
then and else branches must be atomic
instructions. A non-atomic version of the if is
available. The syntax is:
if (<expression>) then <instruction> else <instruction> end
For example, the instruction of Await, which
tests for the presence of e during the current instant, can
be equivalently written as:
await (e,1);
if (return_code () == ETIMEOUT) then
printf ("was absent");
else
printf ("is present");
end
Both then and else branches are optional. The
boolean expression exp is evaluated once, when the control
reaches the if for the first time. Its value determines
which branch is chosen for execution. The chosen branch is then
executed up to completion, which can takes several instants, as it can
be non-atomic.
For example, the following instructions prints at the next instant
the value exp has at the current instant:
if (exp) then
cooperate;
printf ("true!");
else
cooperate;
printf ("false!");
end
2.4.6 Return
The return statement of C cannot be used in atomic
instruction, as it would prevent the instruction to
terminate. However, it can be used as a non-atomic instruction to
force the termination of the executing thread. For example, the
following module terminates when the boolean expression exp
becomes true:
module m ()
while (1) do
if (exp) then return; end
cooperate;
end
end module
Note that, as the return statement is forbidden in atomic
instructions, the following module is incorrect:
module bug ()
while (1) do
{if (exp) return;}
cooperate;
end
end module
2.4.7 Halt
The halt instruction never terminates. It is equivalent to:
while (1) do cooperate; end
Its basic use is to block the execution flow, as in:
if (!exp) then
generate (error);
halt;
end
...
In this code, the if instruction tests exp and
forbids the control to pass in sequence if it is false. In this case,
an event is generated which should be used by an other thread to
recover from this situation.
2.4.8 Generated Values
The get_value instruction is the means to get the values
associated to an event by the valued generations of it. The values are
indexed and, when available, returned in a variable of type void**. The instruction get_value (e,n,r) is an attempt
to get the value of index n, generated for the event e during the current instant. If available, the value is assigned
to r during the current instant; otherwise, r
will be set to NULL at the next instant, and the function
return_code () will return the value ENEXT.
For example, the following instruction is an attempt to get the first
value of evt (for simplicity, values are supposed to be of type
int):
get_value (evt,0,res);
{
if (return_code () == ENEXT) printf ("there was no value! ");
else printf ("first value is %d ", (int)(*res));
}
The following module awaits an event and prints all the values
generated for it:
module print_all_values (event_t evt)
local int i,int res;
await (local(evt));
{local(i) = 0;}
while (1) do
get_value (local(evt), local(i), (void**)&local(res));
if (return_code () == ENEXT) then return;
else
{
printf ("value #%d: %d\n", local(i), local(res));
local(i)++;
}
end
end
end module
Note that the module always terminates at the next instant. This
should not be surprising: one must wait for the end of the current
instant to be sure that all the values have been effectively got.
2.4.9 Run
A module can run another one, using the run non-atomic
instruction. The calling thread suspends execution when encountering
a run instruction. Then, an instance of the called module
is created with the arguments provided. Finally, the calling thread is
resumed when the instance of the called module terminates. Moreover,
a thread which is stopped retransmits the stop order to the thread it
is running, if there is one. Thus, the instance of a called module is
automatically stopped when the calling thread is.
run mod1 ();
run mod2 ("mod2 called");
In this sequence, an instance of mod1 is first
executed. When it terminates (if it does), then an instance of mod2 is executed with a string argument. Finally, the sequence
terminates when the last instance does.
2.4.10 Link
When created, a thread is always linked to a scheduler. During
execution, the thread can link to others schedulers, using the link instruction. The effect of execution the instruction link (sched) is to extract the executing thread from the current
scheduler and to add it to sched, in the state in which it
has left the current scheduler. Thus, after re-linking, the thread
will resume execution in the new scheduler. This can be seen as a
restricted migration of threads.
For example, the following module cycles between two schedulers. On
each scheduler, it awaits an event and then prints a message. Then, if
the two events are generated at each instant, the program prints
"Ping Pong" forever:
module play ()
while (1) do
link (sched1);
await (evt1);
printf ("Ping ");
link (sched2);
await (evt2);
printf ("Pong\n");
end
end module
Native modules only have meaning in the context of a preemptive OS as
instances of native modules should be run by native threads belonging
to the kernel. The presence of the native keyword just after
the keyword module defines the module as native. The unlink non-atomic instruction unlinks the instance of a native
module from the scheduler to which it was previously linked. After the
unlink instruction, the thread is free from any
synchronization. However, an unlinked thread can always re-link to a
scheduler using the link non-atomic instruction (see Link).
The unlink instruction is specific to native modules:
programs where unlink instructions appears in non-native
modules are rejected at compile time.
When unlinked, instances of native modules are autonomous, which means
that they execute independantly of any scheduler, at their own
pace. For example, consider the following program which creates
two native threads instances of the same native module pr:
module native pr (char *s)
unlink;
while (1) do
printf (local(s));
end
end module
module main ()
pr_create ("hello ");
pr_create ("world!\n");
end module
The two lists of messages produced are merged in an unpredictable way
in the output: nondeterminism is introduced by unlinked instances of
native modules. Note that the loop in pr is
instantaneous; this is not a problem as the thread is
unlinked. The granularity of each thread is, however, under the
dependance of the OS, which can be unacceptable in some situations
(see Granularity of Instants).
Native module are important for using standard blocking I/Os in a
cooperative context. For example, the following module uses the getchar function which blocks execution of the calling thread until
a character is read on the standard input:
module native AnalyseInput ()
unlink;
...
while (1) do
{
switch (getchar ()){
...
}
}
end
end module
The first instruction unlinks the thread from the current
scheduler. Then, the getchar function can be safely called
without any risk to block other threads.
The following module read_module implements a cooperative
read I/O, using the standard blocking read function. The
thread first unlinks from the scheduler, then performs the read, and
finally re-links to the scheduler:
module native read_module (int fd,void *buf,size_t count,ssize_t *res)
local scheduler_t sched;
{local(sched) = current_scheduler ();}
unlink;
{(*local(res)) = read (local(fd),local(buf),local(count));}
link (local(sched));
end module
Note that the pattern suggested by this example is a very general one,
useful to reuse code which was not designed to be run in a cooperative
context.
|