【原】多線程并發(fā)之原子變量與非阻塞同步機制

IT樂知 2020-07-17

展開全文

前面所有對資源同步的實現(xiàn)都是加鎖，加鎖就會出現(xiàn)阻塞，實際上還可以實現(xiàn)不用加鎖并且是非阻塞實現(xiàn)同步。

加鎖的缺點

通過加鎖能夠保證線程通過獨占的方式來訪問和修改變量，并且對修改后的變量對之后獲得這個鎖的其他線程是可見的。

線程掛起與恢復的開銷：當存在競爭時，競爭失敗的線程會被掛起然后在后面又會恢復運行，即使在恢復中,也要等待其他正在執(zhí)行線程執(zhí)行完他們的時間片，之后才能被調度執(zhí)行。掛起和恢復的過程存在著很大的開銷，有比較長的中斷，在基于鎖并且有更加細粒度的操作，同時鎖上又存在激烈的競爭時，調度的開銷與工作開銷的比值會比較高。

線程被阻塞時間可能很長或者永久阻塞：當持有鎖的線程因為一些其他原因比如I/O、延遲等原因其他被阻塞線程會一直被阻塞，如果持有鎖的線程發(fā)生死鎖、或者死循環(huán)等故障其他線程就會一直阻塞。

更輕量級的同步機制volatile

volatile的內存可見性能夠保證一定的同步機制，但是它對于一些復合操作不能保證原子性，尤其當volatile變量更新時要依賴其他共享變量或者它自身的時候，比如i++等操作。

比較并交換Compare-and-Swap(CAS)

獨占鎖的方式是其中一個獲取了鎖其他線程都不能修改全部等著，等持有鎖的操作完成后其他線程再來。實際上還可以采用一種更高效的方法中：所有線程都可以去獲取變量，然后計算修改，最后在寫入內存，只是在寫入內存的時候再去校驗是否能夠寫入，重點在保證最后的校驗寫入的原子性。

隨著處理器的發(fā)展，現(xiàn)在幾乎所有現(xiàn)代處理器都支持這個功能的指令比較并交換Compare-and-Swap(CAS)。

CAS的使用場景大概解釋是假如程序有一個變量A，內存中有一個變量V，程序想要把內存中值修改成B，CAS的意思就是程序認為內存中的變量V應該等于變量A，判斷如果等于那么就把B設置進去，如果不等于就不設置，無論如何都返回最新的變量V的值。

這樣當多個線程都獲取到內存中的V的變量放到各自的本地變量A中，通過A計算出來了各自的B，當他們同時去設置的時候，只有一個線程能夠設置成功，其他線程都會發(fā)現(xiàn)變量V已經變了，會設置失敗，如果失敗可以根據(jù)新返回的V值從新計算B再次去設置，或者根據(jù)需求直接返回失敗。

CAS方式是將競爭失敗返回給調用者，由調用者處理是重試還是直接失敗，而鎖則是自動處理沒獲取到就阻塞。

原子變量類

原子變量類能夠達到volatile功能，并且支持原子操作和有條件的讀、改、寫操作。

而最常用的是標量類：AtomicInteger、AtomicLong、AtomicBoolean、AtomicReference；并且AtomicInteger、AtomicLong還支持算數(shù)運算。

還有原子數(shù)組類：AtomicIntegerArray、AtomicLongArray、AtomicReferenceArray；原子數(shù)組中的每個元素都可以實現(xiàn)原子更新。

實現(xiàn)非阻塞算法

阻塞算法中持有鎖的線程如果阻塞那么其他線程都不能繼續(xù)執(zhí)行。而如果一個線程的失敗或者掛起不會導致其他線程的失敗或掛起，這種算法就叫做非阻塞算法。

而如果在算法的每個步驟中都存在某個線程能夠執(zhí)行下去，那個這種算法被稱為無鎖算法。如果在算法中僅將CAS用于協(xié)調線程之間的操作，并且能夠正確地實現(xiàn)，那么它既是一種無阻塞算法，也是一種無鎖算法。

我們要實現(xiàn)非阻塞算法的關鍵在于找出如何將原子修改的范圍縮小到單個變量上，同時還要維護數(shù)據(jù)的一致性。通過將原子修改同步到單個變量，然后通過原子變量類實現(xiàn)修改，最終實現(xiàn)非阻塞算法。

下面是一個非阻塞支持并發(fā)鏈表的put方法的實現(xiàn)，代碼如下圖：

1原子變量類實現(xiàn)鏈表

這里是通過AtomicReference來實現(xiàn)，鏈表的實現(xiàn)還與一般的實現(xiàn)不同，put方法最難的是實現(xiàn)兩個步驟的同步，這兩個步驟是：第一步是把節(jié)點加入到尾結點的next節(jié)點中，相當于加入鏈中。第二步是更新tail，記錄LinkedQueue的尾結點。這是兩步操作他們各個可以通過原子變量實現(xiàn)，但是要保證兩步是原子更新基本不可能。

接下來我們來詳解代碼中是如何實現(xiàn)兩次更新的同步的。首先tail和next都用AtomicReference來實現(xiàn)，先保證它們各自更新為原子操作，我們來看代碼中是如何保證這兩步更新操作的安全。主要在倒數(shù)3個注釋中，分別簡稱1、2、3，接下來是3個步驟的詳細解答：

第一個put進來實際上是先走到2處嘗試把newNode更新到tail的next上。如果這一步執(zhí)行成功后有可能另外一個線程進來了。

新線程會發(fā)現(xiàn)由于tail的next不為null。就知道是有其他線程也在put，并且已經成功一半了。所以這個線程會幫它操作剩下的步驟，把tail的next節(jié)點更新到tail上。這一步完成后又會再次循環(huán)嘗試，直到成功。

當?shù)谝粋€線程在開始執(zhí)行第3步的時候由于tail中的node已經與它持有的curTail不是同一個對象了，是有其他線程已經幫它完成了，所以不會再更新，不過也會返回true。

通過這種方式所有的put方法最終都會成功，并且即使有一個線程因為什么原因阻塞了也不會影響到其他線程。