Я возился с простой реализацией стека без блокировок в Java.
редактировать: см. Исправленную / рабочую версию ниже
Видите ли вы какие-либо проблемы с этой реализацией?
Подобные реализации на родных языках, похоже, страдают от проблемы ABA , но я не уверен, если это проблема здесь; очевидно, что обработка указателей не выполняется напрямую в Java, и, учитывая все, что мне нужно, это конец стека как для pop, так и для push, я не вижу, как «пропущенные» какие-либо изменения в любом элементе не-tail стека могут вызвать проблемы .
public class LockFreeStack<T extends LockFreeStack.StackItem<T>>
{
public abstract static class StackItem<SELF extends StackItem<SELF>>
{
volatile SELF next;
// .. data ..
}
final AtomicReference<T> top = new AtomicReference<T>(null);
public void push(T item)
{
T localTop;
do {
localTop = top.get();
item.next = localTop;
} while(!top.compareAndSet(localTop, item));
}
public T pop()
{
T localTop;
do {
localTop = top.get();
} while(localTop != null && !top.compareAndSet(localTop, localTop.next));
return localTop;
}
}
Но вот что я не понимаю. Я написал простой тест, который запускает несколько потоков; каждый из них извлекает элементы из ранее существовавшего LockFreeStack и (позже, из того же потока, который его вытолкнул) выталкивает их обратно.
После его срабатывания я увеличиваю атомный счетчик, и, прежде чем нажать его обратно, я уменьшаю его. Так что я всегда ожидал, что счетчик будет равен 0 (сразу после уменьшения / сразу перед возвратом в стек) или 1 (сразу после появления и увеличения).
Но это не то, что происходит ...
public class QueueTest {
static class TestStackItem extends LockFreeStack.StackItem<TestStackItem>
{
final AtomicInteger usageCount = new AtomicInteger(0);
public void inc() throws Exception
{
int c = usageCount.incrementAndGet();
if(c != 1)
throw new Exception(String.format("Usage count is %d; expected %d", c, 1));
}
public void dec() throws Exception
{
int c = usageCount.decrementAndGet();
if(c != 0)
throw new Exception(String.format("Usage count is %d; expected %d", c, 0));
}
}
public final LockFreeStack<TestStackItem> testStack = new LockFreeStack<TestStackItem>();
public void test()
{
final int NUM_THREADS = 4;
for(int i = 0; i < 10; i++)
{
TestStackItem item = new TestStackItem();
testStack.push(item);
}
Thread[] threads = new Thread[NUM_THREADS];
for(int i = 0; i < NUM_THREADS; i++)
{
threads[i] = new Thread(new TestRunner());
threads[i].setDaemon(true);
threads[i].setName("Thread"+i);
threads[i].start();
}
while(true)
{
Thread.yield();
}
}
class TestRunner implements Runnable
{
@Override
public void run() {
try {
boolean pop = false;
TestStackItem lastItem = null;
while (true) {
pop = !pop;
if (pop) {
TestStackItem item = testStack.pop();
item.inc();
lastItem = item;
} else {
lastItem.dec();
testStack.push(lastItem);
lastItem = null;
}
}
} catch (Exception ex)
{
System.out.println("exception: " + ex.toString());
}
}
}
}
выдает недетерминированные исключения, например,
exception: java.lang.Exception: Usage count is 1; expected 0
exception: java.lang.Exception: Usage count is 2; expected 1
или из другого прогона
exception: java.lang.Exception: Usage count is 2; expected 0
exception: java.lang.Exception: Usage count is 3; expected 1
exception: java.lang.Exception: Usage count is 3; expected 1
exception: java.lang.Exception: Usage count is 2; expected 1
Таким образом, здесь должна происходить какая-то проблема типа расы.
Что здесь не так - действительно ли это связано с ABA (и если да, то как именно?) Или я что-то упускаю?
Спасибо!
ПРИМЕЧАНИЕ. Это работает, но, похоже, не является хорошим решением. Это не лишает мусора (StampedAtomicReference создает объекты внутри), и при этом не похоже, что выгода от отсутствия блокировки действительно окупается; в моих тестах это было не очень быстро в однопоточной среде, а при одновременном тестировании с 6 потоками значительно отставало от установки блокировок функций push / pop
на основе предложенного ниже решения, это действительно была проблема ABA, и это небольшое изменение обойдет это:
public class LockFreeStack<T extends LockFreeStack.StackItem<T>>
{
public abstract static class StackItem<SELF extends StackItem<SELF>>
{
volatile SELF next;
// .. data ..
}
private final AtomicStampedReference<T> top = new AtomicStampedReference<T>(null, 0);
public void push(T item)
{
int[] stampHolder = new int[1];
T localTop;
do {
localTop = top.get(stampHolder);
item.next = localTop;
} while(!top.compareAndSet(localTop, item, stampHolder[0], stampHolder[0]+1));
}
public T pop()
{
T localTop;
int[] stampHolder = new int[1];
do {
localTop = top.get(stampHolder);
} while(localTop != null && !top.compareAndSet(localTop, localTop.next, stampHolder[0], stampHolder[0]+1));
return localTop;
}
}