Ring buffer for a wait-free producer and a blocking consumer

3
votes

I have a producer thread that produces objects at a rate that might (temporarily) be too fast for the consumer thread to consume. Therefore, I'd like a FIFO that buffers the remaining work. Once the FIFO is full, the producer shall simply retire or retry later. Also, I would like to be able to notify the consumer that no more work is to be done (without enqueuing a special object into the FIFO). The producer shall not get slowed down and the consumer shall not waste CPU cycles, so I have the following requirements:

  • Circular ring buffer of fixed size.
  • Producer shall never wait: It needs to be able to enqueue elements as quickly as possible.
  • Consumer shall be able to block: No busy-waiting for a potentially slow producer. A hybrid lock would be nice.

I am envisioning the following C++ class:

template <typename T, std::size_t N>
class spsc_circular_half_blocking {
    std::array<T, N> buffer;
    // bookkeeping, atomics, mutexes etc. go here
public:
    bool try_push(const T&); // returns whether object could be enqueued
    void notify(); // notifies consumer
    bool wait_pop(T&); // returns whether object was dequeued or notification was received
};

Being able to modify the elements in-place would be nice. It may also use dynamic allocation of the buffer (e.g. size is passed to constructor, buffer is a unique_ptr).

Now for my questions. Is this thing even possible (on x86, at least)?

  • If yes, how would it work? I would really like some implementation, preferably but not necessarily C++.
  • If no, why not?

Pointers to related material, even if it does not exactly fulfill my needs, would also be greatly appreciated.

2
c++multithreadingproducer-consumerlock-freewait-free
You can use signalling mechanism to notify the consumer. – yadhu
Look at github.com/cameron314/readerwriterqueue . It has a blocking version. – rsjaffe
I haven't seen any papers about lock-free circular buffers so it is very likely that such are not yet invented. Lock-free queues have been around for more than two decades. Anyway asking for suggesting off-siteresources is off topic here. – Öö Tiib
Did you benchmark a blocking version with a mutex and a condition variable and found out that it was not fast enough? – Maxim Egorushkin
@Maxim I have a poorly performing solution involving two wait-free queues in a very contrived way which I am trying to improve on. I really need some form of try_push because in my case, it is not sensible to continue operation once the queue limit is reached. The producer never having to wait for the consumer is a strict requirement. – purefanatic

2 Answers

4
votes

One solution would be to use boost single-producer single-consumer queue with you own signalling and blocking.

0
votes

Google found this, no idea about it but worth examining perhaps:

Wait-free multiproducer multiconsumer ring buffer:

https://www.osti.gov/servlets/purl/1531271