Free lesson · Concurrency Interview Mastery
Compare-And-Swap (CAS)
The optimistic-concurrency lesson in Module 4 ended on a promise: that "do the work, commit only if no one interfered, else retry" was the seed of an entire approach to concurrency without locks. This module cashes that promise, and it starts with the primitive that makes it all possible - compare-and-swap. CAS is a single atomic hardware instruction that lets a thread commit a change only if the data hasn't changed since it read it, and from that one capability you can build counters, stacks, queues, and more that are correct under concurrency yet never lock, never block, and never deadlock. Understanding CAS - what it does, how the retry loop works, and what "lock-free" actually guarantees - is the foundation of this whole module and a high-signal interview topic, because lock-free programming is widely considered the deep end of concurrency.
What CAS does
Compare-and-swap is one atomic, indivisible operation with three arguments - a memory location, an expected value, and a new value:
CAS(location, expected, new):
atomically:
if *location == expected:
*location = new
return true // success - we committed our change
else:
return false // failure - someone changed it; we did NOT write
In one uninterruptible step, CAS checks whether the location still holds the value you expected, and only if it does, writes the new value. If another thread changed the location since you read it, the comparison fails and CAS writes nothing, telling you so. The entire check-and-conditionally-write happens atomically - no other thread can sneak in between the compare and the swap. This is the hardware's way of saying "set this to new, but only if no one has touched it since I last looked," which is exactly the optimistic-commit operation from Module 4, delivered as a single instruction.
The key property: CAS lets a thread make a conditional, atomic update that detects interference. Either it succeeds (no one interfered) or it fails (someone did) - and crucially, on failure it changed nothing, so you can safely retry.
The CAS retry loop
A single CAS isn't usually enough - you want to keep trying until you succeed. The CAS retry loop is the fundamental pattern of lock-free programming:
// Lock-free update of a shared value:
loop:
current = atomic_load(location) // read the current value
next = compute(current) // compute the new value (no lock held)
if CAS(location, expected=current, new=next):
break // success - committed atomically
// else: someone changed it between our load and our CAS - loop and retry
Read the current value, compute what you want the new value to be, then CAS it in expecting the value you read. If the CAS succeeds, you committed atomically and you're done. If it fails - because another thread modified the location between your load and your CAS - you loop: read the (now updated) value again, recompute, and retry. No lock is ever held; the thread simply keeps attempting until one attempt lands cleanly. This loop is the skeleton of essentially every lock-free algorithm.
flowchart TD
A["current = load(location)"] --> B["next = compute(current)"]
B --> C{"CAS(location, current, next)?"}
C -->|success: value was still 'current'| D[committed - done]
C -->|failure: someone changed it| A
note1["No lock held anywhere.<br/>Failure just means retry."]
This flowchart shows the compare-and-swap retry loop, the core pattern of lock-free programming. First, the thread loads the current value from the location. Then it computes the new value it wants based on that current value, without holding any lock. Then it attempts a compare-and-swap: write the new value only if the location still equals the current value it read. If the CAS succeeds - meaning no other thread changed the value in between - the change is committed and the thread is done. If the CAS fails - meaning another thread modified the value - the thread loops back, reloads the now-updated value, recomputes, and tries again. No lock is ever held; a failed CAS simply means retry.
Why CAS enables lock-free programming
Here's the conceptual payoff. With a lock, if the thread holding it is delayed - descheduled, paused, slow - every other thread waiting on that lock is blocked, unable to make progress until the holder resumes. The holder's delay stalls everyone. CAS-based code has no such dependency: there's no lock to hold, so no thread can block others by holding something. A thread either successfully CASes its change (and proceeds) or fails and retries (without having blocked anyone). Even if one thread is paused mid-operation, other threads can still complete their CASes and make progress.
This is the essence of lock-free: the system as a whole always makes progress - at any moment, some thread is guaranteed to complete its operation in a bounded number of steps, regardless of what other threads do (even if some are suspended). No single thread's delay can stall the whole system, because there's no lock whose holder everyone waits on. That's a strictly stronger progress guarantee than lock-based code, where a delayed lock-holder halts all waiters.
Progress guarantees: lock-free, wait-free, obstruction-free
"Lock-free" is a precise term, and it sits in a hierarchy of progress guarantees worth knowing:
- Obstruction-free (weakest) - a thread makes progress if it runs in isolation (other threads paused). Concurrent threads might interfere indefinitely.
- Lock-free - the system always makes progress: at least one thread always completes in bounded steps, so the whole system can't stall. But an individual thread could, in theory, retry forever (always losing its CAS to others) - it's starvation-free for the system, not for every thread.
- Wait-free (strongest) - every thread completes its operation in a bounded number of steps, regardless of contention. No thread can starve. This is the hardest to achieve and often costs performance.
Important: A CAS retry loop is lock-free but not wait-free. Lock-free because some thread always wins its CAS and makes progress, so the system advances. Not wait-free because a specific unlucky thread could keep losing its CAS to faster threads and retry indefinitely - in the worst case, starving. This distinction is a favorite interview question: "is a CAS loop wait-free?" - no, it's lock-free; a thread can retry without bound even though the system progresses. Wait-free algorithms exist (and some atomic operations, like fetch-and-add, are wait-free - next lesson), but the basic CAS loop only guarantees system-wide progress, not per-thread progress. Knowing where CAS loops sit in this hierarchy is exactly the depth that signals you understand lock-free programming rather than just CAS.
The canonical example: a lock-free stack
The Treiber stack is the "hello world" of lock-free data structures, and it shows the CAS loop building something real. A stack is a linked list with a head pointer; push and pop both CAS the head:
// Lock-free push: prepend a node by CAS-ing head
function push(value):
node = new Node(value)
loop:
oldHead = atomic_load(head)
node.next = oldHead
if CAS(head, expected=oldHead, new=node): // splice in iff head unchanged
return
// else: head changed (another push/pop) - retry
// Lock-free pop: advance head past the top node by CAS
function pop():
loop:
oldHead = atomic_load(head)
if oldHead == null: return null
newHead = oldHead.next
if CAS(head, expected=oldHead, new=newHead): // remove top iff head unchanged
return oldHead.value
// else: head changed - retry
Both operations follow the loop: read head, prepare the change, and CAS it in expecting the head you read. If another thread modified head in between, the CAS fails and you retry with the new head. No locks - concurrent pushes and pops coordinate purely through the atomic CAS on head. This is a genuinely useful, fully concurrent stack with no locking, and being able to sketch it is a common lock-free interview ask. (It also harbors the ABA problem in pop, which the dedicated lesson covers - a preview of why lock-free programming is subtle.)
Hardware and the cost under contention
At the hardware level, CAS is a real instruction: CMPXCHG on x86. Some architectures (ARM, POWER) instead provide load-linked / store-conditional (LL/SC) - load a value "linked," do work, then store-conditional, which succeeds only if nothing wrote to the location since the load; LL/SC can build CAS and avoids some of its problems. Either way, the hardware provides the atomic conditional update CAS represents.
One practical caution, echoing Module 4's optimistic-under-contention point: CAS loops can retry a lot under high contention. When many threads hammer the same location, most CAS attempts fail (only one wins each round), so threads burn cycles on failed-then-retried attempts - the same wasted-work problem as optimistic concurrency, because lock-free CAS code is optimistic concurrency. Lock-free isn't automatically faster than locking; under heavy contention on a single hot location, the retry churn can make it slower. Lock-free shines under low-to-moderate contention and where avoiding blocking matters (e.g., real-time systems, or avoiding the latency spikes of a contended lock).
A worked comparison: lock-free counter vs mutex counter
Putting the lock-free and lock-based versions of the same thing side by side makes the trade-off concrete - and corrects the common assumption that lock-free is simply "better."
// Mutex counter (lock-based):
function increment():
lock.lock()
count += 1
lock.unlock()
// Lock-free counter (CAS loop):
function increment():
loop:
c = atomic_load(count)
if CAS(count, c, c + 1): break
The behavioral difference is in what happens when a thread is delayed mid-operation. In the mutex version, if the thread holding the lock is descheduled by the OS between lock() and unlock(), every other thread calling increment() blocks - they pile up waiting for a lock whose holder isn't even running. One unlucky scheduling decision stalls the whole set of threads. In the lock-free version, there is no lock to hold, so a thread descheduled mid-increment holds nothing; other threads keep loading, computing, and CASing successfully, completely unaffected by the paused thread. This immunity to a stalled participant is the real, concrete advantage of lock-free code, and it's why lock-free structures matter enormously in contexts where a thread can be paused at any moment: real-time systems (where a priority-inverted lock-holder causes missed deadlines), signal handlers, and any setting where predictable latency matters more than peak throughput.
But the lock-free version is not a free upgrade. Under high contention on this single hot counter, the CAS loop's threads constantly invalidate each other's reads - only one CAS succeeds per round, the rest retry - so the cumulative wasted work can make it slower than the mutex, which at least serializes cleanly with no retry churn. And as established, it's lock-free, not wait-free, so an individual thread can starve. So the honest comparison: lock-free wins on progress guarantees and latency predictability (no stalled-holder problem, no blocking), the mutex can win on raw throughput under heavy single-location contention and is far simpler to write correctly. The choice isn't "lock-free is better"; it's "lock-free buys immunity to blocking and stalls, at the cost of complexity and possible retry churn." (And for this specific counter, fetch-and-add - next lesson - beats both.)
The broader lock-free landscape
The Treiber stack is the entry point, but the lock-free world extends far beyond it, and a sense of the terrain shows why this is considered concurrency's deep end. From CAS you can build lock-free queues (the Michael-Scott queue is the canonical concurrent FIFO), lock-free hash maps, lock-free linked lists, and more - each a careful arrangement of CAS retry loops over the structure's pointers. These power high-performance systems where lock contention would be a bottleneck: concurrent runtimes, low-latency trading systems, OS kernels, and the internals of concurrent collections in standard libraries (Java's ConcurrentLinkedQueue, for instance, is a lock-free Michael-Scott queue).
What makes lock-free programming genuinely hard - and worth a whole module - is the subtleties that lurk beneath the clean CAS loop. Three of them are the subjects of the remaining lessons. The ABA problem: CAS checks "is the value still what I read," but a value can change away and back, fooling CAS into succeeding when the world actually changed underneath it - a real bug in the Treiber pop. Memory ordering: lock-free code can't rely on the implicit ordering a lock provides, so you must reason explicitly about which atomic operations establish which happens-before relationships, or threads will see each other's writes in surprising orders. And memory reclamation: in a garbage-collected language you can pop a node freely, but in a manual-memory language, freeing a node another thread might still be about to CAS on is a use-after-free - solved by intricate schemes (hazard pointers, epoch-based reclamation) that are among the hardest parts of the field. This landscape is why lock-free programming has its reputation: the CAS loop is simple, but using it to build correct concurrent structures requires navigating ABA, memory ordering, and reclamation - exactly the topics this module turns to next. Knowing that these three challenges exist, and that they're what separates a toy CAS loop from a production lock-free structure, is itself a strong signal of lock-free literacy.
The interview angle
Interview: Core questions: (1) "What is compare-and-swap?" - An atomic instruction that writes a new value only if the location still equals an expected value, reporting success/failure; it lets a thread commit a change only if no one interfered. (2) "What's the CAS retry loop?" - Read current, compute new, CAS expecting current; on failure (someone changed it) reload and retry. The skeleton of lock-free algorithms. (3) "Why does CAS enable lock-free programming?" - No lock means no thread can block others by holding one; some thread always succeeds its CAS, so the system always progresses even if threads are delayed. (4) "Lock-free vs wait-free?" - Lock-free: the system always progresses (some thread completes), but an individual thread could retry forever. Wait-free: every thread completes in bounded steps. A CAS loop is lock-free, not wait-free. (5) "Sketch a lock-free stack." - Treiber stack: push/pop CAS the head pointer in a retry loop. The lock-free-vs-wait-free distinction and "CAS loops are lock-free" are the standout depth signals.
Quick reference
COMPARE-AND-SWAP: CAS(location, expected, new)
atomically: if *location == expected { *location = new; return true } else return false
= "commit my change ONLY if no one changed it since I read it" (optimistic, in 1 instruction)
CAS RETRY LOOP (skeleton of lock-free code):
loop: cur = load(loc); next = compute(cur)
if CAS(loc, cur, next): break // success
// else retry (someone changed it)
NO lock held; failure just means retry
PROGRESS GUARANTEES (weak -> strong):
obstruction-free: progress only if running alone
LOCK-FREE: SYSTEM always progresses (some thread completes) - but a thread CAN retry forever
WAIT-FREE: EVERY thread completes in bounded steps (strongest; rare)
-> a CAS loop is LOCK-FREE, NOT wait-free
WHY LOCK-FREE > locks for progress: no lock-holder whose delay stalls all waiters
HARDWARE: CMPXCHG (x86); LL/SC = load-linked/store-conditional (ARM/POWER)
TREIBER STACK: lock-free push/pop by CAS-ing the head pointer (canonical example)
CAUTION: high contention -> many failed CAS retries (it's optimistic; can be slower than a lock)
CAS is the universal building block - from it you can construct any other atomic operation and any lock-free structure. The next lesson surveys the broader family of atomic operations, including one (fetch-and-add) that's wait-free where the CAS loop is only lock-free - a sharp illustration of why having the right specialized atomic matters.