Concurrency Primer 1
Matt Kline and Ching-Chun (Jim) Huang
August 27, 2026
Abstract
System programmers are acquainted with tools such as mutexes, semaphores, and condition variables. However, the question remains: how do these tools work, and how do we write concurrent code in their absence? For example, when working in an embedded environment beneath the operating system, or when faced with hard time constraints that prohibit blocking. Furthermore, since the compiler and hardware often combine to transform code into an unanticipated order, how do multithreaded programs work? Concurrency is a complex and counterintuitive topic, but let us endeavor to explore its fundamental principles.
-
The original title was “What every systems programmer should know about concurrency”. ↩
Background
Modern computers execute multiple instruction streams concurrently. On single-core systems, these streams alternate, sharing the CPU in brief time slices. Multi-core systems, however, allow several streams to run in parallel. These streams are known by various names such as processes, threads, tasks, interrupt service routines (ISR), among others, yet many of the same principles govern them all.
Despite the development of numerous sophisticated abstractions by computer scientists, these instruction streams—hereafter referred to as “threads” for simplicity—primarily interact through shared state. Proper functioning hinges on understanding the sequence in which threads read from and write to memory. Consider a simple scenario where thread A communicates an integer with other threads: it writes the integer to a variable and then sets a flag, signaling other threads to read the newly stored value. This operation could be conceptualized in code as follows:
int v;
bool v_ready = false;
void threadA()
{
// Write the value
// and set its ready flag.
v = 42;
v_ready = true;
}
void threadB()
{
// Await a value change and read it.
while (!v_ready) { /* wait */ }
const int b_v = v;
// Do something with b_v...
}
We must ensure that other threads only observe A’s write to v_ready after A’s write to v.
If another thread can “see” v_ready becoming true before observing v becoming \(42\),
this simple scheme will not work correctly.
One might assume it is straightforward to ensure this order, yet the reality is often more complex. Initially, any optimizing compiler will restructure your code to enhance performance on its target hardware. The primary objective is to maintain the operational effect within the current thread, allowing reads and writes to be rearranged to prevent pipeline stalls1 or to optimize data locality.2
Variables may be allocated to the same memory location if their usage does not overlap. Furthermore, calculations might be performed speculatively ahead of a branch decision and subsequently discarded if the branch prediction proves incorrect.3
Even without compiler alterations, we would face challenges because our hardware complicates matters further! Modern CPUs operate in a fashion far more complex than what traditional pipelined methods, like those depicted in the figure, suggest. They are equipped with multiple data paths tailored for various instruction types and schedulers that reorder and direct instructions through these paths.
A traditional five-stage CPU pipeline with fetch, decode, execute, memory access, and write-back stages. Modern designs are much more complicated, often reordering instructions on the fly.
It is quite common to form oversimplified views about memory operations. Picturing a multi-core processor setup might lead us to envision a model similar to the figure, wherein each core alternately accesses and manipulates the system’s memory.
An idealized multi-core processor where cores take turns accessing a single shared set of memory.
The reality is far from straightforward. Although processor speeds have surged exponentially in recent decades, RAM has struggled to match pace, leading to a significant gap between the execution time of an instruction and the time required to fetch its data from memory. To mitigate this, hardware designers have incorporated increasingly complex hierarchical caches directly onto the CPU die. Additionally, each core often features a store buffer to manage pending writes while allowing further instructions to proceed. Ensuring this memory system remains coherent, thus allowing writes made by one core to be observable by others even when utilizing different caches, presents a significant challenge.
A common memory hierarchy for modern multi-core processors
The myriad complexities within multithreaded programs on multi-core CPUs lead to a lack of a uniform concept of “now”. Establishing some semblance of order among threads requires a concerted effort involving the hardware, compiler, programming language, and your application. Let’s delve into our options and the tools necessary for this endeavor.
-
Most CPU architectures execute segments of multiple instructions concurrently to improve throughput (refer to the figure). A stall, or suspension of forward progress, occurs when an instruction awaits the outcome of a preceding one in the pipeline until the necessary result becomes available. ↩
-
RAM accesses data not byte by byte, but in larger units known as cache lines. Grouping frequently used variables on the same cache line means they are processed together, significantly boosting performance. However, as discussed in Shared Resources, this strategy can lead to complications when cache lines are shared across cores. ↩
-
Profile-guided optimization (PGO) often employs this strategy. ↩
Enforcing law and order
Establishing order in multithreaded programs varies across different CPU architectures. For years, systems languages like C and C++ lacked built-in concurrency mechanisms, compelling developers to rely on assembly or compiler-specific extensions. This gap was bridged in 2011 when the ISO standards for both languages introduced synchronization tools. Provided these tools are used correctly, the compiler ensures that neither its optimization processes nor the CPU will perform reorderings that could lead to data races.1
To ensure our earlier example functions as intended, the “ready” flag must utilize an atomic type.
#include <stdatomic.h>
int v = 0;
atomic_bool v_ready = false;
void *threadA()
{
v = 42;
v_ready = true;
}
int b_v;
void *threadB()
{
while(!v_ready) { /* wait */ }
b_v = v;
/* Do something */
}
The C and C++ standard libraries define a series of these types in <stdatomic.h> and <atomic>,
respectively.
They look and act just like the integer types they mirror (e.g., bool → atomic_bool,
int → atomic_int, etc.),
but the compiler ensures that other variables’ loads and stores are not reordered around theirs.
Informally, we can think of atomic variables as rendezvous points for threads.
By making v_ready atomic,
v = 42 is now guaranteed to happen before v_ready = true in thread A,
just as b_v = v must happen after reading v_ready
in thread B.
Formally, atomic types establish a single total modification order where,
“[…] the result of any execution is the same as if the reads and writes occurred in some order, and the operations of each individual processor appear in this sequence in the order specified by its program.”
This model, defined by Leslie Lamport in 1979,
is called sequential consistency.
Notice that using atomic variables as an lvalue expression, such as v_ready = true and while(!v_ready), is a convenient alternative to explicitly using atomic_load or atomic_store.2
As stated in C11 6.7.2.4 and 6.7.3, the properties associated with atomic types are meaningful only for expressions that are
lvalues.
Lvalue-to-rvalue conversion (which models a memory read from an atomic location to a CPU register) strips atomicity along with other qualifiers.
-
The ISO C11 standard adopted its concurrency features, almost directly, from the C++11 standard. Thus, the functionalities discussed should be the same in both languages, with some minor syntactical differences favoring C++ for clarity. ↩
-
Atomic load/store operations are not necessarily generated as atomic instructions. Under a weaker consistency model, they could simply be normal load/store operations, and their code generation can vary across different architectures. Check out LLVM’s documentation as an example to see how it is handled. ↩
Atomicity
But order is only one of the vital ingredients for inter-thread communication. The other is what atomic types are named for: atomicity. Something is atomic if it can not be divided into smaller parts. If threads do not use atomic reads and writes to share data, we are still in trouble.
Consider a program with two threads. One thread processes a list of files, incrementing a counter each time it finishes working on one. The other thread handles the user interface, periodically reading the counter to update a progress bar. If that counter is a 64-bit integer, we can not access it atomically on 32-bit machines, since we need two loads or stores to read or write the entire value. If we are particularly unlucky, the first thread could be halfway through writing the counter when the second thread reads it, receiving garbage. These unfortunate occasions are called torn reads and writes.
If reads and writes to the counter are atomic, however, our problem disappears. We can see that, compared to the difficulties of establishing the right order, atomicity is fairly straightforward: just make sure that any variables used for thread synchronization are no larger than the CPU word size.
A flowchart depicting how two concurrent programs communicate and coordinate through a shared resource to achieve a goal, accessing the shared resource.
Summary of concepts from the first three sections, as shown in the figure. In Background, we observe the importance of maintaining the correct order of operations: \(t3 \to t4 \to t5 \to t6 \to t7\), so that two concurrent programs can function as expected. In Enforcing law and order, we see how two concurrent programs communicate to guarantee the order of operations: \(t5 \to t6\). In Atomicity, we understand that certain operations must be treated as a single atomic step to ensure the order of operations: \(t3 \to t4 \to t5\) and the order of operations: \(t6 \to t7\).
Arbitrarily-sized “atomic” types
Along with atomic_int and friends,
C++ provides the template std::atomic<T> for defining arbitrary atomic types.
C, lacking a similar language feature but wanting to provide the same functionality,
added an _Atomic keyword.
If T is larger than the machine’s word size,
the compiler and the language runtime automatically surround the variable’s reads and writes with locks.
If you want to make sure this is not happening,1
you can check with:
std::atomic<Foo> bar;
ASSERT(bar.is_lock_free());
In most cases,2
this information is known at compile time.
Consequently, C++17 added is_always_lock_free:
static_assert(std::atomic<Foo>::is_always_lock_free);
-
…which is most of the time, since we are usually using atomic operations to avoid locks in the first place. ↩
-
The language standards permit atomic types to be sometimes lock-free. This might be necessary for architectures that do not guarantee atomicity for unaligned reads and writes. ↩
Read-modify-write
So far we have introduced the importance of order and atomicity. In Enforcing law and order, we see how an atomic object ensures the order of a single store or load operation is not reordered by the compiler within a program. Only upon establishing the correct inter-thread order can we continue to pursue how multiple threads can establish a correct cross-thread order. After achieving this goal, we can further explore how concurrent threads can coordinate and collaborate smoothly. In Atomicity, there is a need for atomicity to ensure that a group of operations is not only sequentially executed but also completes without being interrupted by operations from other threads. This establishes the correct order of operations from different threads.
Exchange, Test and Set, Fetch and…, Compare and Swap can all be transformed into atomic RMW operations, ensuring that operations like \(t1 \to t2 \to t3\) will become an atomic step.
Atomic loads and stores are all well and good when we do not need to consider the previous state of atomic variables, but sometimes we need to read a value, modify it, and write it back as a single atomic step. As shown in the figure, the modification is based on the previous state that is visible for reading, and the result is then written back. A complete read-modify-write operation is performed atomically to ensure visibility to subsequent operations.
Furthermore, for communication between concurrent threads, a shared resource is required, as shown in the figure. Think back to the discussion in previous sections. In order for concurrent threads to collaborate on operating a shared resource, we need a way to communicate. Thus, the need for a channel for communication arises with the appearance of the shared resource.
As discussed earlier, the process of accessing shared resources responsible for communication must also ensure both order and non-interference. To prevent the recursive protection of shared resources, atomic operations can be introduced for the shared resources responsible for communication, as shown in the figure.
There are a few common read-modify-write (RMW) operations that turn a read, a modification, and a write into a single atomic step.
In C++, they are represented as member functions of std::atomic<T>.
In C, they are freestanding functions.
Test and Set (Left) and Compare and Swap (Right) leverage their functionality of checking and their atomicity to make other RMW operations perform atomically. The red color represents atomic RMW operations, while the blue color represents RMW operations that behave atomically.
Exchange
Transform RMW into modifying a private variable first, and then directly swapping the private variable with the shared variable. Therefore, we only need to ensure that the second step, which involves a Read that loads the shared variable, followed by Modify and Write steps that exchange it with the private variable, is a single atomic step. This allows programmers to extensively modify the private variable beforehand and only write it to the shared variable when necessary.
Test and set
Test-and-set works on a Boolean value:
we read it, set it to true, and provide the value it held beforehand.
C and C++ offer a type dedicated to this purpose, called atomic_flag.
The initial value of an atomic_flag is indeterminate until initialized with the ATOMIC_FLAG_INIT macro.
Test-and-set operations are not limited to just RMW functions; they can also be utilized for constructing a simple spinlock. In this scenario, the flag acts as a shared resource for communication between threads. Thus, a spinlock implemented with Test-and-set operations ensures that each full RMW operation on shared resources is performed atomically, as shown in the figure.
atomic_flag af = ATOMIC_FLAG_INIT;
void lock()
{
while (atomic_flag_test_and_set(&af)) { /* wait */ }
}
void unlock() { atomic_flag_clear(&af); }
If we call lock() and the previous value is false,
we are the first to acquire the lock,
and can proceed with exclusive access to whatever the lock protects.
If the previous value is true,
someone else has acquired the lock and we must wait until they release it by clearing the flag.
Fetch and…
Transform RMW to directly modify the shared variable (such as addition, subtraction, or bitwise AND, OR, XOR) and return its previous value, all as part of a single atomic operation. Compared with Exchange in Exchange, when programmers only need to make a simple modification to the shared variable, they can use Fetch-and….
Compare and swap
Finally, we have compare-and-swap (CAS), sometimes called compare-and-exchange. It allows us to conditionally exchange a value if its previous value matches the expected one. In C and C++, as noted in C11 7.17.7.4, CAS resembles the following, if it were executed atomically:
/* A is an atomic type. C is the non-atomic type corresponding to A */
bool atomic_compare_exchange_strong(A* obj, C* expected, C desired)
{
if (memcmp(obj, expected, sizeof(*obj)) == 0) {
memcpy(obj, &desired, sizeof(*obj));
return true;
} else {
memcpy(expected, obj, sizeof(*obj));
return false;
}
}
The _strong suffix may leave you wondering if there is a corresponding “weak” CAS.
Indeed, there is. However, we will delve into that topic later in Spurious LL/SC failures.
Because CAS involves an expected value comparison, it allows CAS operations to extend beyond just RMW functions. Here’s how it works: First, read the shared resource and use this value as the expected value. Modify the private variable, and then CAS. Compare the current shared variable with the expected shared variable. If they match, it indicates that Modify is exclusive, and then write by swapping the shared variable with the private variable. If they don’t match, it implies that interference from another thread has occurred. Subsequently, update the expected value with the current shared value and retry Modify in a loop. This iterative process allows CAS to serve as a communication mechanism between threads, ensuring that entire RMW operations on shared resources are performed atomically. As shown in the figure, compared with Test-and-set Test and set, a thread that employs CAS can directly use the shared resource to check. It uses atomic CAS to ensure that the Modify step is atomic, coupled with a while loop to ensure that the entire RMW can behave atomically.
However, atomic RMW operations here are merely a programming tool for programmers to achieve program logic correctness. Whether they actually execute atomically depends on how the compiler translates them into atomic instructions for a given hardware instruction set. At the instruction level, Exchange, Fetch-and-Add, Test-and-set, and CAS are different styles of atomic RMW instructions. An ISA may provide only some of them, leaving the rest to compilers to synthesize atomic RMW operations. For example, in IA32/64 and IBM System/360/z architectures, Test-and-set functionality is directly supported by hardware instructions. x86 has XCHG and XADD for Exchange and Fetch-and-Add, but implements Test-and-set with XCHG. Arm takes another approach, providing LL/SC (Load Linked/Store Conditional)-style instructions for all the operations, with CAS added in Armv8/v9-A.
Example
The following example code is a simplified implementation of a thread pool, which demonstrates the use of the C11 atomic library.
#include <stdio.h>
#include <stdatomic.h>
#include <threads.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <math.h>
#define PRECISION 100 /* upper bound in BPP sum */
#define CACHE_LINE_SIZE 64
#define N_THREADS 64
struct tpool_future {
void *result;
void *arg;
atomic_flag flag;
};
typedef struct job {
void *(*func)(void *);
struct tpool_future *future;
struct job *next, *prev;
} job_t;
typedef struct idle_job {
/* Padding alone only sizes the struct; the alignment is what keeps "prev"
* off a cache line shared with anything else, and it requires an
* allocation aligned to match. See tpool_init.
*/
_Alignas(CACHE_LINE_SIZE) _Atomic(job_t *) prev;
char padding[CACHE_LINE_SIZE -
sizeof(_Atomic(job_t *))]; /* avoid false sharing */
job_t job;
} idle_job_t;
enum state { idle, running, cancelled };
typedef struct tpool {
atomic_flag initialized;
int size;
thrd_t *pool;
atomic_int state;
thrd_start_t func;
idle_job_t *head; /* job queue is a SPMC ring buffer */
} tpool_t;
static struct tpool_future *tpool_future_create(void *arg)
{
struct tpool_future *future = malloc(sizeof(struct tpool_future));
if (future) {
future->result = NULL;
future->arg = arg;
atomic_flag_clear(&future->flag);
atomic_flag_test_and_set(&future->flag);
}
return future;
}
void tpool_future_wait(struct tpool_future *future)
{
while (atomic_flag_test_and_set(&future->flag))
;
}
void tpool_future_destroy(struct tpool_future *future)
{
free(future->result);
free(future);
}
static int worker(void *args)
{
if (!args)
return EXIT_FAILURE;
tpool_t *thrd_pool = (tpool_t *)args;
while (1) {
/* worker is laid off */
if (atomic_load(&thrd_pool->state) == cancelled)
return EXIT_SUCCESS;
if (atomic_load(&thrd_pool->state) == running) {
/* worker takes the job */
job_t *job = atomic_load(&thrd_pool->head->prev);
/* A failed compare-exchange reloads "job", so the idle job has to
* be ruled out on every iteration, not just once up front.
*/
while (job != &thrd_pool->head->job &&
!atomic_compare_exchange_weak(&thrd_pool->head->prev, &job,
job->prev))
;
/* worker checks if there is only an idle job in the job queue */
if (job == &thrd_pool->head->job) {
/* worker says it is idle */
atomic_store(&thrd_pool->state, idle);
thrd_yield();
continue;
}
job->future->result = (void *)job->func(job->future->arg);
atomic_flag_clear(&job->future->flag);
free(job);
} else {
/* worker is idle */
thrd_yield();
}
}
return EXIT_SUCCESS;
}
static bool tpool_init(tpool_t *thrd_pool, size_t size)
{
if (atomic_flag_test_and_set(&thrd_pool->initialized)) {
printf("This thread pool has already been initialized.\n");
return false;
}
assert(size > 0);
thrd_pool->pool = malloc(sizeof(thrd_t) * size);
if (!thrd_pool->pool) {
printf("Failed to allocate thread identifiers.\n");
/* release the claim, otherwise the pool can never be initialized */
atomic_flag_clear(&thrd_pool->initialized);
return false;
}
/* aligned_alloc, not malloc: the cache line padding in idle_job_t is only
* worth anything if the allocation starts on a cache line boundary.
*/
idle_job_t *idle_job =
aligned_alloc(_Alignof(idle_job_t), sizeof(idle_job_t));
if (!idle_job) {
printf("Failed to allocate idle job.\n");
free(thrd_pool->pool);
atomic_flag_clear(&thrd_pool->initialized);
return false;
}
/* idle_job will always be the first job */
idle_job->job.next = &idle_job->job;
idle_job->job.prev = &idle_job->job;
idle_job->prev = &idle_job->job;
thrd_pool->func = worker;
thrd_pool->head = idle_job;
thrd_pool->state = idle;
thrd_pool->size = size;
/* employer hires many workers */
for (size_t i = 0; i < size; i++) {
if (thrd_create(thrd_pool->pool + i, worker, thrd_pool) !=
thrd_success) {
printf("Failed to create worker %zu.\n", i);
/* lay off whoever was already hired before giving up */
atomic_store(&thrd_pool->state, cancelled);
while (i--)
thrd_join(thrd_pool->pool[i], NULL);
free(idle_job);
free(thrd_pool->pool);
/* init undoes itself completely, so there is nothing left for
* tpool_destroy to reclaim and the caller must not call it.
* Clear the fields anyway, so a later tpool_init has no stale
* pointer or count to trip over.
*/
thrd_pool->pool = NULL;
thrd_pool->head = NULL;
thrd_pool->size = 0;
atomic_flag_clear(&thrd_pool->initialized);
return false;
}
}
return true;
}
static void tpool_destroy(tpool_t *thrd_pool)
{
if (atomic_exchange(&thrd_pool->state, cancelled) == running)
printf("Thread pool cancelled with jobs still running.\n");
for (int i = 0; i < thrd_pool->size; i++)
thrd_join(thrd_pool->pool[i], NULL);
/* Workers are all joined, so the queue is ours alone now. Unclaimed jobs
* own a future that nobody will ever wait on; free both.
*/
while (thrd_pool->head->prev != &thrd_pool->head->job) {
job_t *job = thrd_pool->head->prev->prev;
tpool_future_destroy(thrd_pool->head->prev->future);
free(thrd_pool->head->prev);
thrd_pool->head->prev = job;
}
free(thrd_pool->head);
free(thrd_pool->pool);
atomic_fetch_and(&thrd_pool->state, 0);
atomic_flag_clear(&thrd_pool->initialized);
}
/* Use the Bailey–Borwein–Plouffe formula to approximate PI */
static void *bbp(void *arg)
{
int k = *(int *)arg;
double sum = (4.0 / (8 * k + 1)) - (2.0 / (8 * k + 4)) -
(1.0 / (8 * k + 5)) - (1.0 / (8 * k + 6));
double *product = malloc(sizeof(double));
if (!product)
return NULL;
*product = 1 / pow(16, k) * sum;
return (void *)product;
}
struct tpool_future *add_job(tpool_t *thrd_pool, void *(*func)(void *),
void *arg)
{
job_t *job = malloc(sizeof(job_t));
if (!job)
return NULL;
struct tpool_future *future = tpool_future_create(arg);
if (!future) {
free(job);
return NULL;
}
/* Workers pop from the back and free as they go, but nothing updates the
* front link on the way, so once the queue has drained head->job.next
* still names the last job freed. Drop it before linking, otherwise the
* writes below land in freed memory.
*/
bool was_empty = thrd_pool->head->prev == &thrd_pool->head->job;
if (was_empty)
thrd_pool->head->job.next = &thrd_pool->head->job;
job->func = func;
job->future = future;
job->next = thrd_pool->head->job.next;
job->prev = &thrd_pool->head->job;
thrd_pool->head->job.next->prev = job;
thrd_pool->head->job.next = job;
if (was_empty) {
thrd_pool->head->prev = job;
/* the previous job of the idle job is itself */
thrd_pool->head->job.prev = &thrd_pool->head->job;
}
return future;
}
static inline void wait_until(tpool_t *thrd_pool, int state)
{
while (atomic_load(&thrd_pool->state) != state)
thrd_yield();
}
int main(void)
{
int bbp_args[PRECISION];
struct tpool_future *futures[PRECISION];
double bbp_sum = 0;
tpool_t thrd_pool = { .initialized = ATOMIC_FLAG_INIT };
if (!tpool_init(&thrd_pool, N_THREADS)) {
printf("failed to init.\n");
return EXIT_FAILURE;
}
/* employer asks workers to work */
atomic_store(&thrd_pool.state, running);
/* employer waits ... until workers are idle */
wait_until(&thrd_pool, idle);
/* employer adds more jobs to the job queue */
for (int i = 0; i < PRECISION; i++) {
bbp_args[i] = i;
futures[i] = add_job(&thrd_pool, bbp, &bbp_args[i]);
if (!futures[i]) {
printf("Failed to add job %d.\n", i);
/* Jobs handed out before this point own a future each, and a
* worker that claims one frees the job but not the future. Let
* them drain so those futures can be reclaimed here.
*/
atomic_store(&thrd_pool.state, running);
for (int j = 0; j < i; j++) {
tpool_future_wait(futures[j]);
tpool_future_destroy(futures[j]);
}
/* the pool is drained, so let it say so */
wait_until(&thrd_pool, idle);
tpool_destroy(&thrd_pool);
return EXIT_FAILURE;
}
}
/* employer asks workers to work */
atomic_store(&thrd_pool.state, running);
/* employer waits for the result of the job */
bool complete = true;
for (int i = 0; i < PRECISION; i++) {
tpool_future_wait(futures[i]);
/* bbp returns NULL if it could not allocate its result */
if (futures[i]->result)
bbp_sum += *(double *)(futures[i]->result);
else {
printf("Job %d produced no result.\n", i);
complete = false;
}
tpool_future_destroy(futures[i]);
}
/* employer destroys the job queue and lays workers off. Wait for the
* workers to park first: tpool_destroy reports on a pool it cancels
* while running, and a completed future does not by itself mean the
* last worker has published idle.
*/
wait_until(&thrd_pool, idle);
tpool_destroy(&thrd_pool);
printf("PI calculated with %d terms: %.15f\n", PRECISION, bbp_sum);
return complete ? EXIT_SUCCESS : EXIT_FAILURE;
}
Stdout of the program is:
PI calculated with 100 terms: 3.141592653589793
Exchange
In function tpool_destroy, atomic_exchange(&thrd_pool->state, cancelled) reads the current state and replaces it with “cancelled”.
A warning message is printed if the pool is destroyed while workers are still “running”.
If the exchange is not performed atomically, we may initially get the state as “running”. Subsequently, a thread could set the state to “cancelled” after finishing the last one, resulting in a false warning.
Test and set
In this example, the scenario is as follows:
First, the main thread initially acquires a lock future->flag and then sets it true,
which is akin to creating a job and then transferring its ownership to the worker.
Subsequently, the main thread will be blocked until the worker clears the flag.
This indicates that the main thread will wait until the worker completes the job and returns ownership to the main thread, allowing the two threads to cooperate correctly.
Fetch and…
In the function tpool_destroy, atomic_fetch_and is utilized as a means to set the state to “idle”.
Yet, in this case, it is not necessary, as the pool needs to be reinitialized for further use regardless.
Its return value could be further utilized, for instance, to report the previous state and perform additional actions.
Compare and swap
Once threads are created in the thread pool as workers, they will continuously search for jobs to do.
Jobs are taken from the tail of the job queue.
To take a job without being taken by another worker halfway through, we need to atomically change the pointer to the last job.
Otherwise, the last job is under race.
The while loop in the function worker,
while (job != &thrd_pool->head->job &&
!atomic_compare_exchange_weak(&thrd_pool->head->prev, &job,
job->prev)) {
}
, keeps trying to claim the job atomically until it succeeds.
A failed compare-exchange writes the current value back into job,
so the guard is re-evaluated on every iteration:
another worker may have taken the last job in the meantime,
leaving the idle job, which must never be claimed.
Built-in post increment and decrement operators and compound assignment on atomic objects, such as ++ and +=, are read-modify-write atomic operations with total sequentially consistent ordering as well.
They behave equivalently to a do while loop. See C11 standard 6.5.2.4 and 6.5.16.2 for more details.
What if claiming a job, which updates thrd_pool->head->prev, is not done atomically?
Two or more threads could have races updating thrd_pool->head->prev and working on the same job.
Data races are undefined behavior in C11 and C++11.
Working on the same job can lead to duplication of the calculation of job->future->result,
use after free and double free on the job.
But even when jobs are claimed atomically, a thread can still end up holding a job that has been freed. This is a defect of the example code. Jobs in the example are dynamically allocated. They are freed after a worker finishes each job. However, this situation may lead to dangling pointers for workers that are still holding and attempting to claim the job. If jobs are intended to be dynamically allocated, then safe memory reclamation should be implemented for such shared objects. RCU, hazard pointers, and reference counting are major ways of solving this problem.
Further improvements
At the beginning of Read-modify-write, we described how a global total order is established by combining local order and inter-thread order imposed by atomic objects.
But should every object, including non-atomic ones, participate in a single global order established by atomic objects?
Sequential consistency solves the ordering problem in Enforcing law and order, but it may force too much ordering, as some normal operations may not require it.
By default, atomic operations in the C11 atomic library use memory_order_seq_cst as the default memory order. Operations with the _explicit suffix accept an additional argument to specify which memory order to use.
How to leverage memory orders to optimize performance will be covered later in Do we always need sequentially consistent operations?.
Shared Resources
From Read-modify-write, we have understood that there are two types of shared resources that need to be considered. The first type is shared resources that concurrent threads will access in order to collaborate to achieve a goal. The second type is shared resources that serve as a communication channel for concurrent threads, ensuring correct access to shared resources. However, all of these considerations stem from a programming perspective, where we only distinguish between shared resources and private resources.
Given all the complexities to consider, modern hardware adds another layer to the puzzle, as depicted in the figure. Remember, memory moves between the main RAM and the CPU in segments known as cache lines. These cache lines also represent the smallest unit of data transferred between cores and caches. When one core writes a value and another reads it, the entire cache line containing that value must be transferred from the first core’s cache(s) to the second core’s cache(s), ensuring a coherent “view” of memory across cores. This dynamic can significantly affect performance.
This slowdown is even more insidious when it occurs between unrelated variables that happen to be placed on the same shared resource, which is the cache line, as shown in the figure. When designing concurrent data structures or algorithms, this false sharing must be taken into account. One way to avoid it is to pad atomic variables with a cache line of private data, but this is obviously a large space-time trade-off.
Processor 1 and Processor 2 operate independently on variables A and B. Simultaneously, they read the cache line containing these two variables. In the next time step, each processor modifies A and B in their private L1 cache separately. Subsequently, both processors write their modified cache line to the shared L2 cache. At this moment, the expansion of the scope of shared resources to encompass cache lines highlights the importance of considering cache coherence issues.
Not only shared resources, but we also need to consider shared resources that serve as a communication channel, e.g. spinlock (see Test and set). Processors using locks as a communication channel also need to transfer the cache line. When a processor broadcasts the release of a lock, multiple processors on different chips attempt to acquire the lock simultaneously. To ensure a consistent state of the lock across all private L1 cache lines, which is a part of cache coherence, the cache line containing the lock will be continually transferred among the caches of those cores. Unless the critical sections are considerably lengthy, the time spent managing this cache line movement could exceed the time spent within the critical sections themselves,1 despite the algorithm’s non-blocking nature.
With these high communication costs, there may be only one processor that succeeds in acquiring it again in the case of mutex lock or spinlock, as shown in the figure. Then the other processors that have not successfully acquired the lock will continue to wait, resulting in little practical benefit (only one processor gains the lock) and significant communication overhead. This disparity severely limits the scalability of the spin lock.
Three processors use a lock as a communication channel to ensure correct access to the shared L2 cache. Processors 2 and 3 are trying to acquire a lock that is held by processor 1. Therefore, when processor 1 unlocks, the state of the lock needs to be updated in the other processors’ private L1 caches.
-
This situation underlines how some systems may experience a cache miss that is substantially more costly than an atomic RMW operation, as discussed in Paul E. McKenney’s talk from CppCon 2017 for a deeper exploration. ↩
Concurrency tools and synchronization mechanisms
Atomic loads, stores, and RMW operations are the building blocks for every single concurrency tool. It is useful to split those tools into two camps: blocking and lockless.
As mentioned in Read-modify-write, multiple threads can use these blocking tools to communicate with others. Furthermore, these blocking tools can even assist in synchronization between threads. The blocking mechanism is quite simple, because all threads need to do is block others in order to make their own progress. However, this simplicity can also cause threads to pause for unpredictable durations and then influence the progress of the overall system.
Take a mutex as an example: it requires threads to access shared data sequentially. If a thread locks the mutex and another attempts to lock it too, the second thread must wait, or block, until the first one unlocks it, regardless of the wait time. Additionally, blocking mechanisms are prone to deadlock and livelock, issues that lead to the system becoming immobilized as threads perpetually wait on each other.
If the first thread acquires a mutex first, then the second thread locks another mutex and subsequently attempts to lock the mutex held by the first thread. At the same time, the first thread also tries to lock the mutex held by the second thread. Then the deadlock occurs. Therefore, we can see that deadlock occurs when different threads acquire locks in incompatible orders, leading to system immobilization as threads perpetually wait on each other.
Additionally, in Shared Resources, we can see another problem with the lock: its scalability is limited.
After understanding the issue that blocking mechanisms are prone to, we try to achieve synchronization between threads without lock. Consider the program below: if there is only a single thread, execute these operations as follows:
while (x == 0)
x = 1 - x;
When executed by a single thread, these operations complete within a finite time.
However, with two threads executing concurrently,
if one thread executes x = 1 - x and the other thread executes x = 1 - x subsequently,
then the value of x will always be 0, which will lead to a livelock.
Therefore, even without any locks in concurrent threads,
we still cannot guarantee that the overall system can make progress toward achieving the programmer’s goals.
Consequently, we should not focus on comparing which communication tools or synchronization mechanisms are better, but rather on exploring how to effectively use these tools in a given scenario to facilitate smooth communication between threads and achieve the programmer’s goals.
Lock-free
In Concurrency tools and synchronization mechanisms, we explored different mechanisms based on the characteristics of concurrency tools, as described in Atomicity and Read-modify-write. In this section, we need to explore which strategies can help programmers to design a concurrency program that allows concurrent threads to collectively ensure progress in the overall system while also improving scalability, which is the initial goal of designing a concurrency program. First of all, we must figure out the scope of our problem. Understanding the relationship between the progress of each thread and the progress of the entire system is necessary.
Type of progress
When we consider the scenario where many concurrent threads collaborate and each thread is divided into many operations,
Wait-Free Every operation in every thread will be completed within a limited time. This also implies that each operation contributes to the overall progress of the system.
Lock-Free At any given moment, among all operations in every thread, at least one operation contributes to the overall progress of the system. However, it does not guarantee that starvation will not occur.
Obstruction-Free At any given time, if there is only a single thread operating without interference from other threads, its instructions can be completed within a finite time. However, when threads are working concurrently, it does not guarantee progress.
Therefore, we can understand their three relationships as follows: obstruction-free includes lock-free and lock-free includes wait-free. Achieving wait-free is the most optimal approach, allowing each thread to make progress without being blocked by other threads.
In a wait-free system, each thread is guaranteed to make progress at every moment because no thread can block others. This ensures that the overall system can always make progress. In a lock-free system, at Time 1, Thread 1 may cause other threads to wait while it performs its operation. However, even if Thread 1 suspends at Time 2, it does not subsequently block other threads. This allows Thread 2 to make progress at Time 3, ensuring that the overall system continues to make progress even if one thread is suspended. In an obstruction-free system, when Thread 1 is suspended at Time 2, it causes other threads to be blocked as a result. This means that by Time 3, Thread 2 and Thread 3 are still waiting, preventing the system from making progress thereafter. Therefore, obstruction-free systems may halt progress if one thread is suspended, leading to the potential blocking of other threads and even stalling the system.
The main goal is that the whole system, which contains all concurrent threads, is always making forward progress. To achieve this goal, we rely on concurrency tools, including atomic operations and operations that behave atomically, as described in Read-modify-write. Additionally, we carefully select synchronization mechanisms, as described in Concurrency tools and synchronization mechanisms, which may involve utilizing shared resources for communication (e.g., spinlock), as described in Shared Resources. Furthermore, we design our program with appropriate data structures and algorithms. Therefore, lock-free doesn’t mean we cannot use any lock; we just need to ensure that the blocking mechanism will not limit the scalability and that the system can avoid the problems described in Concurrency tools and synchronization mechanisms (e.g., long waits, deadlock).
Next, we take the single producer and multiple consumers problem as an example to demonstrate how to achieve fully lock-free programming by improving some implementations step by step.1 This problem is that one producer generates tasks and adds them to a job queue, and multiple consumers take tasks from the job queue and execute them.
-
The first three solutions, which are SPMC solution - lock-based, SPMC solution - lock-based and lock-free, and SPMC solution - fully lock-free, are based on Herb Sutter’s talk from CppCon 2014. ↩
SPMC solution - lock-based
First, we introduce the scenario of lock-based algorithms. At any time, there is only one consumer that can get the lock to access the job queue. This is because in this scenario, the lock is a mutex lock, also known as a mutual-exclusion lock. Until the consumer releases the lock, the other consumers are blocked when attempting to access the job queue.
The following text explains the meaning of each state in the figure.
state 1 : The producer is adding tasks to the job queue while multiple consumers wait for tasks to become available and are ready to take on any job that appears in the job queue.
state 2 \(\to\) state 3 : After the producer adds a task to the job queue, the producer releases the mutex lock, and then wakes up the consumers. Those consumers had previously tried to acquire the job queue lock.
state 3 \(\to\) state 4 : Consumer 1 acquires the mutex lock for the job queue, retrieves a task from it, and then releases the mutex lock.
state 5 : Next, other consumers attempt to acquire the mutex lock for the job queue. However, after they acquire the lock, they find no tasks in the queue. This is because the producer has not added more tasks to the job queue.
state 6 : Consequently, the consumers wait on a condition variable. During this time, the consumers are not busy waiting but rather waiting for the producer to wake them up. This is because the mechanism is an advanced form of a mutex lock.
The interaction between the producer and consumer in SPMC Solution 1, including their state transitions.
The reason why this implementation is not lock-free is: First, if a producer suspends, it causes consumers to have no job available, leading them to block and thus halting progress in the entire system, which is obstruction-free, as shown in the figure. Second, consumers need to concurrently access a shared resource: the job. Then, one consumer acquires the lock of the job queue but suddenly gets suspended before completing without unlocking, causing other consumers to be blocked. Meanwhile, the producer still keeps adding jobs, but the system fails to make any progress, which is obstruction-free, as shown in the figure. Therefore, neither the former nor the latter implementation approach is lock-free.
SPMC solution - lock-based and lock-free
As described in SPMC solution - lock-based, there is a problem when the producer suspends; the whole system cannot make any progress. Additionally, consumers contend for the lock of the job queue to access the job; however, after they acquire the lock, they may still need to wait when the queue is empty. To solve this issue, this section introduces lock-based and lock-free algorithms.
The following text explains the meaning of each state in the figure.
state 0 : The producer prepares all the jobs in advance.
state 1 : Consumer 1 acquires the lock on the job queue, takes a job, and releases the lock.
state 2 : After consumer 2 acquires the lock, it definitely can find that there are still jobs in the queue.
Through this approach, once a consumer obtains the lock on the job queue, there is guaranteed to be a job available unless all jobs have been taken by other consumers. Thus, there is no need to wait due to a lack of jobs; the only wait is for acquiring the lock to access the job queue.
The interaction between the producer and consumer in Solution 2, including their state transitions.
This implementation is referred to as both lock-based and lock-free. The algorithm is designed such that the producer adds all jobs to the job queue before multiple consumers begin taking them. This design ensures that if the producer suspends or adds jobs slowly, consumers will not be blocked due to the lack of a job. Consumers simply think they have completed all the jobs that the producer added. Therefore, this implementation qualifies as lock-free, as shown in the figure. The reason that the implementation of getting a job is lock-based, not lock-free, is the same as the second reason described in SPMC solution - lock-based.
SPMC solution - fully lock-free
As described in Shared Resources, we can understand that communications between processors across a chip are through cache lines, which incurs high costs. Additionally, using locks further decreases overall performance and limits scalability. However, when locks are necessary for concurrent threads to communicate, reducing the amount of shared state and the granularity of the shared resource used for communication (e.g., spinlock, mutex lock) is crucial. Therefore, to achieve fully lock-free programming, we change the data structure to reduce the granularity of locks.
The left side shows that the lock protects the entire job queue to ensure exclusive access to its head for multiple threads. The right side illustrates that each thread has its own slot for accessing jobs, not only achieving exclusivity through data structure but also eliminating the need for shared resources for communication.
Providing each consumer with their own unique slot to access jobs addresses the problem at its root, directly avoiding competition. By doing so, consumers no longer rely on a shared resource for communication. Consequently, other consumers will not be blocked by a suspended consumer holding a lock. This approach ensures that the system maintains its progress, as each consumer operates independently within their own slot, which is lock-free, as shown in the figure.
SPMC solution - fully lock-free with CAS
In addition to reducing granularity, there is another way to avoid the situation where one consumer acquires the lock on the job queue, gets suspended, and blocks other consumers, as described in SPMC solution - lock-based and lock-free. As described in Compare and swap, we can use CAS with a loop to ensure that the write operation achieves semantic atomicity.
Unlike SPMC solution - lock-based and lock-free, which uses a shared resource (e.g., an advanced form of a mutex lock) for blocking synchronization, the first thread holding the lock causes the other threads to wait until the first thread releases the lock. As described in Compare and swap, CAS allows threads that initially failed to acquire the lock to continue to execute Read and Modify. Therefore, we can conclude that if one thread is blocked, it indicates that another thread is making progress, which is lock-free, as shown in the figure.
As described in SPMC solution - lock-based and lock-free, a blocking mechanism uses a mutex lock; we can see that only one thread is active when it accesses the job queue. Although CAS will continue to execute Read and Modify, it doesn’t result in an increase in overall progress. This is because the operations will be useless when atomic CAS fails. Therefore, we can understand that lock-free algorithms are not faster than blocking ones. The reason for using lock-free is to ensure that if one thread is blocked, it doesn’t cause other threads to be blocked, thereby ensuring that the overall system must make progress over a long period of time.
Conclusion on lock-free programming
To conclude this section on lock-free programming, we can see that both blocking and lockless approaches have their place in software development. They serve different purposes with their own design philosophies. When performance is a key consideration, it is crucial to profile your application, take advantage of every concurrency tool or mechanism, and accompany them with appropriate data structures and algorithms. The performance impact varies with numerous factors, such as thread count and CPU architecture specifics. Balancing complexity and performance is essential in concurrency, a domain fraught with challenges.
ABA problem
CAS has been introduced as one of the read-modify-write operations. However, the target object not changing does not necessarily mean that no other threads modified it halfway through. If the target object is changed by another thread and then changed back, the result of comparison would still be equal. In this case, the target object has indeed been modified, yet the operation appears unchanged, compromising its atomicity. We call this ABA problem. Consider the following scenario,
#include <stdatomic.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <threads.h>
atomic_int v = 42;
/* handshake flags: they pin the interleaving down instead of leaving it to
* the scheduler, as sleeping would.
*/
atomic_bool a_has_read = false, b_done = false;
int threadA(void *args)
{
(void)args;
int va = atomic_load(&v);
printf("A: v = %d\n", va);
atomic_store(&a_has_read, true);
/* wait for B; a real program would be preempted here instead */
while (!atomic_load(&b_done))
thrd_yield();
/* v was changed and changed back, so the comparison succeeds and A never
* learns that v changed at all.
*/
if (!atomic_compare_exchange_strong(&v, &va, va + 10)) {
printf("A: CAS failed, v = %d\n", atomic_load(&v));
return 1;
}
printf("A: v = %d\n", atomic_load(&v));
return 0;
}
int threadB(void *args)
{
(void)args;
while (!atomic_load(&a_has_read))
thrd_yield();
atomic_fetch_add(&v, 5);
printf("B: v = %d\n", atomic_load(&v));
atomic_fetch_sub(&v, 5);
printf("B: v = %d\n", atomic_load(&v));
atomic_store(&b_done, true);
return 0;
}
int main(void)
{
thrd_t A, B;
/* Each thread spins on a flag only the other one sets, so an unchecked
* thrd_create failure would leave the survivor spinning forever.
*/
if (thrd_create(&A, threadA, NULL) != thrd_success) {
printf("failed to create thread A.\n");
return EXIT_FAILURE;
}
if (thrd_create(&B, threadB, NULL) != thrd_success) {
printf("failed to create thread B.\n");
atomic_store(&b_done, true); /* release A, then reap it */
thrd_join(A, NULL);
return EXIT_FAILURE;
}
int result_a = 0;
thrd_join(A, &result_a);
thrd_join(B, NULL);
return result_a ? EXIT_FAILURE : EXIT_SUCCESS;
}
The execution result would be:
A: v = 42
B: v = 47
B: v = 42
A: v = 52
In the example provided, the ABA problem causes thread A to be unaware that variable v has been altered.
Since the comparison result indicates that v is unchanged, v + 10 is swapped in.
The two flags pin the interleaving down rather than leaving it to the scheduler:
a_has_read holds thread B back until A has loaded v,
since B finishing first would leave nothing for A to be misled about,
and b_done holds A back until B has changed v and changed it back.
In a real-world scenario, instead of this handshake, thread A could be paused by a context switch to another task, including preemption by a higher-priority task.
This example seems harmless, but things can get nasty when atomic RMW operations are used in more complex data structures.
In a broader context, the ABA problem occurs when changes occur between loading and comparing, but the comparing mechanism is unable to identify that the state of the target object is not the latest, yielding a false positive result.
Returning to the thread pool example in Read-modify-write, it contains the ABA problem as well.
In the worker function, we have a thread trying to claim the job.
job_t *job = atomic_load(&thrd_pool->head->prev);
...
while (job != &thrd_pool->head->job &&
!atomic_compare_exchange_weak(&thrd_pool->head->prev, &job,
job->prev))
;
Consider the following scenario:
- There is only one job left.
- Thread A loads the pointer to the job by
atomic_load(). - Thread A is preempted.
- Thread B claims the job and successfully updates
thrd_pool->head->prev. - Thread B sets the thread pool state to idle.
- The main thread finishes waiting and adds more jobs.
- The memory allocator reuses the recently freed memory for new jobs.
- Fortunately, the first added job has the same address as the one thread A held.
- Thread A is back in running state. The comparison result is equal so it updates
thrd_pool->head->prevwith the oldjob->prev, which is already a dangling pointer. - Another thread loads the dangling pointer from
thrd_pool->head->prev.
Notice that even though job->prev is not loaded explicitly before the comparison, the compiler could place loading instructions before the comparison.
In the end, the dangling pointer could either point to garbage or trigger a segmentation fault.
It could be even worse if a nested ABA problem occurs in thread B.
Also, using a memory pool could make allocating a job at the same address more likely, creating more opportunities for the ABA problem to occur.
In fact, pre-allocated memory should be used to achieve lock-free behavior since malloc could involve a mutex in a multi-threaded environment.
Being unable to determine whether the target object has been changed through comparison could result in a false positive when the return value of CAS is true. Thus, the atomicity provided by CAS is not guaranteed. The general concept of solving this problem involves adding more information to make different states distinguishable, and then deciding whether to act on the old state or retry with the new state. If acting on the old state is chosen, then safe memory reclamation should be considered as memory may have already been freed by other threads. More aggressively, one might consider a programming paradigm where each operation on the target object has no side effects that modify it. In a later section, we will introduce a different way of implementing atomic RMW operations using LL/SC instructions. The exclusive status provided by LL/SC instructions avoids the pitfall introduced by comparison.
To make different states distinguishable, a common solution is to increment a version number each time the target object is changed.
Bundling the target object and version into a comparison ensures that each change marks a distinguishable result.
Given a sufficiently large version number, there should be no repeated version numbers.
There are multiple methods for storing the version number, depending on the evaluation of the duration before a version number wraps around.
In the thread pool example, the target object is a pointer. The unused bits in a pointer can be utilized to store the version number.
In addition to embedding the version number into a pointer, we could consider utilizing an additional 32-bit or 64-bit value next to the target object for the version number.
This requires the compare-and-swap instruction to be capable of comparing a wider size at once.
Sometimes, this is referred to as double-width compare-and-swap.
On x86-64 processors, atomic instructions that load or store more than one CPU word require additional hardware support.
You can use grep cx16 /proc/cpuinfo to check if the processor supports 16-byte compare-and-swap.
For hardware that does not support the desired size, software implementations that may involve locks are used instead, as mentioned in Arbitrarily-sized “atomic” types.
Returning to the example, the ABA problem in the following code is fixed by using a version number that increments each time a job is added to the empty queue. On x86-64, add the compiler flag -mcx16 to enable 16-byte compare-and-swap in the worker function.1
#include <stdio.h>
#include <stdatomic.h>
#include <threads.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <math.h>
#define PRECISION 100 /* upper bound in BPP sum */
#define CACHE_LINE_SIZE 64
#define N_THREADS 64
struct tpool_future {
void *result;
void *arg;
atomic_flag flag;
};
typedef struct job {
void *(*func)(void *);
struct tpool_future *future;
struct job *next, *prev;
} job_t;
typedef struct idle_job {
/* Padding alone only sizes the struct; the alignment is what keeps the
* union off a cache line shared with anything else, and it is also what
* guarantees the 16-byte alignment a double-width CAS requires. It needs
* an allocation aligned to match: see tpool_init.
*/
_Alignas(CACHE_LINE_SIZE) union {
struct {
_Atomic(job_t *) prev;
unsigned long long version;
};
_Atomic struct versioned_prev {
job_t *ptr;
unsigned long long _version;
} v_prev;
};
char padding[CACHE_LINE_SIZE - sizeof(_Atomic(job_t *)) -
sizeof(unsigned long long)]; /* avoid false sharing */
job_t job;
} idle_job_t;
enum state { idle, running, cancelled };
typedef struct tpool {
atomic_flag initialized;
int size;
thrd_t *pool;
atomic_int state;
thrd_start_t func;
idle_job_t *head; /* job queue is a SPMC ring buffer */
} tpool_t;
static struct tpool_future *tpool_future_create(void *arg)
{
struct tpool_future *future = malloc(sizeof(struct tpool_future));
if (future) {
future->result = NULL;
future->arg = arg;
atomic_flag_clear(&future->flag);
atomic_flag_test_and_set(&future->flag);
}
return future;
}
void tpool_future_wait(struct tpool_future *future)
{
while (atomic_flag_test_and_set(&future->flag))
;
}
void tpool_future_destroy(struct tpool_future *future)
{
free(future->result);
free(future);
}
static int worker(void *args)
{
if (!args)
return EXIT_FAILURE;
tpool_t *thrd_pool = (tpool_t *)args;
while (1) {
/* worker is laid off */
if (atomic_load(&thrd_pool->state) == cancelled)
return EXIT_SUCCESS;
if (atomic_load(&thrd_pool->state) == running) {
/* worker takes the job */
struct versioned_prev job = atomic_load(&thrd_pool->head->v_prev);
/* A failed compare-exchange reloads "job", so the idle job has to
* be ruled out on every iteration, not just once up front.
*/
while (job.ptr != &thrd_pool->head->job) {
/* compare 16 byte at once */
struct versioned_prev next = { .ptr = job.ptr->prev,
._version = job._version };
if (atomic_compare_exchange_weak(&thrd_pool->head->v_prev, &job,
next))
break;
}
/* worker checks if there is only an idle job in the job queue */
if (job.ptr == &thrd_pool->head->job) {
/* worker says it is idle */
atomic_store(&thrd_pool->state, idle);
thrd_yield();
continue;
}
job.ptr->future->result =
(void *)job.ptr->func(job.ptr->future->arg);
atomic_flag_clear(&job.ptr->future->flag);
free(job.ptr);
} else {
/* worker is idle */
thrd_yield();
}
}
return EXIT_SUCCESS;
}
static bool tpool_init(tpool_t *thrd_pool, size_t size)
{
if (atomic_flag_test_and_set(&thrd_pool->initialized)) {
printf("This thread pool has already been initialized.\n");
return false;
}
assert(size > 0);
thrd_pool->pool = malloc(sizeof(thrd_t) * size);
if (!thrd_pool->pool) {
printf("Failed to allocate thread identifiers.\n");
/* release the claim, otherwise the pool can never be initialized */
atomic_flag_clear(&thrd_pool->initialized);
return false;
}
/* aligned_alloc, not malloc: the double-width CAS on v_prev needs the
* union 16-byte aligned, and the cache line padding is only worth
* anything if the allocation starts on a cache line boundary.
*/
idle_job_t *idle_job =
aligned_alloc(_Alignof(idle_job_t), sizeof(idle_job_t));
if (!idle_job) {
printf("Failed to allocate idle job.\n");
free(thrd_pool->pool);
atomic_flag_clear(&thrd_pool->initialized);
return false;
}
/* idle_job will always be the first job */
idle_job->job.next = &idle_job->job;
idle_job->job.prev = &idle_job->job;
idle_job->prev = &idle_job->job;
idle_job->version = 0ULL;
thrd_pool->func = worker;
thrd_pool->head = idle_job;
thrd_pool->state = idle;
thrd_pool->size = size;
/* employer hires many workers */
for (size_t i = 0; i < size; i++) {
if (thrd_create(thrd_pool->pool + i, worker, thrd_pool) !=
thrd_success) {
printf("Failed to create worker %zu.\n", i);
/* lay off whoever was already hired before giving up */
atomic_store(&thrd_pool->state, cancelled);
while (i--)
thrd_join(thrd_pool->pool[i], NULL);
free(idle_job);
free(thrd_pool->pool);
/* init undoes itself completely, so there is nothing left for
* tpool_destroy to reclaim and the caller must not call it.
* Clear the fields anyway, so a later tpool_init has no stale
* pointer or count to trip over.
*/
thrd_pool->pool = NULL;
thrd_pool->head = NULL;
thrd_pool->size = 0;
atomic_flag_clear(&thrd_pool->initialized);
return false;
}
}
return true;
}
static void tpool_destroy(tpool_t *thrd_pool)
{
if (atomic_exchange(&thrd_pool->state, cancelled) == running)
printf("Thread pool cancelled with jobs still running.\n");
for (int i = 0; i < thrd_pool->size; i++)
thrd_join(thrd_pool->pool[i], NULL);
/* Workers are all joined, so the queue is ours alone now. Unclaimed jobs
* own a future that nobody will ever wait on; free both.
*/
while (thrd_pool->head->prev != &thrd_pool->head->job) {
job_t *job = thrd_pool->head->prev->prev;
tpool_future_destroy(thrd_pool->head->prev->future);
free(thrd_pool->head->prev);
thrd_pool->head->prev = job;
}
free(thrd_pool->head);
free(thrd_pool->pool);
atomic_fetch_and(&thrd_pool->state, 0);
atomic_flag_clear(&thrd_pool->initialized);
}
/* Use the Bailey–Borwein–Plouffe formula to approximate PI */
static void *bbp(void *arg)
{
int k = *(int *)arg;
double sum = (4.0 / (8 * k + 1)) - (2.0 / (8 * k + 4)) -
(1.0 / (8 * k + 5)) - (1.0 / (8 * k + 6));
double *product = malloc(sizeof(double));
if (!product)
return NULL;
*product = 1 / pow(16, k) * sum;
return (void *)product;
}
struct tpool_future *add_job(tpool_t *thrd_pool, void *(*func)(void *),
void *arg)
{
job_t *job = malloc(sizeof(job_t));
if (!job)
return NULL;
struct tpool_future *future = tpool_future_create(arg);
if (!future) {
free(job);
return NULL;
}
/* Workers pop from the back and free as they go, but nothing updates the
* front link on the way, so once the queue has drained head->job.next
* still names the last job freed. Drop it before linking, otherwise the
* writes below land in freed memory.
*/
struct versioned_prev cur = atomic_load(&thrd_pool->head->v_prev);
bool was_empty = cur.ptr == &thrd_pool->head->job;
if (was_empty)
thrd_pool->head->job.next = &thrd_pool->head->job;
job->func = func;
job->future = future;
job->next = thrd_pool->head->job.next;
job->prev = &thrd_pool->head->job;
thrd_pool->head->job.next->prev = job;
thrd_pool->head->job.next = job;
if (was_empty) {
/* Publish the pointer and its version in one 16-byte store. Writing
* the two halves separately would let a worker observe the new job
* paired with the old version, which is precisely the window the
* version number exists to close. This store is unsynchronized: it
* relies on the employer only adding jobs while the pool is idle,
* which a worker preempted just after its own state check does not
* honor. That window is the same one the ABA discussion describes.
*/
struct versioned_prev next = { .ptr = job,
._version = cur._version + 1 };
atomic_store(&thrd_pool->head->v_prev, next);
/* the previous job of the idle job is itself */
thrd_pool->head->job.prev = &thrd_pool->head->job;
}
return future;
}
static inline void wait_until(tpool_t *thrd_pool, int state)
{
while (atomic_load(&thrd_pool->state) != state)
thrd_yield();
}
int main(void)
{
int bbp_args[PRECISION];
struct tpool_future *futures[PRECISION];
double bbp_sum = 0;
tpool_t thrd_pool = { .initialized = ATOMIC_FLAG_INIT };
if (!tpool_init(&thrd_pool, N_THREADS)) {
printf("failed to init.\n");
return EXIT_FAILURE;
}
/* employer asks workers to work */
atomic_store(&thrd_pool.state, running);
/* employer waits ... until workers are idle */
wait_until(&thrd_pool, idle);
/* employer adds more jobs to the job queue */
for (int i = 0; i < PRECISION; i++) {
bbp_args[i] = i;
futures[i] = add_job(&thrd_pool, bbp, &bbp_args[i]);
if (!futures[i]) {
printf("Failed to add job %d.\n", i);
/* Jobs handed out before this point own a future each, and a
* worker that claims one frees the job but not the future. Let
* them drain so those futures can be reclaimed here.
*/
atomic_store(&thrd_pool.state, running);
for (int j = 0; j < i; j++) {
tpool_future_wait(futures[j]);
tpool_future_destroy(futures[j]);
}
/* the pool is drained, so let it say so */
wait_until(&thrd_pool, idle);
tpool_destroy(&thrd_pool);
return EXIT_FAILURE;
}
}
/* employer asks workers to work */
atomic_store(&thrd_pool.state, running);
/* employer waits for the result of the job */
bool complete = true;
for (int i = 0; i < PRECISION; i++) {
tpool_future_wait(futures[i]);
/* bbp returns NULL if it could not allocate its result */
if (futures[i]->result)
bbp_sum += *(double *)(futures[i]->result);
else {
printf("Job %d produced no result.\n", i);
complete = false;
}
tpool_future_destroy(futures[i]);
}
/* employer destroys the job queue and lays workers off. Wait for the
* workers to park first: tpool_destroy reports on a pool it cancels
* while running, and a completed future does not by itself mean the
* last worker has published idle.
*/
wait_until(&thrd_pool, idle);
tpool_destroy(&thrd_pool);
printf("PI calculated with %d terms: %.15f\n", PRECISION, bbp_sum);
return complete ? EXIT_SUCCESS : EXIT_FAILURE;
}
Notice that, in the struct idle_job, a union is used for type punning, which bundles the pointer and version number for compare-and-swap.
Directly casting a job pointer to a pointer that points to a 16-byte object is undefined behavior (due to having different alignment); type punning is used instead.
By using this technique, struct idle_job can still be accessed normally in other places, minimizing code modification.
Compiler optimizations are conservative on type punning, but it is acceptable for atomic operations.
See Atomic fusion.
Another way to prevent the ABA problem in the example is to use safe memory reclamation mechanisms.
Unlike the previously mentioned approach of acting on the old state, the address of a job is not freed until no thread is using it.
This prevents the memory allocator or memory pool from reusing the address and causing problems.
-
When using
-mcx16, programs relying on 16-byte atomic operations (e.g., using__int128) may require linking with-latomic, as these operations are implemented via function calls tolibatomicon some systems. See https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104688. ↩
Sequential consistency on weakly-ordered hardware
Different hardware architectures offer distinct memory models. For instance, x64 architecture1 is known to be strongly-ordered, generally ensuring a global sequence for loads and stores in most scenarios. Conversely, architectures like ARM are considered weakly-ordered, meaning one should not expect loads and stores to follow the program sequence without explicit instructions to the CPU. These instructions, known as memory barriers, are essential to prevent the reordering of these operations.
It is helpful to see how atomic operations work in a weakly-ordered system,
both to understand what’s happening in hardware,
and to see why the C and C++ concurrency models were designed as they were.2
Let’s examine ARM, since it is both popular and straightforward.
Consider the simplest atomic operations: loads and stores.
Given some atomic_int foo,
int getFoo()
{
return foo;
}
\[\text{ } \xrightarrow{\textit{becomes}} \text{ }\]
getFoo:
ldr r3, <&foo>
dmb
ldr r0, [r3, #0]
dmb
bx lr
void setFoo(int i)
{
foo = i;
}
\[\text{ } \xrightarrow{\textit{becomes}} \text{ }\]
setFoo:
ldr r3, <&foo>
dmb
str r0, [r3, #0]
dmb
bx lr
We load the address of our atomic variable into a scratch register (r3),
place our load or store operation between memory barriers (dmb), and then proceed.
These barriers ensure sequential consistency:
the first barrier guarantees that previous reads and writes are not reordered to follow our operation,
and the second ensures that future reads and writes are not reordered to precede it.
-
Also known as x86-64, x64 is a 64-bit extension of the x86 instruction set, officially unveiled in 1999. This extension heralded the introduction of two novel operation modes: 64-bit mode for leveraging the full potential of 64-bit processing and compatibility mode for maintaining support for 32-bit applications. Initially developed by AMD and publicly released in 2000, the x64 architecture has since been adopted by Intel and VIA, signaling a unified industry shift towards 64-bit computing. This wide adoption marked the effective obsolescence of the Intel Itanium architecture (IA-64), despite its initial design to supersede the x86 architecture. ↩
-
It is worth noting that the concepts we discuss here are not specific to C and C++. Other systems programming languages like D and Rust have converged on similar models. ↩
Implementing atomic read-modify-write operations with LL/SC instructions
Like many RISC1 architectures, ARM does not have dedicated RMW instructions. Given that the processor may switch contexts to another thread at any moment, constructing RMW operations from standard loads and stores is not feasible. Special instructions are required instead: load-link and store-conditional (LL/SC). These instructions are complementary: load-link performs a read operation from an address, similar to any load, but it also signals the processor to watch that address. Store-conditional executes a write operation only if no other writes have occurred at that address since its paired load-link. This mechanism is illustrated through an atomic fetch and add example.
On ARM,
void incFoo() { ++foo; }
compiles to:
incFoo:
ldr r3, <&foo>
dmb
loop:
ldrex r2, [r3] // LL foo
adds r2, r2, #1 // Increment
strex r1, r2, [r3] // SC
cmp r1, #0 // Check the SC result.
bne loop // Loop if the SC failed.
dmb
bx lr
We LL the current value, add one, and immediately try to store it back with a SC.
If that fails, another thread may have written to foo since our LL, so we try again.
In this way, at least one thread is always making forward progress in atomically modifying foo,
even if several are attempting to do so at once.2
-
Reduced instruction set computer, in contrast to a complex instruction set computer (CISC) architecture like x64. ↩
-
…though generally, we want to avoid cases where multiple threads are vying for the same variable for any significant amount of time. ↩
Spurious LL/SC failures
It is impractical for CPU hardware to track load-linked addresses for each byte within a system due to the immense resource requirements. To mitigate this, many processors monitor these operations at a broader scale, like the cache line level. Consequently, a SC operation may fail if any part of the monitored block is written to, not just the specific address that was load-linked.
This limitation poses a particular challenge for operations like compare and swap,
highlighting the essential purpose of compare_exchange_weak.
Consider, for example, the task of atomically multiplying a value without an architecture-specific atomic read-multiply-write instruction.
void atomicMultiply(int by)
{
int expected = foo;
// Which CAS should we use?
while (!foo.compare_exchange_?(expected, expected * by)) {
// Empty loop.
// (On failure, expected is updated with foo's most recent value.)
}
}
Many lockless algorithms use CAS loops like this to atomically update a variable when calculating its new value is not atomic. They:
- Read the variable.
- Perform some (non-atomic) operation on its value.
- CAS the new value with the previous one.
- If the CAS failed, another thread beat us to the punch, so try again.
If we use compare_exchange_strong for this family of algorithms,
the compiler must emit nested loops:
an inner one to protect us from spurious SC failures,
and an outer one which repeatedly performs our operation until no other thread has interrupted us.
But unlike the _strong version,
a weak CAS is allowed to fail spuriously, just like the LL/SC mechanism that implements it.
So, with compare_exchange_weak,
the compiler is free to generate a single loop,
since we do not care about the difference between retries from spurious SC failures and retries caused by another thread modifying our variable.
Do we always need sequentially consistent operations?
All of our examples so far have been sequentially consistent to prevent reorderings that break our code. We have also seen how weakly-ordered architectures like ARM use memory barriers to create sequential consistency. But as you might expect, these barriers can have a noticeable impact on performance. After all, they inhibit optimizations that your compiler and hardware would otherwise make.
What if we could avoid some of this slowdown?
Consider a simple case like the spinlock from Test and set.
Between the lock() and unlock() calls,
we have a critical section where we can safely modify shared state protected by the lock.
Outside this critical section,
we only read and write to things that are not shared with other threads.
deepThought.calculate(); // non-shared
lock(); // Lock; critical section begins
sharedState.subject = "Life, the universe and everything";
sharedState.answer = 42;
unlock(); // Unlock; critical section ends
demolishEarth(vogons); // non-shared
It is vital that reads and writes to shared memory do not move outside the critical section. But the opposite is not true! The compiler and hardware could move as much as they want into the critical section without causing any trouble. We have no problem with the following if it is somehow faster:
lock(); // Lock; critical section begins
deepThought.calculate(); // non-shared
sharedState.subject = "Life, the universe and everything";
sharedState.answer = 42;
demolishEarth(vogons); // non-shared
unlock(); // Unlock; critical section ends
So, how do we tell the compiler as much?
Memory orderings
Memory consistency models
Modern concurrent programs execute atop at least two layers that freely reorder memory operations: optimizing compilers transform the source program, and modern microprocessors retire loads and stores through pipelines, caches, speculation, and store buffers. The program therefore does not have to run in the exact order in which it was written. Instead, the system is allowed to change the sequence of operations so long as the observable result remains within an agreed set of valid outcomes. This agreement between the programmer, the compiler, and the hardware is called a memory consistency model.
Memory consistency models operate at several levels. For example, a compiler may rearrange instructions while lowering C++ source into assembly, and the processor may further reorder the resulting machine instructions while they execute. The exact implementation details differ from one layer to another, but each layer must still preserve the outcomes promised by its memory model.
Sequential consistency (SC)
In the 1970s, Leslie Lamport proposed the most widely cited memory consistency model, sequential consistency (SC), defined as follows:
A multiprocessor system is sequentially consistent if the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.
Sequential consistency is easy to reason about because every execution appears to be some interleaving of each thread’s program order. That simplicity comes at a cost: modern hardware and optimizing compilers must give up profitable reorderings in order to preserve the illusion.
A memory consistency model is a semantic contract, not a prescribed implementation. The machine may execute instructions in a very different order from the source text, provided the final result still matches one of the outcomes allowed by the model. Sequential consistency therefore does not imply a single execution order or a single result. It only requires that the execution appear equivalent to some legal interleaving of the participating threads.
To make that concrete, consider the following message-passing litmus test.
Two threads write to and read from two shared variables x and y, both initially set to 0.
// Litmus Test: Message Passing
int x = 0;
int y = 0;
// Thread 1 // Thread 2
x = 1; r1 = y;
y = 1; r2 = x;
If this program is sequentially consistent, then in the global interleaving Thread 1’s operations must appear with x = 1 before y = 1, and Thread 2’s with r1 = y before r2 = x.
Across the whole program, the following six interleavings are possible:
x = 1
y = 1
r1 = y(1)
r2 = x(1)
x = 1
r1 = y(0)
y = 1
r2 = x(1)
x = 1
r1 = y(0)
r2 = x(1)
y = 1
r1 = y(0)
x = 1
y = 1
r2 = x(1)
r1 = y(0)
x = 1
r2 = x(1)
y = 1
r1 = y(0)
r2 = x(0)
x = 1
y = 1
Six possible executions of the message-passing litmus test under sequential consistency.
None of these executions produce r1 = 1 and r2 = 0.
Sequential consistency therefore allows only (r1, r2) to be (1, 1), (0, 1), or (0, 0).
Software may rely on (1, 0) never occurring, while hardware remains free to optimize as long as it preserves that guarantee.
A simple model of sequentially consistent hardware.
The figure above sketches one intuitive implementation: each thread accesses a single shared memory, and that memory processes one read or write at a time. Real machines are more complicated than that. They may include private caches, queues, and multiple banks, but they still qualify as sequentially consistent if the externally visible behavior matches the same abstract model.
Total store order (TSO)
Although sequential consistency is often treated as the gold standard for reasoning about multi-threaded programs, it leaves limited room for performance optimization. Modern processors therefore tend to implement weaker models. For example, x86 processors are usually described using the total store order (TSO) model, which can be approximated by the following picture:
A simplified model of x86-TSO hardware.
Under TSO, all processors can read from a single shared memory, but each processor first places its own writes into a per-core write queue, often called a store buffer.
Consider the following write-queue litmus test:
// Litmus Test: Write Queue (Store Buffer)
int x = 0;
int y = 0;
// Thread 1 // Thread 2
x = 1; y = 1;
r1 = y; r2 = x;
Sequential consistency does not allow r1 = r2 = 0, but TSO does.
Under SC, at least one of x = 1 or y = 1 must become visible before the reads occur.
Under TSO, however, both writes may still be sitting in their respective store buffers when the reads execute, so each thread can still observe 0.
Non-sequentially consistent hardware typically provides memory barriers, or fences, to restore stronger ordering when needed. On a TSO machine, placing a barrier between the write and the read forces older writes to drain before later reads execute:
// Thread 1 // Thread 2
x = 1; y = 1;
barrier; barrier;
r1 = y; r2 = x;
The name total store order comes from the fact that once a write leaves the store buffer and reaches shared memory, every processor agrees on where that write sits relative to other writes. Different processors may see a write late, but they do not disagree about the final order in which committed writes become visible.
Consider the following Independent Reads of Independent Writes (IRIW) litmus test:
// Litmus Test: Independent Reads of Independent Writes (IRIW)
int x = 0;
int y = 0;
// Thread 1 // Thread 2 // Thread 3 // Thread 4
x = 1; y = 1; r1 = x; r3 = y;
r2 = y; r4 = x;
If Thread 3 observes r1 = 1 and r2 = 0, then in the single global store order x = 1 must have committed before y = 1.
If Thread 4 also observes r3 = 1, that same global order forces r4 to see x = 1 as well, so r4 can only be 1.
Under TSO, all threads agree on the order in which committed writes become visible, which rules out the disagreement that IRIW would require.
Relaxed memory models
A simplified relaxed model resembling ARM hardware.
The figure above sketches a more relaxed model similar to that used by modern ARM processors. Each core can read and write through its own local structures, and writes may propagate to other cores in different orders. Reads may also be delayed or speculated until their values are needed. This gives the hardware substantially more freedom than either SC or TSO.
One property still remains essential: accesses to the same memory location must obey coherence. All threads must eventually agree on the order in which writes to a single address become visible. Without coherence, even simple shared-state programs would be almost impossible to reason about.
The following coherence litmus test is therefore disallowed not only on ARM, but also on x86-TSO and under sequential consistency:
// Litmus Test: Coherence
int x = 0;
// Thread 1 // Thread 2 // Thread 3 // Thread 4
x = 1; x = 2; r1 = x; r3 = x;
r2 = x; r4 = x;
No execution may produce r1 = 1, r2 = 2, r3 = 2, and r4 = 1, because that would require different threads to disagree about the order of writes to x.
Litmus tests like these are commonly checked with tools rather than by hand.
The diy and herd7 tools let you describe a small concurrent program, choose an architecture or language memory model, and enumerate the outcomes that are allowed.
That workflow is especially useful when validating whether a surprising execution is genuinely permitted by ARM, x86-TSO, or the C++ memory model.
C11/C++11 atomics
By default, all atomic operations, including loads, stores, and various forms of RMW, are considered sequentially consistent. However, this is just one among many possible orderings. We will explore each of these orderings in detail. A comprehensive list, as well as the corresponding enumerations used by the C and C++ API, can be found here:
- Sequentially Consistent (
memory_order_seq_cst) - Acquire (
memory_order_acquire) - Release (
memory_order_release) - Relaxed (
memory_order_relaxed) - Acquire-Release (
memory_order_acq_rel) - Consume (
memory_order_consume)
To pick an ordering, you provide it as an optional argument that we have slyly failed to mention so far:1
void lock()
{
while (af.test_and_set(memory_order_acquire)) { /* wait */ }
}
void unlock()
{
af.clear(memory_order_release);
}
Non-sequentially consistent loads and stores also use member functions of std::atomic<>:
int i = foo.load(memory_order_acquire);
Compare-and-swap operations are a bit odd in that they have two orderings: one for when the CAS succeeds, and one for when it fails:
while (!foo.compare_exchange_weak(
expected, expected * by,
memory_order_seq_cst, // On success
memory_order_relaxed)) // On failure
{ /* empty loop */ }
With the syntax out of the way, let’s look at what these orderings are and how we can use them. As it turns out, almost all of the examples we have seen so far do not actually need sequentially consistent operations.
Acquire and release
We have just examined the acquire and release operations in the context of the lock example from Do we always need sequentially consistent operations?. You can think of them as “one-way” barriers: an acquire operation permits other reads and writes to move past it, but only in a \(before \to after\) direction. A release works the opposite manner, allowing actions to move in an \(after \to before\) direction. On ARM and other weakly-ordered architectures, this enables us to eliminate one of the memory barriers in each operation, such that
int acquireFoo()
{
return foo.load(memory_order_acquire);
}
void releaseFoo(int i)
{
foo.store(i, memory_order_release);
}
become:
acquireFoo:
ldr r3, <&foo>
ldr r0, [r3, #0]
dmb
bx lr
releaseFoo:
ldr r3, <&foo>
dmb
str r0, [r3, #0]
bx lr
Together, these provide \(writer \to reader\) synchronization: if thread W stores a value with release semantics, and thread R loads that value with acquire semantics, then all writes made by W before its store-release are observable to R after its load-acquire. If this sounds familiar, it is exactly what we were trying to achieve in Background and Enforcing law and order:
int v;
std::atomic_bool v_ready(false);
void threadA()
{
v = 42;
v_ready.store(true, memory_order_release);
}
void threadB()
{
while (!v_ready.load(memory_order_acquire)) {
// wait
}
assert(v == 42); // Must be true
}
Relaxed
Relaxed atomic operations are useful for variables shared between threads where no specific order of operations is needed. Although it may seem like a niche requirement, such scenarios are quite common.
Relaxed operations are beneficial for managing flags shared between threads. For example, a worker thread in thread pool in Read-modify-write might continuously run until it receives a cancelled signal:
while (1) {
if (atomic_load_explicit(&thrd_pool->state, memory_order_relaxed) == cancelled)
return EXIT_SUCCESS;
/* acquire: unlike cancelled, this one announces a filled queue */
if (atomic_load_explicit(&thrd_pool->state, memory_order_acquire) == running) {
/* claim the job */
job_t *job = atomic_load_explicit(&thrd_pool->head->prev,
memory_order_acquire);
while (job != &thrd_pool->head->job &&
!atomic_compare_exchange_weak_explicit(&thrd_pool->head->prev,
&job, job->prev,
memory_order_release,
memory_order_acquire))
;
if (job == &thrd_pool->head->job) {
atomic_store(&thrd_pool->state, idle);
thrd_yield();
} else {
job->future->result = job->func(job->future->arg);
atomic_flag_clear(&job->future->flag);
free(job); /* could cause dangling pointer in other threads */
}
} else {
thrd_yield();
}
}
We do not care if the contents of the loop are rearranged around that load.
Nothing bad will happen so long as cancelled is only used to tell the worker to exit, and not to “announce” any new data.
The very next line shows where that condition stops holding.
running does announce data, because the employer fills the queue and only then switches the pool to it,
so that load is an acquire and pairs with the employer’s store.
Everything the employer wrote beforehand, including the links it rewrote on jobs that were already queued, is ordered by that one pairing.
It is the whole reason the worker may then walk the queue at all,
and it holds only for as long as the employer confines its edits to a pool that is idle.
Finally, relaxed loads are commonly used with CAS loops,
where a failed comparison means nothing more than “try again”
and no order needs enforcing until we have successfully modified our value.
The loop above is not one of those cases, which is why both of the reads it makes on head->prev are acquires:
it follows the pointer it reads, taking job->prev to compute the next candidate and dereferencing the job once the claim succeeds.
A release on the successful CAS only keeps the claiming thread’s own earlier work from drifting past it;
it constrains nothing that comes afterwards,
so it cannot make the employer’s writes visible to the reads that follow the claim.
That has to come from the reading side, and there are two reads here, both of which need it:
the initial load, and the reload that a failed compare-exchange performs, which is why the failure order is an acquire rather than relaxed.
A CAS loop that only re-reads a value it never follows can leave every load relaxed.
Acquire-Release
memory_order_acq_rel is used with atomic RMW operations that need to both load-acquire and store-release a value.
A typical example involves thread-safe reference counting,
like in C++’s shared_ptr:
atomic_int refCount;
void inc()
{
refCount.fetch_add(1, memory_order_relaxed);
}
void dec()
{
if (refCount.fetch_sub(1, memory_order_acq_rel) == 1) {
// No more references, delete the data.
}
}
Order does not matter when incrementing the reference count since no action is taken as a result. However, when we decrement, we must ensure that:
- All access to the referenced object happens before the count reaches zero.
- Deletion happens after the reference count reaches zero.2
Curious readers might be wondering about the difference between acquire-release and sequentially consistent operations. To quote Hans Boehm, chair of the ISO C++ Concurrency Study Group,
The difference between
acq_relandseq_cstis generally whether the operation is required to participate in the single global order of sequentially consistent operations.
In other words, acquire-release provides order relative to the variable being load-acquired and store-released, whereas sequentially consistent operation provides some global order across the entire program. If the distinction still seems hazy, you are not alone. Boehm goes on to say,
This has subtle and unintuitive effects. The [barriers] in the current standard may be the most experts-only construct we have in the language.
Consume
Last but not least, we introduce memory_order_consume.
Imagine a situation where data changes rarely but is frequently read by many threads.
For example, in a kernel tracking peripherals connected to a machine,
updates to this information occur very infrequently—only when a device is plugged in or removed.
In such cases, it is logical to prioritize read optimization as much as possible.
Based on our current understanding, the most effective strategy is:
std::atomic<PeripheralData*> peripherals;
// Writers:
PeripheralData* p = kAllocate(sizeof(*p));
populateWithNewDeviceData(p);
peripherals.store(p, memory_order_release);
// Readers:
PeripheralData *p = peripherals.load(memory_order_acquire);
if (p != nullptr) {
doSomethingWith(p->keyboards);
}
To further enhance optimization for readers,
bypassing a memory barrier on weakly-ordered systems for loads would be ideal.
Fortunately, this is often achievable.
The data being accessed (p->keyboards) relies on the value of p,
leading most platforms, including those with weak ordering,
to maintain the sequence of the initial load (p = peripherals) and its subsequent use (p->keyboards).
However, it is notable that on some particularly weakly-ordered architectures, like DEC Alpha,
this reordering can occur, much to the frustration of developers.
Ensuring the compiler avoids any similar reordering is crucial, and memory_order_consume is designed for this purpose.
Change readers to:
PeripheralData *p = peripherals.load(memory_order_consume);
if (p != nullptr) {
doSomethingWith(p->keyboards);
}
and an ARM compiler could emit:
ldr r3, &peripherals
ldr r3, [r3]
// Look ma, no barrier!
cbz r3, was_null // Check for null
ldr r0, [r3, #4] // Load p->keyboards
b doSomethingWith(Keyboards*)
was_null:
...
Sadly, the emphasis here is on could. Figuring out what constitutes a “dependency” between expressions is not as trivial as one might hope,3 so all compilers currently convert consume operations to acquires.
-
In C, separate functions are defined for cases where specifying an ordering is necessary.
exchange()becomesexchange_explicit(), a CAS becomescompare_exchange_strong_explicit(), and so on. ↩ -
This can be optimized even further by making the acquire barrier only occur conditionally, when the reference count is zero. Standalone barriers are outside the scope of this paper, since they are almost always pessimal compared to a combined load-acquire or store-release. ↩
-
Even the experts in the ISO committee’s concurrency study group, SG1, came away with different understandings. See N4036 for the gory details. Proposed solutions are explored in P0190R3 and P0462R1. ↩
HC SVNT DRACONES
Non-sequentially consistent orderings have many subtleties, and a slight mistake can cause elusive Heisenbugs that only happen sometimes, on some platforms. Before reaching for them, ask yourself:
- Am I using a well-known and understood pattern
(such as the ones shown above)? - Are the operations in a tight loop?
- Does every microsecond count here?
If the answer is not yes to several of these, stick to sequentially consistent operations. Otherwise, be sure to give your code extra review and testing.
Hardware convergence
Those familiar with ARM may have noticed that all assembly shown here is for the seventh version of the architecture.
Excitingly, the eighth generation offers massive improvements for lockless code.
Since most programming languages have converged on the memory model we have been exploring,
ARMv8 processors offer dedicated load-acquire and store-release instructions: lda and stl.
Hopefully, future CPU architectures will follow suit.
If concurrency is the question, volatile is not the answer.
Before we go, we should lay a common misconception surrounding the volatile keyword to rest.
Perhaps because of how it worked in older compilers and hardware,
or due to its different meaning in languages like Java and C#,1
some believe that the keyword is useful for building concurrency tools.
Except for one specific case (see Atomic fusion), this is false.
The purpose of volatile is to inform the compiler that a value can be changed by something besides the program we are executing.
This is useful for memory-mapped I/O (MMIO),
where hardware translates reads and writes to certain addresses into instructions for the devices connected to the CPU.
(This is how most machines ultimately interact with the outside world.)
volatile implies two guarantees:
-
The compiler will not elide loads and stores that seem “unnecessary”. For example, if I have some function:
void write(int *t) { *t = 2; *t = 42; }the compiler would normally optimize it to:
void write(int *t) { *t = 42; }*t = 2is often considered a dead store, seemingly performing no function. However, whentis directed at an MMIO register, this assumption becomes unsafe. In such cases, each write operation could potentially influence the behavior of the associated hardware. -
The compiler will not reorder
volatilereads and writes with respect to othervolatileones for similar reasons.
These rules fall short of providing the atomicity and order required for safe communication between threads.
It is important to note that the second rule only prevents volatile operations from being reordered in relation to one another.
The compiler remains at liberty to reorganize all other “normal” loads and stores around them.
Furthermore, even setting this issue aside,
volatile does not generate memory barriers on hardware with weak ordering.
The effectiveness of the keyword as a synchronization tool hinges on both the compiler and the hardware avoiding any reordering,
which is not a reliable expectation.
-
Unlike in C and C++,
volatiledoes enforce ordering in those languages. ↩
Atomic fusion
Finally, one should realize that while atomic operations do prevent certain optimizations,
they are not somehow immune to all of them.
The optimizer can do fairly mundane things, such as replacing
foo.fetch_and(0) with foo = 0,
but it can also produce surprising results.
Consider:
while (tmp = foo.load(memory_order_relaxed)) {
doSomething(tmp);
}
Since relaxed loads provide no ordering guarantees, the compiler is free to unroll the loop as much as it pleases, perhaps into:
while (tmp = foo.load(memory_order_relaxed)) {
doSomething(tmp);
doSomething(tmp);
doSomething(tmp);
doSomething(tmp);
}
If “fusing” reads or writes like this is unacceptable,
we must prevent it
with volatile casts or incantations like asm volatile("" ::: "memory").1
The Linux kernel provides READ_ONCE() and WRITE_ONCE()
macros for this exact purpose.2
Takeaways
We have only scratched the surface here, but hopefully you now know:
- Why compilers and CPU hardware reorder loads and stores.
- Why we need special tools to prevent these reorderings to communicate between threads.
- How we can guarantee sequential consistency in our programs.
- Atomic read-modify-write operations.
- How atomic operations can be implemented on weakly-ordered hardware, and what implications this can have for a language-level API.
- How we can carefully optimize lockless code using non-sequentially-consistent memory orderings.
- How false sharing can impact the performance of concurrent memory access.
- Why
volatileis an inappropriate tool for inter-thread communication. - How to prevent the compiler from fusing atomic operations in undesirable ways.
To learn more, see the additional resources below, or examine lock-free data structures and algorithms, such as a single-producer/single-consumer (SP/SC) queue or read-copy-update (RCU).1
Good luck and godspeed!
-
See the LWN article, What is RCU, Fundamentally? for an introduction. ↩
Additional Resources
C++ atomics, from basic to advanced. What do they really do? by Fedor Pikus, an hour-long talk on this topic.
How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs, Leslie Lamport’s classic paper introducing sequential consistency.
x86-TSO: A Rigorous and Usable Programmer’s Model for x86 Multiprocessors, by Peter Sewell et al., for a precise description of the x86 memory model.
Hardware Memory Models, by Russ Cox, the essay whose SC/TSO/relaxed progression and litmus tests this chapter’s “Memory consistency models” section is adapted from.
atomic<> Weapons: The C++11 Memory Model and Modern Hardware
by Herb Sutter,
a three-hour talk that provides a deeper dive.
Also the source of the idealized multi-core processor and memory hierarchy figures.
Futexes are Tricky, a paper by Ulrich Drepper on how mutexes and other synchronization primitives can be built in Linux using atomic operations and syscalls.
Is Parallel Programming Hard, And, If So, What Can You Do About It?, by Paul E. McKenney, an incredibly comprehensive book covering parallel data structures and algorithms, transactional memory, cache coherence protocols, CPU architecture specifics, and more.
Memory Barriers: a Hardware View for Software Hackers, an older but much shorter piece by McKenney explaining how memory barriers are implemented in the Linux kernel on various architectures.
diy,
plus the related
herdtools7 suite,
for generating and checking litmus tests against hardware and language memory models.
Preshing On Programming, a blog with many excellent articles on lockless concurrency.
No Sane Compiler Would Optimize Atomics, a discussion of how atomic operations are handled by current optimizers. Available as a writeup, N4455, and as a CppCon talk.
cppreference.com, an excellent reference for the C and C++ memory model and atomic API.
Matt Godbolt’s Compiler Explorer, an online tool that provides live, color-coded disassembly using compilers and flags of your choosing. Fantastic for examining what compilers emit for various atomic operations on different architectures.
Contributing
Contributions are welcome! Sources are available on GitHub. This paper is prepared in LaTeX.
This paper is published under a Creative Commons Attribution-ShareAlike 4.0 International License. The legalese can be found through https://creativecommons.org/licenses/by-sa/4.0/, but in short, you are free to copy, redistribute, translate, or otherwise transform this paper so long as you give appropriate credit, indicate if changes were made, and release your version under this same license.