Free lesson · Concurrency Interview Mastery

Exercise: Compare-and-Swap (CAS)

Medium6 min readconcurrencymultithreadinginterview-prep

This exercise builds lock-free code from CAS: a counter, then the Treiber stack, then a confrontation with what "lock-free but not wait-free" actually means in practice. Reason each through before the solution - the skill is thinking in terms of the read-compute-CAS-retry loop and understanding precisely what progress guarantee it gives.

Important: The mental model for every part: read, compute, then commit only if nothing changed - and if something did, try again. Lock-free code never blocks and never holds a lock; instead it optimistically attempts and retries. Keep asking: what happens on a failed CAS, and is any individual thread guaranteed to eventually succeed?

Part 1 - A lock-free counter

Implement a shared counter's increment using CAS, with no lock. Then state the progress guarantee.

counter = atomic(0)

function increment():
    // TODO: read current, compute +1, CAS it in, retry on failure

Your task: Write the CAS retry loop. Is this counter lock-free, wait-free, or neither? Justify.

loop { c = load(counter); if CAS(counter, c, c+1) break }. It's lock-free: some thread always wins its CAS each round, so the system progresses. It's not wait-free: a specific thread could keep losing its CAS to faster threads and retry without bound. </details>

Part 2 - A lock-free stack (Treiber)

Implement lock-free push and pop for a stack - a linked list with a head pointer - using CAS on head.

head = atomic(null)

function push(value):
    // TODO: make a node, point it at the current head, CAS head to it; retry

function pop():
    // TODO: read head, compute head.next, CAS head to next; retry; handle empty

Your task: Write both with CAS retry loops. Explain how two concurrent pushes coordinate without a lock.

push: loop { old = load(head); node.next = old; if CAS(head, old, node) return }. pop: loop { old = load(head); if old==null return null; if CAS(head, old, old.next) return old.value }. Two concurrent pushes both read the same head; only one's CAS succeeds (head still equals what it read), the other's fails because head now points to the winner's node - so it retries with the new head. The CAS on head is the coordination point. </details>

Part 3 - Lock-free is not starvation-free

Your CAS counter from Part 1 is lock-free. A teammate claims "lock-free means no thread can ever get stuck, so it's strictly better than a mutex."

Your task: Explain why that claim is wrong - construct a scenario where one thread makes no progress even though the counter is lock-free - and state what guarantee lock-free actually provides versus what it does not.

Lock-free guarantees the system progresses (some thread always succeeds), not that every thread does. Imagine a slow thread repeatedly reading the counter, computing, and attempting its CAS - but each time, faster threads have already changed the counter, so the slow thread's CAS always fails and it retries forever. The system advanced (the fast threads incremented), but this one thread starved. Lock-free ≠ wait-free; only wait-free guarantees every thread completes in bounded steps. </details>

Solution

Part 1 - Lock-free counter

counter = atomic(0)

function increment():
    loop:
        current = atomic_load(counter)
        if CAS(counter, expected=current, new=current + 1):
            return                          // committed
        // else: someone else incremented between our load and CAS - retry

Read the current value, attempt to CAS it to value+1 expecting the value we read, and retry if another thread changed it in between. Progress guarantee: lock-free, not wait-free. It's lock-free because in any round of competing CASes, exactly one thread's CAS succeeds (its expected value still matches), so some thread always makes progress - the system never stalls, and crucially, no thread holding anything can block the others (there's nothing held). It's not wait-free because there's no bound on how many times an individual thread might retry: a thread can lose its CAS repeatedly to faster threads and loop indefinitely. So the system is guaranteed to advance, but any single thread is not guaranteed to finish in bounded time. (This is exactly the case where fetch-and-add - the next lesson - does better: it's wait-free.)

Part 2 - Treiber stack

head = atomic(null)

function push(value):
    node = new Node(value)
    loop:
        oldHead = atomic_load(head)
        node.next = oldHead                       // point new node at current top
        if CAS(head, expected=oldHead, new=node): # splice in iff head unchanged
            return
        // else: head changed (another push/pop) - retry with new head

function pop():
    loop:
        oldHead = atomic_load(head)
        if oldHead == null:
            return null                           // empty
        newHead = oldHead.next
        if CAS(head, expected=oldHead, new=newHead):   // remove top iff head unchanged
            return oldHead.value
        // else: head changed - retry

How two concurrent pushes coordinate without a lock: both threads load the same head value (say it points to node X). Both prepare their new node pointing at X. Both attempt CAS(head, X, theirNode). Only one succeeds - whichever's CAS executes first finds head still equal to X and swings it to its node. The other thread's CAS now fails, because head no longer equals X (it points to the winner's node). The loser loops, reloads head (now the winner's node), points its node at that, and retries - succeeding this round (assuming no further interference). The atomic CAS on head is the sole coordination point: it guarantees that exactly one push can splice in at a time, with losers retrying, all without any lock. The same logic makes concurrent pops and push/pop mixes safe - every modification of head goes through a CAS that detects and rejects interference.

Part 3 - Lock-free is not starvation-free

The teammate's claim conflates lock-free with wait-free. Lock-free guarantees the system makes progress - at least one thread completes its operation in bounded steps - but it does not guarantee every individual thread makes progress. Here's the starvation scenario for the Part 1 counter:

Slow thread S:  load counter (=5); compute 6; ... (S is slow here) ...
Fast threads:   meanwhile increment counter 5->6->7->8 repeatedly
Slow thread S:  CAS(counter, expected=5, new=6) -> FAILS (counter is now 8)
Slow thread S:  load counter (=8); compute 9; ...
Fast threads:   increment 8->9->10->11 ...
Slow thread S:  CAS(counter, expected=8, new=9) -> FAILS again
... S retries forever, never succeeding, while the system races ahead ...

Thread S never completes - it starves - even though the counter is steadily incrementing. The system progressed enormously (the fast threads did all the work), satisfying lock-freedom, but S made no progress, violating what wait-freedom would guarantee. So lock-free is not "no thread can ever get stuck"; it's "the system as a whole can't get stuck."

This also corrects the "strictly better than a mutex" claim: lock-free has a stronger system-progress guarantee than a mutex (a delayed lock-holder can't stall everyone), but it does not guarantee fairness to individual threads, and under high contention its retry churn can make it slower than a mutex. Lock-free is a different trade-off, not a universal upgrade. The guarantee it actually provides - system-wide progress, immunity to a stalled thread blocking others - is valuable (especially for real-time and latency-sensitive code), but it comes without per-thread fairness, which only wait-free algorithms provide.

Common mistakes

Warning: Watch for: (1) Claiming a CAS loop is wait-free - it's lock-free; an individual thread can retry without bound. (2) Forgetting to reload inside the loop - on CAS failure you must re-read the current value before recomputing, or you'll retry with stale data and fail forever. (3) Assuming lock-free is always faster than locking - under high contention on one hot location, retry churn can make it slower; it's a different trade-off, not a free win. (4) Overlooking ABA in the stack pop - the Treiber pop has a subtle ABA bug (a node freed and reused) covered in the dedicated lesson; CAS alone doesn't catch A→B→A. (5) Thinking lock-free means starvation-free - only wait-free guarantees every thread progresses.

Why this exercise matters for interviews

Interview: Lock-free programming is the deep end of concurrency interviews, and these are the canonical asks. Part 1 (lock-free counter) and Part 2 (Treiber stack) are direct "implement a lock-free X with CAS" questions - being able to write the read-compute-CAS-retry loop fluently is the baseline. Part 3 is the conceptual discriminator: "is your lock-free counter wait-free?" (no) and "does lock-free mean no thread starves?" (no - system progress, not per-thread). Candidates who can construct the starvation scenario and articulate lock-free vs wait-free precisely stand out sharply, because most people stop at "no locks, so it's better." Rehearse the Treiber stack until you can write it from memory, and rehearse the lock-free/wait-free distinction until you can state it crisply - both come up constantly.

Back to Concurrency Interview Mastery