在JDK 5之前Java語(yǔ)言是靠synchronized關(guān)鍵字保證同步的,這會(huì)導(dǎo)致有鎖
鎖機(jī)制存在以下問(wèn)題:
(1)在多線程競(jìng)爭(zhēng)下浇坐,加鎖冰肴、釋放鎖會(huì)導(dǎo)致比較多的上下文切換和調(diào)度延時(shí),引起性能問(wèn)題奶赠。
(2)一個(gè)線程持有鎖會(huì)導(dǎo)致其它所有需要此鎖的線程掛起鱼填。
(3)如果一個(gè)優(yōu)先級(jí)高的線程等待一個(gè)優(yōu)先級(jí)低的線程釋放鎖會(huì)導(dǎo)致優(yōu)先級(jí)倒置,引起性能風(fēng)險(xiǎn)毅戈。
volatile是不錯(cuò)的機(jī)制苹丸,但是volatile不能保證原子性。因此對(duì)于同步最終還是要回到鎖機(jī)制上來(lái)苇经。
獨(dú)占鎖是一種悲觀鎖赘理,synchronized就是一種獨(dú)占鎖,會(huì)導(dǎo)致其它所有需要鎖的線程掛起扇单,等待持有鎖的線程釋放鎖商模。而另一個(gè)更加有效的鎖就是樂(lè)觀鎖。所謂樂(lè)觀鎖就是,每次不加鎖而是假設(shè)沒(méi)有沖突而去完成某項(xiàng)操作施流,如果因?yàn)闆_突失敗就重試凉倚,直到成功為止。樂(lè)觀鎖用到的機(jī)制就是CAS嫂沉,Compare and Swap稽寒。
一、什么是CAS
CAS:compare and swap的縮寫趟章,中文翻譯成比較并交換杏糙。
我們都知道,在java語(yǔ)言之前蚓土,并發(fā)就已經(jīng)廣泛存在并在服務(wù)器領(lǐng)域得到了大量的應(yīng)用宏侍。所以硬件廠商老早就在芯片中加入了大量直至并發(fā)操作的原語(yǔ),從而在硬件層面提升效率蜀漆。在intel的CPU中谅河,使用cmpxchg指令。
在Java發(fā)展初期确丢,java語(yǔ)言是不能夠利用硬件提供的這些便利來(lái)提升系統(tǒng)的性能的绷耍。而隨著java不斷的發(fā)展,Java本地方法(JNI)的出現(xiàn),使得java程序越過(guò)JVM直接調(diào)用本地方法提供了一種便捷的方式鲜侥,因而java在并發(fā)的手段上也多了起來(lái)褂始。而在Doug Lea提供的cucurenct包中,CAS理論是它實(shí)現(xiàn)整個(gè)java包的基石描函。
CAS 操作包含三個(gè)操作數(shù) —— 內(nèi)存位置(V)崎苗、預(yù)期原值(A)和新值(B)。 如果內(nèi)存位置的值與預(yù)期原值相匹配舀寓,那么處理器會(huì)自動(dòng)將該位置值更新為新值 胆数。否則,處理器不做任何操作互墓。無(wú)論哪種情況必尼,它都會(huì)在 CAS 指令之前返回該 位置的值。(在 CAS 的一些特殊情況下將僅返回 CAS 是否成功轰豆,而不提取當(dāng)前 值胰伍。)CAS 有效地說(shuō)明了“我認(rèn)為位置 V 應(yīng)該包含值 A;如果包含該值酸休,則將 B 放到這個(gè)位置骂租;否則,不要更改該位置斑司,只告訴我這個(gè)位置現(xiàn)在的值即可渗饮〉”
通常將 CAS 用于同步的方式是從地址 V 讀取值 A,執(zhí)行多步計(jì)算來(lái)獲得新 值 B互站,然后使用 CAS 將 V 的值從 A 改為 B私蕾。如果 V 處的值尚未同時(shí)更改,則 CAS 操作成功胡桃。
類似于 CAS 的指令允許算法執(zhí)行讀-修改-寫操作踩叭,而無(wú)需害怕其他線程同時(shí) 修改變量,因?yàn)槿绻渌€程修改變量翠胰,那么 CAS 會(huì)檢測(cè)它(并失斎荼础),算法 可以對(duì)該操作重新計(jì)算之景。
二斤富、CAS的應(yīng)用
利用CPU的CAS指令,同時(shí)借助JNI來(lái)完成Java的非阻塞算法锻狗。其它原子操作都是利用類似的特性完成的满力。而整個(gè)J.U.C都是建立在CAS之上的,因此對(duì)于synchronized阻塞算法轻纪,J.U.C在性能上有了很大的提升油额。
2.1 非阻塞算法 (nonblocking algorithms)
一個(gè)線程的失敗或者掛起不應(yīng)該影響其他線程的失敗或掛起的算法。
現(xiàn)代的CPU提供了特殊的指令桐磁,可以自動(dòng)更新共享數(shù)據(jù)悔耘,而且能夠檢測(cè)到其他線程的干擾,而 compareAndSet() 就用這些代替了鎖定我擂。
拿出AtomicInteger來(lái)研究在沒(méi)有鎖的情況下是如何做到數(shù)據(jù)正確性的。
private volatile int value;
首先毫無(wú)以為缓艳,在沒(méi)有鎖的機(jī)制下可能需要借助volatile原語(yǔ)校摩,保證線程間的數(shù)據(jù)是可見(jiàn)的(共享的)。
這樣才獲取變量的值的時(shí)候才能直接讀取阶淘。
public final int get() {
return value;
}
然后來(lái)看看++i是怎么做到的衙吩。
public final int incrementAndGet() {
for (;;) {
int current = get();
int next = current + 1;
if (compareAndSet(current, next))
return next;
}
}
在這里采用了CAS操作,每次從內(nèi)存中讀取數(shù)據(jù)然后將此數(shù)據(jù)和+1后的結(jié)果進(jìn)行CAS操作溪窒,如果成功就返回結(jié)果坤塞,否則重試直到成功為止。
而compareAndSet利用JNI來(lái)完成CPU指令的操作澈蚌。
public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
整體的過(guò)程就是這樣子的摹芙,利用CPU的CAS指令,同時(shí)借助JNI來(lái)完成Java的非阻塞算法宛瞄。其它原子操作都是利用類似的特性完成的浮禾。
其中
unsafe.compareAndSwapInt(this, valueOffset, expect, update);
類似:
if (this == expect) {
this = update
return true;
} else {
return false;
}
那么問(wèn)題就來(lái)了,成功過(guò)程中需要2個(gè)步驟:比較this == expect,替換this = update盈电,compareAndSwapInt如何這兩個(gè)步驟的原子性呢蝴簇? 參考CAS的原理。
三匆帚、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);
可以看到這是個(gè)本地方法調(diào)用晤锹。這個(gè)本地方法在openjdk中依次調(diào)用的c++代碼為:unsafe.cpp摩幔,atomic.cpp和atomicwindowsx86.inline.hpp。這個(gè)本地方法的最終實(shí)現(xiàn)在openjdk的如下位置:openjdk-7-fcs-src-b147-27jun2011\openjdk\hotspot\src\oscpu\windowsx86\vm\ atomicwindowsx86.inline.hpp(對(duì)應(yīng)于windows操作系統(tǒng)鞭铆,X86處理器)或衡。下面是對(duì)應(yīng)于intel x86處理器的源代碼的片段:
// Adding a lock prefix to an instruction on MP machine
// VC++ doesn't like the lock prefix to be on a single line
// so we can't insert a label after the lock prefix.
// By emitting a lock prefix, we can define a label after it.
#define LOCK_IF_MP(mp) __asm cmp mp, 0 \
__asm je L0 \
__asm _emit 0xF0 \
__asm L0:
inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
// alternative for InterlockedCompareExchange
int mp = os::is_MP();
__asm {
mov edx, dest
mov ecx, exchange_value
mov eax, compare_value
LOCK_IF_MP(mp)
cmpxchg dword ptr [edx], ecx
}
}
如上面源代碼所示,程序會(huì)根據(jù)當(dāng)前處理器的類型來(lái)決定是否為cmpxchg指令添加lock前綴车遂。如果程序是在多處理器上運(yùn)行封断,就為cmpxchg指令加上lock前綴(lock cmpxchg)。反之舶担,如果程序是在單處理器上運(yùn)行坡疼,就省略lock前綴(單處理器自身會(huì)維護(hù)單處理器內(nèi)的順序一致性,不需要lock前綴提供的內(nèi)存屏障效果)衣陶。
intel的手冊(cè)對(duì)lock前綴的說(shuō)明如下:
1.確保對(duì)內(nèi)存的讀-改-寫操作原子執(zhí)行柄瑰。在Pentium及Pentium之前的處理器中,帶有l(wèi)ock前綴的指令在執(zhí)行期間會(huì)鎖住總線剪况,使得其他處理器暫時(shí)無(wú)法通過(guò)總線訪問(wèn)內(nèi)存教沾。很顯然,這會(huì)帶來(lái)昂貴的開銷译断。從Pentium 4授翻,Intel Xeon及P6處理器開始,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ú)法讀/寫該指令要訪問(wèn)的內(nèi)存區(qū)域淮菠,因此能保證指令執(zhí)行的原子性。這個(gè)操作過(guò)程叫做緩存鎖定(cache locking)
杨蛋,緩存鎖定將大大降低lock前綴指令的執(zhí)行開銷兜材,但是當(dāng)多處理器之間的競(jìng)爭(zhēng)程度很高或者指令訪問(wèn)的內(nèi)存地址未對(duì)齊時(shí)理澎,仍然會(huì)鎖住總線。
2. 禁止該指令與之前和之后的讀和寫指令重排序曙寡。
3. 把寫緩沖區(qū)中的所有數(shù)據(jù)刷新到內(nèi)存中糠爬。
關(guān)于CPU的鎖有如下3種:
3.1 處理器自動(dòng)保證基本內(nèi)存操作的原子性
首先處理器會(huì)自動(dòng)保證基本的內(nèi)存操作的原子性。處理器保證從系統(tǒng)內(nèi)存當(dāng)中讀取或者寫入一個(gè)字節(jié)是原子的举庶,意思是當(dāng)一個(gè)處理器讀取一個(gè)字節(jié)時(shí)执隧,其他處理器不能訪問(wèn)這個(gè)字節(jié)的內(nèi)存地址。奔騰6和最新的處理器能自動(dòng)保證單處理器對(duì)同一個(gè)緩存行里進(jìn)行16/32/64位的操作是原子的户侥,但是復(fù)雜的內(nèi)存操作處理器不能自動(dòng)保證其原子性镀琉,比如跨總線寬度,跨多個(gè)緩存行蕊唐,跨頁(yè)表的訪問(wèn)屋摔。但是處理器提供總線鎖定和緩存鎖定兩個(gè)機(jī)制來(lái)保證復(fù)雜內(nèi)存操作的原子性。
3.2 使用總線鎖保證原子性
第一個(gè)機(jī)制是通過(guò)總線鎖保證原子性替梨。如果多個(gè)處理器同時(shí)對(duì)共享變量進(jìn)行讀改寫(i++就是經(jīng)典的讀改寫操作)操作钓试,那么共享變量就會(huì)被多個(gè)處理器同時(shí)進(jìn)行操作,這樣讀改寫操作就不是原子的副瀑,操作完之后共享變量的值會(huì)和期望的不一致弓熏,舉個(gè)例子:如果i=1,我們進(jìn)行兩次i++操作,我們期望的結(jié)果是3糠睡,但是有可能結(jié)果是2挽鞠。如下圖
原因是有可能多個(gè)處理器同時(shí)從各自的緩存中讀取變量i,分別進(jìn)行加一操作狈孔,然后分別寫入系統(tǒng)內(nèi)存當(dāng)中信认。那么想要保證讀改寫共享變量的操作是原子的,就必須保證CPU1讀改寫共享變量的時(shí)候均抽,CPU2不能操作緩存了該共享變量?jī)?nèi)存地址的緩存狮杨。
處理器使用總線鎖就是來(lái)解決這個(gè)問(wèn)題的。所謂總線鎖就是使用處理器提供的一個(gè)LOCK#信號(hào)到忽,當(dāng)一個(gè)處理器在總線上輸出此信號(hào)時(shí),其他處理器的請(qǐng)求將被阻塞住,那么該處理器可以獨(dú)占使用共享內(nèi)存清寇。
3.3 使用緩存鎖保證原子性
第二個(gè)機(jī)制是通過(guò)緩存鎖定保證原子性喘漏。在同一時(shí)刻我們只需保證對(duì)某個(gè)內(nèi)存地址的操作是原子性即可,但總線鎖定把CPU和內(nèi)存之間通信鎖住了华烟,這使得鎖定期間翩迈,其他處理器不能操作其他內(nèi)存地址的數(shù)據(jù),所以總線鎖定的開銷比較大盔夜,最近的處理器在某些場(chǎng)合下使用緩存鎖定代替總線鎖定來(lái)進(jìn)行優(yōu)化负饲。
頻繁使用的內(nèi)存會(huì)緩存在處理器的L1堤魁,L2和L3高速緩存里,那么原子操作就可以直接在處理器內(nèi)部緩存中進(jìn)行返十,并不需要聲明總線鎖妥泉,在奔騰6和最近的處理器中可以使用“緩存鎖定”的方式來(lái)實(shí)現(xiàn)復(fù)雜的原子性。所謂“緩存鎖定”就是如果緩存在處理器緩存行中內(nèi)存區(qū)域在LOCK操作期間被鎖定洞坑,當(dāng)它執(zhí)行鎖操作回寫內(nèi)存時(shí)盲链,處理器不在總線上聲言LOCK#信號(hào),而是修改內(nèi)部的內(nèi)存地址迟杂,并允許它的緩存一致性機(jī)制來(lái)保證操作的原子性刽沾,因?yàn)榫彺嬉恢滦詸C(jī)制會(huì)阻止同時(shí)修改被兩個(gè)以上處理器緩存的內(nèi)存區(qū)域數(shù)據(jù),當(dāng)其他處理器回寫已被鎖定的緩存行的數(shù)據(jù)時(shí)會(huì)起緩存行無(wú)效排拷,在例1中侧漓,當(dāng)CPU1修改緩存行中的i時(shí)使用緩存鎖定,那么CPU2就不能同時(shí)緩存了i的緩存行监氢。
但是有兩種情況下處理器不會(huì)使用緩存鎖定布蔗。第一種情況是:當(dāng)操作的數(shù)據(jù)不能被緩存在處理器內(nèi)部,或操作的數(shù)據(jù)跨多個(gè)緩存行(cache line)忙菠,則處理器會(huì)調(diào)用總線鎖定何鸡。第二種情況是:有些處理器不支持緩存鎖定。對(duì)于Inter486和奔騰處理器,就算鎖定的內(nèi)存區(qū)域在處理器的緩存行中也會(huì)調(diào)用總線鎖定牛欢。
以上兩個(gè)機(jī)制我們可以通過(guò)Inter處理器提供了很多LOCK前綴的指令來(lái)實(shí)現(xiàn)骡男。比如位測(cè)試和修改指令BTS,BTR傍睹,BTC隔盛,交換指令XADD,CMPXCHG和其他一些操作數(shù)和邏輯指令拾稳,比如ADD(加)吮炕,OR(或)等,被這些指令操作的內(nèi)存區(qū)域就會(huì)加鎖访得,導(dǎo)致其他處理器不能同時(shí)訪問(wèn)它龙亲。
四、CAS存在的問(wèn)題
CAS雖然很高效的解決原子操作悍抑,但是CAS仍然存在三大問(wèn)題鳄炉。ABA問(wèn)題,循環(huán)時(shí)間長(zhǎng)開銷大和只能保證一個(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 開始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)開銷大趣些。自旋CAS如果長(zhǎng)時(shí)間不成功,會(huì)給CPU帶來(lái)非常大的執(zhí)行開銷贰您。如果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開始JDK提供了AtomicReference類來(lái)保證引用對(duì)象之間的原子性犬钢,你可以把多個(gè)變量放在一個(gè)對(duì)象里來(lái)進(jìn)行CAS操作。
五思灰、concurrent包的實(shí)現(xiàn)
由于java的CAS同時(shí)具有 volatile 讀和volatile寫的內(nèi)存語(yǔ)義,因此Java線程之間的通信現(xiàn)在有了下面四種方式:
- A線程寫volatile變量混滔,隨后B線程讀這個(gè)volatile變量洒疚。
- A線程寫volatile變量歹颓,隨后B線程用CAS更新這個(gè)volatile變量。
- A線程用CAS更新一個(gè)volatile變量油湖,隨后B線程用CAS更新這個(gè)volatile變量巍扛。
- A線程用CAS更新一個(gè)volatile變量,隨后B線程讀這個(gè)volatile變量乏德。
Java的CAS會(huì)使用現(xiàn)代處理器上提供的高效機(jī)器級(jí)別原子指令撤奸,這些原子指令以原子方式對(duì)內(nèi)存執(zhí)行讀-改-寫操作,這是在多處理器中實(shí)現(xiàn)同步的關(guān)鍵(從本質(zhì)上來(lái)說(shuō)喊括,能夠支持原子性讀-改-寫指令的計(jì)算機(jī)器胧瓜,是順序計(jì)算圖靈機(jī)的異步等價(jià)機(jī)器,因此任何現(xiàn)代的多處理器都會(huì)去支持某種能對(duì)內(nèi)存執(zhí)行原子性讀-改-寫操作的原子指令)郑什。同時(shí)府喳,volatile變量的讀/寫和CAS可以實(shí)現(xiàn)線程之間的通信。把這些特性整合在一起蘑拯,就形成了整個(gè)concurrent包得以實(shí)現(xiàn)的基石钝满。如果我們仔細(xì)分析concurrent包的源代碼實(shí)現(xiàn),會(huì)發(fā)現(xiàn)一個(gè)通用化的實(shí)現(xiàn)模式:
- 首先申窘,聲明共享變量為volatile弯蚜;
- 然后,使用CAS的原子條件更新來(lái)實(shí)現(xiàn)線程之間的同步剃法;
- 同時(shí)碎捺,配合以volatile的讀/寫和CAS所具有的volatile讀和寫的內(nèi)存語(yǔ)義來(lái)實(shí)現(xiàn)線程之間的通信。
AQS玄窝,非阻塞數(shù)據(jù)結(jié)構(gòu)和原子變量類(java.util.concurrent.atomic包中的類)牵寺,這些concurrent包中的基礎(chǔ)類都是使用這種模式來(lái)實(shí)現(xiàn)的,而concurrent包中的高層類又是依賴于這些基礎(chǔ)類來(lái)實(shí)現(xiàn)的恩脂。從整體來(lái)看帽氓,concurrent包的實(shí)現(xiàn)示意圖如下: