|
|
FairThreads is an alternative to standard threads, which is very close to
Loft. FairThreads is first presented; then some little examples are
given; finally, FairThreads is compared with Loft and with standard
POSIX threads.
The API of FairThreads is overviewed in this section. All functions are
presented, but some details, such as error codes, are for simplicity
not considered here. The API is summarized in the annex.
6.1.1 Creation
Schedulers
FairThreads explicitly introduces schedulers, of type ft_scheduler_t. Before being used, a scheduler must be created by
calling the function ft_scheduler_create.
In order to be executed, a scheduler must be started by a call to the
function ft_scheduler_start. Note that several schedulers
can be used without problem simultaneously in the same program. Each
scheduler is run by a dedicated native thread which gives the control
in turn to the threads linked to the scheduler.
Threads
Fair threads are of type ft_thread_t. The call ft_thread_create(s,r,c,a) creates a thread in the scheduler s. The thread is run by a dedicated native thread. The creation
becomes actual at the beginning of the next instant of s.
The thread is automatically started as soon as it is created. The
function r is executed by the thread, and the parameter
a is transmitted to it.
If stopped (by ft_scheduler_stop), the thread switches
execution to the function c to which a is also
transmitted.
Events
Events are of the type ft_event_t. An event is created by
calling the function ft_event_create which takes as
parameter the scheduler in charge of it.
Automata
Automata are fair threads of the type ft_thread_t created
with the function ft_automaton_create. The thread returned
by ft_automaton_create(s,r,c,a) is executed as an automaton
by the scheduler s, which means that it is run by the native
thread of the scheduler. The function r executed by the
automaton must be defined with the macro DEFINE_AUTOMATON.
6.1.2 Orders
Control of Threads
The call ft_scheduler_stop(t) gives to the scheduler which
executes the thread t the order to stop it. The stop will
become actual at the beginning of the next instant of the scheduler,
in order to assure that t is in a stable state when stopped.
The call ft_scheduler_suspend(t) gives to the scheduler
which executes t the order to suspend t. The
suspension will become actual at the beginning of the next instant of
the scheduler. The function ft_scheduler_resume is used to
resume execution of suspended threads.
Broadcast of Events
The function ft_scheduler_broadcast(e) gives to the
scheduler of the event e the order to broadcast it to all
the threads running in the scheduler. The event will be actually
generated at the beginning of the next instant of the scheduler. The
call ft_scheduler_broadcast_value(e,v) associates the value
v to e (v can be read using ft_thread_get_value).
6.1.3 Basic Primitives
Cooperation
The call ft_thread_cooperate() is the explicit way for the
calling thread to return control to the scheduler running it. The call
ft_thread_cooperate_n(i) is equivalent to a sequence of
i calls ft_thread_cooperate().
Termination
The call ft_thread_join(t) suspends the execution of the
calling thread until the thread t terminates (either
normally or because it is stopped). Note that t needs not to
be linked to the scheduler of the calling thread. With ft_thread_join_n(t,i) the suspension takes at most i
instants.
6.1.4 Managing Events
Generating Events
The call ft_thread_generate(e) generates the event e in the scheduler which was associated to it, when created. The
call ft_thread_generate_value(e,v) adds v to the
list of values associated to e during the current instant
(these values can be read using ft_thread_get_value).
Awaiting Events
The call ft_thread_await (e) suspends the execution of the
calling thread until the event e becomes
generated. Execution is resumed as soon as the event is
generated. With ft_thread_await_n (e,i), the waiting takes
at most i instants.
Selecting Events
The call ft_thread_select(k,array,mask) suspends the
execution of the calling thread until the generation of one element of
array which is an array of k events. Then, mask, which is an array of k boolean values, is set
accordingly. With ft_thread_select_n(k,array,mask,i), the
waiting takes at most i instants.
Getting Events Values
The call ft_thread_get_value(e,i,r) is an attempt to get the
ith value associated to the event e during
the current instant. If such a value exists, it is returned in r and the call immediately terminates. Otherwise, the value NULL
is returned at the next instant.
6.1.5 Linking
Link and Unlink
The call ft_thread_unlink() unlinks the calling thread
t from the scheduler in which it was previously
running. Then, t will no longer synchronize, instant after
instant, with other threads linked to the scheduler. Actually, after
unlinking, t behaves as a standard native thread.
The call ft_thread_link(s) links the calling thread to the
scheduler s. The calling thread must be unlinked when
executing the call. The linkage becomes actual at the beginning of the
next instant of s.
Locks
In presence of unlinked threads, locks can be needed to protect data
shared between unlinked and linked threads. Standard mutexes are used
for this purpose. The call ft_thread_mutex_lock(p), where
p is a mutex, suspends the calling thread until the moment
where p can be locked. The lock is released using ft_thread_mutex_unlock. Locks owned by a thread are automatically
released when the thread terminates definitively or when it is
stopped.
6.1.6 Automata
Automata are coded using macros. Here are the macros to define the
automaton structure:
-
AUTOMATON(aut) declares the automaton
aut.
-
DEFINE_AUTOMATON(aut) starts definition of the
automaton aut.
-
BEGIN_AUTOMATON starts the list of states.
-
END_AUTOMATON ends the list of states.
A state with number num starts with one of the following
macros:
-
STATE(num) introduces a standard state.
-
STATE_AWAIT(num,event) and STATE_AWAIT_N(num,event,delay) are states to await event.
-
STATE_JOIN(num,thread) and STATE_JOIN_N(num,thread,delay) are states to join thread.
-
STATE_STAY(num,n) is a state which keeps execution
in it for n instants.
-
STATE_GET_VALUE(num,event,n,result) is a state to
get the nth value associated to event.
-
STATE_SELECT(num,n,array,mask) and STATE_SELECT_N(num,n,array,mask,delay) are generalizing STATE_AWAIT and STATE_AWAIT_N to an array of events of
length n.
Going from one state to another one is done with the macros:
-
GOTO(num) blocks execution for the current
instant and sets the state for the next instant to be state num.
-
GOTO_NEXT blocks execution for the current instant
and sets the state for the next instant to be the next state in the
list of states.
-
IMMEDIATE(num) forces execution to jump to state
num which is immediately executed.
-
RETURN immediately terminates the automaton.
Finally, the following macros define some special variables:
-
SELF is the automaton.
-
LOCAL is the local data of the automaton.
-
SET_LOCAL(data) sets the local data of the
automaton.
-
ARGS is the argument which is passed at creation to
the automaton.
-
RETURN_CODE is the error code set by the macros run
during automaton execution.
6.1.7 Miscellaneous
Current Thread
The calling thread is returned by ft_thread_self().
Current Scheduler
The scheduler of the calling thread is returned by ft_thread_scheduler().
Pthread
The call ft_pthread(t) returns the native pthread which
executes the fair thread t. This function gives direct
access to the Pthreads implementation of FairThreads. In the rest of the
paper, native thread and pthread will be considered as synonymous.
Exiting
The function ft_exit is equivalent to pthread_exit. The basic use of ft_exit is to terminate
the pthread which is running the function main, without
exiting from the process running the whole program.
One only gives two small examples just to show the programming style
in FairThreads. The first example is a complete executable programs, and the
second is an automaton.
6.2.1 Complete Program
The following code is a complete example of FairThreads program, made of two
threads linked to the same scheduler.
#include "fthread.h"
#include <stdio.h>
void h (void *id)
{
while (1) {
fprintf (stderr,"Hello ");
ft_thread_cooperate ();
}
}
void w (void *id)
{
while (1) {
fprintf (stderr,"World!\n");
ft_thread_cooperate ();
}
}
int main (void)
{
ft_scheduler_t sched = ft_scheduler_create ();
ft_thread_create (sched,h,NULL,NULL);
ft_thread_create (sched,w,NULL,NULL);
ft_scheduler_start (sched);
ft_exit ();
return 0;
}
The program outputs Hello World! cyclically. Note the call
of ft_exit to prevent the program to terminate before
executing the two threads. Execution of linked fair threads is
round-robin and deterministic: the two messages Hello and
World! are always printed in this order.
6.2.2 Automaton Use
The following automaton switches control between two threads,
according to the presence of an event. The automaton switch_aut has three states. The first state resumes the first
thread to run (initially, one assumes that both threads are
suspended). The switching event is awaited in the second state, and
the threads are switched when the event becomes present. The third
state is similar to the second, except that the threads are exchanged.
DEFINE_AUTOMATON (switch_aut)
{
void **args = ARGS;
ft_event_t event = args[0]
ft_thread_t thread1 = args[1]
ft_thread_t thread2 = args[2]
BEGIN_AUTOMATON
STATE (0)
{
ft_scheduler_resume (thread1);
}
STATE_AWAIT (1,event)
{
ft_scheduler_suspend (thread1);
ft_scheduler_resume (thread2);
GOTO(2);
}
STATE_AWAIT (2,event)
{
ft_scheduler_suspend (thread2);
ft_scheduler_resume (thread1);
GOTO(1);
}
END_AUTOMATON
}
The automaton behavior is actually the one of a thread
running the following function:
void switch_aut (void *arg)
{
void **args = arg;
ft_event_t event = args[0]
ft_thread_t thread1 = args[1]
ft_thread_t thread2 = args[2]
ft_scheduler_resume (thread1);
while (1) {
ft_thread_await (event);
ft_scheduler_suspend (thread1);
ft_scheduler_resume (thread2);
ft_thread_cooperate ();
ft_thread_await (event);
ft_scheduler_suspend (thread2);
ft_scheduler_resume (thread1);
ft_thread_cooperate ();
}
}
The two main differences between Loft and FairThreads concerns the ease
of programming and the expressiveness given by the existence of
private stacks.
6.3.1 Ease of Programming
The first main difference relies of course on the fact that Loft is
a language while FairThreads is an API. It indeed implies two very different
styles of programming. In Loft, one writes reactive programs which
are linked with standard C code through atoms. In FairThreads, one basically
writes C code in which some function calls are reactive
primitives. Thus, the reactive structure of Loft programs certainly
appears more clearly than in FairThreads programs.
Actually, in FairThreads native threads are the rule and the automata are
the exception, while it is the converse in Loft. The passage from
a thread to an automaton can need in FairThreads the complete rewriting of
the code in order to fit with the automata format. In Loft, the
passage from an automaton to a thread or vice-versa is extremely
simplified, and is actually concentrated in the keyword native. For example, the Loft module that corresponds to the
previous switch_aut automaton is:
module switch_aut (ft_event_t event,ft_thread_t thread1,ft_thread_t thread2)
resume (local(thread1));
while (1) do
await (local(event));
suspend (local(thread1));
resume (local(thread2));
cooperate;
await (local(event));
suspend (local(thread2));
resume (local(thread1));
cooperate;
end
end module
it produces code which is very similar to the previous automaton.
However, by adding the native keyword, the code produced
would be very close to the one of the corresponding fair thread.
The linking mechanism of Loft is a simplification of the one of
FairThreads as there is no need in Loft to be unlinked in order to be
able to link to another scheduler. Actually, when linking to a target
scheduler, the unlinking of the source scheduler is implicit in
Loft. The important point is that is does not implies that the
thread stays unlinked, which would need the use of a native thread.
The arguments of threads in FairThreads have to be passed through an unique
parameter of type void*. This complicates things when
several arguments have to be passed to a same thread. Actually, these
arguments have to be packed in one new structure whose reference is
passed to the thread. In case of an automaton, the arguments are
accessed with the macro ARGS.
An implicit scheduler is always present in Loft which is not the
case in FairThreads where there is no implicit main function which
would create it.
The local variable in Loft have to be explicitely declared as local in
Loft while they coincide with local C variables in FairThreads. This is
an aspect that is simpler in FairThreads than in Loft.
6.3.2 Private Stacks
FairThreads offers possibilities that do not exist in Loft and which are
related to the stacks. Actually, in FairThreads all the threads, except
automata, use their own private stack, as they are basically
pthreads. The opposite holds in Loft where threads, except
instances of native modules, do not need a private stack to execute.
The existence of a private stack allows to code functions that are not
tail-recursive. For example, consider the following recursive
function, which is not tail-recursive because a printing action occurs
after the recursive call:
void sum_aux (int n)
{
if (n == 0) { printf ("0"); return; }
ft_thread_cooperate_n (n);
sum_aux (n - 1);
printf ("+%d",n);
}
The execution exits after a call to the previous function:
void sum (void *k)
{
sum_aux ((int)k);
printf (" = instant number\n");
exit(0);
}
One also defines a function to trace the instants:
void trace_instants (void *n)
{
int i = 0;
while (1){
printf ("\ninstant %d: ", i++);
ft_thread_cooperate();
}
}
Finally, the main function is defined by:
int main(int argc, void** argv)
{
ft_scheduler_t sched = ft_scheduler_create ();
ft_thread_create (sched,trace_instants,NULL,NULL);
ft_thread_create (sched,sum,NULL,argv[1]);
ft_scheduler_start(sched);
ft_exit();
return 0;
}
Given the argument n, the program exits at the instsnt
number s where s is the sum of the n
first instegers. For example, with n equals to 4, on gets:
instant 0:
instant 1:
instant 2:
instant 3:
instant 4:
instant 5:
instant 6:
instant 7:
instant 8:
instant 9:
instant 10: 0+1+2+3+4 = instant number
Thus, the thread executing sum absolutely needs a stack to
store the partial results of the recursive calls because several
instants are passing before the final result is computed.
6.3.3 Select
There is no counterpart in Loft of the ft_thread_select
functions. Thus, the waiting of one amongst several events must be
coded indirectly in Loft. Next versions of Loft should
certainly propose a primitive similar to ft_thread_select of
FairThreads.
|
6.4 Comparison with POSIX Threads
|
When comparing FairThreads with POSIX, the first point to note is of course
that FairThreads is basically cooperative while POSIX is basically
preemptive. More precisely, threads linked to the same scheduler are
executed cooperatively. As a consequence, data protection is
considered very differently in the two contexts: in POSIX mutexes are
basically used for that purpose, while in FairThreads schedulers are used
for the same purpose. If one is sure that a data can only be accessed
by the threads linked to a given scheduler, one can safely deduce that
no race condition occur for the data. If accessing the data needs more
than simple atomic instructions, a boolean variable can be used to
lock and unlock the variable. In this case, however, one is in a
situation very similar to the one using mutexes, with all their
identified problems.
The second point to note when comparing FairThreads and POSIX is that
FairThreads proposes the notion of an automaton which does not need
the full power of a kernel thread to execute. Using automata,
one can pass around the limitations of POSIX implementations
in which threads are mapped onto kernel threads.
One ends the comparison with POSIX by detailing some others important
differences.
Threads and Scheduling
The POSIX notion of a thread attribute and the related functions
pthread_attr_* do not exist in FairThreads in which threads are
more simply of two types: standard fair threads or automata.
Like POSIX (and unlike Java), there is no primitive to start a fair
thread which will be automatically run after creation by ft_thread_create.
Equality of fair threads is standard pointers equality as the type
ft_thread_t is a pointer type (no equivalent of pthread_equals).
Data local to a thread can be defined in POSIX with the notion of keys
and of thread-specific data (functions pthread_key_* and
pthread_getspecific, and pthread_setspecific).
There is no direct counterpart in FairThreads. However, the POSIX functions
for data local can be used in FairThreads by means of the ft_pthread function.
The pthread_once function of POSIX can be simply implemented
with a boolean in FairThreads as one is in a cooperative context.
The functions related to POSIX scheduling policies (for example
pthread_setschedparam) are of no use in FairThreads where only one
policy is available: the fair one. Note that this policy more or less
corresponds to the SCHED_FIFO policy of POSIX.
Priorities
Priority of POSIX do not exist in FairThreads. Priority-based systems
can be coded in FairThreads using several schedulers to manage the
various priority levels. This is another reason why FairThreads is
simpler than POSIX.
Mutex and Condition Variables
All the functions related to mutexes (pthread_mutex_* and
pthread_muttexattr_*) have no counterpart in FairThreads, where
locks are not needed when one stays in the cooperative part of it.
As stated before, schedulers in FairThreads can be used to structure
applications around protected data which are only accessed by linked
threads; in this respect, schedulers are playing a role very
similar to the one of mutexes.
Events in FairThreads basically correspond to condition variables of POSIX.
To generate an event corresponds to pthread_cond_broadcast
and to await it corresponds to pthread_cond_wait. The
limited variant pthread_cond_timedwait is the counterpart of
ft_thread_await_n except that in FairThreads deadlines are counted
in instants. There is no direct counterpart for the nondeterministic
pthread_cond_signal of POSIX which must be coded in FairThreads in
a way similar as the one presented in Single Notification.
Thread Termination
The notion of a detached thread (pthread_detach) has no
counterpart in FairThreads where termination of all threads can be tested at
any moment by ft_thread_join.
Joining a thread in FairThreads and in POSIX are very similar except that
no value are returned by terminating fair threads.
Thread Cancellation
To kill a thread is done in FairThreads with the ft_scheduler_stop
function. In POSIX, the cancellation mechanism with the related
functions (for example, pthread_setcancelstate) can be used
for that purpose. However, it implies that the cancelled thread is in
the correct mode and has set meaninful cancellation points. In FairThreads
thread cancellation can naturally only occurs at beginning of
instants. In this respect, FairThreads is much more simpler than POSIX.
Control over Threads
The suspend-resume mechanism of FairThreads has no direct counterpart in
POSIX where it must be coded indirectly. Note that the equivalent
functionnality has disapeared from the recent versions of Java (it is
deprecated).
|