Lock Free Circular Array

Question

I am thinking about implementing a lock free circular array. One problem is maintaining the head and tail pointers in a lock free manner. The code I have in mind is:

int circularIncrementAndGet(AtomicInteger i) {
    i.compareAndSet(array.length - 1, -1);
    return i.incrementAndGet();
}

Then I would do something like:

void add(double value) {
    int idx = circularIncrementAndGet(tail);
    array[idx] = value;
}

(Note that if the array is full old values will be overwritten, I am fine with that).

Does anyone sees a problem with this design? I suspect there might be a race condition I am not seeing.

Answer 1

A simpler approach is to use a power of 2 size and do the following.

 final double[] array;
 final int sizeMask;
 final AtomicInteger i = new AtomicInteger();

 public CircularBuffer(int size) {
      assert size > 1 && ((size & (size -1)) == 0); // test power of 2.
      array = new double[size];
      sizeMask = size -1;
 }

 void add(double value) {
     array[i.getAndIncrement() & sizeMask] = value;
 }

Answer 2

Check out disruptor : http://lmax-exchange.github.io/disruptor/, it's an open-source lock-free circular buffer in Java.

Answer 3

Yes, there is a race condition.

Say i = array.length - 2, and two threads enter circularIncrementAndGet():

Thread 1: i.compareAndSet(array.length - 1, -1) results in i = array.length - 2
Thread 2: i.compareAndSet(array.length - 1, -1) results in i = array.length - 2
Thread 1: i.incrementAndGet() results in i = array.length - 1
Thread 2: i.incrementAndGet() results in i = array.length

leading to an ArrayIndexOutOfBoundsException when Thread 2 reaches array[idx] = value (and on all subsequent calls to add() until i overflows).

The solution proposed by @Peter Lawrey does not suffer from this problem.

Answer 4

If you stick with the following constraints:

• Only one thread is allowed to modify the head pointer at any time
• Only one thread is allowed to modify the tail pointer at any time
• Dequeue-on-empty gives a return value indicating nothing was done
• Enqueue-on-full gives a return value indicating nothing was done
• You don't keep any count of how many values are stored in the queue.
• You 'waste' one index in the array that will never be used, so that you can tell when the array is full or empty without having to keep count.

It is possible to implement a circular array/queue.

The enqueuing thread owns the tail pointer. The dequeueing thread owns the head pointer. Except for one condition, these two threads don't share any state so far, and so there are no problems.

That condition is testing for emptyness or fullness.

Consider empty to mean that head == tail; Consider full to mean tail == head - 1 modulo array size. Enqueue has to check to see if the queue is full, dequeue has to check to see if the queue is empty. You need to waste one index in the array to detect the difference between full and empty - if you enqueued into that last bucket, then full would be head == tail and empty would be head == tail and now you deadlock - you think you're empty and full at the same time, so no work would get done.

In performing these checks, its possible that one value could be updated while being compared. However since these two values are monotonically increasing, there is no correctness problem:

• If, in the dequeue method, the head == tail computes to be true during the comparison, but tail moves forward just afterward, no problem - you thought the array was empty when it actually wasn't, but no big deal, you'll just return false from the dequeue method and try again.
• If, in the enqueue method, the tail == head - 1 computes to be true, but just after so the head increments, then you'll think the array was full when it really wasn't, but again, no big deal, you'll just return false from enqueue and try again.

This is the design used behind the implementation I found in Dr. Dobb's years ago, and it has served me well:

http://www.drdobbs.com/parallel/lock-free-queues/208801974