skip to content

Explain how a CAS-based lock-free queue like ConcurrentLinkedQueue makes progress, and what 'lock-free' guarantees (versus 'wait-free' and lock-based).

level: principalimportance: nice to knowfreq 33%

answer

  1. Optimistic loop: read -> compute -> CAS -> retry on failure; no lock
  2. Lock-free = system-wide progress, no deadlock; a stalled thread can't block others
  3. Lock-free does NOT prevent per-thread starvation
  4. Wait-free = every thread bounded-steps, no starvation; harder/rarer
  5. Helping mechanism advances lagging tail; ABA mitigated by version stamps

basics

~20 s

Each operation tries to update a pointer with compare-and-swap (CAS); if another thread changed it first, the CAS fails and the operation retries. 'Lock-free' means the system as a whole always makes progress even if some threads stall, but an individual thread can be made to retry indefinitely.

solid answer

~60 s

ConcurrentLinkedQueue uses optimistic CAS loops: a thread reads the current tail (or head), prepares its change, and attempts a compare-and-swap that succeeds only if nothing changed in between; if another thread won the race the CAS fails and the thread re-reads and retries. No thread ever holds a lock, so a thread that is descheduled mid-operation cannot block others. That property is 'lock-free': it guarantees that at any moment at least one thread will complete its operation in a bounded number of steps — i.e. the system as a whole always makes progress and cannot deadlock or be stalled by a parked thread. It does NOT guarantee every individual thread finishes in bounded steps: a slow thread can be forced to retry repeatedly while faster threads keep winning, so it can starve. 'Wait-free' is the stronger guarantee that every thread completes in a bounded number of steps regardless of others — no starvation — but it is much harder to implement and rarer. Lock-based code is neither: if the lock holder is descheduled, everyone waiting blocks, and a crash while holding the lock can wedge the whole system.

code

java · 20 lines
java
// The lock-free pattern at the heart of ConcurrentLinkedQueue: optimistic CAS retry.
// (Conceptual sketch of an enqueue, not the actual JDK source.)
void enqueue(Node newNode) {
    while (true) {                     // retry loop -- no lock held
        Node last = tail;              // optimistic read (tail may lag)
        Node next = last.next;
        if (next == null) {
            // try to link new node at the end; succeeds only if last.next is still null
            if (CAS(last.next, null, newNode)) {
                CAS(tail, last, newNode);   // best-effort tail advance (helping)
                return;                      // this thread made progress
            }
            // CAS failed: another thread enqueued first -> loop and retry
        } else {
            CAS(tail, last, next);      // help advance a lagging tail, then retry
        }
    }
}
// Lock-free: SOME thread always completes a CAS, so the system progresses.
// But a perpetually-losing thread could spin here without finishing -> not wait-free.

go deeper

for a junior

Understands that the queue retries with CAS instead of locking, so threads don't wait on a lock.

for a middle

Can describe the read-compute-CAS-retry loop and that no lock is held, so there's no deadlock.

for a senior

Explains lock-free as system-wide progress, contrasts with lock-based blocking, and notes individual-thread starvation and the ABA pitfall.

for a principal

Places lock-free in the full progress hierarchy (blocking < lock-free < wait-free), reasons about starvation/fairness, cache-line contention costs, and when a lock or contention-spreading design beats a single lock-free structure for the system's SLAs.

## Setting the stage: progress guarantees When many threads share a data structure, we care not just about correctness but about **progress** — the guarantee that work actually completes despite scheduling, stalls, or crashes of individual threads. There is a hierarchy of progress guarantees: **blocking (lock-based) < obstruction-free < lock-free < wait-free**. Understanding ConcurrentLinkedQueue means understanding where 'lock-free' sits. ## The CAS primitive **Compare-And-Swap (CAS)** is an atomic hardware instruction: `CAS(address, expected, new)` atomically checks whether `address` holds `expected`, and if so writes `new`, returning success/failure. It's atomic, so no two threads can both 'win' the same CAS. CAS is the universal building block for lock-free algorithms because it lets a thread commit a change *only if* the world hasn't moved since it looked. ## How the queue makes progress: the optimistic retry loop ConcurrentLinkedQueue is a linked list with `head` and `tail` references, implementing a Michael-Scott-style non-blocking queue. An enqueue looks roughly like: 1. Read the current last node (via `tail`, which may lag). 2. Try `CAS(last.next, null, newNode)` — link the new node only if `last.next` is still `null`. 3. If it **succeeds**, optionally `CAS(tail, last, newNode)` to advance the tail (best-effort; another thread may do it for you — *helping*). 4. If it **fails** (someone enqueued first), loop: re-read and try again. Dequeue is symmetric on `head`. The essential pattern is **read → compute → CAS → retry-on-failure**. There is no lock at any point. The 'helping' mechanism (any thread can finish advancing a lagging tail) is what keeps the structure consistent without a coordinator. ## What 'lock-free' guarantees — and doesn't **Lock-free** is defined precisely: *at least one thread makes progress in a bounded number of steps, system-wide.* Consequences: - **No deadlock, no convoying, no priority inversion** from a held lock — because no lock is held. - **A stalled/descheduled/preempted thread cannot block others.** With a lock, if the holder is paused by the OS (or page-faults, or is a lower-priority thread the scheduler ignores), everyone waiting is stuck. Lock-free has no such single point of stall. - **Crucially, it does NOT guarantee per-thread progress.** A specific unlucky thread can have its CAS fail again and again because other threads keep winning the race — it can **starve** indefinitely. Lock-free guarantees the *whole system* keeps moving, not that *your* thread does. - It is also vulnerable to subtle bugs like the **ABA problem** (a value goes A→B→A and a CAS wrongly succeeds), handled elsewhere with version stamps (AtomicStampedReference). ## Wait-free: the stronger guarantee **Wait-free** means *every* thread completes its operation in a **bounded number of its own steps**, regardless of what other threads do — so no thread can ever starve. This is strictly stronger than lock-free. It's highly desirable for hard-real-time and fairness-critical code but is much harder to design and often has higher constant overhead, so it's comparatively rare in practice. ConcurrentLinkedQueue is lock-free, **not** wait-free. ## Lock-based, for contrast A mutex-guarded queue is **blocking / not lock-free**: while one thread holds the lock, all others block. If the holder is descheduled, preempted by a higher-priority thread that then waits on the same lock (priority inversion), or crashes while holding it, progress can halt entirely. The upside is simplicity and that any consistent operation is trivially atomic inside the critical section. ## Why it matters for a principal Choosing a lock-free structure buys resilience to thread stalls and good scalability under contention, but you must accept possible *starvation of individual threads* and reason about *fairness* separately if it matters. It does not magically remove all costs: CAS contention causes cache-line bouncing (the contended pointer ping-pongs between cores' caches), so under extreme contention a well-tuned lock or a contention-spreading structure (e.g. LongAdder-style striping, or multiple queues) can outperform a single lock-free queue. The decision is about progress guarantees, fairness needs, contention profile, and failure modes — not a blanket 'lock-free is best.' ## One-line summary - **Lock-based**: one thread proceeds, others block; a stalled holder stalls everyone. - **Lock-free** (ConcurrentLinkedQueue): no locks, CAS-retry; the system always progresses, but an individual thread may starve. - **Wait-free**: every thread finishes in bounded steps; no starvation; hardest to build.

  • Why can't a descheduled thread inside ConcurrentLinkedQueue block the others, unlike a lock holder?
    Because the thread holds no lock and exposes no half-committed state that others must wait on — its change either landed via a single atomic CAS or didn't. Other threads simply re-read the current state and proceed, so a paused thread can't stall them. A paused lock holder, by contrast, keeps the lock and forces everyone to wait.
  • Is lock-free always faster than a lock?
    No. Under low contention a simple lock can be as fast or faster, and under extreme contention a single hot CAS causes cache-line bouncing between cores. Lock-free wins on progress guarantees and resilience to stalls, and often on moderate-to-high contention, but the right choice depends on the contention profile, fairness needs, and failure modes.

saying these in an interview costs you the question

  • Equating lock-free with wait-free (lock-free allows individual-thread starvation)
  • Claiming lock-free means 'no waiting ever for any thread'
  • Believing lock-free is always faster than a lock regardless of contention/cache effects
  • Ignoring the ABA problem in CAS-based reasoning
  • Thinking lock-free guarantees fairness

context

resolving links…