本文共 1064 字,大约阅读时间需要 3 分钟。
转自 https://www.cnblogs.com/micrari/p/7719408.html
简介
Treiber Stack在 R. Kent Treiber在1986年的论文中首次出现。它是一种无锁并发栈,其无锁的特性是基于CAS原子操作实现的。
下面给出的Java语言实现为《Java并发编程实战》一书的15.4.1小结中的实现。Treiber Stack的实现套路很简单,就是CAS+重试,不需要任何注释就能轻松的看懂代码。
@ThreadSafepublic class ConcurrentStack{ AtomicReference > top = new AtomicReference >(); public void push(E item) { Node newHead = new Node (item); Node oldHead; do { oldHead = top.get(); newHead.next = oldHead; } while (!top.compareAndSet(oldHead, newHead)); } public E pop() { Node oldHead; Node 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 { public final E item; public Node next; public Node(E item) { this.item = item; } }}
JDK中的FutureTask使用了Treiber Stack。关于FutureTask的源码解读,可以参考我的博文。FutureTask用了Treiber Stack来维护等待任务完成的线程,在FutureTask的任务完成/取消/异常后在finishCompletion钩子方法中会唤醒栈中等待的线程。