在并發上下文中，非阻塞算法是一種允許線程在阻塞其他線程的情況下通路共享狀态的算法。在絕大多數項目中，在算法中如果一個線程的挂起沒有導緻其它的線程挂起，我們就說這個算法是非阻塞的。
為了更好的了解阻塞算法和非阻塞算法之間的差別，我會先講解阻塞算法然後再講解非阻塞算法。
一個阻塞并發算法一般分下面兩步：
執行線程請求的操作
阻塞線程直到可以安全地執行操作
很多算法和并發資料結構都是阻塞的。例如，<code>java.util.concurrent.blockingqueue</code>的不同實作都是阻塞資料結構。如果一個線程要往一個阻塞隊列中插入一個元素，隊列中沒有足夠的空間，執行插入操作的線程就會阻塞直到隊列中有了可以存放插入元素的空間。
下圖示範了一個阻塞算法保證一個共享資料結構的行為：
一個非阻塞并發算法一般包含下面兩步：
通知請求線程操作不能被執行
java也包含幾個非阻塞資料結構。<code>atomicboolean</code>,<code>atomicinteger</code>,<code>atomiclong</code>,<code>atomicreference</code>都是非阻塞資料結構的例子。
下圖示範了一個非阻塞算法保證一個共享資料結構的行為：
阻塞算法和非阻塞算法的主要不同在于上面兩部分描述的它們的行為的第二步。換句話說，它們之間的不同在于當請求操作不能夠執行時阻塞算法和非阻塞算法會怎麼做。
阻塞算法會阻塞線程知道請求操作可以被執行。非阻塞算法會通知請求線程操作不能夠被執行，并傳回。
一個使用了阻塞算法的線程可能會阻塞直到有可能去處理請求。通常，其它線程的動作使第一個線程執行請求的動作成為了可能。 如果，由于某些原因線程被阻塞在程式某處，是以不能讓第一個線程的請求動作被執行，第一個線程會阻塞——可能一直阻塞或者直到其他線程執行完必要的動作。
例如，如果一個線程産生往一個已經滿了的阻塞隊列裡插入一個元素，這個線程就會阻塞，直到其他線程從這個阻塞隊列中取走了一些元素。如果由于某些原因，從阻塞隊列中取元素的線程假定被阻塞在了程式的某處，那麼，嘗試往阻塞隊列中添加新元素的線程就會阻塞，要麼一直阻塞下去，要麼知道從阻塞隊列中取元素的線程最終從阻塞隊列中取走了一個元素。
在一個多線程系統中，線程間通常通過一些資料結構”交流“。例如可以是任何的資料結構，從變量到更進階的俄資料結構（隊列，棧等）。為了確定正确，并發線程在通路這些資料結構的時候，這些資料結構必須由一些并發算法來保證。這些并發算法讓這些資料結構成為并發資料結構。
如果某個算法確定一個并發資料結構是阻塞的，它就被稱為是一個阻塞算法。這個資料結構也被稱為是一個阻塞，并發資料結構。
如果某個算法確定一個并發資料結構是非阻塞的，它就被稱為是一個非阻塞算法。這個資料結構也被稱為是一個非阻塞，并發資料結構。
每個并發資料結構被設計用來支援一個特定的通信方法。使用哪種并發資料結構取決于你的通信需要。在接下裡的部分，我會引入一些非阻塞并發資料結構，并講解它們各自的适用場景。通過這些并發資料結構工作原理的講解應該能在非阻塞資料結構的設計和實作上一些啟發。
java中的<code>volatile</code>變量是直接從主存中讀取值的變量。當一個新的值賦給一個<code>volatile</code>變量時，這個值總是會被立即寫回到主存中去。這樣就確定了，一個<code>volatile</code>變量最新的值總是對跑在其他cpu上的線程可見。其他線程每次會從主存中讀取變量的值，而不是比如線程所運作cpu的cpu緩存中。
<code>colatile</code>變量是非阻塞的。修改一個<code>volatile</code>變量的值是一耳光原子操作。它不能夠被中斷。不過，在一個<code>volatile</code>變量上的一個 read-update-write 順序的操作不是原子的。是以，下面的代碼如果由多個線程執行可能導緻競态條件。
首先，<code>myvar</code>這個volatile變量的值被從主存中讀出來賦給了<code>temp</code>變量。然後，<code>temp</code>變量自增1。然後，<code>temp</code>變量的值又賦給了<code>myvar</code>這個volatile變量這意味着它會被寫回到主存中。
如果兩個線程執行這段代碼，然後它們都讀取<code>myvar</code>的值，加1後，把它的值寫回到主存。這樣就存在<code>myvar</code>僅被加1，而沒有被加2的風險。
你可能認為你不會寫像上面這樣的代碼，但是在實踐中上面的代碼等同于如下的代碼：
執行上面的代碼時，<code>myvar</code>的值讀到一個cpu寄存器或者一個本地cpu緩存中，myvar加1，然後這個cpu寄存器或者cpu緩存中的值被寫回到主存中。
在一些場景下，你僅有一個線程在向一個共享變量寫，多個線程在讀這個變量。當僅有一個線程在更新一個變量，不管有多少個線程在讀這個變量，都不會發生競态條件。是以，無論時候當僅有一個線程在寫一個共享變量時，你可以把這個變量聲明為<code>volatile</code>。
當多個線程在一個共享變量上執行一個 read-update-write 的順序操作時才會發生競态條件。如果你隻有一個線程在執行一個 raed-update-write 的順序操作，其他線程都在執行讀操作，将不會發生競态條件。
下面是一個單個寫線程的例子，它沒有采取同步手段但任然是并發的。
多個線程通路同一個<code>counter</code>執行個體，隻要僅有一個線程調用<code>inc()</code>方法，這裡，我不是說在某一時刻一個線程，我的意思是，僅有相同的，單個的線程被允許去調用<code>inc()></code>方法。多個線程可以調用<code>count()</code>方法。這樣的場景将不會發生任何競态條件。
下圖，說明了線程是如何通路<code>count</code>這個volatile變量的。
使用多個<code>volatile</code>變量去建立資料結構是可以的，建構出的資料結構中每一個<code>volatile</code>變量僅被一個單個的線程寫，被多個線程讀。每個<code>volatile</code>變量可能被一個不同的線程寫（但僅有一個）。使用像這樣的資料結構多個線程可以使用這些<code>volatile</code>變量以一個非阻塞的方法彼此發送資訊。
下面是一個簡單的例子：
如你所見，<code>doublewritercoounter</code>現在包含兩個<code>volatile</code>變量以及兩對自增和讀方法。在某一時刻，僅有一個單個的線程可以調用<code>inc()</code>，僅有一個單個的線程可以通路<code>incb()</code>。不過不同的線程可以同時調用<code>inca()</code>和<code>incb()</code>。<code>counta()</code>和<code>countb()</code>可以被多個線程調用。這将不會引發競态條件。
<code>doublewritercoounter</code>可以被用來比如線程間通信。counta和countb可以分别用來存儲生産的任務數和消費的任務數。下圖，展示了兩個線程通過類似于上面的一個資料結構進行通信的。
聰明的讀者應該已經意識到使用兩個<code>singlewritercounter</code>可以達到使用<code>doublewritercoounter</code>的效果。如果需要，你甚至可以使用多個線程和<code>singlewritercounter</code>執行個體。
注意，，<code>inc()</code>和<code>count()</code>方法都包含一個同步塊。這也是我們像避免的東西——同步塊和 wait()-notify 調用等。
我們可以使用一種java的原子變量來代替這兩個同步塊。在這個例子是<code>atomiclong</code>。下面是synchronizedcounter類的atomiclong實作版本。
上面這些代碼并不是一個原子操作。也就是說，對于兩個不同的線程去調用<code>inc()</code>方法，然後執行<code>long prevcount = this.count.get()</code>語句，是以獲得了這個計數器的上一個count。但是，上面的代碼并沒有包含任何的競态條件。
秘密就在于<code>while</code>循環裡的第二行代碼。<code>compareandset()</code>方法調用是一個原子操作。它用一個期望值和atomiclong 内部的值去比較，如果這兩個值相等，就把atomiclong内部值替換為一個新值。<code>compareandset()</code>通常被cpu中的<code>compare-and-swap</code>指令直接支援。是以，不需要去同步，也不需要去挂起線程。
假設，這個<code>atomiclong</code>的内部值是20,。然後，兩個線程去讀這個值，都嘗試調用<code>compareandset(20, 20 + 1)</code>。盡管<code>compareandset()</code>是一個原子操作，這個方法也會被這兩個線程相繼執行（某一個時刻隻有一個）。
第一個線程會使用期望值20（這個計數器的上一個值）與atomiclong的内部值進行比較。由于兩個值是相等的，atomiclong會更新它的内部值至21（20 + 1 ）。變量<code>updated</code>被修改為true，while循環結束。
現在，第二個線程調用<code>compareandset(20, 20 + 1)</code>。由于atomiclong的内部值不再是20，這個調用将不會成功。atomiclong的值不會再被修改為21。變量，<code>updated</code>被修改為false，線程将會再次在while循環外自旋。這段時間，它會讀到值21并企圖把值更新為22。如果在此期間沒有其它線程調用<code>inc()</code>。第二次疊代将會成功更新atomiclong的内部值到22。
上一部分展現的代碼被稱為樂觀鎖（optimistic locking）。樂觀鎖差別于傳統的鎖，有時也被稱為悲觀鎖。傳統的鎖會使用同步塊或其他類型的鎖阻塞對臨界區域的通路。一個同步塊或鎖可能會導緻線程挂起。
樂觀鎖允許所有的線程在不發生阻塞的情況下建立一份共享記憶體的拷貝。這些線程接下來可能會對它們的拷貝進行修改，并企圖把它們修改後的版本寫回到共享記憶體中。如果沒有其它線程對共享記憶體做任何修改， cas操作就允許線程将它的變化寫回到共享記憶體中去。如果，另一個線程已經修改了共享記憶體，這個線程将不得不再次獲得一個新的拷貝，在新的拷貝上做出修改，并嘗試再次把它們寫回到共享記憶體中去。
稱之為“樂觀鎖”的原因就是，線程獲得它們想修改的資料的拷貝并做出修改，在樂觀的假在此期間沒有線程對共享記憶體做出修改的情況下。當這個樂觀假設成立時，這個線程僅僅在無鎖的情況下完成共享記憶體的更新。當這個假設不成立時，線程所做的工作就會被丢棄，但任然不使用鎖。
樂觀鎖使用于共享記憶體競用不是非常高的情況。如果共享記憶體上的内容非常多，僅僅因為更新共享記憶體失敗，就用浪費大量的cpu周期用在拷貝和修改上。但是，如果砸共享記憶體上有大量的内容，無論如何，你都要把你的代碼設計的産生的争用更低。
我們這裡提到的樂觀鎖機制是非阻塞的。如果一個線程獲得了一份共享記憶體的拷貝，當嘗試修改時，發生了阻塞，其它線程去通路這塊記憶體區域不會發生阻塞。
對于一個傳統的加鎖/解鎖模式，當一個線程持有一個鎖時，其它所有的線程都會一直阻塞直到持有鎖的線程再次釋放掉這個鎖。如果持有鎖的這個線程被阻塞在某處，這個鎖将很長一段時間不能被釋放，甚至可能一直不能被釋放。
簡單的cas樂觀鎖可以用于共享資料結果，這樣一來，整個資料結構都可以通過一個單個的cas操作被替換成為一個新的資料結構。盡管，使用一個修改後的拷貝來替換真個資料結構并不總是可行的。
假設，這個共享資料結構是隊列。每當線程嘗試從向隊列中插入或從隊列中取出元素時，都必須拷貝這個隊列然後在拷貝上做出期望的修改。我們可以通過使用一個<code>atomicreference</code>來達到同樣的目的。拷貝引用，拷貝和修改隊列，嘗試替換在<code>atomicreference</code>中的引用讓它指向新建立的隊列。
然而，一個大的資料結構可能會需要大量的記憶體和cpu周期來複制。這會使你的程式占用大量的記憶體和浪費大量的時間再拷貝操作上。這将會降低你的程式的性能，特别是這個資料結構的競用非常高情況下。更進一步說，一個線程花費在拷貝和修改這個資料結構上的時間越長，其它線程在此期間修改這個資料結構的可能性就越大。如你所知，如果另一個線程修改了這個資料結構在它被拷貝後，其它所有的線程都不等不再次執行 拷貝-修改 操作。這将會增大性能影響和記憶體浪費，甚至更多。
接下來的部分将會講解一種實作非阻塞資料結構的方法，這種資料結構可以被并發修改，而不僅僅是拷貝和修改。
用來替換拷貝和修改整個資料結構，一個線程可以共享它們對共享資料結構預期的修改。一個線程向對修改某個資料結構的過程變成了下面這樣：
檢查是否另一個線程已經送出了對這個資料結構送出了修改
如果沒有其他線程送出了一個預期的修改，建立一個預期的修改，然後向這個資料結構送出預期的修改
執行對共享資料結構的修改
移除對這個預期的修改的引用，向其它線程發送信号，告訴它們這個預期的修改已經被執行
如你所見，第二步可以阻塞其他線程送出一個預期的修改。是以，第二步實際的工作是作為這個資料結構的一個鎖。如果一個線程已經成功送出了一個預期的修改，其他線程就不可以再送出一個預期的修改直到第一個預期的修改執行完畢。
如果一個線程送出了一個預期的修改，然後做一些其它的工作時發生阻塞，這時候，這個共享資料結構實際上是被鎖住的。其它線程可以檢測到它們不能夠送出一個預期的修改，然後回去做一些其它的事情。很明顯，我們需要解決這個問題。
為了避免一個已經送出的預期修改可以鎖住共享資料結構，一個已經送出的預期修改必須包含足夠的資訊讓其他線程來完成這次修改。是以，如果一個送出了預期修改的線程從未完成這次修改，其他線程可以在它的支援下完成這次修改，保證這個共享資料結構對其他線程可用。
下圖說明了上面描述的非阻塞算法的藍圖：
修改必須被當做一個或多個cas操作來執行。是以，如果兩個線程嘗試去完成同一個預期修改，僅有一個線程可以所有的cas操作。一旦一條cas操作完成後，再次企圖完成這個cas操作都不會“得逞”。
上面示範的算法可以稱之為a-b-a問題。a-b-a問題指的是一個變量被從a修改到了b，然後又被修改回a的一種情景。其他線程對于這種情況卻一無所知。
如果線程a檢查正在進行的資料更新，拷貝，被線程排程器挂起，一個線程b在此期可能可以通路這個共享資料結構。如果線程對這個資料結構執行了全部的更新，移除了它的預期修改，這樣看起來，好像線程a自從拷貝了這個資料結構以來沒有對它做任何的修改。然而，一個修改确實已經發生了。當線程a繼續基于現在已經過期的資料拷貝執行它的更新時，這個資料修改已經被線程b的修改破壞。
下圖說明了上面提到的a-b-a問題：
a-b-a通常的解決方法就是不再僅僅替換指向一個預期修改對象的指針，而是指針結合一個計數器，然後使用一個單個的cas操作來替換指針 + 計數器。這在支援指針的語言像c和c++中是可行的。是以，盡管目前修改指針被設定回指向 “不是正在進行的修改”（no ongoing modification），指針 + 計數器的計數器部分将會被自增，使修改對其它線程是可見的。
在java中，你不能将一個引用和一個計數器歸并在一起形成一個單個的變量。不過java提供了<code>atomicstampedreference</code>類，利用這個類可以使用一個cas操作自動的替換一個引用和一個标記（stamp）。
下面的代碼意在在如何實作非阻塞算法上一些啟發。這個模闆基于這篇教程所講的東西。
注意：在非阻塞算法方面，我并不是一位專家，是以，下面的模闆可能錯誤。不要基于我提供的模闆實作自己的非阻塞算法。這個模闆意在給你一個關于非阻塞算法大緻是什麼樣子的一個idea。如果，你想實作自己的非阻塞算法，首先學習一些實際的工業水準的非阻塞算法的時間，在實踐中學習更多關于非阻塞算法實作的知識。
正确的設計和實作非阻塞算法是不容易的。在嘗試設計你的非阻塞算法之前，看一看是否已經有人設計了一種非阻塞算法正滿足你的需求。
java已經提供了一些非阻塞實作（比如 concurrentlinkedqueue），相信在java未來的版本中會帶來更多的非阻塞算法的實作。
非阻塞算法和阻塞算法相比有幾個好處。下面讓我們分别看一下：
非阻塞算法的第一個好處是，給了線程一個選擇當它們請求的動作不能夠被執行時做些什麼。不再是被阻塞在那，請求線程關于做什麼有了一個選擇。有時候，一個線程什麼也不能做。在這種情況下，它可以選擇阻塞或自我等待，像這樣把cpu的使用權讓給其它的任務。不過至少給了請求線程一個選擇的機會。
在一個單個的cpu系統可能會挂起一個不能執行請求動作的線程，這樣可以讓其它線程獲得cpu的使用權。不過即使在一個單個的cpu系統阻塞可能導緻死鎖，線程饑餓等并發問題。
非阻塞算法的第二個好處是，一個線程的挂起不能導緻其它線程挂起。這也意味着不會發生死鎖。兩個線程不能互相彼此等待來獲得被對方持有的鎖。因為線程不會阻塞當它們不能執行它們的請求動作時，它們不能阻塞互相等待。非阻塞算法任然可能産生活鎖（live lock），兩個線程一直請求一些動作，但一直被告知不能夠被執行（因為其他線程的動作）。
挂起和恢複一個線程的代價是昂貴的。沒錯，随着時間的推移，作業系統和線程庫已經越來越高效，線程挂起和恢複的成本也不斷降低。不過，線程的挂起和戶對任然需要付出很高的代價。
無論什麼時候，一個線程阻塞，就會被挂起。是以，引起了線程挂起和恢複過載。由于使用非阻塞算法線程不會被挂起，這種過載就不會發生。這就意味着cpu有可能花更多時間在執行實際的業務邏輯上而不是上下文切換。
在一個多個cpu的系統上，阻塞算法會對阻塞算法産生重要的影響。運作在cpua上的一個線程阻塞等待運作在cpu b上的一個線程。這就降低了程式天生就具備的并行水準。當然，cpu a可以排程其他線程去運作，但是挂起和激活線程（上下文切換）的代價是昂貴的。需要挂起的線程越少越好。
在這裡我們提到的延遲指的是一個請求産生到線程實際的執行它之間的時間。因為在非阻塞算法中線程不會被挂起，它們就不需要付昂貴的，緩慢的線程激活成本。這就意味着當一個請求執行時可以得到更快的響應，減少它們的響應延遲。
非阻塞算法通常忙等待直到請求動作可以被執行來降低延遲。當然，在一個非阻塞資料資料結構有着很高的線程争用的系統中，cpu可能在它們忙等待期間停止消耗大量的cpu周期。這一點需要牢牢記住。非阻塞算法可能不是最好的選擇如果你的資料結構哦有着很高的線程争用。不過，也常常存在通過重構你的程式來達到更低的線程争用。