简单的无锁堆栈

Question

最近发现了这样的java-concurrency面试任务:

使用两种方法编写简单的无锁Stack:push和pop.

我做了专注:

import java.util.concurrent.atomic.AtomicInteger;


public class Stack {
    private AtomicInteger count = new AtomicInteger(-1);
    private Object[] data = new Object[1000];

    public void push(Object o) {
        int c = count.incrementAndGet();
        data[c] = o;
    }

    public Object pop() {
        Object top;
        int c;
        while (true) {
            c = count.get();
            if (c == -1) return null;
            top = data[c];
            if (count.compareAndSet(c, c-1))
                return top;
        }
    }
}

是否与预期的方法类似？或者"无锁堆栈"意味着什么不同？请帮助一个java面试新手.

Answer 1

你当然开始朝着正确的方向前进,考虑使用Java的原子整数和原子函数.因此,这将是一个无锁堆栈,如:没有显式锁.

然而,在同时访问时它仍然是不正确的,并且证明这一点相对简单:假设你的push()线程在获取计数和将新元素添加到堆栈(data [c] = o)之间阻塞,并且在与此同时,一个pop()线程出现,获得更高的数量,并弹出......什么？无论在堆栈中该位置的内存中发生了什么,而不是Object o(因为它尚未插入).

这就是无锁,阵列支持堆栈的问题,你有两件理论上需要调整的东西,特定单元格的数量和内容,你不能同时原子地做这两件事.我不知道那里有任何无锁阵列支持的堆栈算法.

有链接列表支持的堆栈算法,虽然它是无锁的,因为在这种情况下,您可以创建一个新节点,为其分配内容,并且您只有一个操作可以原子执行:更改顶部指针.

如果你对这个论点感兴趣,那么最好的文学作品是Shavit和Herlihy的"多处理器编程艺术",它描述了许多不同的数据结构,包括无锁和基于锁的数据结构.我现在找不到任何纸张详细描述"通常的"无锁堆栈算法,尽管Maged Michael在他的SMR论文中提到了这一点,第8页,第4.2点,我自己做了一个C99实现.