Make one shared operation indivisible
3 min readYour 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 an operation that other threads cannot observe halfway through 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.
#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.
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.
a progress guarantee that some operation completes despite delays to other participating threads 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.
Publish data and transfer ownership
3 min readConsider one measurement and one ready flag. A a rule that limits how operations can be observed across threads 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.
#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 an ordering relationship that makes earlier work safe for a later operation to observe 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.
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.
Share readers and choose whether to spin
3 min readA device configuration might be read for every sample but updated only occasionally. A a lock that permits several readers or one exclusive writer 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 a lock whose waiter repeatedly checks instead of sleeping 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.
Count permits and meet at phase boundaries
3 min readA a synchronization object that counts permits which threads can take and return 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.
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 a rendezvous that releases a configured group only after every participant arrives 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.
A pthread barrier waits for threads. A memory barrier constrains memory ordering. Calling atomic_thread_fence() does not wait for other workers to arrive.
Retry a change with compare-and-swap
3 min readCompare-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.
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.
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.
Observe: Load the current atomic value into a local expected value.
Decide: Reject an invalid state or compute a proposed replacement.
Compare: Test and conditionally replace the atomic value in one operation.
Finish: On success, return without repeating external effects.
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.
Follow ordering through the compiler and CPU
4 min readA cache is a small, fast memory near a processor. A cache line is the unit it usually transfers and tracks. the hardware mechanism that coordinates cached copies of the same memory location 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.
#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. cache-line contention caused by threads writing different objects that occupy the same cache line 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.
#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.
Build and prove an SPSC ring buffer
5 min readSPSC 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.
#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.
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.
Check room: The producer acquires the consumer's published progress.
Fill slot: The producer writes into a slot it owns.
Publish head: A release store announces the filled range.
Take sample: The consumer acquires head and copies the sample.
Publish tail: A release store announces that reading has finished.
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.
Keep removed nodes alive and scale beyond SPSC
4 min readA 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.
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 a failure where a value returns to its earlier representation but the assumptions behind it have changed 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.
Choose a design and diagnose common mistakes
5 min readA 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.
Try it
1 min readUse 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.
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
- Explain to a colleague, in two sentences: identify atomic operations and distinguish atomicity, ordering and progress guarantees.
- Which objective are you least sure about? Re-read that section, then do its exercise in the practice pack.
- 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.
References and further reading
- SpecificationC11 committee draft N1570, sections 5.1.2.4 and 7.17
- Official docsGCC memory-model-aware atomic builtins
- Man pagepthread_spin_lock(3)
- Man pagepthread_rwlock_rdlock(3p)
- Man pagepthread_barrier_wait(3p)
- Man pagesem_wait(3)
- Official docsLinux sequence counters and sequential locks
- Official docsUserspace RCU
- PaperMichael and Scott concurrent queue algorithms
Official documentation first. Links checked when the lesson was published.