CAS算法與Java原子類

點(diǎn)擊上方藍(lán)色字體，選擇“標(biāo)星公眾號(hào)”

優(yōu)質(zhì)文章，第一時(shí)間送達(dá)

? 作者?|??低吟不作語(yǔ)

來(lái)源 |? urlify.cn/eYzAZr

66套java從入門(mén)到精通實(shí)戰(zhàn)課程分享

1、樂(lè)觀鎖

一般而言，在并發(fā)情況下我們必須通過(guò)一定的手段來(lái)保證數(shù)據(jù)的準(zhǔn)確性，如果沒(méi)有做好并發(fā)控制，就可能導(dǎo)致臟讀、幻讀和不可重復(fù)度等一系列問(wèn)題。樂(lè)觀鎖是人們?yōu)榱藨?yīng)付并發(fā)問(wèn)題而提出的一種思想，具體的實(shí)現(xiàn)則有多種方式。

樂(lè)觀鎖假設(shè)數(shù)據(jù)一般情況下不會(huì)造成沖突，只在數(shù)據(jù)進(jìn)行提交更新時(shí)，才會(huì)正式對(duì)數(shù)據(jù)的沖突與否進(jìn)行檢測(cè)，如果發(fā)現(xiàn)沖突了，則返回給用戶錯(cuò)誤的信息，讓用戶決定如何去做。樂(lè)觀鎖適用于讀操作多的場(chǎng)景，可以提高程序的吞吐量。

2、CAS

CAS（Compare And Swap）比較并交換，是一種實(shí)現(xiàn)了樂(lè)觀鎖思想的并發(fā)控制技術(shù)。CAS 算法的過(guò)程是：它包含 3 個(gè)參數(shù) CAS（V，E，N），V 表示要更新的變量（內(nèi)存值），E 表示舊的預(yù)期值，N 表示即將更新的預(yù)期值。當(dāng)且僅當(dāng) V 值等于 E 值時(shí)，才會(huì)將 V 的值設(shè)為 N，如果 V 值和 E 值不同，說(shuō)明已經(jīng)有其他線程做了更新，則當(dāng)前線程什么也不做，并返回當(dāng)前 V 的真實(shí)值。整個(gè)操作是原子性的。

當(dāng)多個(gè)線程同時(shí)使用 CAS 操作一個(gè)變量時(shí)，只有一個(gè)會(huì)勝出，并成功更新，其余均會(huì)失敗。失敗的線程不會(huì)被掛起，僅是被告知失敗，并允許再次嘗試，當(dāng)然也可以放棄本次操作，所以 CAS 算法是非阻塞的。基于上述原理，CAS 操作可以在不借助鎖的情況下實(shí)現(xiàn)合適的并發(fā)處理。

3、ABA 問(wèn)題

ABA 問(wèn)題是 CAS 算法的一個(gè)漏洞。CAS 算法實(shí)現(xiàn)的一個(gè)重要前提是：取出內(nèi)存中某時(shí)刻的數(shù)據(jù)，并在下一時(shí)刻比較并替換，在這個(gè)時(shí)間差內(nèi)可能會(huì)導(dǎo)致數(shù)據(jù)的變化。

假設(shè)有兩個(gè)線程，分別要對(duì)內(nèi)存中某一變量做 CAS 操作，線程一先從內(nèi)存中取出值 A，線程二也從內(nèi)存中取出值 A，并把值從 A 變?yōu)?B 寫(xiě)回，然后又把值從 B 變?yōu)?A 寫(xiě)回，這時(shí)候線程一進(jìn)行 CAS 操作，發(fā)現(xiàn)內(nèi)存中的值還是 A，于是認(rèn)為和預(yù)期值一致，操作成功。盡管線程一的 CAS 操作成功，但并不代表這個(gè)過(guò)程就沒(méi)有問(wèn)題。

ABA 問(wèn)題會(huì)帶來(lái)什么隱患呢？維基百科給出了詳細(xì)的示例：假設(shè)現(xiàn)有一個(gè)用單鏈表實(shí)現(xiàn)的堆棧，棧頂為 A，A.next = B，現(xiàn)有線程一希望用 CAS 把棧頂替換為 B，但在此之前，線程二介入，將 A、B 出棧，再壓入 D、C、A，整個(gè)過(guò)程如下

此時(shí) B 處于游離轉(zhuǎn)態(tài)，輪到線程一執(zhí)行 CAS 操作，發(fā)現(xiàn)棧頂仍為 A，CAS 成功，棧頂變?yōu)?B，但實(shí)際上 B.next = null，即堆棧中只有 B 一個(gè)元素，C 和 D 并不在堆棧中，平白無(wú)故就丟了。簡(jiǎn)單來(lái)說(shuō)，ABA 問(wèn)題使我們漏掉某一段時(shí)間的數(shù)據(jù)監(jiān)控，誰(shuí)知道在這段時(shí)間內(nèi)會(huì)發(fā)生什么有趣（可怕）的事呢？

可以通過(guò)版本號(hào)的方式來(lái)解決 ABA 問(wèn)題，每次執(zhí)行數(shù)據(jù)修改操作時(shí)，都會(huì)帶上一個(gè)版本號(hào)，如果版本號(hào)和數(shù)據(jù)的版本一致，對(duì)數(shù)據(jù)進(jìn)行修改操作并對(duì)版本號(hào) +1，否則執(zhí)行失敗。因?yàn)槊看尾僮鞯陌姹咎?hào)都會(huì)隨之增加，所以不用擔(dān)心出現(xiàn) ABA 問(wèn)題。

4、使用 Java 模擬 CAS 算法

這僅僅是基于 Java 層面上的模擬，真正的實(shí)現(xiàn)要涉及到底層（我學(xué)不會(huì)）

public?class?TestCompareAndSwap?{

????private?static?CompareAndSwap?cas?=?new?CompareAndSwap();

????public?static?void?main(String[]?args)?{

????????for?(int?i?=?0;?i?????????????new?Thread(new?Runnable()?{
????????????????public?void?run()?{
????????????????????//?獲取預(yù)估值
????????????????????int?expectedValue?=?cas.get();
????????????????????boolean?b?=?cas.compareAndSet(expectedValue,?(int)?(Math.random()?*?101));
????????????????????System.out.println(b);
????????????????}
????????????});
????????}
????}
}

class?CompareAndSwap?{

????private?int?value;

????//?獲取內(nèi)存值
????public?synchronized?int?get()?{
????????return?value;
????}

????//?比較
????public?synchronized?int?compareAndSwap(int?expectedValue,?int?newValue)?{
????????//?讀取內(nèi)存值
????????int?oldValue?=?value;
????????//?比較
????????if?(oldValue?==?expectedValue)?{
????????????this.value?=?newValue;
????????}
????????return?oldValue;
????}

????//?設(shè)置
????public?synchronized?boolean?compareAndSet(int?expectedValue,?int?newValue)?{
????????return?expectedValue?==?compareAndSwap(expectedValue,?newValue);
????}
}

5、原子類

原子包 java.util.concurrent.atomic 提供了一組原子類，原子類的操作具有原子性，一旦開(kāi)始，就一直運(yùn)行直到結(jié)束，中間不會(huì)有任何線程上下文切換。原子類的底層正是基于 CAS 算法實(shí)現(xiàn)線程安全。

Java 為我們提供了十六個(gè)原子類，可以大致分為以下四種：

1. 基本類型

• AtomicBoolean

  原子更新布爾類型，內(nèi)部使用 int 類型的 value 存儲(chǔ) 1 和 0 表示 true 和 false，底層也是對(duì) int 類型的原子操作

• AtomicInteger

  原子更新 int 類型

• AtomicLong

  原子更新 long 類型

2. 引用類型

• AtomicReference

  原子更新引用類型，通過(guò)泛型指定要操作的類

• AtomicMarkableReference

  原子更新引用類型，內(nèi)部維護(hù)一個(gè) Pair 類型（靜態(tài)內(nèi)部類）的成員屬性，其中有一個(gè) boolean 類型的標(biāo)志位，避免 ABA 問(wèn)題

• private?static?class?Pair?{
  ????final?T?reference;
  ????final?boolean?mark;
  ????private?Pair(T?reference,?boolean?mark)?{
  ????????this.reference?=?reference;
  ????????this.mark?=?mark;
  ????}
  ????static??Pair?of(T?reference,?boolean?mark)?{
  ????????return?new?Pair(reference,?mark);
  ????}
  }
  
  private?volatile?Pair?pair
  

• AtomicStampedReference

  原子更新引用類型，內(nèi)部維護(hù)一個(gè) Pair 類型（靜態(tài)內(nèi)部類）的成員屬性，其中有一個(gè) int 類型的郵戳（版本號(hào)），避免 ABA 問(wèn)題

• private?static?class?Pair?{
  ????final?T?reference;
  ????final?int?stamp;
  ????private?Pair(T?reference,?int?stamp)?{
  ????????this.reference?=?reference;
  ????????this.stamp?=?stamp;
  ????}
  ????static??Pair?of(T?reference,?int?stamp)?{
  ????????return?new?Pair(reference,?stamp);
  ????}
  }
  
  private?volatile?Pair?pair
  

3. 數(shù)組類型

• AtomicIntegerArray

  原子更新 int 數(shù)組中的元素

• AtomicLongArray

  原子更新 long 數(shù)組中的元素

• AtomicReferenceArray

  原子更新 Object 數(shù)組中的元素

4. 對(duì)象屬性類型

用于解決對(duì)象的屬性的原子操作

• AtomicIntegerFieldUpdater

  原子更新對(duì)象中的 int 類型字段

• AtomicLongFieldUpdater

  原子更新對(duì)象中的 long 類型字段

• AtomicReferenceFieldUpdater

  原子更新對(duì)象中的引用類型字段

之前提到的三種類型的使用都比較簡(jiǎn)單，查閱對(duì)應(yīng) API 即可，而對(duì)象屬性類型則有一些限制：

• 字段必須是 volatile 類型的，在線程之間共享變量時(shí)保證立即可見(jiàn)

• 只能是實(shí)例變量，不能是類變量，也就是說(shuō)不能加 static 關(guān)鍵字

• 只能是可修改變量，不能使用 final 變量

• 該對(duì)象字段能夠被直接操作，因?yàn)樗腔诜瓷鋵?shí)現(xiàn)的

5. 高性能原子類

Java8 新增的原子類，使用分段的思想，把不同的線程 hash 到不同的段上去更新，最后再把這些段的值相加得到最終的值。以下四個(gè)類都繼承自 Striped64，對(duì)并發(fā)的優(yōu)化在 Striped64 中實(shí)現(xiàn)

• LongAccumulator

  long 類型的聚合器，需要傳入一個(gè) long 類型的二元操作，可以用來(lái)計(jì)算各種聚合操作，包括加乘等

• LongAdder

  long 類型的累加器，LongAccumulator 的特例，只能用來(lái)計(jì)算加法，且從 0 開(kāi)始計(jì)算

• DoubleAccumulator

  double 類型的聚合器，需要傳入一個(gè) double 類型的二元操作，可以用來(lái)計(jì)算各種聚合操作，包括加乘等

• DoubleAdder

  double 類型的累加器，DoubleAccumulator 的特例，只能用來(lái)計(jì)算加法，且從 0 開(kāi)始計(jì)算

  
  

粉絲福利：實(shí)戰(zhàn)springboot+CAS單點(diǎn)登錄系統(tǒng)視頻教程免費(fèi)領(lǐng)取

???

?長(zhǎng)按上方微信二維碼?2 秒
即可獲取資料

感謝點(diǎn)贊支持下哈?