Locks, Mutexes, and Lock-Free Data Structures

Concurrency bugs begin when an operation that looks indivisible in source code becomes several machine actions. Consider balance += amount: a processor loads balance, computes a new value, and stores it. If two threads overlap those steps, both can read the same old balance and one update disappears. The arithmetic is correct; the interleaving is not.

Locks and atomic operations both constrain interleavings, but they make different promises. A mutex grants temporary exclusive ownership of a region of state. A compare-and-swap (CAS) operation changes one machine word only if it still contains an expected value. Lock-free algorithms compose such conditional changes so that the system keeps progressing even when an individual thread pauses.

None of these mechanisms is automatically faster or safer. A small mutex-protected state can be easier to prove and faster than a sophisticated CAS loop. Conversely, a thread holding a lock at the wrong moment can stall every peer. The useful question is not “Are locks bad?” It is “Which synchronization contract matches this state, workload, and failure model?”

Races are failures of ordering, not merely timing #

A data race occurs when concurrent accesses target the same memory, at least one access is a write, and the accesses are not synchronized. In Rust, safe code prevents data races through ownership and Send/Sync; in C++, a data race on ordinary memory is undefined behavior. A race condition is broader: the program’s result depends on an unfortunate order, even when every individual access is atomic.

For example, two atomic operations do not make a compound check-then-act operation atomic:

use std::sync::atomic::{AtomicUsize, Ordering};

fn reserve_one(remaining: &AtomicUsize) -> bool {
    let mut observed = remaining.load(Ordering::Relaxed);

    loop {
        if observed == 0 {
            return false;
        }

        match remaining.compare_exchange_weak(
            observed,
            observed - 1,
            Ordering::AcqRel,
            Ordering::Relaxed,
        ) {
            Ok(_) => return true,
            Err(actual) => observed = actual,
        }
    }
}

A separate load, test, and store would oversell the last slot. The CAS loop instead says, “store observed - 1 only if nobody changed the value after I observed it.” Spurious failure is allowed for compare_exchange_weak, so a loop is mandatory. A real competing update also fails the CAS and supplies the current value for the next attempt.

Atomicity solves only part of the problem. Threads also need visibility and ordering: when one thread publishes a pointer, another thread that observes it must also observe the initialized object behind it. That relationship is the job of the language memory model, not wall-clock intuition or the fact that a test passed on one laptop.

Mutexes make invariants explicit #

A mutex is often the best default when several fields form one invariant. Instead of making each field atomic and reasoning about every intermediate combination, put the state behind one lock and update it as a transaction.

use std::collections::HashMap;
use std::sync::Mutex;

struct Ledger {
    balances: Mutex<HashMap<String, i64>>,
}

impl Ledger {
    fn transfer(&self, from: &str, to: &str, amount: i64) -> Result<(), &'static str> {
        if amount < 0 {
            return Err("amount must be non-negative");
        }

        let mut balances = self.balances.lock().map_err(|_| "ledger lock poisoned")?;
        let from_balance = *balances.get(from).unwrap_or(&0);
        if from_balance < amount {
            return Err("insufficient funds");
        }

        *balances.entry(from.to_owned()).or_default() -= amount;
        *balances.entry(to.to_owned()).or_default() += amount;
        Ok(())
    }
}

The guard’s lifetime defines the critical section, and dropping it unlocks the mutex even on an early return. More importantly, no observer can see money removed from one account but not yet added to the other. That invariant is much clearer than a pair of atomic balances.

Keep critical sections bounded: do not perform network calls, wait for user input, or invoke unknown callbacks while holding a lock. Approximate lock cost as

The uncontended fast path may be tiny, while queueing and scheduler handoffs dominate under contention. Measure the tail, not just average lock acquisition time.

Locks introduce liveness hazards:

Deadlock needs four ingredients: mutual exclusion, hold-and-wait, no forced preemption, and a circular wait. Breaking any one prevents it. A global ordering such as “always acquire account locks by account ID” is usually easier to audit than timeouts, which detect delay but do not restore a half-completed invariant.

CAS and memory ordering define publication #

CAS compares an atomic value with an expected value and conditionally replaces it as one indivisible operation. It is the foundation of counters, state machines, free lists, and many concurrent queues. The difficult part is rarely the instruction itself; it is choosing what surrounding memory the operation publishes.

The common orderings are:

Suppose a producer fully initializes a node and then stores its pointer with Release. A consumer loads that pointer with Acquire. If it observes the producer’s pointer, initialization happens-before the consumer’s reads. Relaxed is sufficient for independent statistics counters, but not for publishing an object whose ordinary fields another thread will read.

CAS loops also create a performance tax. With $N$ contenders, a successful update can invalidate cache lines held by roughly $N - 1$ peers. The useful throughput is bounded not just by instruction latency but by cache-coherence traffic:

Counting attempts as operations hides retry amplification. Track successes, failed CAS attempts, and latency percentiles separately.

A lock-free stack still needs safe reclamation #

Treiber’s stack represents the stack as an atomic pointer to an immutable linked list. Push links a new node to the observed head, then CASes the head. Pop reads the head and its successor, then CASes the successor into the head. Here is a compact Rust version using epoch-based reclamation from crossbeam-epoch; T: Copy keeps the example focused on synchronization rather than moving values out of retired nodes.

use crossbeam_epoch::{self as epoch, Atomic, Owned};
use std::sync::atomic::Ordering::{Acquire, AcqRel, Relaxed, Release};

struct Node<T> {
    value: T,
    next: Atomic<Node<T>>,
}

struct Stack<T> {
    head: Atomic<Node<T>>,
}

impl<T: Copy> Stack<T> {
    fn push(&self, value: T) {
        let guard = &epoch::pin();
        let mut new = Owned::new(Node {
            value,
            next: Atomic::null(),
        });

        loop {
            let head = self.head.load(Acquire, guard);
            new.next.store(head, Relaxed);

            match self.head.compare_exchange(head, new, Release, Relaxed, guard) {
                Ok(_) => return,
                Err(error) => new = error.new,
            }
        }
    }

    fn pop(&self) -> Option<T> {
        let guard = &epoch::pin();

        loop {
            let head = self.head.load(Acquire, guard);
            let node = unsafe { head.as_ref()? };
            let next = node.next.load(Relaxed, guard);

            if self
                .head
                .compare_exchange(head, next, AcqRel, Acquire, guard)
                .is_ok()
            {
                let value = node.value;
                unsafe { guard.defer_destroy(head) };
                return Some(value);
            }
        }
    }
}

This is lock-free, not wait-free. If a thread stops midway through push, another thread can still complete an operation. Under contention, however, one unlucky thread may lose the CAS forever. Lock-free guarantees system-wide progress; wait-free guarantees every operation finishes in a bounded number of its own steps. Obstruction-free is weaker: a thread finishes only if it eventually runs without interference.

The unsafe-looking detail is memory reclamation. Immediately freeing a popped node would let another thread dereference memory it read just before the pop. Epoch pinning announces that the current thread may still hold shared pointers. defer_destroy retires the node and destroys it only after no participant can hold a reference from the old epoch.

Reclamation also addresses the ABA problem. A thread reads head address A and pauses. Other threads change A to B, remove B, free A, and later allocate a new node at address A. A pointer-only CAS sees A again and falsely concludes that nothing changed. Epoch reclamation prevents A’s storage from being reused while the paused thread is pinned. Other strategies include hazard pointers, tagged/versioned pointers, reference counting, and garbage collection. Each changes memory overhead, latency, and implementation complexity.

Lock-free does not mean lockless at every layer. An allocator, epoch manager, or atomic type may internally synchronize, and not every target implements every atomic width without a fallback. Check platform guarantees such as is_lock_free, library documentation, and generated behavior for the deployed architecture.

Contention, testing, and the engineering decision #

Synchronization choice should follow shared-state shape and measured contention. Sharding a map across multiple mutexes often beats replacing it with a custom lock-free table. Per-thread counters aggregated periodically avoid a hot atomic cache line. Message passing can give one task exclusive ownership and remove shared mutation entirely. Reducing synchronization demand is usually more valuable than optimizing a primitive.

Test both safety and liveness. Unit tests should verify sequential semantics first. Stress tests then run many randomized operations with barriers that force simultaneous starts, small capacities that cause wraparound, and enough duration to expose rare schedules. Record an operation history and use linearizability checking for a queue, stack, or register: each result must fit some legal sequential order between its invocation and response.

Thread sanitizers catch data races in supported native builds, while tools such as Loom explore bounded Rust interleavings using instrumented atomics and synchronization. Neither proves arbitrary production code. Add watchdogs for stalled progress, run on weakly ordered hardware when relevant, inject pauses between load and CAS, and test shutdown and cancellation paths. Benchmarks need varying thread counts, read/write ratios, preemption, NUMA placement, and realistic work inside the critical section.

A practical review asks: What invariant is protected? Where is the linearization point? Which operation publishes data? Can a thread block, and while holding what? Who reclaims removed memory? What progress guarantee does the product actually require? What happens during cancellation, panic, or overload? If these answers are vague, a clever benchmark is not enough evidence to ship the algorithm.

Takeaways #

• A race is an ordering defect. Atomics prevent torn or conflicting accesses, but compound invariants still need an explicit protocol.
• Mutexes are a strong default for related state: keep the critical section short, establish a lock order, and account for deadlock, livelock, and starvation.
• Acquire/release ordering connects publication with observation; Relaxed is appropriate only when no surrounding-memory relationship is required.
• Lock-free means some operation always progresses; wait-free means every operation completes within a bounded number of its own steps.
• A CAS-based container is incomplete without an ABA and reclamation strategy such as epochs or hazard pointers.
• Optimize the ownership model and contention topology before replacing a clear lock with a difficult non-blocking algorithm, then validate safety and liveness under hostile schedules.