C++ Academy · Lesson

Lock-Free Queue Implementation

Walk through the design of a single-producer single-consumer lock-free queue.

Lock-Free Queue Implementation is a free C++ Academy lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the C++ Academy learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.

Why Lock-Free Queues?

Queues with mutexes can become bottlenecks under high contention. A lock-free queue lets producers and consumers progress concurrently.

SPSC vs MPMC

Two flavors:

SPSC — single producer, single consumer (simplest, fastest)
MPMC — multiple producer, multiple consumer (most general)

SPSC is the natural choice when you control both ends.

SPSC Ring Buffer Sketch

A circular buffer with two indices: head (consumer) and tail (producer). Each side updates its own index.

template <typename T, size_t N>
class SpscQueue {
    T buffer_[N];
    std::atomic<size_t> head_{0};
    std::atomic<size_t> tail_{0};
public:
    bool push(const T& v);
    bool pop(T& v);
};

SPSC push

Producer checks free slots, writes, then publishes by updating tail.

bool push(const T& v) {
    const size_t t = tail_.load(std::memory_order_relaxed);
    const size_t next = (t + 1) % N;
    if (next == head_.load(std::memory_order_acquire))
        return false;     // full
    buffer_[t] = v;
    tail_.store(next, std::memory_order_release);
    return true;
}

SPSC pop

Consumer checks for data, reads, then publishes by updating head.

bool pop(T& v) {
    const size_t h = head_.load(std::memory_order_relaxed);
    if (h == tail_.load(std::memory_order_acquire))
        return false;     // empty
    v = buffer_[h];
    head_.store((h + 1) % N, std::memory_order_release);
    return true;
}

Memory Order Pairing

The release-store on tail synchronizes with the acquire-load on tail in the consumer (and vice versa). Without the right ordering, the data writes could be reordered after the index update.

Cache Line Padding

To avoid false sharing, place head_ and tail_ on separate cache lines (typically 64 bytes apart). Use alignas.

alignas(64) std::atomic<size_t> head_{0};
alignas(64) std::atomic<size_t> tail_{0};

MPMC: Much Harder

Multiple producers or consumers require additional coordination — usually with CAS loops on shared indices. Many designs exist (Vyukov queue, MS-queue, Hazard-Pointer-based).

Boost.Lockfree

Production-quality lock-free queues are hard. Use Boost.Lockfree or Folly s ProducerConsumerQueue rather than rolling your own.

Trade-offs

Lock-free queues:

Higher throughput under contention
Bounded latency (no waiting for a lock)
Much harder to write and debug
Memory ordering bugs are silent and elusive

Testing Lock-Free Code

Use ThreadSanitizer (-fsanitize=thread) to catch data races. Use stress tests with random sleep insertions to expose ordering bugs.

When Mutex Is Enough

Most applications do not need lock-free queues. Measure first — a well-implemented mutex-protected queue often performs adequately, especially with batched processing.

Quick Check

What is false sharing, and why pad head_ and tail_?

Recap

A lock-free SPSC queue uses a ring buffer with producer-owned tail and consumer-owned head. Use acquire/release ordering and pad indices to separate cache lines. For MPMC, prefer a tested library.

Frequently asked questions

Is the “Lock-Free Queue Implementation” lesson free?

Yes — the full text of “Lock-Free Queue Implementation” is free to read here on the web, and the C++ Academy course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the C++ Academy course, upgrade to CoddyKit PRO.

What will I learn in “Lock-Free Queue Implementation”?

Walk through the design of a single-producer single-consumer lock-free queue. You practise C++ Academy with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.

Do I need any experience to start C++ Academy?

No prior experience is required. C++ Academy on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.

How long does the “Lock-Free Queue Implementation” lesson take?

Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.

Can I write and run code in this C++ Academy lesson?

Yes. Every C++ Academy lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.

All lessons in this course

← Back to C++ Academy