Threads in OpenMCL


Table of Contents

Overview
Functional Reference for Native threads
all-processes [Function]
make-process [Function]
process-suspend [Function]
process-resume [Function]
process-suspend-count [Function]
process-preset [Function]
process-enable [Function]
process-run-function [Function]
process-interrupt [Function]
*current-process* [Special Variable]
process-reset [Function]
process-kill [Function]
*ticks-per-second* [Special Variable]
process-whostate [Function]
process-allow-schedule [Function]
process-wait
process-wait-with-timeout [Function]
without-interrupts [Macro]
make-lock [Function]
with-lock-grabbed [Macro]
grab-lock [Function]
release-lock [Function]
try-lock [Function]
make-read-write-lock [Function]
with-read-lock [Macro]
with-write-lock [Macro]
make-semaphore [Function]
signal-semaphore [Function]
wait-on-semaphore [Function]
timed-wait-on-semaphore [Function]
process-input-wait [Function]
process-output-wait [Function]
(Intentionally) Missing Functionality
Implementation issues
Porting code to the new thread model

Overview

OpenMCL provides facilities which enable multiple threads of execution (threads, sometimes called lightweight processes or just processes, though the latter term shouldn't be confused with the OS's notion of a process) within a lisp session. This document describes those facilities and issues related to multitheaded programming in OpenMCL.

Wherever possible, I'll try to use the term "thread" to denote a lisp thread, even though many of the functions in the API have the word "process" in their name. A lisp-process is a lisp object (of type CCL:PROCESS) which is used to control and communicate with an underlying native thread. Sometimes, the distinction between these two (quite different) objects can be blurred; other times, it's important to maintain.

Lisp threads share the same address space, but maintain their own execution context (stacks and registers) and their own dynamic binding context.

Traditionally, OpenMCL's threads have been cooperatively scheduled: through a combination of compiler and runtime suppport, the currently executing lisp thread arranged to be interrrupted at certain discrete points in its execution (typically on entry to a function and at the beginning of any looping construct). This interrupt occurred several dozen times per second; in response, a handler function might observe that the current thread had used up its time slice and another function (the lisp scheduler) would be called to find some other thread that was in a runnable state, suspend execution of the current thread, and resume execution of the newly executed thread. The process of switching contexts between the outgoing and incoming threads happened in some mixture of Lisp and assembly language code; as far as the OS was concerned, there was one native thread running in the Lisp image and its stack pointer and other registers just happened to change from time to time.

Under OpenMCL's cooperative scheduling model, it was possible (via the use of the CCL:WITHOUT-INTERRUPTS construct) to defer handling of the periodic interrupt that invoked the lisp scheduler; it was not uncommon to use WITHOUT-INTERRUPTS to gain safe, exclusive access to global data structures. In some code (including much of OpenMCL itself) this idiom was very common: it was (justifiably) believed to be an efficient way of inhibiting the execution of other threads for a short period of time.

The timer interrupt that drove the cooperative scheduler was only able to (pseudo-)preempt lisp code: if any thread called a blocking OS I/O function, no other thread could be scheduled until that thread resumed execution of lisp code. Lisp library functions were generally attuned to this constraint, and did a complicated mixture of polling and "timed blocking" in an attempt to work around it. Needless to say, this code is complicated and less efficient than it might be; it meant that the lisp was a little busier than it should have been when it was "doing nothing" (waiting for I/O to be possible.)

For a variety of reasons - better utilization of CPU resources on single and multiprocessor systems and better integration with the OS in general - threads in OpenMCL 0.14 and later are preemptively scheduled. In this model, lisp threads are native threads and all scheduling decisions involving them are made by the OS kernel. (Those decisions might involve scheduling multiple lisp threads simultaneously on multiple processors on SMP systems.) This change has a number of subtle effects:

  • it is possible for two (or more) lisp threads to be executing simultaneously, possibly trying to access and/or modify the same data structures. Such access really should have been coordinated through the use of synchronization objects regardless of the scheduling model in effect; preemptively scheduled threads increase the chance of things going wrong at the wrong time and do not offer lightweight alternatives to the use of those synchronization objects.

  • even on a single-processor system, a context switch can happen on any instruction boundary. Since (in general) other threads might allocate memory, this means that a GC can effectively take place at any instruction boundary. That's mostly an issue for the compiler and runtime system to be aware of, but it means that certain practices (such as trying to pass the address of a lisp object to foreign code) that were always discouraged are now discouraged ... vehemently.

  • there is no simple and efficient way to "inhibit the scheduler" or otherwise gain exclusive access to the entire CPU. (There are a variety of simple and efficient ways to synchronize access to particular data structures.)

As a broad generalization: code that's been aggressively tuned to the constraints of the cooperative scheduler may need to be redesigned to work well with the preemptive scheduler (and code written to run under OpenMCL's interface to the native scheduler may be less portable to other CL implementations, many of which offer a cooperative scheduler and an API similar to OpenMCL (< 0.14) 's.) At the same time, there's a large overlap in functionality in the two scheduling models, and it'll hopefully be possible to write interesting and useful MP code that's largely independent of the underlying scheduling details.

The keyword :OPENMCL-NATIVE-THREADS is on *FEATURES* in 0.14 and later and can be used for conditionalization where required.

Functional Reference for Native threads

all-processes [Function]

Syntax

all-processes

Description

Returns a list of all lisp threads known to OpenMCL as of the precise instant it's called. It's safe to traverse this list and to modify the cons cells that comprise that list (it's freshly consed.) Since other threads can create and kill threads at any time, there's generally no way to get an "accurate" list of all threads, and (generally) no sense in which such a list can be accurate.

make-process [Function]

Syntax

make-process name &key persistent (priority 0) (class (find-class 'ccl:process)) (stack-size ccl:*default-control-stack-size*) (vstack-size ccl:*default-value-stack-size*) (tstack-size ccl:*default-temp-stack-size*) initial-bindings (use-standard-initial-bindings t)

Description

Creates and returns a new process with the specified attributes. The newly created process will be incapable of execution; it will need to be preset (given an initial function to run) and enabled (allowed to execute) before it's able to actually do anything.

Arguments

 

name

a string, used to identify the process

persistent

if true, requests that information about the process be retained by SAVE-APPLICATION so that an equivalent process can be restarted when a saved image is run.

priority

this argument is currently ignored.[1]

class

The class of process object to create (should be a subclass of CCL:PROCESS.)

stack-size

the size, in bytes, of the newly-created process's control stack (used for foreign function calls and to save function return address context.)

vstack-size

the size, in bytes of the newly-created process's value stack (used for lisp function arguments, local variables, etc.)

tstack-size

the size, in bytes, of the newly-created process's temp stack (used for the allocation of dynamic-extent objects.)

use-standard-initial-bindings

when true (the default), the global “standard initial bindings” are put into effect in the new thread before. See DEF-STANDARD-INITIAL-BINDING. (“standard” initial bindings are put into effect before any bindings specified by :initial-bindings are.

initial-bindings

an alist of (SYMBOL . VALUEFORM) pairs, which can be used to initialize special variable bindings in the new thread. Each valueform is used to effect the binding of the corresponding symbol according to the following rules:

  1. if valueform is a function, it's called (with no arguments) in the execution environment of the newly created thread; the value returned from this call is used to initialize the corresponding variable.

  2. if valueform is a constant (or a list whose CAR is QUOTE), the constant value (or the CADR of the QUOTE form) is used to initialize the corresponding variable.

  3. if valueform is a symbol, that symbol's SYMBOL-VALUE - in the context of the calling thread as of the time that MAKE-PROCESS is called - is used to initialize the corresponding variable.

  4. if valueform is a list, its CAR is applied to its CDR in the execution environment of the newly created thread; the value returned from this call is used to initialize the corresponding variable.

process-suspend [Function]

Syntax

process-suspend process

Description

Suspends the specified process (i.e., prevents it from running). This is a fairly expensive operation (it involves a few calls to the OS) and can be somewhat dangerous (for instance, if the process being suspended owns a lock or other resource.) Each call to PROCESS-SUSPEND must be paired by a matching PROCESS-ENABLE call before the process is able to run. Returns T if the process had been enabled and is now disabled, NIL otherwise (that is, returns T if the process's PROCESS-SUSPEND-COUNT transitioned from 0 to 1.

A thread can suspend itself; it it's successful in doing so, then it can obviously only be resumed by some other thread.

[2]

Arguments

 

process

the process to suspend

process-resume [Function]

Syntax

process-resume process

Description

Undoes the effect of a previous call to PROCESS-SUSPEND; if all such calls are undone, makes the process runnable. Has no effect if the process is not suspended. Returns T if the process had been suspended and is now not suspended (if the process's PROCESS-SUSPEND-COUNT transitioned from 1 to 0.)

[3]

 

Arguments

 

process

the process to resume

process-suspend-count [Function]

Syntax

process-suspend-count process

Description

Returns the number of “outstanding” PROCESS-SUSPEND calls on the specified process (those that don't have a matching PROCESS-RESUME), or NIL if the process has expired (if its initial function has returned.) Newly created processes have a (PROCESS-SUSPEND-COUNT) of 0 (but are not runnable until they've been preset and enabled).

Arguments

 

process

the process

process-preset [Function]

Syntax

process-preset process function &rest args

Description

Typically used to initialize a newly-created or newly-reset process, setting things up so that it'll begin execution by applying the specified function to the specified args when it's enabled.

Arguments

 

process

the process to preset

function

the initial function (or a symbol which names a function)

args

0 or more values, appropriate for the specified function.

process-enable [Function]

Syntax

process-enable process &optional (wait-timeout 1)

Description

Tries to make a process which has successfully been preset begin executing the initial function provided by PROCESS-PRESET. An error is signaled if the process has never been preset; otherwise, an attempt is made to synchronize with the process, which is presumed to be reset or in the act of resetting itself. If this attempt at synchronization is not succesful (within the time interval specified by the wait-timeout argument), a continuable error is signaled, which offers the opportunity to try again.

A

process cannot meaningfully attempt to enable itself.

Arguments

 

process

the process to be enabled

wait-timeout

a time interval in seconds (a non-negative real number, the FLOOR of which fits in 32 bits.)

process-run-function [Function]

Syntax

process-run-function name function &rest args

Description

Creates a process (via MAKE-PROCESS), presets it (via PROCESS-PRESET), enables it (via PROCESS-ENABLE), and returns that process. This is the simplest way to create and run a lisp thread.

Arguments

 

name

either a string used to name the process or a list of keyword/value pairs used to supply additional arguments to MAKE-PROCESS. In the latter case, the additional keyword :NAME can be used to specifiy the name of the new process.

function

the initial function (or a symbol which names a function)

args

a list of values, appropriate for the specified function.

process-interrupt [Function]

Syntax

process-interrupt process function &rest args

Description

Arranges for the target process to apply function to args at some point in the near future (interrupting whatever the process was doing.) If function returns normally, the process resumes execution at the point at which it was interrupted.

Arguments

 

process

the target process. It's perfectly legal for a process to interrupt itself. A process must be in an enabled state in order to respond to a PROCESS-INTERRUPT request.[4]

function

the function that the target process should run in response to an interrupt

args

a list of values, appropriate for the specified function.

*current-process* [Special Variable]

Description

Bound to (of all things) the current thread in each thread. Shouldn't be set by user code.

process-reset [Function]

Syntax

process-reset process &optional kill-option

Description

Generally used to cause a running process to cleanly exit from any ongoing computation and either exit (if the kill-option argument is non-nil) or enter a state where it can be preset. This is implemented by signaling a condition (of type PROCESS-RESET); user-defined condition handlers should generally refrain from attempting to handle conditions of this type.

A process can meaningfully reset itself.

There is in general no way to know precisely when a process has completed the act of resetting or killing itself; a process that's either entered the limbo of the reset state or exited has few ways of communicating either fact. As described above, PROCESS-ENABLE can reliably determine when a process has entered the “limbo of the reset state”, but can't predict how long the clean exit from ongoing computation might take: that depends on the behavior of UNWIND-PROTECT cleanup forms, the behavior of the OS scheduler, and other factors.

Resetting a process other than the current one involves the use of PROCESS-INTERRUPT.

Arguments

 

process

a process

process-kill [Function]

Syntax

process-kill process

Description

Entirely equivalent to calling (PROCESS-RESET PROCESS T).

Arguments

 

process

a process

*ticks-per-second* [Special Variable]

Description

Initialized to the OS scheduler's clock resolution every time a lisp image starts up; shouldn't be modified by user code. The scheduler's clock resolution is ordinarily of marginal interest at best, but (for backward compatibility) some functions accept “timeout” values expressed in “ticks”. Currently, both LinuxPPC and DarwinPPC cause this variable to be initialized to 100.

process-whostate [Function]

Syntax

process-whostate process

Description

Returns a string which describes the “state” of the specified process, primarily for the benefit of debugging tools. [5]

Arguments

 

process

a process

process-allow-schedule [Function]

Syntax

process-allow-schedule

Description

Advises the OS scheduler that the current thread has nothing useful to do and that it should try to find some other thread to schedule in its place. There's almost always a better alternative (involving waiting for some specific event to occur.)

process-wait

Syntax

process-wait whostate function &rest args

Description

Causes the current process to repeatedly apply function to args until the call returns a true result, then returns NIL. After each failed call, yields the CPU as if by PROCESS-ALLOW-SCHEDULE. Again, it's almost always more efficient to wait for some specific event to occur; this isn't exactly busy-waiting, but the OS scheduler can do a better job of scheduling if it's involved in the process.

Arguments

 

whostate

a string, which will be the value of PROCESS-WHOSTATE while the process is waiting

function

a function or function name, treated as a predicate

args

arguments to provide to the predicate

process-wait-with-timeout [Function]

Syntax

process-wait-with-timeout whostate ticks function args

Description

If ticks is NIL, behaves exactly like PROCESS-WAIT (and then returns T.) Otherwise, ticks should be a small positive integer expressing a time interval in “ticks” (see *TICKS-PER-SECOND*). In this case, the predicate will be tested repeatedly (in the same kind of test/yield loop as in PROCESS-WAIT) until the predicate returns true (in which case PROCESS-WAIT-WITH-TIMEOUT returns T) or the time interval is exceeded (in which case NIL is returned.) The astute reader has no doubt anticipated the observation that better alternatives should be used whenever possible.

Arguments

 

whostate

a string, which will be the value of PROCESS-WHOSTATE while the process is waiting

ticks

a small positive integer or NIL

function

a function or function name, treated as a predicate

args

arguments to provide to the predicate

without-interrupts [Macro]

Syntax

without-interrupts &body body

Description

Executes the body (and returns whatever value(s) it returns) in an environment in which PROCESS-INTERRUPT requests are deferred. As noted above, this has nothing to do with the scheduling of other threads; it may be necessary to inhibit PROCESS-INTERRUPT handling when (for instance) modifying some data structure (for which the current thread holds an appropriate lock) in some manner that's not reentrant.

Arguments

 

body

a sequence of Lisp forms

make-lock [Function]

Syntax

make-lock &optional name

Description

Creates and returns an object of type CCL:LOCK, which can be used to synchronize access to some shared resource. The lock is initially in a "free" state; locks can also be "owned" by a thread.

Arguments

 

name

any value; typically a string or symbol which may appear in some PROCESS-WHOSTATEs of threads that're waiting for the lock.

with-lock-grabbed [Macro]

Syntax

with-lock-grabbed (lock) &body body

Description

Waits until the lock is either free or owned by the calling thread, then excutes the body as an implicit PROGN and with the lock owned by the calling thread. If the lock was originally free, it's restored to a free state. Returens whatever values(s) the body returns.

Arguments

 

lock

a lock, as returned by MAKE-LOCK

body

a sequence of Lisp forms.

grab-lock [Function]

Syntax

grab-lock lock

Description

Blocks until the lock is owned by the calling thread.[6]

Arguments

 

lock

a lock, as returned by MAKE-LOCK

release-lock [Function]

Syntax

release-lock lock

Description

Signals an error (of type CCL:LOCK-NOT-OWNER) if the lock is not already owned by the calling thread; otherwise, undoes the effect of a previous GRAB-LOCK operation. If this undoes the earliest such paired GRAB-LOCK, the lock becomes free.

Arguments

 

lock

a lock, as returned by MAKE-LOCK

try-lock [Function]

Syntax

try-lock

Description

If the lock can be obtained without blocking (i.e., it's either free or already owned by the calling thread, causes it to be owned by the calling thread and returns T. Otherwise, the lock is already owned by another thread and cannot be obtained without blocking; NIL is returned in this case.

Arguments

 

lock

a lock, as returned by MAKE-LOCK

make-read-write-lock [Function]

Syntax

make-read-write-lock

Description

Creates and returns an object of type CCL::READ-WRITE-LOCK. The returned object has no "writer" and no "readers". READ-WRITE-LOCKs allow multiple threads to be "readers" (with presumed read access to the objects protected by the lock) or a single thread to be a "writer" (with exclusive read-write acccess to the protected object.)

[7]

 

with-read-lock [Macro]

Syntax

with-read-lock (lock) &body body

Description

Waits until the specified READ-WRITE-LOCK has no writer, then ensures that the current thread is a reader. Executes the body and returns whatever value(s) it returns, restoring the current thread's “reader” status to what it was on entry.

Arguments

 

lock

a READ-WRITE-LOCK, as returned by MAKE-READ-WRITE-LOCK.

body

a sequence of lisp forms

with-write-lock [Macro]

Syntax

with-write-lock (lock) &body body

Description

Waits until the specified READ-WRITE-LOCK has no readers and no other writer, then ensures that the current thread is the writer. Executes the body and returns whatever value(s) it returns, restoring the current thread's “writer” status to what it was on entry.

Arguments

 

lock

a READ-WRITE-LOCK, as returned by MAKE-READ-WRITE-LOCK.

body

a sequence of lisp forms

make-semaphore [Function]

Syntax

make-semaphore

Description

Creates and returns an object of type CCL:SEMAPHORE. The returned object has a "count" of 0.

signal-semaphore [Function]

Syntax

signal-semaphore semaphore

Description

Atomically increments the semaphore's count by 1; this may enable a waiting thread to resume execution. Returns an OS error indication (which should probably be interpreted and processed; the most common error would probably involve trying to operate on something that's not a semaphore.

Arguments

 

semaphore

a semaphore, as returned by MAKE-SEMAPHORE

wait-on-semaphore [Function]

Syntax

wait-on-semaphore semaphore

Description

Waits until the semaphore has a positive count that can be atomically decremented; this will succeed exactly once for each corresponding call to SIGNAL-SEMAPHORE. Returns an OS error indication.wait-on-semaphore [Function]

Arguments

 

semaphore

a semphore, as returned by MAKE-SEMAPHORE

timed-wait-on-semaphore [Function]

Syntax

timed-wait-on-semaphore semaphore timeout-interval

Description

Waits until the semaphore has a positive count that can be atomically decremented or until the specified timeout-interval has elapsed. Returns T in the former case, NIL in the latter.

Arguments

 

semaphore

a semaphore, as returned by MAKE-SEMAPHORE

timeout-interval

a non-negative real number, the FLOOR of which fits in 32 bits.

process-input-wait [Function]

Syntax

process-input-wait fd &optional timeout

Description

Wait until input is available on the file descriptor fd. This uses the select system call and is generally a fairly efficient way of blocking while waiting for input. More accurately, this function waits until it's possible to read from fd without blocking or until the timeout value (if any) expires. Note that it's possible to read without blocking if an end-of-file condition exists.

Arguments

 

fd

a small non-negative integer used by the OS to denote an open file, socket, or similar I/O connection. The generic function (CCL::STREAM-DEVICE (s stream) direction) - where "direction" is one of :INPUT or :OUTPUT - will return the file descriptor associated with a stream, if any.

timeout

either NIL (the default) or a non-negative integer expressing a timeout interval in "ticks". There are CCL::*TICKS-PER-SECOND* (typically 100) ticks per second

process-output-wait [Function]

Syntax

process-output-wait fd

Description

Wait until output is possible on the file descriptor fd. This uses the select system call and is generally a fairly efficient way of blocking while waiting for output to become possible. (It can also be used to determine when a stream socket has established a connection, for instance.)

Arguments

 

fd

a small non-negative integer used by the OS to denote an open file, socket, or similar I/O connection. The generic function (CCL::STREAM-DEVICE (s stream) direction) - where “direction” is one of :INPUT or :OUTPUT - will return the file descriptor associated with a stream, if any.

(Intentionally) Missing Functionality

Much of the functionality described above is similar to that provided by OpenMCL's cooperative scheduler, some other parts of which make no sense in a native threads implementation.

  • PROCESS-RUN-REASONS and PROCESS-ARREST-REASONS were SETFable process attributes; each was just a list of arbitrary tokens. A thread was eligible for scheduling (roughly equivalent to being “enabled”) if its arrest-reasons list was empty and its run-reasons list was not. I don't think that it's appropriate to encourage a programming style in which otherwise runnable threads are enabled and disabled on a regular basis (it's preferable for threads to wait for some sort of synchronization event to occur if they can't occupy their time productively.)

  • There are a number of primitives for maintaining process queues; that's now the OS's job.

  • Cooperative threads were based on coroutining primitives associated with objects of type STACK-GROUP. STACK-GROUPs no longer exist.

Implementation issues

As of August 2003:

  • It's not clear that exposing PROCESS-SUSPEND/PROCESS-RESUME is a good idea: it's not clear that they offer ways to win, and it's clear that they offer ways to lose.

  • It has traditionally been possible to reset and enable a process that's "exhausted" . (As used here, the term "exhausted" means that the process's initial function has run and returned and the underlying native thread has been deallocated.) One of the principle uses of PROCESS-RESET is to “recycle” threads; enabling an exhausted process involves creating a new native thread (and stacks and synchronization objects and ...), and this is the sort of overhead that such a recycling scheme is seeking to avoid. It might be worth trying to tighten things up and declare that it's an error to apply PROCESS-ENABLE to an exhausted thread (and to make PROCESS-ENABLE detect this error.)

  • When native threads that aren't created by OpenMCL first call into lisp, a “foreign process” is created, and that process is given its own set of initial bindings and set up to look mostly like a process that had been created by MAKE-PROCESS. The life cycle of a foreign process is certainly different from that of a lisp-created one: it doesn't make sense to reset/preset/enable a foreign process, and attempts to perform these operations should be detected and treated as errors.

Porting code to the new thread model

It's hard to give step-by-step instructions; there are certainly a few things that one should look at carefully:

  • It's wise to be suspicious of most uses of WITHOUT-INTERRUPTS; there may be exceptions, but WITHOUT-INTERRUPTS is often used as shorthand for WITH-APPROPRIATE-LOCKING. Determining what type of locking is appropriate and writing the code to implement it is likely to be straightforward and simple most of the time.

  • I've only seen one case where a process's “run reasons" were used to communicate information as well as to control execution; I don't think that this is a common idiom, but may be mistaken about that.

  • It's certainly possible that programs written for cooperatively scheduled lisps that have run reliably for a long time have done so by accident: resource-contention issues tend to be timing-sensitive, and decoupling thread scheduling from lisp program execution affects timing. I know that there is or was code in both OpenMCL and commercial MCL that was written under the explicit assumption that certain sequences of open-coded operations were uninterruptable; it's certainly possible that the same assumptions have been made (explicitly or otherwise) by application developers.



[1] It shouldn't be ignored of course, but there are complications on some platforms.

[2] This was previously called PROCESS-DISABLE. PROCESS-ENABLE now names a function for which there is no obvious inverse, so PROCESS-DISABLE is no longer defined.

[3] This was previously called PROCESS-ENABLE; PROCESS-ENABLE now does something slightly different.

[4] PROCESS-INTERRUPT uses asynchronous POSIX signals to interrupt threads. If the thread being interrupted is executing lisp code, it can respond to the interrupt almost immediately (as soon as it has finished pseudo-atomic operations like consing and stack-frame initialization.) If the interrupted thread is blocking in a system call, that system call is aborted by the signal and the interrupt is handled on return. It is still difficult to reliably interrupt arbitrary foreign code (that may be stateful or otherwise non-reentrant); the interrupt request is handled when such foreign code returns to or enters lisp.

[5] This should be SETFable, but doesn't seem to ever have been.

[6] The WITH-LOCK-GRABBED macro could be defined in terms of GRAB-LOCK and RELEASE-LOCK. (It's actually implemented at a slightly lower level.)

[7] There probably should be some way to atomically "promote" a reader (making it a writer).