近年來，在并發算法領域的大多數研究都側重于非阻塞算法，這種算法用底層的原子機器指令來代替鎖來確保數據在并發訪問中的一致性，非阻塞算法被廣泛應用于OS和JVM中實現線程/進程調度機制和GC以及鎖，并發數據結構中。

與鎖的方案相比，非阻塞算法都要復雜的多，他們在可伸縮性和活躍性上（避免死鎖）都有巨大的優勢。

非阻塞算法，顧名思義，多個線程競爭相同的數據時不會發生阻塞，因此他能在粒度更細的層次上進行協調，而且極大的減少調度開銷。

15.1 鎖的劣勢

獨占，可見性是鎖要保證的。

許多JVM都對非競爭的鎖獲取和釋放做了很多優化，性能很不錯了。但是如果一些線程被掛起然后稍后恢復運行，當線程恢復后還得等待其他線程執行完他們的時間片，才能被調度，所以掛起和恢復線程存在很大的開銷，其實很多鎖的力度很小的，很簡單，如果鎖上存在著激烈的競爭，那么多調度開銷/工作開銷比值就會非常高。

與鎖相比volatile是一種更輕量的同步機制，因為使用volatile不會發生上下文切換或者線程調度操作，但是volatile的指明問題就是雖然保證了可見性，但是原子性無法保證，比如i++的字節碼就是N行。

鎖的其他缺點還包括，如果一個線程正在等待鎖，它不能做任何事情，如果一個線程在持有鎖的情況下唄延遲執行了，例如發生了缺頁錯誤，調度延遲，那么就沒法執行。如果被阻塞的線程優先級較高，那么就會出現priority invesion的問題，被永久的阻塞下去。

15.2 硬件對并發的支持

獨占鎖是悲觀所，對于細粒度的操作，更高效的應用是樂觀鎖，這種方法需要借助沖突監測機制來判斷更新過程中是否存在來自其他線程的干擾，如果存在則失敗重試。

幾乎所有的現代CPU都有某種形式的原子讀-改-寫指令，例如compare-and-swap等，JVM就是使用這些指令來實現無鎖并發。

15.2.1 比較并交換

CAS（Compare and set）樂觀的技術。Java實現的一個compare and set如下，這是一個模擬底層的示例：

@ThreadSafe public class SimulatedCAS {@GuardedBy("this") private int value;public synchronized int get() {return value;}public synchronized int compareAndSwap(int expectedValue,int newValue) {int oldValue = value;if (oldValue == expectedValue)value = newValue;return oldValue;}public synchronized boolean compareAndSet(int expectedValue,int newValue) {return (expectedValue== compareAndSwap(expectedValue, newValue));} }

15.2.2 非阻塞的計數器

public class CasCounter {private SimulatedCAS value;public int getValue() {return value.get();}public int increment() {int v;do {v = value.get();} while (v != value.compareAndSwap(v, v + 1));return v + 1;} }

Java中使用AtomicInteger。

首先在競爭激烈一般時候，CAS性能遠超過第三章基于鎖的計數器。看起來他的指令更多，但是無需上下文切換和線程掛起，JVM內部的代碼路徑實際很長，所以反而好些。但是激烈程度比較高的時候，它的開銷還是比較大，但是你會發生這種激烈程度非常高的情況只是理論，實際生產環境很難遇到。況且JIT很聰明，這種操作往往能非常大的優化。

為了確保正常更新，可能得將CAS操作放到for循環里，從語法結構上來看，使用CAS比使用鎖更加復雜，得考慮失敗的情況（鎖會掛起線程，直到恢復）；但是基于CAS的原子操作，在性能上基本超過了基于鎖的計數器，即使只有很小的競爭或者不存在競爭！

在輕度到中度的爭用情況下，非阻塞算法的性能會超越阻塞算法，因為 CAS 的多數時間都在第一次嘗試時就成功，而發生爭用時的開銷也不涉及線程掛起和上下文切換，只多了幾個循環迭代。沒有爭用的 CAS 要比沒有爭用的鎖便宜得多（這句話肯定是真的，因為沒有爭用的鎖涉及 CAS 加上額外的處理，加鎖至少需要一個CAS，在有競爭的情況下，需要操作隊列，線程掛起，上下文切換），而爭用的 CAS 比爭用的鎖獲取涉及更短的延遲。

CAS的缺點是它使用調用者來處理競爭問題，通過重試、回退、放棄，而鎖能自動處理競爭問題，例如阻塞。

原子變量可以看做更好的volatile類型變量。

AtomicInteger在JDK8里面做了改動。

public final int getAndIncrement() {return unsafe.getAndAddInt(this, valueOffset, 1); }

JDK7里面的實現如下：

public final int getAndAdd(int delta) {for(;;) {intcurrent= get();intnext=current+delta;if(compareAndSet(current,next))returncurrent;}}

Unsafe是經過特殊處理的，不能理解成常規的java代碼，區別在于：

• 1.8在調用getAndAddInt的時候，如果系統底層支持fetch-and-add，那么它執行的就是native方法，使用的是fetch-and-add；

• 如果不支持，就按照上面的所看到的getAndAddInt方法體那樣，以java代碼的方式去執行，使用的是compare-and-swap；

這也正好跟openjdk8中Unsafe::getAndAddInt上方的注釋相吻合：

// The following contain CAS-based Java implementations used on // platforms not supporting native instructions

15.3 原子變量類

J.U.C的AtomicXXX

例如一個AtomictReference的使用如下：

public class CasNumberRange {@Immutableprivate static class IntPair {// INVARIANT: lower <= upperfinal int lower;final int upper;public IntPair(int lower, int upper) {this.lower = lower;this.upper = upper;}}private final AtomicReference<IntPair> values =new AtomicReference<IntPair>(new IntPair(0, 0));public int getLower() {return values.get().lower;}public int getUpper() {return values.get().upper;}public void setLower(int i) {while (true) {IntPair oldv = values.get();if (i > oldv.upper)throw new IllegalArgumentException("Can't set lower to " + i + " > upper");IntPair newv = new IntPair(i, oldv.upper);if (values.compareAndSet(oldv, newv))return;}}public void setUpper(int i) {while (true) {IntPair oldv = values.get();if (i < oldv.lower)throw new IllegalArgumentException("Can't set upper to " + i + " < lower");IntPair newv = new IntPair(oldv.lower, i);if (values.compareAndSet(oldv, newv))return;}} }

15.3.2 性能比較：鎖與原子變量

略

15.4 非阻塞算法

Lock-free算法，可以實現棧、隊列、優先隊列或者散列表。

15.4 非阻塞的棧

Trebier算法，1986年提出的。

public class ConcurrentStack <E> {AtomicReference<Node<E>> top = new AtomicReference<Node<E>>();public void push(E item) {Node<E> newHead = new Node<E>(item);Node<E> oldHead;do {oldHead = top.get();newHead.next = oldHead;} while (!top.compareAndSet(oldHead, newHead));}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;public Node(E item) {this.item = item;}} }

15.4.2 非阻塞的鏈表

有點復雜哦，實際J.U.C的ConcurrentLinkedQueue也是參考了這個由Michael and Scott，1996年實現的算法。

public class LinkedQueue <E> {private static class Node <E> {final E item;final AtomicReference<LinkedQueue.Node<E>> next;public Node(E item, LinkedQueue.Node<E> next) {this.item = item;this.next = new AtomicReference<LinkedQueue.Node<E>>(next);}}private final LinkedQueue.Node<E> dummy = new LinkedQueue.Node<E>(null, null);private final AtomicReference<LinkedQueue.Node<E>> head= new AtomicReference<LinkedQueue.Node<E>>(dummy);private final AtomicReference<LinkedQueue.Node<E>> tail= new AtomicReference<LinkedQueue.Node<E>>(dummy);public boolean put(E item) {LinkedQueue.Node<E> newNode = new LinkedQueue.Node<E>(item, null);while (true) {LinkedQueue.Node<E> curTail = tail.get();LinkedQueue.Node<E> tailNext = curTail.next.get();if (curTail == tail.get()) {if (tailNext != null) {// Queue in intermediate state, advance tailtail.compareAndSet(curTail, tailNext);} else {// In quiescent state, try inserting new nodeif (curTail.next.compareAndSet(null, newNode)) {// Insertion succeeded, try advancing tailtail.compareAndSet(curTail, newNode);return true;}}}}} }

15.4.3 原子域更新

AtomicReferenceFieldUpdater,一個基于反射的工具類，它能對指定類的指定的volatile引用字段進行原子更新。(注意這個字段不能是private的)

通過調用AtomicReferenceFieldUpdater的靜態方法newUpdater就能創建它的實例，該方法要接收三個參數：

• 包含該字段的對象的類
• 將被更新的對象的類
• 將被更新的字段的名稱

AtomicReferenceFieldUpdater updater=AtomicReferenceFieldUpdater.newUpdater(Dog.class,String.class,"name"); Dog dog1=new Dog(); updater.compareAndSet(dog1,dog1.name,"test") ; System.out.println(dog1.name); class Dog { volatile String name="dog1"; }

15.4.4 ABA問題

AtomicStampedReference //TODO

總結

以上是生活随笔為你收集整理的Java并发编程实战系列15之原子遍历与非阻塞同步机制(Atomic Variables and Non-blocking Synchronization)...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。