無鎖並不像人們所說的那麼好

杜老師說 2022-01-07 13:18:02 阅读数:150

不像

原文鏈接譯文連接,譯者:梁海艦,校對:李任

注意,我將在這篇文章中說一些關於“無鎖”和“無等待”算法的壞話。在我們開始之前,讓我來問你一個問題:

你之前有過需要無鎖算法來解决問題嗎?為什麼必須使用無鎖算法來解决?

這是一個意味深長的問題,在某種意義上,我們嘗試區分哪些問題需要“無鎖”或者受益於“無鎖”提供的保證,哪些問題使用阻塞解决方案就已經足够了。那麼,什麼樣的問題可以利用無鎖算法解决呢?

你會說高競爭下的擴展性?是的,聽起來無鎖算法確實是合適的候選方案,但是,實際上它很大程度取决於算法的某一些特征。

例如:如果循環中有很多CAS操作,當你增加線程數量時候,那些CAS操作將增加大量的重試,記住CAS操作的代價是很高的,並且很有可能成為該算法的瓶頸。實際上,這意味著CAS操作上越多的線程競爭,你的代碼運行的整體速度越慢,不管你添加多少線程。

如果你一開始沒有很多線程,那為什麼不使用阻塞的方式呢?在這個例子中使用阻塞的方式通常更簡單、更快實現。

如果問題允許,你甚至可以使用讀寫鎖,不同於大部分無鎖算法,讀寫鎖已經展示了讀線程的數量可擴展。

還有人說用在解决高競爭下的低延遲,好吧,無鎖僅僅保證了某些線程能够執行,但讓我們假設你沒有一個高優先級的線程或一個高於其他線程優先級的線程,未必當前線程就在執行它的任務(在這種情况下你需要無等待算法實現低延遲保證)。

對於這樣的情况,無鎖確實給了你比阻塞更好的保證,但是除此之外不要期望得太多。首先,你很可能丟失一些性能(但不是很多),其次,如果其他線程持續的執行,那麼特定的任務可能耗費無限的時間直至完成並且導致當前操作重啟。這意味著那些循環中包含很多CAS操作的無鎖算法,執行起來慢得離譜,其原因在於重試的次數,並不是所謂的複雜性。

現在我們知道為什麼使用無鎖,值得注意的是,許多無鎖算法在它們執行的一些步驟中會暗自分配和釋放內存。

我所知道的,沒有一個系統使用“無鎖”算法進行內存管理,事實上,在大部分系統中,內存分配有時候執行得非常慢。想象一下你申請一個對象,系統需要為你獲得一個新的內存頁,更糟糕的是,內存不足,需要將它舊的內容從內存中交換到硬盤中。

如果你關注的是擴展能力,那麼偶爾的阻塞,內存分配慢並不是太壞,但問題是你需要的是低延遲,使用無鎖進行內存分配、釋放沒有使用到任何“無鎖”算法自身提供的保證。不管使用有內存管理或無內存管理的系統都有這個棘手的問題,換而言之有沒有使用內存回收也是一樣。

我認為無鎖算法的適用性影響非常大,大到我們需要有兩個清楚的分類來為無鎖算法命名:

無界無鎖:這個算法是無鎖的,但是它的方法中或多或少需要為新的對象分配內存或者釋放一些對象占用的內存。

有界無鎖:這個算法是無鎖定,並且它的方法中沒有涉及到對象分配內存或者是有限制分配並且一開始預先分配,然後使用一個池設計模式,池也是采用無鎖方式實現的。

對於“無界無鎖”,如果我們教條主義,我們甚至可以說“無界無鎖”算法完全不是無鎖,因為算法中會有操作被阻塞,並且會導致任務阻塞。

我不會那麼教條主義,畢竟內存分配通常是很快的,並且垃圾回收器只是偶爾執行。

有一件事是可以肯定的,那就是給定一個需要解决低延遲的問題,它有兩個解决方案可選,一個是“無界無鎖”,另一個是“有界無鎖”,我會選擇有界的那個,即便它性能更低。

順便說一下,把上面所有段落中的“無鎖”字眼替換成“無等待”,它仍然適用。

話雖如此,我想再重申一下我偏愛的並發算法的順序,下面的算法中最上面的是你可以實現的最好的算法:

  1. 有界集居數無關無等待
  2. 有界無等待
  3. 有界無鎖
  4. 無界集居數無關無等待
  5. 無界無等待
  6. 無界無鎖
  7. 阻塞

原創文章,轉載請注明: 轉載自並發編程網 – ifeve.com本文鏈接地址: 無鎖並不像人們所說的那麼好

FavoriteLoading添加本文到我的收藏
版权声明:本文为[杜老師說]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201071318023329.html