Treiber stack

The Treiber stack algorithm is a scalable lock-free stack utilizing the fine-grained concurrency primitive compare-and-swap. It is believed that R. Kent Treiber was the first to publish it in his 1986 article "Systems Programming: Coping with Parallelism".

Basic principle

The basic principle for the algorithm is to only add something new to the stack when the item to add is verified to be the only thing that has been added since the operation began. This is done by using compare-and-swap. Pushing an item to the stack is done by first taking the top of the stack (old head) and placing it after the new item to create a new head. The old head is then compared to the current head. If the two match then the old head can be swapped to the new one, if not then it means another thread has added an item to the stack, in which case another attempt is necessary.

When popping an item from the stack, before returning the item it must be verified that another thread has not added a new item since the operation began.

Correctness

Some implementations of the Treiber stack—particularly, those in languages without garbage collection—can be at risk for the ABA problem. When a process is about to remove an element from the stack (just before the compare-and-swap in the pop routine below) another process can change the stack such that the head is the same, but the second element is different. The compare-and-swap will set the head of the stack to the old second element in the stack, mixing up the complete data structure. Implementations in languages with garbage collection where new elements are allocated for each push (as in the Java implementation below) do not suffer such problems since the old head remains reachable from the process performing the compare-and-swap, and thus cannot be reclaimed and reused by another process pushing a new element to the stack as above.

Testing for failures such as ABA can be exceedingly difficult, because the problematic sequence of events is very rare. Model checking is an excellent way to uncover such problems. See for instance exercise 7.3.3 in "Modeling and analysis of communicating Systems".

Java example

Below is an implementation of the Treiber Stack in Java, based on the one provided by book Java Concurrency in Practice.

import java.util.concurrent.atomic.*;

import net.jcip.annotations.*;

/**
 * ConcurrentStack
 *
 * Nonblocking stack using Treiber's algorithm
 *
 * @author Brian Goetz and Tim Peierls
 */
@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;
        }
    }
}