C++11如何實現無鎖隊列

Posted on by

無鎖操作的本質依賴的原子操作，C++11提供瞭atomic的原子操作支持

atomic

compare_exchange_weak / compare_exchange_strong
當前值與期望值相等時，修改當前值為設定值，返回true
當前值與期望值不等時，將期望值修改為當前值，返回false

memory_order枚舉值

在這裡插入圖片描述 

template<typename T>
class lock_free_stack
{
private:
    struct node
    {
        T data;
        node* next;
        node(T const& data_):
        data(data_)
        {
        }
    };

    std::atomic<node*> head;

public:
    void push(T const& data)
    {
        node* const new_node=new node(data);
        new_node->next=head.load();  

        /*
        ** 當前值.compare_exchange_weak(期望值, 設置值)
        ** 單線程的情況：
        ** 第一次執行while循環：
        ** 此時當前值與期望值相等，修改當前值為設定值 head = new_node，返回true
        ** 多線程的情況：
        ** 第一次執行循環體的時候：
        ** compare_exchange_weak如果失敗, 返回false, 證明有其他線程更新瞭棧頂head，
        ** 當前值與期望值不等時，將期望值修改為當前值, 即new_node->next等於新的棧頂head,
        ** 被其他線程更新的新棧頂值會被更新到new_node->next中，
        ** 因此循環可以直接再次嘗試壓棧而無需由程序員更新new_node->next。
        ** 然後第二次執行循環體：
        ** 此時 head == new_node->next, 所以 head = new_node.
        ** 如果這是仍有其他線程幹擾，則仍為循環更新new_node->next
        */
        while(!head.compare_exchange_weak(new_node->next,new_node));
    }
};

CAS原子操作

  • CAS即Compare and Swap，是所有CPU指令都支持CAS的原子操作（X86中CMPXCHG匯編指令），用於實現實現各種無鎖（lock free）數據結構。
  • CAS用於檢查一個內存位置是否包含預期值，如果包含，則把新值復賦值到內存位置。成功返回true，失敗返回false。

示例代碼如下：

bool compare_and_swap ( int *memory_location, int expected_value, int new_value)
{
    if (*memory_location == expected_value)
    {
        *memory_location = new_value;
        return true;
    }
    return false;
}

ABA問題

所謂ABA（見維基百科的ABA詞條），問題基本是這個樣子：

  • 進程P1在共享變量中讀到值為A
  • P1被搶占瞭，進程P2執行
  • P2把共享變量裡的值從A改成瞭B，再改回到A，此時被P1搶占。
  • P1回來看到共享變量裡的值沒有被改變，於是繼續執行。

雖然P1以為變量值沒有改變，繼續執行瞭，但是這個會引發一些潛在的問題。ABA問題最容易發生在lock free 的算法中的，CAS首當其沖，因為CAS判斷的是指針的地址。如果這個地址被重用瞭呢，問題就很大瞭。（地址被重用是很經常發生的，一個內存分配後釋放瞭，再分配，很有可能還是原來的地址）

eg:
好比你拿著一個裝滿錢的手提箱在飛機場，此時過來瞭一個火辣性感的美女，然後她很暖昧地挑逗著你，並趁你不註意的時候，把用一個一模一樣的手提箱和你那裝滿錢的箱子調瞭個包，然後就離開瞭，你看到你的手提箱還在那，於是就提著手提箱去趕飛機去瞭。

這就是ABA的問題。

Fetch-And-Add （FAA）

一般用來對變量做+1的原子操作

Test-And-Set (TAS)

寫值到某個內存位置並傳回其舊值

參考文章

C++11：原子交換函數compare_exchange_weak和compare_exchange_strong

到此這篇關於C++11如何實現無鎖隊列的文章就介紹到這瞭,更多相關C++11無鎖隊列內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：