[[424670]]

前言

獨(dú)占鎖是一種悲觀鎖，synchronized就是一種獨(dú)占鎖，會(huì)導(dǎo)致其它所有需要鎖的線程掛起，等待持有鎖的線程釋放鎖;

而另一個(gè)更加有效的鎖就是樂(lè)觀鎖。所謂樂(lè)觀鎖就是，每次不加鎖而是假設(shè)沒(méi)有沖突而去完成某項(xiàng)操作，如果因?yàn)闆_突失敗就重試，直到成功為止。樂(lè)觀鎖用到的機(jī)制就是CAS;

今天我們就來(lái)介紹下cas機(jī)制;

一、CAS介紹

1、什么是CAS

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

2、那些地方采用了 CAS 機(jī)制

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

3、synchronized 和 CAS 的區(qū)別

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

4、為什么需要CAS機(jī)制

我們經(jīng)常使用volatile關(guān)鍵字修飾某一個(gè)變量，表明這個(gè)變量是全局共享的一個(gè)變量，同時(shí)具有了可見(jiàn)性和有序性。但是卻沒(méi)有原子性。比如說(shuō)一個(gè)常見(jiàn)的操作a++。這個(gè)操作其實(shí)可以細(xì)分成三個(gè)步驟：

(1)從內(nèi)存中讀取a

(2)對(duì)a進(jìn)行加1操作

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

在單線程狀態(tài)下這個(gè)操作沒(méi)有一點(diǎn)問(wèn)題，但是在多線程中就會(huì)出現(xiàn)各種各樣的問(wèn)題了。因?yàn)榭赡芤粋€(gè)線程對(duì)a進(jìn)行了加1操作，還沒(méi)來(lái)得及寫入內(nèi)存，其他的線程就讀取了舊值。造成了線程的不安全現(xiàn)象;

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

CAS操作由處理器提供支持，是一種原語(yǔ)。原語(yǔ)是操作系統(tǒng)或計(jì)算機(jī)網(wǎng)絡(luò)用語(yǔ)范疇。是由若干條指令組成的，用于完成一定功能的一個(gè)過(guò)程，具有不可分割性，即原語(yǔ)的執(zhí)行必須是連續(xù)的，在執(zhí)行過(guò)程中不允許被中斷。如 Intel 處理器，比較并交換通過(guò)指令的 cmpxchg 系列實(shí)現(xiàn);

二、cas底層實(shí)現(xiàn)

1、底層依靠Unsafe的CAS操作來(lái)保證原子性;

CAS的實(shí)現(xiàn)主要在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; 
} 

代碼是一個(gè)無(wú)限循環(huán)，也就是CAS的自旋。循環(huán)體當(dāng)中做了三件事：

獲取當(dāng)前值;

當(dāng)前值+1，計(jì)算出目標(biāo)值;

進(jìn)行CAS操作，如果成功則跳出循環(huán)(當(dāng)前值和目標(biāo)值相等)，如果失敗則重復(fù)上述步驟;

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++實(shí)現(xiàn) 

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

3、compareAndSwapInt為native方法，對(duì)應(yīng)底層hotspot虛擬機(jī)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來(lái)保證原子性，可繼續(xù)跟進(jìn)代碼

4、Atomic::cmpxchg針對(duì)不同平臺(tái)有不同的實(shí)現(xiàn)方式

*** 
// 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，通過(guò)lock的方式來(lái)保證原子;

lock解釋：

• 確保后續(xù)指令執(zhí)行的原子性;
• 在Pentium及之前的處理器中，帶有l(wèi)ock前綴的指令在執(zhí)行期間會(huì)鎖住總線，使得其它處理器暫時(shí)無(wú)法通過(guò)總線訪問(wèn)內(nèi)存，很顯然，這個(gè)開(kāi)銷很大。在新的處理器中，Intel使用緩存鎖定來(lái)保證指令執(zhí)行的原子性，緩存鎖定將大大降低lock前綴指令的執(zhí)行開(kāi)銷;
• 禁止該指令與前面和后面的讀寫指令重排序;
• 把寫緩沖區(qū)的所有數(shù)據(jù)刷新到內(nèi)存中;

總之：JAVA中我們使用到涉及到CAS操作的底層實(shí)現(xiàn)為對(duì)應(yīng)平臺(tái)虛擬機(jī)中的c++代碼(lock指令)實(shí)現(xiàn)來(lái)保證原子性;

三、CAS 的缺點(diǎn)及解決方式

CAS雖然很高效的解決原子操作，但是CAS仍然存在三大問(wèn)題。ABA問(wèn)題，循環(huán)時(shí)間長(zhǎng)開(kāi)銷大和只能保證一個(gè)共享變量的原子操作;

1、ABA問(wèn)題：因?yàn)镃AS需要在操作值的時(shí)候檢查下值有沒(méi)有發(fā)生變化，如果沒(méi)有發(fā)生變化則更新，但是如果一個(gè)值原來(lái)是A，變成了B，又變成了A， 那么使用CAS進(jìn)行檢查時(shí)會(huì)發(fā)現(xiàn)它的值沒(méi)有發(fā)生變化，但是實(shí)際上卻變化了;

ABA問(wèn)題的解決思路就是使用版本號(hào)。在變量前面追加上版本號(hào)，每次變量更新的時(shí)候把版本號(hào)加一，那么A-B-A 就會(huì)變成1A-2B-3A;

從Java1.5開(kāi)始JDK的atomic包里提供了一個(gè)類 AtomicStampedReference 來(lái)解決ABA問(wèn)題。這個(gè)類的compareAndSet方法作用是首先檢查當(dāng)前引用是否等于預(yù)期引用，并且當(dāng)前標(biāo)志是否等于預(yù)期標(biāo)志，如果全部相等，則以原子方式將該引用和該標(biāo)志的值設(shè)置為給定的更新值;

2、循環(huán)時(shí)間長(zhǎng)開(kāi)銷大：在并發(fā)量比較高的情況下，如果許多線程反復(fù)嘗試更新某一個(gè)變量，即自旋CAS如果長(zhǎng)時(shí)間不成功，會(huì)給CPU帶來(lái)非常大的執(zhí)行開(kāi)銷;

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

代碼層面，破壞掉for死循環(huán)，當(dāng)自旋超過(guò)一定時(shí)間或者一定次數(shù)時(shí)，return退出;

使用類似ConcurrentHashMap的方法。當(dāng)多個(gè)線程競(jìng)爭(zhēng)時(shí)，將粒度變小，將一個(gè)變量拆分為多個(gè)變量，達(dá)到多個(gè)線程訪問(wèn)多個(gè)資源的效果，最后再調(diào)用sum把它合起來(lái)，能降低CPU消耗，但是治標(biāo)不治本;

3、只能保證一個(gè)共享變量的原子操作：當(dāng)對(duì)一個(gè)共享變量執(zhí)行操作時(shí)，我們可以使用循環(huán)CAS的方式來(lái)保證原子操作，但是對(duì)多個(gè)共享變量操作時(shí)，循環(huán)CAS就無(wú)法保證操作的原子性;

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

從Java1.5開(kāi)始JDK提供了AtomicReference類來(lái)保證引用對(duì)象之間的原子性，你可以把多個(gè)變量放在一個(gè)對(duì)象里來(lái)進(jìn)行CAS操作;

四、CAS使用的時(shí)機(jī)

線程數(shù)較少、等待時(shí)間短可以采用自旋鎖進(jìn)行CAS嘗試拿鎖，較于synchronized高效;

線程數(shù)較大、等待時(shí)間長(zhǎng)，不建議使用自旋鎖，占用CPU較高;

總結(jié)

CAS可以保證多線程對(duì)數(shù)據(jù)寫操作時(shí)數(shù)據(jù)的一致性;

CAS的思想：三個(gè)參數(shù)，一個(gè)當(dāng)前內(nèi)存值V、舊的預(yù)期值A(chǔ)、即將更新的值B，當(dāng)且僅當(dāng)預(yù)期值A(chǔ)和內(nèi)存值V相同時(shí)，將內(nèi)存值修改為B并返回true，否則什么都不做，并返回false;