引言
原子(atom)本意是“不能被進一步分割的最小粒子”,而原子操作(atomic operation)意為”不可被中斷的一個或一系列操作” 。在多處理器上實現原子操作就變得有點複雜。本文讓我們一起來聊一聊在Inter處理器和Java裡是如何實現原子操作的。
處理器如何實現原子操作
32位IA-32處理器使用基於對緩存加鎖或總線加鎖的方式來實現多處理器之間的原子操作。
1、處理器自動保證基本內存操作的原子性
首先處理器會自動保證基本的內存操作的原子性。處理器保證從系統內存當中讀取或者寫入一個字節是原子的,意思是當一個處理器讀取一個字節時,其他處理器不能訪問這個字節的內存地址。奔騰6和最新的處理器能自動保證單處理器對同一個緩存行裡進行16/32/64位的操作是原子的,但是複雜的內存操作處理器不能自動保證其原子性,比如跨總線寬度,跨多個緩存行,跨頁表的訪問。但是處理器提供總線鎖定和緩存鎖定兩個機制來保證複雜內存操作的原子性。
2、使用總線鎖保證原子性
第一個機制是通過總線鎖保證原子性。如果多個處理器同時對共享變量進行讀改寫(i++就是經典的讀改寫操作)操作,那麼共享變量就會被多個處理器同時進行操作,這樣讀改寫操作就不是原子的,操作完之後共享變量的值會和期望的不一致,舉個例子:如果i=1,我們進行兩次i++操作,我們期望的結果是3,但是有可能結果是2。如下圖所示:
原因是有可能多個處理器同時從各自的緩存中讀取變量i,分別進行加一操作,然後分別寫入系統內存當中。那麼想要保證讀改寫共享變量的操作是原子的,就必須保證CPU1讀改寫共享變量的時候,CPU2不能操作緩存了該共享變量內存地址的緩存。
處理器使用總線鎖就是來解決這個問題的。所謂總線鎖就是使用處理器提供的一個LOCK#信號,當一個處理器在總線上輸出此信號時,其他處理器的請求將被阻塞住,那麼該處理器可以獨佔使用共享內存。
3、使用緩存鎖保證原子性
第二個機制是通過緩存鎖定保證原子性。在同一時刻我們只需保證對某個內存地址的操作是原子性即可,但總線鎖定把CPU和內存之間通信鎖住了,這使得鎖定期間,其他處理器不能操作其他內存地址的數據,所以總線鎖定的開銷比較大,最近的處理器在某些場合下使用緩存鎖定代替總線鎖定來進行優化。
頻繁使用的內存會緩存在處理器的L1,L2和L3高速緩存裡,那麼原子操作就可以直接在處理器內部緩存中進行,並不需要聲明總線鎖,在奔騰6和最近的處理器中可以使用“緩存鎖定”的方式來實現複雜的原子性。所謂“緩存鎖定”就是如果緩存在處理器緩存行中內存區域在LOCK操作期間被鎖定,當它執行鎖操作回寫內存時,處理器不在總線上聲言LOCK#信號,而是修改內部的內存地址,並允許它的緩存一致性機制來保證操作的原子性,因為緩存一致性機制會阻止同時修改被兩個以上處理器緩存的內存區域數據,當其他處理器回寫已被鎖定的緩存行的數據時會起緩存行無效,在例1中,當CPU1修改緩存行中的i時使用緩存鎖定,那麼CPU2就不能同時緩存了i的緩存行。
但是有兩種情況下處理器不會使用緩存鎖定。第一種情況是:當操作的數據不能被緩存在處理器內部,或操作的數據跨多個緩存行(cache line),則處理器會調用總線鎖定。第二種情況是:有些處理器不支持緩存鎖定。對於Inter486和奔騰處理器,就算鎖定的內存區域在處理器的緩存行中也會調用總線鎖定。
以上兩個機制我們可以通過Inter處理器提供了很多LOCK前綴的指令來實現。比如位測試和修改指令BTS,BTR,BTC,交換指令XADD,CMPXCHG和其他一些操作數和邏輯指令,比如ADD(加),OR(或)等,被這些指令操作的內存區域就會加鎖,導致其他處理器不能同時訪問它。
CAS
在java中可以通過循環CAS的方式來實現原子操作,即Compare and Swap。
CAS有3個操作數,內存值V,舊的預期值A,要修改的新值B。當且僅當預期值A和內存值V相同時,將內存值V修改為B,否則什麼都不做。
我們看一下AtomicInteger這個類的incrementAndGet方法:
1public final int incrementAndGet() {
2 for (;;) {
3 int current = get();
4 int next = current + 1;
5 if (compareAndSet(current, next))
6 return next;
7 }
8}
在這裡採用了CAS操作,每次從內存中讀取數據然後將此數據和+1後的結果進行CAS操作,如果成功就返回結果,否則重試直到成功為止。而compareAndSet利用JNI來完成CPU指令的操作。
CAS中的ABA問題
CAS用起來雖然很爽,但是會引起ABA問題,假設如下事件序列:
- 線程 1 從內存位置V中取出A。
- 線程 2 從位置V中取出A。
- 線程 2 進行了一些操作,將B寫入位置V。
- 線程 2 將A再次寫入位置V。
- 線程 1 進行CAS操作,發現位置V中仍然是A,操作成功。
- 儘管線程 1 的CAS操作成功,但不代表這個過程沒有問題——對於線程 1 ,線程 2 的修改已經丟失。
我們再舉一個鏈表ABA的例子:
(1) 現有一個用單向鏈表實現的堆棧,棧頂為A。這時線程T1已經知道A.next為B,然後希望用CAS將棧頂替換為B:
1head.compareAndSet(A,B);
(2) 在T1執行上面這條指令之前,線程T2介入,將A、B出棧,再依次入棧D、C、A,而對象B此時處於遊離狀態。
(3) 此時輪到線程T1執行CAS操作,檢測發現棧頂仍為A,所以CAS成功,棧頂變為B。但實際上B.next為null,此時堆棧中只有B一個元素,C和D組成的鏈表不再存在於堆棧中,C、D被丟掉了。
如何解決CAS中的ABA問題
ABA問題的解決思路就是使用版本號。在變量前面追加上版本號,每次變量更新的時候把版本號加一,那麼A-B-A 就會變成1A-2B-3A。
在java中可以使用AtomicStampedReference 這個類解決ABA問題,它內部不僅維護了對象值,還維護了一個時間戳(我這裡把它稱為時間戳,實際上它可以使任何一個整數,它使用整數來表示狀態值)。當AtomicStampedReference對應的數值被修改時,除了更新數據本身外,還必須要更新時間戳。當AtomicStampedReference設置對象值時,對象值以及時間戳都必須滿足期望值,寫入才會成功。因此,即使對象值被反覆讀寫,寫回原值,只要時間戳發生變化,就能防止不恰當的寫入。
1/比較設置 參數依次為:期望值 寫入新值 期望時間戳 新時間戳
2public boolean compareAndSet(V expectedReference,V
3newReference,int expectedStamp,int newStamp)
4//獲得當前對象引用
5public V getReference()
6//獲得當前時間戳
7public int getStamp()
8//設置當前對象引用和時間戳
9public void set(V newReference, int newStamp)
10
我們將incrementAndGet方法使用該類重寫一下,代碼如下:
1public class AtomicStampedReferenceDemo {
2 AtomicStampedReference<integer> atomicStampedReference = new AtomicStampedReference<integer>(0, 0);/<integer>/<integer>
3 public int incrementAndGet() {
4 for (;;) {
5 int stamp = atomicStampedReference.getStamp();
6 int ref = atomicStampedReference.getReference();
7 int next = ref+1;
8 if (atomicStampedReference.compareAndSet(ref,next, stamp, stamp + 1){
9 return next;
10 }
11 }
12
13 }
14}
使用CAS會引發的問題
使用CAS雖然比java中使用鎖的開銷要低,但是也存在以下幾點問題:
1、ABA問題
該問題的解決辦法前面已經說的很詳細,可以加版本號解決。
2、循環時間長開銷大
自旋CAS如果長時間不成功,會給CPU帶來非常大的執行開銷。如果JVM能支持處理器提供的pause指令那麼效率會有一定的提升,pause指令有兩個作用,第一它可以延遲流水線執行指令(de-pipeline),使CPU不會消耗過多的執行資源,延遲的時間取決於具體實現的版本,在一些處理器上延遲時間是零。第二它可以避免在退出循環的時候因內存順序衝突(memory order violation)而引起CPU流水線被清空(CPU pipeline flush),從而提高CPU的執行效率。
3、只能保證一個共享變量的原子操作
當對一個共享變量執行操作時,我們可以使用循環CAS的方式來保證原子操作,但是對多個共享變量操作時,循環CAS就無法保證操作的原子性,這個時候就可以用鎖,或者有一個取巧的辦法,就是把多個共享變量合併成一個共享變量來操作。比如有兩個共享變量i=2,j=a,合併一下ij=2a,然後用CAS來操作ij。從Java1.5開始JDK提供了AtomicReference類來保證引用對象之間的原子性,你可以把多個變量放在一個對象裡來進行CAS操作。
閱讀更多 科技伍小黑 的文章