java - 简单无锁堆栈

Question

最近发现了这样一个java并发的面试任务:

Write simple lock-free Stack with two methods: push and 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 在 his SMR paper 中提到了它。 ，第 8 页，第 4.2 点，我已经完成了 a C99 implementation我自己。