Atomic Operations & Compare-and-Swap

Atomic operations are instructions that execute indivisibly — no other thread can observe a partial result. They are the foundation for all synchronization primitives.

Why Atomicity Matters

// Non-atomic: two threads reading/writing simultaneously
counter++;  // Actually: read counter, increment, write counter
            // Thread A reads 5, Thread B reads 5
            // Thread A writes 6, Thread B writes 6
            // Final: 6 (should be 7!)

With an atomic operation:

__sync_fetch_and_add(&counter, 1);  // Guaranteed: final = 7

Compare-and-Swap (CAS)

CAS is the most important atomic primitive. It’s used to build all lock-free data structures.

CAS(address, expected, new):
    if *address == expected:
        *address = new
        return true
    else:
        return false

The key property: CAS succeeds only if the memory hasn’t changed since you last read it. If another thread modified it, CAS fails and you retry.

Lock-Free Increment (using CAS)

void atomic_increment(int *value) {
    int old;
    do {
        old = *value;
    } while (!CAS(value, old, old + 1));
}

If another thread modifies *value between reading old and CAS, the CAS fails and we retry. No lock needed — just a loop.

Other Atomic Operations

Operation	What it does
Test-and-Set (TAS)	Set to 1, return old value
Fetch-and-Add (FAA)	Add value, return old value
Load-Linked / Store-Conditional (LL/SC)	CAS variant, no ABA problem
Exchange	Swap a value atomically

The ABA Problem

Thread 1 reads value A from address
Thread 2 changes A → B → A (back to A, but structure changed)
Thread 1's CAS succeeds — but the world has changed

Solution: Use tagged pointers (ABA counter) or LL/SC instruction.