C++ Treiber堆棧和原子下一個指針

「Treiber Stack」通常是最簡單的無鎖數據結構之一，因此在教授無鎖算法介紹時經常使用它。C++ Treiber堆棧和原子下一個指針

我見過很多使用C++ atomics的Treiber Stacks的實現。算法本身是微不足道的，所以真正的挑戰是處理無鎖數據結構的所有其他附帶細節，例如提供某種方式來執行安全的內存回收，避免ABA問題，並以無鎖方式分配節點。這可以通過各種方式解決，例如使用原子引用計數，危險指針，計數/標記指針以避免ABA，以及使用無鎖內存池。

但忽略所有這些細節，專注於簡單的算法本身，也發生在我一個問題是，二極管驅動器堆棧的每一個實現，我記得使用實現原子下一個指針節點類的事實。例如：

struct Node 
{ 
    T value; 
    std::atomic<Node*> next; 
};

但考慮到算法後，我不知道爲什麼下一個指針需要原子。

一般PUSH算法（忽略無鎖分配，安全內存回收，回退，避免ABA等）：

Node* n = new Node(); 
Node* front = m_front.load(); 
n->next.store(front); 
while (!m_front.compare_exchange_weak(front, n)) 
{ 
    n->next.store(front); 
}

一般的POP算法（再次，無視除了實際的算法所有細節邏輯）是：

Node* front = m_front.load(); 
Node* next = front->next.load(); 
while (!m_front.compare_exchange_weak(front, next)) 
{ 
    next = front->next.load(); 
}

這裏是一個真實的例子執行PUSH算法：

https://github.com/khizmax/libcds/blob/master/cds/intrusive/treiber_stack.h#L736

所以我不明白爲什麼下一個指針甚至需要是原子的。大多數C++實現使用next指針來使用寬鬆的加載/存儲，所以在讀/寫下一個指針時我們不需要任何內存限制，但是我的想法是它根本不需要是原子的。

從我所看到的，任何時候都不會寫入任何節點的下一個指針。相反，下一個指針可以同時加載，但我從來沒有看到算法同時加載+存儲或同時存儲+存儲的機會。實際上，在PUSH算法中，根本不會同時訪問下一個指針。

因此，在我看來，下一個指針在同時訪問時是有效的「只讀」，所以我不知道爲什麼甚至有必要使它們成爲原子。然而，我看到的Treiber Stack的每個C++實現都使得下一個指針是原子的。所以我是否正確，或者有什麼理由讓下一個指針必須是原子的？

來源

2017-09-25 Siler

因爲沒有原子，你沒有CAS？ – cHao

你不要在下一個指針 – Siler

上用CAS。我明白你現在在說什麼。在C++中原子性，排序和可見性相互關聯的可能性很小。 Java似乎不需要'next'的原子，但是它的內存模型本身提供了一些同步保證。 – cHao

如果它與您顯示的代碼一樣簡單，那麼您就是對的。指向它的指針發佈後，一個Node永遠不會被修改。但是你忽略了清理節點的部分，以便它們可以被垃圾回收。（彈出之後你不能只有delete;另一個線程仍然可以有一個指向它的指針，但還沒有讀取它，這對於RCU也是一個棘手的問題。）

這是你離開了功能，CAS後叫pop成功：

protected: 
    void clear_links(node_type * pNode) CDS_NOEXCEPT 
    { 
     pNode->m_pNext.store(nullptr, memory_model::memory_order_relaxed); 
    }

這裏有一個順序，其中，而它的寫入讀取器讀取next：

A: Node* front = m_front.load(); 
           B: Node* front = m_front.load(); // same value 
A: Node* next = front->next.load(); 
A: m_front.compare_exchange_weak(front, next) // succeeds, no loop 
A: clear_links(front); // i.e. front->next.store(nullptr); 

           B: front->next.load();

因此，C++未定義的行爲，就標準合規性而言的結尾。

實際上，大多數CPU架構上的非原子加載will happen to be atomic anyway或者最糟糕的情況是撕裂。（任何ISA的IDK導致除了值之外的任何不可預知的事情，但C++將此選項打開）。

我不知道有一個地方撕裂值可以真正得到使用（投入m_front），因爲clear_links()不能，直到成功CAS後運行的任何情況。如果CAS在一個線程中成功，它將在另一個線程中失敗，因爲它只會嘗試使用舊front作爲expected arg到CAS的殘缺值next值。

在實踐中，幾乎每一個執行誰會關心有寬鬆的原子加載/存儲與普通的指針大小的物體無需支付額外費用。事實上，如果atomicity isn't "free" for a pointer這個堆棧非常糟糕。

例如在AVR（使用16位指針的8位RISC微控制器）上，僅鎖定數據結構會更便宜，而不是讓std::atomic在此算法中爲每個加載/存儲使用鎖。（特別是因爲有沒有多核心CPU的AVR，因此鎖可能是非常便宜的實施。）

atomic<>也得到編譯器假設值可以被另一個線程異步修改。因此，它可以阻止它優化負載或商店，有點像volatile。（但也可參見Why don't compilers merge redundant std::atomic writes?。）我不認爲這裏有任何需要的地方，而且不會發生。

非原子OPS通過原子有序的獲取和釋放操作，類似於寬鬆原子操作，以及CAS修改front，所以前置式>未來has a new front`所以非原子負載不能優化掉。

在將atomic <Node*> next替換爲Node *next後，查看是否從編譯器獲得相同的asm輸出可能是一個有趣的實驗。（或者使用仍具有加載/存儲成員函數的non_atomic包裝類，因此不必修改太多代碼）。

使用寬鬆的原子商店看起來不錯。你肯定不要實現它，你就有了辦法，用seq_cst專賣店爲初始化已經沒有任何指向它尚未公佈一個新的對象的一部分。在那個時候，原子是不需要的，但它是免費的（在正常的CPU上），所以避免它是沒有好處的。沒有任何商店或貨物可以優化。

來源

2017-09-26 00:17:55

C++ Treiber堆棧和原子下一個指針

回答

相關問題