Concurrency

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.

  1. A processor is free to use run-to-completion, timeslicing and/or concurrent execution.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.

Table of contents

current-thread lockp <lock>
lock <thread-already-started> <thread-condition>
thread-reschedule thread-start thread-value
threadp <thread> ticks-per-second
unlock wait wait
<wrong-thread-continuation>

<thread> : classINDEX
The class of all instances of <thread>.

Initialization options

init-function : fn
an instance of which will be called when the resulting thread is started by thread-start.

threadp : functionINDEX

Arguments

object
An object to examine.

Result

The supplied argument if it is an instance of <thread>, otherwise ().

thread-reschedule : functionINDEX
This function takes no arguments.

Result

The result is ().

Remarks

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.

current-thread : functionINDEX
This function takes no arguments.

Result

The thread on which current-thread was executed.

thread-start : functionINDEX

Arguments

thread
the thread to be started, which must be new. If thread is not new, an error is signalled (condition class: <thread-already-started>).
obj1 ...objn
values to be passed as the arguments to the initial function of thread.

Result

The thread which was supplied as the first argument.

Remarks

The state of thread is changed to running. The values obj1 to objn will be passed as arguments to the initial function of thread.

thread-value : functionINDEX

Arguments

thread
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.

See also:

thread-reschedule, signal.

wait : generic-functionINDEX

Generic arguments

obj
An object.
(timeout <object>)
One of (), t or a non-negative integer.

Result

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:
  1. A condition associated with obj returns true;
  2. timeout time units elapse;
  3. 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))

See also:

threads (section ), streams (section ?? ).

wait : methodINDEX

Specialized arguments

(thread <thread>)
The thread on which to wait.
(timeout )
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.

See also:

wait and ticks-per-second (Section ?? ).

ticks-per-second : <double-float>INDEX
The number of time units in a second expressed as a double precision floating point number. This value is implementation-defined.

<thread-condition> : <condition>INDEX

Initialization options

current-thread : thread
The thread which is signalling the condition.

Remarks

This is the general condition class for all conditions arising from thread operations.

<wrong-thread-continuation> : <thread-condition>INDEX

Initialization options

continuation : continuation
A continuation.
thread : thread
The thread on which continuation was created.

Remarks

Signalled if the given continuation is called on a thread other than the one on which it was created.

<thread-already-started> : <thread-condition>INDEX

Initialization options

thread : thread
A thread.

Remarks

Signalled by thread-start if the given thread has been started already.

Locks

The defined name of this module is lock.

<lock> : classINDEX
The class of all instances of <lock>. This class has no init-options. The result of calling make on <lock> is a new, open lock.

lockp : functionINDEX

Arguments

object
An object to examine.

Result

The supplied argument if it is an instance of lock, otherwise ().

lock : functionINDEX

Arguments

lock
the lock to be acquired.

Result

The lock supplied as argument.

Remarks

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.

unlock : functionINDEX

Arguments

lock
the lock to be released.

Result

The lock supplied as argument.

Remarks

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