CAS操作以及jdk1.8后的優(yōu)化

一、前言

說到CAS之前觉壶，先來看看樂觀鎖與悲觀鎖：

悲觀鎖認為：每個線程在對一數(shù)據(jù)進行操作時脑题，都會有其他線程來并發(fā)修改，所以在獲取數(shù)據(jù)的時候就上鎖來進行操作铜靶，synchronized和lock就是一種悲觀鎖的策略叔遂。也就是先上鎖再操作。

樂觀鎖認為：每個線程在對以數(shù)據(jù)進行操作時争剿，沒有其他線程來并發(fā)修改已艰，這樣就其實是所有線程都去讀取共享區(qū)的數(shù)據(jù)，然后在本地工作內(nèi)存操作蚕苇，最后看共享區(qū)的數(shù)據(jù)有無被其他線程更新哩掺。如果沒有則將修改后的數(shù)據(jù)寫入，如果有的話就根據(jù)具體實現(xiàn)具體分析（報錯或者自動重試）涩笤。即直接操作

我們不難得出：
悲觀鎖適合大量寫操作的場景嚼吞，先加鎖可以保證寫操作時數(shù)據(jù)的正確。
樂觀鎖適合大量讀操作的場景蹬碧，不加鎖的特點能夠使其讀操作的性能大大提升舱禽。

二、什么是CAS操作

CAS操作锰茉，全稱Compare and Swap呢蔫，比較并交換。

CAS操作就是一個虛擬機實現(xiàn)的原子操作（一條硬件操作指令，不可被中斷的一個或一系列操作）片吊，功能是將舊值替換為新值绽昏，如果舊值沒有改變則替換成功，否則替換失敗俏脊。

一般使用鎖的時候全谤，線程獲取鎖是一種悲觀鎖策略。即假設每一次在訪問共享資源都會產(chǎn)生沖突爷贫，所以當前線程獲取到鎖的同時就會阻塞其他線程獲取該鎖认然。

而CAS操作是一種樂觀鎖策略。它假設每一次在訪問共享資源時都不會產(chǎn)生沖突漫萄，那不沖突就不會阻塞其他線程獲取該鎖卷员，這樣線程就不會出現(xiàn)阻塞停頓狀態(tài)。Java使用CAS來鑒別線程是否出現(xiàn)沖突腾务，出現(xiàn)沖突就重試當前操作直到?jīng)]有沖突為止毕骡。線程只會收到操作失敗的信號并進行原地自旋，并不會阻塞岩瘦。

三未巫、CAS操作的過程

CAS操作離不開這三個值(V, O, N)：

V：內(nèi)存地址存放的實際值
O：舊值
N：即將更新的新值

當且僅當VO相同時，即舊值和內(nèi)存中實際存放的值相同启昧，這表明該值沒有被其他線程更改過叙凡，此時CAS通過原子的方式將N賦給V，并返回true密末。這是一個比較+更新操作握爷，是原子操作。如果VO不相同严里，則該值已經(jīng)被其他線程修改饼拍，不能把N賦給V，此時不進行操作田炭，返回false。多個線程使用CAS操作一個變量時漓柑，只有一個線程會成功教硫，并且成功更新，其余會失斄静肌（并不會阻塞其他線程）瞬矩。失敗的線程會重新嘗試，也可以選擇掛起線程锋玲。

synchronized存在線程競爭的情況下會出現(xiàn)線程阻塞和喚醒鎖帶來的性能問題景用，因為這是一種互斥同步（阻塞同步）。而CAS在競爭時如果失敗，會進行一定的嘗試伞插，而并不是單純的進行掛起喚醒操作割粮，因此也叫非阻塞同步。

四媚污、CAS的問題

CAS主要有以下三個問題：

1.ABA問題

CAS會檢查共享內(nèi)存的值有無變化舀瓢，如果我們的共享內(nèi)存值由A變成了B，可是又由B變回來了耗美，此時CAS檢查的時候發(fā)現(xiàn)共享內(nèi)存的值并沒有變化依然為A京髓，但是實際上卻是發(fā)生了變化。如果基本類型倒無所謂商架，引用類型就會有一些問題堰怨。

解決方案：對其進行版本控制，這樣A-B-A就變成1A-2B-3A了蛇摸。Java1.5后atomic包提供的AromicStampedReference來解決ABA問題备图，具體封裝在compareAndSet()中。compareAndSet()首先檢查當前引用和當前標志與預期引用和預期標志是否相等皇型，如果都相等诬烹，則以原子方式將引用值和標志的值設置為給定的更新值。

2.自旋時間過長

CAS是一種非阻塞同步弃鸦，線程不會自己被掛起绞吁，而是不停的嘗試而產(chǎn)生自旋現(xiàn)象（會死循環(huán)），自旋時間過長就會造成CPU很大的性能消耗唬格。
解決方案請看夏慶文

3.只能保證一個共享變量的原子操作

如果對多個共享變量進行操作家破，CAS不能保證其原子性。
解決方案：利用對象整合多個變量购岗，即一個類中的成員就是這幾個變量汰聋，然后對這個對象進行CAS操作，這么做就能保證其原子性喊积。atomic提供了AtomicReference來保證引用對象的原子性

五烹困、jdk1.8對于CAS的優(yōu)化

jdk1.8提供了一個LongAdder類，嘗試使用分段CAS以及自動分段遷移的方式來大幅度替身多線程高并發(fā)執(zhí)行CAS的性能乾吻。

1.分段CAS：

public class LongAdder extends Striped64 implements Serializable

其繼承的Striped64里面有兩個重要變量：

/**
 * Table of cells. When non-null, size is a power of 2.
 * cell數(shù)組髓梅，大小總是2的冪次方
 */
transient volatile Cell[] cells;
/**
 * Base value, used mainly when there is no contention, but also as
 * a fallback during table initialization races. Updated via CAS.
 * 基本值，主要在沒有爭用的情況下使用绎签，在表的初始化的時候也作為一個基礎值枯饿。通過CAS更新。
 */
transient volatile long base;

如果發(fā)現(xiàn)并發(fā)更新的線程數(shù)量不是很多诡必，就直接給base值進行累加奢方。如果發(fā)現(xiàn)并發(fā)更新的數(shù)量過多，就開始實行分段CAS機制，系統(tǒng)把這些線程分配到不同的cell數(shù)組元素中蟋字。

public void add(long x) {
    Cell[] cs; long b, v; int m; Cell c;
    if ((cs = cells) != null || !casBase(b = base, b + x)) {
        boolean uncontended = true;
        if (cs == null || (m = cs.length - 1) < 0 ||
            (c = cs[getProbe() & m]) == null ||
            !(uncontended = c.cas(v = c.value, v + x)))
            longAccumulate(x, null, uncontended);
    }
}

源碼大概流程就是首先通過CAS進行對base值的更新稿蹲，此時只有一個線程會成功，然后保存進sum愉老。其余的線程進行cell數(shù)組計算下標并分配场绿，每個線程依次的對cell的元素進行累加，最后將base + sum[i] 求出最后的總和嫉入。

看一下LongAdder中的求cell數(shù)組總和的源碼：

public long sum() {
    Cell[] cs = cells;
    long sum = base;
    if (cs != null) {
        for (Cell c : cs)
            if (c != null)
                sum += c.value;
    }
    return sum;
}

假設當前有80個線程進行一變量的自增操作焰盗，cell數(shù)組長度為8，則每一組都有10個線程咒林，每一組對cell數(shù)組的其中一個元素做自增熬拒，最后cell數(shù)組8個元素的值都為10，累加得到80垫竞。這就等于80個線程對i進行了80次自增操作澎粟。

2.自動遷移機制

隨著線程增多，每個cell中分配的線程數(shù)也會增多欢瞪，當其中一個線程操作失敗的時候活烙，它會自動遷移到下一個cell中進行操作，這也就解決了CAS空旋轉(zhuǎn)遣鼓，自旋不停等待的問題啸盏。