C++ Academy · Lesson

Lock-Free Queue Implementation

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

Lesson 3 of 414 steps

Lock-Free Queue Implementation is a free C++ Academy lesson on CoddyKit. This is lesson 3 of 4. Any 3 lessons of this learning path are free to read in full — after that, CoddyKit PRO unlocks every lesson, plus hands-on practice with a built-in code editor and a 24/7 AI tutor. It is part of the C++ Academy learning path, and your progress syncs across the web and the CoddyKit app. The C++ Academy course includes 4 lessons in total.

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_?

Answer it in the interactive lesson

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.

Free to start

Learn C++ with an AI tutor — free

Write and run real code in your browser, get instant help from a 24/7 AI tutor, and pick up where you left off on the web or in the app.

Courses: 51
Lessons: 203

Start learning free View the full course

Frequently Asked Questions

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

Yes — any 3 lessons of the C++ Academy learning path, including “Lock-Free Queue Implementation”, are free to read in full here on the web. After that, CoddyKit PRO unlocks every lesson, plus interactive practice with a built-in code editor and a 24/7 AI tutor. The C++ Academy course includes 4 lessons in total.

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, so you can start here or from the beginning and move at your own pace. This is lesson 3 of 4.

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