無鎖隊列的潛在優(yōu)勢
無鎖隊列
先大致介紹一下無鎖隊列。無鎖隊列的根本是CAS函數(shù)——CompareAndSwap，即比較并交換，函數(shù)功能可以用C++函數(shù)來說明：
{
int old_reg_val = *reg;
if (old_reg_val == oldval)
*reg = newval;
return old_reg_val;
}
它將reg的值與oldval的值進行對比，若相同則將reg賦新值。注意以上操作是原子操作。大部分語言都有提供CAS支持，不過函數(shù)原型可能有些微的不同，許多語言（包括go）中CAS的返回值是標(biāo)識是否賦值成功的bool值。
無鎖隊列則是以CAS來實現(xiàn)同步的一種隊列，我的具體實現(xiàn)這里就不貼出來了，有點冗長，文末給出了源碼地址。這里僅僅大致給出實現(xiàn)思路，網(wǎng)上關(guān)于無鎖隊列的資料很多，這里就不詳細說了。
{
q = new record();
q->value = x;
q->next = NULL;
p = tail;
oldp = p
do {
while (p->next != NULL)
p = p->next;
} while( CAS(p.next, NULL, q) != TRUE); //如果沒有把結(jié)點鏈在尾上，再試
CAS(tail, oldp, q); //置尾結(jié)點
}
DeQueue() //出隊列
{
do{
p = head;
if (p->next == NULL){
return ERR_EMPTY_QUEUE;
}
while( CAS(head, p, p->next) != TRUE );
return p->next->value;
}
自旋鎖
自旋鎖是加鎖失敗時接著循環(huán)請求加鎖，直到成功。它的特點是不會釋放CPU，故也沒有互斥鎖那種內(nèi)核態(tài)切換操作，但缺點也很明顯，就是會一直占用CPU，理論上適用于臨界區(qū)小、不需要長時間加鎖的場景。 這里只貼鎖的相關(guān)代碼，隊列的實現(xiàn)就不貼了：
type spinMutex struct {
mutex int32
}
const locked = 1
const unlocked = 0
func (spin *spinMutex) lock() {
for !atomic.CompareAndSwapInt32(&spin.mutex, unlocked, locked) {}
}
func (spin *spinMutex) unlock() {
atomic.SwapInt32(&spin.mutex, unlocked)
}
互斥鎖
這個沒什么好說的，用的golang自帶的互斥鎖sync.Mutex。
測試
下面將分2種場景進行測試：分別是高并發(fā)和低并發(fā)。高并發(fā)我用4個協(xié)程往隊列中push數(shù)據(jù)，4個協(xié)程從隊列中pop數(shù)據(jù)（雖然不是很高，但足以區(qū)分性能，就沒測太高并發(fā)了，畢竟測一次等的太久也累）；低并發(fā)不好模擬，于是我干脆極端點改為無并發(fā)——先順序?qū)懀夙樞蜃x。
無并發(fā)
大致測試代碼結(jié)構(gòu)如下（刪減了不關(guān)鍵的語句）：
for i := 1; i <= dataNum; i++ {
suc := queue.PushBack(i)
}
queue.Disable()
for {
val, enable := queue.PopFront()
if !enable {
break
}
}
fmt.Println("用時：", time.Since(t1))
為了方便對比，我特地還增加了不加鎖的隊列的測試結(jié)果。測試結(jié)果如下：（左側(cè)為dataNum數(shù)據(jù)量）
添加圖片注釋，不超過 140 字（可選）
可以看到數(shù)據(jù)量小的時候性能差別還不明顯，甚至cas還有少許的優(yōu)勢。但數(shù)據(jù)量一大就很明顯的看出自旋鎖的效率會高一點，cas次之。不過它們差別都不大。
高并發(fā)
這里用4個生產(chǎn)者4個消費者共用一個隊列來模擬高并發(fā)。測試代碼結(jié)構(gòu)如下：
wgr := sync.WaitGroup{}
wgw := sync.WaitGroup{}
t1 := time.Now()
for i := 0; i < 4; i++ {
wgr.Add(1)
go reader(i*1000000, &wgr)
}
for i := 0; i < 4; i++ {
wgw.Add(1)
go writter(&wgw)
}
wgr.Wait()
queue.Disable()
wgw.Wait()
fmt.Println("用時：", time.Since(t1))
}
func reader(startNum int, wg *sync.WaitGroup) {
for i := 0; i < dataNum; i++ {
suc := queue.PushBack(startNum + i)
for !suc {
suc = queue.PushBack(startNum + i)
}
}
wg.Done()
}
func writter(wg *sync.WaitGroup) {
for {
r, enable := queue.PopFront()
if enable == false {
break
}
if r == defaultVal {
continue
}
}
wg.Done()
}
這種情況下就沒法測試無鎖隊列了，數(shù)據(jù)都不完整（已驗證）。測試結(jié)果如下，左側(cè)為讀/寫協(xié)程數(shù)*dataNum數(shù)據(jù)量（下面讀/寫協(xié)程數(shù)為4指總共開了8個協(xié)程）：
添加圖片注釋，不超過 140 字（可選）
可以看到cas有巨大的性能優(yōu)勢，甚至達到了3到5倍的性能差距，說明這個思路還是可行的?。ㄏ乳_始被chan打擊到了）反倒是自旋鎖的性能最差，這個倒有些出乎我的意料，按照我的理解在這種頻繁加鎖解鎖的情況下自旋鎖的性能應(yīng)該更好才對，若有知情人士望告知。
分析
為了對這幾種鎖的性能特點有更深入的分析，這里還補充了幾組測試，分別用了不同的協(xié)程數(shù)和數(shù)據(jù)量進行補充測試：
添加圖片注釋，不超過 140 字（可選）
可以很明顯的看到一個趨勢——隨著并發(fā)度增加，自旋鎖的性能急劇下降，由無并發(fā)時的與cas性能幾乎一樣到最后與cas將近7倍的效率差。而mutex和cas情況下，隨著并發(fā)度增加，性能影響并不大，下面將前面的測試數(shù)據(jù)重新組織一下方便對比：
添加圖片注釋，不超過 140 字（可選）
可以看到總數(shù)據(jù)量不變的情況下，并發(fā)協(xié)程數(shù)對mutex和cas的影響非常小，基本在波動范圍以內(nèi)。相較之下自旋鎖就比較慘了。
總結(jié)
**根據(jù)上面的結(jié)果來說的話，當(dāng)實際競爭特別小的時候，可以考慮用自旋鎖；而并發(fā)大的時候，用無鎖隊列這種結(jié)構(gòu)有很大潛在優(yōu)勢。**之所以說潛在的是因為我也僅僅是簡單的實現(xiàn)某種結(jié)構(gòu)，肯定有考慮不全的地方，我寫這個無鎖例子主要用于測試，也沒打算用于實際場景中。但是我盡量保證了同樣的代碼結(jié)構(gòu)下，最大化各個鎖結(jié)構(gòu)對性能的影響?？偟膩碚f，本文測試結(jié)果僅作參考，希望能有拋磚引玉的效果。
最后，再附上源碼地址：https://github.com/HandsomeRosin/lockfree
更新：
針對自旋鎖效率低下的問題我仔細想了想，應(yīng)該是原子操作cas耗時的問題（畢竟在無并發(fā)情況下，cas和真正不加鎖還是有很大的性能差距）。于是對自旋鎖的代碼進行了微調(diào)，減少了CAS的調(diào)用次數(shù)：（被注釋掉的是原本的代碼邏輯）
// for !atomic.CompareAndSwapInt32(&spin.mutex, unlocked, locked) {}
BEGINING:
for spin.mutex != unlocked {}
if !atomic.CompareAndSwapInt32(&spin.mutex, unlocked, locked) {
goto BEGINING
}
}
事實證明，這樣做效率確實提高了約1/4，不過還是改變不了它的大趨勢（與cas和mutex的性能差距依舊巨大），所以就沒更新前面的測試數(shù)據(jù)了。
不過這也佐證了CAS也是比較耗時的一個操作，平時還是不能肆意使用。
-
數(shù)據(jù)
+關(guān)注
關(guān)注
8文章
6715瀏覽量
88308 -
源碼
+關(guān)注
關(guān)注
8文章
626瀏覽量
28966 -
函數(shù)
+關(guān)注
關(guān)注
3文章
4237瀏覽量
61965 -
CAS
+關(guān)注
關(guān)注
0文章
34瀏覽量
15160
發(fā)布評論請先 登錄
相關(guān)推薦
使用USB進行測量應(yīng)用的優(yōu)勢和潛在危險
《有鎖》/《無鎖》/《簽約》/《解鎖》/《越獄》/《激活》專
AWorks軟件設(shè)計，郵箱、消息隊列和自旋鎖使用方法
智能鎖按鍵出現(xiàn)無反應(yīng)或禁止操作的原因坤坤智能鎖告訴你
利用CAS技術(shù)實現(xiàn)無鎖隊列
關(guān)于CAS等原子操作介紹 無鎖隊列的鏈表實現(xiàn)方法
怎么設(shè)計實現(xiàn)一個無鎖高并發(fā)的環(huán)形連續(xù)內(nèi)存緩沖隊列
發(fā)燒友實測 | i.MX8MP 編譯DPDK源碼實現(xiàn)rte_ring無鎖環(huán)隊列進程間通信
無源智能鎖的應(yīng)用前景
新品上架——無源智能把手鎖
固態(tài)電池(SSBs)的潛在優(yōu)勢
如何實現(xiàn)一個多讀多寫的線程安全的無鎖隊列
無鎖CAS如何實現(xiàn)各種無鎖的數(shù)據(jù)結(jié)構(gòu)
工商網(wǎng)監(jiān)
評論