ring buffer without priority inversion

Question

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?

Answer 1

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.

Answer 2

Boost provides a circular buffer, but it's not thread safe. Unfortunately, I don't know of any implementation that is.

The upcoming C++ standard adds atomic operations to the standard library, so they'll be available in the future, but they aren't supported by most implementations yet.

I don't see any cross-platform solution to keeping count sane while both threads are writing to it, unless you implement locking.

Normally, you would probably use a messaging system and force the low priority thread to request that the high priority thread make updates, or something similar. For example, if the low priority thread consumes 15 bytes, it should ask the high priority thread to reduce the count by 15.

Essentially, you would limit 'write' access to the high priority thread, and only allow the low priority thread to read. This way, you can avoid all locking, and the high priority thread won't have to worry about waiting for a write to be completed by the lower thread, making the high priority thread truly high priority.