How to safely overwrite data in a full circular_buffer in C++

I currently try to wrap my head around how to safely handle the case that a circular buffer is full and the producer wants to insert data into it. The reason is that I have a classic producer-consumer problem with a camera (producer) producing images and a viewer (consumer) showing them, both running in their own thread. Since I do not want to limit the cameras frame rate (maybe that is not the best idea, but let's assume it is), the producer might at some point overwrite images that the consumer has not yet processed. As the images might be rather large, I would opt to not return them by value, but by reference or pointer. So once the buffer is full, it might occur that the producer would overwrite an image to which the consumer currently holds a pointer, probably even while the consumer reads its memory location. This, of course, is a behaviour that needs to be avoided, as the consumer does not expect to have the data changed under his fingers.

However, I wonder what would actually be the behaviour one would expect, and which would be the best, most encapsulated solution for this.

Since limiting the cameras frame rate is not desired, it would not be an option to simply pause the producer with a mutex or semaphore once it attempts to overwrite active images. So the only solution I can think of here is to skip the image currently handled by the consumer and overwrite the second oldest image instead. However, for this one would need a mechanism to indicate that the image is currently used. Maybe returning a std::shared_ptr when requesting an image and checking its use_count on overwriting images would be an option.

I tried to find similar questions, but couldn't. Any input how to solve this properly, or if this question is a non-issue since my basic idea is flawed, would help. Thanks a lot!

Solution

I think it's easiest to abandon the idea of a true circular buffer. The main motivation for circular buffers is that they are the most efficient way to represent large queues of small records, since there is no per-record memory overhead (a typical example is an audio buffers with 16 or 32-bit samples), but this overhead becomes negligible once your records are sufficiently large, as in your use case: presumably, buffers containing video frames are quite large (kilobytes if not megabytes?), so there is little reason to keep them in contiguous memory. You might as well allocate the buffers on the heap and store pointers in a queue-like data structure.

For your problem it suffices to have:

A free list of pre-allocated buffers.
A list of filled buffers to be consumed.

Then the consumer does something like:

Grab a buffer from the front of list 2 (blocking if empty).
Process it.
Return the buffer to list 1 to be reused.

And the producer:

Grab a buffer from list 1, or if it is empty, grab it from the front of list 2 instead (this is how you end up overwriting the oldest filled buffer).
Fill the buffer.
Add the buffer to the back of list 2 to be processed.

The lists can be implemented simply with std::deque<buffer*>. Smart pointers are not necessary here because at no point is any buffer being shared: the buffer is either in the free list, in the queue, owned by the producer, or owned by the consumer, with nothing in between. Maybe std::unique_ptr<> is useful to guarantee that each buffer is freed exactly once.

What is important, however, is that access to the deques (or whatever data structure you decide to use) is synchronized. A simple mutex will probably suffice (combined with a semaphore to handle the cases where the consumer needs to block and wait in step 1). There are also lockless implementations of queues which you can use, but it's highly unlikely that the performance difference is big enough to matter for this use case.

Note that you can still allocate all the buffers in contiguous memory if you want. The important part is that you only store pointers in the queues so that synchronized access can be extremely fast.