Abstract

Treiber Stack Algorithm是一個可擴展的無鎖棧，利用細(xì)粒度的并發(fā)原語CAS來實現(xiàn)的，Treiber Stack在 R. Kent Treiber在1986年的論文Systems Programming: Coping with Parallelism中首次出現(xiàn)。

基本原理

該算法的基本原理是：只有當(dāng)您知道要添加的項目是自開始操作以來唯一添加的項目時，才會添加新的項目。 這是通過使用比較和交換完成的。 在添加新項目時使用堆棧，將堆棧的頂部放在新項目之后。 然后，將這個新構(gòu)造的頭元素（舊頭）的第二個項目與當(dāng)前項目進行比較。 如果兩者匹配，那么你可以將舊頭換成新頭，否則就意味著另一個線程已經(jīng)向堆棧添加了另一個項目，在這種情況下，你必須再試一次。

當(dāng)從堆棧中彈出一個項目時，在返回項目之前，您必須檢查另一個線程自操作開始以來沒有添加其他項目。

正確性

在某些語言中，特別是那些沒有垃圾回收的語言，Treiber棧可能面臨ABA問題。當(dāng)一個進程要從堆棧中移除一個元素時（就在下面的pop例程比較和設(shè)置之前），另一個進程可以改變堆棧，使得頭部是相同的，但是第二個元素是不同的。比較和交換將堆棧的頭部設(shè)置為堆棧中舊的第二個元素，混合完整的數(shù)據(jù)結(jié)構(gòu)。但是，由于Java運行時提供了更強大的保證，所以此頁面上的Java版本不受此問題的影響（新創(chuàng)建的不混淆的對象引用不可能與任何其他可到達的對象引用相同）。

對諸如ABA之類的故障進行測試可能會非常困難，因為有問題的事件序列非常少見。

Java示例

下面是Java中Treiber Stack的實現(xiàn)，它基于Java Concurrency in Practice提供的

public class ConcurrentStack<E> {private 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;}} }

流程分析

PUSH操作

根據(jù)上述的描述做圖如上，并分析其工作流程。

首先單鏈表保存了各個Stack中的各個元素，成員變量top持有了棧的棧頂元素。

當(dāng)執(zhí)行push操作時，首先創(chuàng)建一個新的元素為newHead，并讓該新節(jié)點的next指針指向top節(jié)點（此時top=oldHead）。

最后通過CAS替換top=newHead，CAS的交換條件是top=oldHead。

當(dāng)條件滿足后，操作后的狀態(tài)如下：

POP操作

根據(jù)上述的描述做圖如上，并分析其工作流程。

當(dāng)執(zhí)行pop操作時，創(chuàng)建一個新的指針，該指針指向top的next元素。

然后通過CAS替換top=newHead，CAS的交換條件是top=oldHead。

3.當(dāng)條件滿足后，操作后的狀態(tài)如下：

參考：https://en.wikipedia.org/wiki/Treiber_Stack#cite_note-4

總結(jié)

以上是生活随笔為你收集整理的Treiber Stack简单分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。