並發數據結構-1.1.3 非阻塞技術

杜老師說 2022-01-07 12:59:35 阅读数:590

1.1.3 阻塞

原文鏈接譯文鏈接,譯者:Noodles,校對:周可人

1.1.3 非阻塞技術

正如前面討論的那樣,非阻塞實現主要目的是為了消除由鎖帶來的相關問題,為了形式化研究這一概念,多種非阻塞演進條件已經在相關文獻有所研究了,如wait-freedom演進條件,lock-freedom演進條件,和obstruction-freedom演進條件。滿足wait-free演進條件的操作是指在執行自身包含的有限步驟之後,保證操作必須完成,而不用考慮其他操作發生的時序,滿足lock-free演進條件的操作是指在執行自身包含的有限步驟之後,保證某些操作完成。滿足obstruction-free演進條件的操作是指在不受其他操作幹擾的情况下,執行它包含的有限步驟之後,保證其完成。

顯然,wait-freedom是比lock-freedom强的演進條件,lock-freedom又比obstruction-freedom强。 但是,這三者都比以前那些使用像鎖這樣的阻塞構造的演進條件要强。雖然越强的演進條件看上去是可取的,但是通常來說,保證越弱的演進條件,實現起來越簡單,效率更高,且更容易設計和驗證。實際上,我們可以采用回退技術或者是精密的沖突管理技術對弱演進條件進行補償。

cas

圖 1.2  CAS 操作的語義

回到共享計數器的例子中,從Fiesher的研究結果中(被Herlihy,Loui和Abu-Amara擴展到共享內存上),我們可以得出,一個共享計數器不能通過僅僅使用load和store指令來訪問內存的來達到lock-free。上述研究結果錶明,現有提議的實現中,一些异常的交叉操作可能導致不正確的結果。這些(异常的)交叉操作大多是是由於load和store是相互獨立所引起的。這個問題可以通過將load和store指令合並為一個原子的硬件指令來解决。事實上,所有現代的多核處理器都提供了這樣的同步指令,最常見的是compare-and-swap(CAS)和load-linked/store-conditional(LL/SC)。CAS指令的語義可見圖1.2。為了說明問題,我們假定被atomically關鍵字標記的代碼塊必須原子性的執行,也即是說,其他線程看不到代碼塊執行的中間狀態。CAS操作原子性地完成以下操作序列:從某個內存地址中加載,將所讀的值和期望值對比,如果比較成功,那麼將新的值寫入到該內存地址。Herlihy[49]指出像CAS和LL/SC這樣的指令是通用的:對於一個支持這樣指令的系統,任意的並發數據結構都存在wait-free的實現方式。

一個簡單的lock-free計數器可以通過CAS操作來實現。思路是這樣實現fetch-and-inc:首先加載計數器的值,然後通過CAS操作來原子地將計數器的值改變為一個比加載值大1的值。CAS指令只有在加載和CAS操作之間,值發生改變的時候才無法增加計數器。對於這種情况,(操作)可以采取重試,(因為)由此導致的CAS失敗不會造成影響。該實現屬於lock-free方式,因為CAS會因為其他fetch-and-inc操作的成功而失敗。但這不屬於wait-free方式,因為單個fetch-and-inc操作可能在其CAS時會不斷失敗。

上面的例子介紹了一個對同步的樂觀方案:fetch-and-inc操作在期望的大多數情况下,不會和其他並發操作產生沖突,從而快速地完成。但是,一旦出現資源競爭,則需要采用複雜的技術來解决(例如:回退)。

雖然上述的lock-free計數器是容易實現的,但是它有著和那些通過鎖來實現的原始計數器相同的缺點:串行瓶頸和單點資源高競爭。人們很自然地會想到使用上面所討論的類似的實現來改善這個簡單實現的性能。但是通常情况下,優化一個非阻塞實現比優化一個阻塞實現難一些。簡略來說,這是因為一個線程在執行序列操作的時候,可以通過鎖來阻止其他線程的幹擾,如果不用鎖,那麼我們的實現需要保證即使存在並發操作,結果仍然是正確的;在當前的系統架構中,這通常需要使用複雜和耗時的技術,而這樣做會削弱我們對無鎖並發的改進。在1.1.7節中,我們將深入討論事務性內存技術,事務性內存使得設計和實現複雜的並發數據結構變得簡單。但是,支持這一機制的硬件還不存在(譯者注:當時不存在,在Intel Haswell上已經引入這一新技術了[1])。

參考資料:

[1] http://software.intel.com/en-us/blogs/2012/02/07/transactional-synchronization-in-haswell

原創文章,轉載請注明: 轉載自並發編程網 – ifeve.com本文鏈接地址: 並發數據結構-1.1.3 非阻塞技術

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