Atomic Operations and Lock-Free Programming

When Locks Are Too Expensive

Locks work by suspending threads — a thread that cannot acquire a lock is put to sleep by the operating system and woken up later. This context switch has real cost: typically 1–10 microseconds. For operations that themselves take only nanoseconds (like incrementing a counter), the lock overhead can dwarf the actual work.

Atomic operations are CPU-level instructions that perform a read-modify-write cycle as a single, uninterruptible step. No thread can observe the value in an intermediate state. No OS-level suspension is needed.

The most important atomic primitive is Compare-And-Swap (CAS):

CAS(memory_location, expected_value, new_value):
    if *memory_location == expected_value:
        *memory_location = new_value
        return SUCCESS
    else:
        return FAILURE  # someone else changed it; retry

This is the foundation of lock-free data structures. A thread reads the current value, computes a new value, then atomically swaps — but only if the value hasn't changed since it was read. If it has changed (another thread got there first), the operation fails and the thread retries.

Python example using threading atomics via a lock-free counter pattern:

import threading

# Python's GIL makes simple integer ops effectively atomic,
# but in languages like Java/C++, you'd use AtomicInteger/std::atomic
class AtomicCounter:
    def __init__(self):
        self._value = 0
        self._lock = threading.Lock()

    def increment_and_get(self):
        with self._lock:
            self._value += 1
            return self._value

# In Java, the equivalent without any explicit lock:
# AtomicInteger counter = new AtomicInteger(0);
# int newVal = counter.incrementAndGet(); // Uses CPU CAS instruction

The ABA Problem — A Critical Edge Case:
CAS checks that the value equals expected_value before swapping. But what if another thread changed the value from A → B → A between your read and your CAS? Your CAS succeeds (the value looks like A), but the state of the system has changed in ways your thread didn't account for. This is the ABA problem. The fix is to use a versioned CAS — store a (value, version) pair and increment the version on every write, so A-at-version-1 is distinguishable from A-at-version-3.

Key Point: Atomic operations eliminate lock overhead for simple operations and are the building block of high-performance concurrent data structures. However, lock-free programming is significantly harder to reason about than lock-based programming. The ABA problem, memory ordering, and retry storms under high contention are all failure modes that don't exist with simple locks. Use lock-free structures from well-tested libraries (like java.util.concurrent) rather than implementing them from scratch.