Atomic Operation

Atomic Operations — CPU-level operations that execute as a single indivisible step, ensuring no other thread can observe a partial result. Foundation of lock-free programming.

Key Atomic Operations

• Load/Store: Read or write a value atomically
• Fetch-and-Add: Atomically increment and return old value
• Compare-and-Swap (CAS): If value == expected, replace with new value. Returns success/failure
• Test-and-Set: Set a flag and return old value (used for spinlocks)

CAS Pattern (most important)

do {
    old = atomic_load(&counter);
    new = old + 1;
} while (!CAS(&counter, old, new));  // retry if another thread changed it

Lock-Free Data Structures

• Lock-free stack (Treiber stack): Push/pop using CAS on head pointer
• Lock-free queue (Michael-Scott): CAS on head and tail pointers
• Lock-free hash map: Per-bucket CAS
• Guarantee: Some thread always makes progress (no deadlock possible)

ABA Problem

• CAS succeeds even if value changed from A→B→A
• Fix: Tagged pointers (add version counter)

Performance

• Atomic operation: ~10-100ns (much faster than mutex lock/unlock ~25-100ns)
• But: Heavy contention causes cache line bouncing between cores

Atomic operations enable the highest-performance concurrent algorithms, but correctness is extremely difficult to verify.