Concurrency Primitives Primer

Concurrency bugs share three root causes:

• Race conditions — the outcome depends on the interleaving of thread schedules. Classic: x++ on a shared counter is load → add → store, and two threads racing produce a counter that's less than the number of increments because their reads / writes interleaved.
• Atomicity violations — an operation that looks like one step but actually isn't. A check-then-act ("if (cache.contains(k)) cache.get(k)") can have an eviction happen between the check and the act. Most concurrency bugs are atomicity bugs hiding behind the language's expressive abstractions.
• Memory-visibility issues — one thread writes a value, another thread reads it later and sees the old value (or a torn intermediate). The cache-coherence primer covers why this can happen at the hardware level; the fix is the memory-ordering mechanism in section 4.

The shared-state problem

Two threads in the same address space (process-thread primer) share every byte of heap and global memory. Without explicit synchronisation, the kernel is free to schedule them in any interleaving — and the CPU is free to reorder their instructions within each thread, as long as the single-threaded program-order is preserved.

Three coping strategies have emerged:

• Avoid sharing. The cleanest approach. Per-thread state, channels for cross-thread communication, immutable data structures. Erlang, Rust (without unsafe), Go (with channels) push this as the default.
• Lock the shared state. Wrap every read and write in a mutex. Easy to write, hard to scale (lock contention), and a different kind of bug emerges (deadlock).
• Lock-free atomics. Use hardware atomic primitives (CAS, fetch-add) to update shared state without locks. Highest throughput, hardest to write correctly. The memory-ordering rules in section 4 are unavoidable here.

Why "just use a mutex" is sometimes wrong

Locks are easy to reason about — one thread at a time inside the critical section. Three failure modes hit them at scale: contention (many threads waiting on the same lock, scheduler thrashing), deadlock (two threads each holding one lock and waiting for the other), priority inversion (low-priority thread holds a lock that a high-priority thread needs). Each has its own mitigation (lock-free, lock ordering, priority-inheritance mutexes), but the fundamental constraint stays: a global lock caps throughput at one critical-section completion per single-CPU latency.

What the kernel can and can't help with

The kernel can suspend a thread (via mutex / condvar / sleep), the kernel can deliver wakeups, the kernel can schedule priorities. The kernel cannot enforce that your code releases locks in the right order, doesn't double-free shared memory, doesn't read a value before another thread writes it. Those are correctness contracts the application owns — and the language runtime can only help so much (Rust's borrow checker is the most aggressive attempt to make some of these compile-time errors).

Mutex

A mutex (mutual exclusion lock) ensures only one thread at a time is inside its critical section. Operations:lock (acquire; block if held by someone else) andunlock (release). Implementations:

• Spinlock — busy-loop until the lock is free. Burns CPU but avoids the syscall cost of going to sleep. Used inside the kernel for short critical sections, or in lock-free libraries for very brief contention.
• Sleeping mutex (pthread_mutex) — try to acquire (often via a spin first); if contended, syscall into the kernel to sleep on a futex (next section). The standard userspace mutex.
• Adaptive mutex — spin a few thousand cycles first, then sleep. Cheap if contention is brief; correct if it isn't.

Mutex contention is the single most common scaling bottleneck. Tools like perf lock, jstack thread-dump analysis, or pprof's mutex profiles identify which lock is hot.

Semaphore

A semaphore is a mutex generalised to N — at most N threads can be inside the critical section at once. Operations:wait (decrement count; block if 0) and signal (increment count; wake a waiter if any). Used for rate-limiting (e.g. only N concurrent connections to a slow service), bounded buffers, and resource pools.

Condition variable

A condvar lets one thread wait for a condition to become true, signalled by another thread. Critically, it always pairs with a mutex — the condvar protocol is:

// waiter
lock(mtx);
while (!condition) {
    cond_wait(cv, mtx);  // atomically releases mtx and sleeps;
                         // reacquires mtx on wake
}
// condition is true here
unlock(mtx);

// signaller
lock(mtx);
make_condition_true();
cond_signal(cv);  // wake one waiter (or cond_broadcast for all)
unlock(mtx);

The while loop on the waiter side is mandatory — spurious wakeups (the waiter wakes without a corresponding signal) are allowed by POSIX, and on multi-waiter cases a different thread may consume the signal's state change before this one gets to check. The classical "wait, check, sleep, recheck" loop is the pattern.

Condvars are how higher-level constructs like Java's BlockingQueue, Go's sync.Cond, or Rust's channels work under the hood.

RWLock

A reader-writer lock allows many concurrent readers OR one exclusive writer. Useful when reads vastly outnumber writes (caches, configuration), but the bookkeeping is more expensive than a plain mutex — and a single writer can be starved by a constant stream of readers (most implementations prefer writers as a fairness measure).

Deadlock

Lock acquisition can deadlock when two threads each hold a lock and need the other's. Classic four conditions (Coffman): mutual exclusion, hold-and-wait, no preemption, circular wait. The standard fix is lock ordering — always acquire locks in a fixed global order. Static analysis tools (clang-tidy, Java's @GuardedBy annotations) catch some cases; runtime detection (gdb's mutex tracker, Java ThreadMXBean) catches others. The cleanest fix is to not nest locks at all.

Hardware atomic operations

CPUs expose a small set of operations that read-modify-write a memory location atomically with respect to other cores. On x86, most are encoded as a normal instruction with a LOCKprefix:

• LOCK XADD — atomic fetch-and-add. Returns the old value, adds. Used for atomic counters.
• LOCK CMPXCHG — atomic compare-and-swap. If memory equals expected, set to new value; return whether the swap happened. The foundation of every lock-free algorithm.
• LOCK BTS / BTR — atomic bit-set / bit-reset. Used in some lock implementations as a lightweight signal.
• MOV with appropriate alignment — naturally aligned 1/2/4/8-byte stores are already atomic on x86 (no LOCK needed), but you still need memory-ordering annotations for visibility to other cores.

ARM uses a different mechanism: LDREX (load-exclusive) reserves a cache line and STREX attempts to write — succeeds only if no other core has touched the line since the LDREX. CAS becomes a small retry loop. ARMv8.1 added direct CASAL / SWPAL instructions as a faster alternative for simple cases.

Cost (cache-coherence primer): uncontended atomic ~10-25 cycles, contended ~100 ns per bounce. Lock-free isn't free.

Futex — the fast userspace mutex

A futex (Fast Userspace muTEX) is a Linux kernel primitive that lets userspace implement locks with minimal kernel involvement. The key insight: if the lock isn't contended, no syscall is needed — just do an atomic compare-and-swap in userspace. Only on contention does the kernel need to put the waiter to sleep.

Futex syscall (futex(addr, op, val, ...)) operations:

• FUTEX_WAIT — "atomically check *addr == val and if so, sleep until woken on this addr." The atomic check prevents the lost-wakeup race.
• FUTEX_WAKE — wake N (typically 1) waiters waiting on this addr.
• FUTEX_REQUEUE — wake some and move others to a different futex. Used by pthread_cond_broadcast to avoid thundering-herd issues.

How pthread_mutex uses futex

A modern pthread_mutex_lock implementation roughly:

int* state;  // 0 = unlocked, 1 = locked, 2 = locked-with-waiters

// fast path: compare-and-swap 0 → 1
if (CAS(state, 0, 1) == 0) return;  // uncontested, done — no syscall

// contended path: mark as locked-with-waiters and sleep
while (true) {
    int v = atomic_exchange(state, 2);  // mark as having waiters
    if (v == 0) return;                 // got it
    futex_wait(state, 2);               // sleep until woken
}

// unlock
if (atomic_exchange(state, 0) == 2) {   // was locked-with-waiters?
    futex_wake(state, 1);                // wake one waiter
}

The fast path is one atomic instruction — no syscall, ~10 ns. The slow path is one futex_wait syscall — ~1 μs. So mutexes are very cheap when uncontended and reasonably cheap when contended; the worst case (lots of threads constantly contending) is dominated by the cost of bouncing the state cache line.

Lock-free data structures

Build a queue / stack / hash table using only atomic primitives instead of locks. Benefits: no thread can be blocked by a slow peer (no deadlock, no priority inversion). Costs: implementing them correctly is famously hard, the ABA problem makes naive CAS loops wrong, and reclaiming memory of removed nodes is its own problem (hazard pointers, epoch-based reclamation, RCU). Java's ConcurrentLinkedQueue, C++ Boost.lockfree, Rust's crossbeam are the production-ready implementations.

Within a single thread, the as-if rule guarantees the program sees its own operations in program order — the compiler can reorder them internally as long as the observable result is the same. Across threads, no such guarantee exists. Thread B reading two values that Thread A wrote may see them in either order, in any interleaving — unless the language and CPU agreed to enforce a specific order.

The four memory orders you need to know

• relaxed — atomicity only, no ordering guarantees. The atomic operation completes as a single step (no torn reads), but the CPU and compiler are free to reorder surrounding operations across it. Used for counters where you only care about the final total, not the order.
• acquire — load barrier. After this load returns, all later operations in this thread are guaranteed to happen after — none are reordered before. Paired with release on another thread.
• release — store barrier. All operations in this thread before the release are guaranteed to be visible to any other thread that acquires the same atomic. None are reordered past the release.
• seq_cst (sequentially consistent) — the strongest and the C++ default. Adds: all seq_cst operations across all threads agree on a single global total order. Stronger than acquire-release for the rare cases where you need it (Peterson's algorithm, some lock-free constructions).

The acquire-release pattern

The producer-consumer scenario is the canonical use:

// producer
data = compute();                   // can be relaxed or non-atomic
flag.store(true, memory_order_release);

// consumer
while (!flag.load(memory_order_acquire)) {}
use(data);                          // sees the data the producer wrote

The release on the producer's store + the acquire on the consumer's load establishes a happens-before relationship: everything the producer did before the release is visible to the consumer after the acquire. This is what every reference-counting, every wait-free signalling, every spsc queue is built on.

Why this varies by architecture

x86 is TSO (Total Store Order): for free, every load is acquire-like and every store is release-like — only store-load reordering across different addresses is allowed. This means "works on x86" lock-free code may break on ARM, which is much weaker. Real example: data; flag = true;in plain C++ works on x86 even without atomics, but on ARM the compiler/CPU can reorder freely, and the consumer may see flag before data.

seq_cst costs extra on x86 (an MFENCE per seq_cst store) and more on ARM (a DMB ISH for both loads and stores). The performance-aware choice is to use the weakest ordering that gives the guarantee you need: relaxed for counters, acquire-release for signalling, seq_cst only when you actually need cross-address global ordering.

The classic mistake

Defaulting to relaxed because "it's faster." Relaxed ordering doesn't establish any happens-before relationship with other operations. Code like counter.fetch_add(1, relaxed) for a per-thread statistic is fine; flag.store(true, relaxed) to signal that data is ready will silently corrupt the consumer's view of data on weakly-ordered hardware. The rule of thumb: if other code depends on what was done before the atomic, you need release; if it depends on what comes after, you need acquire.

Red flags in code review

• Condvar wait without a while loop. POSIX permits spurious wakeups; without the loop, you wake up and act on a state that may not be true.
• memory_order_relaxed used for inter-thread signalling. Works on x86, broken on ARM. Use acquire-release at minimum for anything that establishes a visibility relationship.
• Multiple locks acquired in different orders in different paths. Deadlock waiting to happen. Establish and document a global lock order; assert it with static analysis.
• Holding a mutex across a syscall. If the syscall blocks (read, write, file open, etc.), every other thread wanting the same mutex sits idle. Restructure to do the syscall outside the critical section.
• Hand-rolled lock-free data structures. Always a bug. Use a library (Java's java.util.concurrent, C++ Boost.lockfree, Rust crossbeam) or fall back to a mutex.