Treiber stack

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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".

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.

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 { 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; } } }

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378756203 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001378756203 · captured 1791242445.0 · version history

Cite this page as: encyclopegia.org, “Treiber stack”, snapshot enwiki-001378756203. https://encyclopegia.org/a/treiber-stack

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.