xylz,imxylz

關(guān)注后端架構(gòu)、中間件、分布式和并發(fā)編程

:: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合

:: 管理 ::

111 隨筆 :: 10 文章 :: 2680 評論 :: 0 Trackbacks

深入淺出 Java Concurrency (5): 原子操作 part 4

在JDK 5之前Java語言是靠synchronized關(guān)鍵字保證同步的，這會(huì)導(dǎo)致有鎖（后面的章節(jié)還會(huì)談到鎖）。

鎖機(jī)制存在以下問題：

（1）在多線程競爭下，加鎖、釋放鎖會(huì)導(dǎo)致比較多的上下文切換和調(diào)度延時(shí)，引起性能問題。

（2）一個(gè)線程持有鎖會(huì)導(dǎo)致其它所有需要此鎖的線程掛起。

（3）如果一個(gè)優(yōu)先級高的線程等待一個(gè)優(yōu)先級低的線程釋放鎖會(huì)導(dǎo)致優(yōu)先級倒置，引起性能風(fēng)險(xiǎn)。

volatile是不錯(cuò)的機(jī)制，但是volatile不能保證原子性。因此對于同步最終還是要回到鎖機(jī)制上來。

獨(dú)占鎖是一種悲觀鎖，synchronized就是一種獨(dú)占鎖，會(huì)導(dǎo)致其它所有需要鎖的線程掛起，等待持有鎖的線程釋放鎖。而另一個(gè)更加有效的鎖就是樂觀鎖。所謂樂觀鎖就是，每次不加鎖而是假設(shè)沒有沖突而去完成某項(xiàng)操作，如果因?yàn)闆_突失敗就重試，直到成功為止。

CAS 操作

上面的樂觀鎖用到的機(jī)制就是CAS，Compare and Swap。

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

非阻塞算法（nonblocking algorithms）

一個(gè)線程的失敗或者掛起不應(yīng)該影響其他線程的失敗或掛起的算法。

現(xiàn)代的CPU提供了特殊的指令，可以自動(dòng)更新共享數(shù)據(jù)，而且能夠檢測到其他線程的干擾，而 compareAndSet() 就用這些代替了鎖定。

拿出AtomicInteger來研究在沒有鎖的情況下是如何做到數(shù)據(jù)正確性的。

private volatile int value;

首先毫無以為，在沒有鎖的機(jī)制下可能需要借助volatile原語，保證線程間的數(shù)據(jù)是可見的（共享的）。

這樣才獲取變量的值的時(shí)候才能直接讀取。

public final int get() {
return value;
}

然后來看看++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來完成CPU指令的操作。

public final boolean compareAndSet(int expect, int update) {
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }

整體的過程就是這樣子的，利用CPU的CAS指令，同時(shí)借助JNI來完成Java的非阻塞算法。其它原子操作都是利用類似的特性完成的。

而整個(gè)J.U.C都是建立在CAS之上的，因此對于synchronized阻塞算法，J.U.C在性能上有了很大的提升。參考資料的文章中介紹了如果利用CAS構(gòu)建非阻塞計(jì)數(shù)器、隊(duì)列等數(shù)據(jù)結(jié)構(gòu)。

CAS看起來很爽，但是會(huì)導(dǎo)致“ABA問題”。

CAS算法實(shí)現(xiàn)一個(gè)重要前提需要取出內(nèi)存中某時(shí)刻的數(shù)據(jù)，而在下時(shí)刻比較并替換，那么在這個(gè)時(shí)間差類會(huì)導(dǎo)致數(shù)據(jù)的變化。

比如說一個(gè)線程one從內(nèi)存位置V中取出A，這時(shí)候另一個(gè)線程two也從內(nèi)存中取出A，并且two進(jìn)行了一些操作變成了B，然后two又將V位置的數(shù)據(jù)變成A，這時(shí)候線程one進(jìn)行CAS操作發(fā)現(xiàn)內(nèi)存中仍然是A，然后one操作成功。盡管線程one的CAS操作成功，但是不代表這個(gè)過程就是沒有問題的。如果鏈表的頭在變化了兩次后恢復(fù)了原值，但是不代表鏈表就沒有變化。因此前面提到的原子操作AtomicStampedReference/AtomicMarkableReference就很有用了。這允許一對變化的元素進(jìn)行原子操作。

參考資料：

（1）非阻塞算法簡介

（2）流行的原子

原子操作 part 3 指令重排序與happens-before法則

目錄

鎖機(jī)制 part 1 Lock與ReentrantLock

posted on 2010-07-04 18:03 imxylz 閱讀(48027) 評論(19) 編輯收藏所屬分類: J2EE

請教博主，從網(wǎng)上找了一段模擬CAS的代碼，能夠?qū)崿F(xiàn)i++功能，改了一下。開了10000個(gè)線程運(yùn)行，結(jié)果是錯(cuò)誤的，達(dá)不到10000. 為什么？
public class CasCounter {
private SimulatedCAS simulatedCAS = null;
public int getValue(){
return simulatedCAS.getValue();
}

public int increment(){
int oldValue = simulatedCAS.getValue();
while(simulatedCAS.compareAndSwap(oldValue, oldValue+1) != oldValue)
oldValue = simulatedCAS.getValue();
return oldValue;
}

public CasCounter(SimulatedCAS cas){
this.simulatedCAS = cas;
}

public static void main(String[] args) throws InterruptedException {
CasCounter counter = new CasCounter(new SimulatedCAS());
Thread[] ts = new Thread[10000];
for(int i = 0; i <10000; i++){
ts[i] = new CounterThread(counter);

}
for(Thread t : ts){
t.start();
}

for(Thread t : ts){
t.join();
}

System.out.println("counter: "+ counter.getValue());
}
}

public class CounterThread extends Thread {
CasCounter counter = null;

public CounterThread(CasCounter counter) {

this.counter = counter;
}

@Override
public void run() {
counter.increment();
}
}

public class SimulatedCAS {

private volatile int value = 0;
public synchronized int getValue(){
return value;

}
public synchronized int compareAndSwap(int expectedValue, int newValue){
if(value == expectedValue)
value = newValue;
return expectedValue;
}
}
回復(fù) 更多評論

# re: 深入淺出 Java Concurrency (5): 原子操作 part 4[未登錄] 2011-08-09 20:07 xxx

@kick
問題可能出在CasCounter.increment()函數(shù)中。
多個(gè)線程可能取到相同的 oldValue，會(huì)導(dǎo)致線程修改失效。
如果給這個(gè)函數(shù)加上 synchronized差不多就可以了。

不過郁悶的是，加上synchronized以后，也會(huì)出現(xiàn)達(dá)不到10000的情況。
不過比不加synchronized的情況好的多。不知道是為什么了回復(fù) 更多評論

# re: 深入淺出 Java Concurrency (5): 原子操作 part 4 2011-08-09 21:29 xylz

@xxx
@kick

出錯(cuò)的地方在于CAS操作，稍微改動(dòng)一下：
public synchronized int compareAndSwap(int expectedValue, int newValue) {
if (value == expectedValue) {
value = newValue;
return expectedValue;
}
return - expectedValue;
}
就可以得到正確結(jié)果的。通常CAS操作可以返回true/false，如果操作成功返回true，否則返回false。原來的代碼是不管操作是否成功都返回了期待值，所以就改變了操作邏輯。
回復(fù) 更多評論

# re: 深入淺出 Java Concurrency (5): 原子操作 part 4 2011-08-11 15:49 zhangxl

@xylz
這里的模擬都使用了synchronized(內(nèi)在鎖)關(guān)鍵字，模擬CAS還有什么意義呢？引入CAS的目的不就是為了較少鎖的競爭，提高多線程并發(fā)的吞吐率嗎？
我覺得要模擬也應(yīng)該像AQS那樣，比如，這是AQS的源碼中狀態(tài)變量的原子操作:

A.Q.S里面包含了一個(gè)存儲(chǔ)同步狀態(tài)的變量，它的聲明如下：

private volatile int state;

這里采用了volatile修飾符的原因是為了保證對state變量的寫對所有的線程都是可見的。但是大家都知道，volatile只能保證變量的可見性，不能保證對變量操作的原子性，所以A.Q.S里面就采用了CAS（Compare And Swap）操作來更新state變量的值，代碼如下：

protected final boolean compareAndSetState(int expect, int update)
{ // See below for intrinsics setup to support this
return unsafe.compareAndSwapInt(this, stateOffset, expect, update); }

個(gè)人覺得這樣才能模擬出CAS的本質(zhì)，原子特性。
回復(fù) 更多評論

# re: 深入淺出 Java Concurrency (5): 原子操作 part 4 2011-08-13 20:18 yintiefu

@kick
修改2個(gè)地方的代碼

1.
public int increment() {

for(;;){
int oldValue = simulatedCAS.getValue();
if(simulatedCAS.compareAndSwap(oldValue,oldValue+1)){
oldValue = simulatedCAS.getValue();
return oldValue;
}
}
}

2.
public synchronized boolean compareAndSwap(int expectedValue, int newValue) {
if (value == expectedValue){
value = newValue;
return true;
}
return false;
} 回復(fù) 更多評論

# re: 深入淺出 Java Concurrency (5): 原子操作 part 4 2011-08-26 10:53 imtxt

@zhangxl
您講的是上面的回復(fù)貼出的代碼？本來那就是拿來做好玩用的吧。回復(fù) 更多評論

# re: 深入淺出 Java Concurrency (5): 原子操作 part 4 2012-07-09 11:39 waitingfortime

@xylz
這個(gè)代碼不做修改，也可以得到正確的數(shù)啊？怎么得不到呢回復(fù) 更多評論

# re: 深入淺出 Java Concurrency (5): 原子操作 part 4[未登錄] 2013-03-03 14:40 teasp

“獨(dú)占鎖是一種悲觀鎖”，這是錯(cuò)誤的說法。回復(fù) 更多評論

# re: 深入淺出 Java Concurrency (5): 原子操作 part 4 2013-03-06 21:44 asdf

@teasp
別話說一半，解釋一下回復(fù) 更多評論

# re: 深入淺出 Java Concurrency (5): 原子操作 part 4[未登錄] 2013-03-07 12:54 teasp

@asdf
獨(dú)占鎖既可以是悲觀的也可以是樂觀的呀，用CAS實(shí)現(xiàn)的獨(dú)占鎖不就是樂觀的？回復(fù) 更多評論

# re: 深入淺出 Java Concurrency (5): 原子操作 part 4[未登錄] 2013-06-16 13:24 flying

用博主的 int compareAndSwap方法返回- expectedValue，有時(shí)會(huì)出現(xiàn)9999，用boolean是對的，應(yīng)該是expectedValue為零時(shí)，-0和0是相同的值，導(dǎo)致沒有加成功。回復(fù) 更多評論

# re: 深入淺出 Java Concurrency (5): 原子操作 part 4[未登錄] 2013-06-16 13:31 flying

@xylz
SimulatedCAS 類的value 是volatile ，getValue的synchronized 關(guān)鍵字是不是可以去掉了？
回復(fù) 更多評論

# re: 深入淺出 Java Concurrency (5): 原子操作 part 4 2014-08-06 21:04 vanjayzhou

借這里問個(gè)問題哈，java 當(dāng)中的cas問題，java concurrent 包的實(shí)現(xiàn)是依賴 CAS準(zhǔn)則實(shí)現(xiàn)的，對AtomicInteger 方法中的 compareAndSet方法有些疑惑。
public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

unsafe.compareAndSwapInt方法是本地方法，我考慮這么一種情況：
兩個(gè)線程T1， T2 同時(shí)取了主內(nèi)存中A， T1調(diào)用compareAndSet 方法成功，將A變成 A1，因?yàn)锳值是同時(shí)從內(nèi)存中取出來的，那T2調(diào)用compareAndSet方法也會(huì)成功，將A變成A2. 那結(jié)果不是不正確了么。
幫我分析一下啊。
謝啦
回復(fù) 更多評論

# re: 深入淺出 Java Concurrency (5): 原子操作 part 4 2014-08-08 10:13 imxylz

@vanjayzhou
CAS的CPU原語保證A修改時(shí)，T2修改會(huì)失敗。所以T2才需要循環(huán)操作，直到成功。回復(fù) 更多評論

# re: 深入淺出 Java Concurrency (5): 原子操作 part 4[未登錄] 2014-10-31 16:58 JJZHK

@vanjayzhou
老版的CPU會(huì)進(jìn)行鎖總線，新版的CPU進(jìn)行的是緩存鎖定。所以T2修改的時(shí)候肯定會(huì)失敗的，因?yàn)楣蚕韮?nèi)存已經(jīng)被CPU鎖定了。回復(fù) 更多評論

# re: 深入淺出 Java Concurrency (5): 原子操作 part 4[未登錄] 2016-01-06 08:40 William Chen

沒錯(cuò)是交換設(shè)置。回復(fù) 更多評論

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發(fā)表評論。




網(wǎng)站導(dǎo)航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關(guān)文章: Java 8 入門/新特性隨機(jī)選擇集合的子元素集合 Crack JRebel 5.3.1 一次簡單卻致命的錯(cuò)誤 Spring Framework 3.1 Reference CHM 編程語言大戰(zhàn) 處理Zookeeper的session過期問題享受熱部署的好處 Crack JRebel 4.0，無需重啟JVM，熱部署解決方案當(dāng)Ajax遭遇GBK編碼 (完全解決方案)

xylz,imxylz

公告

常用鏈接

留言簿(149)

隨筆分類(137)

隨筆檔案(107)

文章分類(12)

文章檔案(12)

友情鏈接

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

評論