CODEWITHSUNDEEP
javaandroidmultithreadingatomiclock-free
Louis Jenkins
Louis Jenkins

Reputation: 391

Creating an Atomic RingBuffer in Java

I was thinking of how I would go about implementing a thread-safe RingBuffer in Java and Android (as for some reason there is none, even after all these years, not even a circular queue. So, no (Circular/Ring)ByteBuffer, nor (Circular/Ring)(Buffer/Queue).

Even majority of the RingBuffer implementations that are third party are said to be not thread safe, which makes me think it really isn't as simple as I think it is going to be. What I was thinking about was doing something like this:

Would this work, and better yet, would it yield any benefits over simply synchronizing access to the collection?

A small code sample/pseudocode (has not been run yet, and I do not even know how to remotely test an atomic data structure, I plan on using it for buffering/streaming media but I haven't gotten that far yet as I need to create this first) can be found here. I have comments/documentation that details my concerns there.

Lastly, to address a possible "Why" question, as in "Why do you need such performance", I'll be truthful. I have always found data structures, especially atomic/lock-free data structures very interesting, and I found this as a very good exercise to learn, plus I always wanted to create a Ring Buffer. I could have just "synchronized" everything, however I do also value performance.

Upvotes: 2

Views: 1058

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59194

Multiple reader/multiple writer ring buffers are tricky.

Your way doesn't work, because you can't update that start/end position AND the array contents atomically. Consider adding to the buffer: If you update the end position first, then there is a moment before you update the array when the buffer contains an invalid item. If you update the array first, then there's nothing to stop simultaneous additions from stomping on the same array element.

There are lots of ways to deal with these problems, but the various ways have different trade-offs, and you have better options available if you can get rid of the multiple reader or multiple writer requirement.

If I had to guess at why we don't have a concurrent ring buffer in the standard library, I'd say it's because there is no one best way to implement it that is going to be good for most scenarios. The data structure used for ConcurrentLinkedQueue, in contrast, is simple and elegant and an obvious choice when a concurrent linked list is required.

Upvotes: 1

Related Questions