Treiber stack

Introduction

Treiber stack 是线程安全的，基于 CAS 的无锁并发栈。由 R. Kent Treiber 于 1986 年首次在文章 “Systems Programming: Coping with Parallelism” 中发表。

基本原理：

1. 入栈时，通过 CAS 算法，将当前栈顶元素（old head）放在新元素之后以创建 new head 来完成

2. 出栈时，在返回元素之前，必须检查自该操作开始以来，是否有另一个线程往栈中添加了新元素

Java example

用一个例子就能很容易看明白。

/**
 * ConcurrentStack
 *
 * Nonblocking stack using Treiber's algorithm
 *
 * @author Brian Goetz and Tim Peierls
 */
@ThreadSafe
public class ConcurrentStack <E> {
    AtomicReference<Node<E>> top = new AtomicReference<>();

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

real case

Hystrix

在限流框架 Hystrix 中就使用到了 Treiber stack。其主要实现和上面的 demo 差不多。

源码位置：com.netflix.hystrix.Hystrix.ConcurrentStack

FutureTask

FutureTask 用到了 Treiber stack，但是是将其作为了简单链表来使用，使调用 get() 方法来检索结果的等待线程排队，并不是像上面的那样实现。

先挖个坑，后面 FutureTask 的文章会分析其入栈和出栈过程。

源码位置：java.util.concurrent.FutureTask.WaitNode

---