Lock-Free Queues

Every multi-threaded program eventually needs a queue: one side produces work, the other side consumes it. The obvious solution wraps the queue in a mutex — a lock that only one thread may hold at a time. Simple, but costly: if the consumer is slow, the producer waits. If the producer crashes while holding the lock, everyone waits forever.

Lock-free data structures remove that dependency. Instead of a lock, every operation reads the shared state, computes the desired new state, and then calls compare-and-swap (CAS) — a single CPU instruction that atomically writes the new value only if the old value is still there. If another thread changed the state first, CAS fails and the caller simply retries. No thread ever blocks; progress is guaranteed system-wide.

The landmark design is the Michael-Scott queue (1996), a singly-linked list where both enqueue and dequeue use exactly one CAS each. It ships inside the Java Virtual Machine, the Linux kernel, and countless high-performance systems today.

Spin up producers that enqueue numbers and consumers that dequeue them. Every operation uses a simulated compare-and-swap: it reads the current tail (or head), computes the new pointer, and only commits if nothing changed in between.

<!-- {{c_html_intro}} -->
<div class="controls">
  <div class="ctrl-group">
    <label>{{lbl_producers}}</label>
    <div class="btn-row">
      <button id="add-producer" type="button">+ {{btn_producer}}</button>
      <button id="rem-producer" type="button" class="ghost">- {{btn_producer}}</button>
    </div>
  </div>
  <div class="ctrl-group">
    <label>{{lbl_consumers}}</label>
    <div class="btn-row">
      <button id="add-consumer" type="button">+ {{btn_consumer}}</button>
      <button id="rem-consumer" type="button" class="ghost">- {{btn_consumer}}</button>
    </div>
  </div>
  <button id="reset-btn" type="button" class="ghost wide">{{btn_reset}}</button>
</div>
<div class="queue-vis" id="queue-vis">
  <span class="vis-label">{{lbl_queue}}</span>
  <div id="cells" class="cells"></div>
  <span class="vis-label-right">{{lbl_tail}}</span>
</div>
<div class="stats-row">
  <div class="stat"><span id="stat-enqueued">0</span><small>{{stat_enqueued}}</small></div>
  <div class="stat"><span id="stat-dequeued">0</span><small>{{stat_dequeued}}</small></div>
  <div class="stat accent"><span id="stat-retries">0</span><small>{{stat_retries}}</small></div>
  <div class="stat"><span id="stat-size">0</span><small>{{stat_size}}</small></div>
</div>
<div class="log-box" id="log-box"></div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.controls { display: flex; gap: .6rem; flex-wrap: wrap; align-items: flex-end; margin-bottom: .7rem; }
.ctrl-group { display: flex; flex-direction: column; gap: .3rem; }
.ctrl-group label { font-weight: 600; font-size: .8rem; color: #555; text-transform: uppercase; letter-spacing: .04em; }
.btn-row { display: flex; gap: .3rem; }
button { font: 600 13px system-ui, sans-serif; padding: .35rem .75rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button.wide { width: 100%; }
/* {{c_css_queue}} */
.queue-vis { display: flex; align-items: center; gap: .4rem; background: #f4f7fa;
             border: 1px solid #d0dae4; border-radius: 9px; padding: .5rem .7rem;
             margin-bottom: .5rem; overflow-x: auto; min-height: 54px; }
.vis-label { font-size: .72rem; font-weight: 700; color: #7a90a4; text-transform: uppercase; white-space: nowrap; }
.vis-label-right { font-size: .72rem; font-weight: 700; color: #c94040; text-transform: uppercase; white-space: nowrap; }
.cells { display: flex; gap: .3rem; flex: 1; min-width: 0; flex-wrap: nowrap; }
.cell { width: 38px; height: 38px; border-radius: 6px; display: flex; align-items: center;
        justify-content: center; font: 700 13px ui-monospace, monospace;
        border: 1.5px solid #adb5bd; background: #e9ecf0; color: #1d3557;
        flex-shrink: 0; animation: pop .25s ease; }
@keyframes pop { from { transform: scale(.6); opacity: 0; } to { transform: scale(1); opacity: 1; } }
.cell.new { background: #cfe3f7; border-color: #5a99cc; }
/* {{c_css_stats}} */
.stats-row { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
.stat { flex: 1 1 60px; background: #f4f7fa; border: 1px solid #d0dae4; border-radius: 8px;
        padding: .4rem .5rem; text-align: center; }
.stat span { display: block; font: 700 1.3rem ui-monospace, monospace; color: #1d3557; }
.stat small { font-size: .7rem; color: #7a90a4; text-transform: uppercase; }
.stat.accent span { color: #c94040; }
/* {{c_css_log}} */
.log-box { font: 12px/1.6 ui-monospace, monospace; color: #333; background: #f9fbfc;
           border: 1px solid #d8e2ea; border-radius: 8px; padding: .5rem .6rem;
           height: 120px; overflow-y: auto; }
.log-box .enq { color: #1a6e2e; }
.log-box .deq { color: #1d3557; }
.log-box .retry { color: #c94040; }

// Code not found

Watch the CAS retries counter. When two producers race to append at the same time, one of them loses the CAS and must retry — no blocking, just one more loop iteration. The queue stays consistent at every moment because CAS is atomic: partial writes are impossible.

Lock-free algorithms come with precise guarantees, and the vocabulary matters:

• Lock-freedom means that at least one thread always makes progress. A slow or crashed thread cannot stall the rest of the system — the strongest practically achievable property without tight hardware support.
• Wait-freedom is stronger: every thread finishes its operation in a bounded number of steps, no matter what others do. Most practical queues settle for lock-freedom because wait-free designs add significant complexity.
• Linearizability is the correctness criterion: every operation must appear to take effect at exactly one instant between its call and its return. The Michael-Scott queue is linearizable, which makes it a safe drop-in replacement for a mutex-protected queue.

The subtle enemy is the ABA problem: thread A reads value A at address X, gets preempted, thread B changes X to B and then back to A, and thread A's CAS succeeds even though the state has changed. Real implementations use tagged pointers — a version counter packed alongside the address — so that A → B → A is distinct from the original A.

The fundamental tension is between simplicity and correctness: a mutex is one line of code, while a correct lock-free queue needs careful reasoning about every possible interleaving. Tools like formal verification and model checkers are often applied to check these designs.

"Multiple threads need to share a queue at high speed" appears everywhere modern software runs:

• JVM thread pools: java.util.concurrent.ConcurrentLinkedQueue is a direct Michael-Scott queue. Every Java application that submits tasks to an executor is using lock-free enqueue and dequeue.
• OS schedulers: Linux's per-CPU run queues use lock-free structures so that adding a task to a core never stalls other cores — critical when the scheduler itself must run in microseconds.
• Network stacks: packet receive buffers in high-speed NICs are lock-free queues between interrupt context and the kernel's softirq handler.
• High-frequency trading: order books and market-data feeds use lock-free queues so that a slow consumer never delays a fast producer, keeping latency in nanoseconds.
• Garbage collectors: concurrent GC phases hand off objects between mutator threads and collector threads through lock-free work-stealing queues.

Whenever a mutex would become the bottleneck — because threads contend too often, or because one slow holder would cascade into the whole system — a lock-free queue is the standard remedy. Understanding them means understanding the atomic building block that underlies most of the concurrent algorithms in production software today.

A lock-free queue looks almost like a regular linked list. The only difference is that every pointer update goes through compare-and-swap instead of a write under a mutex. That one change buys a powerful guarantee: no thread can ever stall the whole system, no matter how slow, preempted, or badly-timed it is.

The price is subtlety — ABA bugs, memory ordering, and proofs of linearizability lurk where a mutex would hide them. But for the JVMs, kernels, and trading systems of the world, that subtlety is worth it. Next time a server handles a million requests per second without grinding to a halt, there is a very good chance a CAS loop somewhere in the stack is the reason why.