230: Atomic Operations

by Marc Nieper-Wißkirchen

Status

This SRFI is currently in final status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-230@nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

• Received: 2021-08-29
• Draft #1 published: 2021-09-01
• Draft #2 published: 2021-11-07
• Finalized: 2021-11-15

Abstract

This SRFI defines atomic operations for the Scheme programming language. An atomic operation is an operation that, even in the presence of multiple threads, is either executed completely or not at all. Atomic operations can be used to implement mutexes and other synchronization primitives, and they can be used to make concurrent algorithms lock-free. For this, this SRFI defines two data types, atomic flags and atomic (fixnum) boxes, whose contents can be queried and mutated atomically. Moreover, each atomic operation comes with a memory order that defines the level of synchronization with other threads.

Rationale

Virtually all modern multi-threaded CPUs support atomic operations. They can often be used to avoid costly locks in concurrent programming. Many general-purpose programming languages like C, C++, Go, or Rust expose a standard set of atomic operations to the programmer. This SRFI does the same for the Scheme programming language.

This SRFI is particularly interesting for multi-threaded applications, e.g. those based on SRFI 18 (or any other threading library), but can also be used in general library code to make it thread-safe.

Example

The following example shows a typical use of atomic fixnum boxes. If the counter were a regular variable, the read-modify-write operation of increasing the counter might be interrupted by another one in a different thread, resulting in a total count too small.

(import (scheme base)
	(scheme write)
	(srfi 18)
	(srfi 230))

(define *atomic-counter* (make-atomic-fxbox 0))

(define (task)
  (do ((i 0 (+ i 1)))
      ((= i 1000))
    (atomic-fxbox+/fetch! *atomic-counter* 1)))

(define threads (make-vector 10))

(do ((i 0 (+ i 1)))
    ((= i 10))
  (let ((thread (make-thread task)))
    (vector-set! threads i thread)
    (thread-start! thread)))

(do ((i 0 (+ i 1)))
    ((= i 10))
  (thread-join! (vector-ref threads i)))

(display (atomic-fxbox-ref *atomic-counter*))
(newline)

Specification

The procedures and syntax described in this section are exported by the (srfi 230) library in an R⁷RS system and by both the (srfi :230 atomic) and (srfi :230) libraries in an R⁶RS system.

Entry format

The following naming conventions imply type restrictions:

obj

expected

desired

any object

fx

fixnum

memory-order

any memory order

atomic-flag

atomic flag

atomic-box

atomic box

atomic-fxbox

atomic fixnum box

atomic-pair

atomic pair

Atomicity

Unless otherwise specified, all procedures prefixed with atomic- in the library are executed atomically.

Note: In a safe top-level program (in the sense of R⁶RS), all reads and writes to the store are necessarily atomic. In particular, a library implementing SRFI 18 is not necessarily safe.

Memory orders

The memory order specifies how accesses, including regular, non-atomic memory accesses, are to be ordered around an atomic operation. When multiple threads simultaneously read and write to several variables, one thread can observe the values change in an order different from the order in which another thread wrote them. Indeed, the apparent order of changes can even differ among multiple reader threads.

The default behavior of all atomic operations defined in this library provides for sequentially consistent ordering (see below). That default can hurt performance, but the library's atomic operations can be given an additional memory-order argument to specify the exact constraints, beyond atomicity, that the implementation must enforce for that operation.

Atomic operations can be given the following memory orders to modify the default behavior:

relaxed

Relaxed operation: there are no synchronization or ordering constraints imposed on other reads or writes. Only this operation's atomicity is guaranteed.

acquire

A read operation on the store with this memory order performs the acquire operation on the affected memory location: no reads or writes in the current thread can be reordered before this read. All writes in other threads that release the same atomic variable are visible in the current thread.

release

A write operation on the store with this memory order performs the release operation: no reads or writes in the current thread can be reordered after this write. All writes in the current thread are visible in other threads that acquire the same atomic variable.

acquire-release

A read-modify-write operation on the store with this memory order is both an acquire operation and a release operation. No reads or writes on the store in the current thread can be reordered before or after this write. All writes in other threads that release the same atomic variable are visible before the modification and the modification is visible in other threads that acquire the same atomic variable.

sequentially-consistent

A read operation on the store with this memory order performs an acquire operation, a write performs a release operation, and read-modify-write performs both an acquire operation and a release operation, plus a single total order exists in which all threads observe all modifications in the same order.

(memory-order memory-order symbol)syntax

It is a syntax violation if memory-order symbol is not a symbol whose name is one of relaxed, acquire, release, acquire-release, and sequentially-consistent. The result is the corresponding symbol, and specifies the associated memory order.

Note: Only the name of memory-order symbol is significant.

(memory-order? obj)procedure

Returns #t if the argument is a valid memory-order symbol, and returns #f otherwise.

Atomic flags

An atomic flag is tagged with a location that can be either in the clear state or in the set state and which can be changed and tested atomically.

(make-atomic-flag)procedure

Returns a newly allocated atomic flag, which is initially in the clear state.

(atomic-flag? obj)procedure

Returns #t if obj is an atomic flag, and returns #f otherwise.

(atomic-flag-test-and-set! atomic-flag)procedure

(atomic-flag-test-and-set! atomic-flag memory-order)procedure

Returns #t if the state of atomic-flag is set, and returns #f otherwise. Changes the state of atomic-flag to set.

(atomic-flag-clear! atomic-flag)procedure

(atomic-flag-clear! atomic-flag memory-order)procedure

Changes the state of atomic-flag to clear.

Atomic boxes

An atomic box is tagged with a location that can hold any object, the content of the atomic box, and which can be changed and tested atomically.

(make-atomic-box obj)procedure

Returns a newly allocated atomic box whose initial content is obj.

(atomic-box? obj)procedure

Returns #t if obj is an atomic box, and returns #f otherwise.

(atomic-box-ref atomic-box)procedure

(atomic-box-ref atomic-box memory-order)procedure

Returns the content of atomic-box.

(atomic-box-set! atomic-box obj)procedure

(atomic-box-set! atomic-box obj memory-order)procedure

Sets the content of atomic-box to obj, and returns unspecified values.

(atomic-box-swap! atomic-box obj)procedure

(atomic-box-swap! atomic-box obj memory-order)procedure

Sets of the content of atomic-box to obj, and returns the previous content.

(atomic-box-compare-and-swap! atomic-box expected desired)procedure

(atomic-box-compare-and-swap! atomic-box expected desired memory-order)procedure

Operationally equivalent to the following, executed atomically:

(let ((actual (atomic-box-ref atomic-box memory-order)))
  (when (eq? actual expected)
    (atomic-box-set! atomic-box desired memory-order))
  actual)

Atomic fixnum boxes

An atomic fixnum box is tagged with a location that can hold a fixnum, the content of the atomic fixnum box, which can be changed and tested atomically.

(make-atomic-fxbox obj)procedure

Returns a newly allocated atomic fixnum box whose initial content is obj.

(atomic-fxbox? obj)procedure

Returns #t if obj is an atomic fixnum box, and returns #f otherwise.

(atomic-fxbox-ref atomic-fxbox)procedure

(atomic-fxbox-ref atomic-fxbox memory-order)procedure

Returns the content of atomic-fxbox.

(atomic-fxbox-set! atomic-fxbox fx)procedure

(atomic-fxbox-set! atomic-fxbox fx memory-order)procedure

Sets the content of atomic-fxbox to fx, and returns unspecified values.

(atomic-fxbox-swap! atomic-fxbox fx)procedure

(atomic-fxbox-swap! atomic-fxbox fx memory-order)procedure

Sets of the content of atomic-fxbox to fx, and returns the previous content.

(atomic-fxbox-compare-and-swap! atomic-fxbox expected desired)procedure

(atomic-fxbox-compare-and-swap! atomic-fxbox expected desired memory-order)procedure

Operationally equivalent to the following, executed atomically:

(let ((actual (atomic-fxbox-ref atomic-fxbox memory-order)))
  (when (fx=? actual expected)
    (atomic-fxbox-set! atomic-fxbox desired memory-order))
  actual)

(atomic-fxbox+/fetch! atomic-fxbox fx)procedure

(atomic-fxbox+/fetch! atomic-fxbox fx memory-order)procedure

Sets the content of atomic-fxbox to the sum of the previous content and fx, and returns the previous content.

(atomic-fxbox-/fetch! atomic-fxbox fx)procedure

(atomic-fxbox-/fetch! atomic-fxbox fx memory-order)procedure

Sets the content of atomic-fxbox to the difference of the previous content and fx, and returns the previous content.

(atomic-fxbox-and/fetch! atomic-fxbox fx)procedure

(atomic-fxbox-and/fetch! atomic-fxbox fx memory-order)procedure

Sets the content of atomic-fxbox to the bitwise and of the previous content and fx, and returns the previous content.

(atomic-fxbox-ior/fetch! atomic-fxbox fx)procedure

(atomic-fxbox-ior/fetch! atomic-fxbox fx memory-order)procedure

Sets the content of atomic-fxbox to the bitwise inclusive or of the previous content and fx, and returns the previous content.

(atomic-fxbox-xor/fetch! atomic-fxbox fx)procedure

(atomic-fxbox-xor/fetch! atomic-fxbox fx memory-order)procedure

Sets the content of atomic-fxbox to the bitwise exclusive or of the previous content and fx, and returns the previous content.

Atomic pairs

An atomic pair is tagged with two locations that can hold a pair of Scheme objects, the contents of the atomic pair, and which can be changed and tested atomically.

Atomic pairs can be used to solve the so-called ABA problem, for example.

(make-atomic-pair obj1 obj2)procedure

Returns a newly allocated atomic pair whose initial contents are obj1 and obj2.

(atomic-pair? obj)procedure

Returns #t if obj is an atomic pair, and returns #f otherwise.

(atomic-pair-ref atomic-pair)procedure

(atomic-pair-ref atomic-pair memory-order)procedure

Returns the contents of atomic-pair as two values.

(atomic-pair-set! atomic-pair obj1 obj2)procedure

(atomic-pair-set! atomic-pair obj1 obj2 memory-order)procedure

Sets the content of atomic-pair to obj1 and obj2, and returns unspecified values.

(atomic-pair-swap! atomic-pair obj1 obj2)procedure

(atomic-pair-swap! atomic-pair obj1 obj2 memory-order)procedure

Sets the content of atomic-pair to obj1 and obj2, and returns the previous contents as two values.

(atomic-pair-compare-and-swap! atomic-pair expected1 expected2 desired1 desired2)procedure

(atomic-pair-compare-and-swap! atomic-pair expected1 expected2 desired1 desired2 memory-order)procedure

Operationally equivalent to the following, executed atomically:

(let-values (((actual1 actual2) (atomic-pair-ref atomic-pair memory-order)))
  (when (and (eq? actual1 expected1) (eq? actual2 expected2))
    (atomic-pair-set! atomic-pair desired1 desired2 memory-order))
  (values actual1 actual2))

Memory synchronization

(atomic-fence memory-order)procedure

Establishes memory synchronization ordering of non-atomic and relaxed atomic accesses, as instructed by memory-order, without an associated atomic operation. Returns unspecified values.

Note: As this procedure does not store a value into a previous allocated location, its name does not end in “!”.

Implementation

For Schemes that do not support multiple threads, an implementation of this SRFI is trivial as all operations are automatically atomic. In particular, atomic flags and atomic boxes could be represented by SRFI 111 boxes.

For Schemes that support multiple threads, an implementation based on SRFI 18 or SRFI 226 mutexes is possible.

The primitives defined in this SRFI are all supported by modern multi-threaded CPUs and are also implemented in the C and the C++ programming languages. Thus, Scheme systems with a native compiler or Scheme systems with a virtual machine based on C or C++ can easily implement this SRFI efficiently.

The sample implementation is an R⁷RS implementation based on SRFI 18.

Acknowledgements

This SRFI was inspired by the C11 atomic operations library.

It uses language from the C reference wiki.

Many thanks go to Justin Ethier, who implemented SRFI 230 natively for his Cyclone Scheme compiler.

Likewise, thanks go to Göran Weinholt for private feedback. He pointed out to me the omission of double-width CAS operations in the first draft.

Shiro Kawai wrote portable tests.

Copyright

© 2021 Marc Nieper-Wißkirchen.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice (including the next paragraph) shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.