背景

近年來，在并發(fā)算法領域的大多數研究都側重于非阻塞算法，這種算法用底層的原子機器指令（例如比較并發(fā)交換指令）代替鎖來確保數據在并發(fā)訪問中的一致性。非阻塞算法被廣泛的用于在操作系統(tǒng)和JVM中實現線程/進程調度機制、垃圾回收機制以及鎖和其他并發(fā)數據結構。

與基于鎖的方案相比，非阻塞算法在設計和實現上都要復雜的多，但他們在可伸縮性和活躍性上卻擁有巨大的優(yōu)勢，由于非阻塞算法可以使多個線程在競爭相同數據時不會發(fā)生阻塞，因此它能在粒度更細的層次上面進行協調，并且極大的減少調度開銷。鎖雖然Java語言鎖定語法比較簡潔，但JVM操作和管理鎖時，需要完成的工作缺并不簡單，在實現鎖定時需要遍歷JVM中一條復雜的代碼路徑，并可能導致操作系統(tǒng)級的鎖定、線程掛起以及上下文切換等操作。

非阻塞算法

在基于鎖的算法中可能會發(fā)生各種活躍性故障，如果線程在持有鎖時由于阻塞I/O，內存頁缺失或其他延遲執(zhí)行，那么很可能所有線程都不能繼續(xù)執(zhí)行下去。如果在某種算法中，一個線程的失敗或掛起不會導致其他線程也失敗或掛起，那么這種算法就稱為非阻塞算法。如果在算法的每個步驟中都存在某個線程能夠執(zhí)行下去，那么這種算法也被稱為無鎖算法。如果在算法中僅將CAS用于協調線程之間的操作，并且能夠正確的實現，那么他既是一種無阻塞算法，又是一種無鎖算法。

Java對非阻塞算法的支持：從Java5.0開始，底層可以使用原子變量類（例如AtomicInteger和AtoMicReference）來構建高效的非阻塞算法，底層實現采用的是一個比較并交換指令（CAS）。

比較并交換（CAS）

CAS包括了三個操作數，需要讀寫的內存位置V，進行比較的值A和擬寫入的新值B。當且僅當V的值等于A時，CAS才會通過原子方式用新值B來更新A的值，否則不會執(zhí)行任何操作。無論V的值是否等于A，都將返回V原有的值。CAS的含義是：我認為V的值應該是A，如果是那么將V的值更新為B，否則不修改并告訴V的值實際為多少。

原子變量類

原子變量（對應內存模型中的原子性）比鎖的粒度更細。量級更輕，并且對于在多處理器系統(tǒng)上實現高性能的并發(fā)代碼來說是非常關鍵的。原子變量將發(fā)生競爭的范圍縮小到單個變量上面，這是你獲得的粒度最細的情況。更新原子變量的快速（非競爭）路徑不會被獲得鎖的快速路徑慢，并且通常會更快，而它的慢速路徑肯定比鎖的慢速路徑塊，因為他不需要掛起或者重新調度線程。在使用基于原子變量而非鎖的算法中，線程在執(zhí)行時更不易出現延遲，并且如果遇到競爭，也更容易恢復過來。

Java中的13個原子操作類

Java從JDK1.5開始提供了java.util.concurrent.atomic包（以下簡稱Atomic包），這個包中的原子操作類提供了一種用法簡單、性能高效、線程安全地更新一個變量的方式。因為變量的類型有很多種，所以在Atomic包里一共提供了13個類，屬于4種類型的原子更新方式，分別是原子更新基本類型、原子更新數組、原子更新引用和原子更新屬性（字段）。Atomic包里的類基本都是使用Unsafe實現的包裝類。

• 原子更新基本類型類
  

使用原子的方式更新基本類型，Atomic包提供了以下3個類。

1.AtomicBoolean：原子更新布爾類型。
2.AtomicInteger：原子更新整型。
3.AtomicLong：原子更新長整型。

• 原子更新數組
  

通過原子的方式更新數組里的某個元素，Atomic包提供了以下4個類。

1.AtomicIntegerArray：原子更新整型數組里的元素。
2.AtomicLongArray：原子更新長整型數組里的元素。
3.AtomicReferenceArray：原子更新引用類型數組里的元素。

• 原子更新引用類型
  

原子更新基本類型的AtomicInteger，只能更新一個變量，如果要原子更新多個變量，就需要使用這個原子更新引用類型提供的類。Atomic包提供了以下3個類。

1.AtomicReference：原子更新引用類型。
2.AtomicReferenceFieldUpdater：原子更新引用類型里的字段。
3.AtomicMarkableReference：原子更新帶有標記位的引用類型。可以原子更新一個布爾類型的標記位和引用類型。構造方法是AtomicMarkableReference（V initialRef，booleaninitialMark）。

• 原子更新字段類
  

如果需原子地更新某個類里的某個字段時，就需要使用原子更新字段類，Atomic包提供了以下3個類進行原子字段更新。

1.AtomicIntegerFieldUpdater：原子更新整型的字段的更新器。
2.AtomicLongFieldUpdater：原子更新長整型字段的更新器。
3.AtomicStampedReference：原子更新帶有版本號的引用類型。該類將整數值與引用關聯起來，可用于原子的更新數據和數據的版本號，可以解決使用CAS進行原子更新時可能出現的
4.ABA問題。

AtomicLong源碼分析

上面的4種原子類型都是基于CAS實現，低層借助于unsafe實現原子操作。接下來結合源碼，看一下比較有代表性的AtomicLong源碼

初始化

//保存AtomicLong的實際值，用volatile 修飾保證可見性
private volatile long value;
 
// 獲取value的內存地址的邏輯操作
  static {
    try {
      valueOffset = unsafe.objectFieldOffset
        (AtomicLong.class.getDeclaredField("value"));
    } catch (Exception ex) { throw new Error(ex); }
  }
 
 
//根據傳入的參數初始化實際值，默認值為0
public AtomicLong(long initialValue) {
    value = initialValue;
  }

接下來我們主要看一下幾個更新方法

//以原子方式更新值為傳入的newValue，并返回更新之前的值
public final long getAndSet(long newValue) {
    return unsafe.getAndSetLong(this, valueOffset, newValue);
  }
 
 
//輸入期望值和更新值，如果輸入的值等于預期值，則以原子方式更新該值為輸入的值
public final boolean compareAndSet(long expect, long update) {
    return unsafe.compareAndSwapLong(this, valueOffset, expect, update);
  }
 
//返回當前值原子加1后的值
public final long getAndIncrement() {
    return unsafe.getAndAddLong(this, valueOffset, 1L);
  }
 
//返回當前值原子減1后的值
public final long getAndDecrement() {
    return unsafe.getAndAddLong(this, valueOffset, -1L);
  }
 
//返回當前值原子增加delta后的值
public final long getAndAdd(long delta) {
    return unsafe.getAndAddLong(this, valueOffset, delta);
  }

上面列出來主要用的一些方法，可以看出基本都是調用unsafe.getAndAddLong方法，接下來我們具體看下

public native long getLongVolatile(Object var1, long var2); 
 
 
public final native boolean compareAndSwapLong(Object var1, long var2, long var4, long var6);
 
/*
unsafe.getAndAddLong(this, valueOffset, 1L)
var1 當前值
var2 value值在AtomicLong對象中的內存偏移地址
*/
 
public final long getAndAddLong(Object var1, long var2, long var4) {
    long var6;
    do {
      //根據var1和var2得出當前變量的值，以便接下來執(zhí)行更新操作
      var6 = this.getLongVolatile(var1, var2);
 
      //如果當前值為var6，則將值加var4，這樣做是確保每次更新時，變量的值是沒有被其他線
//程修改過的值，如果被修改，則重新獲取最新值更新，直到更新成功
    } while(!this.compareAndSwapLong(var1, var2, var6, var6 + var4));
 
    return var6;
  }

從源碼可以看出，獲取當前值getLongVolatile方法，比較并交換compareAndSwapLong方法都是native方法。說明不是采用java實現原子操作的，具體各位同學可以繼續(xù)去查看底層源碼（應該是c++）實現，這里不在深入了（能力有限）。

比較并交換的缺陷

1、通過源碼可以看出，原子更新時，會先獲取當前值，確保當前值沒被修改過后在進行更新操作，這也意味著如果競爭十分激烈，CAS的效率是有可能比鎖更低的（一般在實際中不會出現這種情況），JDK后面推出了LongAdd，粒度更小，競爭也會被分散到更低，具體實現各位同學可以自行了解。

2、ABA是談到CAS不可避免的話題，比較并交換，會存在這樣一個場景，當變量為值A時，將值執(zhí)行更新。然而在實際中，有可能其他線程將值先改為B，然后又將值改回A，此時還是能夠成功執(zhí)行更新操作的（對于某些不在乎過程的沒啥影響，對于鏈表之類的就不滿足了）。解決方式是給變量打上版本號，如果版本號和值一致才執(zhí)行更新操作（可使用AtomicReference）。

總結

非阻塞算法通過底層的并發(fā)原語（例如比較交換而不是鎖）來維持線程的安全性。這些底層的原語通過原子變量類向外公開，這些類也用做一種“更好的volatile變量”，從而為整數和對象引用提供原子的更新操作。

參考書籍：

《JAVA并發(fā)編程實戰(zhàn)》

《JAVA并發(fā)編程的藝術》

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

最新評論