無(wú)鎖隊(duì)列是 lock-free 中最基本的數(shù)據(jù)結(jié)構(gòu)喳张，一般應(yīng)用在需要一款高性能隊(duì)列的場(chǎng)景下。
對(duì)于多線程用戶來(lái)說(shuō)美澳，無(wú)鎖隊(duì)列的入隊(duì)和出隊(duì)操作是線程安全的销部，不用再加鎖控制
什么是無(wú)鎖隊(duì)列
隊(duì)列每個(gè)開(kāi)發(fā)者都知道，那么什么又是無(wú)鎖隊(duì)列呢制跟？字面理解起來(lái)就是一個(gè)無(wú)鎖狀態(tài)的隊(duì)列舅桩，多個(gè)線程（消費(fèi)者）同時(shí)操作數(shù)據(jù)的時(shí)候不需要加鎖，因?yàn)榧?解鎖都是一個(gè)很消耗資源的動(dòng)作雨膨。
實(shí)現(xiàn)原理
我們先看一下無(wú)鎖隊(duì)列的底層實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)擂涛。
數(shù)據(jù)結(jié)構(gòu)
無(wú)鎖隊(duì)列底層的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)方式主要有兩種：數(shù)組 和 鏈接。
數(shù)組
在首次初始化時(shí)聊记，需要申請(qǐng)一塊連接的大的內(nèi)存歼指。讀寫(xiě)數(shù)據(jù)直接從數(shù)據(jù)的指定位置操作即可，時(shí)間復(fù)雜度為O(1)甥雕。
缺點(diǎn)：數(shù)組長(zhǎng)度有限踩身，一旦數(shù)組索引位置寫(xiě)滿，則無(wú)法繼續(xù)寫(xiě)入社露，即隊(duì)列有上限挟阻。
鏈表
不用像數(shù)組一樣，剛開(kāi)始就申請(qǐng)一塊連接的大的內(nèi)存空間峭弟。只有在每次寫(xiě)時(shí)數(shù)據(jù)的時(shí)候附鸽，申請(qǐng)這個(gè)數(shù)據(jù)節(jié)點(diǎn)大小的內(nèi)存即可，這樣就可以實(shí)現(xiàn)無(wú)限的寫(xiě)入瞒瘸，沒(méi)有長(zhǎng)度限制問(wèn)題坷备。
缺點(diǎn)：每次寫(xiě)數(shù)據(jù)都要申請(qǐng)內(nèi)存，在寫(xiě)的場(chǎng)景情臭，最差的情況是多少個(gè)數(shù)據(jù)就申請(qǐng)多少次內(nèi)存省撑，而每次申請(qǐng)都是一個(gè)消耗資源的動(dòng)作。
可以看到無(wú)鎖底層的實(shí)現(xiàn)的不同各有優(yōu)勢(shì)俯在。多數(shù)據(jù)情況下竟秫，我們都采用鏈表來(lái)實(shí)現(xiàn)無(wú)鎖隊(duì)列，主要原因就是寫(xiě)入可以沒(méi)有長(zhǎng)度的限制跷乐。相比每次申請(qǐng)都要費(fèi)時(shí)來(lái)說(shuō)肥败，滿足前面的條件是我們最基本的要求。當(dāng)然主要還是真正的使用場(chǎng)景。
CAS
CAS 是 Compare And Swap 的簡(jiǎn)稱, 屬于 樂(lè)觀鎖馒稍，這是一個(gè)并發(fā)同步原語(yǔ). 偽代碼如下:
bool compare_and_swap(int *reg, int oldval, int newval)
{
int reg_val = *reg;
if(reg_val == oldval)
{
*reg = newval;
return true;
}
return false;
}
CAS操作有三個(gè)參數(shù)皿哨，分別表示 內(nèi)存值V、舊的預(yù)期值A(chǔ) 和 修改后的更新值B纽谒。
判斷變量?jī)?nèi)存某個(gè)位置的值是否為預(yù)期值往史，如果是則更改為新的值，并返回true佛舱，這個(gè)過(guò)程是原子性操作椎例。如果修改失敗，可能需要重試再次執(zhí)行CAS操作请祖，直到修改成功订歪，一般稱此過(guò)程為自旋∷敛叮可以看到每次調(diào)用 CAS 命令前需要先讀取舊值 oldval刷晋。
現(xiàn)在幾乎所有的CPU指令都支持CAS的原子操作，X86下對(duì)應(yīng)的是 CMPXCHG 匯編指令慎陵。有了這個(gè)操作眼虱，我們就可以用其來(lái)實(shí)現(xiàn)各種無(wú)鎖的數(shù)據(jù)結(jié)構(gòu)。
使用場(chǎng)景
無(wú)鎖隊(duì)列也屬于隊(duì)列的一種席纽，所以大部分隊(duì)列的使用場(chǎng)景都可以使用它來(lái)代替其它有鎖隊(duì)列,無(wú)鎖隊(duì)列通過(guò)不加鎖的方式提高隊(duì)列性能捏悬。
參考資料
- https://zhuanlan.zhihu.com/p/336912752
- 無(wú)鎖隊(duì)列是否不適用于大容量應(yīng)用場(chǎng)景？
- https://www.dazhuanlan.com/2019/12/16/5df6622b4f46b/
- https://blog.codingnow.com/2014/12/skynet_spinlock.html
- https://blog.csdn.net/yishizuofei/article/details/78353722
- 一文徹底搞懂CAS實(shí)現(xiàn)原理 & 深入到CPU指令
- 無(wú)鎖隊(duì)列的分析與設(shè)計(jì)
