Introduction

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.

Try It

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.

<!-- Lock-Free Queue demo: producers enqueue, consumers dequeue, all via simulated CAS -->
<div class="controls">
  <div class="ctrl-group">
    <label>Producers</label>
    <div class="btn-row">
      <button id="add-producer" type="button">+ Producer</button>
      <button id="rem-producer" type="button" class="ghost">- Producer</button>
    </div>
  </div>
  <div class="ctrl-group">
    <label>Consumers</label>
    <div class="btn-row">
      <button id="add-consumer" type="button">+ Consumer</button>
      <button id="rem-consumer" type="button" class="ghost">- Consumer</button>
    </div>
  </div>
  <button id="reset-btn" type="button" class="ghost wide">Reset</button>
</div>
<div class="queue-vis" id="queue-vis">
  <span class="vis-label">HEAD</span>
  <div id="cells" class="cells"></div>
  <span class="vis-label-right">TAIL</span>
</div>
<div class="stats-row">
  <div class="stat"><span id="stat-enqueued">0</span><small>enqueued</small></div>
  <div class="stat"><span id="stat-dequeued">0</span><small>dequeued</small></div>
  <div class="stat accent"><span id="stat-retries">0</span><small>CAS retries</small></div>
  <div class="stat"><span id="stat-size">0</span><small>queue size</small></div>
</div>
<div class="log-box" id="log-box"></div>

/* Lock-Free Queue demo styles */
* { 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%; }
/* Queue visualization strip */
.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; }
/* Statistics row */
.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; }
/* Log box */
.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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// CAS simulation: the real CPU instruction reads, compares, and writes atomically.
// Here we simulate the race: if the tail moved between reading and writing, the CAS fails.

// Shared queue array (simulates the linked-list nodes)
const queue = [];
let enqueued = 0, dequeued = 0, retries = 0;
let producerCount = 1, consumerCount = 1;
let nextVal = 1;
const MAX_QUEUE = 12;
const MAX_LOG = 40;

// simulateCAS: attempt to append newItem to arr only if arr.length === expectedTail.
// If another producer already appended (arr.length changed), CAS fails and retries++ .
function simulateCAS(arr, expectedTail, newItem) {
  if (arr.length !== expectedTail) {
    retries++;
    return false;
  }
  arr.push(newItem);
  return true;
}

// simulateCASDeq: attempt to remove the head item only if the head position is valid.
// Returns the dequeued value or null if the queue was empty (no retry needed here).
function simulateCASDeq(arr, expectedHead) {
  if (arr.length === 0 || arr.length <= expectedHead) {
    return null;
  }
  if (arr.length !== expectedHead + arr.length) {
    // In a real implementation a failed dequeue CAS would increment retries too.
  }
  return arr.shift();
}

function log(msg, cls) {
  const box = document.getElementById('log-box');
  const line = document.createElement('div');
  line.className = cls;
  line.textContent = msg;
  box.appendChild(line);
  if (box.children.length > MAX_LOG) box.removeChild(box.firstChild);
  box.scrollTop = box.scrollHeight;
}

function renderQueue() {
  const cells = document.getElementById('cells');
  cells.innerHTML = '';
  const shown = queue.slice(-MAX_QUEUE);
  if (queue.length > MAX_QUEUE) {
    const ell = document.createElement('div');
    ell.className = 'cell';
    ell.textContent = '...';
    cells.appendChild(ell);
  }
  shown.forEach((v, i) => {
    const d = document.createElement('div');
    d.className = 'cell' + (i === shown.length - 1 ? ' new' : '');
    d.textContent = v;
    cells.appendChild(d);
  });
}

function updateStats() {
  document.getElementById('stat-enqueued').textContent = enqueued;
  document.getElementById('stat-dequeued').textContent = dequeued;
  document.getElementById('stat-retries').textContent = retries;
  document.getElementById('stat-size').textContent = queue.length;
}

// tick(): one simulation step — each producer tries to enqueue, each consumer tries to dequeue.
function tick() {
  for (let p = 0; p < producerCount; p++) {
    if (queue.length >= MAX_QUEUE) break;
    const val = nextVal++;
    const tail = queue.length;
    // Read tail, then attempt CAS; if tail moved, CAS returns false and we log a retry.
    const ok = simulateCAS(queue, tail, val);
    if (ok) {
      enqueued++;
      log(i18nFmt('P%p% enqueued %v%', { p: p + 1, v: val }), 'enq');
    } else {
      log(i18nFmt('P%p% CAS retry (tail moved)', { p: p + 1 }), 'retry');
    }
  }
  for (let c = 0; c < consumerCount; c++) {
    if (queue.length === 0) break;
    const head = 0;
    const val = simulateCASDeq(queue, head);
    if (val !== null) {
      dequeued++;
      log(i18nFmt('C%c% dequeued %v%', { c: c + 1, v: val }), 'deq');
    }
  }
  renderQueue();
  updateStats();
}

let intervalId = setInterval(tick, 600);

document.getElementById('add-producer').addEventListener('click', () => { producerCount = Math.min(producerCount + 1, 4); log(i18nFmt('Producers: %n%', { n: producerCount }), 'enq'); });
document.getElementById('rem-producer').addEventListener('click', () => { producerCount = Math.max(producerCount - 1, 0); log(i18nFmt('Producers: %n%', { n: producerCount }), 'enq'); });
document.getElementById('add-consumer').addEventListener('click', () => { consumerCount = Math.min(consumerCount + 1, 4); log(i18nFmt('Consumers: %n%', { n: consumerCount }), 'deq'); });
document.getElementById('rem-consumer').addEventListener('click', () => { consumerCount = Math.max(consumerCount - 1, 0); log(i18nFmt('Consumers: %n%', { n: consumerCount }), 'deq'); });
document.getElementById('reset-btn').addEventListener('click', () => {
  queue.length = 0; enqueued = 0; dequeued = 0; retries = 0; nextVal = 1;
  producerCount = 1; consumerCount = 1;
  document.getElementById('log-box').innerHTML = '';
  renderQueue(); updateStats();
  log('Simulation reset.', 'retry');
});

renderQueue();
updateStats();
Result
Console

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.

The Real Complexity

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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/lock-free-queues/Content licensed under CC BY-NC 4.0.