Treiber Stack介绍

2022-6-21 / 0评 / Java

简介
Treiber Stack在 R. Kent Treiber在1986年的论文Systems Programming: Coping with Parallelism中首次出现。它是一种无锁并发栈,其无锁的特性是基于CAS原子操作实现的。


实现
下面给出的Java语言实现为《Java并发编程实战》一书的15.4.1小结中的实现。Treiber Stack的实现套路很简单,就是CAS+重试,不需要任何注释就能轻松的看懂代码。

@ThreadSafe
public class ConcurrentStack <E> {
    AtomicReference<Node<E>> top = new AtomicReference<Node<E>>();

    public void push(E item) {
        Node<E> newHead = new Node<E>(item);
        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;
        }
    }
}

JDK中的使用
JDK中的FutureTask使用了Treiber Stack。关于FutureTask的源码解读,可以参考FutureTask源码解读。
FutureTask用了Treiber Stack来维护等待任务完成的线程,在FutureTask的任务完成/取消/异常后在finishCompletion钩子方法中会唤醒栈中等待的线程。

参考
《Java并发编程实战》
Treiber Stack

本文共计 90667 字,感谢您的耐心浏览与评论。

声明:土豆丝不辣|版权所有,违者必究|如未注明,均为原创|转载请注明原文链接说明出处

0条回应:“Treiber Stack介绍”