Atomics

Atomics are variables used in multithreading to protect against race conditions by guaranteeing thread-safe access to shared variables. The main idea is that standard operations on atomic objects are indivisible and linearisable. What does this mean?

• Indivisibility guarantees that the atomic operation is executed as a single, uninterruptible step from the POV of other threads. What this means is that while the atomic operation is running, no other thread can access or modify the same variable. This means that other threads must wait for the operation to terminate before modifying it.
  • i.e., the operation looks like it’s either finished or didn’t happen at all
• Linearisability refers to the idea that each thread can modify the atomic variable in a pseudo-linear, sequential way. Multiple threads can take turns sequentially until they’re all done using the variable.

Atomic operations are the building blocks for all concurrency tools in programming.

Key considerations

In general, atomics are best used for simple operations on single variables less than a single word. If we program involving complicated scenarios with multiple variables/data structures, it may be better to use a higher-level synchronisation tool like mutexes.

This is because atomics are limited by the underlying architecture’s word size. If something is larger than the word size, load/store operations (writing from one thread, reading from another) will take multiple instructions and it’s possible for conflicts. This mean’s there’s overhead (locking) in ensuring indivisibility (from the POV of other threads).

For example, think about reading/writing a 64-bit integer on a 32-bit system. We’d need at least two operations (lw and sw), and we might be unlucky enough to land in the middle of this.

For arbitrary atomic types, the compiler/runtime adds locks around the variable’s reads and writes. Locks add extra problems we try to avoid: extra CPU time, difficulties debugging. This is done via a few different locking mechanisms: spinlocks, mutexes, semaphores. This is supported in hardware, via the operating system, via compilers, and via libraries.

Atomic variables are like rendezvous points for threads. Atomic types establish a single total modification order called sequential consistency, which implies that operations appear to take place in some total order, and that that order is consistent with the order of operations on each individual thread.

Thread A, B. Even if a thread is far ahead of another thread, if A has observed some operation from B, it can never observe a state prior to B.

Operations

Read-modify-write operations do exactly that: they read, modify and write in a single atomic step. There’s a few types that’re important to know, most of which have some assembly instruction support.

• Exchanges read and replace a new value.
• Test-and-sets work on a Boolean value. They’re read, set to true, and provided what it held beforehand.
• Fetch operations read a value, perform a simple ALU operation on it, and return its previous value.
• Compare-and-swaps conditionally exchange a value if its previous value matches an expected one. On x86, we use cmpxchg.

All synchronisation tools are build on these basic atomic operations. For example, spinlocks rely on test-and-sets.

Language-specific

In C++

The STL has the std::atomic<T> template for defining arbitrary atomic types (as of C++11).

To check if a variable is free of any locks (which is known at compile-time), we can use:

std::atomic<Foo> bar;
ASSERT(bar.is_lock_free());

In C

In C, we declare types with the _Atomic type qualifier (as of C11). There are no atomic array types. A systematic way to declare atomics is the following, which ensures that we keep the array restriction in mind:

_Atomic(<type>); // i.e.,
_Atomic(double[45]) C; // invalid!
_Atomic(double) D[45]; // valid!

For the most part, the C atomics standard was pulled mostly from C++. This means that much of the code described in the above section applies equally to C.

Resources

• What every systems programmer should know about concurrency, by Matt Kline