鎖定自由同步

我的問題涉及到多線程無鎖同步。我想知道以下內容：鎖定自由同步

什麼是實現此目的的一般方法？我讀了一些關於LockFreePrimitives的地方，比如CompareAndExchange（CAS）或DoubleCompareAndExchange（DCA），但沒有給出這些解釋嗎？任何最小化使用鎖的方法？
Java/.NET如何實現其併發容器？他們使用鎖還是無鎖同步？

在此先感謝。

來源

2012-02-01 Bober02

下面是可以最大限度地減少鎖的使用一些通用的方法，假設你的算法有一些特定的可利用的特點：

當更新一個數字變量，你可以使用非阻塞原語如CAS ，atomic_increment等。它們通常比經典的阻塞臨界區（鎖，互斥鎖）快得多。
當數據結構被多個線程讀取，但只能由一個或幾個線程寫入時，顯而易見的解決方案將是讀寫鎖定，而不是完全鎖定。
嘗試利用細粒鎖定。例如，不是使用單個鎖來鎖定整個數據結構，而是使用多個不同的鎖來保護數據結構的不同部分。
如果你依靠鎖的內隱記憶柵欄效應，以保證跨線程的單一變量的可見性，只需使用volatile ，如果有的話。
有時候，使用條件變量（和相關的鎖）在實踐中太慢了。在這種情況下，一個volatile繁忙的旋轉效率更高。關於這一主題在這裏

一個很好的讀取在另一個SO問題：Lock-free multi-threading is for real threading experts（不要被標題嚇到）。

而且atomic_decrement的最近討論無鎖的Java實現：Starvation in non-blocking approaches

採用volatile這裏適用於如Java語言，其中volatile已經在存儲模型中定義語義，但不到C或C++，其中volatile在引入跨線程內存模型之前並未與其集成。類似的結構可用於這些語言，例如C++中的各種std::memory_order說明符。

來源

2012-02-01 21:49:35 Tudor

你有一些好點，但＃4是錯的。 'volatile'不能達到你期望的效果。它可能會阻止編譯器進行一些優化，但不會阻止處理器重新排序讀取，因此無法替代障礙。 – ugoren 2012-02-01 22:16:39

@ugoren這在Java上下文中不正確。易失性讀取/存儲部署必要的內存障礙。 – 2012-02-01 22:24:24

@JohnVint，我承認我對Java不太瞭解，並且正在考慮C（其中volatile是最容易被誤解的關鍵字）。由於該問題沒有標記爲「Java」，因此至少應該明確這一點。 – ugoren 2012-02-01 22:42:02

比較和交換是有用的，但有一個更簡單的（所謂'無鎖'）技術，在某些生產者/消費者用例中很有用，所以我會提及它。

想象一下，您有一個寫入緩衝區的函數doWork（）。

線程A初始化易失性布爾變量（標誌）爲假是由兩個線程A訪問並創建易失性緩衝區對象的doWork將輸出到線程B（全球等）。
線程A創建調用doWork（）的線程B.
線程B的doWork（）開始創建/寫入緩衝區。完成後，它將布爾值設置爲true。
線程A可以輪詢一個開始爲false的全局布爾標誌。當它變爲真（非假）時，它可以訪問緩衝區對象中的數據，確保完成。在民意調查之間線程A可以做其他工作。（例如，它在更新調用中輪詢一次，不等待真正的值）。這不考慮錯誤處理，但這也可以在緩衝區內處理。

這隻適用於因爲A只能讀取而B只能寫入，但這個用例對'後臺工作者'線程來說是相當普遍的。這隻能確保在Java或C＃上工作，其中volatile會附帶保證。

來源

2012-02-01 22:02:29

您不能使用簡單的布爾值進行此類同步。編譯器和/或處理器可能會重新排列您的讀取，導致錯誤。你認爲你先閱讀布爾（並且看到它是真的），然後纔讀取緩衝區。但實際上（你得到「半焙」的數據），讀數可能會顛倒。你需要一個信號量。 – ugoren 2012-02-01 22:14:04

我相信永遠不會有線程A首先讀取並使用緩衝區的情況，因爲它是在條件依賴值中讀取布爾值讀取的，編譯器不會切換這些東西。這就是爲什麼你可以編寫一個條件來檢查空指針，然後使用指針。 – 2012-02-01 22:22:30

我並不反對原則，但在多線程編程中，這是一個很大的錯誤。編譯器可能會或可能不會切換任何東西，但CPU可能會涉及到不同的地址。英特爾CPU做了很多重新排序，而且我已經看到了由此產生的驚人錯誤。 – ugoren 2012-02-01 22:40:20

有一些有用的方法可以使用無鎖同步（比如那些@Tudor提及）。但是我想告誡一件事 - 無鎖同步不構成。

例如，您可能有一個由比較&交換維護的整數，並且沒關係。你也可能有一個隊列，由一個無鎖算法維護（這有點棘手，但有很好的算法），隊列也可以。
但是，如果您嘗試使用計數器來計算隊列中的元素，您將得到錯誤的答案。有時候會添加一個元素，但計數器還沒有反映出來（反之亦然），如果您信任它（例如，您可能嘗試添加到完整隊列中），則可以獲取錯誤。

總之 - 你可以讓每個元素與自身一致，但彼此不一致。

來源

2012-02-01 22:21:37 ugoren

鎖定自由同步

回答

相關問題