一崎页、無(wú)鎖
對(duì)于并發(fā)控制而言，鎖是一種悲觀的策略腰埂，總是假設(shè)每一次進(jìn)入臨界區(qū)操作都會(huì)產(chǎn)生沖突飒焦，如果多線程訪問臨界區(qū)資源，就寧可犧牲性能讓線程等待屿笼，所以鎖會(huì)阻塞線程執(zhí)行牺荠。而無(wú)鎖是一種樂觀策略，它會(huì)假設(shè)對(duì)臨界區(qū)資源的訪問是沒有沖突的驴一，所有線程都會(huì)不停頓的執(zhí)行休雌，但是如果遇到?jīng)_突那該怎么辦？無(wú)鎖策略使用一種叫做比較交換的技術(shù)（CAS Compare And Swap）來(lái)鑒定線程沖突肝断，一旦檢測(cè)到?jīng)_突杈曲，就進(jìn)行重試直至沒有沖突為止。
1.1 比較交換（CAS）
使用無(wú)鎖的方式?jīng)]有鎖競(jìng)爭(zhēng)帶來(lái)的系統(tǒng)開銷胸懈，也沒有線程間上下文頻繁調(diào)度帶來(lái)的開銷担扑，相對(duì)有鎖而言具有優(yōu)越的性能。
CAS算法的過(guò)程是這樣的：它包含三個(gè)參數(shù)CAS(V,E,N)趣钱。V表示要更新的變量涌献，E表示預(yù)期值，N表示新值首有。僅當(dāng)V值等于E時(shí)燕垃，才會(huì)將V的值設(shè)為N，如果V值和E值不同绞灼，則說(shuō)明已經(jīng)有其他線程做了更新利术，則當(dāng)前線程什么都不做。最后低矮，CAS返回當(dāng)前V的真實(shí)值印叁。CAS操作是抱著樂觀的態(tài)度進(jìn)行的，它總認(rèn)為自己可以完成操作军掂。當(dāng)多個(gè)線程同時(shí)使用CAS操作一個(gè)變量時(shí)轮蜕，只有一個(gè)會(huì)勝出，并成功更新蝗锥，其余均會(huì)失敗跃洛。失敗的線程不會(huì)被掛起，僅是被告知失敗终议，并且允許再次嘗試汇竭，當(dāng)然也允許失敗的線程放棄操作葱蝗。基于這樣的原理细燎，CAS操作即使沒有鎖两曼，也可以發(fā)現(xiàn)其他線程對(duì)當(dāng)前線程的干擾，并進(jìn)行恰當(dāng)?shù)奶幚怼?/p>
1.2 無(wú)鎖的線程安全整數(shù)
JDK并發(fā)包中有一個(gè)atomic包玻驻，里面實(shí)現(xiàn)了一些直接使用CAS操作的線程安全的類型悼凑。其中，最常用的一個(gè)類璧瞬，應(yīng)該就是AtomicInteger户辫。可以把它看做是一個(gè)整數(shù)嗤锉。但是與Integer不同渔欢，它是可變的，并且是線程安全的瘟忱。對(duì)其進(jìn)行任何修改等操作膘茎，都是用CAS指令進(jìn)行的。AtomicInteger的一些主要方法：
//獲取當(dāng)前的值
public final int get()
//設(shè)置當(dāng)前值
public final void set(int newValue)
//取當(dāng)前的值酷誓，并設(shè)置新的值
public final int getAndSet(int newValue)
//如果當(dāng)前值為expect,則設(shè)置為update
public final boolean compareAndSet(int expect,int update)
//獲取當(dāng)前的值披坏，并自增
public final int getAndIncrement()
//獲取當(dāng)前的值，并自減
public final int getAndDecrement()
//,返回當(dāng)前值盐数，并增加delta
public final int addAndGet(int delta)
//當(dāng)前值+1,返回新值
public final int incrementAndGet()
//當(dāng)前值-1,返回新值
public final int decrementAndGet()
AtomicInteger有兩個(gè)核心字段：
//當(dāng)前實(shí)際取值
private volatile int value;
//value字段在AtomicInteger對(duì)象中的偏移量
private static final long valueOffset;
AtomicInteger使用的具體示例如下：
public class AtomicIntegerDemo {
static AtomicInteger i = new AtomicInteger();
public static class AddThred implements Runnable {
@Override
public void run() {
for(int k=0; k<10000; k++) {
i.incrementAndGet();
}
}
}
public static void main(String[] args) throws InterruptedException {
Thread[] ts = new Thread[10];
for (int k = 0; k < 10; k++) {
ts[k] = new Thread(new AddThred());
}
for(int k=0; k<10; k++) {ts[k].start();}
for(int k=0; k<10; k++) {ts[k].join();}
System.out.println(i);
}
}
如果執(zhí)行這段代碼棒拂，程序輸出100000。說(shuō)明程序正常執(zhí)行玫氢，沒有錯(cuò)誤帚屉。如果不是線程安全的，i的值應(yīng)該會(huì)小于100000漾峡。
incrementAndGet()的內(nèi)部實(shí)現(xiàn)為：
public final int incrementAndGet() {
for (;;) {
int current = get();
int next = current + 1;
if (compareAndSet(current, next))
return next;
}
}
第2行的死循環(huán)是因?yàn)镃AS操作未必是成功的攻旦，因此對(duì)于不成功的情況，我們就需要進(jìn)行不斷的嘗試生逸。第3行的get()取得當(dāng)前的值牢屋，接著加1后得到新值next。這樣槽袄，得到了CAS必需的兩個(gè)參數(shù)：期望值以及新值烙无。使用compareAndSet()方法將新值next寫入，成功的條件是在寫入的時(shí)刻遍尺，當(dāng)前的值應(yīng)該要等于剛剛?cè)〉玫腸urrent截酷。如果不是這樣，說(shuō)明AtomicInteger的值在第3行到第5行代碼之間乾戏，又被其他線程修改了迂苛。當(dāng)前線程看到的狀態(tài)就是一個(gè)過(guò)期狀態(tài)三热。因此，compareAndSet返回失敗三幻，需要下一次重試康铭，直到成功。
和AtomicInteger類似的類還有AtomicLong用來(lái)代表long型赌髓，AtomicBoolean表示boolean型，AtomicReference表示對(duì)象引用催跪。
1.3 無(wú)鎖的對(duì)象引用：AtomicReference
AtomicReference是對(duì)普通的對(duì)象引用锁蠕，也就是它可以保證你在修改對(duì)象引用時(shí)的線程安全性。線程判斷被修改對(duì)象是否可以正確寫入的條件是對(duì)象的當(dāng)前值和期望值是否一致懊蒸。但有可能出現(xiàn)例外荣倾，當(dāng)獲得對(duì)象當(dāng)前數(shù)據(jù)后，對(duì)象的值又恢復(fù)為舊值骑丸。這樣舌仍，當(dāng)前線程就無(wú)法正確判斷這個(gè)對(duì)象究竟是否被修改過(guò)。有這樣一個(gè)案例：打一個(gè)比方通危，如果有一家蛋糕店铸豁，為了挽留客戶，決定為貴賓卡里余額小于20元的客戶一次性贈(zèng)送20元菊碟。但條件是节芥，每一位客戶只能被贈(zèng)送一次。
定義用戶賬戶余額：
static AtomicReference<Integer> money = new AtomicReference<Integer>();
money.set(19);
接著逆害，需要若干個(gè)后臺(tái)線程头镊，它們不斷掃描數(shù)據(jù)，并為滿足條件的客戶充值:
for(int i=0; i<3; i++) {
new Thread() {
public void run() {
while(true) {
while(true) {
Integer m = money.get();
if(m<20) {
if(money.compareAndSet(m, m+20)) {
System.out.println("余額小于20元魄幕，充值成功相艇，余額："+ money.get() + "元");
break;
} else {
break;
}
}
}
}
};
}.start();
此時(shí)，如果很不幸纯陨，就在贈(zèng)予金額到賬的同時(shí)坛芽，用戶進(jìn)行了一次消費(fèi)，正好消費(fèi)20元翼抠，這時(shí)的金額又小于20元靡馁。這時(shí)，后臺(tái)的贈(zèng)予就會(huì)誤以為這個(gè)賬戶還沒有贈(zèng)予机久。所以臭墨，存在多次被贈(zèng)予的可能。下面模擬了這個(gè)消費(fèi)線程：
new Thread() {
public void run() {
for (int j = 0; j < 100; j++) {
while(true) {
Integer m = money.get();
if(m>10) {
System.out.println("大于10元");
if(money.compareAndSet(m, m-10)) {
System.out.println("成功消費(fèi)10元膘盖，余額：" + money.get());
break;
}
} else {
System.out.println("沒有足夠金額");
break;
}
}
try {
Thread.sleep(100);
} catch (InterruptedException e) {
}
}
};
}.start();
上述代碼胧弛，消費(fèi)者只要貴賓卡里的錢大于10元尤误，就會(huì)立即進(jìn)行一次10元的消費(fèi)。執(zhí)行上述代碼结缚，得到的輸出如下：
余額小于20元损晤，充值成功，余額：39元
大于10元
成功消費(fèi)10元红竭，余額：29
大于10元
成功消費(fèi)10元尤勋，余額：19
余額小于20元，充值成功茵宪，余額：39元
大于10元
成功消費(fèi)10元最冰，余額：29
大于10元
成功消費(fèi)10元，余額：39
余額小于20元稀火，充值成功暖哨，余額：39元
可以看到，這個(gè)賬戶被先后反復(fù)多次充值凰狞。其原因正是因?yàn)橘~戶余額被反復(fù)修改篇裁，修改后的值等于原有的值，使得CAS操作無(wú)法正確判斷當(dāng)前數(shù)據(jù)狀態(tài)赡若。
1.4 帶有時(shí)間戳的隊(duì)形引用：AtomicStampedReference
之所以出現(xiàn)上面的這種情況达布，是因?yàn)锳tomicReference在對(duì)象修改過(guò)程中，丟失了狀態(tài)信息逾冬。AtomicStampedReference則解決了上述問題往枣，其內(nèi)部不僅維護(hù)了對(duì)象值，還維護(hù)了一個(gè)時(shí)間戳粉渠。當(dāng)AtomicStampedReference對(duì)應(yīng)的數(shù)值被修改時(shí)分冈，除了更新數(shù)據(jù)本身外，還必須要更新時(shí)間戳霸株。當(dāng)AtomicStampedReference設(shè)置對(duì)象值時(shí)雕沉，對(duì)象值以及時(shí)間戳都必須滿足期望值，寫入才會(huì)成功去件。因此坡椒，即使對(duì)象值被反復(fù)讀寫，寫回原值尤溜，只要時(shí)間戳發(fā)生變化倔叼，就能防止不恰當(dāng)?shù)膶懭搿?br> AtomicStampedReference的幾個(gè)API在AtomicReference的基礎(chǔ)上新增了有關(guān)時(shí)間戳的信息：
//比較設(shè)置參數(shù)依次為：期望值 寫入新值 期望時(shí)間戳 新時(shí)間戳
public boolean compareAndSet(V expectedReference, V newReference,int expectedStamp,int newStamp)
//獲得當(dāng)前對(duì)象引用
public V getReference()
//獲得當(dāng)前時(shí)間戳
public int getStamp()
//設(shè)置當(dāng)前對(duì)象引用和時(shí)間戳
public void set(V newReference, int newStamp)
我們使用AtomicStampedReference解決上面反復(fù)充值的問題：
public class AtomicStampedReferenceDemo {
static AtomicStampedReference<Integer> money = new AtomicStampedReference<Integer>(19,0);
public static void main(String[] args) {
for(int i=0; i<3; i++) {
final int timestamp = money.getStamp();
new Thread() {
public void run() {
while(true) {
while(true) {
Integer m = money.getReference();
if(m<20) {
if(money.compareAndSet(m, m+20,timestamp,timestamp+1)) {
System.out.println("余額小于20元，充值成功宫莱，余額："+ money.getReference() + "元");
break;
} else {
break;
}
}
}
}
};
}.start();
}
new Thread() {
public void run() {
for (int j = 0; j < 100; j++) {
while(true) {
int timestamp = money.getStamp();
Integer m = money.getReference();
if(m>10) {
System.out.println("大于10元");
if(money.compareAndSet(m, m-10,timestamp,timestamp+1)) {
System.out.println("成功消費(fèi)10元丈攒，余額：" + money.getReference());
break;
}
} else {
System.out.println("沒有足夠金額");
break;
}
}
try {
Thread.sleep(100);
} catch (InterruptedException e) {
// TODO: handle exception
}
}
};
}.start();
}
}
結(jié)果輸出如下：
余額小于20元，充值成功，余額：39元
大于10元
成功消費(fèi)10元巡验，余額：29
大于10元
成功消費(fèi)10元际插，余額：19
大于10元
成功消費(fèi)10元，余額：9
沒有足夠金額
1.5 數(shù)組也能無(wú)鎖：AtomicIntegerArray
當(dāng)前可用的原子數(shù)組有：AtomicIntegerArray显设、AtomicLongArray框弛、AtomicReferenceArray，分別表示整數(shù)數(shù)組捕捂、long型數(shù)組和普通對(duì)象數(shù)組瑟枫。以AtomicIntegerArray為例，展示原子數(shù)組的使用方式指攒。AtomicIntegerArray本質(zhì)上是對(duì)int[]類型的封裝慷妙，使用Unsafe類通過(guò)CAS的方式控制int[]在多線程的安全性。它提供以下幾個(gè)核心API：
//獲得數(shù)組第i個(gè)下標(biāo)的元素
public final int get(int i)
//獲得數(shù)組的長(zhǎng)度
public final int length()
//將數(shù)組第i個(gè)下標(biāo)設(shè)置為newValue幽七，并返回舊的值
public final int getAndSet(int i, int newValue)
//進(jìn)行CAS操作，如果第i個(gè)下標(biāo)的元素等于expect溅呢，則設(shè)置為update澡屡，設(shè)置成功返回true
public final boolean compareAndSet(int i, int expect, int update)
//將第i個(gè)下標(biāo)元素加 1
public final int getAndIncrement(int i)
//將第i個(gè)下標(biāo)的元素減1
public final int getAndDecrement(int i)
//將第i個(gè)下標(biāo)的元素增加delta(delta可以是負(fù)數(shù))
public final int getAndAdd(int i, int delta)
下面展示AtomicIntegerArray的使用：
public class AtomicIntegerArrayDemo {
static AtomicIntegerArray arr = new AtomicIntegerArray(10);
public static class AddThread implements Runnable {
@Override
public void run() {
for(int k=0; k<10000; k++) {
arr.getAndIncrement(k%arr.length());
}
}
}
public static void main(String[] args) throws InterruptedException {
Thread[] ts = new Thread[10];
for(int k=0; k<10; k++) {
ts[k] = new Thread(new AddThread());
}
for(int k=0; k<10; k++) {
ts[k].start();
}
for(int k=0; k<10; k++) {
ts[k].join();
}
System.out.println(arr);
}
}
結(jié)果為：
[10000,10000,10000,10000,10000,10000,10000,10000,10000,10000]
如果線程安全，數(shù)組內(nèi)10個(gè)元素的值必然都是10000咐旧。反之驶鹉，如果線程不安全，則部分或者全部數(shù)值會(huì)小于10000铣墨。
1.6 讓普通變量也享受原子操作：AtomicIntegerFieldUpdater
可能由于初期考慮不周室埋，一些普通變量會(huì)有線程安全的需求，原子包中的一個(gè)實(shí)用工具類AtomicIntegerFieldUpdater可以讓普通變量享受CAS原子操作帶來(lái)的線程安全性伊约。根據(jù)類型的不同姚淆，這個(gè)Updater有三種：AtomicIntegerFieldUpdater,AtomicLongFieldUpdater和AtomicReferenceFieldUpdater。分別可以對(duì)int,long和普通對(duì)象進(jìn)行CAS修改屡律。
現(xiàn)在思考一個(gè)場(chǎng)景腌逢。假設(shè)某地要進(jìn)行一次選舉。現(xiàn)在模擬這個(gè)投票場(chǎng)景超埋，如果選民投了候選人一票搏讶，就記為1，否則記為0霍殴。最終的選票顯然就是所有數(shù)據(jù)的簡(jiǎn)單求和媒惕。
public class AtomicIntegerFieldUpdaterDemo {
public static class Candidate {
int id;
volatile int score;
}
public final static AtomicIntegerFieldUpdater<Candidate> scoreUpdater
= AtomicIntegerFieldUpdater.newUpdater(Candidate.class, "score");
public static AtomicInteger allScore = new AtomicInteger(0);
public static void main(String[] args) throws InterruptedException {
final Candidate stu = new Candidate();
Thread[] t = new Thread[10000];
for(int i=0; i<10000; i++) {
t[i] = new Thread() {
@Override
public void run() {
if(Math.random() > 0.4) {
scoreUpdater.incrementAndGet(stu);
allScore.incrementAndGet();
}
}
};
t[i].start();
}
for(int i=0; i<10000; i++) {t[i].join();}
System.out.println("score=" + stu.score);
System.out.println("allScore=" + allScore);
}
}
運(yùn)行這段程序，最終的Candidate.score總是和allScore絕對(duì)相等来庭。這說(shuō)明AtomicIntegerFieldUpdater很好地保證了Candidate.score的線程安全妒蔚。
注意：
- Updater只能修改它可見范圍的變量。因?yàn)閁pdater是通過(guò)反射得到的這個(gè)變量。如果變量不可見面睛，會(huì)出錯(cuò)絮蒿。比如score申明為private,就不行；
- 為了確保變量被正確的讀取叁鉴，必須是volatile修飾土涝；
- 由于CAS操作會(huì)通過(guò)對(duì)象實(shí)例中的偏移量直接進(jìn)行賦值，因此幌墓，它不支持static字段(public native long objectFieldOffset()不支持靜態(tài)變量) 但壮。
二、有關(guān)死鎖的問題
死鎖：兩個(gè)或者多個(gè)線程常侣，相互占用對(duì)方需要的資源蜡饵，而都不進(jìn)行釋放，導(dǎo)致彼此之間都相互等待對(duì)方釋放資源胳施，產(chǎn)生了無(wú)限制等待的現(xiàn)象溯祸。死鎖一旦發(fā)生，如果沒有外力接入舞肆，這種等待將永遠(yuǎn)存在焦辅，從而對(duì)線程產(chǎn)生嚴(yán)重的影響。
下面用一個(gè)簡(jiǎn)單的例子模擬死鎖問題：
public class DeadLock extends Thread {
protected Object tool;
static Object fork1 = new Object();
static Object fork2 = new Object();
public DeadLock(Object obj) {
this.tool = obj;
if(tool == fork1) {
this.setName("A");
}
if(tool == fork2) {
this.setName("B");
}
}
@Override
public void run() {
if(tool == fork1) {
synchronized (fork1) {
try {
Thread.sleep(500);
} catch (Exception e) {
e.printStackTrace();
}
synchronized (fork2) {
System.out.println("哲學(xué)家A開始吃飯了");
}
}
}
if(tool == fork2) {
synchronized (fork2) {
try {
Thread.sleep(500);
} catch (Exception e) {
e.printStackTrace();
}
synchronized (fork1) {
System.out.println("哲學(xué)家B開始吃飯了");
}
}
}
}
public static void main(String[] args) throws InterruptedException {
DeadLock A = new DeadLock(fork1);
DeadLock B = new DeadLock(fork2);
A.start();
B.start();
Thread.sleep(1000);
}
}
上述代碼模擬了兩個(gè)哲學(xué)家互相等待對(duì)方的叉子椿胯。如果吃飯必須用兩個(gè)叉子筷登，哲學(xué)家A先占用叉子1，哲學(xué)家B占用叉子2哩盲，接著他們就互相等待前方，都沒有辦法獲得兩個(gè)叉子用餐，這就是死鎖廉油。
如果在實(shí)際環(huán)境中惠险，遇到了這種情況，通常的表現(xiàn)就是相關(guān)的進(jìn)程不再工作抒线，并且CPU占用率為0（因?yàn)樗梨i的線程不占用CPU）莺匠。想確認(rèn)問題，需要使用JDK提供的工具十兢。首先趣竣，可以使用jps命令得到j(luò)ava進(jìn)程的進(jìn)程ID，接著使用jstack命令得到線程的線程堆棧：
jps
獲取進(jìn)程旱物。
jstack [id]
查看指定進(jìn)程的堆棧信息遥缕。
