java™ 5.0 第一次讓使用 java 語言開發非阻塞算法成為可能，<code>java.util.concurrent</code> 包充分地利用了這個功能。非阻塞算法屬于并發算法，它們可以安全地派生它們的線程，不通過鎖定派生，而是通過低級的原子性的硬體原生形式
—— 例如比較和交換。非阻塞算法的設計與實作極為困難，但是它們能夠提供更好的吞吐率，對生存問題（例如死鎖和優先級反轉）也能提供更好的防禦。在這期的 java
理論與實踐 中，并發性大師 brian goetz 示範了幾種比較簡單的非阻塞算法的工作方式。
在不隻一個線程通路一個互斥的變量時，所有線程都必須使用同步，否則就可能會發生一些非常糟糕的事情。java 語言中主要的同步手段就是 <code>synchronized</code> 關鍵字（也稱為内在鎖），它強制實行互斥，確定執行 <code>synchronized</code> 塊的線程的動作，能夠被後來執行受相同鎖保護的 <code>synchronized</code> 塊的其他線程看到。在使用得當的時候，内在鎖可以讓程式做到線程安全，但是在使用鎖定保護短的代碼路徑，而且線程頻繁地争用鎖的時候，鎖定可能成為相當繁重的操作。
volatile 變量類似，但是因為它們也可以被原子性地修改，是以可以把它們用作不使用鎖的并發算法的基礎。
清單 1 中的 <code>counter</code> 是線程安全的，但是使用鎖的需求帶來的性能成本困擾了一些開發人員。但是鎖是必需的，因為雖然增加看起來是單一操作，但實際是三個獨立操作的簡化：檢索值，給值加
1，再寫回值。（在 <code>getvalue</code> 方法上也需要同步，以保證調用 <code>getvalue</code> 的線程看到的是最新的值。雖然許多開發人員勉強地使自己相信忽略鎖定需求是可以接受的，但忽略鎖定需求并不是好政策。）
在多個線程同時請求同一個鎖時，會有一個線程獲勝并得到鎖，而其他線程被阻塞。jvm 實作阻塞的方式通常是挂起阻塞的線程，過一會兒再重新排程它。由此造成的上下文切換相對于鎖保護的少數幾條指令來說，會造成相當大的延遲。
清單 2 中的 <code>nonblockingcounter</code> 顯示了一種最簡單的非阻塞算法：使用 <code>atomicinteger</code> 的 <code>compareandset()</code> （cas）方法的計數器。<code>compareandset()</code> 方法規定
“比較和設定” 的更多解釋。）
原子變量類之是以被稱為原子的，是因為它們提供了對數字和對象引用的細粒度的原子更新，但是在作為非阻塞算法的基本構造塊的意義上，它們也是原子的。非阻塞算法作為科研的主題，已經有 20 多年了，但是直到 java 5.0 出現，在 java 語言中才成為可能。
現代的處理器提供了特殊的指令，可以自動更新共享資料，而且能夠檢測到其他線程的幹擾，而 <code>compareandset()</code> 就用這些代替了鎖定。（如果要做的隻是遞增計數器，那麼 <code>atomicinteger</code> 提供了進行遞增的方法，但是這些方法基于 <code>compareandset()</code>，例如<code>nonblockingcounter.increment()</code>）。
非阻塞版本相對于基于鎖的版本有幾個性能優勢。首先，它用硬體的原生形态代替 jvm 的鎖定代碼路徑，進而在更細的粒度層次上（獨立的記憶體位置）進行同步，失敗的線程也可以立即重試，而不會被挂起後重新排程。更細的粒度降低了争用的機會，不用重新排程就能重試的能力也降低了争用的成本。即使有少量失敗的 cas 操作，這種方法仍然會比由于鎖争用造成的重新排程快得多。
<code>nonblockingcounter</code> 這個示例可能簡單了些，但是它示範了所有非阻塞算法的一個基本特征
—— 有些算法步驟的執行是要冒險的，因為知道如果 cas 不成功可能不得不重做。非阻塞算法通常叫作樂觀算法，因為它們繼續操作的假設是不會有幹擾。如果發現幹擾，就會回退并重試。在計數器的示例中，冒險的步驟是遞增 —— 它檢索舊值并在舊值上加一，希望在計算更新期間值不會變化。如果它的希望落空，就會再次檢索值，并重做遞增計算。
非阻塞算法稍微複雜一些的示例是清單 3 中的 <code>concurrentstack</code>。<code>concurrentstack</code> 中的 <code>push()</code> 和 <code>pop()</code> 操作在結構上與<code>nonblockingcounter</code> 上相似，隻是做的工作有些冒險，希望在
“送出” 工作的時候，底層假設沒有失效。<code>push()</code> 方法觀察目前最頂的節點，建構一個新節點放在堆棧上，然後，如果最頂端的節點在初始觀察之後沒有變化，那麼就安裝新節點。如果
cas 失敗，意味着另一個線程已經修改了堆棧，那麼過程就會重新開始。
在輕度到中度的争用情況下，非阻塞算法的性能會超越阻塞算法，因為 cas 的多數時間都在第一次嘗試時就成功，而發生争用時的開銷也不涉及線程挂起和上下文切換，隻多了幾個循環疊代。沒有争用的 cas 要比沒有争用的鎖便宜得多（這句話肯定是真的，因為沒有争用的鎖涉及 cas 加上額外的處理），而争用的 cas 比争用的鎖擷取涉及更短的延遲。
目前為止的示例（計數器和堆棧）都是非常簡單的非阻塞算法，一旦掌握了在循環中使用 cas，就可以容易地模仿它們。對于更複雜的資料結構，非阻塞算法要比這些簡單示例複雜得多，因為修改連結清單、樹或哈希表可能涉及對多個指針的更新。cas 支援對單一指針的原子性條件更新，但是不支援兩個以上的指針。是以，要建構一個非阻塞的連結清單、樹或哈希表，需要找到一種方式，可以用 cas 更新多個指針，同時不會讓資料結構處于不一緻的狀态。
在連結清單的尾部插入元素，通常涉及對兩個指針的更新：“尾” 指針總是指向清單中的最後一個元素，“下一個” 指針從過去的最後一個元素指向新插入的元素。因為需要更新兩個指針，是以需要兩個 cas。在獨立的 cas 中更新兩個指針帶來了兩個需要考慮的潛在問題：如果第一個 cas 成功，而第二個 cas 失敗，會發生什麼？如果其他線程在第一個和第二個 cas 之間企圖通路連結清單，會發生什麼？
對于非複雜資料結構，建構非阻塞算法的 “技巧” 是確定資料結構總處于一緻的狀态（甚至包括線上程開始修改資料結構和它完成修改之間），還要確定其他線程不僅能夠判斷出第一個線程已經完成了更新還是處在更新的中途，還能夠判斷出如果第一個線程走向 awol，完成更新還需要什麼操作。如果線程發現了處在更新中途的資料結構，它就可以 “幫助” 正在執行更新的線程完成更新，然後再進行自己的操作。當第一個線程回來試圖完成自己的更新時，會發現不再需要了，傳回即可，因為 cas 會檢測到幫助線程的幹預（在這種情況下，是建設性的幹預）。
這種 “幫助鄰居” 的要求，對于讓資料結構免受單個線程失敗的影響，是必需的。如果線程發現資料結構正處在被其他線程更新的中途，然後就等候其他線程完成更新，那麼如果其他線程在操作中途失敗，這個線程就可能永遠等候下去。即使不出現故障，這種方式也會提供糟糕的性能，因為新到達的線程必須放棄處理器，導緻上下文切換，或者等到自己的時間片過期（而這更糟）。
清單 4 的 <code>linkedqueue</code> 顯示了
michael-scott 非阻塞隊列算法的插入操作，它是由 <code>concurrentlinkedqueue</code> 實作的：
像許多隊列算法一樣，空隊列隻包含一個假節點。頭指針總是指向假節點；尾指針總指向最後一個節點或倒數第二個節點。圖 1 示範了正常情況下有兩個元素的隊列：
cas 進行的：從隊列目前的最後節點（c）連結到新節點，并把尾指針移動到新的最後一個節點（d）。如果第一步失敗，那麼隊列的狀态不變，插入線程會繼續重試，直到成功。一旦操作成功，插入被當成生效，其他線程就可以看到修改。還需要把尾指針移動到新節點的位置上，但是這項工作可以看成是 “清理工作”，因為任何處在這種情況下的線程都可以判斷出是否需要這種清理，也知道如何進行清理。
null，就可以判斷出隊列的狀态，這是讓線程可以幫助其他線程 “完成” 操作的關鍵。
第一個 cas（c）可能因為兩個線程競争通路隊列目前的最後一個元素而失敗；在這種情況下，沒有發生修改，失去 cas 的線程會重新裝入尾指針并再次嘗試。如果第二個 cas（d）失敗，插入線程不需要重試 —— 因為其他線程已經在步驟（b）中替它完成了這個操作！
如果深入 jvm 和作業系統，會發現非阻塞算法無處不在。垃圾收集器使用非阻塞算法加快并發和平行的垃圾搜集；排程器使用非阻塞算法有效地排程線程和程序，實作内在鎖。在 mustang（java 6.0）中，基于鎖的 <code>synchronousqueue</code> 算法被新的非阻塞版本代替。很少有開發人員會直接使用 <code>synchronousqueue</code>，但是通過 <code>executors.newcachedthreadpool()</code> 工廠建構的線程池用它作為工作隊列。比較緩存線程池性能的對比測試顯示，新的非阻塞同步隊列實作提供了幾乎是目前實作
3 倍的速度。在 mustang 的後續版本（代碼名稱為 dolphin）中，已經規劃了進一步的改進。
非阻塞算法要比基于鎖的算法複雜得多。開發非阻塞算法是相當專業的訓練，而且要證明算法的正确也極為困難。但是在 java 版本之間并發性能上的衆多改進來自對非阻塞算法的采用，而且随着并發性能變得越來越重要，可以預見在 java 平台的未來發行版中，會使用更多的非阻塞算法。
goetz，2004 年 11 月）：描述了 java 5.0 中加入的原子變量類，以及比較-交換操作。