C++11怎么實(shí)現(xiàn)無(wú)鎖隊(duì)列

這篇文章主要講解了“C++11怎么實(shí)現(xiàn)無(wú)鎖隊(duì)列”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“C++11怎么實(shí)現(xiàn)無(wú)鎖隊(duì)列”吧！

無(wú)鎖操作的本質(zhì)依賴的原子操作，C++11提供了atomic的原子操作支持

atomic

compare_exchange_weak / compare_exchange_strong
當(dāng)前值與期望值相等時(shí)，修改當(dāng)前值為設(shè)定值，返回true
當(dāng)前值與期望值不等時(shí)，將期望值修改為當(dāng)前值，返回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();  

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

CAS原子操作

• CAS即Compare and Swap，是所有CPU指令都支持CAS的原子操作（X86中CMPXCHG匯編指令），用于實(shí)現(xiàn)實(shí)現(xiàn)各種無(wú)鎖（lock free）數(shù)據(jù)結(jié)構(gòu)。

• CAS用于檢查一個(gè)內(nèi)存位置是否包含預(yù)期值，如果包含，則把新值復(fù)賦值到內(nèi)存位置。成功返回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問(wèn)題

所謂ABA（見(jiàn)維基百科的ABA詞條），問(wèn)題基本是這個(gè)樣子：

• 進(jìn)程P1在共享變量中讀到值為A

• P1被搶占了，進(jìn)程P2執(zhí)行

• P2把共享變量里的值從A改成了B，再改回到A，此時(shí)被P1搶占。

• P1回來(lái)看到共享變量里的值沒(méi)有被改變，于是繼續(xù)執(zhí)行。

雖然P1以為變量值沒(méi)有改變，繼續(xù)執(zhí)行了，但是這個(gè)會(huì)引發(fā)一些潛在的問(wèn)題。ABA問(wèn)題最容易發(fā)生在lock free 的算法中的，CAS首當(dāng)其沖，因?yàn)镃AS判斷的是指針的地址。如果這個(gè)地址被重用了呢，問(wèn)題就很大了。（地址被重用是很經(jīng)常發(fā)生的，一個(gè)內(nèi)存分配后釋放了，再分配，很有可能還是原來(lái)的地址）

eg:
好比你拿著一個(gè)裝滿錢的手提箱在飛機(jī)場(chǎng)，此時(shí)過(guò)來(lái)了一個(gè)火辣性感的美女，然后她很暖昧地挑逗著你，并趁你不注意的時(shí)候，把用一個(gè)一模一樣的手提箱和你那裝滿錢的箱子調(diào)了個(gè)包，然后就離開(kāi)了，你看到你的手提箱還在那，于是就提著手提箱去趕飛機(jī)去了。

這就是ABA的問(wèn)題。

Fetch-And-Add （FAA）

一般用來(lái)對(duì)變量做+1的原子操作

Test-And-Set (TAS)

寫(xiě)值到某個(gè)內(nèi)存位置并傳回其舊值

感謝各位的閱讀，以上就是“C++11怎么實(shí)現(xiàn)無(wú)鎖隊(duì)列”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)C++11怎么實(shí)現(xiàn)無(wú)鎖隊(duì)列這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！