Search code examples
c++concurrencycircular-buffer

ring buffer without priority inversion


I have a high-priority process that needs to pass data to a low-priority process. I've written a basic ring buffer to handle the passing of data:

class RingBuffer {
  public:
    RingBuffer(int size);
    ~RingBuffer();

    int count() {return (size + end - start) % size;}

    void write(char *data, int bytes) {
      // some work that uses only buffer and end
      end = (end + bytes) % size;
    }

    void read(char *data, int bytes) {
      // some work that uses only buffer and start
      start = (start + bytes) % size;
    }

  private:
    char *buffer;
    const int size;
    int start, end;
};

Here's the problem. Suppose the low-priority process has an oracle that tells it exactly how much data needs to be read, so that count() need never be called. Then (unless I'm missing something) there are no concurrency issues. However, as soon as the low-priority thread needs to call count() (the high-priority thread might want to call it too to check if the buffer is too full) there is the possibility that the math in count() or the update to end is not atomic, introducing a bug.

I could put a mutex around the accesses to start and end but that would cause priority inversion if the high-priority thread has to wait for the lock acquired by the low-priority thread.

I might be able to work something out using atomic operations but I'm not aware of a nice, cross-platform library providing these.

Is there a standard ring-buffer design that avoids these issues?


Solution

  • What you have should be OK, as long as you adhere to these guidelines:

    • Only one thread can do writes.
    • Only one thread can do reads.
    • Updates and accesses to start and end are atomic. This might be automatic, for example Microsoft states:

    Simple reads and writes to properly-aligned 32-bit variables are atomic operations. In other words, you will not end up with only one portion of the variable updated; all bits are updated in an atomic fashion.

    • You allow for the fact that count might be out of date even as you get the value. In the reading thread, count will return the minimum count you can rely on; for the writing thread count will return the maximum count and the true count might be lower.