MPSC Lock-Free Queue

Overview

This is a lock-free, thread-safe queue where multiple producers can push data concurrently and a single consumer thread pops from it.

It is typically implemented as a singly-linked list where:

Each producer creates a new node and links it to the tail.
The consumer traverses and pops from the head.
The head/tail pointers must be updated atomically.

Requirements

Thread-safe push() from multiple threads
Single-threaded pop() from the consumer
Must use atomic operations (no mutex or blocking)

Hints

Use a dummy node as the initial head.
tail is updated using std::atomic<Node*>
head is only modified by the consumer.
On push(), atomically exchange tail and link the node.
On pop(), advance head if next exists.

This pattern is lock-free and supports high-throughput scenarios.

Implement a multiple-producer, single-consumer lock-free queue using a linked list.

cpp

#include <atomic>

template <typename T>
class MPSCQueue {
public:
    MPSCQueue();
    ~MPSCQueue();

    void push(const T& item);
    bool pop(T& item);

private:
    struct Node {
        T value;
        std::atomic<Node*> next;
        Node(const T& val) : value(val), next(nullptr) {}
    };

    std::atomic<Node*> tail_;
    Node* head_; // only used by consumer
};

Mark as complete