C++11如何實(shí)現(xiàn)無鎖隊(duì)列
無鎖操作的本質(zhì)依賴的原子操作,C++11提供了atomic的原子操作支持
atomic
compare_exchange_weak / compare_exchange_strong
當(dāng)前值與期望值相等時(shí),修改當(dāng)前值為設(shè)定值,返回true
當(dāng)前值與期望值不等時(shí),將期望值修改為當(dāng)前值,返回falsememory_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)可以直接再次嘗試壓棧而無需由程序員更新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)各種無鎖(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問題
所謂ABA(見維基百科的ABA詞條),問題基本是這個(gè)樣子:
- 進(jìn)程P1在共享變量中讀到值為A
- P1被搶占了,進(jìn)程P2執(zhí)行
- P2把共享變量里的值從A改成了B,再改回到A,此時(shí)被P1搶占。
- P1回來看到共享變量里的值沒有被改變,于是繼續(xù)執(zhí)行。
雖然P1以為變量值沒有改變,繼續(xù)執(zhí)行了,但是這個(gè)會(huì)引發(fā)一些潛在的問題。ABA問題最容易發(fā)生在lock free 的算法中的,CAS首當(dāng)其沖,因?yàn)镃AS判斷的是指針的地址。如果這個(gè)地址被重用了呢,問題就很大了。(地址被重用是很經(jīng)常發(fā)生的,一個(gè)內(nèi)存分配后釋放了,再分配,很有可能還是原來的地址)
eg:
好比你拿著一個(gè)裝滿錢的手提箱在飛機(jī)場(chǎng),此時(shí)過來了一個(gè)火辣性感的美女,然后她很暖昧地挑逗著你,并趁你不注意的時(shí)候,把用一個(gè)一模一樣的手提箱和你那裝滿錢的箱子調(diào)了個(gè)包,然后就離開了,你看到你的手提箱還在那,于是就提著手提箱去趕飛機(jī)去了。
這就是ABA的問題。
Fetch-And-Add (FAA)
一般用來對(duì)變量做+1的原子操作
Test-And-Set (TAS)
寫值到某個(gè)內(nèi)存位置并傳回其舊值
參考文章
C++11:原子交換函數(shù)compare_exchange_weak和compare_exchange_strong
到此這篇關(guān)于C++11如何實(shí)現(xiàn)無鎖隊(duì)列的文章就介紹到這了,更多相關(guān)C++11無鎖隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++實(shí)現(xiàn)將輸入的內(nèi)容輸出到文本文件
這篇文章主要介紹了C++實(shí)現(xiàn)將輸入的內(nèi)容輸出到文本文件問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-08-08C語言數(shù)據(jù)結(jié)構(gòu)系列篇二叉樹的概念及滿二叉樹與完全二叉樹
在上一章中我們正式開啟了對(duì)數(shù)據(jù)結(jié)構(gòu)中樹的講解,介紹了樹的基礎(chǔ)。本章我們將學(xué)習(xí)二叉樹的概念,介紹滿二叉樹和完全二叉樹的定義,并對(duì)二叉樹的基本性質(zhì)進(jìn)行一個(gè)簡(jiǎn)單的介紹。本章附帶課后練習(xí)2022-02-02C語言數(shù)據(jù)結(jié)構(gòu)之算法的時(shí)間復(fù)雜度
這篇文章主要介紹了C語言數(shù)據(jù)結(jié)構(gòu)之算法的時(shí)間復(fù)雜度,文章基于c語言的相關(guān)資料展開詳細(xì)介紹,具有一定的參價(jià)值,需要的小伙伴可以參考一下2022-05-05C語言報(bào)錯(cuò)Use of Uninitialized Variable的原因及解決方案
Use of Uninitialized Variable是C語言中常見且危險(xiǎn)的錯(cuò)誤之一,它通常在程序試圖使用一個(gè)未初始化的變量時(shí)發(fā)生,本文將詳細(xì)介紹Use of Uninitialized Variable的產(chǎn)生原因,提供多種解決方案,并通過實(shí)例代碼演示如何有效避免和解決此類錯(cuò)誤,需要的朋友可以參考下2024-06-06C語言用fun函數(shù)實(shí)現(xiàn)兩個(gè)數(shù)的交換方式
這篇文章主要介紹了C語言用fun函數(shù)實(shí)現(xiàn)兩個(gè)數(shù)的交換方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-12-12C++實(shí)現(xiàn)與Lua相互調(diào)用的示例詳解
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)與Lua相互調(diào)用的方法,文中的示例代碼講解詳細(xì),具有一定的學(xué)習(xí)價(jià)值,感興趣的小伙伴可以了解一下2023-03-03