原文鏈接，譯文鏈接，譯者：周可人，校對(duì)：梁海艦

1.1.2 阻塞技術(shù)

在很多數(shù)據(jù)結(jié)構(gòu)中，內(nèi)存競(jìng)爭(zhēng)所帶來(lái)的不良現(xiàn)象和前文所說(shuō)的順序瓶頸帶來(lái)的影響都可以通過(guò)使用細(xì)粒度鎖機(jī)制來(lái)減小。在細(xì)粒度鎖機(jī)制中，我們用多個(gè)粒度較小的鎖來(lái)保護(hù)數(shù)據(jù)結(jié)構(gòu)中的不同部分。這樣做的目的是允許并發(fā)操作在它們不訪問(wèn)數(shù)據(jù)結(jié)構(gòu)的相同部分時(shí)并行執(zhí)行。這種方法也可以用于避免獨(dú)立內(nèi)存位置訪問(wèn)的額外競(jìng)爭(zhēng)。在一些數(shù)據(jù)結(jié)構(gòu)中，這種現(xiàn)象經(jīng)常發(fā)生；舉個(gè)例子，在哈希表中，對(duì)那些被哈希到不同哈希桶中的值的操作自然訪問(wèn)的是數(shù)據(jù)結(jié)構(gòu)中的一部分。

對(duì)其他的數(shù)據(jù)結(jié)構(gòu)，如基于鎖的共享計(jì)數(shù)器，怎樣減少競(jìng)爭(zhēng)和降低順序瓶頸并沒有那么清晰，因?yàn)槌橄蟮貋?lái)說(shuō)，所有的操作都對(duì)數(shù)據(jù)結(jié)構(gòu)的同一部分做修改。一種處理競(jìng)爭(zhēng)的方法是將所有操作分散在不同時(shí)間，從而使每一個(gè)操作在不同的時(shí)段訪問(wèn)計(jì)數(shù)器。一種廣泛使用的處理技術(shù)被稱為回退。然而，即使減少了競(jìng)爭(zhēng)，我們的基于鎖的計(jì)數(shù)器仍然缺少并行性，并且不可擴(kuò)展。幸運(yùn)的是，更加細(xì)致的技術(shù)可以提升可擴(kuò)展性。

一種技術(shù)，被稱為“合并樹”，可以用來(lái)實(shí)現(xiàn)一個(gè)可擴(kuò)展的計(jì)數(shù)器。這種技術(shù)使用了一個(gè)二叉樹，每個(gè)葉子表示一個(gè)線程。樹的根節(jié)點(diǎn)存儲(chǔ)實(shí)際的計(jì)數(shù)器值，樹的其他內(nèi)部節(jié)點(diǎn)用來(lái)協(xié)調(diào)對(duì)根節(jié)點(diǎn)的訪問(wèn)。其中的核心思想是線程從樹的葉子節(jié)點(diǎn)向上爬，嘗試去和其他并發(fā)操作“合并”。每一次兩個(gè)線程的操作在一個(gè)內(nèi)部節(jié)點(diǎn)合并，其中一個(gè)線程（失敗者），簡(jiǎn)單地在當(dāng)前節(jié)點(diǎn)等待，直到一個(gè)返回值傳遞給它。另外一個(gè)線程（勝利者），朝著根節(jié)點(diǎn)向上，攜帶所有在該節(jié)點(diǎn)子樹中合并的操作之和；一個(gè)到達(dá)根節(jié)點(diǎn)的勝利者線程將它的和增加到計(jì)數(shù)器中，因此所有合并的操作增長(zhǎng)被加到計(jì)數(shù)器中。之后這個(gè)勝利者在樹中下降，分發(fā)一個(gè)返回值給每一個(gè)之前合并的，處在等待狀態(tài)的失敗者線程。這些返回值被分發(fā)下來(lái)，這樣的效果就好像所有增長(zhǎng)操作都在根計(jì)數(shù)器被修改的時(shí)刻一個(gè)接著一個(gè)的執(zhí)行。

在合并樹中，失敗者在等待勝利者時(shí)所使用的技術(shù)對(duì)性能而言是重要的。一個(gè)失敗者采用重復(fù)地讀取一個(gè)樹節(jié)點(diǎn)的一個(gè)內(nèi)存地址的方式操作等待，這被稱為自旋。在緩存一致性多核處理器中，一個(gè)重要的推論是這個(gè)位置會(huì)位于運(yùn)行失敗者操作的處理器的本地緩存，直到勝利者操作報(bào)告結(jié)果。這意味著等待的失敗者并沒有產(chǎn)生任何不必要的，并且可能降低勝利者性能的內(nèi)存流量。這種等待被稱為本地自旋，且已經(jīng)被證實(shí)對(duì)提升可擴(kuò)展性來(lái)說(shuō)至關(guān)重要。

在所謂的非一致性內(nèi)存訪問(wèn)(NUMA)架構(gòu)中，處理器訪問(wèn)他們的共享存儲(chǔ)中本地存儲(chǔ)部分要比訪問(wèn)其他處理器的部分要快的多。在這樣的架構(gòu)中，數(shù)據(jù)布局——合并樹中節(jié)點(diǎn)在內(nèi)存中的分布方式——對(duì)性能有著顯著的影響。將樹的葉子節(jié)點(diǎn)存放在處理相應(yīng)線程的處理器附近可以提升性能。（我們假設(shè)線程是和處理器靜態(tài)綁定的）

數(shù)據(jù)布局的問(wèn)題也對(duì)緩存一致性多核處理器上并發(fā)數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)有影響。回顧合并樹的一個(gè)作用是減少獨(dú)立內(nèi)存位置的競(jìng)爭(zhēng)，從而提升性能。然而，因?yàn)榫彺嬉恢滦远嗪颂幚砥饔镁彺嫘写笮〉膲K管理內(nèi)存，如果兩個(gè)線程訪問(wèn)不同內(nèi)存區(qū)域，落在了相同的緩存行中，會(huì)和他們?cè)L問(wèn)同一塊內(nèi)存地址一樣受到性能影響。這種現(xiàn)象被稱為偽共享，這是一個(gè)常見的，令人困惑的性能問(wèn)題。

在減少獨(dú)立內(nèi)存位置的競(jìng)爭(zhēng)，用本地自旋減少內(nèi)存流量，允許操作并行執(zhí)行之后，用合并樹實(shí)現(xiàn)的，隨著并發(fā)線程的數(shù)量擴(kuò)展的計(jì)數(shù)器，比單鎖版本的計(jì)數(shù)器要好的多。如果所有線程被用于不斷合并，那么一個(gè)P寬度的樹允許P個(gè)線程在O(logP)個(gè)（合并樹中的）上升和下降的操作之后，返回P個(gè)值，提供了O(P/logP)的加速比。

盡管使用合并樹的方式有很多優(yōu)點(diǎn)，但是它也有一些不足之處。合并樹需要限定P個(gè)線程訪問(wèn)計(jì)數(shù)器，并且需要O(P)的空間。雖然它在高負(fù)載下能提供更高的吞吐量，即在樹被大量線程訪問(wèn)時(shí)，但它在低負(fù)載訪問(wèn)時(shí)的最好性能是差的：它必須遍歷樹中的O(logP)個(gè)節(jié)點(diǎn)，然而一個(gè)基于單鎖的fetch-and-inc操作在常數(shù)時(shí)間內(nèi)可以完成。此外，如果一個(gè)線程因?yàn)樗谝粋€(gè)勝利者線程離開樹向上后馬上到達(dá)導(dǎo)致合并失敗，那么它必須等待，直到勝利者返回才能繼續(xù)向上。如果上升的勝利者，失敗者，以及之后的上升線程之間的協(xié)調(diào)處理錯(cuò)誤，那么可能會(huì)導(dǎo)致死鎖：線程可能以循環(huán)的方式互相阻塞，沒有一個(gè)可以繼續(xù)執(zhí)行。避免死鎖顯著地增加了設(shè)計(jì)正確，并且高效的阻塞并發(fā)數(shù)據(jù)結(jié)構(gòu)的復(fù)雜性。

總的來(lái)說(shuō)，如果在使用足夠的阻塞來(lái)達(dá)到正確，和盡量降低阻塞來(lái)允許并發(fā)操作并行執(zhí)行之間達(dá)到平衡，阻塞數(shù)據(jù)結(jié)構(gòu)可以提供強(qiáng)大的，高效的實(shí)現(xiàn)。

文章轉(zhuǎn)自?并發(fā)編程網(wǎng)-ifeve.com

總結(jié)

以上是生活随笔為你收集整理的并发数据结构-1.1.2 阻塞技术的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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