0

A very naive array based circular buffer implementation,

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;

public class SomeRingBuffer {

    private volatile String[] holder;
    private AtomicInteger cursor = new AtomicInteger(-1);

    public SomeRingBuffer(int capacity) {
        holder = new String[capacity];
    }

    public void add(String data) {
        if (data == null) {
            return; // do nothing
        }

        int updatedCursor = cursor.updateAndGet(i -> (i + 1) % holder.length);
        holder[updatedCursor] = data;
        holder = holder; // holder is marked volatile, intentional write barrier
    }

    public List<String> getLastN(int n) {
        if (n < 1 || n > holder.length) {
            n = holder.length;
        }

        List<String> result = new ArrayList<>(n);
        int current = cursor.get();

        while (n > 0) {
            result.add(holder[current--]);
            if (current < 0) {
                current = holder.length - 1;
            }

            n--;
        }

        return result;
    }

}

It is supposed to be non-blocking and thread safe. Synchronisation is achieved using AtomicInteger, while memory visibility is ensured via volatile r/w.

Is there any problem from concurrency point of view? As we are writing to array elements, is memory visibility here guaranteed among the threads?

14
  • No. Because reading holder doesn't guarantee which slots of the array are safe to read afterwards. Commented Jun 24, 2022 at 11:22
  • 1
    If there is only one call to add and holder write already happened, getLastN will see the array slot properly written and the object itself properly published. Commented Jun 24, 2022 at 11:53
  • 1
    However, if there is any overlapping between add and getLastN, all bets are off. Commented Jun 24, 2022 at 11:56
  • 1
    Assuming that a statement like holder = holder; had an effect, is just wrong. A volatile write establishes a happens before relationship to subsequent reads but since all reads see the same value (as the reference doesn’t change), there is no way to tell whether a read is subsequent. The other thread could read the array reference before the writing threat performed the redundant write, hence, there is no happens before relationship. Commented Jun 27, 2022 at 10:23
  • 2
    There is no such thing as a “write barrier” in the specification. Hence, you can not assume that this statement that has no observable effect will “trigger write barrier”. There are JVMs using barriers as an implementation detail, still, even in those implementations, you need a pair of write barrier and read barrier in the right synchronization order to establish memory visibility. So even on those JVMs, a construct that can’t guaranty that the actions will happen in the right order does not establish the necessary happens-before relationship. Commented Jun 29, 2022 at 8:31

1 Answer 1

0

IMO there are following problems:

  1. update in add() is not atomic
    This was already discussed in the comments by @akarnokd and you: 1, 2
    But I would like to show one more example:

    • given:
      • buffer size is 10
      • 50 threads executing add()
      • 1 thread executing getLastN()
    • all 50 add()-threads simultaneously finished incrementing cursor and are writing now in holder[idx]

    As a result for every element of the holder there are 5 parallel writes by different threads without synchronization (i.e. data races).
    The elements returned by getLastN() can be any random combination of old and newly written values.

  2. getLastN() is not atomic
    While you are iterating over the elements of holder in one thread, other threads might update the buffer at the same time.
    As a result the elements returned by getLastN() might be from "different generations".
    This cannot happen in a single-threaded code — so this might be considered as non-thread-safe as well.
    (sometimes such "inconsistencies" are considered acceptable in concurrent algorithms, but then this should be explicitly documented)

Sign up to request clarification or add additional context in comments.

1 Comment

thanks for taking time to write this detailed analysis. Yes, if thread contention is much higher and appropriate buffer capacity is not chosen at the time of SomeRingBuffer object construction, the issue you highlighted is bound to happen. A trade off between memory usage and concurrency level. As I mentioned above, this is not at all a production code, something just for education purposes.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.