非阻塞算法和互斥

Question

維基百科說：

非阻塞算法確保 線程共享 資源競爭沒有自己的執行 無限期相互排斥 推遲。

如何確保在多個線程需要訪問某個臨界區時實現這個目標？

Answer 1

請原諒的文章，但是，往往是我的寫作風格。

非阻塞算法有各種形狀，但基本思想是構造算法，使得您可以在一個或多或少的確定性步驟中完成，而不是無限期地被鎖定停止。如果您的操作可能很耗時，有時您可以做的最好的做法是確保您的線程有其他工作來推進程序的整體操作。

並非所有的算法都是適用於非阻塞方法，許多無阻塞方法有小的臨界區在其中，因此不會嚴格地說無阻塞，但在實踐中表現得如此。在實現任何類型的併發時都要用腦，因爲它是調試的熊，無論你是否是有經驗的程序員。

- =無阻塞算法= -

原子算法執行中發生的不能被中斷的單個步驟的更新。一個簡單的例子是使用++或+ =遞增一個值，當更新發生時，它逐字地歸結爲單個CPU指令，因此將完成而沒有被中斷的可能性，並且如果多處理中斷了CPU，則CPU將修復它更新。我不太清楚在一條CPU指令觸及多個數據段時，這會延伸到SIMD指令的範圍。

如果您有一種算法不需要返回值，那麼您可以使用生產者/消費者隊列系統，其中只有隊列是基於鎖的，或者可能使用原子更新將項插入隊列。無論哪種情況，隊列都會很快更新，並且在消費者線程處理積壓時，控制權會返回給調用者。網絡和磁盤寫入通常具有這種變化。

如果需要返回值，在操作完成時的回調可以通知你的線程，或者一些新的數據可爲您處理。最理想的是，您還有其他事情要做，而不是簡單地等待回調。

CAS算法，其中讀取和更新確保在首次完成時獲勝系統是確保進度的另一種方式，但中止需要時間，因此如果算法需要重試，可能會創建非確定性完成時間當發生中止時。數據庫使用一種稱爲樂觀鎖定的事務完成類型的CAS。當爭用率較低時，或者在爭用需要通知用戶並收集其他輸入的情況下，這種方式效果最佳。

- =阻止算法= -

阻塞算法塊中的所有的向前進展，但螺紋（或多個）單個或多個小試圖在共享資源上進行操作。如果操作冗長，這可能會導致嚴重的延遲，所以任何阻塞算法的目標都應該是將發生爭用的關鍵部分減少到儘可能小的整體算法的一小部分。執行此操作的數據庫事務使用悲觀鎖定。

- =死鎖和活鎖= -

死鎖是兩個線程分別阻斷彼此，通常是因爲每個持有鎖的其它想要的。

活鎖可能發生在兩個線程再次希望訪問其他控件的資源的情況下，或者兩個線程完全由它們相互發送的數據使用的情況。在任何一種情況下，該算法都會不斷等待，直到取得進展，但是這兩個（或者更多）線程在不進行真正的前進過程的情況下繼續旋轉。

- =重要性= -

爲什麼這些重要？任何併發的主要問題是可能出現不可預知的狀態，因爲兩個線程在相同的數據上運行而不考慮彼此的變化。爲了防止這種情況發生，可以使用阻塞和非阻塞算法，但如果出錯，最終可能導致死鎖，活鎖或數據損壞。

我希望這強調併發問題同時存在於阻塞和非阻塞算法中，無論您選擇的殺死併發野獸的方法如何，您都必須密切關注您的程序的結構使用方式，或者提供共享資源。

Answer 2

非阻塞算法，充分利用中科院：Java Concurrency: CAS vs Locking