Why Your Lock-Free Queue Starves Threads

You've used lock-free MPMC queues before. Crossbeam in Rust, Disruptor in Java, Vyukov's ring buffer in C++. Fast, elegant — and hiding a problem most engineers never notice: under heavy contention, individual threads can starve indefinitely.

Why this matters

Lock-free means the system always makes progress. It does not mean your thread makes progress. If eight producers hammer a queue and one keeps losing the CAS race, that thread retries for an unbounded number of attempts.

In latency-critical code — game loops, trading engines, audio pipelines — one starving thread means a dropped frame, a missed tick, a glitch users notice instantly.

How it works

A bounded MPMC ring buffer assigns each slot a sequence number. Producers and consumers CAS on these numbers to claim slots. Simple and fast — until contention spikes and one thread starts losing repeatedly.

Bounded waiting adds a fairness layer. Instead of letting a thread lose the CAS race forever, the algorithm counts interferences. Past a threshold, the thread gets priority. "Eventually completes" becomes "completes within N steps."

The cost is small: an extra atomic read and conditional branch per slot claim. Typically 5–15% overhead compared to an unfair queue.

Where this helps

• Real-time audio — a starving consumer thread causes audible dropouts
• High-frequency trading — order updates must reach matching engines within microseconds; unbounded retries violate latency SLAs
• Game servers — 64+ threads feeding a central event queue; starvation means a frozen frame for one player
• Packet processing — DPDK pipelines where every microsecond of jitter means queued or dropped packets

Watch out

Bounded waiting is not wait-free. Wait-free guarantees completion in bounded steps. Bounded waiting guarantees completion after bounded interferences. The distinction matters in hard real-time systems.

Cache contention still scales with thread count. A 32-thread producer pool on a dual-socket NUMA machine pays cross-socket latency on every CAS. Partition your queues before you optimize fairness.

If your workload rarely hits high contention, the overhead is not worth it. Measure first.

Try it yourself

The Vyukov bounded MPMC queue — the foundation bounded waiting builds on — in under 50 lines of Rust:

use std::sync::atomic::{AtomicUsize, Ordering};
use std::cell::UnsafeCell;

const BOUND: usize = 1024;

struct Slot {
    seq: AtomicUsize,
    data: UnsafeCell>,
}

pub struct MpmcQueue {
    buf: Box<[Slot]>,
    head: AtomicUsize,
    tail: AtomicUsize,
}

unsafe impl Send for MpmcQueue {}
unsafe impl Sync for MpmcQueue {}

impl MpmcQueue {
    pub fn new() -> Self {
        let buf: Vec<_> = (0..BOUND).map(|i| Slot {
            seq: AtomicUsize::new(i),
            data: UnsafeCell::new(None),
        }).collect();
        Self { buf: buf.into(), head: AtomicUsize::new(0), tail: AtomicUsize::new(0) }
    }

    pub fn push(&self, val: T) -> Result<(), T> {
        let mut pos = self.tail.load(Ordering::Relaxed);
        loop {
            let slot = &self.buf[pos % BOUND];
            let diff = slot.seq.load(Ordering::Acquire) as isize - pos as isize;
            if diff == 0 && self.tail
                .compare_exchange_weak(pos, pos + 1, Ordering::Relaxed, Ordering::Relaxed).is_ok() {
                unsafe { *slot.data.get() = Some(val); }
                slot.seq.store(pos + 1, Ordering::Release);
                return Ok(());
            } else if diff < 0 { return Err(val); }
            else { pos = self.tail.load(Ordering::Relaxed); }
        }
    }

    pub fn pop(&self) -> Option {
        let mut pos = self.head.load(Ordering::Relaxed);
        loop {
            let slot = &self.buf[pos % BOUND];
            let diff = slot.seq.load(Ordering::Acquire) as isize - (pos + 1) as isize;
            if diff == 0 && self.head
                .compare_exchange_weak(pos, pos + 1, Ordering::Relaxed, Ordering::Relaxed).is_ok() {
                let val = unsafe { (*slot.data.get()).take() };
                slot.seq.store(pos + BOUND, Ordering::Release);
                return val;
            } else if diff < 0 { return None; }
            else { pos = self.head.load(Ordering::Relaxed); }
        }
    }
}

Add a per-thread interference counter. When it crosses a threshold, yield priority to the losing thread — that is the leap from lock-free to bounded waiting.

TL;DR

• What: Lock-free MPMC queues guarantee system-wide progress, but individual threads can starve under heavy contention. Bounded waiting caps how long any thread waits.
• Why: In latency-critical systems, one starving thread causes dropped frames, missed ticks, or stale data. Predictable worst-case latency beats high average throughput.
• Try: Load-test your concurrent queues under high contention and check for tail-latency outliers. Starvation hides in the P99.