我正在考虑实现一个无锁环形数组。其中一个问题是以无锁的方式维护头指针和尾指针。我想到的代码如下：
int circularIncrementAndGet(AtomicInteger i) {
i.compareAndSet(array.length - 1, -1);
return i.incrementAndGet();
}
那么我会做类似这样的事情：
void add(double value) {
int idx = circularIncrementAndGet(tail);
array[idx] = value;
}
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;
}
请查看disruptor：http://lmax-exchange.github.io/disruptor/，它是Java中的开源无锁循环缓冲区。
是的，存在竞态条件。
假设 i = array.length - 2，并且两个线程进入 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
当第二个线程到达array[idx] = value时（以及在i溢出之前的所有后续调用add()），会导致ArrayIndexOutOfBoundsException。
@Peter Lawrey提出的解决方案不会遇到这个问题。
可以实现循环数组/队列。
入队线程拥有尾指针。出队线程拥有头指针。除了一个条件外，这两个线程到目前为止没有共享任何状态，因此没有问题。
该条件是测试是否为空或已满。
考虑空队列表示head == tail; 考虑满队列表示tail == head - 1模数组大小。Enqueue必须检查队列是否已满，dequeue必须检查队列是否为空。您需要在数组中浪费一个索引来检测full和empty之间的差异-如果您将其入队到最后一个桶中，则full将是head == tail，而empty将是head == tail，现在您死锁了-您认为自己同时为空和满，因此不会完成任何工作。