[[424670]]

前言

獨占鎖是一種悲觀鎖，synchronized就是一種獨占鎖，會導致其它所有需要鎖的線程掛起，等待持有鎖的線程釋放鎖;

而另一個更加有效的鎖就是樂觀鎖。所謂樂觀鎖就是，每次不加鎖而是假設沒有沖突而去完成某項操作，如果因為沖突失敗就重試，直到成功為止。樂觀鎖用到的機制就是CAS;

今天我們就來介紹下cas機制;

一、CAS介紹

1、什么是CAS

• CAS,compare and swap的縮寫，中文翻譯成比較并交換。CAS指令在Intel CPU上稱為CMPXCHG指令，它的作用是將指定內存地址的內容與所給的某個值相比，如果相等，則將其內容替換為指令中提供的新值，如果不相等，則更新失敗從內存領域來說這是樂觀鎖，因為它在對共享變量更新之前會先比較當前值是否與更新前的值一致，如果是，則更新，如果不是，則無限循環執行(稱為自旋)，直到當前值與更新前的值一致為止，才執行更新;
• CAS 操作包含三個操作數 —— 內存位置(V)、預期原值(A)和新值(B)。如果內存位置的值與預期原值相匹配，那么處理器會自動將該位置值更新為新值 。否則，處理器不做任何操作。無論哪種情況，它都會在 CAS 指令之前返回該 位置的值;
• 通常將 CAS 用于同步的方式是從地址 V 讀取值 A，執行多步計算來獲得新 值 B，然后使用 CAS 將 V 的值從 A 改為 B。如果 V 處的值尚未同時更改，則 CAS 操作成功;
• 類似于 CAS 的指令允許算法執行讀-修改-寫操作，而無需害怕其他線程同時 修改變量，因為如果其他線程修改變量，那么 CAS 會檢測它(并失敗)，算法 可以對該操作重新計算;

2、那些地方采用了 CAS 機制

• 在 java.util.concurrent.atomic 包下，一系列以 Atomic 開頭的包裝類。例如AtomicBoolean，AtomicInteger，AtomicLong 等，它們就是典型的利用 CAS 機制實現的原子操作類;
• Lock 系列類的底層實現以及 Java 1.6 在 synchronized 轉換為重量級鎖之前，也會采用到 CAS 機制;

3、synchronized 和 CAS 的區別

• synchronized 采用的是 CPU 悲觀鎖機制，即線程獲得的是獨占鎖。獨占鎖就意味著 其他線程只能依靠阻塞來等待線程釋放鎖。而在 CPU 轉換線程阻塞時會引起線程上下文切換，當有很多線程競爭鎖的時候，會引起 CPU 頻繁的上下文切換導致效率很低。盡管 Java1.6 為 synchronized 做了優化，增加了從偏向鎖到輕量級鎖再到重量級鎖的過度，但是在最終轉變為重量級鎖之后，性能仍然較低;
• Synchronized(未優化前)最主要的問題是：在存在線程競爭的情況下會出現線程阻塞和喚醒鎖帶來的性能問題，因為這是一種互斥同步(阻塞同步)。而CAS并不是武斷的間線程掛起，當CAS操作失敗后會進行一定的嘗試，而非進行耗時的掛起喚醒的操作，因此也叫做非阻塞同步。這是兩者主要的區別;
• 使用CAS時非阻塞同步，也就是說不會將線程掛起，會自旋(無非就是一個死循環)進行下一次嘗試，如果這里自旋時間過長對性能是很大的消耗。如果JVM能支持處理器提供的pause指令，那么在效率上會有一定的提升;
• CAS它當中使用了3個基本操作數：內存地址 V，舊的預期值 A，要修改的新值 B。采用的是一種樂觀鎖的機制，它不會阻塞任何線程，所以在效率上，它會比 synchronized 要高。所謂樂觀鎖就是：每次不加鎖而是假設沒有沖突而去完成某項操作，如果因為沖突失敗就重試，直到成功為止;

4、為什么需要CAS機制

我們經常使用volatile關鍵字修飾某一個變量，表明這個變量是全局共享的一個變量，同時具有了可見性和有序性。但是卻沒有原子性。比如說一個常見的操作a++。這個操作其實可以細分成三個步驟：

(1)從內存中讀取a

(2)對a進行加1操作

(3)將a的值重新寫入內存中

在單線程狀態下這個操作沒有一點問題，但是在多線程中就會出現各種各樣的問題了。因為可能一個線程對a進行了加1操作，還沒來得及寫入內存，其他的線程就讀取了舊值。造成了線程的不安全現象;

Volatile關鍵字可以保證線程間對于共享變量的可見性可有序性，可以防止CPU的指令重排序(DCL單例)，但是無法保證操作的原子性，所以jdk1.5之后引入CAS利用CPU原語保證線程操作的院子性;

CAS操作由處理器提供支持，是一種原語。原語是操作系統或計算機網絡用語范疇。是由若干條指令組成的，用于完成一定功能的一個過程，具有不可分割性，即原語的執行必須是連續的，在執行過程中不允許被中斷。如 Intel 處理器，比較并交換通過指令的 cmpxchg 系列實現;

二、cas底層實現

1、底層依靠Unsafe的CAS操作來保證原子性;

CAS的實現主要在JUC中的atomic包，我們以AtomicInteger類為例：

/** 
 * Atomically adds the given value to the current value. 
 * 
 * @param delta the value to add 
 * @return the previous value 
 */ 
public final int getAndAdd(int delta) { 
    return unsafe.getAndAddInt(this, valueOffset, delta); 
} 
public final int incrementAndGet() { 
    for (;;) { 
        int current = get(); 
        int next = current + 1; 
        if (compareAndSet(current, next)) 
            return next; 
    } 
} 
private volatile int value; 
public final int get() { 
    return value; 
} 

代碼是一個無限循環，也就是CAS的自旋。循環體當中做了三件事：

獲取當前值;

當前值+1，計算出目標值;

進行CAS操作，如果成功則跳出循環(當前值和目標值相等)，如果失敗則重復上述步驟;

2、Unsafe.class

public final int getAndAddInt(Object var1, long var2, int var4) { 
    int var5; 
    do { 
        var5 = this.getIntVolatile(var1, var2); 
    } while (!this.compareAndSwapInt(var1, var2, var5, var5 + var4));//native方法 
    return var5; 
}    
******** 
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);//底層c++實現 

public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);//底層c++實現

3、compareAndSwapInt為native方法，對應底層hotspot虛擬機unsage.cpp

UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x)) 
  UnsafeWrapper("Unsafe_CompareAndSwapInt"); 
  oop p = JNIHandles::resolve(obj); 
  jint* addr = (jint *) index_oop_from_field_offset_long(p, offset); 
  return (jint)(Atomic::cmpxchg(x, addr, e)) == e; 
UNSAFE_END 
*** 

這里可以看到最終使用了Atomic::cmpxchg來保證原子性，可繼續跟進代碼

4、Atomic::cmpxchg針對不同平臺有不同的實現方式

*** 
// Adding a lock prefix to an instruction on MP machine 
#define LOCK_IF_MP(mp) "cmp $0, " #mp "; je 1f; lock; 1: " 
*** 
inline jint     Atomic::cmpxchg    (jint     exchange_value, volatile jint*     dest, jint     compare_value) { 
  int mp = os::is_MP(); 
  __asm__ volatile (LOCK_IF_MP(%4) "cmpxchgl %1,(%3)" 
                    : "=a" (exchange_value) 
                    : "r" (exchange_value), "a" (compare_value), "r" (dest), "r" (mp) 
                    : "cc", "memory"); 
  return exchange_value; 
} 

最重要的指令為 LOCK_IF_MP ， MP是指多CPU(multi processors)，最終意義為多CPU的情況下需要lock，通過lock的方式來保證原子;

lock解釋：

• 確保后續指令執行的原子性;
• 在Pentium及之前的處理器中，帶有lock前綴的指令在執行期間會鎖住總線，使得其它處理器暫時無法通過總線訪問內存，很顯然，這個開銷很大。在新的處理器中，Intel使用緩存鎖定來保證指令執行的原子性，緩存鎖定將大大降低lock前綴指令的執行開銷;
• 禁止該指令與前面和后面的讀寫指令重排序;
• 把寫緩沖區的所有數據刷新到內存中;

總之：JAVA中我們使用到涉及到CAS操作的底層實現為對應平臺虛擬機中的c++代碼(lock指令)實現來保證原子性;

三、CAS 的缺點及解決方式

CAS雖然很高效的解決原子操作，但是CAS仍然存在三大問題。ABA問題，循環時間長開銷大和只能保證一個共享變量的原子操作;

1、ABA問題：因為CAS需要在操作值的時候檢查下值有沒有發生變化，如果沒有發生變化則更新，但是如果一個值原來是A，變成了B，又變成了A， 那么使用CAS進行檢查時會發現它的值沒有發生變化，但是實際上卻變化了;

ABA問題的解決思路就是使用版本號。在變量前面追加上版本號，每次變量更新的時候把版本號加一，那么A-B-A 就會變成1A-2B-3A;

從Java1.5開始JDK的atomic包里提供了一個類 AtomicStampedReference 來解決ABA問題。這個類的compareAndSet方法作用是首先檢查當前引用是否等于預期引用，并且當前標志是否等于預期標志，如果全部相等，則以原子方式將該引用和該標志的值設置為給定的更新值;

2、循環時間長開銷大：在并發量比較高的情況下，如果許多線程反復嘗試更新某一個變量，即自旋CAS如果長時間不成功，會給CPU帶來非常大的執行開銷;

如果JVM能支持處理器提供的pause指令，那么效率會有一定的提升。pause指令有兩個作用，第一它可以延遲流水線執行指令(de-pipeline),使CPU不會消耗過多的執行資源，延遲的時間取決于具體實現的版本，在一些處理器上延遲時間是零。第二它可以避免在退出循環的時候因內存順序沖突(memory order violation)而引起CPU流水線被清空(CPU pipeline flush)，從而提高CPU的執行效率;

代碼層面，破壞掉for死循環，當自旋超過一定時間或者一定次數時，return退出;

使用類似ConcurrentHashMap的方法。當多個線程競爭時，將粒度變小，將一個變量拆分為多個變量，達到多個線程訪問多個資源的效果，最后再調用sum把它合起來，能降低CPU消耗，但是治標不治本;

3、只能保證一個共享變量的原子操作：當對一個共享變量執行操作時，我們可以使用循環CAS的方式來保證原子操作，但是對多個共享變量操作時，循環CAS就無法保證操作的原子性;

這個時候就可以用鎖，或者有一個取巧的辦法，就是把多個共享變量合并成一個共享變量來操作。比如有兩個共享變量i=2,j=a，合并一下ij=2a，然后用CAS來操作ij;

從Java1.5開始JDK提供了AtomicReference類來保證引用對象之間的原子性，你可以把多個變量放在一個對象里來進行CAS操作;

四、CAS使用的時機

線程數較少、等待時間短可以采用自旋鎖進行CAS嘗試拿鎖，較于synchronized高效;

線程數較大、等待時間長，不建議使用自旋鎖，占用CPU較高;

總結

CAS可以保證多線程對數據寫操作時數據的一致性;

 

CAS的思想：三個參數，一個當前內存值V、舊的預期值A、即將更新的值B，當且僅當預期值A和內存值V相同時，將內存值修改為B并返回true，否則什么都不做，并返回false;