Module 2 · Lesson 14 of 30

Advanced synchronisation, atomics, lock-free ring buffer

Choose synchronization tools, prove an atomic SPSC ring correct on ARM, and investigate false sharing, ABA and safe memory reclamation.

  • Beginner to advanced
  • 28 min read
  • 60 min lab
What you will need

Linux with a C11 compiler and pthreads; optional ARM Linux board, ThreadSanitizer and perf for target measurements

By the end you can 7 objectives
  • Identify atomic operations and distinguish atomicity, ordering and progress guarantees.
  • Explain release/acquire publication and compare relaxed and sequentially consistent ordering.
  • Apply spinlocks, read-write locks, barriers and POSIX semaphores to suitable workloads.
  • Implement a single-producer single-consumer ring and justify both ownership transfers.
  • Analyze compare-and-swap loops, ABA and memory reclamation in stacks and MPMC queues.
  • Evaluate seqlocks, user-space RCU and lock-free alternatives using correctness and latency evidence.
  • Design benchmarks that separate synchronization cost, false sharing and scheduler effects.
Read the lesson below; the video will appear here when published.
01

Make one shared operation indivisible

3 min read

Your sensor worker counts completed samples. A network worker counts completed transmissions.

The previous lesson used a mutex to keep shared changes consistent. Keep that solution unless measurements reveal a problem. Here you learn tools for different sharing patterns and shorter communication paths.

An can update a shared counter without your own mutex. C11 supplies atomic types and operations in <stdatomic.h>. The type atomic_int is an atomic integer; _Atomic(int) is the corresponding spelling using a language feature.

Atomicity answers whether an operation can be split from another thread's viewpoint. Ordering answers which surrounding operations must be visible before others. Progress answers whether a delayed participant can stop the others. These are separate questions.

Save this complete capability probe as atomic_probe.c. It stores a count, adds two, replaces the value, then reads it. Printing the results makes each operation's return value visible.

c
#include <stdatomic.h>
#include <stdio.h>

int main(void)
{
    atomic_int completed;
    atomic_init(&completed, 0);
    atomic_store(&completed, 7);
    int before_add = atomic_fetch_add(&completed, 2);
    int before_reset = atomic_exchange(&completed, 0);
    int current = atomic_load(&completed);
    printf("before_add=%d before_reset=%d current=%d lock_free=%d\n",
           before_add, before_reset, current,
           atomic_is_lock_free(&completed));
    return 0;
}

Compile it as C11. -Wall and -Wextra enable useful warnings; -pthread selects thread support for later examples.

bash
cc -std=c11 -O2 -Wall -Wextra -pthread atomic_probe.c -o atomic_probe
./atomic_probe

The first returned value should describe the count before addition. The exchange returns the value before replacement. Both operations read and modify the object as one action. A separate load followed by a store would leave room for another updater between them.

The non-explicit interfaces above use memory_order_seq_cst, explained next. Initialize objects before workers can reach them. Do not copy a live atomic object with memcpy() to create another synchronization object.

describes an algorithm under its stated execution assumptions. It does not promise every thread finishes quickly. Wait-free means each operation takes a bounded number of its own steps. Neither guarantee promises a wall-clock deadline when Linux can stop scheduling your thread.

The C language does not require every atomic type to be lock-free. Inspect atomic_is_lock_free() for actual objects.

Macros such as ATOMIC_INT_LOCK_FREE encode never, sometimes or always lock-free as 0, 1 or 2. A target may need library helpers and -latomic at link time. A successful build alone proves neither lock freedom nor low latency. GCC's atomic documentation explains possible external helpers.

Three separate guaranteesAtomicityCan another thread observe half an update?OrderingWhich earlier work becomes safe to read?ProgressCan delayed participants stop other operations?AtomicityCan another thread observehalf an update?OrderingWhich earlier work becomessafe to read?ProgressCan delayed participants stopother operations?
Atomicity, ordering and progress answer different questions about shared operations.
02

Publish data and transfer ownership

3 min read

Consider one measurement and one ready flag. A lets you express this handoff. memory_order_relaxed keeps the flag atomic but does not publish the measurement by itself.

These file-scope definitions and functions form a one-shot fragment. Call publish() exactly once from one thread. A second thread can call receive() until it succeeds. The payload remains alive and unchanged afterward.

c
#include <stdatomic.h>
#include <stdbool.h>

static int measurement;
static atomic_bool ready = false;

void publish(void)
{
    measurement = 42;
    atomic_store_explicit(&ready, true, memory_order_release);
}

bool receive(int *result)
{
    if (!atomic_load_explicit(&ready, memory_order_acquire))
        return false;
    *result = measurement;
    return true;
}

1Prepare the payload

The producer writes measurement before its release store. Release prevents that publication from losing the required ordering with earlier work. It does not make the payload itself atomic.

2Observe the publication

The consumer's acquire load must observe the value from that release store. Merely executing an acquire somewhere else is insufficient. Here there is only one store of true, which makes the source of the observed value clear.

3Read under the new ownership rule

The connection establishes a edge. The producer's payload write happens before the consumer's read. No ordinary accesses to that payload now conflict without ordering.

Resetting ready and overwriting the payload would require another handoff. The producer must know the consumer has finished reading. This return path is the part many broken queues omit.

Order Suitable use What it does not supply
relaxed Independent statistics counter Publication of another object
release Store that publishes completed writes Permission to read unrelated writers' data
acquire Load that observes a publication A guarantee that a new value appears immediately
acq_rel Read-modify-write that receives and publishes Automatic protection of a whole structure
seq_cst A simpler initial atomic design Lifetime management or a multi-object transaction

Sequential consistency adds one total order over sequentially consistent operations, subject to the language's rules. It simplifies many arguments but does not merge several instructions into one operation. Each atomic object also has its own modification order, the order of writes to that object. Relaxed operations retain that property.

Use relaxed fetch-add for a counter whose value does not grant permission to read other data. Use release/acquire to hand over data. Start with sequential consistency when the weaker proof is unclear. Consult the memory model and atomic clauses in the C11 draft for exact rules.

Volatile does not synchronize threads

A volatile access does not establish a happens-before edge or make an increment indivisible. Adding volatile to an ordinary shared flag does not repair a C data race.

One-shot publicationWritepayloadProducerowns thedataReleaseflagPublishearlierwritesAcquireflagObservethatreleaseReadpayloadNoconcurrentoverwriteWritepayloadProducerowns thedataReleaseflagPublishearlierwritesAcquireflagObservethatreleaseReadpayloadNoconcurrentoverwrite
A release store and its observing acquire load order a payload write before its read.
03

Share readers and choose whether to spin

3 min read

A device configuration might be read for every sample but updated only occasionally. A can fit that pattern. Readers must perform only reads of the protected state.

Declare a pthread_rwlock_t and initialize it with PTHREAD_RWLOCK_INITIALIZER, or use pthread_rwlock_init(). A reader calls pthread_rwlock_rdlock(), copies what it needs, then calls pthread_rwlock_unlock(). A writer uses pthread_rwlock_wrlock() before changing the state. Destroy the lock with pthread_rwlock_destroy() after all users finish.

These functions return error numbers directly. Check them using the pthread error handling from the previous lesson. Do not report pthread failures by reading errno.

Never assume you can upgrade a held read lock into a write lock. Two upgrading readers can wait for each other. Release the read lock, acquire the write lock, and recheck the condition. The state may change during the gap.

Fairness means how the implementation distributes opportunities to acquire a lock. POSIX does not offer one universal reader/writer fairness promise. Sustained reader traffic can delay writers.

On glibc, the default reader preference has specific starvation implications. Its nonportable PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP setting requires you to avoid recursive read locking. Do not assume musl has glibc's extension. See the glibc-specific attribute documentation.

A can avoid a sleep and wakeup for extremely short waits. POSIX provides pthread_spinlock_t, pthread_spin_init(&lock, PTHREAD_PROCESS_PRIVATE), pthread_spin_lock(), pthread_spin_trylock(), pthread_spin_unlock() and pthread_spin_destroy().

Keep the protected work bounded. Never perform blocking I/O, allocate memory or call a sleeping function while holding a spinlock. A signal handler that interrupts its holder and tries the same lock can stop progress indefinitely.

The scheduler can pause a user-space lock holder at any instruction. A spinner then burns CPU while the holder cannot release the lock.

On one core, this often makes waiting worse. A high-priority spinner can prevent a lower-priority holder from running. This is priority inversion: important work waits indirectly for less important work.

Ordinary Linux mutex implementations usually complete uncontended operations in user space. Their blocking path commonly uses a futex, which lets the kernel sleep a waiter only if a shared word still matches an expected value. A mutex therefore need not pay a system-call cost on every acquisition.

Going deeperKernel spinlocks are a different environment

Kernel locking includes rules about preemption and interrupts that pthread spinlocks cannot provide. PREEMPT_RT also changes the implementation of many kernel spinlocks; raw spinlocks retain stricter spinning behavior.

Kernel lockdep and KCSAN diagnose kernel locking and races. They do not check your pthread application. Use user-space tools for user-space defects.

Choose a mutex first. Try a read-write lock when substantial read work can overlap. Consider spinning only with measured short holds and enough runnable CPU capacity. More readers do not guarantee an rwlock beats a mutex: readers still update lock metadata.

Match access and waitingMutexRead-writelockSpinlockAccessOne ownerReaders orwriterOne ownerWaitingMay sleepMay sleepBusy checksGood candidateGeneralshared stateLong readworkVery shortholdsWatch forHold durationWriterstarvationPreemptedholder
A mutex, read-write lock and spinlock differ in access rules and waiting cost.
04

Count permits and meet at phase boundaries

3 min read

A supports more than exclusive ownership. Initialize an unnamed sem_t slots with sem_init(&slots, 0, capacity). Zero selects sharing among threads of this process. A nonzero sharing argument requires storage in genuinely shared memory for interprocess use.

sem_wait() takes one permit, sleeping if none are available. sem_post() adds one and can wake a waiter. A different thread may post; semaphores have no mutex-style owner. Their operations return zero on success and minus one on failure, setting errno.

This helper retries an interrupted wait. It requires <semaphore.h> and <errno.h> and returns other failures to its caller.

c
static int take_permit(sem_t *permits)
{
    int rc;
    do {
        rc = sem_wait(permits);
    } while (rc == -1 && errno == EINTR);
    return rc;
}

A bounded queue can use one semaphore for free slots and another for available items. The producer takes a free-slot permit, inserts safely, then posts an item permit.

The consumer reverses that flow. Multiple producers still need to coordinate which slot each owns. Permit counting alone does not protect a shared index.

Successful semaphore operations also synchronize memory. Prepare an item before posting its permit, and take the item permit before reading that item. Your slot-selection rules must still connect each permit to valid storage.

If insertion fails after taking a slot, return its permit. If cancellation is allowed, arrange cleanup at every ownership transition.

Posting too often can overflow the semaphore. Reading sem_getvalue() and then deciding whether to wait is a race; use sem_trywait() for an immediate attempt. Destroy an unnamed semaphore only after no thread can wait on or otherwise use it. sem_wait(3) documents interruption and failure behavior.

A divides work into phases. Create pthread_barrier_t phase with pthread_barrier_init(&phase, NULL, workers). Each worker writes its private result and calls pthread_barrier_wait(&phase).

One unspecified participant receives PTHREAD_BARRIER_SERIAL_THREAD; the others receive zero. Both indicate success. The special return does not mean that participant finishes its following work before the others proceed.

If one participant combines results, a second barrier must separate that combination from the next phase. Otherwise another thread could reuse an input or read an unfinished combined result. Do not reinitialize or destroy the barrier while participants still use it.

A failed thread creation is especially dangerous here. If the barrier expects four workers but only three start, the three may wait forever. Hold workers behind a start gate until creation succeeds, or abort the teaching process on startup failure. A reusable service needs an explicit recovery design.

Two meanings of barrier

A pthread barrier waits for threads. A memory barrier constrains memory ordering. Calling atomic_thread_fence() does not wait for other workers to arrive.

Two rendezvous protect reusePrivateresultsEach workerfinishesits partFirstbarrierAll participantsarriveCombineresultsOneparticipantworks;othersapproachnextbarrierSecondbarrierCombinationfinishesbeforeanyoneproceedsReuseinputsNext phasecan start↻ Repeat from step 1PrivateresultsEach workerfinishesits partFirstbarrierAll participantsarriveCombineresultsOneparticipantworks;othersapproachnextbarrierSecondbarrierCombinationfinishesbeforeanyoneproceedsReuseinputsNext phasecan start↻ Repeat from step 1
Workers rendezvous before a serial combination and again before reusing phase data.
05

Retry a change with compare-and-swap

3 min read

Compare-and-swap, abbreviated CAS, means compare an atomic object's value with an expected value and replace it only if they match. C calls these operations compare-exchange. Success returns true. Failure returns false and updates the caller's expected object with the observed value.

Here a relaxed atomic counter records admissions up to a fixed limit. It grants no access to other data. Include <stdatomic.h> and <stdbool.h>. The counter is initialized once to a value no greater than limit; no other operation changes it except calls using this same limit.

c
bool admit(atomic_uint *used, unsigned limit)
{
    unsigned observed = atomic_load_explicit(used, memory_order_relaxed);
    for (;;) {
        if (observed >= limit)
            return false;
        if (atomic_compare_exchange_weak_explicit(
                used, &observed, observed + 1,
                memory_order_relaxed, memory_order_relaxed))
            return true;
    }
}

The proposed addition cannot overflow here: it occurs only while observed < limit, and limit fits in unsigned. A failed comparison changes observed. The loop then recomputes the desired value from that newer observation.

atomic_compare_exchange_weak() may fail even when the comparison matches. This spurious failure suits hardware that uses an exclusive load followed by a conditional store. An interruption or another write can invalidate its reservation. A weak CAS belongs in a retry loop unless failure is acceptable.

atomic_compare_exchange_strong() does not report that kind of spurious failure. It remains useful when one failed comparison should choose another path. Strong CAS can still lose to real interference; it does not guarantee an entire algorithm succeeds without retries.

A successful CAS records one admission by incrementing used once. Comparison failure or spurious weak-CAS failure returns to the limit check using the observed value; observed at least limit returns false.

  • states: [{"id": "check", "label": "Check observed against limit"}, {"id": "attempt", "label": "Weak CAS: replace observed with observed + 1"}, {"id": "admitted", "label": "Return true: one admission recorded"}, {"id": "rejected", "label": "Return false: limit reached"}]
  • transitions: [{"from": "check", "to": "attempt", "event": "Observed is below limit"}, {"from": "check", "to": "rejected", "event": "Observed is at least limit"}, {"from": "attempt", "to": "admitted", "event": "CAS succeeds"}, {"from": "attempt", "to": "check", "event": "Comparison fails: refresh observed"}, {"from": "attempt", "to": "check", "event": "Spurious failure: recheck observed"}]

Explicit CAS has separate success and failure orders. A failed CAS performs a load, so its failure order cannot be release or acq_rel.

Under C11 it also cannot be stronger than the success order. Use release/relaxed when only successful replacement publishes a new object. Use acquire/acquire when either success or failure must make an observed node's initialized fields available.

Keep retry bodies free from irreversible effects. Do not send a message or charge a device inside a loop that may repeat. Allocation inside the loop also complicates cleanup and progress. Prefer preparing resources before attempting publication.

Step by stepFollow one compare-exchange attempt
  1. Observe: Load the current atomic value into a local expected value.

  2. Decide: Reject an invalid state or compute a proposed replacement.

  3. Compare: Test and conditionally replace the atomic value in one operation.

  4. Finish: On success, return without repeating external effects.

  5. Retry: On failure, use the updated expected value and reconsider the decision.

CAS checks a value, not its history. If a pointer changes from address A to B and back to A, a comparison may succeed. That observation starts the ABA problem, explored after the ring buffer. A stronger memory order cannot tell you whether a removed object was freed and replaced.

Reconsider after interferenceObserveLocalexpectedvalueComputeproposalChecklimitsfirstCompare andreplaceFailureupdatesexpectedReconsiderRecomputefromupdatedexpectedExit from step 3: successReturn↻ Repeat from step 1ObserveLocalexpectedvalueComputeproposalChecklimitsfirstCompare andreplaceFailureupdatesexpectedReconsiderRecomputefromupdatedexpectedExit from step 3: successReturn↻ Repeat from step 1
A compare-exchange loop recomputes its proposal after failure updates the expected value.
06

Follow ordering through the compiler and CPU

4 min read

A cache is a small, fast memory near a processor. A cache line is the unit it usually transfers and tracks. does not replace the C memory model. Coherent machines can still expose different orders for operations on different locations.

The compiler transforms C according to language rules. The CPU may overlap instructions or hold stores temporarily before other cores observe them. You must satisfy both layers. Testing ordinary racy code on a strongly ordered CPU does not make it defined C.

For ordinary cacheable memory, x86's total store order, or TSO, is relatively strong. A later load of another address can nevertheless execute before an earlier buffered store becomes visible elsewhere. On AArch64, a common 64-bit Arm execution architecture, ordinary loads and stores allow more reordering.

Compilers commonly map suitable AArch64 acquire loads to ldar and release stores to stlr. They can use dmb, a hardware memory barrier instruction, when required. Atomic updates may use exclusive-load/store loops, hardware atomic instructions, or library helpers. Target features and compiler decisions matter; do not infer instructions from the C name alone.

Release and acquire often need no extra hardware fence for simple x86 loads and stores, yet still restrict compiler transformations. Do not remove them when porting to an ARM board. Inspect generated assembly using your configured cross-compiler and its -S option. Its target C library and atomic support must match the board.

1Place a fence before publication

A fence orders surrounding memory operations without storing a flag itself. This alternative one-shot fragment uses relaxed flag operations to connect two fences. It has the same no-reset and unchanged-payload requirements as the earlier handoff.

c
#include <stdatomic.h>
#include <stdbool.h>

static int payload;
static atomic_bool published = false;

void publish_fenced(void)
{
    payload = 42;
    atomic_thread_fence(memory_order_release);
    atomic_store_explicit(&published, true, memory_order_relaxed);
}

bool receive_fenced(int *result)
{
    if (!atomic_load_explicit(&published, memory_order_relaxed))
        return false;
    atomic_thread_fence(memory_order_acquire);
    *result = payload;
    return true;
}

2Connect the fences through the atomic flag

The observing load reads the store after the release fence. The acquire fence follows that load.

Without that communication, unrelated fences do not publish anything. Prefer direct release/acquire flag operations when they make the proof easier. A relaxed fence has no effect. atomic_signal_fence() constrains compiler ordering for signal interactions; it is not a substitute for inter-thread synchronization.

Neither fence writes modified cache lines to persistent storage. Nor do C atomics provide device-specific ordering for memory-mapped registers or direct memory access, where hardware moves data without CPU instructions. Follow the device driver interface for those operations. Linux's barrier guide distinguishes these hardware concerns; its kernel primitives are not user-space C APIs.

Contention means several workers compete for the same shared resource. can make correct code slow. Two relaxed atomic counters can repeatedly transfer line ownership between cores. No language data race is needed.

For a board whose relevant cache line is 64 bytes, this GNU C layout separates two counters. Alignment means restricting an object's starting address to a required boundary.

c
#include <stdatomic.h>

struct counter_cell {
    atomic_ulong value;
} __attribute__((aligned(64)));

static struct counter_cell counters[2];

Padding is unused space inserted between objects or at a structure's end. The aligned structure's size includes padding so successive array elements satisfy its alignment. _Alignas(64) is a standard C alternative for appropriately placed objects. Neither spelling discovers the target's line size. Do not place over-aligned objects in storage that fails their alignment requirement; ordinary malloc() is not a universal solution for extended alignment.

Compare packed and separated counters using two workers, each updating only its own counter. Initialize before starting.

Read final totals after joining. Keep the same atomic operation and iteration count; otherwise you changed more than sharing. Padding consumes scarce RAM and can worsen locality, so measure before applying it everywhere.

Different objects can share trafficPackedcountersSeparatedcountersWorker ownershipOne countereachOne countereachCache placementSame linepossibleSeparaterelevantlinesWrite trafficLineownershipcompetesIndependentlineownershipTradeoffSmallerstoragePadding usesRAM
Independent counters can compete for one cache line, while aligned cells separate their writes.
07

Build and prove an SPSC ring buffer

5 min read

SPSC means single producer, single consumer. Exactly one thread calls the insertion function. Exactly one calls the removal function. An index identifies an array slot; wrapping makes the slot after the last one be slot zero.

Here head is the next slot to fill and tail the next slot to remove. Equal indices mean empty. To distinguish full from empty, one slot always remains unused. An array of RING_N slots holds at most RING_N - 1 items.

This complete reusable component has no main(). Save it as spsc.c. Call ring_init() before workers start.

Keep the ring alive until both workers have joined. Failed attempts return immediately, allowing your caller to choose retry, drop or backpressure. Backpressure means slowing an upstream producer when downstream storage is full.

c
#include <stdatomic.h>
#include <stdbool.h>
#include <stddef.h>

#define RING_N 256u
_Static_assert(RING_N >= 2u, "ring needs a sentinel slot");

struct ring {
    _Alignas(64) atomic_size_t head;
    _Alignas(64) atomic_size_t tail;
    _Alignas(64) unsigned samples[RING_N];
};

void ring_init(struct ring *q)
{
    atomic_init(&q->head, 0);
    atomic_init(&q->tail, 0);
}

bool ring_push(struct ring *q, unsigned sample)
{
    size_t h = atomic_load_explicit(&q->head, memory_order_relaxed);
    size_t next = h + 1u;
    if (next == RING_N)
        next = 0;
    size_t t = atomic_load_explicit(&q->tail, memory_order_acquire);
    if (next == t)
        return false;
    q->samples[h] = sample;
    atomic_store_explicit(&q->head, next, memory_order_release);
    return true;
}

bool ring_pop(struct ring *q, unsigned *sample)
{
    size_t t = atomic_load_explicit(&q->tail, memory_order_relaxed);
    size_t h = atomic_load_explicit(&q->head, memory_order_acquire);
    if (t == h)
        return false;
    size_t next = t + 1u;
    if (next == RING_N)
        next = 0;
    *sample = q->samples[t];
    atomic_store_explicit(&q->tail, next, memory_order_release);
    return true;
}

Use a static or properly aligned ring object. The 64-byte layout is a tuning assumption, not part of correctness. Check lock freedom of both index objects on your target. If either uses a blocking helper, the component cannot claim lock-free progress there.

Compile the component to an object file before integrating a worker harness. -c stops before linking because this component has no entry point.

bash
cc -std=c11 -O2 -Wall -Wextra -pthread -c spsc.c -o spsc.o

1Give each index one writer

Only the producer stores head; only the consumer stores tail. Each can load its own index with relaxed ordering. The opposing index carries ownership and needs acquire ordering. Adding another producer breaks this proof, even though every index access remains atomic.

2Publish the sample

The producer writes a slot before publishing its new head with release ordering. The consumer's observing acquire orders that slot write before its read. The ordinary array element therefore needs no atomic type.

3Return the slot

The consumer reads the slot before its release store to tail. The producer's observing acquire orders that read before later reuse. Without this return edge, the next write could race with a consumer still reading.

In a successful slot reuse cycle, the head release and observing acquire order the sample write before its read. The tail release and observing acquire order the completed read before the next overwrite; exactly one producer and one consumer are required.

  • states: [{"id": "check_room", "label": "Producer checks capacity for this slot"}, {"id": "writable", "label": "Producer owns reusable slot"}, {"id": "filled", "label": "Sample written but not published"}, {"id": "published", "label": "Head release publishes filled slot"}, {"id": "readable", "label": "Consumer has acquired published head"}, {"id": "copied", "label": "Consumer has finished copying sample"}]
  • transitions: [{"from": "check_room", "to": "writable", "event": "Producer acquires tail and confirms room"}, {"from": "writable", "to": "filled", "event": "Producer writes sample"}, {"from": "filled", "to": "published", "event": "Producer release-stores head"}, {"from": "published", "to": "readable", "event": "Consumer acquire observes head publication"}, {"from": "readable", "to": "copied", "event": "Consumer reads sample"}, {"from": "copied", "to": "check_room", "event": "Consumer release-stores tail"}]
Step by stepFollow a slot through one complete reuse cycle
  1. Check room: The producer acquires the consumer's published progress.

  2. Fill slot: The producer writes into a slot it owns.

  3. Publish head: A release store announces the filled range.

  4. Take sample: The consumer acquires head and copies the sample.

  5. Publish tail: A release store announces that reading has finished.

  6. Reuse safely: The producer observes returned capacity before overwriting that slot.

Going deeperProve wraparound without assuming fresh reads

Indices always stay within the array. Each operation advances at most one slot. Atomic coherence prevents one thread's successive observations of an opposing index from moving backward in that index's modification order.

A stale index can conservatively report full or empty. It cannot grant permission to cross the reserved gap.

The producer cannot lap the consumer because each advance stops at that gap; the consumer cannot pass published head. Numeric index values repeat, but the ordering argument follows successive publications, not integer uniqueness. Neither a single atomic load nor C's abstract model promises an immediate fresh value.

A shared count field would introduce a second location both workers modify and would need its own algorithm. This design avoids it. Do not replace the wrap check with % capacity and assume it is free: division by a runtime value can require an actual division instruction.

Batching can publish several initialized slots with one release, reducing coherence traffic but delaying visibility. Caching the opposing index locally can reduce loads, provided you refresh it before returning full or empty. Prove the simple version first. A false return is a failed attempt, not a promise that the queue stays full or empty afterward.

Both handoffs protect the slotProducerSlotConsumerWrite sampleRelease head; acquireCopy sampleRelease tail; acquireReuse after capacity1. Producer → SlotWrite sample2. Producer → ConsumerRelease head; acquire3. Slot → ConsumerCopy sample4. Consumer → ProducerRelease tail; acquire5. Producer → SlotReuse after capacity
Producer and consumer transfer filled data forward and reusable capacity backward through separate indices.
08

Keep removed nodes alive and scale beyond SPSC

4 min read

A stack removes its most recently added item first. A CAS-based stack can replace an atomic top pointer with that node's next pointer. Its linearization point is the atomic change where an operation appears to take effect. Linearizability means operations behave as if they took effect at single instants between their calls and returns, respecting completed-before-started order.

This fragment deliberately postpones every reclamation until all workers join. Include <stdatomic.h> and <stddef.h>.

Initialize each node's payload before pushing it. Each node may be pushed only once; its fields remain unchanged after publication, even after removal. Retain a separate allocation list for final cleanup.

c
struct node {
    unsigned sample;
    struct node *next;
};

struct stack {
    _Atomic(struct node *) top;
};

void stack_init(struct stack *s)
{
    atomic_init(&s->top, NULL);
}

void stack_push_once(struct stack *s, struct node *n)
{
    struct node *old = atomic_load_explicit(&s->top, memory_order_relaxed);
    do {
        n->next = old;
    } while (!atomic_compare_exchange_weak_explicit(
        &s->top, &old, n, memory_order_release, memory_order_relaxed));
}

struct node *stack_pop_deferred(struct stack *s)
{
    struct node *old = atomic_load_explicit(&s->top, memory_order_acquire);
    while (old != NULL) {
        struct node *next = old->next;
        if (atomic_compare_exchange_weak_explicit(
                &s->top, &old, next,
                memory_order_acquire, memory_order_acquire))
            return old;
    }
    return NULL;
}

Push failure updates old, so the loop rewrites the unpublished node's link before retrying. Pop failure acquires a possibly different node before dereferencing it on the next iteration.

Published links remain immutable, and every node stays allocated. These restrictions make stale dereferences safe. They are essential parts of the example.

A release sequence starts with a release operation and continues through qualifying modifications of the same atomic object. Other threads' read-modify-write operations can extend it in C11. Intervening pops therefore preserve the publication chain when a pop exposes an older node. Do not replace those atomic modifications with arbitrary stores and assume the same proof holds.

The becomes dangerous when you reuse nodes. Suppose a thread reads top A and next B.

Another thread removes both, reuses A, and installs A with a different link. The stale CAS can restore obsolete B. Sequential consistency does not prevent this history.

The restricted stack forbids removed-node reuse during the run. It is useful for a finite stress test, not a bounded-memory service. Allocate a known pool before starting.

Give samples unique identifiers, record successful pops in private per-thread storage, then join. Check every identifier appears exactly once and that the stack is empty after draining. Matching only an aggregate sum can miss errors.

Hazard pointers let readers announce which nodes they may dereference. A reader loads a candidate, publishes a hazard, then reloads the shared pointer. If it changed, the reader retries before dereferencing.

Removed nodes go onto a retired list. A reclaimer scans hazard records and frees only unprotected nodes. Publication and validation need a proven ordering protocol; casual relaxed stores can invalidate the protection.

Epoch-based reclamation groups activity into generations. Readers announce entry and exit.

A removed node becomes reclaimable after every reader that could have seen it has left the relevant older generation. A stalled reader can retain large retired lists, which matters on small boards. Both approaches require registration, shutdown and thread-exit handling.

Going deeperTags do not solve all pointer hazards

A pointer plus a changing tag can expose some ABA cycles. A finite tag can wrap, and a double-width atomic may require a non-lock-free helper.

Tags also do not prevent dereferencing freed memory before a CAS. Lifetime protection and history detection answer different questions. Never encode tags in supposedly unused pointer bits without an explicit architecture and ABI guarantee.

MPMC means multiple producers and multiple consumers. The Michael-Scott queue uses a linked list with a dummy node, atomic head/tail updates and helping. The dummy is a placeholder at the front rather than an item waiting for delivery.

Helping means completing another operation's unfinished shared bookkeeping. Linking a new node is enqueue's decisive change; advancing a lagging tail can be helped by another thread. A successful head advance removes an item, but the former dummy still needs safe reclamation. Its published algorithm states important allocator assumptions; do not translate pseudocode into C and add immediate free().

The LMAX Disruptor pattern instead emphasizes preallocated ring entries and sequence positions. Consumers can depend on earlier processing stages. Producers must gate reuse on the slowest required consumer.

Multi-producer variants separate claiming a sequence from publishing a completed entry. Padding and batching reduce traffic, while wait strategies trade CPU time for wake latency. These are design choices, not automatic improvements over an SPSC queue.

Removal is not reclamationInitializenodePrivateownershipPublishpointerReaders mayretain itRemove nodeOld readersmay remainRetire nodeKeepallocationaliveCheckprotectionHazardscleared orgraceperiodcompletedReclaimstorageNo readercandereferenceitInitializenodePrivateownershipPublishpointerReaders mayretain itRemove nodeOld readersmay remainRetire nodeKeepallocationaliveCheckprotectionHazardscleared orgraceperiodcompletedReclaimstorageNo readercandereferenceit
Removal, retirement and reclamation are separate events because readers may retain old pointers.
09

Choose a design and diagnose common mistakes

5 min read

A seqlock combines writer serialization with a sequence counter for readers. Before changing data, the writer makes the sequence odd.

After completing the update, it makes the sequence even. A reader reads an even sequence, copies the data, then rereads the sequence. It accepts only an unchanged even value.

Linux provides seqcount_t and seqlock_t for kernel code. Raw sequence counters require separate writer serialization.

Long or preempted writes can make readers retry extensively. Pointer targets can disappear while a reader follows them, so a sequence check alone does not protect their lifetime. See the kernel's seqlock documentation.

Do not translate that pattern into standard C using ordinary concurrent payload reads and writes. Retrying after a conflicting read does not erase the data race. A conservative teaching variant uses atomic payload fields and sequence operations, all sequentially consistent, plus serialized writers.

Its snapshot proof must exclude sequence wrap during one read. Weakening those orders requires another proof. For most user-space programs, a mutex or immutable replacement is easier to maintain.

Read-copy-update, or RCU, separates replacement from reclamation. A writer builds a new immutable version and publishes its pointer.

Readers enter a read-side region, use the current version, then leave. A grace period waits until readers that could have held the removed version have finished. Only then can storage be freed.

Use a supported user-space implementation such as liburcu. Its API includes rcu_read_lock(), rcu_read_unlock(), pointer publication/access helpers and synchronize_rcu().

Registration and build requirements depend on the chosen flavor. Do not call a blocking grace-period wait inside a read-side region that prevents that period from ending. RCU does not serialize competing writers or make in-place changes safe by itself.

Symptom Likely cause Diagnose Fix
Works on x86, fails on ARM Missing publication edge Draw each payload handoff; run race checks Restore release/acquire on both directions
Rare crash after stack pop A reader still holds a freed node AddressSanitizer; trace allocation lifetime Retire nodes through a proven reclamation scheme
Full queue overwrites samples Shared count or extra producer Record caller identities and sequence gaps Enforce SPSC or choose an MPMC algorithm
CPU rises without throughput Spinning, CAS retries or false sharing Profile busy loops and compare layouts Block, batch or separate measured hot fields
Barrier never completes Missing participant or unequal rounds Inspect all thread backtraces Correct phase counts and startup failure handling

1Establish correctness before timing

Stress the ring through many wraps using ordered identifiers. Test empty, full and transitions between them.

Delay either worker deliberately. Verify exact order and item counts, including the final drain. A fixed-count test can avoid a complicated shutdown protocol; a service must define what happens when production stops.

Build a separate ThreadSanitizer run using a supported compiler/runtime. The compiler adds checks that observe memory accesses to find races. It cannot prove linearizability or lock freedom.

Some environments fail before the test begins because of runtime address-space constraints. That is an unavailable check, not a passing result. AddressSanitizer needs a separate build to investigate lifetime defects.

2Compare equivalent work

Benchmark the SPSC ring against a mutex-protected buffer with the same capacity, item representation and validation. Report failed insertion attempts, CPU usage and elapsed time. Busy polling and condition-variable sleeping are different wait policies; name that difference explicitly. Keep printing, allocation and validation bookkeeping outside the timed hot path.

Measure time with clock_gettime(CLOCK_MONOTONIC, ...), which provides an elapsed-time clock unaffected by wall-clock adjustments. Throughput means items completed per unit time. Latency means the delay for one item. Report a distribution and its long tail, not only an average.

3Isolate hardware and scheduling effects

Repeat the packed-counter experiment on separate physical cores, then compare with both threads sharing a core. Affinity means restricting where the scheduler may run a thread.

Set it separately for each worker if your harness supports it. Pinning the entire process to a two-CPU mask does not assign one worker to each CPU. Record the CPU model, frequency policy, temperature and competing load; embedded boards may change frequency under heat or power limits.

perf stat can count events such as cycles and cache misses around a benchmark. perf c2c can investigate cache-line contention where the CPU and kernel support the required sampling. Generic cache-miss totals alone do not prove false sharing. BusyBox installations may lack these tools. Cross-build with the target sysroot, a directory containing its headers and libraries, then collect measurements with available target tooling.

Lock-free structures can win with fixed-size preallocated data, stable ownership and brief overlapping operations. Under heavy contention, CAS retries and coherence traffic can dominate.

Under light load, a sleeping mutex queue may use far less energy. A priority-inheritance mutex can address a scheduling dependency that a lock-free label does not eliminate. Reclamation and allocation may also block even when the pointer-update loop is lock-free.

Evidence before optimizationDefineownershipWho writeseachobject?ProveorderingConnecteverypayloadhandoffProtectlifetimeDelay reuseuntil safeCheckschedulingCanrequiredworkersrun?MeasureworkloadLatency,throughputand CPU useDefineownershipWho writeseachobject?ProveorderingConnecteverypayloadhandoffProtectlifetimeDelay reuseuntil safeCheckschedulingCanrequiredworkersrun?MeasureworkloadLatency,throughputand CPU use
Choose synchronization by checking ownership, lifetime, scheduling and measured cost.
10

Try it

1 min read

Use the lab, Build and benchmark an SPSC ring; measure false sharing; stress a CAS stack, to put these ownership rules under load. Start with the ring's exact identifier order, then compare its measured behavior with the mutex buffer. In the false-sharing task, change only the counter layout and explain the evidence. Use the lesson's practice pack to review ordering and lifetime decisions, and keep the stack's nodes allocated until all test workers finish.

Three practice investigationsProve theringCheckorderingacross manywrapsComparebuffersSameworkload;disclosewaitpoliciesMeasuresharingPackedversusalignedcountersStress thestackKeep nodesalive untilworkersjoinProve theringCheckorderingacross manywrapsComparebuffersSameworkload;disclosewaitpoliciesMeasuresharingPackedversusalignedcountersStress thestackKeep nodesalive untilworkersjoin
Practice proceeds from ring correctness to performance measurements and safe stack stress testing.

Key takeaways

  • An atomic object protects its own accesses; ordering determines what other data you can safely read.
  • Release/acquire publication needs an acquire that observes the relevant release.
  • C11 atomics can use library support; verify lock freedom on your target.
  • Spin only when the holder can run and the measured wait is very short.
  • An SPSC ring transfers filled slots forward and reusable slots back through separate atomic indices.
  • False sharing wastes cache traffic even when threads modify different objects.
  • Successful pointer removal does not prove that other readers have stopped using the node.
  • Choose a lock-free design only after proving safety and measuring the workload that matters.

Reflect

  1. Explain to a colleague, in two sentences: identify atomic operations and distinguish atomicity, ordering and progress guarantees.
  2. Which objective are you least sure about? Re-read that section, then do its exercise in the practice pack.
  3. What surprised you when you ran the commands yourself?

On a real board

Repeat the key commands on your Raspberry Pi or lab board over SSH or the serial console. Note anything that behaves differently from your PC, such as missing tools, a BusyBox shell or a read-only filesystem.

Practise this lessonExercises, quiz, interview preparation and spaced review

References and further reading

Official documentation first. Links checked when the lesson was published.

Find your next step

↑ ↓ to move · Enter to open · Esc to close