Low-level designDeep dive9 min

Atomics and memory visibility

An atomic operation reads and changes a value in one indivisible step, and compare-and-set changes it only if it still holds what you saw. Atomics also decide what other threads can see: without them, a write in one thread may never become visible in another.

Watch it evolve1 / 8
The problem

One seat left

Each buyer reads the remaining seats and, if there's one, writes one less.

80
Start
Stage 1
Stage 2
Final

1 · The situation

The last seat at a webinar

A webinar has a fixed number of seats, and many buyers try to book at once, each on its own thread. Booking is "if a seat is left, take it": read the number of remaining seats, and if it's above zero, write one less. One seat is left, and Ana and Ben try at the same moment.

As on Threads and shared state, the first two programs replay one order that real threads can run in, with each buyer's steps split apart, so the output is the same every run.

Check, then actJava
class Buyer {
    private final String name;
    private final SeatCounter seats;
    private int seen;
    private boolean ticket;

    Buyer(String name, SeatCounter seats) {
        this.name = name;
        this.seats = seats;
    }

    void checkStep() {
        seen = seats.read();
        System.out.println(name + " sees " + seen + " seat left");
    }

    void claimStep() {
        if (seen == 0) return;
        seats.write(seen - 1);
        ticket = true;
        System.out.println(name + " takes it and writes " + (seen - 1));
    }

    boolean hasTicket() {
        return ticket;
    }
}

2 · The race

Two tickets for one seat

Both buyers check before either claims:

Ana sees 1 seat left
Ben sees 1 seat left
Ana takes it and writes 0
Ben takes it and writes 0
Tickets sold: 2 for 1 seat

Each buyer's check was true when it was made, and false by the time it was acted on.

This is the check-then-act race. The fault isn't in either step but in the gap between them: a decision made on a value another thread can change before the decision is carried out. A lock around both steps would close the gap. This page is about a lighter tool that works on a single value without a lock.

Ben acts on a value that changed after he read it. Nothing tells him.

3 · The fix

Change it only if it's still what you saw

Compare-and-set, or CAS, is one indivisible operation with three inputs: a location, the value you expect it to hold, and the new value. If the location still holds the expected value, it's replaced and the call succeeds; if anything changed it since you read it, nothing is written and the call fails. A failed buyer reads again and decides again.

SeatCounter.compareAndSet(seen, seen - 1) writes only if the count is still the one the buyer saw. In this replay it stands in for the real atomic, one step at a time.

Java
class SeatCounter {
    private int remaining;

    SeatCounter(int remaining) {
        this.remaining = remaining;
    }

    int get() {
        return remaining;
    }

    boolean compareAndSet(int expected, int value) {
        if (remaining != expected) return false;
        remaining = value;
        return true;
    }
}
SeatCounter− remaining: int~ get(): int~ compareAndSet(int, int): booleanBuyer− name: String− seats: SeatCounter− seen: int− ticket: boolean~ readStep()~ swapStep()~ hasTicket(): boolean
Ana reads 1
Ben reads 1
Ana swaps 1 for 0: claimed
Ben expected 1 but it changed: retry
Ben reads 0
Ben is refused: sold out
Tickets sold: 1 for 1 seat

The same order of steps as before; this time Ben's write is refused because the count changed.

With real threads, eight buyers make 50 attempts each at 100 seats. Exactly 100 tickets are sold, on every run:

Tickets sold: 100 for 100 seats
Refused: 300

4 · The idea

Atomic, and visible

An atomic operation happens all at once from every other thread's point of view: no thread sees it half done, and none can slip in between its parts. Atomic types offer a few such operations on one value: read, write, add, and compare-and-set, from which any other update can be built as a retry loop. Because nothing is locked, a thread that loses a race doesn't wait; it just tries again. This style is called lock-free when, as here, the hardware does the operation without a hidden lock (C++ reports it with is_lock_free()), so some thread always makes progress.

Atomics settle a second question too: visibility. Without synchronization, a compiler or a processor may keep a value in a register or a cache and never re-read it, so a thread can loop forever on a flag another thread already cleared. Languages define when a write must become visible as a happens-before relation. In Java, a write to a volatile field happens before every later read of it, an unlock happens before the next lock of the same lock, and everything a thread does happens before another thread returns from join() on it.

A plain field gives no guarantee that the worker ever sees the change. A volatile or atomic field does.

Language

Atomic value

Makes a write visible

Java

AtomicInteger, AtomicLong, AtomicReference

volatile fields, atomics, locks, start() and join()

C++

std::atomic

Atomic operations and their memory orders, mutexes, thread start and join; volatile does neither job

JavaScript

Atomics operations on a SharedArrayBuffer

Atomics operations; ordinary reads of shared memory have no ordering guarantees

Python

None in the standard library

Locks; the global interpreter lock orders single bytecode steps, not whole operations

5 · What it costs

One value at a time, and retries under contention

Atomics have limits:

  • One value. A CAS covers one location. If booking must also add the buyer to a guest list, the count and the list must change together, and that needs a lock or a different design.
  • Retries under contention. With many threads hitting one value, many swaps fail and are retried; each retry is wasted work. A lock makes threads wait instead; neither is free.
  • Subtle loops. A hand-written CAS loop must re-read on every failure and must not act on a stale value. Prefer the ready-made operations, such as incrementAndGet() or updateAndGet(), where they fit.

Need

Usually

A counter, a flag, or one reference that's swapped

An atomic

Several values that must change together

A lock

Many threads adding to one total

Per-thread counts combined later, or a striped counter such as Java's LongAdder

A flag one thread sets and others read

A volatile field in Java, an atomic bool in C++

6 · Getting it right

Atomics, not volatile, for updates

  • volatile isn't atomic. In Java, volatile int count; count++ is still a read and a write: the field is visible, but two threads can still lose an update.
  • C++ volatile isn't for threads at all. Its accesses aren't atomic and don't order other memory; use std::atomic.
  • Read once per attempt. A CAS loop reads the value, decides on that value, and swaps from that value; reading twice reopens the gap.
  • Don't mix plain and atomic access to the same data. One unguarded read is enough for a stale value.

A swap that succeeds can still be wrong when a value changes and changes back between your read and your swap: the ABA problem. A plain counter doesn't care, since 5 is 5. A lock-free stack that compares pointers can, because the node at the top may have been removed and a different one put back at the same address.

7 · Look-alikes

Optimistic and pessimistic

Compare-and-set is one case of a wider idea.

Idea

How it handles a conflict

Lock (pessimistic)

Prevents it: other threads wait until the holder is done

Compare-and-set (optimistic)

Detects it: the swap fails, and the loser retries

Optimistic locking in a database

The same idea for rows: update where the version is still the one you read, and retry if no row matched

volatile

Doesn't handle conflicts; only makes writes visible

Immutable values

Avoids them: shared data never changes

Optimistic approaches win when conflicts are rare, since nobody waits. Pessimistic ones win when conflicts are common, since retries are wasted work. The webinar's last seat is a rare, short conflict: a good fit for compare-and-set.

8 · In practice

Where atomics show up

Java's atomic package describes itself as a toolkit for lock-free, thread-safe programming on single variables, and its own example is a sequence number generator built on getAndIncrement(). Ids, counters, statistics and "is it shut down yet" flags are the everyday uses.

Concurrent collections are built from the same operations, so most code uses atomics through them. Concurrent collections shows one: a map whose merge() updates a count without any lock in sight.

Check yourself

4 questions

1. A field is volatile int sold; and two threads run sold++. Is the count safe?
2. Ben's compare-and-set fails. What should his code do?
3. Booking must lower the seat count and add the buyer to the guest list together. What's the right tool?
4. Why does the Python version use a lock?

Takeaways

Remember this

  • Check-then-act on shared data is a race: the value can change between the check and the act.
  • Compare-and-set writes only if the value is still what you read; on failure, read again and decide again.
  • A failed compare-and-set retries instead of blocking, which is cheap when conflicts are rare.
  • Visibility is a separate guarantee: without volatile, atomics or locks, a thread may never see another's write.
  • Atomics cover one value; several values that change together need a lock.