并发编程算法 | Treiber Stack 实现 lock-free stack

多线程环境下各种数据结构的实现有了很大的变化,每当我们更新某个数据的时候,我们都要考虑其它线程是否对其进行了修改。最简单的一种方法就是加锁,不过加锁会导致性能低下,而且可能阻塞其他线程。因此,我们引入了非阻塞 (non-blocking) 的算法 —— 通过 CAS 操作保证操作的原子性,同时我们还引入了 lock-free 的概念,它指的是一个线程出现问题(如阻塞,失败)但不影响其他线程(从总体看程序仍然是在运行的)。这里就来看一下 Non-blocking stack 的一个实现 —— Treiber Stack

Treiber Stack

这里给出的是 Treiber Stack 的一个简化版的 Java 实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.concurrent.atomic.AtomicReference;
/**
* Concurrent stack implementation
* Treiber's Algorithm
*/
public class ConcurrentStack<E> {
private AtomicReference<Node<E>> top = new AtomicReference<>();
public void push(E elem) {
Node<E> newHead = new Node<>(elem);
Node<E> oldHead;
do {
oldHead = top.get();
newHead.next = oldHead;
} while (!top.compareAndSet(oldHead, newHead));
}
public E pop() {
Node<E> oldHead;
Node<E> newHead;
do {
oldHead = top.get();
if (oldHead == null)
return null;
newHead = oldHead.next;
} while (!top.compareAndSet(oldHead, newHead));
return oldHead.item;
}
private static class Node<E> {
public final E item;
public Node<E> next;
public Node(E item) {
this.item = item;
}
}
}

我们使用了 AtomicReference 来实现 Treiber Stack。每当我们 push 进去一个元素的时候,我们首先根据要添加的元素创建一个 Node,然后获取原栈顶结点,并将新结点的下一个结点指向原栈顶结点。此时我们使用 CAS 操作来更改栈顶结点,如果此时的栈顶和之前的相同,代表 CAS 操作成功,那么就把新插入的元素设为栈顶;如果此时的栈顶和之前的不同(即其他线程改变了栈顶结点),CAS 操作失败,那么需要重复上述操作(更新当前的栈顶元素并且重设 next),直到成功。pop 操作的原理也相似。


References

  • Java Concurrency In Practice
文章目录
  1. 1. Treiber Stack
  2. 2. References