《Java并發(fā)編程的藝術(shù)》 —2.3　原子操作的實現(xiàn)原理

2.3　原子操作的實現(xiàn)原理

原子（atomic）本意是“不能被進(jìn)一步分割的最小粒子”，而原子操作（atomic operation）意為“不可被中斷的一個或一系列操作”。在多處理器上實現(xiàn)原子操作就變得有點復(fù)雜。讓我們一起來聊一聊在Intel處理器和Java里是如何實現(xiàn)原子操作的。

1.術(shù)語定義

在了解原子操作的實現(xiàn)原理前，先要了解一下相關(guān)的術(shù)語，如表2-7所示。

表2-7　CPU術(shù)語定義

2.處理器如何實現(xiàn)原子操作

32位IA-32處理器使用基于對緩存加鎖或總線加鎖的方式來實現(xiàn)多處理器之間的原子操作。首先處理器會自動保證基本的內(nèi)存操作的原子性。處理器保證從系統(tǒng)內(nèi)存中讀取或者寫入一個字節(jié)是原子的，意思是當(dāng)一個處理器讀取一個字節(jié)時，其他處理器不能訪問這個字節(jié)的內(nèi)存地址。Pentium 6和最新的處理器能自動保證單處理器對同一個緩存行里進(jìn)行16/32/64位的操作是原子的，但是復(fù)雜的內(nèi)存操作處理器是不能自動保證其原子性的，比如跨總線寬度、跨多個緩存行和跨頁表的訪問。但是，處理器提供總線鎖定和緩存鎖定兩個機(jī)制來保證復(fù)雜內(nèi)存操作的原子性。

（1）使用總線鎖保證原子性

第一個機(jī)制是通過總線鎖保證原子性。如果多個處理器同時對共享變量進(jìn)行讀改寫操作（i++就是經(jīng)典的讀改寫操作），那么共享變量就會被多個處理器同時進(jìn)行操作，這樣讀改寫操作就不是原子的，操作完之后共享變量的值會和期望的不一致。舉個例子，如果i=1，我們進(jìn)行兩次i++操作，我們期望的結(jié)果是3，但是有可能結(jié)果是2，如圖2-3所示。

原因可能是多個處理器同時從各自的緩存中讀取變量i，分別進(jìn)行加1操作，然后分別寫入系統(tǒng)內(nèi)存中。那么，想要保證讀改寫共享變量的操作是原子的，就必須保證CPU1讀改寫共享變量的時候，CPU2不能操作緩存了該共享變量內(nèi)存地址的緩存。

處理器使用總線鎖就是來解決這個問題的。所謂總線鎖就是使用處理器提供的一個LOCK＃信號，當(dāng)一個處理器在總線上輸出此信號時，其他處理器的請求將被阻塞住，那么該處理器可以獨占共享內(nèi)存。

（2）使用緩存鎖保證原子性

第二個機(jī)制是通過緩存鎖定來保證原子性。在同一時刻，我們只需保證對某個內(nèi)存地址的操作是原子性即可，但總線鎖定把CPU和內(nèi)存之間的通信鎖住了，這使得鎖定期間，其他處理器不能操作其他內(nèi)存地址的數(shù)據(jù)，所以總線鎖定的開銷比較大，目前處理器在某些場合下使用緩存鎖定代替總線鎖定來進(jìn)行優(yōu)化。

頻繁使用的內(nèi)存會緩存在處理器的L1、L2和L3高速緩存里，那么原子操作就可以直接在處理器內(nèi)部緩存中進(jìn)行，并不需要聲明總線鎖，在Pentium 6和目前的處理器中可以使用“緩存鎖定”的方式來實現(xiàn)復(fù)雜的原子性。所謂“緩存鎖定”是指內(nèi)存區(qū)域如果被緩存在處理器的緩存行中，并且在Lock操作期間被鎖定，那么當(dāng)它執(zhí)行鎖操作回寫到內(nèi)存時，處理器不在總線上聲言LOCK＃信號，而是修改內(nèi)部的內(nèi)存地址，并允許它的緩存一致性機(jī)制來保證操作的原子性，因為緩存一致性機(jī)制會阻止同時修改由兩個以上處理器緩存的內(nèi)存區(qū)域數(shù)據(jù)，當(dāng)其他處理器回寫已被鎖定的緩存行的數(shù)據(jù)時，會使緩存行無效，在如圖2-3所示的例子中，當(dāng)CPU1修改緩存行中的i時使用了緩存鎖定，那么CPU2就不能同時緩存i的緩存行。

但是有兩種情況下處理器不會使用緩存鎖定。

第一種情況是：當(dāng)操作的數(shù)據(jù)不能被緩存在處理器內(nèi)部，或操作的數(shù)據(jù)跨多個緩存行（cache line）時，則處理器會調(diào)用總線鎖定。

第二種情況是：有些處理器不支持緩存鎖定。對于Intel 486和Pentium處理器，就算鎖定的內(nèi)存區(qū)域在處理器的緩存行中也會調(diào)用總線鎖定。

針對以上兩個機(jī)制，我們通過Intel處理器提供了很多Lock前綴的指令來實現(xiàn)。例如，位測試和修改指令：BTS、BTR、BTC；交換指令XADD、CMPXCHG，以及其他一些操作數(shù)和邏輯指令（如ADD、OR）等，被這些指令操作的內(nèi)存區(qū)域就會加鎖，導(dǎo)致其他處理器不能同時訪問它。

3.Java如何實現(xiàn)原子操作

在Java中可以通過鎖和循環(huán)CAS的方式來實現(xiàn)原子操作。

（1）使用循環(huán)CAS實現(xiàn)原子操作

JVM中的CAS操作正是利用了處理器提供的CMPXCHG指令實現(xiàn)的。自旋CAS實現(xiàn)的基本思路就是循環(huán)進(jìn)行CAS操作直到成功為止，以下代碼實現(xiàn)了一個基于CAS線程安全的計數(shù)器方法safeCount和一個非線程安全的計數(shù)器count。

private AtomicInteger atomicI = new AtomicInteger(0);

private int i = 0;

public static void main(String[] args) {

final Counter cas = new Counter();

List ts = new ArrayList(600);

long start = System.currentTimeMillis();

for (int j = 0; j < 100; j++) {

Thread t = new Thread(new Runnable() {

@Override

public void run() {

for (int i = 0; i < 10000; i++) {

cas.count();

cas.safeCount();

}

}

});

ts.add(t);

}

for (Thread t : ts) {

t.start();

}

// 等待所有線程執(zhí)行完成

for (Thread t : ts) {

try {

t.join();

} catch (InterruptedException e) {

e.printStackTrace();

}

}

System.out.println(cas.i);

System.out.println(cas.atomicI.get());

System.out.println(System.currentTimeMillis() - start);

}

/**??????? * 使用CAS實現(xiàn)線程安全計數(shù)器??????? */

private void safeCount() {

for (;;) {

int i = atomicI.get();

boolean suc = atomicI.compareAndSet(i, ++i);

if (suc) {

break;

}

}

}

/**

* 非線程安全計數(shù)器

*/

private void count() {

i++;

}

}

從Java 1.5開始，JDK的并發(fā)包里提供了一些類來支持原子操作，如AtomicBoolean（用原子方式更新的boolean值）、AtomicInteger（用原子方式更新的int值）和AtomicLong（用原子方式更新的long值）。這些原子包裝類還提供了有用的工具方法，比如以原子的方式將當(dāng)前值自增1和自減1。

（2）CAS實現(xiàn)原子操作的三大問題

在Java并發(fā)包中有一些并發(fā)框架也使用了自旋CAS的方式來實現(xiàn)原子操作，比如LinkedTransferQueue類的Xfer方法。CAS雖然很高效地解決了原子操作，但是CAS仍然存在三大問題。ABA問題，循環(huán)時間長開銷大，以及只能保證一個共享變量的原子操作。

1）ABA問題。因為CAS需要在操作值的時候，檢查值有沒有發(fā)生變化，如果沒有發(fā)生變化則更新，但是如果一個值原來是A，變成了B，又變成了A，那么使用CAS進(jìn)行檢查時會發(fā)現(xiàn)它的值沒有發(fā)生變化，但是實際上卻變化了。ABA問題的解決思路就是使用版本號。在變量前面追加上版本號，每次變量更新的時候把版本號加1，那么A→B→A就會變成1A→2B→3A。從Java 1.5開始，JDK的Atomic包里提供了一個類AtomicStampedReference來解決ABA問題。這個類的compareAndSet方法的作用是首先檢查當(dāng)前引用是否等于預(yù)期引用，并且檢查當(dāng)前標(biāo)志是否等于預(yù)期標(biāo)志，如果全部相等，則以原子方式將該引用和該標(biāo)志的值設(shè)置為給定的更新值。

public boolean compareAndSet(

V????? expectedReference,???? // 預(yù)期引用

V????? newReference,???????????? // 更新后的引用

int??? expectedStamp,??????? // 預(yù)期標(biāo)志

int??? newStamp????????? // 更新后的標(biāo)志

)

2）循環(huán)時間長開銷大。自旋CAS如果長時間不成功，會給CPU帶來非常大的執(zhí)行開銷。如果JVM能支持處理器提供的pause指令，那么效率會有一定的提升。pause指令有兩個作用：第一，它可以延遲流水線執(zhí)行指令（de-pipeline），使CPU不會消耗過多的執(zhí)行資源，延遲的時間取決于具體實現(xiàn)的版本，在一些處理器上延遲時間是零；第二，它可以避免在退出循環(huán)的時候因內(nèi)存順序沖突（Memory Order Violation）而引起CPU流水線被清空（CPU Pipeline Flush），從而提高CPU的執(zhí)行效率。

3）只能保證一個共享變量的原子操作。當(dāng)對一個共享變量執(zhí)行操作時，我們可以使用循環(huán)CAS的方式來保證原子操作，但是對多個共享變量操作時，循環(huán)CAS就無法保證操作的原子性，這個時候就可以用鎖。還有一個取巧的辦法，就是把多個共享變量合并成一個共享變量來操作。比如，有兩個共享變量i＝2,j=a，合并一下ij=2a，然后用CAS來操作ij。從Java 1.5開始，JDK提供了AtomicReference類來保證引用對象之間的原子性，就可以把多個變量放在一個對象里來進(jìn)行CAS操作。

（3）使用鎖機(jī)制實現(xiàn)原子操作

鎖機(jī)制保證了只有獲得鎖的線程才能夠操作鎖定的內(nèi)存區(qū)域。JVM內(nèi)部實現(xiàn)了很多種鎖機(jī)制，有偏向鎖、輕量級鎖和互斥鎖。有意思的是除了偏向鎖，JVM實現(xiàn)鎖的方式都用了循環(huán)CAS，即當(dāng)一個線程想進(jìn)入同步塊的時候使用循環(huán)CAS的方式來獲取鎖，當(dāng)它退出同步塊的時候使用循環(huán)CAS釋放鎖。

Java java學(xué)習(xí)

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。