1.CAS原理

概述
CAS（Compare-and-Swap），即比較并替換，是一種實(shí)現(xiàn)并發(fā)算法時(shí)常用到的技術(shù)，Java并發(fā)包中的很多類都使用了CAS技術(shù)。CAS也是現(xiàn)在面試經(jīng)常問(wèn)的問(wèn)題，本文將深入的介紹CAS的原理。

CAS指令執(zhí)行時(shí)，當(dāng)且僅當(dāng)內(nèi)存地址V的值與預(yù)期值A(chǔ)相等時(shí)，將內(nèi)存地址V的值修改為B，否則就什么都不做。整個(gè)比較并替換的操作是一個(gè)原子操作。

AutomicIntege.incrementAndGet()方法如下:

    /**
     * Atomically increments by one the current value.
     *
     * @return the updated value
     */
    public final int incrementAndGet() {
        return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
    }

getAndAddInt方法解析：拿到內(nèi)存位置的最新值v，使用CAS嘗試修將內(nèi)存位置的值修改為目標(biāo)值v+delta，如果修改失敗，則獲取該內(nèi)存位置的新值v，然后繼續(xù)嘗試，直至修改成功。

    public final int getAndAddInt(Object var1, long var2, int var4) {
        int var5;
        do {
            var5 = this.getIntVolatile(var1, var2);
        } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

        return var5;
    }

源碼分析

上面源碼分析時(shí)，提到最后調(diào)用了compareAndSwapInt方法，接著繼續(xù)深入探討該方法，該方法在Unsafe中對(duì)應(yīng)的源碼如下。

image

可以看到調(diào)用了“Atomic::cmpxchg”方法，“Atomic::cmpxchg”方法在linux_x86和windows_x86的實(shí)現(xiàn)如下。

linux_x86的實(shí)現(xiàn)：

image

windows_x86的實(shí)現(xiàn)：

image

Atomic::cmpxchg方法解析：

mp是“os::is_MP()”的返回結(jié)果，“os::is_MP()”是一個(gè)內(nèi)聯(lián)函數(shù)，用來(lái)判斷當(dāng)前系統(tǒng)是否為多處理器。

1. 如果當(dāng)前系統(tǒng)是多處理器，該函數(shù)返回1。
2. 否則，返回0。

LOCK_IF_MP(mp)會(huì)根據(jù)mp的值來(lái)決定是否為cmpxchg指令添加lock前綴。

1. 如果通過(guò)mp判斷當(dāng)前系統(tǒng)是多處理器（即mp值為1），則為cmpxchg指令添加lock前綴。
   lock cmpxchg
2. 否則，不加lock前綴。

這是一種優(yōu)化手段，認(rèn)為單處理器的環(huán)境沒(méi)有必要添加lock前綴，只有在多核情況下才會(huì)添加lock前綴，因?yàn)閘ock會(huì)導(dǎo)致性能下降。cmpxchg是匯編指令，作用是比較并交換操作數(shù)。

intel手冊(cè)對(duì)lock前綴的說(shuō)明如下：

• 確保對(duì)內(nèi)存的讀-改-寫(xiě)操作原子執(zhí)行。在Pentium及Pentium之前的處理器中，帶有l(wèi)ock前綴的指令在執(zhí)行期間會(huì)鎖住總線，使得其他處理器暫時(shí)無(wú)法通過(guò)總線訪問(wèn)內(nèi)存。很顯然，這會(huì)帶來(lái)昂貴的開(kāi)銷。從Pentium 4，Intel Xeon及P6處理器開(kāi)始，intel在原有總線鎖的基礎(chǔ)上做了一個(gè)很有意義的優(yōu)化：如果要訪問(wèn)的內(nèi)存區(qū)域（area of memory）在lock前綴指令執(zhí)行期間已經(jīng)在處理器內(nèi)部的緩存中被鎖定（即包含該內(nèi)存區(qū)域的緩存行當(dāng)前處于獨(dú)占或以修改狀態(tài)），并且該內(nèi)存區(qū)域被完全包含在單個(gè)緩存行（cache line）中，那么處理器將直接執(zhí)行該指令。由于在指令執(zhí)行期間該緩存行會(huì)一直被鎖定，其它處理器無(wú)法讀/寫(xiě)該指令要訪問(wèn)的內(nèi)存區(qū)域，因此能保證指令執(zhí)行的原子性。這個(gè)操作過(guò)程叫做緩存鎖定（cache locking），緩存鎖定將大大降低lock前綴指令的執(zhí)行開(kāi)銷，但是當(dāng)多處理器之間的競(jìng)爭(zhēng)程度很高或者指令訪問(wèn)的內(nèi)存地址未對(duì)齊時(shí)，仍然會(huì)鎖住總線。
• 禁止該指令與之前和之后的讀和寫(xiě)指令重排序。
• 把寫(xiě)緩沖區(qū)中的所有數(shù)據(jù)刷新到內(nèi)存中。

上面的第1點(diǎn)保證了CAS操作是一個(gè)原子操作，第2點(diǎn)和第3點(diǎn)所具有的內(nèi)存屏障效果，保證了CAS同時(shí)具有volatile讀和volatile寫(xiě)的內(nèi)存語(yǔ)義。

CAS的缺點(diǎn)：

CAS雖然很高效的解決了原子操作問(wèn)題，但是CAS仍然存在三大問(wèn)題。

1. 循環(huán)時(shí)間長(zhǎng)開(kāi)銷很大。
2. 只能保證一個(gè)共享變量的原子操作。
3. ABA問(wèn)題。

循環(huán)時(shí)間長(zhǎng)開(kāi)銷很大：我們可以看到getAndAddInt方法執(zhí)行時(shí)，如果CAS失敗，會(huì)一直進(jìn)行嘗試。如果CAS長(zhǎng)時(shí)間一直不成功，可能會(huì)給CPU帶來(lái)很大的開(kāi)銷。

只能保證一個(gè)共享變量的原子操作：當(dāng)對(duì)一個(gè)共享變量執(zhí)行操作時(shí)，我們可以使用循環(huán)CAS的方式來(lái)保證原子操作，但是對(duì)多個(gè)共享變量操作時(shí)，循環(huán)CAS就無(wú)法保證操作的原子性，這個(gè)時(shí)候就可以用鎖來(lái)保證原子性。

什么是ABA問(wèn)題？ABA問(wèn)題怎么解決？

如果內(nèi)存地址V初次讀取的值是A，并且在準(zhǔn)備賦值的時(shí)候檢查到它的值仍然為A，那我們就能說(shuō)它的值沒(méi)有被其他線程改變過(guò)了嗎？

如果在這段期間它的值曾經(jīng)被改成了B，后來(lái)又被改回為A，那CAS操作就會(huì)誤認(rèn)為它從來(lái)沒(méi)有被改變過(guò)。這個(gè)漏洞稱為CAS操作的“ABA”問(wèn)題。Java并發(fā)包為了解決這個(gè)問(wèn)題，提供了一個(gè)帶有標(biāo)記的原子引用類“AtomicStampedReference”，它可以通過(guò)控制變量值的版本來(lái)保證CAS的正確性。因此，在使用CAS前要考慮清楚“ABA”問(wèn)題是否會(huì)影響程序并發(fā)的正確性，如果需要解決ABA問(wèn)題，改用傳統(tǒng)的互斥同步可能會(huì)比原子類更高效。

轉(zhuǎn)公眾號(hào)：JoonWhee，Java原創(chuàng)知識(shí)交流，優(yōu)秀技術(shù)文章、職場(chǎng)人生、面試經(jīng)驗(yàn)分享。

2.Synchronized原理

在 Java 中，關(guān)鍵字 synchronized可以保證在同一個(gè)時(shí)刻，只有一個(gè)線程可以執(zhí)行某個(gè)方法或者某個(gè)代碼塊(主要是對(duì)方法或者代碼塊中存在共享數(shù)據(jù)的操作)，同時(shí)我們還應(yīng)該注意到synchronized另外一個(gè)重要的作用，synchronized可保證一個(gè)線程的變化(主要是共享數(shù)據(jù)的變化)被其他線程所看到（保證可見(jiàn)性，完全可以替代Volatile功能），這點(diǎn)確實(shí)也是很重要的。

2.1使用的三種形式

• 對(duì)于普通同步方法，鎖是當(dāng)前實(shí)例對(duì)象。
• 對(duì)于靜態(tài)同步方法，鎖是當(dāng)前類的Class對(duì)象。
• 對(duì)于同步方法塊，鎖是Synchonized括號(hào)里配置的對(duì)象。

2.2字節(jié)碼

monitorenter、monitorexit
從JVM規(guī)范中可以看到Synchonized在JVM里的實(shí)現(xiàn)原理，JVM基于進(jìn)入和退出Monitor對(duì) 象來(lái)實(shí)現(xiàn)方法同步和代碼塊同步，但兩者的實(shí)現(xiàn)細(xì)節(jié)不一樣。代碼塊同步是使用monitorenter 和monitorexit指令實(shí)現(xiàn)的，而方法同步是使用另外一種方式實(shí)現(xiàn)的，細(xì)節(jié)在JVM規(guī)范里并沒(méi)有 詳細(xì)說(shuō)明。但是，方法的同步同樣可以使用這兩個(gè)指令來(lái)實(shí)現(xiàn)。
monitorenter指令是在編譯后插入到同步代碼塊的開(kāi)始位置，而monitorexit是插入到方法結(jié) 束處和異常處，JVM要保證每個(gè)monitorenter必須有對(duì)應(yīng)的monitorexit與之配對(duì)。任何對(duì)象都有 一個(gè)monitor與之關(guān)聯(lián)，當(dāng)且一個(gè)monitor被持有后，它將處于鎖定狀態(tài)。線程執(zhí)行到monitorenter 指令時(shí)，將會(huì)嘗試獲取對(duì)象所對(duì)應(yīng)的monitor的所有權(quán)，即嘗試獲得對(duì)象的鎖。

2.3原理

2.3.1 Java對(duì)象內(nèi)存分布

Java對(duì)象內(nèi)存分布

JVM對(duì)于普通對(duì)象和數(shù)組對(duì)象的大小計(jì)算方式有所不同，我畫(huà)了一張圖說(shuō)明：

image

解釋一下其中每個(gè)部分：

1. Mark Word：存儲(chǔ)對(duì)象運(yùn)行時(shí)記錄信息，占用內(nèi)存大小與機(jī)器位數(shù)一樣，即32位機(jī)占4字節(jié)，64位機(jī)占8字節(jié)
2. 元數(shù)據(jù)指針：指向描述類型的Class對(duì)象（Java類的C++對(duì)等體）的指針，Class對(duì)象包含了實(shí)例對(duì)象所屬類型的元數(shù)據(jù)，因此該字段被稱為元數(shù)據(jù)指針，JVM在運(yùn)行時(shí)將頻繁使用這個(gè)指針定位到位于方法區(qū)內(nèi)的類型信息。
3. 數(shù)組長(zhǎng)度：數(shù)組對(duì)象特有，一個(gè)指向int型的引用類型，用于描述數(shù)組長(zhǎng)度，這個(gè)數(shù)據(jù)的大小和元數(shù)據(jù)指針大小相同。
4. 實(shí)例數(shù)據(jù)：實(shí)例數(shù)據(jù)就是8大基本數(shù)據(jù)類型byte、short、int、long、float、double、char、boolean（對(duì)象類型也是由這8大基本數(shù)據(jù)類型復(fù)合而成），每種數(shù)據(jù)類型占多少字節(jié)就不一一例舉了
5. 填充：不定，HotSpot的對(duì)齊方式為8字節(jié)對(duì)齊，即一個(gè)對(duì)象必須為8字節(jié)的整數(shù)倍，因此如果最后前面的數(shù)據(jù)大小為17則填充7，前面的數(shù)據(jù)大小為18則填充6，以此類推

2.3.2 Mark Word

Java對(duì)象頭里的Mark Word里默認(rèn)存儲(chǔ)對(duì)象的HashCode、分代年齡和鎖標(biāo)記位。32位JVM 的Mark Word的默認(rèn)存儲(chǔ)結(jié)構(gòu)如:

image.png

在運(yùn)行期間，Mark Word里存儲(chǔ)的數(shù)據(jù)會(huì)隨著鎖標(biāo)志位的變化而變化。Mark Word可能變 化為存儲(chǔ)以下4種數(shù)據(jù):

image.png

image.png

2.3.3鎖的升級(jí)

整體的鎖升級(jí)過(guò)程如下：

image.png

image.png

無(wú)鎖：

無(wú)鎖沒(méi)有對(duì)資源進(jìn)行鎖定，所有的線程都能訪問(wèn)并修改同一個(gè)資源，但同時(shí)只有一個(gè)線程能修改成功。
無(wú)鎖的特點(diǎn)就是修改操作在循環(huán)內(nèi)進(jìn)行，線程會(huì)不斷的嘗試修改共享資源。如果沒(méi)有沖突就修改成功并退出，否則就會(huì)繼續(xù)循環(huán)嘗試。如果有多個(gè)線程修改同一個(gè)值，必定會(huì)有一個(gè)線程能修改成功，而其他修改失敗的線程會(huì)不斷重試直到修改成功。上面我們介紹的CAS原理及應(yīng)用即是無(wú)鎖的實(shí)現(xiàn)。無(wú)鎖無(wú)法全面代替有鎖，但無(wú)鎖在某些場(chǎng)合下的性能是非常高的。

偏向鎖

偏向鎖是指一段同步代碼一直被一個(gè)線程所訪問(wèn)，那么該線程會(huì)自動(dòng)獲取鎖，降低獲取鎖的代價(jià)。
在大多數(shù)情況下，鎖總是由同一線程多次獲得，不存在多線程競(jìng)爭(zhēng)，所以出現(xiàn)了偏向鎖。其目標(biāo)就是在只有一個(gè)線程執(zhí)行同步代碼塊時(shí)能夠提高性能。

當(dāng)一個(gè)線程訪問(wèn)同步代碼塊并獲取鎖時(shí)，會(huì)在對(duì)象頭MarkWord和棧幀中的鎖記錄里存儲(chǔ)鎖偏向的線程ID里存儲(chǔ)鎖偏向的線程ID。在線程進(jìn)入和退出同步塊時(shí)不再通過(guò)CAS操作來(lái)加鎖和解鎖，而是檢測(cè)Mark Word里是否存儲(chǔ)著指向當(dāng)前線程的偏向鎖。引入偏向鎖是為了在無(wú)多線程競(jìng)爭(zhēng)的情況下盡量減少不必要的輕量級(jí)鎖執(zhí)行路徑，因?yàn)檩p量級(jí)鎖的獲取及釋放依賴多次CAS原子指令，而偏向鎖只需要在置換ThreadID的時(shí)候依賴一次CAS原子指令即可。

1.偏向鎖的撤銷
偏向鎖只有遇到其他線程嘗試競(jìng)爭(zhēng)偏向鎖時(shí)，持有偏向鎖的線程才會(huì)釋放鎖，線程不會(huì)主動(dòng)釋放偏向鎖。偏向鎖的撤銷，需要等待全局安全點(diǎn)（在這個(gè)時(shí)間點(diǎn)上沒(méi)有字節(jié)碼正在執(zhí)行），它會(huì)首先暫停擁有偏向鎖的線程，判斷鎖對(duì)象是否處于被鎖定狀態(tài)。撤銷偏向鎖后恢復(fù)到無(wú)鎖（標(biāo)志位為“01”）或輕量級(jí)鎖（標(biāo)志位為“00”）的狀態(tài)。
2.偏向鎖的關(guān)閉
偏向鎖在JDK 6及以后的JVM里是默認(rèn)啟用的。可以通過(guò)JVM參數(shù)關(guān)閉偏向鎖：-XX:-UseBiasedLocking=false，關(guān)閉之后程序默認(rèn)會(huì)進(jìn)入輕量級(jí)鎖狀態(tài)。

輕量級(jí)鎖

是指當(dāng)鎖是偏向鎖的時(shí)候，被另外的線程所訪問(wèn)，偏向鎖就會(huì)升級(jí)為輕量級(jí)鎖，其他線程會(huì)通過(guò)自旋的形式嘗試獲取鎖，不會(huì)阻塞，從而提高性能。

在代碼進(jìn)入同步塊的時(shí)候，如果同步對(duì)象鎖狀態(tài)為無(wú)鎖狀態(tài)（鎖標(biāo)志位為“01”狀態(tài)，是否為偏向鎖為“0”），虛擬機(jī)首先將在當(dāng)前線程的棧幀中建立一個(gè)名為鎖記錄（Lock Record）的空間，用于存儲(chǔ)鎖對(duì)象目前的Mark Word的拷貝，然后拷貝對(duì)象頭中的Mark Word復(fù)制到鎖記錄中。

拷貝成功后，虛擬機(jī)將使用CAS操作嘗試將對(duì)象的Mark Word更新為指向Lock Record的指針，并將Lock Record里的owner指針指向?qū)ο蟮腗ark Word。

如果這個(gè)更新動(dòng)作成功了，那么這個(gè)線程就擁有了該對(duì)象的鎖，并且對(duì)象Mark Word的鎖標(biāo)志位設(shè)置為“00”，表示此對(duì)象處于輕量級(jí)鎖定狀態(tài)。

如果輕量級(jí)鎖的更新操作失敗了，虛擬機(jī)首先會(huì)檢查對(duì)象的Mark Word是否指向當(dāng)前線程的棧幀，如果是就說(shuō)明當(dāng)前線程已經(jīng)擁有了這個(gè)對(duì)象的鎖，那就可以直接進(jìn)入同步塊繼續(xù)執(zhí)行，否則說(shuō)明多個(gè)線程競(jìng)爭(zhēng)鎖。

若當(dāng)前只有一個(gè)等待線程，則該線程通過(guò)自旋進(jìn)行等待。但是當(dāng)自旋超過(guò)一定的次數(shù)（10次），或者一個(gè)線程在持有鎖，一個(gè)在自旋，又有第三個(gè)來(lái)訪時(shí)，輕量級(jí)鎖升級(jí)為重量級(jí)鎖。

重量級(jí)鎖

級(jí)為重量級(jí)鎖時(shí)，鎖標(biāo)志的狀態(tài)值變?yōu)椤?0”，此時(shí)Mark Word中存儲(chǔ)的是指向重量級(jí)鎖的指針，這時(shí)要向操作系統(tǒng)申請(qǐng)申請(qǐng)系統(tǒng)資源，mutex互斥量。此時(shí)等待鎖的線程都會(huì)進(jìn)入阻塞狀態(tài)。
綜上，偏向鎖通過(guò)對(duì)比Mark Word解決加鎖問(wèn)題，避免執(zhí)行CAS操作。而輕量級(jí)鎖是通過(guò)用CAS操作和自旋來(lái)解決加鎖問(wèn)題，避免線程阻塞和喚醒而影響性能。重量級(jí)鎖是將除了擁有鎖的線程以外的線程都阻塞。

3.Volatile關(guān)鍵字詳解