ABA問題的本質及其解決辦法

目錄

• ​​簡介​​

• ​​第一類問題​​
• ​​第二類問題​​

• ​​第一類問題的解決​​
• ​​第二類問題的解決​​
• ​​總結​​

簡介

CAS的全稱是compare and swap，它是java同步類的基礎，java.util.concurrent中的同步類基本上都是使用CAS來實作其原子性的。

CAS的原理其實很簡單，為了保證在多線程環境下我們的更新是符合預期的，或者說一個線程在更新某個對象的時候，沒有其他的線程對該對象進行修改。線上程更新某個對象（或值）之前，先儲存更新前的值，然後在實際更新的時候傳入之前儲存的值，進行比較，如果一緻的話就進行更新，否則失敗。

注意，CAS在java中是用native方法來實作的，利用了系統本身提供的原子性操作。

那麼CAS在使用中會有什麼問題呢？一般來說CAS如果設計的不夠完美的話，可能會産生ABA問題，而ABA問題又可以分為兩類，我們先看來看一類問題。

第一類問題

我們考慮下面一種ABA的情況：

1. 在多線程的環境中，線程a從共享的位址X中讀取到了對象A。
2. 線上程a準備對位址X進行更新之前，線程b将位址X中的值修改為了B。
3. 接着線程b将位址X中的值又修改回了A。
4. 最新線程a對位址X執行CAS，發現X中存儲的還是對象A，對象比對，CAS成功。

上面的例子中CAS成功了，但是實際上這個CAS并不是原子操作，如果我們想要依賴CAS來實作原子操作的話可能就會出現隐藏的bug。

第一類問題的關鍵就在2和3兩步。這兩步我們可以看到線程b直接替換了記憶體位址X中的内容。

在擁有自動GC環境的程式設計語言，比如說java中，2，3的情況是不可能出現的，因為在java中，隻要兩個對象的位址一緻，就表示這兩個對象是相等的。

2，3兩步可能出現的情況就在像C++這種，不存在自動GC環境的程式設計語言中。因為可以自己控制對象的生命周期，如果我們從一個list中删除掉了一個對象，然後又重新配置設定了一個對象，并将其add back到list中去，那麼根據 MRU memory allocation算法，這個新的對象很有可能和之前删除對象的記憶體位址是一樣的。這樣就會導緻ABA的問題。

第二類問題

如果我們在擁有自動GC的程式設計語言中，那麼是否仍然存在CAS問題呢？

考慮下面的情況，有一個連結清單裡面的資料是A->B->C,我們希望執行一個CAS操作，将A替換成D，生成連結清單D->B->C。考慮下面的步驟：

1. 線程a讀取連結清單頭部節點A。
2. 線程b将連結清單中的B節點删掉，連結清單變成了A->C
3. 線程a執行CAS操作，将A替換從D。

最後我們的到的連結清單是D->C，而不是D->B->C。

問題出在哪呢？CAS比較的節點A和最新的頭部節點是不是同一個節點，它并沒有關心節點A在步驟1和3之間是否内容發生變化。

我們舉個例子：

public void useABAReference(){
        CustUser a= new CustUser();
        CustUser b= new CustUser();
        CustUser c= new CustUser();
        AtomicReference<CustUser> atomicReference= new AtomicReference<>(a);
        log.info("{}",atomicReference.compareAndSet(a,b));
        log.info("{}",atomicReference.compareAndSet(b,a));
        a.setName("change for new name");
        log.info("{}",atomicReference.compareAndSet(a,c));
    }      

上面的例子中，我們使用了AtomicReference的CAS方法來判斷對象是否發生變化。在CAS b和a之後，我們将a的name進行了修改，我們看下最後的輸出結果：

[main] INFO com.flydean.aba.ABAUsage - true
[main] INFO com.flydean.aba.ABAUsage - true
[main] INFO com.flydean.aba.ABAUsage - true      

三個CAS的結果都是true。說明CAS确實比較的兩者是否為統一對象，對其中内容的變化并不關心。

第二類問題可能會導緻某些集合類的操作并不是原子性的，因為你并不能保證在CAS的過程中，有沒有其他的節點發送變化。

第一類問題的解決

第一類問題在存在自動GC的程式設計語言中是不存在的，我們主要看下怎麼在C++之類的語言中解決這個問題。

根據官方的說法，第一類問題大概有四種解法：

1. 使用中間節點 - 使用一些不代表任何資料的中間節點來表示某些節點是标記被删除的。
2. 使用自動GC。
3. 使用hazard pointers - hazard pointers 儲存了目前線程正在通路的節點的位址，在這些hazard pointers中的節點不能夠被修改和删除。
4. 使用read-copy update (RCU) - 在每次更新的之前，都做一份拷貝，每次更新的是拷貝出來的新結構。

第二類問題的解決

第二類問題其實算是整體集合對象的CAS問題了。一個簡單的解決辦法就是每次做CAS更新的時候再添加一個版本号。如果版本号不是預期的版本，就說明有其他的線程更新了集合中的某些節點，這次CAS是失敗的。

我們舉個AtomicStampedReference的例子：

public void useABAStampReference(){
        Object a= new Object();
        Object b= new Object();
        Object c= new Object();
        AtomicStampedReference<Object> atomicStampedReference= new AtomicStampedReference(a,0);
        log.info("{}",atomicStampedReference.compareAndSet(a,b,0,1));
        log.info("{}",atomicStampedReference.compareAndSet(b,a,1,2));
        log.info("{}",atomicStampedReference.compareAndSet(a,c,0,1));
    }      

AtomicStampedReference的compareAndSet方法，多出了兩個參數，分别是expectedStamp和newStamp，兩個參數都是int型的，需要我們手動傳入。

總結

ABA問題其實是由兩類問題組成的，需要我們分開來對待和解決。

本文的例子​​https://github.com/ddean2009/

learn-java-base-9-to-20​​

本文作者：flydean程式那些事