ToCDocOverviewCGDocRelNotesFAQIndexPermutedIndex
Allegro CL version 8.1
New since 8.1 release.

Symmetric Multiprocessing in Allegro CL

This document contains the following sections:

1.0 Symmetric Multiprocessing introduction
   1.1 An example of the difference between SMP Lisp and non-SMP Lisp
   1.2 Non-SMP images on platforms that support SMP
2.0 Deprecated macros
   2.1 Deprecated macro: excl::atomically
   2.2 Deprecated macro: without-interrupts
   2.3 Deprecated macro: sys:without-scheduling
3.0 New macros and related functionality
   3.1 Non-synchronizing usages
   3.2 Atomic read-modify-write primitives
   3.3 Concurrency control for shared objects
4.0 The 8.1 SMP-macros patch


1.0 Symmetric Multiprocessing introduction

Starting in Allegro CL 9.0 (not released at this time), Allegro CL on certain platforms will have images that will allow using multiple independent processors. When Lisp is executed with multiple processors, certain features that result automatically from knowing only one processor is used for executing Lisp code will no longer apply. Several macros designed to utilize these automatic features will no longer work as in earlier releases, and code may have to be rewritten in light of these changes.

On the other hand, because multiple processors can be used simultaneously, there may be dramatic speedups in executing Lisp code and hardware devoted to running Lisp applications will be fully utilized.

This document describes some of the concerns and techniques for altering existing lisp code to be consistant with smp. Many techniques used in non-SMP Allegro CL to control concurrent access to shared data are inadequate in an Allegro CL with smp. We discuss the general problem and the macros and data elements introduced in Allegro CL 9.0 to control concurrent access. Many of the macros have keyword arguments that can be used to control how the macro expands in a non-SMP Lisp. This makes it easier to write souce code that works efficiently whether it is compiled for running in an SMP Lisp or a non-SMP Lisp.

In a non-SMP Lisp only one thread of control at a time is ever running Lisp code. Lisp execution is gated by a mutex and low-level runtime code selects one lisp process to execute at a time. A Lisp process can voluntarily yield control, either explicitly or by waiting on some event. A running Lisp process can also be preempted, temporarily ceding control to another process in response to some event.

In a non-SMP Lisp interleaved execution of multiple processes is coarse-grained. A process can not lose control at arbitrary points in its execution. Running Lisp code checks periodically, at what might be called safe points, to see if an interruption in the normal flow of sequence has been requested. If so, the state of the running process is saved, the state of the preempting process restored, and that second process allowed to execute.

Lisp-level handling of asynchronous signals is restricted to happen at these same safe points. This is true in SMP-enabled Lisps as well as in non-SMP Lisps. Low-level, non-Lisp support code keeps a record of signals seen but not yet processed. This code responds to asynchronous signals like SIGALRM by recording the event in an unprocessed-signals buffer and setting a global flag to show that a signal has been seen, and then returning to the lisp processing that was happening when the signal was recognized. At the next safe point, the state of the global flag will be seen and Lisp-level processing of the signal will occur. In a non-SMP Lisp this could result in a process switch.

In a non-SMP Lisp, controlling concurrent access to shared objects often reduces to controlling when these process-switch and signal-handling events can occur. By ensuring that a block of Lisp code will execute without interruption, an application running in a non-SMP Lisp can provide arbitrarily complex operations that will look atomic to multiple processes. This is obviously inadequate in an SMP Lisp, where multiple threads of control are running Lisp code simultaneously.


1.1 An example of the difference between SMP Lisp and non-SMP Lisp

Consider the following example. We have a variable VAR whose initial value is the fixnum 8. Various processes are running in Lisp and independently incrementing or decrementing the value of VAR with calls to incf and decf. Our first attempt is:

;; In process-1:
(incf var)

;; In process-2:
(incf var)

;; In process-3:
(decf var)

But this might cause us trouble, because (incf var) macroexpands to (setq var (+ var 1)). It is possible that (+ 1 var) is evaluated and then there is a process switch, before that value is stored as the value of VAR, so when the process gets control again, it might store what has become the wrong value.

But in a non-SMP Lisp, we can prevent a process switch with without-interrupts, so we recode as follows:

;; In process-1:
(without-interrupts (incf var))

;; In process-2:
(without-interrupts (incf var))

;; In process-3:
(without-interrupts (decf var))

In non-SMP Lisp, once process-1, process-2, and process-3 have completed (or at least executed the forms shown), the value of VAR will be 9 (8 + 1 + 1 - 1). We do not actually know in what order the additions and subtraction will occur, but the without-interrupts guarantees that each will complete once it has started without any process switch and so we can be confident of the final result.

In an SMP Lisp, the without-interrupts macro does not have the effect of preventing a process switch because all processes can be running simultaneously on different processors, and so the whole notion of 'process switch' is problematic. So the following can happen:

1. process-1 reads the value 8 from VAR and places that value in one
of its registers.

2. Before process-1 does its calculation and stores a new value in
VAR, process-2 reads the value (still 8) from VAR and places it in one
of its registers.

3. process-1 adds 1 to 8 and stores the result (9) in VAR.

4. After process-1 stores its new value but before process-2 stores a
new value, process-3 reads the value (9) from VAR and places it in one
of its registers.

5. process-2 adds 1 to 8 and stores the result (9) as the value of
VAR.

6. process-3 subtracts 1 from 9 and stores the result (8) as the value
of VAR.

When all this completes, the value of VAR is 8, not 9. The value could indeed end up as 7 (process-3 reads first and stores last), 8 (as shown), 9 or 10 (left as an excercise to the reader).

So code which depended on without-interrupts to ensure that certain operations will not be interfered with and that therefore certain final results could be depended upon will no longer work as expected.

The fundamental issue is that on a non-SMP Lisp, process locking (ensuring that code in a single Lisp process is guaranteed to execute to completion without interruption) gave you object locking (ensuring that only one process could read or set a value) as a side effect. In an SMP Lisp, that is no longer true.

New macros (see Section 3.0 New macros and related functionality) provide object locking to allow the example here and related examples to run as desired. The macros incf-atomic and decf-atomic are specific to this example and others to related examples. Of course, programmers can also use more complex mechanisms to lock objects and processes and avoid undesired concurrency, although these techniques often have a significant overhead.

Here is the code that guarantees that all the incf's and decf's will run as desired (but in an undefined order). This works in SMP and non-SMP Lisps.

;; In process-1:
(incf-atomic var)

;; In process-2:
(incf-atomic var)

;; In process-3:
(decf-atomic var)

1.2 Non-SMP images on platforms that support SMP

All platforms that will support SMP Lisp will also have non-SMP images available. Current programs that depend on the fact that Lisp code is run on a single processors will thus continue to work using the non-SMP images without any changes relating to SMP (beyond trivial supression of compiler warnings, done by evaluating (setq excl::*warn-smp-usage* nil)).

Therefore there is no need for users who do not wish to use SMP to make any changes to their programs. The rest of this document is directed at users who do wish to use SMP. They will have to determine whether their code must be modified (usally, some changes must be made) using the information in this document.



2.0 Deprecated macros

Three macros are used in non-SMP Lisps to provide concurrancy control: excl::atomically, without-interrupts, and without-scheduling. (The symbol excl::atomically was not exported and the associated macro never documented, but some users were aware of it; if you are unfamiliar with excl::atomically, you need not worry about it as its use is now deprecated. You just have less code to modify).

These macros are all very light-weight in processing overhead and are much cheaper than using a process-lock. They have the additional advantage that they do not require the multiprocessing package be loaded. This allows a programmer to write code that runs correctly in a multi-process application, but still runs efficiently in a single-process appliction. All three rely on the coarse-grained scheduling of non-SMP multiprocessing. All three represent problem situations for multiprocessing under SMP. They are all deprecated in 8.2 and later Lisps (and also in 8.1 after the relevant patch -- see Section 4.0 The 8.1 SMP-macros patch -- is loaded), although they are still available and still perform the same functions in a non-SMP lisp as they did before 8.2.

New macros have been introduced in 8.2 to provide the same functions as the deprecated macros, in ways that are compatible with an smp environment. The new macros are described in Section 3.0 New macros and related functionality. Starting in 8.2 and in 8.1 with the relevant patch loaded, the deprecated macros generate compile-time warnings (which can be globally muffled by evaluating (setq excl::*warn-smp-usage* nil)).

A patch for 8.1 acl (see Section 4.0 The 8.1 SMP-macros patch) redefines the deprecated macros to give the same compile-time warning, and also defines the new macros designed to replace them in 8.2 and later Lisps. This makes it feasible to write code that will compile and run correctly in an SMP-enabled 9.0 Lisp, in 8.2, and in a patched 8.1 lisp.


2.1 Deprecated macro: excl::atomically

The excl::atomically macro was never documented and the symbol naming it was never exported. However, some users made use of it. Users who never used atomically can skip this section.

excl::atomically is wrapped around a sequence of forms:

(excl::atomically . BODY)

This acted exactly like

(progn . BODY)

as far as code generation was concerned, but the compiler would produce a diagnostic if BODY involved any operations that might result in a process switch or a garbage collection. Such opportunities are inherent in almost any out-of-line call, in object allocation, in anything that might signal an error, and in several other low-level actions. If BODY contained none of these, then the compiler would accept the form and the programmer could be confident that BODY would execute atomically as far as Lisp processes were concerned.

A major use of excl::atomically was to wrap a section of code in which it was required that garbage collection not relocate some object or objects. This requirement was independent of multiprocessing concerns, and happened most often in low level code that was trying to process an array's elements very efficiently.

In some cases, the excl::atomically form was used not to assure atomicity, or to guarantee gc-free running, but to wrap a section of code that needed to be as fast as possible. If some infelicitous change to the compiler caused it to start generating out-of-line calls where in-line code was expected, the presence of the excl::atomically wrapper made sure there would be a compile-time warning.

The new macro fast-and-clean replaces excl::atomically. In an SMP Lisp, (fast-and-clean ...), which is the functional equialent of (excl::atomically ...), cannot be guaranteed to be atomic because of the nature of SMP and atomicity. It will, however, prevent a gc from happening while the form is executing, because gc's can only happen when a process allocates something or at one of the same "safe-point"s that allow interrupts (described below in Section 2.2 Deprecated macro: without-interrupts). The fast-and-clean form assures us we have neither of these. Even so, if control of garbage collection is the issue, using the with-pinned-objects macro is preferred.


2.2 Deprecated macro: without-interrupts

The without-interrupts macro works as follows:

(without-interrupts . BODY)

acts almost exactly like

(let ((excl::*without-interrupts* t)) BODY)

excl::*without-interrupts* is a special variable (named by an unexported symbol and so not documented) which gates the processing of asynchronous signals. When an asynchronous signal triggers Lisp's low-level signal handler, the signal is queued and a flag is set to indicate the situation. This happens without any Lisp code executing, and does not interrupt the running Lisp code. While executing, Lisp code polls the flag periodically, checking for the signal-has-happened situation.

These checks are made at safe-points in the code, where the Lisp system is ready to allow execution of arbitrary signal-handling code in an interrupt-the-application mode; handling the signals at the Lisp level could result in a process-interrupt, or cause a process switch in a non-SMP Lisp. If excl::*without-interrupts* is nil, then the safe-point check happens normally, and any queued signals get handled. If excl::*without-interrupts* is non-nil, then queued signals are ignored. No process-interrupt will be handled, and in a non-SMP Lisp, no automatic process switch can happen when excl::*without-interrupts* is non-nil, although an explicit process-wait or other scheduling operation would break through this barrier.

Ignored signals are not discarded, and signals caught while excl::*without-interrupts* is non-nil will still be added to the queue of pending signals, to be processed at some safe-point after leaving the without-interrupts regime. The way in which without-interrupts differs from the simple let form shown above has to do with details of safe and efficient processing, ensuring that we pay as little as possible in computation overhead to ignore the pending signals and that when excl::*without-interrupts* returns to a nil value, we handle any pending signals at the next safe-point.

However, even though interrupts are delayed and process switches from the code running within a without-interrupts are also inhibited, object locking, a side effect in a non-SMP Lisp is no longer guaranteed and gc's may occur even if the code within the without-interrupts form does no consing and so does not itself trigger a gc.

The new macro with-delayed-interrupts replaces without-interrupts. In a non-SMP Lisp, with-delayed-interrupts expands to the same code as without-interrupts (but does not produce a compiler warning). In an SMP Lisp, interrupts are delayed, so the code within the macro runs to completion once it is started, but objects are not locked as other processes can run.


2.3 Deprecated macro: sys:without-scheduling

sys:without-scheduling worked as follows:

(without-scheduling . BODY)

worked like

(let ((*disallow-scheduling* t))
  (progn . BODY))

*disallow-scheduling* is a special variable that gates automatic process switches in non-SMP Lisps. It is checked when other factors indicate it is time to stop the currently running process and let another one have control for a while. If it is nil, then the switch will happen; if non-nil, the switch will be prohibited and the current process will continue running. sys:*disallow-scheduling* finds some specialized uses, as when it is important to honor sys:with-timeout requests (which require handling timer signals, which would be ignored by without-interrupts) without allowing a process switch to occur.

There is no exact replacement for sys:without-scheduling since the model for processes is changed and the concept of process switching is nearly without meaning. If you use sys:without-scheduling, the question is why? If the purpose was object locking (ensuring that values are not read or written by other processes while code runs), you have to use the new object locking routines. If the purpose was to ensure that the process ran to completion but also allowed for signal processing (for sys:with-timeout, for example), that is not longer supported.



3.0 New macros and related functionality

We provide new macros for efficient object-level synchronization. Some of these involve locking objects, and others are atomic read-modify-write primitives. We also provide a set of macros to perform those functions of the deprecated macros that did not serve to synchronize access to specific objects. These new macros appear in 8.2 and later lisps. A patch makes the macros available in 8.1, with certain limits, as described with specific macro descriptions.

A Lisp that actually supports SMP has :smp on its *features* list. A lisp that supports these new macros has :smp-macros on its *features* list. Thus a 9.0 smp-enabled Lisp has both :smp and :smp-macros on its *features* list, while an 8.2 Lisp, a patched 8.1 Lisp, or a non-SMP 9.0 Lisp have the feature :smp-macros but not :smp.

All the symbols naming the functions, macros, classes and structure types added as part of SMP are exported from the excl package.


3.1 Non-synchronizing usages

The first three new macros provide the non-concurrent-access-related uses of the old excl::atomically and without-interrupts macros.


3.2 Atomic read-modify-write primitives

When an atomic operation fits the pattern

(setf [place] (foo [place]))

and [place] is one of several inline-accessible 'slots' like (car x), the compiler can generate code to ensure that the value in [place] doesn't change between the initial read and the subsequent write. There are several macros that provide special cases of this operation, and a general conditional-update form on which all of them are based. [place] can be any of the following setf-places:

These places are a subset of places legal for setf. In particlar, they do not include local or special bound variables. Local places that cannot be shared between multiple processes, but the actual reason is really one of hardware/system limits on where can be done a low-level atomic read-modify-write.

The relevant macros are:


3.3 Concurrency control for shared objects

None of the deprecated macros provide effective concurrency control in an smp lisp. New macros are provided to give the programmer tools for controlling concurrent access. There is no way to make the change to smp automatic and painless. The crux of the problem is that in the absence of smp, one-sided concurrency control works. That is, a process modifying a shared object could wrap a series of modifications with pre-8.2 forms like those using without-interrupts, and be assured that all processes would see those changes as an atomic transaction. The forms themselves assured that no other process would see the object until all the changes were in place.

A confounding factor is that pre-8.2 concurrency was very coarse-grained. Processes were preempted at a very low frequency, typically once in 2 seconds, unless they explicitly waited on some condition. Even with no attempt at concurrency control, it was rare to see an inconveniently-timed process switch break a transaction that should have been atomic.

In an SMP Lisp, concurrency is as fine-grained as it could possibly be. Writers and readers must all cooperate to ensure that access to shared structures is legitimate.

Allegro CL has a set of object-locking macros. These are lighter weight and less flexible than the mp:process-lock features, and do not rely on the mp package. They must be used with care to avoid deadlocks.

The macros and related functionality are:



4.0 The 8.1 SMP-macros patch

A patch for Allegro CL 8.1 released in July, 2009 allows the SMP funcionality to be used in verion 8.1. This patch can only be loaded into an 8.1 Lisp. Applying it gives access to those smp-related macros described in this document that will be available in all 8.2 and later Lisps. Specifically, applying the patch to an 8.1 Lisp has the following effects:


Copyright (c) 1998-2009, Franz Inc. Oakland, CA., USA. All rights reserved.
Documentation for Allegro CL version 8.1. This page is new in the 8.1 release.
Created 2007.4.30.

ToCDocOverviewCGDocRelNotesFAQIndexPermutedIndex
Allegro CL version 8.1
New since 8.1 release.