并发编程算法 | 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
