{
  "id": "enwiki-001378756203",
  "slug": "treiber-stack",
  "title": "Treiber stack",
  "qid": "",
  "lead": "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\".",
  "body": "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==",
  "categories": [
    "20355135",
    "23603337",
    "26220375"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1378756203",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1791242445.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001378756203",
    "type": "webpage",
    "title": "Treiber stack",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/treiber-stack",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          18
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          18
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001378756203",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1378756203",
    "note": "Immutable snapshot enwiki-001378756203"
  }
}