Lock-Free Data Structures & Algorithms
Lock-free programming eliminates blocking, deadlock risk, and priority inversion by using hardware compare-and-swap instructions instead of locks. this topic builds a lock-free stack, queue, and inventory counter from scratch on top of that one primitive.
Learning objectives
- Explain what compare-and-swap does and why lock-free code retries it in a loop
- Implement a lock-free stack (Treiber stack) and a lock-free queue (Michael-Scott queue)
- Apply the CAS-retry pattern to prevent a classic time-of-check-to-time-of-use race
- Describe the ABA problem and when it's a genuine risk
- Distinguish lock-free from wait-free progress guarantees
A synchronized block gives correctness in exchange for a real cost: every thread that wants the resource has to line up and take turns, even threads that could, in principle, make progress without stepping on each other. Under high contention this queueing itself becomes the bottleneck - only one thread advances at a time no matter how many CPU cores are sitting idle waiting for their turn.
Locks bring a few problems that are structural, not just about speed. A thread holding a lock can deadlock with another thread holding a different lock, as covered earlier in this course. A low-priority thread holding a lock that a high-priority thread needs causes priority inversion - the high-priority thread is now effectively throttled to the low-priority thread's schedule. And if a thread dies while holding a lock - an uncaught exception, a kill signal - every other thread waiting on that lock blocks forever, since nothing ever releases it.
Lock-free programming sidesteps all three at once by never having a lock to begin with. Instead of "one thread owns the resource while everyone else waits," every thread attempts its own update speculatively, and the hardware itself resolves conflicts atomically. The core primitive is compare-and-swap (CAS): a single CPU instruction that says "set this memory location to a new value, but only if it still holds the value I expect - and tell me whether that succeeded." If two threads race to update the same value, exactly one CAS succeeds and the other fails; the loser just retries against the fresh value instead of blocking.
This isn't free. Lock-free code is measurably harder to write correctly and harder to debug, since there's no single critical section to reason about - correctness has to hold for every possible interleaving of every thread's CAS attempts. It's also only faster under real contention; at low contention a well-tuned synchronized block can win outright, since it pays no cost for a CAS retry loop that never actually needs to retry. The practical default is to reach for already-built, battle-tested lock-free structures - AtomicInteger, ConcurrentLinkedQueue - and only hand-roll a custom one once profiling shows an actual lock bottleneck that those don't solve.
Before Java 9, low-level atomic field access was only available through sun.misc.Unsafe - an internal, explicitly unsupported JVM trapdoor that library authors, including the JDK's own java.util.concurrent package, relied on for decades despite repeated warnings it could be removed at any time. VarHandle is the safe, standardized replacement: the same compare-and-swap capability that underlies every lock-free algorithm, but type-checked and access-controlled through ordinary Java module rules.
This is exactly what powers AtomicInteger and AtomicReference internally, and what the lock-free stack and queue built later in this topic rest on. Reaching for VarHandle directly instead of an Atomic* wrapper class makes sense when writing a data structure with many fields, where allocating a separate wrapper object per field would add memory and indirection overhead that a raw field access avoids.
CAS is a one-shot operation: it either succeeds or it doesn't, and calling it again with the same "expected" value after it has already succeeded will simply fail, because the field no longer holds that value. That's not a bug - it's the entire point. CAS only succeeds when reality still matches what was read at the moment the check happens; if another thread got there first, the caller has to re-read the current value and decide what to do next. Every lock-free structure in this topic wraps a single CAS call in a loop that does exactly that: read, compute, attempt, and on failure, loop back and try again against the fresh value.
💻 Code example
package concurrency.lockfree; import java.lang.invoke.MethodHandles; import java.lang.invoke.VarHandle; public class VarHandleCasDemo { // `volatile` ensures plain reads/writes outside the CAS calls are also // immediately visible across threads. private volatile int state = 0; // Looking up a VarHandle is relatively costly, so it's done once here and // shared by every instance/thread rather than per-call. private static final VarHandle STATE_HANDLE; static { try { STATE_HANDLE = MethodHandles.lookup() .findVarHandle(VarHandleCasDemo.class, "state", int.class); } catch (Exception e) { throw new RuntimeException(e); } } public boolean casState(int expected, int newValue) { // Atomic compare-and-swap directly on `this.state`: succeeds only if // the field's current value equals `expected`. return STATE_HANDLE.compareAndSet(this, expected, newValue); } public static void main(String[] args) { VarHandleCasDemo demo = new VarHandleCasDemo(); boolean success = demo.casState(0, 5); System.out.println("CAS success? " + success + " | state: " + demo.state); // Calling casState(0, 5) again now returns false - state is already 5, // not 0. This is the "expected value mismatch" every CAS retry loop // below is built to handle, not a bug. } }
A plain linked-list stack is unsafe under concurrency: two threads popping at the same time could both read the same head, both compute the same "new head," and one thread's update gets silently lost. synchronized fixes the correctness problem but forces every thread to serialize through one lock. The Treiber stack - named for R. Kent Treiber, who described it at IBM in 1986 - gets the same correctness guarantee, exactly-once semantics for every push and pop, with no blocking at all. Contending threads never suspend; they just retry a cheap, purely local computation.
push() builds the new node off to the side first - pure thread-local work, no contention possible yet - snapshots the current head, links the new node's next pointer to that snapshot, then attempts to CAS head from the old snapshot to the new node. If another thread's push or pop got there first, the CAS fails and the loop retries against the freshly re-read head. pop() is the mirror image: snapshot head, return immediately if it's null (an empty stack), read the snapshot's next field as the candidate new head, then CAS.
The entire structure's mutable state is a single AtomicReference<Node<T>> pointing at the top of the stack - every bit of push/pop coordination happens through CAS operations on that one reference, with no separate lock object anywhere.
💻 Code example
package concurrency.lockfree; import java.util.concurrent.atomic.AtomicReference; public class TreiberStack<T> { static class Node<T> { final T value; Node<T> next; Node(T value) { this.value = value; } } // The stack's entire mutable state: a single atomic pointer to the top node. private final AtomicReference<Node<T>> head = new AtomicReference<>(); public void push(T value) { Node<T> newHead = new Node<>(value); // Pure thread-local work so far. Node<T> oldHead; do { oldHead = head.get(); // Snapshot the current top-of-stack. newHead.next = oldHead; // Speculatively link in front of it. // Succeeds only if head is still exactly oldHead; otherwise retry // against the fresh head. } while (!head.compareAndSet(oldHead, newHead)); } public T pop() { Node<T> oldHead; Node<T> newHead; do { oldHead = head.get(); if (oldHead == null) return null; // Empty stack. newHead = oldHead.next; // Candidate new top if this pop succeeds. } while (!head.compareAndSet(oldHead, newHead)); return oldHead.value; } public static void main(String[] args) { TreiberStack<String> stack = new TreiberStack<>(); stack.push("task-1"); stack.push("task-2"); System.out.println("Popped: " + stack.pop()); // task-2 (LIFO) System.out.println("Popped: " + stack.pop()); // task-1 } }
A FIFO queue is structurally harder to make lock-free than a stack, because it has two ends - head for removal and tail for insertion - that must stay coordinated. Naively CAS-ing both independently isn't safe: a thread could be interrupted between linking a new node in and updating tail to point at it, leaving the queue in a transiently "torn" state that another thread might observe.
The Michael-Scott queue, described by Maged Michael and Michael Scott in 1996 and the algorithm behind ConcurrentLinkedQueue, solves this with a technique called helping: any thread that notices the tail pointer is lagging behind the actual last node advances the tail pointer on behalf of whichever thread left it behind, before proceeding with its own operation. This guarantees global progress even if the thread that left the tail lagging is paused or descheduled indefinitely - the defining property of a genuinely lock-free algorithm, as opposed to one that's merely usually fast. Both head and tail start out pointing at a shared dummy sentinel node, so the empty-queue case needs no special branching.
Removing the "helping" line breaks the progress guarantee entirely: a thread suspended right after linking a node but before advancing tail could stall every other thread's enqueue and dequeue indefinitely, since nobody would ever fix up the lagging pointer. The re-verification check that the snapshot of tail hasn't changed matters too - without it, a thread could act on a torn read and corrupt the chain. In production code, the right move is almost always to reach for ConcurrentLinkedQueue directly - it implements this exact algorithm, already tested at scale.
💻 Code example
package concurrency.lockfree; import java.util.concurrent.atomic.AtomicReference; public class MichaelScottQueue<T> { static class Node<T> { final T value; // null only for the dummy sentinel final AtomicReference<Node<T>> next = new AtomicReference<>(null); Node(T value) { this.value = value; } } private final Node<T> dummy = new Node<>(null); private final AtomicReference<Node<T>> head = new AtomicReference<>(dummy); private final AtomicReference<Node<T>> tail = new AtomicReference<>(dummy); public void enqueue(T value) { Node<T> newNode = new Node<>(value); while (true) { Node<T> curTail = tail.get(); Node<T> tailNext = curTail.next.get(); if (curTail == tail.get()) { // Consistent snapshot check. if (tailNext == null) { // tail really is the last node: link our node in. if (curTail.next.compareAndSet(null, newNode)) { tail.compareAndSet(curTail, newNode); // Advance tail. return; } } else { // tail was lagging behind an already-linked node from // another thread's in-progress enqueue - help it along. tail.compareAndSet(curTail, tailNext); } } } } public T dequeue() { while (true) { Node<T> curHead = head.get(); Node<T> curTail = tail.get(); Node<T> headNext = curHead.next.get(); if (curHead == head.get()) { if (curHead == curTail) { if (headNext == null) return null; // Genuinely empty. tail.compareAndSet(curTail, headNext); // Help advance tail. } else { T val = headNext.value; // Read before the CAS below. if (head.compareAndSet(curHead, headNext)) return val; } } } } public static void main(String[] args) { MichaelScottQueue<Integer> q = new MichaelScottQueue<>(); q.enqueue(100); q.enqueue(200); System.out.println("Dequeued: " + q.dequeue()); // 100 (FIFO) System.out.println("Dequeued: " + q.dequeue()); // 200 } }
Consider 1000 concurrent shoppers trying to buy from the last 50 units of a flash-sale item. A naive "read stock, check if enough, subtract" is a classic time-of-check-to-time-of-use race: two threads could both read stock == 10, both independently decide "yes, 3 is available," and both subtract 3 - leaving the counter at 4 instead of the correct 7, silently overselling 3 units that don't exist.
The lock-free fix is the same CAS-retry loop pattern from the stack and queue, applied to a single AtomicInteger: read the current stock, check whether it's enough to satisfy the request, and if so, attempt to CAS it down to current - quantity. If the CAS fails - because another thread changed the value between the read and the attempt - loop back, re-read the fresh value, and try again. Because every successful reservation is validated against the value at the exact instant it commits, two threads can never both succeed in oversubscribing the same units.
This could be written more compactly with stock.updateAndGet(v -> v >= quantity ? v - quantity : v), which wraps the same CAS-retry loop internally - but extra logic would still be needed to detect and report the failure case, which is why writing the loop explicitly is worth understanding on its own. Restocking needs no loop at all: stock.addAndGet(quantity) is a single atomic add with nothing to retry against, since there's no precondition to check before adding.
Two specific mistakes reintroduce the exact bug this pattern exists to prevent: dropping the while retry for a single one-shot CAS call means a failed CAS under contention gets silently ignored - the method would report success without stock actually being deducted. And removing the "enough stock" check before the CAS lets the counter go negative under high demand.
💻 Code example
package concurrency.lockfree; import java.util.concurrent.atomic.AtomicInteger; public class LockFreeInventory { private final AtomicInteger stock = new AtomicInteger(10); public boolean reserve(int quantity) { int current; do { current = stock.get(); // Snapshot the latest committed value. if (current < quantity) return false; // Not enough units. // Succeeds only if no other thread changed stock since we read // `current`; otherwise loop back and retry against the fresh value. } while (!stock.compareAndSet(current, current - quantity)); return true; } public int getStock() { return stock.get(); } public static void main(String[] args) { LockFreeInventory inventory = new LockFreeInventory(); boolean reserved = inventory.reserve(3); System.out.println("Reserved 3? " + reserved + " | remaining: " + inventory.getStock()); } }
◆ Under the hood
CAS only checks that a reference is unchanged - literally the same object identity - not that nothing happened in between. Imagine thread 1 reads head == A (with A.next == B), then pauses. Thread 2 pops A, pops B, then pushes a brand-new node that happens to reuse the same memory location or object identity as A - something that can genuinely happen with object pooling, though ordinary new Node<>() allocation, as used throughout this topic, makes it astronomically unlikely. Thread 1 resumes: its CAS sees head == A, "succeeds," and swaps head to A.next - but that next may now be stale garbage from the old chain, silently corrupting the stack. This is the ABA problem: a value went A to B to A, fooling a naive CAS into thinking nothing changed. AtomicStampedReference and AtomicMarkableReference, which pair the reference with a version counter, are the standard fix when ABA is a genuine risk. Plain object-identity CAS is safe as long as nodes are never reused after being popped.
▲ Edge case
Lock-free is a weaker guarantee than wait-free, and the difference matters. A blocking synchronized structure gives no progress guarantee at all - if the thread holding the lock is delayed or descheduled, everyone waiting on it is stuck too. Lock-free guarantees that at least one thread, system-wide, makes progress in a finite number of steps; individual threads can still "starve" if their CAS keeps losing to someone else's, but the system as a whole never stalls entirely. Wait-free is the strongest guarantee: every thread completes its own operation in a bounded number of steps, regardless of what any other thread does. AtomicInteger.get() and .set() are wait-free - no retry loop at all. CAS-retry-loop operations like incrementAndGet(), and every structure built in this topic, are only lock-free: in theory, under pathological adversarial scheduling, one thread's CAS could keep losing indefinitely, even though the system overall keeps making progress.
▲ Common mistake
Reaching for a hand-rolled CAS loop before checking what the standard library already offers. AtomicInteger and AtomicBoolean are already lock-free and battle-tested for simple counters and flags. ConcurrentLinkedQueue already implements the Michael-Scott algorithm. LongAdder outperforms a plain AtomicLong under very high contention, because it stripes the counter across multiple internal cells to reduce CAS collisions, then sums them on read. A custom lock-free structure is worth building only after profiling shows an actual lock bottleneck that none of these already solve - and only for a single reference or counter, since CAS can only atomically update one location at a time. Anything that needs multiple related variables to change together, or that spans a complex multi-field invariant, needs a real lock.
What does compare-and-swap actually do? : A single atomic CPU instruction: "set this memory location to a new value, but only if it still holds the value I expect." It succeeds or fails; a failure means another thread changed the value first, and the caller re-reads and retries.
Why is lock-free code harder than it looks? : Correctness has to hold for every possible interleaving of every thread's CAS attempts, since there's no single critical section to reason about. It's also only a performance win under real contention - at low contention, a well-tuned lock can be faster.
What is the ABA problem?
: CAS checks object identity, not history - a value that changed from A to B and back to A looks unchanged to a naive CAS, which can corrupt a structure if nodes are reused. AtomicStampedReference (a reference plus a version counter) is the standard fix when this is a genuine risk.
What's the difference between lock-free and wait-free? : Lock-free guarantees the system as a whole always makes progress, but an individual thread's CAS can keep losing indefinitely. Wait-free guarantees every single thread finishes in a bounded number of steps regardless of what others do - a much stronger and much rarer guarantee.
When should I build a custom lock-free structure?
: Only after profiling shows a real lock bottleneck that AtomicInteger, ConcurrentLinkedQueue, or LongAdder don't already solve - and only for a single reference or counter, since CAS can't atomically update multiple variables at once.
Want a visual for this concept?
Generate a diagram tailored to “Lock-Free Data Structures & Algorithms” — the AI picks whichever visual (flowchart, comparison, sequence, etc.) best fits.
Sign in to generate a visual →