并發資料結構-1.1.2 阻塞技術

在很多資料結構中，記憶體競争所帶來的不良現象和前文所說的順序瓶頸帶來的影響都可以通過使用細粒度鎖機制來減小。在細粒度鎖機制中，我們用多個粒度較小的鎖來保護資料結構中的不同部分。這樣做的目的是允許并發操作在它們不通路資料結構的相同部分時并行執行。這種方法也可以用于避免獨立記憶體位置通路的額外競争。在一些資料結構中，這種現象經常發生；舉個例子，在哈希表中，對那些被哈希到不同哈希桶中的值的操作自然通路的是資料結構中的一部分。

對其他的資料結構，如基于鎖的共享計數器，怎樣減少競争和降低順序瓶頸并沒有那麼清晰，因為抽象地來說，所有的操作都對資料結構的同一部分做修改。一種處理競争的方法是将所有操作分散在不同時間，進而使每一個操作在不同的時段通路計數器。一種廣泛使用的處理技術被稱為回退。然而，即使減少了競争，我們的基于鎖的計數器仍然缺少并行性，并且不可擴充。幸運的是，更加細緻的技術可以提升可擴充性。

一種技術，被稱為“合并樹”，可以用來實作一個可擴充的計數器。這種技術使用了一個二叉樹，每個葉子表示一個線程。樹的根節點存儲實際的計數器值，樹的其他内部節點用來協調對根節點的通路。其中的核心思想是線程從樹的葉子節點向上爬，嘗試去和其他并發操作“合并”。每一次兩個線程的操作在一個内部節點合并，其中一個線程（失敗者），簡單地在目前節點等待，直到一個傳回值傳遞給它。另外一個線程（勝利者），朝着根節點向上，攜帶所有在該節點子樹中合并的操作之和；一個到達根節點的勝利者線程将它的和增加到計數器中，是以所有合并的操作增長被加到計數器中。之後這個勝利者在樹中下降，分發一個傳回值給每一個之前合并的，處在等待狀态的失敗者線程。這些傳回值被分發下來，這樣的效果就好像所有增長操作都在根計數器被修改的時刻一個接着一個的執行。

在合并樹中，失敗者在等待勝利者時所使用的技術對性能而言是重要的。一個失敗者采用重複地讀取一個樹節點的一個記憶體位址的方式操作等待，這被稱為自旋。在緩存一緻性多核處理器中，一個重要的推論是這個位置會位于運作失敗者操作的處理器的本地緩存，直到勝利者操作報告結果。這意味着等待的失敗者并沒有産生任何不必要的，并且可能降低勝利者性能的記憶體流量。這種等待被稱為本地自旋，且已經被證明對提升可擴充性來說至關重要。

在所謂的非一緻性記憶體通路(numa)架構中，處理器通路他們的共享存儲中本地存儲部分要比通路其他處理器的部分要快的多。在這樣的架構中，資料布局——合并樹中節點在記憶體中的分布方式——對性能有着顯著的影響。将樹的葉子節點存放在處理相應線程的處理器附近可以提升性能。（我們假設線程是和處理器靜态綁定的）

資料布局的問題也對緩存一緻性多核處理器上并發資料結構的設計有影響。回顧合并樹的一個作用是減少獨立記憶體位置的競争，進而提升性能。然而，因為緩存一緻性多核處理器用緩存行大小的塊管理記憶體，如果兩個線程通路不同記憶體區域，落在了相同的緩存行中，會和他們通路同一塊記憶體位址一樣受到性能影響。這種現象被稱為僞共享，這是一個常見的，令人困惑的性能問題。

在減少獨立記憶體位置的競争，用本地自旋減少記憶體流量，允許操作并行執行之後，用合并樹實作的，随着并發線程的數量擴充的計數器，比單鎖版本的計數器要好的多。如果所有線程被用于不斷合并，那麼一個p寬度的樹允許p個線程在o(logp)個（合并樹中的）上升和下降的操作之後，傳回p個值，提供了o(p/logp)的加速比。

盡管使用合并樹的方式有很多優點，但是它也有一些不足之處。合并樹需要限定p個線程通路計數器，并且需要o(p)的空間。雖然它在高負載下能提供更高的吞吐量，即在樹被大量線程通路時，但它在低負載通路時的最好性能是差的：它必須周遊樹中的o(logp)個節點，然而一個基于單鎖的fetch-and-inc操作在常數時間内可以完成。此外，如果一個線程因為它在一個勝利者線程離開樹向上後馬上到達導緻合并失敗，那麼它必須等待，直到勝利者傳回才能繼續向上。如果上升的勝利者，失敗者，以及之後的上升線程之間的協調處理錯誤，那麼可能會導緻死鎖：線程可能以循環的方式互相阻塞，沒有一個可以繼續執行。避免死鎖顯著地增加了設計正确，并且高效的阻塞并發資料結構的複雜性。

總的來說，如果在使用足夠的阻塞來達到正确，和盡量降低阻塞來允許并發操作并行執行之間達到平衡，阻塞資料結構可以提供強大的，高效的實作。