最近发现了这样一个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面试新手。
最佳答案
您肯定已经朝着正确的方向开始,考虑使用 Java 的原子整数和原子函数。因此,这将是一个无锁堆栈,例如:没有显式锁。
但是,在并发访问时仍然不正确,并且证明这一点相对简单:假设您的 push() 线程在获取计数和将新元素添加到堆栈之间阻塞(data[c] = o),与此同时,一个 pop() 线程出现,获得更高的计数,然后弹出......什么?无论发生在堆栈中该位置的内存中的什么,但不是 Object o(因为它尚未插入)。
这就是无锁、支持数组的堆栈的问题,理论上你需要调整两件事,即特定单元格的计数和内容,而且你不能同时以原子方式进行这两项操作.我不知道那里有任何无锁数组支持的堆栈算法。
虽然有链表支持的堆栈算法,但它们是无锁的,因为在这种情况下,您可以创建一个新节点,为其分配内容,并且您只需原子执行一个操作:更改顶部指针。
如果您对这个论点感兴趣,最好的文学作品是 Shavit 和 Herlihy 的“多处理器编程艺术”,其中描述了许多不同的数据结构,包括无锁和基于锁的。我现在找不到任何详细描述“普通”无锁堆栈算法的论文,尽管 Maged Michael 在 his SMR paper 中提到了它。 ,第 8 页,第 4.2 点,我已经完成了 a C99 implementation我自己。
关于java - 简单无锁堆栈,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5614599/