1. CAS

1.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í)行更新。

1.2 CAS 的應(yīng)用

CAS 有 3 個(gè)操作數(shù)噩斟，內(nèi)存值 V曹锨，舊的預(yù)期值 A，要修改的新值 B剃允。當(dāng)且僅當(dāng)預(yù)期值 A 和內(nèi)存值 V 相同時(shí)沛简，將內(nèi)存值 V 修改為 B，否則什么都不做斥废。

1.3 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)銷大誊垢。自旋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í)行效率。

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操作澳泵。

1.4 CAS 的原理

CAS 通過(guò)調(diào)用 JNI 的代碼實(shí)現(xiàn)的。JNI:java Native Interface 為 JAVA 本地調(diào)用兼呵，允許 java 調(diào)用其他語(yǔ)言兔辅。而compareAndSwapInt就是借助C來(lái)調(diào)用CPU底層指令實(shí)現(xiàn)的。

下面從分析比較常用的CPU（intel x86）來(lái)解釋CAS的實(shí)現(xiàn)原理击喂。下面是sun.misc.Unsafe類的compareAndSwapInt()方法的源代碼：

public final native boolean compareAndSwapInt(Object o, long offset,
                                              int expected,
                                              int x);

結(jié)合對(duì)應(yīng)于intel x86處理器的源代碼的片段分析维苔，可知程序會(huì)根據(jù)當(dāng)前處理器的類型來(lái)決定是否為cmpxchg指令添加lock前綴。如果程序是在多處理器上運(yùn)行懂昂，就為cmpxchg指令加上lock前綴（lock cmpxchg）介时。反之，如果程序是在單處理器上運(yùn)行凌彬，就省略lock前綴（單處理器自身會(huì)維護(hù)單處理器內(nèi)的順序一致性沸柔，不需要lock前綴提供的內(nèi)存屏障效果）。

2. AQS

具體細(xì)節(jié)看文章：

http://www.cnblogs.com/everSeeker/p/5582007.html 铲敛， 主要講 reentrantlock

http://www.cnblogs.com/waterystone/p/4920797.html 褐澎， 主要講 AQS 源碼，未讀完

http://www.reibang.com/p/6afaef97264a , 鎖的獲取和釋放流程伐蒋，大致的講解工三。

2.1 概述

AbstractQueuedSynchronizer(簡(jiǎn)稱AQS)，隊(duì)列同步器先鱼，是用來(lái)構(gòu)建鎖或者其他同步組建的基礎(chǔ)框架俭正。該類主要包括：

1. 模式分為共享和獨(dú)占。

2. volatile int state焙畔，用來(lái)表示鎖的狀態(tài)掸读。state = 0 表示鎖空閑，>0 表示鎖已被占用。

3. FIFO雙向隊(duì)列寺枉，用來(lái)維護(hù)等待獲取鎖的線程抑淫。

image

獨(dú)占模式的鎖：ReentrantLock

共享模式的鎖：Semaphore，CountDownLatch

AQS 部分代碼說(shuō)明如下：

public abstract class AbstractQueuedSynchronizer
    extends AbstractOwnableSynchronizer
    implements java.io.Serializable {

    static final class Node {
        /** 共享模式姥闪，表示可以多個(gè)線程獲取鎖始苇，比如讀寫鎖中的讀鎖 */
        static final Node SHARED = new Node();
        /** 獨(dú)占模式，表示同一時(shí)刻只能一個(gè)線程獲取鎖筐喳，比如讀寫鎖中的寫鎖 */
        static final Node EXCLUSIVE = null;

        volatile Node prev;
        volatile Node next;
        volatile Thread thread;
    }

    /** AQS類內(nèi)部維護(hù)一個(gè)FIFO的雙向隊(duì)列催式，負(fù)責(zé)同步狀態(tài)的管理，當(dāng)前線程獲取同步狀態(tài)失敗時(shí)避归，同步器會(huì)將當(dāng)前線程以及等待狀態(tài)等
        構(gòu)造成一個(gè)節(jié)點(diǎn)Node并加入同步隊(duì)列荣月；當(dāng)同步狀態(tài)釋放時(shí)，會(huì)把首節(jié)點(diǎn)中線程喚醒梳毙，使其再次嘗試同步狀態(tài) */
    private transient volatile Node head;
    private transient volatile Node tail;

    /** 狀態(tài)哺窄，主要用來(lái)確定lock是否已經(jīng)被占用；在ReentrantLock中账锹，state=0表示鎖空閑萌业，>0表示鎖已被占用；可以自定義奸柬，改寫tryAcquire(int acquires)等方法即可  */
    private volatile int state;
}

這里主要說(shuō)明下雙向隊(duì)列生年，通過(guò)查看源碼分析，隊(duì)列是這個(gè)樣子的：

head -> node1 -> node2 -> node3(tail)

注意：head初始時(shí)是一個(gè)空節(jié)點(diǎn)(所謂的空節(jié)點(diǎn)意思是節(jié)點(diǎn)中沒(méi)有具體的線程信息)廓奕，之后表示的是獲取了鎖的節(jié)點(diǎn)抱婉。因此實(shí)際上head->next(即node1)才是同步隊(duì)列中第一個(gè)可用節(jié)點(diǎn)。

AQS的設(shè)計(jì)基于模版方法模式桌粉，使用者通過(guò)繼承AQS類并重寫指定的方法蒸绩，可以實(shí)現(xiàn)不同功能的鎖×蹇希可重寫的方法主要包括：

image

不同的自定義同步器爭(zhēng)用共享資源的方式也不同侵贵。自定義同步器在實(shí)現(xiàn)時(shí)只需要實(shí)現(xiàn)共享資源state的獲取與釋放方式即可，至于具體線程等待隊(duì)列的維護(hù)（如獲取資源失敗入隊(duì)/喚醒出隊(duì)等）缘薛，AQS已經(jīng)在頂層實(shí)現(xiàn)好了窍育。自定義同步器實(shí)現(xiàn)時(shí)主要實(shí)現(xiàn)以下幾種方法：

• isHeldExclusively()：該線程是否正在獨(dú)占資源。只有用到condition才需要去實(shí)現(xiàn)它宴胧。

• tryAcquire(int)：獨(dú)占方式漱抓。嘗試獲取資源，成功則返回true恕齐，失敗則返回false乞娄。

• tryRelease(int)：獨(dú)占方式。嘗試釋放資源，成功則返回true仪或，失敗則返回false确镊。

• tryAcquireShared(int)：共享方式。嘗試獲取資源范删。負(fù)數(shù)表示失斃儆颉；0表示成功到旦，但沒(méi)有剩余可用資源旨巷；正數(shù)表示成功，且有剩余資源添忘。

• tryReleaseShared(int)：共享方式采呐。嘗試釋放資源，成功則返回true搁骑，失敗則返回false斧吐。

一般來(lái)說(shuō)，自定義同步器要么是獨(dú)占方法仲器，要么是共享方式煤率，他們也只需實(shí)現(xiàn)tryAcquire-tryRelease、tryAcquireShared-tryReleaseShared中的一種即可娄周。但AQS也支持自定義同步器同時(shí)實(shí)現(xiàn)獨(dú)占和共享兩種方式涕侈，如ReentrantReadWriteLock沪停。

以ReentrantLock為例煤辨，state初始化為0，表示未鎖定狀態(tài)木张。A線程lock()時(shí)众辨，會(huì)調(diào)用tryAcquire()獨(dú)占該鎖并將state+1。此后舷礼，其他線程再tryAcquire()時(shí)就會(huì)失敗鹃彻，直到A線程unlock()到state=0（即釋放鎖）為止，其它線程才有機(jī)會(huì)獲取該鎖妻献。當(dāng)然蛛株，釋放鎖之前，A線程自己是可以重復(fù)獲取此鎖的（state會(huì)累加）育拨，這就是可重入的概念谨履。但要注意，獲取多少次就要釋放多么次熬丧，這樣才能保證state是能回到零態(tài)的笋粟。

再以CountDownLatch以例，任務(wù)分為N個(gè)子線程去執(zhí)行，state也初始化為N（注意N要與線程個(gè)數(shù)一致）害捕。這N個(gè)子線程是并行執(zhí)行的绿淋，每個(gè)子線程執(zhí)行完后countDown()一次，state會(huì)CAS減1尝盼。等到所有子線程都執(zhí)行完后(即state=0)吞滞，會(huì)unpark()主調(diào)用線程，然后主調(diào)用線程就會(huì)從await()函數(shù)返回东涡，繼續(xù)后余動(dòng)作冯吓。

兩個(gè)重要的狀態(tài)

1. AQS的state

state可以理解有多少線程獲取了資源,即有多少線程獲取了鎖,初始時(shí)state=0表示沒(méi)有線程獲取鎖。

獨(dú)占鎖時(shí),這個(gè)值通常為1或者0疮跑，如果獨(dú)占鎖可重入時(shí),即一個(gè)線程可以多次獲取這個(gè)鎖時(shí),每獲取一次,state就加1组贺。一旦有線程想要獲得鎖,就可以通過(guò)對(duì)state進(jìn)行CAS增量操作,即原子性的增加state的值，其他線程發(fā)現(xiàn)state不為0,這時(shí)線程已經(jīng)不能獲得鎖(獨(dú)占鎖),就會(huì)進(jìn)入AQS的隊(duì)列中等待祖娘。釋放鎖是仍然是通過(guò)CAS來(lái)減小state的值,如果減小到0就表示鎖完全釋放(獨(dú)占鎖)

Node 中的waitStatus

Node的正常狀態(tài)是0失尖。對(duì)于處在隊(duì)列中的節(jié)點(diǎn)來(lái)說(shuō),前一個(gè)節(jié)點(diǎn)有喚醒后一個(gè)節(jié)點(diǎn)的任務(wù)，所以對(duì)與當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)來(lái)說(shuō)渐苏，如果waitStatus > 0, 則節(jié)點(diǎn)處于cancel狀態(tài),應(yīng)踢出隊(duì)列掀潮，如果waitStatus = 0, 則將waitStatus改為-1(signal)。因此隊(duì)列中節(jié)點(diǎn)的狀態(tài)應(yīng)該為-1,-1,-1,0

2.2 源碼詳解

acquire(int)

此方法是獨(dú)占模式下線程獲取共享資源的頂層入口琼富。如果獲取到資源仪吧，線程直接返回，否則進(jìn)入等待隊(duì)列鞠眉，直到獲取到資源為止薯鼠，且整個(gè)過(guò)程忽略中斷的影響。這也正是lock()的語(yǔ)義械蹋，當(dāng)然不僅僅只限于lock()出皇。獲取到資源后，線程就可以去執(zhí)行其臨界區(qū)代碼了哗戈。下面是acquire()的源碼：

public final void acquire(int arg) {
    if (!tryAcquire(arg) &&
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
    selfInterrupt();
}

函數(shù)流程如下：

1. 調(diào)用自定義同步器的tryAcquire()嘗試直接去獲取資源郊艘，如果成功則直接返回

2. 沒(méi)成功，則addWaiter()將該線程加入等待隊(duì)列的尾部唯咬，并標(biāo)記為獨(dú)占模式

3. acquireQueued()使線程在等待隊(duì)列中休息纱注，有機(jī)會(huì)時(shí)（輪到自己，會(huì)被unpark()）會(huì)去嘗試獲取資源胆胰。獲取到資源后才返回狞贱。如果在整個(gè)等待過(guò)程中被中斷過(guò)，則返回true煮剧，否則返回false

4. 如果線程在等待過(guò)程中被中斷過(guò)斥滤，它是不響應(yīng)的将鸵。只是獲取資源后才再進(jìn)行自我中斷selfInterrupt()，將中斷補(bǔ)上

流程圖：

image

release(int)

此方法是獨(dú)占模式下線程釋放共享資源的頂層入口佑颇。它會(huì)釋放指定量的資源顶掉，如果徹底釋放了（即state=0）,它會(huì)喚醒等待隊(duì)列里的其他線程來(lái)獲取資源。這也正是unlock()的語(yǔ)義挑胸，當(dāng)然不僅僅只限于unlock()痒筒。下面是release()的源碼：

public final boolean release(int arg) {
    if (tryRelease(arg)) {
        Node h = head;//找到頭結(jié)點(diǎn)
        if (h != null && h.waitStatus != 0)
            unparkSuccessor(h);//喚醒等待隊(duì)列里的下一個(gè)線程
        return true;
    }
    return false;
}

release()是根據(jù)tryRelease()的返回值來(lái)判斷該線程是否已經(jīng)完成釋放掉資源了，如果已經(jīng)徹底釋放資源(state=0)茬贵，要返回true簿透，否則返回false。

acquireShared(int)

此方法是共享模式下線程獲取共享資源的頂層入口解藻。它會(huì)獲取指定量的資源老充，獲取成功則直接返回，獲取失敗則進(jìn)入等待隊(duì)列螟左，直到獲取到資源為止啡浊，整個(gè)過(guò)程忽略中斷。下面是acquireShared()的源碼：

public final void acquireShared(int arg) {
    if (tryAcquireShared(arg) < 0)
        doAcquireShared(arg);
}

這里tryAcquireShared()依然需要自定義同步器去實(shí)現(xiàn)胶背。但是AQS已經(jīng)把其返回值的語(yǔ)義定義好了：負(fù)值代表獲取失斚锵；0代表獲取成功钳吟，但沒(méi)有剩余資源廷粒；正數(shù)表示獲取成功，還有剩余資源红且，其他線程還可以去獲取坝茎。所以這里acquireShared()的流程就是：

1. tryAcquireShared()嘗試獲取資源，成功則直接返回直焙。

2. 失敗則通過(guò)doAcquireShared()進(jìn)入等待隊(duì)列park()川背，直到被unpark()/interrupt()并成功獲取到資源才返回具被。整個(gè)等待過(guò)程也是忽略中斷的。

跟獨(dú)占模式比站粟，還有一點(diǎn)需要注意的是：當(dāng)前線程獲取資源成功后搔涝，如果還有剩余資源厨喂，那么還會(huì)喚醒后面的線程來(lái)嘗試獲取資源。

releaseShared()

此方法是共享模式下線程釋放共享資源的頂層入口庄呈。它會(huì)釋放指定量的資源蜕煌，如果徹底釋放了（即state=0）,它會(huì)喚醒等待隊(duì)列里的其他線程來(lái)獲取資源。下面是releaseShared()的源碼：

public final boolean releaseShared(int arg) {
    if (tryReleaseShared(arg)) {//嘗試釋放資源
        doReleaseShared();//喚醒后繼結(jié)點(diǎn)
        return true;
    }
    return false;
}

跟獨(dú)占模式下的release()相似诬留，但有一點(diǎn)稍微需要注意：獨(dú)占模式下的tryRelease()在完全釋放掉資源（state=0）后斜纪，才會(huì)返回true去喚醒其他線程贫母，這主要是基于可重入的考量；而共享模式下的releaseShared()則沒(méi)有這種要求盒刚，一是共享的實(shí)質(zhì)--多線程可并發(fā)執(zhí)行腺劣；二是共享模式基本也不會(huì)重入吧（至少我還沒(méi)見(jiàn)過(guò)），所以自定義同步器可以根據(jù)需要決定返回值因块。