Atomic Operations and Memory Ordering

The previous lesson measured how the side waiting on a mutex advances: the lock holder on its own, the waiter when something else finishes. This lesson’s question is: does every kind of sharing require a waiting side? The answer is no — simple forms of sharing that satisfy a specific condition can be updated safely with no one waiting at all, through the hardware’s own guarantee. This is this topic’s last lesson, and it measures lock-free progress directly.

This condition is narrow: only simple values that fit into a single machine word (integers, booleans, pointer-width numbers) can be updated atomically. A struct carrying more than one field, like the SharedRecord seen in earlier lessons, or a list that grows on the heap, like the one in the Message Passing with Channels lesson, cannot be updated with a single atomic operation — data of that shape still needs a lock. The lock-free progress this lesson measures is therefore a narrow but significant special case: the shared update of a single number, a single flag, a single pointer.

The Hardware’s Single-Step Guarantee

The Operating System Concepts course and the JVM, Concurrency and Performance course both spoke of hardware primitives like compare-and-swap; that concept is not established again here. An atomic operation is a read-modify-write sequence the processor carries out in a single indivisible step: incrementing a counter by one, even if two threads attempt it at the same instant, never produces a result that is half-finished or overwritten. A mutex achieves the same result, but by a different route — it makes everyone but the single lock holder wait. An atomic operation makes no one wait at all; the hardware itself queues two simultaneous requests and processes both without loss.

Seeing why this guarantee is necessary only requires looking at why an unprotected increment gives the wrong result. Incrementing an integer by one is actually three separate steps: read the current value, add one, write the result back. If two threads attempt these three steps at the same time, unprotected, both can read the same old value, both can write their own newly computed value — and whichever writes last overwrites the other’s increment. The result is that, despite two increments having taken place, the counter has advanced by only one; this is a direct consequence of a data race. An atomic operation makes this overwrite impossible by turning these three steps into a single indivisible unit at the hardware level — no other thread can step in between the read, the add, and the write.

This difference has a counterpart in the measurement: of ten threads incrementing a counter protected by a mutex, nine of them may, at any given moment, be waiting while the tenth holds the lock — they fall into the when-something-else-finishes class. None of the ten threads incrementing an atomic counter enter such a wait; all of them stay in the on-its-own class. The measurement below shows this difference by comparing the result the two methods produce: both produce the same total, because both run with no lost update — what differs is only how they achieve it.

The Send/Sync framework established in the Thread Safety in the Type System lesson holds here too: the AtomicUsize type is both Send and Sync, so Arc<AtomicUsize> can be shared among more than one thread. This is the same pair of permissions Arc<Mutex<usize>> carries — the difference is that Mutex carries a lock inside itself, while AtomicUsize carries no lock at all, relying directly on the hardware’s indivisible operations. Both are an instance of the same permission in the type system, but the way they provide the guarantee differs.

Two Methods, Same Result

The program below defines two functions and runs both from main with the same constants: ten threads, each incrementing five hundred times. lock_and_count does this with the familiar Arc<Mutex<usize>> arrangement — every increment requests a handle, and the lock is released once the handle goes out of scope. atomic_count performs the same job with Arc<AtomicUsize>; there is no handle here, only a single call named fetch_add, and that call performs both the read and the write internally, in one indivisible step. Both functions have the same return type (usize), so their results can be compared directly.

// atomic.rs — a lock-free counter advances without waiting; increment order is not measured, only the total.

use std::sync::atomic::{AtomicUsize, Ordering};
use std::sync::{Arc, Mutex};
use std::thread;

const THREAD_COUNT: usize = 10;
const INCREMENTS: usize = 500;

fn lock_and_count() -> usize {
    let counter = Arc::new(Mutex::new(0usize));
    let mut handles = Vec::new();
    for _ in 0..THREAD_COUNT {
        let s = Arc::clone(&counter);
        handles.push(thread::spawn(move || {
            for _ in 0..INCREMENTS {
                // every increment requests the lock: a waiting thread advances when something else finishes
                let mut value = s.lock().unwrap();
                *value += 1;
            }
        }));
    }
    for t in handles {
        t.join().unwrap();
    }
    let result = *counter.lock().unwrap();
    result
}

fn atomic_count() -> usize {
    let counter = Arc::new(AtomicUsize::new(0));
    let mut handles = Vec::new();
    for _ in 0..THREAD_COUNT {
        let s = Arc::clone(&counter);
        handles.push(thread::spawn(move || {
            for _ in 0..INCREMENTS {
                // no thread waits on a lock: every increment advances on its own
                s.fetch_add(1, Ordering::SeqCst);
            }
        }));
    }
    for t in handles {
        t.join().unwrap();
    }
    counter.load(Ordering::SeqCst)
}

fn main() {
    let locked_result = lock_and_count();
    let atomic_result = atomic_count();
    let expected = THREAD_COUNT * INCREMENTS;

    println!("expected total: {}", expected);
    println!("locked total: {}", locked_result);
    println!("atomic total: {}", atomic_result);
    println!(
        "both methods gave the same result: {}",
        locked_result == atomic_result && atomic_result == expected
    );

    // --- two atomic counters: which increment happens first is not measured, only the final total ---
    let a = Arc::new(AtomicUsize::new(0));
    let b = Arc::new(AtomicUsize::new(0));
    let mut handles = Vec::new();
    for i in 0..THREAD_COUNT {
        let (a, b) = (Arc::clone(&a), Arc::clone(&b));
        handles.push(thread::spawn(move || {
            if i % 2 == 0 {
                a.fetch_add(1, Ordering::SeqCst);
            } else {
                b.fetch_add(1, Ordering::SeqCst);
            }
        }));
    }
    for t in handles {
        t.join().unwrap();
    }
    let pair_total = a.load(Ordering::SeqCst) + b.load(Ordering::SeqCst);
    println!();
    println!("total of the two separate atomic counters: {}", pair_total);
    println!("(which thread incremented which counter first is not printed)");
}

expected total: 5000
locked total: 5000
atomic total: 5000
both methods gave the same result: true

total of the two separate atomic counters: 10
(which thread incremented which counter first is not printed)

TH8. Ten threads, each incrementing five hundred times, increment the same counter five thousand times in total. lock_and_count does this with a mutex: every increment requests a lock call, and nine of the ten threads may be waiting for the lock at any given moment — a mechanism that falls into the when-something-else-finishes class. atomic_count performs the same five thousand increments with a fetch_add call: no thread needs a lock, all of them stay in the on-its-own class. Both methods produce the expected total (5000), and this result comes out identical across three separate runs — there is no lost-update difference between the locked and the atomic counter.

The structure of the two functions makes this visible too: the loop body inside lock_and_count takes a Mutex handle, changes the value, and releases the handle — these three steps repeat on every increment. The loop body inside atomic_count, by contrast, only calls fetch_add; no handle is taken and none is explicitly released, because the AtomicUsize type itself carries no lock. Both functions using the same number of threads, the same number of increments, and being compared against the same expected constant keeps the method as the single variable — any difference in the result would come from being locked or not, from no other variable.

Order Is Not Measured, Only the Total

The program’s second part uses two separate atomic counters: even-numbered threads increment counter a, odd-numbered threads increment counter b. The order in which the ten threads run, which one calls fetch_add first, is never measured or printed anywhere in this program — only the two counters’ final total (10) is printed. This shows that the rule established in the Thread Creation lesson holds here too: no observation that depends on timing is printed, only what is deterministic — in this example, how many threads are even- or odd-numbered, and therefore what the final total will be — is printed.

The purpose of this second measurement is to show, by using two separate counters instead of one, that the answer to the question “which thread ran first” does not change the program’s output. The order in which the scheduler runs the ten threads can differ on every run — since the THREAD_COUNT constant is ten in this program, five of them write to counter a and five to counter b, and the total of the two counters is always ten. This total does not change even if the timing changes, because the i % 2 computation depends on the thread’s number, not on its running order. This is another example showing the difference between the result of a computation and the order of the operations that produced it.

The Limits of the Measurement

Being atomic does not mean being ordered. The Ordering::SeqCst used in this lesson guarantees that the operation itself is indivisible — no thread ever sees a half-finished increment — but which increment happens before another is never determined anywhere in this run, and cannot be: ten threads run at the same time, and the order in which the scheduler grants them their share of the processor depends on the environment. The only thing measured is that none of the five thousand increments is lost — that the final total is exactly equal to the expected number. The question of which thread performed which increment at which moment is never measured anywhere, under this course’s determinism rule.

Memory ordering itself — Ordering::SeqCst, Ordering::Relaxed, and the options between them — is explained in this lesson as a concept, not measured, because it cannot be measured: the difference between one ordering option and another shows up in a multi-processor hardware’s own cache-coherence behavior, and that behavior can vary from run to run, and even from call to call within the same run. SeqCst is the strongest and easiest-to-reason-about option: every thread behaves as if it sees every atomic operation in the same global order. Weaker options (like Relaxed) guarantee only the indivisibility of a single variable, not the order in which operations become visible to each other — this difference matters when a relationship needs to be established between two different atomic variables, but it stays invisible in the single-counter scenario used in this lesson.

Why SeqCst was chosen is also part of this boundary. This lesson increments a single atomic variable (and, in the second measurement, two atomic variables independent of each other); no scenario is built here that observes whether a read on one atomic variable appears before or after a write on another. Had such a scenario been built, the chosen ordering option could have affected the result, and that difference would have shown up only on particular processor architectures, in particular cache states — that is, it would have been an environment-dependent observation. Under this course’s rule, no such observation is ever built; SeqCst was chosen because it is the safest option, and for the one thing this lesson measures — the correctness of the total — no ordering option would have given a different result from another.

Summary

• An atomic operation is a read-modify-write sequence the hardware carries out in a single indivisible step; this is what lets a lock-free counter advance on its own, needing no one.
• The same five thousand increments, performed with both the locked and the atomic method, produce exactly the same total (5000); the difference is not in the result but in a waiting side existing in the locked counter and not existing at all in the atomic one.
• In a locked counter, threads can enter the when-something-else-finishes class by waiting for the lock; in an atomic counter, no thread waits on anyone, all of them advance on their own.
• Being atomic is not being ordered: which increment happens first is never measured or printed in this course; what is measured is only the correctness of the final total.
• Memory ordering options are explained as a concept and not measured by running the program, because the difference between them depends on the hardware’s cache behavior, and that behavior is never printed.
• Lock-free progress depends on a narrow condition: only simple values that fit into a single machine word can be updated atomically; a struct carrying more than one field still needs a lock.

Next Step

Throughout this topic’s five lessons, the units measured fell into three of the course’s four classes: independent threads advancing on their own — the lock-free counters seen in this lesson belong to this class too —, sides waiting for something else to finish, and units written in the source that never advanced at all. Every unit that advanced rested on a shared assumption: once started, a thread is carried forward by the operating system’s scheduler — the programmer only determines when it will wait, not the advancing itself. The fourth class, when polled, was never seen in this topic.

The Asynchronous Programming topic reverses this assumption. A task written in the source stands as a lazy value that never advances on its own, bound to no thread — unlike a thread, a task does nothing the moment it is created. The next lesson measures this difference directly: of two tasks built from the same source, one is handed to an executor and advances, the other is withheld and produces no record — even though their sources are exactly identical.