【進階之路】並發編程（三）-非阻塞同步機制
導言
這一篇的內容主要來自於《java並發編程實戰》，有一說一，看這種寫的很專業的書不是很輕鬆，也沒辦法直接提高多少開發的能力，但是卻能更加夯實基礎，就像玩war3，熟練的基本功並不能讓你快速地與對方拉開差距，但是卻能再每一次團戰中積累優勢。
近年來，並發編程的領域更多的偏向於使用非阻塞算法，這種算法底層用原子機器指令（如比較交換CAS之類的）來替代鎖用以確保數據在並發訪問中的一致性。這樣的非阻塞算法廣泛的用於在操作系統和JVM中實現線程/程序調用機制、垃圾回收算法等。
java5.0後，使用原子變量類(例如AtomicInteger和AtomicReference)來構建高效的非阻塞算法。
與基本類型的包裝類相比原子變量類是可修改的，在原子變量類中沒有重新定義hashCode或equals方法,每個實例都是不同的，不宜用做基於散列的容器中的鍵值。
原子變量類比鎖的粒度更細量級更輕，將發生競爭的範圍縮小到單個變量上。
從《並發編程實戰》這本書出發，對給予的用例進行測試，能夠得出的結論：原子變量因其使用CAS的方法，在性能上有很大優勢。
- 1、在沒有競爭的情況下，原子變量的性能更高。
- 2、在中低程度的競爭下，原子變量基於CAS的操作，性能會遠超過鎖。
- 3 在高強度的競爭下,鎖能夠更好地幫助我們避免競爭（類似於，交通略擁堵時，環島疏通效果好，但是當交通十分擁堵時，信號燈能夠實現更高的吞吐量）。
之前的文章已經講過了volatitle變量、CAS算法、AtomicInteger線程安全的原子變量等，沒有看過或者已經忘記的的同學可以點擊下方的藍色鏈接去看看（複習一下）。
非阻塞算法
如果一個線程的失敗或者掛起不會導致其他線程的失敗或掛起，這種算法就叫做非阻塞算法。
1、非阻塞棧
在並發訪問的環境下,push和pop方法通過CAS算法可以保證棧的原子性和可見性,從而安全高效的更新非阻塞棧。
//根據《並發編程實戰》的代碼進行分析
public class CocurrentStack<E> {
/**
* AtomicReference和AtomicInteger非常類似，不同之處就在於AtomicInteger是對整數的封裝，
* 而AtomicReference則對應普通的對象引用。也就是它可以保證你在修改對象引用時的線程安全性
*/
AtomicReference<Node<E>> top = new AtomicReference<Node<E>>();
/*
* 這裡定義了一個棧（其實是列表，但是我們提供的功能僅僅能作為棧），
* 當有新值加入,會把舊值掛在新值的next方法上,,可以通過遞歸next拿到所有Node
* */
public void push(E item) {
Node<E> newHead = new Node<E>(item);
Node<E> oldHead;
do {
oldHead = top.get();
newHead.next = oldHead;
//這邊用了CAS算法進行判斷，這也是非阻塞算的和核心之一
} while (!top.compareAndSet(oldHead, newHead));
}
/**
* 實現出棧功能，同時出棧也實現了CAS的功能
*/
public E pop() {
Node<E> oldHead;
Node<E> newHead;
do {
oldHead = top.get();
if(oldHead == null) {
return null;
}
newHead = oldHead.next;
} while (!top.compareAndSet(oldHead, newHead));
return oldHead.item;
}
private static class Node<E> {
public final E item;
public Node<E> next;
private Node(E item) {
this.item = item;
}
}
}
根據代碼我們可以看出它擁有非阻塞算法的特點：一個線程的失敗或者掛起不會導致其他線程的失敗或掛起。如果某項操作的完成具有不確定性，不成功則會重新執行。
這個非阻塞棧通過CAS來嘗試修改棧頂元素，該方法為原子操作，如果發現被其他線程干擾，CAS會更新失敗，這個時候意味着另一個線程已經修改了堆棧。這些操作都是原子化地進行的。同時，我們需要不斷的循環，以保證在線程衝突的時候能夠重試更新。
2、非阻塞鏈表
根據CAS算法的內容與對非阻塞棧的研究，我們知道要實現非阻塞算法的方法就是實現原子級的變量。
使用非阻塞算法實現一個鏈接隊列比棧更複雜，因為它需要支持首尾的快速訪問，需要維護兩個獨立的隊首指針和隊尾指針,初始時都指向隊列的末尾節點，在成功加入新元素時兩個指針都需要原子化的更新。
//依然是根據《並發編程實戰》的代碼進行分析
public class LinkedQueue <E> {
private static class Node <E> {
final E item;
//還是和之前的一樣，以保證你在修改對象引用時的線程安全性
final AtomicReference<Node<E>> next;
public Node(E item, Node<E> next) {
this.item = item;
this.next = new AtomicReference<Node<E>>(next);
}
}
//初始化節點
private final Node<E> dummy = new Node<E>(null, null);
//聲明AtomicReference類型的頭尾節點、一切都是為了安全
private final AtomicReference<Node<E>> head
= new AtomicReference<Node<E>>(dummy);
private final AtomicReference<Node<E>> tail
= new AtomicReference<Node<E>>(dummy);
/**
*非阻塞算法新增操作
*/
public boolean put(E item) {
//聲明一個新的節點
Node<E> newNode = new Node<E>(item, null);
while (true) {
Node<E> curTail = tail.get();
Node<E> tailNext = curTail.next.get();
//得到鏈表的尾部節點
if (curTail == tail.get()) {
// 如果尾部節點的後續節點不為空，則隊列處於不一致的狀態
if (tailNext != null) {
// 比較後將為尾部節點向後退進；
tail.compareAndSet(curTail, tailNext);
} else {
// 如果尾部節點的後續節點為空，則隊列處於一致的狀態，沒有其他隊列操作，嘗試更新
if (curTail.next.compareAndSet(null, newNode)) {
// 更新成功，將為尾部節點向後退進；
tail.compareAndSet(curTail, newNode);
return true;
}
}
}
}
}
}
通過代碼，我們能看出，隊列里的每一個節點都有一個空置節點。任何線程在執行插入操作的時候，都能夠通過tail.next操作檢查隊列的狀態。如果不為空的情況，則能判斷出有其他的線程已經插入了一個節點，但是還沒有將tail指向最新的節點，這時候代碼可以通過推進tail指針向前移動一個節點把狀態恢復為穩定（即尾結點的置空狀態）。同時，另一個已經執行一半的線程的尾結點恢復穩定後，也不會受到影響。
這種設計的好處在於，如果多個線程同時操作方法，不需要加鎖等待，每次插入之前鏈表自身會檢查tail.next是否為空來判定隊列是否需要保持穩定狀態,如果是,它首先會推進隊尾指針(可能多次),直到隊列處於穩定狀態(tail.next為空)。
我們從源碼中也能看到，非阻塞鏈表ConcurrentLinkedQueue的實現方式。
結語
非阻塞算法通過使用底層的並發原語,比如CAS算法,取代了鎖.原子變量類向用戶提供了這些低層級原語,也能夠當做”更佳的volatile變量”使用,同時提供了整數類和對象引用的原子化更新操作.
非阻塞算法在設計和實現中很困難,但是在典型條件下能夠提供更好的可伸縮性,並能更好地預防活躍度失敗。從JVM並發性能的提升很大程度上來源於非阻塞算法的使用,包括在JVM內部以及平台類庫。
有需要的同學可以加我的公眾號，以後的最新的文章第一時間都在裏面，也可以找我要思維導圖
