Java并發
一、鎖
1. 偏向鎖
1. 思想背景
來源：HotSpot的作者經過研究發現，大多數情況下，鎖不僅不存在多線程競争，而且總是由同 一線程多次獲得，為了讓線程獲得鎖的代價更低而引入了偏向鎖。
原理：在對象頭和棧幀中的鎖記錄裡存儲鎖偏向的線程ID，以後該線程在進入和退出 同步塊時不需要進行CAS操作來加鎖和解鎖，隻需簡單地測試一下對象頭的Mark Word裡是否 存儲着指向目前線程的偏向鎖。
悟：偏向鎖的來源就是為了節省當同一個線程通路臨界區資源的時候頻繁CAS加鎖解鎖操作的開支，同樣這也是偏向鎖使用的場景，即隻有一個線程通路臨界區資源的情況
Java對象頭中的Mark Word結構：
image
2. 偏向鎖的加鎖
當一個線程通路同步塊并 擷取鎖時，會在對象頭和棧幀中的鎖記錄裡存儲鎖偏向的線程ID，以後該線程在進入和退出 同步塊時不需要進行CAS操作來加鎖和解鎖，隻需簡單地測試一下對象頭的Mark Word裡是否存儲着指向目前線程的偏向鎖：
如果目前對象頭的線程ID指向了該線程，那麼說明已經獲得了鎖
否則，判斷對象頭中的Mark Word鎖的辨別是否是偏向鎖(對應就是鎖标志位為01，是否是偏向鎖為1)
如果是偏向鎖，那麼會使用CAS将線程ID指向該線程
否則，則使用CAS競争鎖(說明此時是更進階的輕量鎖或者重量鎖，需要競争才行)
最順利的情況就是線程ID指向該線程，這就對應隻有一個線程頻繁通路臨界區資源的情況，此時能夠最大程度的減少CAS操作
3.偏向鎖的撤銷
偏向鎖使用了一種等到競争出現才釋放鎖的機制，是以當其他線程嘗試競争偏向鎖時， 持有偏向鎖的線程才會釋放鎖。偏向鎖的撤銷，需要等待全局安全點(在這個時間點上沒有正 在執行的位元組碼)：
首先暫停擁有偏向鎖的線程，然後檢查持有偏向鎖的線程是否活着
如果不處于活動狀态，則将對象頭設定成無鎖狀态
否則，擁有偏向鎖的棧會被執行，周遊偏向對象的鎖記錄，棧中的鎖記錄和對象頭的Mark Word進行更改：
要麼重新偏向于其他線程，
要麼恢複到無鎖
要麼标記對象不适合作為偏向鎖(此時需要更新鎖)
最後喚醒暫停的線程
4. 過程圖
image
2. 輕量鎖
1. 思想背景
起源：由于線程的阻塞/喚醒需要CPU在使用者态和核心态間切換，頻繁的轉換對CPU負擔很重，進而對并發性能帶來很大的影響
原理：在隻有兩個線程并發通路資源區是，一個持有鎖，另一個進行自旋等待
2. 輕量鎖加鎖
線程在執行同步塊之前，JVM會先在目前線程的棧幀中建立用于存儲鎖記錄的空間，并将對象頭中的Mark Word複制到鎖記錄中(Displaced Mark Word-即被取代的Mark Word)做一份拷貝
拷貝成功後，線程嘗試使用CAS将對象頭的Mark Word替換為指向鎖記錄的指針(将對象頭的Mark Word更新為指向鎖記錄的指針，并将鎖記錄裡的Owner指針指向Object Mark Word)
如果更新成功，目前線程獲得鎖，繼續執行同步方法
如果更新失敗，表示其他線程競争鎖，目前線程便嘗試使用自旋來擷取鎖，若自旋後沒有獲得鎖，此時輕量級鎖會更新為重量級鎖，目前線程會被阻塞
3. 輕量級鎖解鎖
解鎖時會使用CAS操作将Displaced Mark Word替換回到對象頭
如果解鎖成功，則表示沒有競争發生
如果解鎖失敗，表示目前鎖存在競争，鎖會膨脹成重量級鎖，需要在釋放鎖的同時喚醒被阻塞的線程，之後線程間要根據重量級鎖規則重新競争重量級鎖
4. 流程圖
image
3. 三種鎖比較
image
二、處理器和Java中原子性操作的實作
1. 處理器原子性操作的實作
處理器級别記憶體操作的原子性保證有兩種機制：總線鎖定和緩存鎖定。(注意：處理器會自動保證基本的記憶體操作的原子性，即對于記憶體中某一個位址資料的通路時保證同一時刻隻有一個處理器可以)
1. 總線鎖
總線鎖比較簡單粗暴，對于需要限制的共享變量，通過LOCK信号，使得在操作該貢獻變量的時候，一個處理器獨占共享記憶體
2. 緩存鎖
總線鎖使得隻能有一個處理器通路記憶體，其他處理器不能夠操作記憶體裡的其他資料，屬于“一刀切”“一棒子打死”的做法，是以開銷比較大。
所謂“緩存鎖定”是指記憶體區域如果被緩存在處理器的緩存 行中，并且在Lock操作期間被鎖定，那麼當它執行鎖操作回寫到記憶體時，處理器不在總線上聲 言LOCK＃信号，而是修改内部的記憶體位址，并允許它的緩存一緻性機制來保證操作的原子 性，因為緩存一緻性機制會阻止同時修改由兩個以上處理器緩存的記憶體區域資料，當其他處理器回寫已被鎖定的緩存行的資料時，會使緩存行無效，進而使他們重新從記憶體中擷取資料。
雖然，緩存鎖更好，但是總線鎖并沒有完全棄用。有些情況，緩存鎖沒有辦法發揮，此時便需要總線鎖了。
2. Java中實作原子操作的原理
不管是加鎖還是其他方法，Java都是使用循環CAS的方式實作原子操作的。
三、Java記憶體模型
一、記憶體模型
JMM決定一個線程對共享變量的寫入何時對另一個線程可見。從抽象的角度來看，JMM定義了線程和主記憶體之間的抽象關系：線程之間的共享變量存儲在主記憶體(Main Memory)中，每個線程都有一個私有的本地記憶體(Local Memory)，本地記憶體中存儲了該線程以讀/寫共享變量的副本。本地記憶體是JMM的一個抽象概念，并不真實存在。它涵蓋了緩存、寫緩沖區、寄存器以及其他的硬體和編譯器優化。
1. 指令重排序
在執行程式時，為了提高性能，編譯器和處理器常常會對指令做重排序：
編譯器優化的重排序：編譯器在不改變串行語義的前提下，可以安排語句的執行順序
指令級并行的重排序：現代處理器才用了指令級的并行技術(流水線技術)來将多條指令重疊執行。如果不存在資料依賴性，處理器可以改變語句對應 機器指令的執行順序。
記憶體系統的重排序：由于處理器使用緩存和讀/寫緩沖區，這使得加載和存儲操作看上 去可能是在亂序執行。(我們不用關注記憶體系統的重排序，其不再JMM的覆寫範圍)
2. 資料依賴性
如果兩個操作中至少有一個操作是寫操作的話，那麼就說這兩個操作之間具有資料依賴性。
編譯器和處理器在重排序時，會遵守資料依賴性，編譯器和處理器不會改變存在資料依賴關系的兩個操作的執行順序。(這裡的順序依賴性隻針對單線程下的指令)，即指令重排序必須保證單線程下的串行語義。
3. 順序一緻性
當程式未正确同步時，就可能存在資料競争，所謂資料競争就是：1. 在一個線程中寫入一個變量 2. 在另一個線程中讀同一個變量 3. 且寫和讀沒有通過同步來排序
而正确同步的線程，不會發生資料競争。
如果程式是正确同步的，那麼程式的執行具有順序一緻性。
順序一緻性模型有兩條規則：
一個線程中的所有操作必須按照程式的順序來執行。
(不管程式是否同步)所有線程都隻能看到一個單一的操作執行順序。在順序一緻性記憶體模型中，每個操作都必須原子執行且立刻對所有線程可見。
可見，這兩條規則是非常理想化的，如果線程的操作是按照我門程式中寫的順序執行，且不同線程之間的操作立刻可見，那麼并發程式設計會是一件很容易的事情。但是很遺憾JMM一條也沒有遵守順序一緻性模型。對于第一條，編譯器和處理器都會對指令進行重排序，是以執行順序和書寫順序并不相同；對于第二條更不可能了。
但是，在Java中同步了的程式具有順序一緻性的效果：
[圖檔上傳失敗...(image-2082d2-1583984997624)]
是以，Java保證隻要是同步了的代碼，程式員可以把他當做是在順序一緻性模型下運作的一樣
二、Volatile記憶體語義
volatile變量讀寫的記憶體語義：
當寫一個volatile變量時，JMM會把該線程對應的本地記憶體中的共享變量值重新整理到主記憶體(注意：是所有的共享變量，不光是volatile變量)
當讀一個volatile變量時，JMM會把該線程對應的本地記憶體置為無效。線程接下來将從主記憶體中讀取共享變量(注意：這裡也是所有的共享變量)
關于線程如何确定要将共享變量的值重新整理到記憶體，以及為何要從記憶體讀取最新的值，涉及到cpu之間的通信、嗅探等，這裡不做展開。
悟：volatile變量的記憶體語義保證了在讀volatile變量之前，記憶體中所有的共享變量都是最新的，也就是之前執行的的任意線程的寫操作都對本次的讀操作可見；同樣，本次寫操作都對之後任意線程執行的讀操作可見。而且，volatile的讀操作和寫操作都具有原子性。
1. volatile讀寫操作對重排序的影響
JMM的記憶體語義解決了記憶體可見性可能會引發的問題，但是還有一種問題可能會産生，那就是指令重排序的問題：
volatile a = 0;
int b = 1;
public void A (){
b = 2; // 1
a = 1; // 2
}
public void B() {
int c = 0;
if (a == 1) // 3
c = b; // 4
}
假如volatile不會對重排序有任何影響的話，那麼由于代碼1和代碼2兩處沒有資料依賴性，是以二者是可以重排序的，我們假設代碼2在代碼1之前被執行，此時由于a是volatile變量，是以将a = 1， b = 1重新整理進入主記憶體；如果這時候方法A所在的線程cpu時間片用完了，輪到了方法B在另一個線程中執行，由于a是volatile變量是以代碼3處執行的時候會将b = 1， a = 1從主記憶體中讀出，此時代碼4再執行的話c會變為1，而不是預想的2(因為按照我們書寫的順序來看，a=1發生在b=2之後)
發生這種錯誤的原因在于：volatile變量寫操作與在其之前的代碼發生了重排序，使得重新整理記憶體的時機提早了，可能會漏掉我們寫在volatile變量指派操作之前的那些共享變量的修改。是以這就引出了volatile變量對指令重排序的第一個影響：
第二個操作是volatile寫時，不管第一個操作是什麼，都不能重排序。這個規則確定 volatile寫之前的操作不會被編譯器重排序到volatile寫之後。換句話說，以volatile寫這行代碼為分割線，之前的對共享變量的各種讀寫操作的指令不管如何進行重排序，都不可能跑到volatile寫操作之後執行，確定volatile寫操作重新整理記憶體裡共享變量的值時程式員希望發生的變動都能夠正确的重新整理到記憶體中
同理，對應也有volatile變量對指令重排序的另一個影響：
第一個操作是volatile讀時，不管第二個操作是什麼，都不能重排序。這個規則確定 volatile讀之後的操作不會被編譯器重排序到volatile讀之前。確定volatile讀操作讀取記憶體裡的最新值是程式員希望讀到的、操作的值
另外還有一條影響：
第一個操作是volatile寫，第二個操作是volatile讀時，不能重排序
三、Lock鎖的記憶體語義
Java中的鎖的記憶體語義和volatile一模一樣，而ReentrantLock加鎖和釋放鎖的原理就是通過操作一個volatile狀态變量來實作。
1. ReentrantLock公平鎖加鎖的實作
ReentrantLock有自己的繼承鍊，但是真正開始加鎖是從自己的tryAcquire方法：
protected final boolean tryAcquire(int acquires) {
final Thread current = Thread.currentThread();
int c = getState(); // 擷取鎖的開始，首先讀volatile變量state
if (c == 0) {
if (isFirst(current) && compareAndSetState(0, acquires)) { // ------------- 代碼 1------------
setExclusiveOwnerThread(current);
return true;
}
}
else if (current == getExclusiveOwnerThread()) {
int nextc = c + acquires;
if (nextc < 0)
throw new Error("Maximum lock count exceeded");
setState(nextc);
return true;
}
return false;
}
重點在代碼1，注意：這裡的條件中有一個CAS操作，也就是說多個競争鎖的線程中可能都能夠執行到這裡，但是隻有一個能夠使得該條件傳回true，其他都傳回false。執行CAS傳回true的線程通過setExclusiveOwnerThread進行獨占式綁定。而，CAS傳回false的線程最終會直接從該加鎖方法中傳回false，意味着加鎖失敗。
2. ReentrantLock公平鎖釋放鎖的實作
ReentrantLock公平鎖的釋放最終的實作是在其父類中實作的，開始釋放鎖是在tryRelease方法中：
protected final boolean tryRelease(int releases){
int c = getState() - releases;
if (Thread.currentThread() != getExclusiveOwnerThread())
throw new IllegalMonitorStateException();
boolean free = false;
if (c == 0) {
free = true;
setExclusiveOwnerThread(null);
}
setState(c); // 釋放鎖的最後，寫volatile變量state return free;
}
由于線程已經得到了鎖，是以釋放鎖的方法中沒有任何CAS操作API的調用，釋放鎖的邏輯是：判斷c的值，如果c為0了，說明要釋放鎖，此時需要解除線程對該鎖的綁定；如果c沒有變為0，隻是簡單的更新state，永遠不要忘了state是一個volatile變量。
四、final的記憶體語義
五、再了解happen-before原則
happen-before原則是JMM對程式員的一種保證，即一個操作A happen-before另一個操作B，意味着：
A的結果對B可見，且A的執行順序在B之前
并不意味着Java具體實作必須要按照happen-before指定的順序來執行，如果重排序後執行結果與按照happen-before關系來執行的結果一緻，那麼也是允許的
也就是說，JMM的happen-before隻是保證了串行語義的順序和正确同步的順序。也就是說，A happen-before B如果A與B之間有依賴關系、同步關系的話，那麼A确實在B之前執行；如果A與B之間沒有依賴、沒有同步關系的話，那麼A與B之間的執行順序是可以改變的，但是對于程式員來說，結果都一樣，沒所謂，是以認為A執行在B之前也是可以的。
三、線程
四、Java中的Lock
使用Lock比使用synchronized有很多優點：
Lock更靈活，當一個線程同時涉及到多個鎖的時候，使用synchronized就顯得很麻煩了，比如在擷取B鎖之後要釋放A鎖，在擷取C鎖之後要放棄B鎖
Lock對加鎖有更多的選擇：Lock支援非阻塞地擷取鎖、能被中斷地擷取鎖(當擷取到鎖的線程被中斷時，中斷異常将會被抛出，同時釋放鎖)、逾時擷取鎖
Java中Lock中常見的API方法
image
隊列同步器
Java中的隊列同步器AbstractQueuedSynchronizer是用來建構鎖和其他同步元件的基礎架構。它使用一個int成員變量表示同步狀态，并且提供了CAS方法，通過内置的FIFO隊列來完成資源擷取線程的排隊工作。
Java中的鎖和其他的同步元件一般都是在内部定義一個同步器的實作子類，通過同步器定義的方法來管理同步狀态。鎖是面向程式員的，而其内部同步器的實作是面向設計者的。
同步器提供給同步元件的方法主要就是上文Java鎖語義中提到的：
getState
setState
compareAndSetState
三個方法。
一、隊列同步器的實作原理
Java中隊列同步器内部維護了一個雙向的隊列，隊列的作用就是将沒有競争到鎖的線程包裝成一個Node節點插入到隊列中，其中頭結點代表持有鎖的線程。當然，有一些具體的資訊都包括在Node節點中：
image
而線程之是以表現為一種阻塞狀态，是因為擷取不到鎖的線程會陷入一個自旋的循環中不斷地嘗試擷取鎖而導緻線程卡在lock()方法處，具體細節下面再說。需要注意的是，AQS中将競争鎖失敗的線層包裝成節點插入到隊列的尾部是一個CAS操作，這保證了隊列插入順序在多線程下的正确性。
二、獨占式同步狀态擷取與釋放
上面說了，Lock的實作基本上是委托于内部AQS的子類，以ReenTrantLock為例，其内部有一系列Sync的内部類是AQS的具體實作類，而ReentrantLock的lock方法内部調用了sync的acquire(int arg):
public final void acquire(int arg) {
if (!tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt();
}
其中的tryAcquire(arg)方法的實作在上文中展示過了，tryAcquire方法是多個線程競争鎖發生的地方，隻有一個鎖能夠傳回true并且獨占鎖，其他的都會傳回false。
而其他的tryAcquire傳回false的線程會調用acquireQueued實作将線程包裝成雙向隊列的Node并加入的同步隊列中。
final boolean acquireQueued(final Node node, int arg) {
boolean failed = true;
try {
boolean interrupted = false;
for (;;) {
final Node p = node.predecessor();
if (p == head && tryAcquire(arg)) {
setHead(node);
p.next = null; // help GC
failed = false;
return interrupted;
}
if (shouldParkAfterFailedAcquire(p, node) &&
parkAndCheckInterrupt())
interrupted = true;
}
} finally {
if (failed)
cancelAcquire(node);
}
}
重點關注方法内部的for循環，通過這個循環我們知道隻有頭結點的後繼節點會在自旋中調用tryAcquire方法嘗試擷取鎖，而其他的後繼節點隻是在空自旋；然後，當頭結點代表的線程釋放鎖之後，将其移除雙向隊列的地方在後繼節點代替它成為頭結點的地方，看到了将被阻塞的節點加入到隊列中的操作，接下來該看看是如何把一個阻塞的線程包裝成雙向連結清單的節點的：
private Node addWaiter(Node mode) {
Node node = new Node(Thread.currentThread(), mode);
// Try the fast path of enq; backup to full enq on failure
Node pred = tail;
if (pred != null) {
node.prev = pred;
if (compareAndSetTail(pred, node)) {
pred.next = node;
return node;
}
}
enq(node);
return node;
}
對于獨占式擷取鎖的過程，該方法傳遞的參數是Node.EXCLUSIVE，代表一個正阻塞在獨占狀态下的節點。該方法實作的前半部分負責調用CAS方法将該節點加入到雙向隊列的尾部，而最後有調用了一次enq(Node)方法：
private Node enq(final Node node) {
for (;;) {
Node t = tail;
if (t == null) { // Must initialize
if (compareAndSetHead(new Node()))
tail = head;
} else {
node.prev = t;
if (compareAndSetTail(t, node)) {
t.next = node;
return t;
}
}
}
}
Q:這裡點疑惑好像又加入了一次尾部，是不是有點重複了？
小結
以ReentrantLock為例，獨占式鎖的加鎖流程：
ReentrantLock的lock方法的實作委托給了ReentrantLock内部的AQS的實作類Sync的acquire(int arg)方法，而Sync并沒有重寫該方法，acquire的具體實作在抽象父類AbstractQueuedSynchronizer
acquire方法會調用tryAcquire方法嘗試擷取鎖，這裡是發生多個線程競争鎖的地方；其中隻有一個線程能夠通過CAS方法擷取到鎖傳回true，競争失敗的線程都會傳回false
那些競争失敗的線程首先會被addWaiter方法包裝成一個雙向隊列的節點并且加入到雙向隊列的尾部
之後會在acquireQueued方法進行自旋操作，但是隻有頭結點的後繼節點才會調用tryAcquire方法嘗試擷取鎖，其他的後繼節點隻會空自旋