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.