The basic elements of parallel processing in EuLisp are processes and mutual
exclusion, which are provided by the classes <thread>
and <lock> respectively.
A thread is allocated and initialized, by calling make. The
initarg of a thread specifies the initial function, which is where execution
starts the first time the thread is dispatched by the scheduler. In this
discussion four states of a thread are identified: new, running, aborted and
finished. These are for conceptual purposes only and a EuLisp program cannot
distinguish between new and running or between aborted and finished.
(Although accessing the result of a thread would permit such a distinction
retrospectively, since an aborted thread will cause a condition to be signalled
on the accessing thread and a finished thread will not.) In practice, the
running state is likely to have several internal states, but these distinctions
and the information about a thread's current state can serve no useful purpose
to a running program, since the information may be incorrect as soon as it is
known. The initial state of a thread is new. The union of the two final states
is known as determined. Although a program can find out whether
a thread is determined or not by means of wait with a
timeout of t (denoting a poll), the information is only useful
if the thread has been determined.
A thread is made available for dispatch by starting it, using the function
thread-start, which changes its state from new to running.
After running a thread becomes either finished or aborted. When a thread is
finished, the result of the initial function may be accessed using
thread-value. If a thread is aborted, which can only occur as
a result of a signal handled by the default handler (installed when the thread
is created), then thread-value will signal the condition that
aborted the thread on the thread accessing the value. Note that
thread-value suspends the calling thread if the thread whose
result is sought is not determined.
While a thread is running, its progress can be suspended by accessing a lock,
by a stream operation or by calling thread-value on an
undetermined thread. In each of these cases,
thread-reschedule is called to allow another thread to
execute. This function may also be called voluntarily. Progress can resume
when the lock becomes unlocked, the input/output operation completes or the
undetermined thread becomes determined.
The actions of a thread can be influenced externally by
signal. This function registers a condition to be signalled no
later than when the specified thread is rescheduled for execution|when
thread-reschedule returns. The condition must be an
instance of <thread-condition>. Conditions are
delivered to the thread in order of receipt. This ordering requirement is only
important in the case of a thread sending more than one signal to the same
thread, but in other circumstances the delivery order cannot be verified. A
signal on a determined thread has no discernable effect on
either the signalled or signalling thread unless the condition is not an instance
of , in which case an error is signalled on
the signalling thread. See also Section ?? .
A lock is an abstract data type protecting a binary value which denotes
whether the lock is locked or unlocked. The operations on a lock are
lock and unlock. Executing a
lock operation will eventually give the calling thread
exclusive control of a lock. The unlock operation unlocks the
lock so that either a thread subsequently calling lock or one
of the threads which has already called lock on the lock can
gain exclusive access.
It is intended that implementations of locks based on spin-locks,
semaphores or channels should all be capable of satisfying the above
description. However, to be a conforming implementation, the use of a
spin-lock must observe the fairness requirement, which demands that between
attempts to acquire the lock, control must be ceded to the scheduler.
The programming model is that of concurrently executing threads, regardless
of whether the configuration is a multi-processor or not, with some constraints
and some weak fairness guarantees.
A processor is free to use run-to-completion, timeslicing and/or
concurrent execution.
A conforming program must assume the possibility of concurrent
execution of threads and will have the same semantics in all cases|see
discussion of fairness which follows.
The default condition handler for a new thread, when invoked, will
change the state of the thread to aborted, save the
signalled condition and reschedule the thread.
A continuation must only be called from within its dynamic extent. This
does not include threads created within the dynamic extent. An error is
signalled (condition class:
<wrong-thread-continuation>), if a continuation
is called on a thread other than the one on which it was created.
The lexical environment (inner and top) associated with the initial
function may be shared, as is the top-dynamic environment, but each
thread has a distinct inner-dynamic environment. In consequence, any
modifications of bindings in the lexical environment or in the
top-dynamic environment should be mediated by locks to avoid
non-deterministic behaviour.
The creation and starting of a thread represent changes to the state of
the processor and as such are not affected by the processor's handling of
errors signalled subsequently on the creating/starting thread (c.f.
streams). That is to say, a non-local exit to a point dynamically outside
the creation of the subsidiary thread has no default effect on the
subsidiary thread.
The behaviour of i/o on the same stream by multiple threads is
undefined unless it is mediated by explicit locks.
The parallel semantics are preserved on a sequential run-to-completion
implementation by requiring communication between threads to use only
thread primitives and shared data protected by locks|both the thread
primitives and locks will cause rescheduling, so other threads can be assumed
to have a chance of execution.
There is no guarantee about which thread is selected next. However, a fairness
guarantee is needed to provide the illusion that every other thread is running.
A strong guarantee would ensure that every other thread gets scheduled before
a thread which reschedules itself is scheduled again. Such a scheme is usually
called \round-robin". This could be stronger than the guarantee provided by a
parallel implementation or the scheduler of the host operating system and
cannot be mandated in this definition.
A weak but sufficient guarantee is that if any thread reschedules infinitely
often then every other thread will be scheduled infinitely often. Hence if a
thread is waiting for shared data to be changed by another thread and is using
a lock, the other thread is guaranteed to have the opportunity to change the
data. If it is not using a lock, the fairness guarantee ensures that in the same
scenario the following loop will exit eventually:
(while (= data 0) (thread-reschedule))
Threads
The defined name of this module is thread. This section
defines the operations on threads.
This function is called for side-effect only and may cause
the thread which calls it to be suspended, while other threads are run. In
addition, if the thread's condition queue is not empty, the first condition is
removed from the queue and signalled on the thread. The resume continuation
of the signal will be one which will eventually call the continuation of the call
to thread-reschedule.
See also:
thread-value, signal and
Section ?? for details of conditions and signalling.
the thread whose finished value is to be accessed.
Result
The result of the initial function applied to the arguments
passed from thread-start. However, if a condition is signalled
on thread which is handled by the default handler the condition will now be
signalled on the thread calling thread-value|that is the
condition will be propagated to the accessing thread.
Remarks
If thread is not determined, each thread calling
thread-value is suspended until thread is
determined, when each will either get the thread's value or signal the
condition.
Returns () if timeout was
reached, otherwise a non-() value.
Remarks
wait provides a generic interface to
operations which may block. Execution of the current thread will continue
beyond the wait form only when one of the following
happened:
A condition associated with obj returns true;
timeout time units elapse;
A condition is raised by another thread on this thread.
wait returns () if timeout occurs, else
it returns a non-() value.
A timeout argument of () or zero denotes a
polling operation. A timeout argument of
t denotes indefinite blocking (cases or above). A
timeout argument of a non-negative integer denotes the
minimum number of time units before timeout. The number of time units in a
second is given by the implementation-defined constant
ticks-per-second.
Examples
This code fragment copies characters from stream
s to the current output stream until no data is received on
the stream for a period of at least 1 second.
(labels
((loop ()
(when (wait s (round ticks-per-second))
(print (read-char s))
(loop))))
(loop))
The timeout
period which is specified by one of (),
t, and non-negative integer.
Result
Result is either thread or (). If
timeout is (), the result is thread if it
is determined. If timeout is t, thread
suspends until thread is determined and the result is
guaranteed to be thread. If timeout is a non-negative
integer, the call blocks until either thread is determined, in which
case the result is thread, or until the timeout period is
reached, in which case the result is (), whichever is the
sooner. The units for the non-negative integer timeout are the number of clock
ticks to wait. The implementation-defined constant
ticks-per-second is used to make timeout periods processor
independent.
Executing a lock operation will
eventually give the calling thread exclusive control of lock. A
consequence of calling lock is that a condition from another
thread may be signalled on this thread. Such a condition will be signalled
before lock has been acquired, so a thread which does not handle
the condition will not lead to starvation; the condition will be signalled
continuably so that the process of acquiring the lock may continue after the
condition has been handled.
See also:
unlock and Section ?? for details of
conditions and signalling.
The unlock operation unlocks
lock so that either a thread subsequently calling
lock or one of the threads which has already called
lock on the lock can gain exclusive access.
See also:
lock.
Julian Padget, jap@maths.bath.ac.uk, this version November 28, 1996