Multi threaded circular buffer

Question

I've written a circular buffer with multithreaded write and single read ability:

public class RingBuffer<E> extends AbstractList<E> implements RandomAccess {

    class Pointer {
        int p = 0;

        public int getPointer(){
            return this.p;
        }

        public void increasePointer(int p) {
            this.p = p;
        }
    }

    private final int n;
    private final List<E> rb;

    private int size = 0;
    private Pointer ptr_w = new Pointer();
    private Pointer ptr_r = new Pointer();

    public RingBuffer(int n) {
        this.n = n + 1;
        this.rb = new ArrayList<E>(Collections.nCopies(this.n, (E) null));
    }

    public int size() {
        return this.size;
    }

    private int wrap(int i) {
        int m = i % this.n;
        return (m < 0) ? m += this.n : m;
    }

    @Override
    public E get(int i) {
        return (this.size == 0) ? null : this.rb.get(i);
    }

    @Override
    public E remove(int i) {
        E e = this.get(this.ptr_r.getPointer());
        if(e != null) {
            this.rb.set(this.ptr_r.getPointer(), null);
            setPointer(false, this.ptr_r);
        }
        System.out.println("Read: " + this.ptr_r.getPointer() + " " + size());
        return e;
    }

    @Override
    public synchronized boolean add(E e) {
        if (size() == this.n - 1)
            throw new IllegalStateException("Cannot add element. Ringbuffer is filled.");
        this.rb.set(this.ptr_w.getPointer(), e);
        setPointer(true, this.ptr_w);
        System.out.println("Write: " + this.ptr_w.getPointer() + " " + size());
        return true;
    }

    private synchronized void setPointer(boolean a, Pointer ptr) {
        this.size = (a) ? this.size + 1 : this.size - 1;
        ptr.increasePointer(wrap(ptr.getPointer() + 1));
    }
}

I would like to know what I could improve and what you think about the code. I'm new to multithreading and would love to get some feedback.

Answer 1

I highly recommend Java Concurrency in Practice by Brian Goetz et al. This will give you a solid foundation for building multi-threaded Java applications.

The biggest problem with RingBuffer is that it is not thread-safe. You must synchronize all read and write operations to be certain to see the latest values for fields. This doesn't mean you have to lock the structure the entire time.

This is explained far better in the book than I can here. The short of it is that without synchronization via memory barriers, the JVM is free to cache values read in one thread and miss writes happening in another.

1. Thread A calls get and sees that the buffer is empty.
2. Thread B calls add which updates the pointer.
3. Thread A calls get again, but without a memory barrier the cached pointer value tells it that the queue is still empty.

You'll need to add synchronization to guard any access of the pointers and size. Sometimes you can merely add synchronized to the method, but this usually hurts performance. You want to shrink your synchronized blocks to the bare minimum; prefer using synchronized (<lock>) blocks over synchronized methods.

Here are some other suggestions unrelated to concurrency:

1. RingBuffer composes an ArrayList so it should not extend AbstractList itself. It shouldn't even implement the basic List interface nor RandomAccess because it doesn't truly support the get operation. It should implement Queue instead.

2. As written, get allows reading outside the buffer. Are you sure you want to support this? See (1) above.

3. You don't need a class to hold an integer pointer given that it is internal to RingBuffer. A simple int is sufficient.

4. The modulo operator % should handle negative values already (test this!) so wrap could be simplified.