compare-and-swap and fetch-and-add
Two atomic operations do most of the heavy lifting in lock-free code. The first, fetch-and-add, is the simple one: atomically add a value to a variable and return what was there before, all in one indivisible step. It is exactly what you want for a shared counter — every thread's increment lands, none is lost, with no lock. The second, compare-and-swap (CAS), is the clever one and the cornerstone of nearly all lock-free algorithms.
Compare-and-swap takes three things: a memory location, an expected value, and a new value. Atomically, it checks 'does the location still hold the expected value? If yes, replace it with the new value and report success; if no, change nothing and report failure (usually returning the value it actually found).' The power is in the 'if it has not changed' part: a thread reads the current value, computes what the new value should be, then uses CAS to install the new value only if no other thread has modified the location in the meantime. If another thread snuck in, the CAS fails, and you loop: re-read, re-compute, re-try. This read-compute-CAS-retry loop is the heartbeat of optimistic concurrency — you assume no conflict, and CAS catches you if you are wrong. Fetch-and-add can be seen as a specialised, always-succeeding sibling for the pure-addition case.
These two primitives are why lock-free programming is possible at all: instead of taking a lock to make a change safely, a thread prepares the change and atomically commits it with CAS only if the world has not shifted under it. They are single CPU instructions on modern hardware (cmpxchg on x86, load-linked/store-conditional pairs on ARM and others). One subtle hazard to name honestly: the ABA problem — between your read and your CAS, the value might change from A to B and back to A, so CAS sees the expected A and succeeds even though the world really did change underneath. Real lock-free code guards against ABA with version tags or hazard pointers; the full treatment belongs to lock-free programming in Volume II.
A lock-free push onto a stack: do { old = head; node->next = old; } while (!atomic_compare_exchange(&head, &old, node)); — the CAS installs node as the new head only if head is still old; if another thread changed head, it loops and retries.
CAS commits a change only if nothing moved since you read; loop and retry when it did.
CAS can suffer the ABA problem: a value changing A->B->A makes a stale CAS succeed even though the data structure really changed underneath. Also, a CAS-retry loop is not wait-free — under heavy contention a thread can retry many times, so CAS is not automatically faster than a mutex.