Atomicity

In ancient Greek philosophy, atomos meant 'indivisible'—the smallest unit of matter that could not be further divided. In computing, we've borrowed this concept for perhaps the most fundamental property in concurrent programming: atomicity.

An atomic operation is one that appears to happen instantaneously and completely—or not at all. There is no intermediate state visible to other threads. Consider incrementing a counter:

counter = counter + 1;

This is not atomic on most hardware. It's actually three operations:

1. Load counter from memory into a register
2. Add 1 to the register
3. Store the result back to memory

Another thread could read counter between any of these steps, seeing an intermediate state. This is the root cause of lost updates and data corruption.

Atomic operations eliminate this problem entirely. An atomic increment is indivisible—other threads see only the before-state or the after-state, never an in-between.

Atomicity is the property of an operation appearing to occur instantaneously and indivisibly with respect to all other concurrent operations.

More formally:

An operation is atomic if it appears to all observers (other threads, processors, or systems) as if it:

1. Occurs at a single, distinct point in time
2. Either completes entirely or does not occur at all
3. Cannot be observed in any intermediate state

The 'All-or-Nothing' Principle:

Atomic operations have no partial completion. Either:

• The entire operation completes and its effects are visible, or
• The operation has no effect whatsoever

There is no scenario where 'half' of an atomic operation is visible.

Atomicity vs. Instantaneity:

An atomic operation doesn't actually happen instantly—CPUs take time. What matters is that no other operation can observe the 'during' phase. From any external viewpoint, the operation transitions from 'not started' to 'complete' with nothing in between.

Examples of atomic vs. non-atomic operations:

*Even simple writes may not be atomic if misaligned or if the C standard is strictly followed (where no guarantees exist without explicit atomics).

Modern CPUs provide special instructions that are guaranteed atomic. These are the building blocks on which all higher-level synchronization is built.

1. Atomic Load and Store

Reading or writing a naturally-aligned, word-sized value is typically atomic on modern CPUs. However, the C/C++ standards don't guarantee this, so explicit atomic types should be used for portability.

2. Test-and-Set (TAS)

Atomically sets a memory location to a value and returns the old value:

TAS(addr): old = *addr; *addr = 1; return old;  // Atomic

3. Compare-and-Swap (CAS) / Compare-and-Exchange (CMPXCHG)

Atomically compares a memory location with an expected value; if they match, updates to a new value:

CAS(addr, expected, new):
    if (*addr == expected) {
        *addr = new;
        return true;  // Success
    }
    return false;     // Failure

This is the most powerful and widely-used atomic primitive.

4. Fetch-and-Add (FAA) / Atomic Increment

Atomically adds a value and returns the previous value:

FAA(addr, val): old = *addr; *addr = old + val; return old;  // Atomic

5. Load-Linked/Store-Conditional (LL/SC)

Used on ARM, PowerPC, RISC-V instead of CAS:

• LL (Load-Linked): Reads a value and sets a 'reservation'
• SC (Store-Conditional): Writes a value only if the reservation is still valid

If anything modified the location since LL, the SC fails. This is more general than CAS (avoids ABA problem) but requires a retry loop.

How hardware implements atomicity:

For single-location operations:

• The CPU's cache coherence protocol ensures exclusive access during the operation
• On x86: the LOCK prefix forces cache line lock or bus lock
• The operation completes before any other CPU can access that cache line

For multi-location operations:

• Hardware doesn't provide multi-location atomicity
• Software must use locks or complex lock-free algorithms
• Intel's TSX (Transactional Synchronization Extensions) was an attempt, but has been retired due to security issues

A crucial distinction that many developers miss: atomicity and synchronization are different concepts that often work together but solve different problems.

Atomicity ensures that an operation is indivisible—no partial states are visible.

Synchronization (memory ordering) ensures that operations occur in a predictable order visible to all threads.

You can have one without the other:

Atomic without ordering (memory_order_relaxed):

atomic_fetch_add_explicit(&counter, 1, memory_order_relaxed);

The increment itself is atomic (no lost updates), but there's no guarantee about when or in what order it becomes visible relative to other operations. Other threads may see this increment before or after surrounding non-atomic operations, in unpredictable order.

Ordering without atomicity:

Conceptually possible but not useful—memory barriers order operations, but if the operations themselves aren't atomic, you still get races.

Combined atomicity + ordering (the common case):

atomic_store_explicit(&ready, 1, memory_order_release);

The store is atomic AND provides release semantics (all prior operations are visible before this store becomes visible to other threads).

When to use relaxed atomics:

• Statistics counters — You don't care about ordering, just that increments aren't lost
• Sequence numbers — Each thread gets a unique value, order doesn't matter
• Fast paths with later synchronization — The relaxed operation is 'fixed up' later by a synchronized operation

When you need full synchronization:

• Publication patterns — Writer must use release, reader must use acquire, to ensure data is visible
• Lock implementations — Acquire/release semantics are essential for locks
• Ordered communication — When threads must observe events in a specific order

Modern programming languages provide atomic types that map to hardware atomic operations:

C11 Atomics:

#include <stdatomic.h>

atomic_int counter;                    // Atomic integer
atomic_flag lock = ATOMIC_FLAG_INIT;   // Atomic boolean (spinlock primitive)
_Atomic(struct Point) point;           // Any type can be atomic

C++11 Atomics:

#include <atomic>

std::atomic<int> counter{0};
std::atomic<bool> flag{false};
std::atomic<T> value;  // Any trivially copyable type

Java Atomics:

import java.util.concurrent.atomic.*;

AtomicInteger counter = new AtomicInteger(0);
AtomicReference<Node> head = new AtomicReference<>();
AtomicLong timestamp = new AtomicLong();

Go sync/atomic:

import "sync/atomic"

var counter int64
atomic.AddInt64(&counter, 1)
atomic.LoadInt64(&counter)

One of the most subtle bugs in lock-free programming is the ABA problem, which can occur when using compare-and-swap.

The scenario:

1. Thread 1 reads value A from location X
2. Thread 1 is preempted
3. Thread 2 changes X from A to B
4. Thread 2 changes X from B back to A
5. Thread 1 resumes, performs CAS(X, A, C)
6. CAS succeeds! (X is A, matches expected)

Why this is a problem:

Thread 1's CAS succeeded, but the world has changed since it read A. If A was a pointer and Thread 2 freed and reallocated memory, Thread 1 might now be pointing to completely different data. The 'A' value is the same, but its meaning has changed.

Classic example: lock-free stack

Solutions to the ABA problem:

1. Double-width CAS with version counter:

Instead of CAS on just the pointer, CAS on (pointer, version). Increment version on every modification. Even if the pointer returns to A, the version is different.

struct TaggedPointer {
    Node* ptr;
    uint64_t version;
};
// Use 128-bit CAS (cmpxchg16b on x86-64)

2. Hazard pointers:

Before accessing a node, publish a 'hazard pointer' to it. Other threads check hazard pointers before freeing, deferring reclamation if the node is protected.

3. Epoch-based reclamation:

Track 'epochs' of execution. Defer freeing until all threads have passed through a grace period, ensuring no thread holds old references.

4. LL/SC instead of CAS:

Load-Linked/Store-Conditional (on ARM, PowerPC) naturally avoids ABA because SC fails if any write occurred, not just if the value differs.

Atomic operations are the foundation on which locks are built. Let's see how a simple spinlock works:

Basic spinlock with TAS:

atomic_flag lock = ATOMIC_FLAG_INIT;

void acquire() {
    while (atomic_flag_test_and_set(&lock)) {
        // Spin until we acquire the lock
    }
}

void release() {
    atomic_flag_clear(&lock);
}

How it works:

• atomic_flag_test_and_set atomically sets the flag to true and returns the old value
• If old value was false, we acquired the lock (we just set it)
• If old value was true, someone else has the lock—spin and retry
• atomic_flag_clear atomically sets the flag to false, releasing the lock

Better spinlock with CAS:

From spinlock to blocking lock:

Production-quality mutexes add blocking:

1. Attempt to acquire with atomic operation
2. If failure, spin briefly (optimistic—lock may release soon)
3. If still locked, add to wait queue and sleep
4. Upon unlock, the releasing thread wakes a waiter

This combines the low-latency of spinning (for short critical sections) with the efficiency of blocking (for longer waits). This is what pthread_mutex and std::mutex typically implement.

Hardware atomics operate on single memory locations. What about operations that must atomically update multiple values?

The challenge:

Consider transfer between accounts:

accounts[from] -= amount;  // Must be atomic with next line
accounts[to] += amount;    // Together, or neither

No single atomic instruction can update two separate memory locations atomically.

Solution 1: Locks

The straightforward solution—acquire a lock covering both locations:

lock(&accounts_lock);
accounts[from] -= amount;
accounts[to] += amount;
unlock(&accounts_lock);

Solution 2: Two-phase locking

For finer granularity, lock both accounts:

lock(&locks[from]); lock(&locks[to]);  // Lock ordering to prevent deadlock
// ... perform transfer ...
unlock(&locks[to]); unlock(&locks[from]);

Solution 3: Software Transactional Memory (STM)

Log changes, commit atomically at end:

atomic {
    accounts[from] -= amount;
    accounts[to] += amount;
}  // Commits all changes atomically or retries

Solution 4: Lock-free with CAS (complex)

For specific data structures, clever algorithms can achieve multi-location atomicity:

• Mark-and-sweep: mark locations as 'being modified', complete update, unmark
• Helping: if a thread sees an in-progress operation, it helps complete it
• Double-CAS: some specialized hardware supports CAS on two locations

These are advanced techniques used in lock-free queues, skip lists, and other specialized structures.

Database Transactions:

Databases provide atomic transactions through:

• Write-Ahead Logging (WAL): log all changes before applying
• Two-Phase Commit (2PC): prepare all participants, then commit all at once
• Multi-Version Concurrency Control (MVCC): each transaction sees a consistent snapshot