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

加鎖的缺點(diǎn)

通過(guò)加鎖能夠保證線(xiàn)程通過(guò)獨(dú)占的方式來(lái)訪(fǎng)問(wèn)和修改變量，并且對(duì)修改后的變量對(duì)之后獲得這個(gè)鎖的其他線(xiàn)程是可見(jiàn)的。

線(xiàn)程掛起與恢復(fù)的開(kāi)銷(xiāo)：當(dāng)存在競(jìng)爭(zhēng)時(shí)，競(jìng)爭(zhēng)失敗的線(xiàn)程會(huì)被掛起然后在后面又會(huì)恢復(fù)運(yùn)行，即使在恢復(fù)中,也要等待其他正在執(zhí)行線(xiàn)程執(zhí)行完他們的時(shí)間片，之后才能被調(diào)度執(zhí)行。掛起和恢復(fù)的過(guò)程存在著很大的開(kāi)銷(xiāo)，有比較長(zhǎng)的中斷，在基于鎖并且有更加細(xì)粒度的操作，同時(shí)鎖上又存在激烈的競(jìng)爭(zhēng)時(shí)，調(diào)度的開(kāi)銷(xiāo)與工作開(kāi)銷(xiāo)的比值會(huì)比較高。

線(xiàn)程被阻塞時(shí)間可能很長(zhǎng)或者永久阻塞：當(dāng)持有鎖的線(xiàn)程因?yàn)橐恍┢渌虮热鏘/O、延遲等原因其他被阻塞線(xiàn)程會(huì)一直被阻塞，如果持有鎖的線(xiàn)程發(fā)生死鎖、或者死循環(huán)等故障其他線(xiàn)程就會(huì)一直阻塞。

更輕量級(jí)的同步機(jī)制volatile

volatile的內(nèi)存可見(jiàn)性能夠保證一定的同步機(jī)制，但是它對(duì)于一些復(fù)合操作不能保證原子性，尤其當(dāng)volatile變量更新時(shí)要依賴(lài)其他共享變量或者它自身的時(shí)候，比如i++等操作。

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

獨(dú)占鎖的方式是其中一個(gè)獲取了鎖其他線(xiàn)程都不能修改全部等著，等持有鎖的操作完成后其他線(xiàn)程再來(lái)。實(shí)際上還可以采用一種更高效的方法中：所有線(xiàn)程都可以去獲取變量，然后計(jì)算修改，最后在寫(xiě)入內(nèi)存，只是在寫(xiě)入內(nèi)存的時(shí)候再去校驗(yàn)是否能夠?qū)懭?，重點(diǎn)在保證最后的校驗(yàn)寫(xiě)入的原子性。

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

CAS的使用場(chǎng)景大概解釋是假如程序有一個(gè)變量A，內(nèi)存中有一個(gè)變量V，程序想要把內(nèi)存中值修改成B，CAS的意思就是程序認(rèn)為內(nèi)存中的變量V應(yīng)該等于變量A，判斷如果等于那么就把B設(shè)置進(jìn)去，如果不等于就不設(shè)置，無(wú)論如何都返回最新的變量V的值。

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

CAS方式是將競(jìng)爭(zhēng)失敗返回給調(diào)用者，由調(diào)用者處理是重試還是直接失敗，而鎖則是自動(dòng)處理沒(méi)獲取到就阻塞。

原子變量類(lèi)

原子變量類(lèi)能夠達(dá)到volatile功能，并且支持原子操作和有條件的讀、改、寫(xiě)操作。

而最常用的是標(biāo)量類(lèi)：AtomicInteger、AtomicLong、AtomicBoolean、AtomicReference；并且AtomicInteger、AtomicLong還支持算數(shù)運(yùn)算。

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

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

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

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

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

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

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

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

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

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

當(dāng)?shù)谝粋€(gè)線(xiàn)程在開(kāi)始執(zhí)行第3步的時(shí)候由于tail中的node已經(jīng)與它持有的curTail不是同一個(gè)對(duì)象了，是有其他線(xiàn)程已經(jīng)幫它完成了，所以不會(huì)再更新，不過(guò)也會(huì)返回true。

通過(guò)這種方式所有的put方法最終都會(huì)成功，并且即使有一個(gè)線(xiàn)程因?yàn)槭裁丛蜃枞艘膊粫?huì)影響到其他線(xiàn)程。

總結(jié)

synchronized、Lock都是在獲取不到資源的時(shí)候會(huì)阻塞線(xiàn)程，而非阻塞算法就在于多個(gè)線(xiàn)程競(jìng)爭(zhēng)同一個(gè)資源時(shí)不會(huì)發(fā)生阻塞，因此它能夠在粒度更細(xì)的層次上進(jìn)行協(xié)調(diào)，并且極大地減少調(diào)度開(kāi)銷(xiāo)，并且非阻塞算法不會(huì)發(fā)生死鎖和其他活躍性問(wèn)題。

Java程序員日常學(xué)習(xí)筆記，如理解有誤歡迎各位交流討論！