摘要：并發(fā)包將這種無鎖方案封裝提煉之后，實現(xiàn)了一系列的原子類。無鎖方案相對互斥鎖方案，最大的好處就是性能。作為一條指令，指令本身是能夠保證原子性的。

前面我們多次提到一個累加器的例子，示例代碼如下。在這個例子中，add10K() 這個方法不是線程安全的，問題就出在變量 count 的可見性和 count+=1 的原子性上。可見性問題可以用 volatile 來解決，而原子性問題我們前面一直都是采用的互斥鎖方案。

public class Test {
  long count = 0;
  void add10K() {
    int idx = 0;
    while(idx++ < 10000) {
      count += 1;
    }
  }
}

其實對于簡單的原子性問題，還有一種無鎖方案。Java SDK 并發(fā)包將這種無鎖方案封裝提煉之后，實現(xiàn)了一系列的原子類。

在下面的代碼中，我們將原來的 long 型變量 count 替換為了原子類 AtomicLong，原來的count +=1 替換成了 count.getAndIncrement()，僅需要這兩處簡單的改動就能使 add10K() 方法變成線程安全的，原子類的使用還是挺簡單的。

public class Test {
  AtomicLong count = 
    new AtomicLong(0);
  void add10K() {
    int idx = 0;
    while(idx++ < 10000) {
      count.getAndIncrement();
    }
  }
}

無鎖方案相對互斥鎖方案，最大的好處就是性能?；コ怄i方案為了保證互斥性，需要執(zhí)行加鎖、解鎖操作，而加鎖、解鎖操作本身就消耗性能；同時拿不到鎖的線程還會進入阻塞狀態(tài)，進而觸發(fā)線程切換，線程切換對性能的消耗也很大。 相比之下，無鎖方案則完全沒有加鎖、解鎖的性能消耗，同時還能保證互斥性，既解決了問題，又沒有帶來新的問題，可謂絕佳方案。那它是如何做到的呢？

其實原子類性能高的秘密很簡單，硬件支持而已。CPU 為了解決并發(fā)問題，提供了 CAS 指令（CAS，全稱是 Compare And Swap，即“比較并交換”）。CAS 指令包含 3 個參數(shù)：共享變量的內(nèi)存地址 A、用于比較的值 B 和共享變量的新值 C；并且只有當內(nèi)存中地址 A 處的值等于 B 時，才能將內(nèi)存中地址 A 處的值更新為新值 C。作為一條 CPU 指令，CAS 指令本身是能夠保證原子性的。

你可以通過下面 CAS 指令的模擬代碼來理解 CAS 的工作原理。在下面的模擬程序中有兩個參數(shù)，一個是期望值 expect，另一個是需要寫入的新值 newValue， 只有當目前 count 的值和期望值 expect 相等時，才會將 count 更新為 newValue

class SimulatedCAS{
  int count；
  synchronized int cas(
    int expect, int newValue){
    // 讀目前 count 的值
    int curValue = count;
    // 比較目前 count 值是否 == 期望值
    if(curValue == expect){
      // 如果是，則更新 count 的值
      count = newValue;
    }
    // 返回寫入前的值
    return curValue;
  }
}

count += 1的一個核心問題是：基于內(nèi)存中 count 的當前值 A 計算出來的 count+=1 為 A+1，在將 A+1 寫入內(nèi)存的時候，很可能此時內(nèi)存中 count 已經(jīng)被其他線程更新過了，這樣就會導致錯誤地覆蓋其他線程寫入的值。

使用 CAS 來解決并發(fā)問題，一般都會伴隨著自旋，而所謂自旋，其實就是循環(huán)嘗試。例如，實現(xiàn)一個線程安全的count += 1操作，CAS+ 自旋的實現(xiàn)方案如下所示，首先計算 newValue = count+1，如果 cas(count,newValue) 返回的值不等于 count，則意味著線程在執(zhí)行完代碼①處之后，執(zhí)行代碼②處之前，count 的值被其他線程更新過。那此時該怎么處理呢？可以采用自旋方案，就像下面代碼中展示的，可以重新讀 count 最新的值來計算 newValue 并嘗試再次更新，直到成功。

class SimulatedCAS{
  volatile int count;
  // 實現(xiàn) count+=1
  addOne(){
    do {
      newValue = count+1; //①
    }while(count !=
      cas(count,newValue) //②
  }
  // 模擬實現(xiàn) CAS，僅用來幫助理解
  synchronized int cas(
    int expect, int newValue){
    // 讀目前 count 的值
    int curValue = count;
    // 比較目前 count 值是否 == 期望值
    if(curValue == expect){
      // 如果是，則更新 count 的值
      count= newValue;
    }
    // 返回寫入前的值
    return curValue;
  }
}

通過上面的示例代碼，想必你已經(jīng)發(fā)現(xiàn)了，CAS 這種無鎖方案，完全沒有加鎖、解鎖操作，即便兩個線程完全同時執(zhí)行 addOne() 方法，也不會有線程被阻塞，所以相對于互斥鎖方案來說，性能好了很多。

但是在 CAS 方案中，有一個問題可能會常被你忽略，那就是ABA問題。

前面我們提到“如果 cas(count,newValue) 返回的值不等于count，意味著線程在執(zhí)行完代碼①處之后，執(zhí)行代碼②處之前，count 的值被其他線程更新過。那如果 cas(count,newValue) 返回的值等于count，是否就能夠認為 count 的值沒有被其他線程更新過呢？

顯然不是的，假設 count 原本是 A，線程 T1 在執(zhí)行完代碼①處之后，執(zhí)行代碼②處之前，有可能 count 被線程 T2 更新成了 B，之后又被 T3 更新回了 A，這樣線程 T1 雖然看到的一直是 A，但是其實已經(jīng)被其他線程更新過了，這就是 ABA 問題。

可能大多數(shù)情況下我們并不關心 ABA 問題，例如數(shù)值的原子遞增，但也不能所有情況下都不關心，例如原子化的更新對象很可能就需要關心 ABA 問題，因為兩個 A 雖然相等，但是第二個 A 的屬性可能已經(jīng)發(fā)生變化了。所以在使用 CAS 方案的時候，一定要先 check 一下。

在本文開始部分，我們使用原子類 AtomicLong 的 getAndIncrement() 方法替代了count+1

1，從而實現(xiàn)了線程安全。原子類 AtomicLong 的 getAndIncrement() 方法內(nèi)部就是基于 CAS 實現(xiàn)的，下面我們來看看 Java 是如何使用 CAS 來實現(xiàn)原子化的

在 Java 1.8 版本中，getAndIncrement() 方法會轉調(diào) unsafe.getAndAddLong() 方法。這里 this 和 valueOffset 兩個參數(shù)可以唯一確定共享變量的內(nèi)存地址。

final long getAndIncrement() {
  return unsafe.getAndAddLong(
    this, valueOffset, 1L);
}

unsafe.getAndAddLong() 方法的源碼如下，該方法首先會在內(nèi)存中讀取共享變量的值，之后循環(huán)調(diào)用 compareAndSwapLong() 方法來嘗試設置共享變量的值，直到成功為止。compareAndSwapLong() 是一個 native 方法，只有當內(nèi)存中共享變量的值等于 expected 時，才會將共享變量的值更新為 x，并且返回 true；否則返回 fasle。compareAndSwapLong 的語義和 CAS 指令的語義的差別僅僅是返回值不同而已。

public final long getAndAddLong(
  Object o, long offset, long delta){
  long v;
  do {
    // 讀取內(nèi)存中的值
    v = getLongVolatile(o, offset);
  } while (!compareAndSwapLong(
      o, offset, v, v + delta));
  return v;
}
// 原子性地將變量更新為 x
// 條件是內(nèi)存中的值等于 expected
// 更新成功則返回 true
native boolean compareAndSwapLong(
  Object o, long offset, 
  long expected,
  long x);

另外，需要你注意的是，getAndAddLong() 方法的實現(xiàn)，基本上就是 CAS 使用的經(jīng)典范例。所以請你再次體會下面這段抽象后的代碼片段，它在很多無鎖程序中經(jīng)常出現(xiàn)。Java 提供的原子類里面 CAS 一般被實現(xiàn)為 compareAndSet()，compareAndSet() 的語義和 CAS 指令的語義的差別僅僅是返回值不同而已，compareAndSet() 里面如果更新成功，則會返回 true，否則返回 false。

do {
  // 獲取當前值
  oldV = xxxx；
  // 根據(jù)當前值計算新值
  newV = ...oldV...
}while(!compareAndSet(oldV,newV);

Java SDK 并發(fā)包里提供的原子類內(nèi)容很豐富，我們可以將它們分為五個類別：

原子化的基本數(shù)據(jù)類型

原子化的對象引用類型

原子化數(shù)組

原子化對象屬性更新器

原子化的累加器

。這五個類別提供的方法基本上是相似的，并且每個類別都有若干原子類，你可以通過下面的原子類組成概覽圖來獲得一個全局的印象。下面我們詳細解讀這五個類別。

相關實現(xiàn)有 AtomicBoolean、AtomicInteger 和 AtomicLong，提供的方法主要有以下這些，詳情你可以參考 SDK 的源代碼，都很簡單，這里就不詳細介紹了。

getAndIncrement() // 原子化 i++
getAndDecrement() // 原子化的 i--
incrementAndGet() // 原子化的 ++i
decrementAndGet() // 原子化的 --i
// 當前值 +=delta，返回 += 前的值
getAndAdd(delta) 
// 當前值 +=delta，返回 += 后的值
addAndGet(delta)
//CAS 操作，返回是否成功
compareAndSet(expect, update)
// 以下四個方法
// 新值可以通過傳入 func 函數(shù)來計算
getAndUpdate(func)
updateAndGet(func)
getAndAccumulate(x,func)
accumulateAndGet(x,func)

相關實現(xiàn)有 AtomicReference、AtomicStampedReference 和 AtomicMarkableReference，利用它們可以實現(xiàn)對象引用的原子化更新。AtomicReference 提供的方法和原子化的基本數(shù)據(jù)類型差不多，這里不再贅述。不過需要注意的是，對象引用的更新需要重點關注 ABA 問題，AtomicStampedReference 和 AtomicMarkableReference 這兩個原子類可以解決 ABA 問題。

解決 ABA 問題的思路其實很簡單，增加一個版本號維度就可以了。每次執(zhí)行 CAS 操作，附加再更新一個版本號，只要保證版本號是遞增的，那么即便 A 變成 B 之后再變回 A，版本號也不會變回來（版本號遞增的）。AtomicStampedReference 實現(xiàn)的 CAS 方法就增加了版本號參數(shù)，方法簽名如下：

boolean compareAndSet(
  V expectedReference,
  V newReference,
  int expectedStamp,
  int newStamp) 

AtomicMarkableReference 的實現(xiàn)機制則更簡單，將版本號簡化成了一個 Boolean 值，方法簽名如下：

boolean compareAndSet(
  V expectedReference,
  V newReference,
  boolean expectedMark,
  boolean newMark)

相關實現(xiàn)有 AtomicIntegerArray、AtomicLongArray 和 AtomicReferenceArray，利用這些原子類，我們可以原子化地更新數(shù)組里面的每一個元素。這些類提供的方法和原子化的基本數(shù)據(jù)類型的區(qū)別僅僅是：每個方法多了一個數(shù)組的索引參數(shù)，所以這里也不再贅述了。

相關實現(xiàn)有 AtomicIntegerFieldUpdater、AtomicLongFieldUpdater 和 AtomicReferenceFieldUpdater，利用它們可以原子化地更新對象的屬性，這三個方法都是利用反射機制實現(xiàn)的，創(chuàng)建更新器的方法如下：

public static 
AtomicXXXFieldUpdater 
newUpdater(Class tclass, 
  String fieldName)

boolean compareAndSet(
  T obj, 
  int expect, 
  int update)