代碼實現(xiàn)了這篇文章中的無鎖隊列。

fangcun：簡單，高效，實用的非阻塞(無鎖)和阻塞并行隊列算法?zhuanlan.zhihu.com

無鎖隊列需要實現(xiàn)一個FreeList來避免一個線程釋放了結(jié)點，而另一個線程仍在訪問該結(jié)點的問題，如圖所示的語句就存在這個問題：

代碼使用mingw64在windows下成功編譯，使用gcc內(nèi)建的原子操作函數(shù)。

且實現(xiàn)代碼入隊和出隊操作的每條語句依賴前一語句，編譯器不會進行語句級的重排。

FreeList使用了一個技巧來使FreeList的結(jié)點和無鎖隊列的結(jié)點使用完全相同的內(nèi)存，這樣結(jié)點不是在FreeList中，就是在無鎖隊列中，不會出現(xiàn)泄漏問題。

FreeList的Alloc(給無鎖隊列分配結(jié)點)和Free操作(這個Free操作是給無鎖隊列用來將結(jié)點放入FreeList中)也是無鎖的。

FreeList自身的釋放結(jié)點操作需要在安全的地方(非競爭環(huán)境)進行。

FreeList的最大結(jié)點數(shù)等于無鎖隊列中元素最多時的元素個數(shù)。

無鎖隊列中的元素個數(shù)沒有限制，這里的FreeList的最大結(jié)點數(shù)不是指FreeList存在大小限制，而是指無鎖隊列中Free的元素會被放進FreeList重復(fù)使用，所以FreeList的最大結(jié)點數(shù)不可能超過無鎖隊列的峰值元素數(shù)。

無鎖隊列中的結(jié)點可以安全地放入FreeList中重復(fù)使用，即使存在多個線程持有結(jié)點嘗試出隊結(jié)點，也只有一個可以成功出隊，也就是結(jié)點只被放入FreeList一次，不會被其它線程再次放入，放入FreeList的結(jié)點，可能仍然被其它線程持有，但它接下來的CAS會失敗，但我們不能直接釋放結(jié)點內(nèi)存，可以對結(jié)點進行寫操作，其它線程雖然持有結(jié)點，但只進行讀操作，如果我們直接釋放結(jié)點內(nèi)存，其它線程的讀操作就會crash整個程序(讀的內(nèi)存地址非法)，這也是使用FreeList的原因，其它線程持有結(jié)點，也不影響FreeList分配它給無鎖隊列重新使用。

使用__ATOMIC_RELAXED內(nèi)存順序的原因是查閱Intel64文檔，文檔表明load，store可以在一定程度上保證線程間的內(nèi)存可見性。

__ATOMIC_RELAXED內(nèi)存順序的_atomic_load只是一個原子操作，不會作為編譯器優(yōu)化屏障。

文檔地址：

http://120.52.51.18/www.cs.cmu.edu/~410-f10/doc/Intel_Reordering_318147.pdf?120.52.51.18

下面是我實現(xiàn)的無鎖隊列代碼，歡迎大家討論。

/*

總結(jié)

以上是生活随笔為你收集整理的gitclone 一个tag的地址_一个无锁队列和FreeList实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。