什么是CAS

CAS算法（Compare And Swap），即比較并替換，是一種實(shí)現(xiàn)并發(fā)編程時(shí)常用到的算法，Java并發(fā)包中的很多類都使用了CAS算法。

CAS算法有3個(gè)基本操作數(shù)：

• 內(nèi)存地址V
• 舊的預(yù)期值A(chǔ)
• 要修改的新值B

CAS使用自旋的方式來交換值，操作步驟為：

1. 讀取內(nèi)存地址V的值保存在A中
2. 在原子操作中比較內(nèi)存地址V的值是否與A相同
3. 相同時(shí)，修改內(nèi)存地址V的值為B，原子操作成功。
4. 不相同時(shí)，循環(huán)執(zhí)行第一至第三步（自旋），直到成功。

什么是自旋鎖？

自旋鎖（spinlock）：是指當(dāng)一個(gè)線程在獲取鎖的時(shí)候，如果鎖已經(jīng)被其它線程獲取，那么該線程將循環(huán)等待，然后不斷的判斷鎖是否能夠被成功獲取，直到獲取到鎖才會(huì)退出循環(huán)。

自旋鎖與互斥鎖比較類似，它們都是為了解決對(duì)某項(xiàng)資源的互斥使用。無論是互斥鎖，還是自旋鎖，在任何時(shí)刻，最多只能有一個(gè)保持者，也就說，在任何時(shí)刻最多只能有一個(gè)執(zhí)行單元獲得鎖。

對(duì)于互斥鎖，會(huì)讓沒有得到鎖資源的線程進(jìn)入BLOCKED狀態(tài)，而后在爭(zhēng)奪到鎖資源后恢復(fù)為RUNNABLE狀態(tài)，這個(gè)過程中涉及到操作系統(tǒng)用戶模式和內(nèi)核模式的轉(zhuǎn)換，代價(jià)比較高。但是自旋鎖不會(huì)引起調(diào)用者堵塞，如果自旋鎖已經(jīng)被別的執(zhí)行單元保持，調(diào)用者就一直循環(huán)在那里看是否該自旋鎖的保持者已經(jīng)釋放了鎖。

自旋鎖的實(shí)現(xiàn)基礎(chǔ)是CAS算法機(jī)制。CAS自旋鎖屬于樂觀鎖，樂觀地認(rèn)為程序中的并發(fā)情況不那么嚴(yán)重，所以讓線程不斷去嘗試更新。

基于CAS實(shí)現(xiàn)-原子操作類

先看一個(gè)線程不安全的例子：

public class AutomicDemo {
    public static int num = 0;
    public static void main(String[] args){
        for(int i=0; i<5; i++){
            new Thread(new Runnable() {
                @Override
                public void run() {
                    try {
                        Thread.sleep(10);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    for(int j=0; j<200; j++){
                        num++;
                    }
                }
            }).start();
        }
        /* 主控失眠3秒，保證所有線程執(zhí)行完成 */
        try {
            Thread.sleep(15000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("num=" + num);
    }
}

輸出結(jié)果：

num=950

因?yàn)樽栽霾僮鞑皇窃有?，多線程環(huán)境下，訪問共享變量線程不安全。

解決方法，加synchronized同步鎖：

for(int j=0; j<200; j++){
    synchronized (AutomicDemo.class){
        num++;
    }
}

輸出結(jié)果：
num=1000

線程安全。

synchronized確保了線程安全，但會(huì)讓沒有得到鎖資源的線程進(jìn)入BLOCKED狀態(tài)，而后在爭(zhēng)奪到鎖資源后恢復(fù)為RUNNABLE狀態(tài)，這個(gè)過程中涉及到操作系統(tǒng)用戶模式和內(nèi)核模式的轉(zhuǎn)換，代價(jià)比較高。

盡管Java1.6為Synchronized做了優(yōu)化，增加了從偏向鎖到輕量級(jí)鎖再到重量級(jí)鎖的過度，但是在最終轉(zhuǎn)變?yōu)橹亓考?jí)鎖之后，性能仍然較低。

于是JDK提供了一系列原子操作類：AtomicInteger、AtomicLong、AtomicBoolean、AtomicReference等，它們都是基于CAS去實(shí)現(xiàn)的，下面我們就來詳細(xì)看一看原子操作類。

public class AutomicDemo {
    public static AtomicInteger num = new AtomicInteger(0);
    public static void main(String[] args){
        for(int i=0; i<5; i++){
            new Thread(new Runnable() {
                @Override
                public void run() {
                    try {
                        Thread.sleep(10);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    for(int j=0; j<200; j++){
                        num.incrementAndGet();
                    }
                }
            }).start();
        }
        /* 主控失眠3秒，保證所有線程執(zhí)行完成 */
        try {
            Thread.sleep(15000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("num=" + num.get());
    }
}

輸出：
num=1000

使用AtomicInteger之后，最終的輸出結(jié)果同樣可以保證是200。并且在某些情況下，代碼的性能會(huì)比Synchronized更好。

原子類操作方法

• public final int get()：取得當(dāng)前值
• public final void set(int newValue)：設(shè)置當(dāng)前值
• public final int getAndSet(int newValue)：設(shè)置新值并返回舊值
• public final boolean compareAndSet(int expect, int update)：如果當(dāng)前值為expect，則設(shè)置為update
• public final boolean weakCompareAndSet(int expect, int update)：如果當(dāng)前值為expect，則設(shè)置為update，可能失敗，不提供保障
• public final int getAndIncrement()：當(dāng)前值加1，返回舊值
• public final int getAndDecrement()：當(dāng)前值減1，返回舊值
• public final int getAndAdd(int delta)：當(dāng)前值加delta，返回舊值
• public final int incrementAndGet()：當(dāng)前值加1，返回新值
• public final int decrementAndGet()：當(dāng)前值減1，返回新值
• public final int addAndGet(int delta)：當(dāng)前值加delta，返回新值

AtomicInteger底層原理

所有Atomic相關(guān)類的實(shí)現(xiàn)都是通過CAS（Compare And Swap）去實(shí)現(xiàn)的，它是一種樂觀鎖的實(shí)現(xiàn)。

CAS實(shí)現(xiàn)放在 Unsafe 這個(gè)類中的，其內(nèi)部大部分是native方法。這個(gè)類是不允許更改的，而且也不建議開發(fā)者調(diào)用，它只是用于JDK內(nèi)部調(diào)用，看名字就知道它是不安全的，因?yàn)樗侵苯硬僮鲀?nèi)存，稍不注意就可能把內(nèi)存寫崩。

Unsafe類使Java擁有了像C語言的指針一樣操作內(nèi)存空間的能力。有一下特點(diǎn)：

1、不受jvm管理，也就意味著無法被GC，需要我們手動(dòng)GC，稍有不慎就會(huì)出現(xiàn)內(nèi)存泄漏。

2、Unsafe的不少方法中必須提供原始地址(內(nèi)存地址)和被替換對(duì)象的地址，偏移量要自己計(jì)算，一旦出現(xiàn)問題就是JVM崩潰級(jí)別的異常，會(huì)導(dǎo)致整個(gè)JVM實(shí)例崩潰，表現(xiàn)為應(yīng)用程序直接crash掉。

3、直接操作內(nèi)存，也意味著其速度更快，在高并發(fā)的條件之下能夠很好地提高效率。

去看AtomicInteger的內(nèi)部實(shí)現(xiàn)可以發(fā)現(xiàn)，全是調(diào)用的Unsafe類中的方法：

CAS機(jī)制ABA問題

ABA問題：CAS算法通過比較變量值是否相同來修改變量值以保證原子性，但如果一個(gè)內(nèi)存地址的值本身是A，線程1準(zhǔn)備修改為C。在這期間，線程2將值修改為B，線程3將值修改為A，線程1獲取內(nèi)存地址的值還是A，故修改為C成功。但獲取的A已不再是最開始那一個(gè)A。這就是經(jīng)典的ABA問題，A已不再是A。

如何解決ABA問題呢？

兩個(gè)方法，1、增加版本號(hào)；2、增加時(shí)間戳。

• 增加版本號(hào)：讓值的修改從A-B-A-C變?yōu)?A-2B-3A-4C；這樣在線程1 中就能判別出1A不是當(dāng)前內(nèi)存中的3A，從而不會(huì)更新變量為4C。
• 增加時(shí)間戳：值被修改時(shí)，除了更新數(shù)據(jù)本身外，還必須更新時(shí)間戳。對(duì)象值以及時(shí)間戳都必須滿足期望，寫入才會(huì)成功。JDK提供了一個(gè)帶有時(shí)間戳的CAS操作類AtomicStampedeReference。

CAS的缺點(diǎn)

Java原子類使用自旋的方式來處理每次比較不相同時(shí)后的重試操作，下面來看看AtomicInteger類incrementAndGet方法的代碼：

//AtomicInteger 的incrementAndGet方法，變量U為靜態(tài)常量jdk.internal.misc.Unsafe類型
public final int incrementAndGet() {
  //使用getAndAddInt方法，實(shí)際操作類似j++
  return U.getAndAddInt(this, VALUE, 1) + 1;
}
//jdk.internal.misc.Unsafe類型的getAndAddInt方法
public final int getAndAddInt(Object o, long offset, int delta) {
  int v;
  do {
    //獲取變量o的可見值
    v = getIntVolatile(o, offset);
    //比較與替換變量o（CAS算法）
  } while (!weakCompareAndSetInt(o, offset, v, v + delta));
  return v;
}
//jdk.internal.misc.Unsafe類型的weakCompareAndSetInt方法
public final boolean weakCompareAndSetInt(Object o, long offset,
                                              int expected,
                                              int x) {
  //執(zhí)行比較與替換
  return compareAndSetInt(o, offset, expected, x);
}

在Unsafe類的getAndAddInt方法中使用了do…while循環(huán)語句，循環(huán)語句的作用為自旋，Unsafe的weakCompareAndSetInt實(shí)現(xiàn)CAS算法。

如果weakCompareAndSetInt一直不成功將會(huì)一直自旋下去，這將消耗過多的CPU時(shí)間。而且原子類使用CAS算法實(shí)現(xiàn)，這導(dǎo)致原子類只能保證一個(gè)變量的原子操作，對(duì)于需要保證一個(gè)具有多個(gè)操作的事務(wù)將變得無能為力。

總結(jié)如下：

• CPU開銷較大
  • 在并發(fā)量比較高的情況下，如果許多線程反復(fù)嘗試更新某一個(gè)變量，卻又一直更新不成功，循環(huán)往復(fù)，自旋會(huì)給CPU帶來很大的壓力。
• 不能保證代碼塊的原子性
  • CAS機(jī)制所保證的只是一個(gè)變量的原子性操作，而不能保證整個(gè)代碼塊的原子性。比如需要保證3個(gè)變量共同進(jìn)行原子性的更新，就不得不使用Synchronized了。

為應(yīng)對(duì)CAS存在缺點(diǎn)，替換方案如下：

• 自旋效率：Java提供了自適應(yīng)自旋鎖
• 片面性：應(yīng)對(duì)片面性問題Java提供了讀寫鎖
• ABA問題：用AtomicStampedReference/AtomicMarkableReference解決ABA問題

到此這篇關(guān)于Java中的CAS和自旋鎖詳解的文章就介紹到這了,更多相關(guān)Java的CAS和自旋鎖內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論