1. 鎖的劣勢(shì)
前文中曾經(jīng)對(duì)比同步方法的內(nèi)置鎖相比和顯式鎖曙旭，來說明它們各自的優(yōu)勢(shì)，但是無論是內(nèi)置說還是顯式鎖蕊程，其本質(zhì)都是通過加鎖來維護(hù)多線程安全雏搂。
由于加鎖機(jī)制藕施，線程在申請(qǐng)鎖和等待鎖的過程中，必然會(huì)造成線程的掛起和恢復(fù)凸郑，這樣的線程上線文間切換會(huì)帶來很大的資源開銷裳食，尤其是在鎖資源競(jìng)爭(zhēng)激烈的情況下。
同時(shí)芙沥，線程在等待鎖的過程中诲祸，因?yàn)樽枞裁匆沧龀九危瑹o限條件的等待不僅性能效率不佳，同時(shí)也容易造成死鎖烦绳。
2. 悲觀鎖和樂觀鎖
無論是內(nèi)置鎖還是顯式鎖卿捎，都是一種獨(dú)占鎖，也是悲觀鎖径密。所謂悲觀鎖午阵，就是以悲觀的角度出發(fā)，認(rèn)為如果不上鎖享扔，一定會(huì)有其他線程修改數(shù)據(jù)底桂，破壞一致性，影響多線程安全惧眠，所以必須通過加鎖讓線程獨(dú)占資源籽懦。
與悲觀鎖相對(duì)，還有更高效的方法——樂觀鎖氛魁，這種鎖需要借助沖突檢查機(jī)制來判斷在更新的過程中是否存在來氣其他線程的干擾暮顺，如果沒有干擾，則操作成功秀存，如果存在干擾則操作失敗捶码，并且可以重試或采取其他策略。換而言之或链，樂觀鎖需要原子性“讀-改-寫”指令的支持惫恼，來讀取數(shù)據(jù)是否被其他線程修改，改寫數(shù)據(jù)內(nèi)容并將最新的數(shù)據(jù)寫回到原有地址“难危現(xiàn)在大部分處理器以及可以支持這樣的操作祈纯。
3. 比較并交換操作CAS
大部分處理器框架是通過實(shí)現(xiàn)比較并交換（Compare and Swap，CAS）指令來實(shí)現(xiàn)樂觀鎖叼耙。CAS指令包含三個(gè)操作數(shù)：需要讀寫的內(nèi)存位置V腕窥，進(jìn)行比較的值A(chǔ)和擬寫入新值B。當(dāng)且僅當(dāng)V處的值等于A時(shí)旬蟋，才說明V處的值沒有被修改過油昂，指令才會(huì)使用原子方式更新其為B值革娄，否者將不會(huì)執(zhí)行任何操作倾贰。無論操作是否執(zhí)行， CAS都會(huì)返回V處原有的值拦惋。下面的代碼模仿了CAS的語義匆浙。如果你在學(xué)習(xí)Java的過程中或者在工作中遇到什么問題都可以來群里提問，阿里Java高級(jí)大牛直播講解知識(shí)點(diǎn)厕妖，分享知識(shí)首尼，多年工作經(jīng)驗(yàn)的梳理和總結(jié)，帶著大家全面、科學(xué)地建立自己的技術(shù)體系和技術(shù)認(rèn)知软能！可以加群找我要課堂鏈接 注意：是免費(fèi)的 沒有開發(fā)經(jīng)驗(yàn)誤入哦! 非喜勿入迎捺！ 學(xué)習(xí)交流QQ群：478052716
public class SimulatedCAS {
@GuardedBy("this") private int value;
public synchronized int get() {
return value;
}
// CAS = compare and swap
public synchronized int compareAndSwap(int expectedValue,
int newValue) {
int oldValue = value;
if (oldValue == expectedValue)
value = newValue;
return oldValue;
}
public synchronized boolean compareAndSet(int expectedValue,
int newValue) {
return (expectedValue
== compareAndSwap(expectedValue, newValue));
}
}
當(dāng)多個(gè)線程嘗試更新同一個(gè)值時(shí)，只會(huì)有一個(gè)線程成功查排，其他線程都會(huì)失敗凳枝，但是在CAS中，失敗的線程不會(huì)被擁塞跋核，可以自主定義失敗后該如何處理岖瑰，是重試還是取消操作，更具有靈活性砂代。
通常CAS的使用方法為：先從V中讀取A值蹋订，并根據(jù)A值計(jì)算B值，然后再通過CAS以原子的方法各部分更新V中的值刻伊。以計(jì)數(shù)器為例
public class CasCounter {
private SimulatedCAS value;
public int getValue() {
return value.get();
}
public int increment() {
int v;
do {
// 獲得當(dāng)前的值
v = value.get();
} while (v != value.compareAndSwap(v, v + 1));
// 如果返回值不同露戒，則說明更新成功了
return v + 1;
}
}
以不加鎖的方式實(shí)現(xiàn)了原子的“讀-改-寫”操作。
CAS的方法在性能上有很大優(yōu)勢(shì)：在競(jìng)爭(zhēng)程度不是很大的情況下捶箱，基于CAS的操作玫锋，在性能上遠(yuǎn)遠(yuǎn)超過基于鎖的計(jì)數(shù)器；在沒有競(jìng)爭(zhēng)的情況下讼呢，CAS的性能更高撩鹿。
但是CAS的缺點(diǎn)是：將競(jìng)爭(zhēng)的問題交給調(diào)用者來處理，但是悲觀鎖自身就能處理競(jìng)爭(zhēng)悦屏。
4. 原子變量
隨著硬件上對(duì)于原子操作指令的支持节沦，Java中也引入CAS。對(duì)于int础爬、long和對(duì)象的引用甫贯，Java都支持CAS操作，也就是原子變量類看蚜，JVM會(huì)把對(duì)于原子變量類的操作編譯為底層硬件提供的最有效的方法：如果硬件支持CAS叫搁，則編譯為CAS指令，如果不支持供炎，則編譯為上鎖的操作渴逻。
原子變量比鎖的粒度更細(xì)， 更為輕量級(jí)音诫，將競(jìng)爭(zhēng)控制在單個(gè)變量之上惨奕。因?yàn)槠洳恍枰湘i，所以不會(huì)引發(fā)線程的掛起和恢復(fù)竭钝，因此避免了線程間上下文的切換梨撞，性能更好雹洗，不易出現(xiàn)延遲和死鎖的現(xiàn)象。
常見的原子變量有AtomicInteger卧波、AtomicLong时肿、AtomicBoolean和AtomicReference，這些類都支持原子操作港粱，使用get和set方法來獲取和更新對(duì)象嗜侮。原子變量數(shù)組只支持AtomicInteger、AtomicLong和AtomicReference類型啥容，保證數(shù)組中每個(gè)元素都是可以以volatile語義被訪問锈颗。
需要注意的是原子變量沒有定義hashCode和equals方法，所以每個(gè)實(shí)例都是不同的咪惠，不適合作為散列容器的key击吱。
原子變量可以被視為一種更好volatile變量，通過compareAndSet方法嘗試以CAS方式更新數(shù)據(jù)遥昧，下面以實(shí)現(xiàn)數(shù)字區(qū)間為示例代碼展示如何使用AtomicReference覆醇。
public class CasNumberRange {
@Immutable
private static class IntPair {
// INVARIANT: lower <= upper
final int lower;
final int upper;
public IntPair(int lower, int upper) {
this.lower = lower;
this.upper = upper;
}
}
//源自引用 IntPair 初始化為[0，0]
private final AtomicReference values =
new AtomicReference(new IntPair(0, 0));
public int getLower() {
return values.get().lower;
}
public int getUpper() {
return values.get().upper;
}
//設(shè)置下限
public void setLower(int i) {
//開始循環(huán)嘗試
while (true) {
// 獲得變量值
IntPair oldv = values.get();
// 如果下限設(shè)置比當(dāng)前上限還要大
if (i > oldv.upper)
//拋出異常
throw new IllegalArgumentException("Can't set lower to " + i + " > upper");
IntPair newv = new IntPair(i, oldv.upper);
//原子性更新
if (values.compareAndSet(oldv, newv))
//如果更新成功則直接返回炭臭，否者重新嘗試
return;
}
}
//設(shè)置上限 過程和setLower類似
public void setUpper(int i) {
while (true) {
IntPair oldv = values.get();
if (i < oldv.lower)
throw new IllegalArgumentException("Can't set upper to " + i + " < lower");
IntPair newv = new IntPair(oldv.lower, i);
if (values.compareAndSet(oldv, newv))
return;
}
}
}
性能對(duì)比：
前文已經(jīng)提過永脓，原子變量因其使用CAS的方法，在性能上有很大優(yōu)勢(shì)：在競(jìng)爭(zhēng)程度不是很大的情況下鞋仍，基于CAS的操作常摧，在性能上遠(yuǎn)遠(yuǎn)超過基于鎖的計(jì)數(shù)器；在沒有競(jìng)爭(zhēng)的情況下威创，CAS的性能更高落午；但是在高競(jìng)爭(zhēng)的情況下，加鎖的性能將會(huì)超過原子變量性能（類似于肚豺，交通略擁堵時(shí)溃斋，環(huán)島疏通效果好，但是當(dāng)交通十分擁堵時(shí)吸申，信號(hào)燈能夠?qū)崿F(xiàn)更高的吞吐量）梗劫。
不過需要說明的是，在真實(shí)的使用環(huán)境下截碴，資源競(jìng)爭(zhēng)的強(qiáng)度絕大多數(shù)情況下不會(huì)大到可以讓鎖的性能超過原子變量。所以還是應(yīng)該優(yōu)先考慮使用原子變量隐岛。
鎖和原子變量在不同競(jìng)爭(zhēng)程度上性能差異很好地說明了各自的優(yōu)勢(shì)：在中低程度的競(jìng)爭(zhēng)之下瓷翻，原子變量能提供更高的可伸縮性割坠，而在高強(qiáng)度的競(jìng)爭(zhēng)下，鎖能夠有效地避免競(jìng)爭(zhēng)妒牙。
當(dāng)然彼哼，如果能避免在多線程間使用共享狀態(tài)湘今，轉(zhuǎn)而使用線程封閉（如ThreadLocal），代碼的性能將會(huì)更進(jìn)一步地提高摩瞎。
5. 非阻塞算法
如果某種算法中拴签，一個(gè)線程的失敗或者掛起不會(huì)導(dǎo)致其他線程也失敗和掛起，這該種算法是非阻塞的算法旗们。如果在算法的每一步中都存在某個(gè)線程能夠執(zhí)行下去，那么該算法是無鎖（Lock-free）的算法上渴。
如果在算法中僅僅使用CAS用于協(xié)調(diào)線程間的操作，并且能夠正確的實(shí)現(xiàn)曹阔，那么該算法既是一種無阻塞算法隔披，也是一種無鎖算法。在非擁塞算法中奢米，不會(huì)出現(xiàn)死鎖的優(yōu)先級(jí)反轉(zhuǎn)的問題（但是不排除活鎖和資源饑餓的問題，因?yàn)樗惴ㄖ袝?huì)反復(fù)嘗試）恃慧。
上文中的CasNumberRange就是一種非阻塞算法痢士，其很好的說明了非擁塞算法設(shè)計(jì)的基本模式：在更新某個(gè)值時(shí)存在不確定性彪薛，如果失敗就重新嘗試怠蹂。其中關(guān)鍵點(diǎn)在于將執(zhí)行CAS的范圍縮小在單一變量上。
5.1 非阻塞的棧
我們以非阻塞的棧為例說明非擁塞算法的設(shè)計(jì)思路易遣。創(chuàng)建非阻塞算法的關(guān)鍵在于將原子修改的范圍縮小到單個(gè)變量上嫌佑，同時(shí)保證數(shù)據(jù)一致性侨歉。
棧是最簡(jiǎn)單的鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)：每個(gè)元素僅僅指向一個(gè)元素揩魂，每個(gè)元素也僅被一個(gè)元素引用，關(guān)鍵的操作入棧（push）和出棧（pop）都是針對(duì)于棧頂元素（top）的火脉。因此每次操作只需要保證棧頂元素的一致性，將原子操作的范圍控制在指向棧頂元素的引用即可畸颅。實(shí)例代碼如下：
//非阻塞的并發(fā)棧
public class ConcurrentStack {
//原子對(duì)象 棧頂元素
AtomicReference> top = new AtomicReference>();
public void push(E item) {
Node newHead = new Node(item);
Node oldHead;
do { //循環(huán)嘗試
oldHead = top.get();//獲得舊值
newHead.next = oldHead;
} while (!top.compareAndSet(oldHead, newHead)); //比較舊值是否被修改方援，如果沒有則操作成功，否者繼續(xù)嘗試肯骇；
}
public E pop() {
Node oldHead;
Node newHead;
do {
oldHead = top.get();
if (oldHead == null)
return null;
newHead = oldHead.next;
} while (!top.compareAndSet(oldHead, newHead));
return oldHead.item;
}
private static class Node {
public final E item;
public Node next;
public Node(E item) {
this.item = item;
}
}
}
以上代碼充分體現(xiàn)了非阻塞算法的特點(diǎn)：某項(xiàng)操作的完成具有不確定性，如不成功必須重新執(zhí)行笛丙。這個(gè)棧通過compareAndSet來修改棧頂元素，該方法為原子操作胚鸯，如果發(fā)現(xiàn)被其他線程干擾姜钳，則修改操作失敗，方法將重新嘗試哥桥。
算法中的多線程安全性依賴于compareAndSet，其提供和加鎖機(jī)制一樣的安全性拟糕。既保證原子性，有保證了可見性送滞。除此之外，AtomicReference對(duì)象上使用get方法边涕，也保證了內(nèi)存可見性， 和使用volatile變量一樣功蜓。
5.2 非阻塞的鏈表
鏈表的結(jié)構(gòu)比棧更為復(fù)雜，其必須支持頭指針和尾指針腮介，且同時(shí)有兩個(gè)指針指向尾部端衰，分別是尾指針和最后一個(gè)元素next指針甘改。如何保證兩個(gè)指針的數(shù)據(jù)一致性是一個(gè)難題，這不能通過一個(gè)CAS操作來完成抵代。
這個(gè)難題可以應(yīng)用這樣一個(gè)技巧來解決：當(dāng)線程B發(fā)現(xiàn)線程A正在修改數(shù)據(jù)結(jié)構(gòu)時(shí)忘嫉，數(shù)據(jù)結(jié)構(gòu)中應(yīng)該有足夠多的信息使得線程B能幫助線程A完成操作，保證數(shù)據(jù)結(jié)構(gòu)維持一致性庆冕。
我們以插入操作為例分析。在插入過程中有兩個(gè)步驟：
插入新節(jié)點(diǎn)晦嵌，將原有尾節(jié)點(diǎn)的next域指向該節(jié)點(diǎn)拷姿；
將尾指針移動(dòng)到新的尾節(jié)點(diǎn)處。
所以我們可以根據(jù)尾節(jié)點(diǎn)的next域判斷鏈表是否在穩(wěn)定狀態(tài)：如尾節(jié)點(diǎn)的next域?yàn)閚ull描滔，則說明該鏈表是穩(wěn)定狀態(tài)踪古，沒有其他線程在執(zhí)行插入操作；反之茎芋，節(jié)點(diǎn)的next域不為null蜈出，則說明有其他線程在插入數(shù)據(jù)。
如果鏈表不處于穩(wěn)定狀態(tài)該怎么辦呢铡原？可以讓后到的線程幫助正在插入的線程將尾部指針向后推移到新插入的節(jié)點(diǎn)處商叹。示例代碼如下：
public class LinkedQueue {
private static class Node {
final E item;
//下一個(gè)節(jié)點(diǎn)
final AtomicReference> next;
public Node(E item, Node next) {
this.item = item;
this.next = new AtomicReference>(next);
}
}
//啞結(jié)點(diǎn) 也是頭結(jié)點(diǎn)
private final Node dummy = new Node(null, null);
private final AtomicReference> head
= new AtomicReference>(dummy);
//尾部節(jié)點(diǎn)
private final AtomicReference> tail
= new AtomicReference>(dummy);
public boolean put(E item) {
Node newNode = new Node(item, null);
while (true) {
Node curTail = tail.get();
Node tailNext = curTail.next.get();
//得到尾部節(jié)點(diǎn)
if (curTail == tail.get()) {
// 1. 尾部節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)不為空剖笙，則隊(duì)列處于不一致的狀態(tài)
if (tailNext != null) {
// 2. 將為尾部節(jié)點(diǎn)向后退進(jìn)请唱；
tail.compareAndSet(curTail, tailNext);
} else {
// 3. 尾部節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)為空，則隊(duì)列處于一致的狀態(tài)聚至，嘗試更新
if (curTail.next.compareAndSet(null, newNode)) {
// 4. 更新成功本橙，將為尾部節(jié)點(diǎn)向后退進(jìn)；
tail.compareAndSet(curTail, newNode);
return true;
}
}
}
}
}
}
假如步驟一處發(fā)現(xiàn)鏈表處在非穩(wěn)定狀態(tài)贷币，則會(huì)以原子的方法嘗試將尾指針移動(dòng)到新插入的節(jié)點(diǎn)亏狰，無論是否成功這時(shí)鏈表都會(huì)回到穩(wěn)定狀態(tài)，tail.next=null骚揍，此時(shí)再去重新新嘗試。如果步驟二出已經(jīng)將鏈表的尾指針移動(dòng)嘲叔，則步驟四處的原子操作就會(huì)失敗抽活，不過這沒有關(guān)系，因?yàn)閯e的線程已經(jīng)幫助其完成了該操作丁逝，鏈表保持穩(wěn)定狀態(tài)梭姓。
5.3 原子域更新器
上面提到的非擁塞鏈表，在ConcurrentLinkedQueue就有所應(yīng)用誉尖，但是ConcurrentLinkedQueue并不是使用原子變量，而是使用普通的volatile變量琢感，通過基于反射的原子域更新器（AtomicReferenceFieldUpdater）來進(jìn)行更新。
原子域更新器是現(xiàn)有volatile域的一種基于反射的“視圖”烘挫，能夠在volatile域上使用CAS指令柬甥。原子域更新器沒有構(gòu)造器，要構(gòu)建對(duì)象需要使用工廠方法newUpdater暗甥，函數(shù)然注釋如下
/**
* @param tclass 持有待更新域的類
* @param vclass 待更新域的類型
* @param fieldName 待更新域的名字
*/
public static AtomicReferenceFieldUpdater newUpdater(Class tclass,
Class vclass,
String fieldName)撤防；
使用更新器的好處在于避免構(gòu)建原子變量的開銷棒口，但是這只適用于那些頻繁分配且生命周期很短對(duì)象，比如列表的節(jié)點(diǎn)漾肮，其他情況下使用原子變量即可茎毁。
5.4 帶有版本號(hào)原子變量
CAS操作是通過比較值來判斷原值是否被修改，但是還有可能出現(xiàn)這樣的情況：原值為A被修改為B七蜘，然后又被修改為A，也就是A-B-A的修改情況扮念。這時(shí)再通過比較原值就不能判斷是否被修改了碧库。這個(gè)問題也被稱為ABA問題。
ABA問題的解決方案是為變量的值加上版本號(hào)弄匕，只要版本號(hào)變化沽瞭，就說明原值被修改了，這就是帶有時(shí)間戳的原子變量AtomicStampedReference
//原值和時(shí)間戳
public AtomicStampedReference(V initialRef, int initialStamp)柒瓣；
總結(jié)
非擁塞算法通過底層CAS指令來維護(hù)多線程的安全性，CAS指令被封裝成原子變量的形式對(duì)外公開芙贫，是一種更好的volatile變量，可以提供更好伸縮性魂仍，防止死鎖拣挪，但是設(shè)計(jì)和實(shí)現(xiàn)較為復(fù)雜，對(duì)開發(fā)人員要求很高赊舶。
