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?

Danner

Do you have any constraints on the platforms used? – Aslam

@Peter Let's assume x86 (where IIRC 32-bit writes to aligned addresses are atomic) though the more portable the better. – Danner

Here is a queue which operates mostly wait-free software.intel.com/en-us/articles/… – Aslam

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.

Apomorphine

Is there any risk of the compiler splitting the updates into a nonatomic sequence of steps? Ie, turning the last line of write() into end += bytes; end %= size;? – Danner

The compiler can compute the RHS non-atomically and depending on your platform might even store an int non-atomically (i.e. store a 16-bit int using two 8-bit writes on an 8-bit platform). – Aslam

@user168715, if you absolutely don't trust your compiler to do the right thing, create a volatile temporary variable to hold the calculation then copy it for the update. – Apomorphine

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.

Cleome

Answer 3

boost::interprocess offers cross-platform atomic functions in boost/interprocess/detail/atomic.hpp

Habanera