All Manuals > LispWorks User Guide and Reference Manual > 19 Multiprocessing

NextPrevUpTopContentsIndex

19.3 Atomicity and thread-safety of the LispWorks implementation

Access to all Common Lisp objects is thread-safe in the sense that it does not cause an error because of threading issues.

19.3.1 Immutable objects

Immutable (or read-only) objects such as numbers, characters, functions, pathnames and restarts can be freely shared between threads, but special precautions must be taken when all of the following conditions are true:

In this situation, it is your responsibility to ensure that all of the stores that occurred when creating the new object are visible to the other threads, as described by Making an object's contents accessible to other threads.

19.3.2 Mutable objects supporting atomic access

This section outlines for which types of mutable Common Lisp object access is atomic. That is, each value read from the object will correspond to the state at some point in time. Note however, that if several values are read, there is no guarantee about how these values will relate to each other if they are being modified by another thread (see Issues with order of memory accesses).

When one of these mutable atomic objects is modified, readers see either the old or new value (not something else), and it is guaranteed that the Lisp image is not corrupted by the modification even if multiple threads read or write the object simultaneously.

Access to conses, simple arrays except arrays with element type of integer with less than 8 bits, symbols, packages and structures is atomic. Note that this does not apply to non-simple arrays.

Slot access in objects of type standard-object is atomic with respect to modification of the slots and with respect to class redefinition.

vector-pop, vector-push, vector-push-extend, (setf fill-pointer) and adjust-array are all atomic with respect to each other, and with respect to other access to the array elements.

The Common Lisp functions that access hash tables are atomic with respect to each other. See also modify-hash for atomic reading and writing an entry and with-hash-table-locked. See also Modifying a hash table with multiprocessing for thread-safe ways to ensure a table entry.

Access to packages is atomic.

Note that pathnames cannot be modified, and therefore access to them is always atomic.

Access to synchronization objects (of type mailbox, barrier, semaphore and condition-variable) is atomic. More information about these objects is in Synchronization between threads.

Operations on editor buffers (including points) are atomic and thread-safe as long as their arguments are valid. This includes modification to the text. However, buffers and points may become invalid because of execution on another thread. The macros editor:with-buffer-locked and editor:with-point-locked should be used around editor operations on buffers and points that may be affected by other processes. Note that this is applicable also to operations that do not actually modify the text, because they can behave inconsistently if the buffer they are looking at changes during the operation. See the LispWorks Editor User Guide for details of these macros.

19.3.3 Mutable objects not supporting atomic access

This section outlines for which types of mutable Common Lisp object access is not atomic.

Access to arrays with element type of integer of less than 8 bits is not guaranteed to be atomic.

Access to non-simple arrays is not guaranteed to be atomic.

Access to lists (including alists and plists) is not atomic. Lists are made of multiple cons objects, so although access to the individual conses is atomic, the same does not hold for the list as a whole.

Sequence operations which modify multiple elements are not atomic.

Macros that expand to multiple accesses are in general not atomic. In particular, modifying macros like push and incf are not atomic (but see the atomic versions of some of them in Low level atomic operations).

Making several calls to Common Lisp functions that access hash tables will not be atomic overall. However LispWorks provides thread-safe ways to ensure a hash table entry - see Modifying a hash table with multiprocessing. See also modify-hash for atomic reading and writing an entry and with-hash-table-locked.

Stream operations are in general not atomic. There is an undocumented interface for locking of streams when this is required - contact Lisp Support if you need this.

Operations on CAPI objects are not atomic in general. The same is true for anything in the LispWorks IDE. These operations need to be invoked from the thread that owns the object, for example by capi:execute-with-interface or capi:apply-in-pane-process.

19.3.4 Making an object's contents accessible to other threads

An object's contents become accessible to other threads when it is stored into a cell that may be accessed by those threads (a "globally accessible cell"). In most cases, you should either use a synchronization mechanism (typically a lock) to control access to the cell because it is the most reliable approach or use a mailbox to make the object accessible to other threads (the mailbox acts as the globally accessible cell).

If you do not use a synchronization mechanism or mailbox, then all stores into the object must be forced to be visible to other threads ("ensured") before the object is stored in the globally accessible cell. This also applies to any stores that LispWorks did during construction of the object. Normally, LispWorks does not do that for every store, because it would slow the program too much. Note that numbers, except fixnum and short-float (in 32-bit LispWorks) or fixnum and single-float (in 64-bit LispWorks), are also objects that are constructed using stores that need to be ensured.

Storing objects into globally accessible cells would typically be done by setf or a related macro such as push or incf, but can also be done by Common Lisp functions such as rplaca, fill, nsublis, nsubst or replace (when the target is globally accessible). If stores into the objects that these functions store have not been ensured and may be read by another thread without synchronization, then one of the mechanisms in Ways to guarantee the visibility of stores must be used. Note that when a sequence itself, rather than the elements, is modified, for example by delete, nreverse, nconc, nunion, then all access to the sequence needs to controlled by a synchronization mechanisms, which will also guarantee the visibility of stores.

19.3.4.1 Ways to guarantee the visibility of stores

The visibility (in other threads) of stores in an object referenced by a globally accessible cell can only be guaranteed in these situations:

  1. You use a lock or any other synchronization mechanism (barrier, condition-variable, semaphore, mailbox, or the lock of a hash-table) to serialize all access to the globally accessible cell. Any use of a synchronization mechanism that may affect the behavior of another thread will implicitly ensure all preceding stores on the current thread.
  2. The store is done by (setf symbol-function) or (setf macro-function) into a symbol, or by one of (setf gethash), vector-push, vector-push-extend into a "multithreaded" hash-table or vector (see Single-thread context arrays and hash-tables).
  3. You store a newly interned symbol (all stores that occur during interning are ensured). However, if the store is done using an operator that allocates (see Special care for macros and accessors that may themselves allocate) then you will still need to ensure.
  4. You use one of the low level atomic operations, all of which ensure all stores on the current thread before they modify the cell. This includes stores from any allocation they may do and applies also to user defined atomic modify macros that are defined by define-atomic-modify-macro. Currently these atomic operations are: compare-and-swap, atomic-exchange, atomic-push, atomic-pop, atomic-fixnum-incf, atomic-fixnum-decf, atomic-incf, atomic-decf. Any atomic operations added in the future will do the same.
  5. You start a new thread and access the object from that thread. LispWorks ensures all preceding stores on the current thread before the new thread runs, so if all accesses to an object occur in threads that start after the object was last modified then you do not need to ensure the stores into it.
  6. You are storing an immediate object (fixnum, character or short-float in 32-bit LispWorks; fixnum, character or single-float in 64-bit LispWorks) in the globally accessible cell. There are no stores that need to be ensured during the creation of these objects. However, if the store is done using an operator that allocates (see Special care for macros and accessors that may themselves allocate) then you will still need to ensure.
  7. The store is by setf or a related macro (for example push or incf), and the place argument is wrapped by the macro globally-accessible.
  8. You call ensure-stores-after-stores between the time the object was made (and any stores of interest were done into it) and the time it is stored into a globally accessible cell. ensure-stores-after-stores ensures all preceding stores in the current thread.
  9. Note: ensure-memory-after-store and ensure-stores-after-memory do what ensure-stores-after-stores does and more, but may be more expensive and are not required in this context.

Stores into objects must be "ensured" once by one of the above mechanisms, before the object becomes globally accessible. Stores that occur after this are not guaranteed to be visible to other threads until another ensuring operation.

In some circumstances you can make the program more efficient by explicitly ensuring stores using globally-accessible (7) or ensure-stores-after-memory (8) before or when the object is first made visible. See Ensuring stores are visible to other threads for more details.

A synchronizing operation (1), atomic operation (4) or a call to ensure-stores-after-stores (8) ensures all stores into objects that were created by the current thread. The other situations ensure the stores that they perform and anything pointed to by those stores, but are not guaranteed to ensure other stores (because they may be able to skip ensuring in some circumstances).

19.3.4.2 Special care for macros and accessors that may themselves allocate

A situation that always requires special care is storing into a globally accessible cell using macros and accessors that may themselves allocate. If the store is not done using (1), (4) or (5) in Ways to guarantee the visibility of stores, then you need to use globally-accessible to ensure the stores in new objects that may be allocated are visible, even if the object that is stored does not need it (because it is an immediate, an interned symbol or was ensured earlier). These macros and accessors include:

Macros:

push, pushnew, push-end, push-end-new, incf (when not a fixnum), decf (when not a fixnum).

Accessors:

getf, cdr-assoc, mask-field (when not a fixnum), ldb (when not a fixnum).

User defined accessors that allocate:

Any user defined accessor (that is an operator with a setf expander defined by define-setf-expander or defsetf) that allocates during the setting operation. Note that allocation during the macro expansion is not an issue.

See Destructive macros and accessors that allocate internally for more details.

19.3.5 Ensuring stores are visible to other threads

A store to a cell from one thread is said to be "visible" from another thread when a load from that cell from the other thread obtains the value that was stored. Within a single thread, all stores are visible immediately to loads from the same thread, but that is not always the case in a multithreaded situation. Store operations that occur in one thread are not necessarily visible from other threads until something ensures that they are. In other words, another thread loading from the cell where the store was done may still obtain the cell's previous value, even if "logically" it seems that the load happened after the store. For a new object, the previous value may be anything that was in memory, including an invalid value that may cause crashes.

19.3.5.1 An example to consider the issues

For example, assume that the symbol *a-global-symbol* is not dynamically bound anywhere and its value is nil, and we have two threads, A and B, executing without synchronization.

Thread A executes this code:

(setq *a-global-symbol* (cons 1 2))

and thread B executes this code:

(let ((maybe-cons *a-global-symbol*))
  (if (consp maybe-cons)
      (car maybe-cons)
    -1))

It looks like the form that thread B executes will always return either 1 (if it happens after thread A has set *a-global-symbol*) or -1 (otherwise), because in the case that maybe-cons is a cons it must already have 1 in the car. However, that is not necessarily true because the store of the cons into *a-global-symbol* may be visible to thread B before the store of 1 into the cons (which happens inside the call to cons) is visible. This applies to explicit stores in the program as well, for example if thread A executes:

(setq *a-global-symbol* (rplaca (list nil) 1))

then the same problem arises (in this case, the call to car in thread B may return 1, nil (the value that list stored in the car), or whatever was in that memory before that).

Note: the second load in thread B (inside car) is dependent on the first load (reading the value cell from *a-global-symbol*). Such dependent loads are guaranteed to occur in the program order in all current LispWorks releases. In situations when the two loads are independent, but you still need them to occur in the program order, you will need to use ensure-loads-after-loads.

19.3.5.2 The general solution using a lock

In most circumstances, all access to globally accessible cells should be controlled by a lock, which eliminates all of these problems because releasing a lock implicitly ensures that all stores in that thread are visible to all other threads, so by the time another thread gets ownership of the lock, all the stores are already visible. Sending an object via a mailbox, using (setf gethash), vector-push or vector-push-extend or synchronizing using any of the other synchronization mechanisms (barrier, condition-variable, semaphore or the lock of a hash-table) also ensures the stores are already visible (for a full list, see Making an object's contents accessible to other threads). If you make an object globally accessible without any of these mechanisms, then you need to ensure explicitly that the stores are all visible. Note that if the store occurs inside a lock but the object is not read inside the same lock, then you still need to ensure the stores, because the reading may happen before unlocking has ensured the stores are visible. Note also that, for some macros and accessors (listed below), you need to ensure the stores even if the value that you store does not need ensuring.

19.3.5.3 An alternative solution using globally-accessible

If you need to explicitly ensure that all stores are visible, then the best approach is to use globally-accessible, which takes a single argument, place, which can be any generalized reference form as described in section 5.1.1 Overview of Places and Generalized Reference of the Common Lisp HyperSpec. In most cases, (globally-accessible place) is the same as place. However, when globally-accessible is used inside setf or a related macro such as push or incf then it also ensures all stores are visible to other threads before modifying place. For example, if we change the code that thread A in An example to consider the issues executes to:

(setf (sys:globally-accessible *a-global-symbol*)
      (cons 1 2))

then the value returned by the form in thread B is guaranteed to be 1 or -1 as expected.

19.3.5.4 An alternative solution using ensure-stores-after-stores

The other approach is to use ensure-stores-after-stores just before storing into the globally accessible cell, but after any allocation or other operations that modify the object being stored in the cell. In the example in An example to consider the issues, thread A would do:

(let ((cons (cons 1 2)))
  (sys:ensure-stores-after-stores)
  (setq *a-global-symbol* cons))

ensure-stores-after-stores cannot be used when the form that stores the object is a destructive macro such as push (for a full list, see Destructive macros and accessors that allocate internally below), because push itself allocates a cons using stores that need to be ensured. globally-accessible takes care of that, by ensure the stores after any allocation that the macro may do (except when it is a macro with a non-standard setf expansion that allocates or stores in the setter). Thus globally-accessible is preferable when you can use it. You need to use ensure-stores-after-stores when the store is encapsulated in some other operation. For example, if you use fill to store a new object in a globally accessible sequence (some-vector below) then you will need to do something like this:

(let ((new-object (cons x y)))
  (sys:ensure-stores-after-stores)
  (fill some-vector new-object))

ensure-stores-after-stores always ensures all the stores that have happened in the current thread. globally-accessible is not guaranteed to ensure all preceding stores accept into the value that it stores, because it may be able to skip ensuring in some circumstances.

19.3.5.5 Destructive macros and accessors that allocate internally

The macros push, pushnew, push-end, push-end-new, incf (when not a fixnum) and decf (when not a fixnum) may generate new objects internally, so if they are used to destructively modify a globally accessible cell without synchronization then you will need to use globally-accessible.

For example:

(pushnew some-object (sys:globally-accessible *a-global-symbol*))

Note that globally-accessible is needed with push, pushnew, push-end, and push-end-new even if there are no stores into the object being pushed that need ensuring. For incf and decf, if you can guarantee that the new value is fixnum, then you do not need globally-accessible.

The accessors getf, cdr-assoc, mask-field and ldb take a place argument that may generate new objects when modified, so if place is globally accessible and it is modified without synchronization then you will need to wrap globally-accessible around such modifications of place.

For example:

(setf (getf (sys:globally-accessible *a-global-symbol*)
            :key) 
      value)

For getf and cdr-assoc, globally-accessible is needed even if there are no stores into the new object and key that need ensuring because new conses might be added to the place. For mask-field and ldb, if you are absolutely sure that the new value is fixnum then you do not need globally-accessible.

In addition, setf expanders defined by define-setf-expander or defsetf cannot be used on globally accessible cells without synchronization (by a lock or other synchronization mechanism) if they do any of the following:

See section 5.1.1.2 Setf Expansions of the Common Lisp HyperSpec for the definition of "value forms" and "storing form".

19.3.5.6 Miscellaneous notes

For an object that is not modified later, ensuring all stores when the object is created is sufficient, and after that the object can be used freely from any thread.

ensure-stores-after-stores can be used to ensure stores for objects that are modified after becoming globally accessible. However, if you need to ensure that the new values are seen by other threads that may be already accessing the modified objects then you need to use some synchronization mechanism anyway. Thus in most cases you should use a lock, which will deal with the synchronization.

ensure-stores-after-stores does slow the program a little on architectures that need it (Currently ARM, ARM64 and PowerPC), so you can consider the following optimizations:

As noted in Ensuring stores are visible to other threads, loads from an object that was obtained from a globally accessible cell are currently guaranteed to occur after the load the cell itself, because all the architectures that LispWorks runs on guarantee that. In principle, sometime in the future there may be a new architecture that does not provide that guarantee. You can guard against this by using globally-accessible when reading from the globally accessible cell as well. Currently that just macroexpands into its argument, so does not affect the performance, but for an architecture that requires anything it will do the right thing.

19.3.6 Issues with order of memory accesses

When multiple threads access the same memory location, the order of those accesses is not generally guaranteed. You should therefore not attempt to implement "lockless algorithms" which depend on the order of memory accesses unless you have a good understanding of multiprocessing issues at the CPU level (see Ensuring order of memory between operations in different threads).

However, all of the Low level atomic operations and locking operations (see Locks) do ensure that all memory accesses that happen before them have finished and that all memory accesses that happen after them start after them. Therefore, normally there is nothing special to consider when using those operations. The modification check macros described in Aids for implementing modification checks also take care of this.

19.3.7 Single-thread context arrays and hash-tables

Access to hash tables and non-simple arrays can be improved where they are known to be accessed in a single thread context. That is, only one thread at the same time accesses them.

The make-hash-table argument single-thread tells make-hash-table that the table is going to be used only in single thread context, and therefore does not need to be thread-safe. Such a table allows faster access.

Similarly the make-array argument single-thread creates an array that is single threaded. Currently, the main effect of single-thread is on the speed of vector-pop, vector-push. and vector-push-extend on non-simple vectors. These operations are much faster on "single threaded" vectors, typically more than twice as fast as "multithreaded" vectors.

You can also make an array be "single-threaded" with set-array-single-thread-p.

The result of parallel access to a "single-threaded" vector is unpredictable.


LispWorks User Guide and Reference Manual - 20 Sep 2017

NextPrevUpTopContentsIndex