我們知道,在java中提供了兩類鎖的實現,一種是在jvm層級上實現的synchrinized隱式鎖,另一類是jdk在程式碼層級實現的,juc包下的Lock顯示鎖,而提到Lock就不得不提一下它的核心佇列同步器(AQS)了,它的全稱是AbstractQueuedSynchronizer,是用來構建鎖或者其他一些同步元件的基礎,除了ReentrantLock、ReentrantReadWriteLock外,它還在CountDownLatch、Semaphore以及ThreadPoolExecutor中被使用,透過理解佇列同步器的工作原理,對我們瞭解和使用這些工具類會有很大的幫助。
1、AQS 基礎
為了便於理解AQS的概念,首先摘錄部分AbstractQueuedSynchronizer的註釋進行簡要翻譯:
它提供了一個框架,對於依賴先進先出等待佇列的阻塞鎖和同步器(例如訊號量和事件),可以用它來實現。這個類的設計,對於大多數依賴於單個原子值來表示狀態(state)的同步器,可以提供有力的基礎。子類需要重寫被protected修飾的方法,例如更改狀態(state),定義在獲取或釋放物件時這些狀態表示的含義。基於這些,類中的其他方法實現了佇列和阻塞機制。在子類中可以維護其他的狀態欄位,但是隻有使用getState,setState,compareAndSetState方法原子更新的狀態值變數,才與同步有關。
子類被推薦定義為非public的內部類,用來實現封閉類的屬性同步。同步器本身沒有實現任何同步介面,它僅僅定義了一些方法,供具體的鎖和同步元件中的public方法呼叫。
佇列同步器支援獨佔模式和共享模式,當一個執行緒在獨佔模式下獲取時,其他執行緒不能獲取成功,在共享模式下多執行緒的獲取可能成功。在不同模式下,等待的執行緒使用的是相同的先進先出佇列。通常,實現子類只支援其中的一種模式,但是在ReadWriteLock中兩者都可以發揮作用。只支援一種模式的子類在實現時不需要重寫另一種模式中的方法。
閱讀這些註釋,可以知道AbstractQueuedSynchronizer是一個抽象類,它基於內部先進先出(FIFO)的雙向佇列、以及內建的一些protected方法來實現同步器,完成同步狀態的管理,並且我們可以透過子類繼承AQS抽象類的方式,在共享模式或獨佔模式下,實現自定義的同步元件。
透過上面的描述,可以看出AQS中的兩大核心是同步狀態和雙向的同步佇列,來看一下原始碼中是如何對它們進行定義的:
public abstract class AbstractQueuedSynchronizer extends AbstractOwnableSynchronizer implements java.io.Serializable { static final class Node { volatile int waitStatus; volatile Node prev; volatile Node next; volatile Thread thread; //... } private transient volatile Node head; private transient volatile Node tail; private volatile int state; //...}
下面針對這兩個核心內容分別進行研究。
同步佇列
AQS內部靜態類Node用於表示同步佇列中的節點,變量表示的意義如下:
prev:當前節點的前驅節點,如果當前節點是同步佇列的頭節點,那麼prev為nullnext:當前節點的後繼節點,如果當前節點是同步佇列的尾節點,那麼next為nullthread:獲取同步狀態的執行緒waitStatus:等待狀態,取值可為以下情況 CANCELLED(1):表示當前節點對應的執行緒被取消,當執行緒等待超時或被中斷時會被修改為此狀態SIGNAL(-1):當前節點的後繼節點的執行緒被阻塞,當前執行緒在釋放同步狀態或取消時,需要喚醒後繼節點的執行緒CONDITION(-2):節點處於等待佇列中,節點執行緒等待在Condition上,當其他執行緒呼叫Condition的signal方法後,會將節點從等待佇列移到同步佇列PROPAGATE(-3):表示下一次共享式同步狀態獲取能夠被執行,即同步狀態的獲取可以向後繼節點的後繼進行無條件的傳播0:初始值,表示當前節點等待獲取同步狀態每個節點的prev和next指標在加入佇列的時候進行賦值,透過這些指標就形成了一個雙向列表,另外AQS還儲存了同步佇列的頭節點head和尾節點tail,透過這樣的結構,就能夠透過頭節點或尾節點,找到佇列中的任何一個節點。使用圖來表示同步佇列的結構如下:
另外可以看到,在原始碼中為了保證可見性,同步器中的head、tail、state,以及節點中的prev,next屬性都加了關鍵字volatile修飾。
同步狀態
AQS的另一核心同步狀態,在程式碼中是使用int型別的變數state來表示的,透過原子操作修改同步狀態的值,來實現對同步元件的狀態進行修改。在子類中,主要透過AQS提供的下面3個方法對同步狀態的訪問和轉換進行操作:
getState():獲取當前的同步狀態setState(int newState): 設定新的同步狀態compareAndSetState(int expect,int update): 呼叫Unsafe類的compareAndSwapInt方法,使用CAS操作更新同步狀態,保證了狀態修改的原子性執行緒會試圖修改state的值,如果修改成功那麼表示執行緒得到或釋放了同步狀態,如果失敗就會將當前執行緒封裝成一個Node節點,然後將其加入到同步佇列中,並阻塞當前執行緒。
設計思想
AQS的設計使用了模板方法的設計模式,模板方法一般在父類中封裝不變的部分(如演算法骨架),把擴充套件的可變部分交給子類進行擴充套件,子類的執行結果會影響父類的結果,是一種反向的控制結構。AQS中應用了這種設計模式,將一部分方法交給子類進行重寫,而自定義的同步元件在呼叫同步器提供的模板方法(父類中的方法)時,又會呼叫子類重寫的方法。
以AQS類中常用於獲取鎖的acquire方法為例,它的程式碼如下:
public final void acquire(int arg) { if (!tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt();}
acquire方法被final修飾,不可以在子類中重寫,因為它是對外提供的模板方法,有相對具體和固定的執行邏輯。在acquire方法中呼叫了tryAcquire方法:
protected boolean tryAcquire(int arg) { throw new UnsupportedOperationException();}
可以看到帶有protected修飾的tryAcquire方法是一個空殼方法,並沒有定義實際獲取同步狀態的邏輯,這就需要我們在繼承AQS的子類中對齊進行重寫,從而達到擴充套件目的。在重寫過程中,就會用到上面提到的獲取和修改同步狀態的3個方法getState、setState和compareAndSetState。
以ReentrantLock中的方法呼叫為例,當呼叫ReentrantLock中的lock方法時,會呼叫繼承了AQS的內部類Sync的父類中的acquire方法,acquire方法再呼叫子類Sync的tryAcquire方法並返回boolean型別結果。
除了tryAcquire方法外,子類中還提供了其他可以重寫的方法,列出如下:
tryAcquire:獨佔式獲取同步狀態tryRelease:獨佔式釋放同步狀態tryAcquireShared:共享式獲取同步狀態tryReleaseShared:共享式釋放同步狀態isHeldExclusively:當前執行緒是否獨佔式的佔用同步狀態而我們在實現自定義的同步元件時,可以直接呼叫AQS提供的下面這些模板方法:
acquire:獨佔式獲取同步狀態,如果執行緒獲取同步狀態成功那麼方法返回,否則執行緒阻塞,進入同步佇列中acquireInterruptibly:在acquire基礎上,添加了響應中斷功能tryAcquireNanos:在acquireInterruptibly基礎上,添加了超時限制,超時會返回falseacquireShared:共享式獲取同步狀態,如果執行緒獲取同步狀態成功那麼方法返回,否則執行緒進入同步佇列中阻塞。與acquire不同,該方法允許多個執行緒同時獲取鎖acquireSharedInterruptibly:在acquireShared基礎上,可響應中斷tryAcquireSharedNanos:在acquireSharedInterruptibly基礎上,添加了超時限制release:獨佔式釋放同步狀態,將喚醒同步佇列中第一個節點的執行緒releaseShared:共享式釋放同步狀態getQueuedThreads:獲取等待在同步佇列上的執行緒集合從模板方法中可以看出,大多方法都是獨佔模式和共享模式對稱出現的,除去查詢等待執行緒方法外,可以將他們分為兩類:獨佔式獲取或釋放同步狀態、共享式獲取或釋放同步狀態,並且它們的核心都是acquire與release方法,其他方法只是在它們實現的基礎上做了部分的邏輯改動,增加了中斷和超時功能的支援。下面對主要的4個方法進行分析。
2、原始碼分析acquire
分析上面acquire方法中原始碼的執行流程:
1.首先呼叫tryAcquire嘗試獲取同步狀態,如果獲取成功,那麼直接返回
2.如果獲取同步狀態失敗,呼叫addWaiter方法生成新Node節點並加入同步佇列:
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節點,在同步佇列的隊尾節點不為空的情況下(說明同步佇列非空),呼叫compareAndSetTail方法以CAS的方式把新節點設定為同步佇列的隊尾節點。如果隊尾節點為空或新增新節點失敗,則呼叫enq方法:
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; } } }}
在同步佇列為空的情況下,會先建立一個新的空節點作為頭節點,然後透過CAS的方式將當前執行緒建立的Node設為尾節點。在for迴圈中,只有透過CAS將節點插入到隊尾後才會返回,否則就會重複迴圈,透過這樣的方式,能夠將併發新增節點的操作變為序列新增,保證了執行緒的安全性。這一過程可以使用下圖表示:
3.新增新節點完成後,呼叫acquireQueued方法,嘗試以自旋的方式獲取同步狀態:
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); }}
當新新增的Node的前驅節點是同步佇列的頭節點並且嘗試獲取同步狀態成功時,執行緒將Node設為頭節點並從自旋中退出,否則呼叫shouldParkAfterFailedAcquire方法判斷是否需要掛起:
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) { int ws = pred.waitStatus; if (ws == Node.SIGNAL) return true; if (ws > 0) { do { node.prev = pred = pred.prev; } while (pred.waitStatus > 0); pred.next = node; } else { compareAndSetWaitStatus(pred, ws, Node.SIGNAL); } return false;}
在該方法中,傳入的第一個Node型別的引數是當前節點的前驅節點,對其等待狀態進行判斷:
如果為SIGNAL狀態,那麼前驅節點釋放同步狀態或取消時都會通知後繼節點,因此可以將當前執行緒阻塞,返回true如果大於0,那麼為CANCEL狀態,表示前驅節點被取消,那麼一直向前回溯,找到一個不為CANCEL狀態的節點,並將當前節點的前驅指向它如果不是上面的兩種情況,那麼將前驅節點的等待狀態設為SIGNAL。這裡的目的是在每個節點進入阻塞狀態前將前驅節點的等待狀態設為SIGNAL,否則節點將無法被喚醒在後兩種情況下,都會返回false,然後在acquireQueued方法中進行迴圈,直到進入shouldParkAfterFailedAcquire方法時為第一種情況,阻塞執行緒當返回為true時,呼叫parkAndCheckInterrupt方法:
private final boolean parkAndCheckInterrupt() { LockSupport.park(this); return Thread.interrupted();}
在方法內部呼叫了LockSupport的park方法,阻塞當前執行緒,並返回當前執行緒是否被中斷的狀態。
在上面的程式碼中,各節點透過自旋的方式檢測自己的前驅節點是否頭節點的過程,可用下圖表示:
4.當滿足條件,返回acquire方法後,呼叫selfInterrupt方法。方法內部使用interrupt方法,喚醒被阻塞的執行緒,繼續向下執行:
static void selfInterrupt() { Thread.currentThread().interrupt();}
最後,使用流程圖的方式總結acquire方法獨佔式獲取鎖的整體流程:
release
與acquire方法對應,release方法負責獨佔式釋放同步狀態,流程也相對簡單。在ReentrantLock中,unlock方法就是直接呼叫的AQS的release方法。先來直接看一下它的原始碼:
public final boolean release(int arg) { if (tryRelease(arg)) { Node h = head; if (h != null && h.waitStatus != 0) unparkSuccessor(h); return true; } return false;}
1.方法中首先呼叫子類重寫的tryRelease方法,嘗試釋放當前執行緒持有的同步狀態,如果成功則向下執行,失敗返回false
2.如果同步佇列的頭節點不為空且等待狀態不為初始狀態,那麼將呼叫unparkSuccessor方法喚醒它的後繼節點:
private void unparkSuccessor(Node node) { int ws = node.waitStatus; if (ws < 0) compareAndSetWaitStatus(node, ws, 0); Node s = node.next; if (s == null || s.waitStatus > 0) { s = null; for (Node t = tail; t != null && t != node; t = t.prev) if (t.waitStatus <= 0) s = t; } if (s != null) LockSupport.unpark(s.thread);}
方法主要實現的功能有:
如果頭節點的等待狀態小於0,使用CAS將它置為0如果後續節點為空、或它的等待狀態為CANCEL被取消,那麼從隊尾開始,向前尋找最靠近佇列頭部的一個等待狀態小於0 的節點找到符合條件的節點後,呼叫LockSupport工具類的unpark方法,喚醒後繼節點中對應的執行緒同步佇列新頭節點的設定過程如下圖所示:
在上面的過程中,採用的是從後向前遍歷尋找未取消節點的方式,這是因為AQS的同步佇列是一個弱一致性的雙向列表,在下面的情況中,存在next指標為null的情況:
在enq方法插入新節點時,可能存在舊尾節點的next指標還未指向新節點的情況在shouldParkAfterFailedAcquire方法中,當移除CANCEL狀態的節點時,也存在next指標還未指向後續節點的情況acquireShared
在瞭解了獨佔式獲取同步狀態後,再來看一下共享式獲取同步狀態。在共享模式下,允許多個執行緒同時獲取到同步狀態,來看一下它的原始碼:
public final void acquireShared(int arg) { if (tryAcquireShared(arg) < 0) doAcquireShared(arg);}
首先呼叫子類重寫的tryAcquireShared方法,返回值為int型別,如果值大於等於0表示獲取同步狀態成功,那麼直接返回。如果小於0表示獲取失敗,執行下面的doAcquireShared方法,將執行緒放入等待佇列使用自旋嘗試獲取,直到獲取同步狀態成功:
private void doAcquireShared(int arg) { final Node node = addWaiter(Node.SHARED); boolean failed = true; try { boolean interrupted = false; for (;;) { final Node p = node.predecessor(); if (p == head) { int r = tryAcquireShared(arg); if (r >= 0) { setHeadAndPropagate(node, r); p.next = null; // help GC if (interrupted) selfInterrupt(); failed = false; return; } } if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt()) interrupted = true; } } finally { if (failed) cancelAcquire(node); }}
對上面的程式碼進行簡要的解釋:
1.呼叫addWaiter方法,封裝新節點,並以共享模式(Node.SHARED)將節點放入同步佇列中隊尾
2.在for迴圈中,獲取當前節點的前驅節點,如果前驅節點是同步佇列的頭節點,那麼就以共享模式去嘗試獲取同步狀態,判斷tryAcquireShared的返回值,如果返回值大於等於0,表示獲取同步狀態成功,修改新的頭節點,並將資訊傳播給同步佇列中的後繼節點,然後檢查中斷標誌位,如果執行緒被阻塞,那麼進行喚醒
3.如果前驅節點不是頭節點、或獲取同步狀態失敗時,呼叫shouldParkAfterFailedAcquire判斷是否需要阻塞,如果需要則呼叫parkAndCheckInterrupt,在前驅節點的等待狀態為SIGNAL時,將節點對應的執行緒阻塞
可以看到,共享式的獲取同步狀態的呼叫過程和acquire方法非常相似,但不同的是在獲取同步狀態成功後,會呼叫setHeadAndPropagate方法進行共享式同步狀態的傳播:
private void setHeadAndPropagate(Node node, int propagate) { Node h = head; // Record old head for check below setHead(node); if (propagate > 0 || h == null || h.waitStatus < 0 || (h = head) == null || h.waitStatus < 0) { Node s = node.next; if (s == null || s.isShared()) doReleaseShared(); }}
因為共享式同步狀態是允許多個執行緒共享的,所以在一個執行緒獲取到同步狀態後,需要在第一時間通知後繼節點的執行緒可以嘗試獲取同步資源,這樣就可以避免其他執行緒阻塞時間過長。在方法中,把當前節點設定為頭節點後,需要根據情況判斷後繼節點是否需要釋放:
propagate>0:表示還擁有剩餘的同步資源,從doAcquireShared方法中執行到這時,取值是大於等於0的,在等於0的情況下,會繼續下面的判斷h == null:原頭節點為空,一般情況下不滿足,有可能發生在原頭節點被gc回收的情況,此條不滿足情況則向下繼續判斷h.waitStatus < 0:原頭節點的等待狀態可能取值為0或-3 當某個執行緒釋放同步資源或者前一個節點共享式獲取同步狀態時(會執行下面的doReleaseShared方法),會將自己的waitStatus從-1改變為0 這時可能後繼節點還沒有來的及將自己更新為頭節點,如果有其他的執行緒在這個時候再呼叫doReleaseShared方法,那麼取到的還是原頭節點,會把它的waitStatus從0改變為-3,在這個過程中,說明其他執行緒呼叫doReleaseShared釋放了同步資源(h = head) == null:新頭節點為空,一般情況下不滿足,會向下繼續判斷h.waitStatus < 0:新頭節點的等待狀態可能取值為0或-3或-1 如果後繼節點剛加入佇列,還沒有執行到shouldParkAfterFailedAcquire方法,修改其前驅節點的等待狀態時,此時可能為0如果節點被喚醒成為了新的頭節點,並且此時後繼節點才剛被加入同步佇列,又有其他執行緒釋放鎖呼叫了doReleaseShared,會把頭節點的狀態從0改為-3佇列中的節點已經呼叫了shouldParkAfterFailedAcquire,會把waitStatus 從0或-3 改為-1如果滿足上面的任何一種狀態,並且它的後繼節點是SHARED狀態的,則執行doReleaseShared方法釋放後繼節點:
private void doReleaseShared() { for (;;) { Node h = head; if (h != null && h != tail) { int ws = h.waitStatus; if (ws == Node.SIGNAL) { if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0)) continue; // loop to recheck cases unparkSuccessor(h); } else if (ws == 0 && !compareAndSetWaitStatus(h, 0, Node.PROPAGATE)) continue; // loop on failed CAS } if (h == head) // loop if head changed break; }}
doReleaseShared方法不僅在這裡的共享狀態傳播的情況下被呼叫,還會在後面介紹的共享式釋放同步狀態中被呼叫。在方法中,當頭節點不為空且不等於尾節點(意味著沒有後繼節點需要等待喚醒)時:
先將頭節點從SIGNAL狀態更新為0,然後呼叫unparkSuccessor方法喚醒頭節點的後繼節點將頭節點的狀態從0更新為PROPAGATE,表明狀態需要向後繼節點傳播如果頭節點在更新狀態的時候沒有發生改變,則退出迴圈透過上面的流程,就實現了從頭節點嘗試向後喚醒節點,實現了共享狀態的向後傳播。
releaseShared
最後,再來看一下對應的共享式釋放同步狀態方法:
public final boolean releaseShared(int arg) { if (tryReleaseShared(arg)) { doReleaseShared(); return true; } return false; }
releaseShared方法會釋放指定量的資源,如果呼叫子類重寫的tryReleaseShared方法返回值為true,表示釋放成功,那麼還是執行上面介紹過的doReleaseShared方法喚醒同步佇列中的等待執行緒。
3、自定義同步元件
在前面的介紹中說過,在使用AQS時,需要定義一個子類繼承AbstractQueuedSynchronizer抽象類,並實現它的抽象方法來管理同步狀態。接下來我們就來手寫一個獨佔式的鎖,按照文件中的推薦,我們將子類定義為自定義同步工具類的靜態內部類:
public class MyLock { private static class AqsHelper extends AbstractQueuedSynchronizer { @Override protected boolean tryAcquire(int arg) { int state = getState(); if (state == 0) { if (compareAndSetState(0, arg)) { setExclusiveOwnerThread(Thread.currentThread()); return true; } } else if (getExclusiveOwnerThread() == Thread.currentThread()) { setState(getState() + arg); return true; } return false; } @Override protected boolean tryRelease(int arg) { int state = getState() - arg; if (state == 0) { setExclusiveOwnerThread(null); setState(state); return true; } setState(state); return false; } @Override protected boolean isHeldExclusively() { return getState() == 1; } } private final AqsHelper aqsHelper = new AqsHelper(); public void lock() { aqsHelper.acquire(1); } public boolean tryLock() { return aqsHelper.tryAcquire(1); } public void unlock() { aqsHelper.release(1); } public boolean isLocked() { return aqsHelper.isHeldExclusively(); }}
在AQS的子類中,首先重寫了tryAcquire方法,在方法中利用CAS來修改state的狀態值,並在修改成功時設定當前執行緒獨佔資源。並且透過比較嘗試獲取鎖的執行緒與持有鎖的執行緒是否相同的方式,來實現了鎖的可重入性。在重寫的tryRelease方法中,進行資源的釋放,如果存在重入的情況,會一直到所有重入鎖釋放完才會真正的釋放鎖,並放棄佔有狀態。
可以注意到在自定義的鎖工具類中,我們定義了lock和tryLock兩個方法,分別呼叫了acquire和tryAcquire方法,它們的區別是lock會等待鎖資源,直到成功時才會返回,而tryLock嘗試獲取鎖時,會立即返回成功或失敗的狀態。
接下來,我們透過下面的測試程式碼,驗證自定義的鎖的有效性:
public class Test { private MyLock lock=new MyLock(); private int i=0; public void sayHi(){ try { lock.lock(); System.out.println("i am "+i++); }finally { lock.unlock(); } } public static void main(String[] args) { Test test=new Test(); Thread[] th=new Thread[20]; for (int i = 0; i < 20; i++) { new Thread(()->{ test.sayHi(); }).start(); } }}
執行上面的測試程式碼,結果如下,可以看見透過加鎖保證了對變數i的同步訪問控制:
接下來透過下面的例子測試鎖的可重入性:
public class Test2 { private MyLock lock=new MyLock(); public void function1(){ lock.lock(); System.out.println("execute function1"); function2(); lock.unlock(); } public void function2(){ lock.lock(); System.out.println("execute function2"); lock.unlock(); } public static void main(String[] args) { Test2 test2=new Test2(); new Thread(()->{ test2.function1(); }).start(); }}
執行上面的程式碼,可以看到在function1未釋放鎖的情況下,function2對鎖進行了重入並執行了後續的程式碼:
總結
透過上面的學習,我們瞭解了AQS的兩大核心同步佇列和同步狀態,並對AQS對資源的管理以及佇列狀態的變化有了一定的研究。其實歸根結底,AQS只是提供給我們來開發同步元件的一個底層框架,在它的層面上,並不關心子類在繼承它時要實現什麼功能,AQS只是提供了一套維護同步狀態的功能,至於要完成什麼樣的一個工具類,這完全是由我們自己去定義的。