1. 問題
1.1鎖的問題
要實現(xiàn)并發(fā)，最常見的方式是加鎖沈矿。在使用鎖實現(xiàn)并發(fā)時上真，線程的掛起、恢復過程中存在很大的開銷细睡。如果競爭比較激烈谷羞，調(diào)度開銷和實際工作開銷的比值會很高。
此外，當一個線程正在等待鎖時葛超，它不能做任何事逆粹。如果一個線程在持有鎖的情況下被延遲執(zhí)行，那么所有需要這個鎖的線程都無法執(zhí)行下去猫妙。如果被阻塞的線程優(yōu)先級高，而持有鎖的線程優(yōu)先級低，將會導致優(yōu)先級反轉(zhuǎn)(Priority Inversion)图贸。即 高優(yōu)先級的線程即使可以搶先執(zhí)行，也需要等待鎖被釋放冕广，在這種情況下疏日，高優(yōu)先級線程的級別實際上就降到了低優(yōu)先級線程的級別。
1.2 volatile的問題
與鎖相比撒汉，volatile變量是一種更輕量級的同步機制沟优，因為在使用這些變量時不會發(fā)生上下文切換和線程調(diào)度等操作，可以保證線程之間的可見性和讀寫的原子性睬辐。
但是volatile變量也有其局限：不能用于構建原子的復合操作挠阁，因此當一個變量依賴其他變量或者舊值時就不能使用volatile變量。我們無法用volatile實現(xiàn)原子的更新操作溯饵。
基于上述問題侵俗，我們期望能有一種開銷更低、更安全并且支持原子的更新操作的機制丰刊。
2. 樂觀鎖與悲觀鎖
獨占鎖是一種悲觀鎖隘谣，synchronized就是一種獨占鎖，它假設最壞的情況啄巧，并且只有在確保其它線程不會造成干擾的情況下執(zhí)行寻歧，會導致其它所有需要鎖的線程掛起，等待持有鎖的線程釋放鎖棵帽。而另一個更加有效的鎖就是樂觀鎖熄求。所謂樂觀鎖就是，每次不加鎖而是假設沒有沖突而去完成某項操作逗概，如果因為沖突失敗就重試弟晚，直到成功為止。
3. CAS
3.1 CAS介紹
大多數(shù)處理器都提供了一種CAS（Compare and swap，比較并交換）指令卿城，CAS有3個操作數(shù)枚钓，內(nèi)存值V，舊的預期值A瑟押，要寫入的新值B搀捷。CAS的含義是：當且僅當預期值A和內(nèi)存值V相同時，將內(nèi)存值V修改為B多望，否則什么都不做嫩舟。無論V的值是否等于A，都返回V原有的值怀偷。 CAS原理圖如下家厌。
可以將CAS近似理解為一種樂觀鎖的技術。 當多個線程嘗試使用CAS同時更新同一個變量時椎工，只有其中一個線程能更新變量的值饭于，而其它線程都失敗，失敗的線程并不會被掛起维蒙，而是被告知在這次競爭中失敗了掰吕，可以再次嘗試。 由于線程在競爭失敗時不會被掛起颅痊，所以線程可以靈活地決定在失敗時執(zhí)行什么操作（重試殖熟、恢復操作或什么都不做）。
下面這段代碼來自《Java并發(fā)編程實戰(zhàn)》八千，幫助我們更好地理解CAS的語義：
public synchronized int compareAndSwap(int expectValue, int newValue) {
int old = this.value;
if (old == expectValue) {
this.value = newValue;
}
return old;
}
public synchronized boolean compareAndSet(int expectValue, int newValue) {
return (expectValue == compareAndSwap(expectValue, newValue));
}
3.2 CAS的優(yōu)勢：
CAS是CPU指令級的操作吗讶，只有一步原子操作，避免了在JVM級和操作系統(tǒng)級的鎖定恋捆、線程掛起和上下文切換照皆，所以性能比加鎖更快。這里可以展開很多沸停，暫時不詳述膜毁。
4. JVM對CAS的支持
在Java的原子類變量中，如java.util.concurrent.atomic中的AtomicXXX愤钾，都使用了這些底層的JVM支持為數(shù)字類型的引用類型提供一種高效的CAS操作瘟滨，而在java.util.concurrent中的大多數(shù)類在實現(xiàn)時都直接或間接地使用了這些原子變量類。
4.1 Atomic變量
以AtomicInteger變量為例來說明能颁。AtomicInteger中的部分方法實現(xiàn)：
public class AtomicInteger extends Number implements java.io.Serializable {
private static final long serialVersionUID = 6214790243416807050L;
// setup to use Unsafe.compareAndSwapInt for updates
private static final Unsafe unsafe = Unsafe.getUnsafe();
private static final long valueOffset;
public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
public final int getAndIncrement() {
return unsafe.getAndAddInt(this, valueOffset, 1);
}
}
可以看到杂瘸，在實現(xiàn)中，都調(diào)用了sun.misc.Unsafe類庫里面的CAS算法伙菊，用處理器提供的CAS指令來實現(xiàn)無鎖自增败玉。
4.2 非阻塞算法
如果在某種算法中敌土，一個線程的失敗或掛起不會導致其他線程也失敗或掛起，那么這種算法就稱為非阻塞算法运翼。
如果在算法的每個步驟中都存在某個線程能夠執(zhí)行下去返干，那么這種算法也被稱為無鎖算法。
如果在算法中僅將CAS用于協(xié)調(diào)線程之間的操作血淌，并且正確地實現(xiàn)矩欠，那么它既是一種無阻塞算法，又是一種無鎖算法悠夯。
4.3 無鎖棧
下面是一個無鎖的非阻塞算法的例子癌淮，無鎖棧ConcurrentStack。
在ConcurrentStack中沦补，push() 方法觀察當前棧頂?shù)墓?jié)點该默，構建一個新節(jié)點放在堆棧上，然后策彤，如果棧頂?shù)墓?jié)點在初始觀察之后沒有變化，那么就安裝新節(jié)點匣摘。如果 CAS 失敗店诗，意味著另一個線程已經(jīng)修改了堆棧，那么過程就會重新開始音榜。
類似地庞瘸，在pop()方法中，先獲取棧頂?shù)墓?jié)點赠叼，再根據(jù)棧頂?shù)墓?jié)點獲取第二個節(jié)點（即新的棧頂節(jié)點）擦囊，如果棧頂?shù)墓?jié)點在初始觀察之后沒有變化，那么就安裝新節(jié)點嘴办。如果 CAS 失敗瞬场，意味著另一個線程已經(jīng)修改了堆棧，那么過程就會重新開始涧郊。
public class ConcurrentStack<E> {
AtomicReference<Node<E>> top = new AtomicReference<Node<E>>();
public void push(E item) {
Node<E> newHead = new Node<E>(item);
Node<E> oldHead;
while (true) {
oldHead = top.get();
newHead.next = oldHead;
if (top.compareAndSet(oldHead, newHead)) {
return;
}
}
}
public E pop() {
while (true) {
Node<E> oldHead = top.get();
if (oldHead == null) {
return null;
}
Node<E> newHead = oldHead.next;
if (top.compareAndSet(oldHead, newHead)) {
return oldHead.item;
}
}
}
private static class Node<E> {
public final E item;
public Node<E> next;
public Node(E item) {
this.item = item;
}
}
}
5.ABA問題
這是一種異常情況：當線程獲得對象當前數(shù)據(jù)后贯被，在準備修改為新值前，對象的值被其他線程連續(xù)修改了兩次妆艘，而經(jīng)過這兩次修改后彤灶，對象的值又恢復為舊值。即由A變?yōu)锽批旺，又變?yōu)锳（ABA）幌陕。在一些算法中，對象的值如果經(jīng)過了A-B-A的變化汽煮，仍然會被認為發(fā)生了變化搏熄，需要重新執(zhí)行算法中的某些步驟棚唆。
針對這種情況，有一種常見的解決方案：不是更新某個值搬卒，而是更新值和版本號瑟俭。即使某個值由A變?yōu)锽又變回A，版本號也是不同的契邀。 AtomicStampedReference 和 AtomicMarkableReference 支持在兩個變量上執(zhí)行原子的條件更新摆寄。AtomicStampedReference可以原子地更新 ”對象-引用“ 二元組，通過增加版本號坯门，避免ABA問題微饥。 AtomicMarkableReference可以原子地更新 ”對象-布爾值“ 二元組，通過增加標記值古戴，實現(xiàn)特殊的標記功能欠橘。一個例子是：通過AtomicMarkableReference二元組使節(jié)點保存在鏈表中同時又將其標記為”已刪除的節(jié)點“。
6.總結(jié)
鎖是常見的實現(xiàn)并發(fā)的方式现恼，但有很多局限性肃续。處理器的CAS指令實現(xiàn)了原子級別的更新操作，通過比較并交換而不是鎖來維持線程的安全性叉袍，實現(xiàn)并發(fā)始锚。在JAVA中，這些底層的指令通過原子變量類向外公開喳逛，為整數(shù)和對象引用提供原子的更新操作瞧捌。
基于這些原子的更新操作，我們可以設計實現(xiàn)非阻塞的算法和無鎖的算法润文。這類算法通常能提供更高的可伸縮性姐呐，并能更好地防止活躍性故障。 這類功能也可以為我們在實際工作中設計并發(fā)算法提供思路典蝌。
參考文檔：
非阻塞同步算法與CAS(Compare and Swap)無鎖算法
https://blog.csdn.net/fjslovejhl/article/details/17025001
https://cloud.tencent.com/developer/article/1362763
《Java并發(fā)編程實戰(zhàn)》
sun.misc.Unsafe詳解和CAS底層實現(xiàn)
