深入JVM鎖機制之二：Lock
前文（深入JVM鎖機制-synchronized）分析了JVM中的synchronized實現(xiàn)，本文繼續(xù)分析JVM中的另一種鎖Lock的實現(xiàn)。與synchronized不同的是，Lock完全用Java寫成，在java這個層面是無關JVM實現(xiàn)的。
在java.util.concurrent.locks包中有很多Lock的實現(xiàn)類，常用的有ReentrantLock、ReadWriteLock（實現(xiàn)類ReentrantReadWriteLock），其實現(xiàn)都依賴java.util.concurrent.AbstractQueuedSynchronizer類，實現(xiàn)思路都大同小異，因此我們以ReentrantLock作為講解切入點。
1. ReentrantLock的調(diào)用過程
經(jīng)過觀察ReentrantLock把所有Lock接口的操作都委派到一個Sync類上，該類繼承了AbstractQueuedSynchronizer：
- static abstract class Sync extends AbstractQueuedSynchronizer
Sync又有兩個子類：
- final static class NonfairSync extends Sync
- final static class FairSync extends Sync
顯然是為了支持公平鎖和非公平鎖而定義，默認情況下為非公平鎖。
先理一下Reentrant.lock()方法的調(diào)用過程（默認非公平鎖）：
這些討厭的Template模式導致很難直觀的看到整個調(diào)用過程，其實通過上面調(diào)用過程及AbstractQueuedSynchronizer的注釋可以發(fā)現(xiàn)，AbstractQueuedSynchronizer中抽象了絕大多數(shù)Lock的功能，而只把tryAcquire方法延遲到子類中實現(xiàn)。tryAcquire方法的語義在于用具體子類判斷請求線程是否可以獲得鎖，無論成功與否AbstractQueuedSynchronizer都將處理后面的流程。
2. 鎖實現(xiàn)（加鎖）
簡單說來，AbstractQueuedSynchronizer會把所有的請求線程構(gòu)成一個CLH隊列，當一個線程執(zhí)行完畢（lock.unlock()）時會激活自己的后繼節(jié)點，但正在執(zhí)行的線程并不在隊列中，而那些等待執(zhí)行的線程全部處于阻塞狀態(tài)，經(jīng)過調(diào)查線程的顯式阻塞是通過調(diào)用LockSupport.park()完成，而LockSupport.park()則調(diào)用sun.misc.Unsafe.park()本地方法，再進一步，HotSpot在Linux中中通過調(diào)用pthread_mutex_lock函數(shù)把線程交給系統(tǒng)內(nèi)核進行阻塞。
該隊列如圖：
與synchronized相同的是，這也是一個虛擬隊列，不存在隊列實例，僅存在節(jié)點之間的前后關系。令人疑惑的是為什么采用CLH隊列呢？原生的CLH隊列是用于自旋鎖，但Doug Lea把其改造為阻塞鎖。
當有線程競爭鎖時，該線程會首先嘗試獲得鎖，這對于那些已經(jīng)在隊列中排隊的線程來說顯得不公平，這也是非公平鎖的由來，與synchronized實現(xiàn)類似，這樣會極大提高吞吐量。
如果已經(jīng)存在Running線程，則新的競爭線程會被追加到隊尾，具體是采用基于CAS的Lock-Free算法，因為線程并發(fā)對Tail調(diào)用CAS可能會導致其他線程CAS失敗，解決辦法是循環(huán)CAS直至成功。AbstractQueuedSynchronizer的實現(xiàn)非常精巧，令人嘆為觀止，不入細節(jié)難以完全領會其精髓，下面詳細說明實現(xiàn)過程：
2.1 Sync.nonfairTryAcquire
nonfairTryAcquire方法將是lock方法間接調(diào)用的***個方法，每次請求鎖時都會首先調(diào)用該方法。
- final boolean nonfairTryAcquire(int acquires) {
- final Thread current = Thread.currentThread();
- int c = getState();
- if (c == 0) {
- if (compareAndSetState(0, acquires)) {
- setExclusiveOwnerThread(current);
- return true;
- }
- }
- else if (current == getExclusiveOwnerThread()) {
- int nextc = c + acquires;
- if (nextc < 0) // overflow
- throw new Error("Maximum lock count exceeded");
- setState(nextc);
- return true;
- }
- return false;
- }
該方法會首先判斷當前狀態(tài)，如果c==0說明沒有線程正在競爭該鎖，如果不c !=0 說明有線程正擁有了該鎖。
如果發(fā)現(xiàn)c==0，則通過CAS設置該狀態(tài)值為acquires,acquires的初始調(diào)用值為1，每次線程重入該鎖都會+1，每次unlock都會-1，但為0時釋放鎖。如果CAS設置成功，則可以預計其他任何線程調(diào)用CAS都不會再成功，也就認為當前線程得到了該鎖，也作為Running線程，很顯然這個Running線程并未進入等待隊列。
如果c !=0 但發(fā)現(xiàn)自己已經(jīng)擁有鎖，只是簡單地++acquires，并修改status值，但因為沒有競爭，所以通過setStatus修改，而非CAS，也就是說這段代碼實現(xiàn)了偏向鎖的功能，并且實現(xiàn)的非常漂亮。
2.2 AbstractQueuedSynchronizer.addWaiter
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;
- }
- 如果當前隊尾已經(jīng)存在(tail!=null)，則使用CAS把當前線程更新為Tail。
- 如果當前Tail為null或則線程調(diào)用CAS設置隊尾失敗，則通過enq方法繼續(xù)設置Tail。
- private Node enq(final Node node) {
- for (;;) {
- Node t = tail;
- if (t == null) { // Must initialize
- Node h = new Node(); // Dummy header
- h.next = node;
- node.prev = h;
- if (compareAndSetHead(h)) {
- tail = node;
- return h;
- }
- }
- else {
- node.prev = t;
- if (compareAndSetTail(t, node)) {
- t.next = node;
- return t;
- }
- }
- }
- }
該方法就是循環(huán)調(diào)用CAS，即使有高并發(fā)的場景，無限循環(huán)將會最終成功把當前線程追加到隊尾（或設置隊頭）?？偠灾琣ddWaiter的目的就是通過CAS把當前現(xiàn)在追加到隊尾，并返回包裝后的Node實例。
把線程要包裝為Node對象的主要原因，除了用Node構(gòu)造供虛擬隊列外，還用Node包裝了各種線程狀態(tài)，這些狀態(tài)被精心設計為一些數(shù)字值：
◆ SIGNAL(-1) ：線程的后繼線程正/已被阻塞，當該線程release或cancel時要重新這個后繼線程(unpark)。
◆ CANCELLED(1)：因為超時或中斷，該線程已經(jīng)被取消。
◆ CONDITION(-2)：表明該線程被處于條件隊列，就是因為調(diào)用了Condition.await而被阻塞。
◆ PROPAGATE(-3)：傳播共享鎖。
◆ 0：0代表無狀態(tài)。
2.3 AbstractQueuedSynchronizer.acquireQueued
acquireQueued的主要作用是把已經(jīng)追加到隊列的線程節(jié)點（addWaiter方法返回值）進行阻塞，但阻塞前又通過tryAccquire重試是否能獲得鎖，如果重試成功能則無需阻塞，直接返回
- final boolean acquireQueued(final Node node, int arg) {
- try {
- boolean interrupted = false;
- for (;;) {
- final Node p = node.predecessor();
- if (p == head && tryAcquire(arg)) {
- setHead(node);
- p.next = null; // help GC
- return interrupted;
- }
- if (shouldParkAfterFailedAcquire(p, node) &&
- parkAndCheckInterrupt())
- interrupted = true;
- }
- } catch (RuntimeException ex) {
- cancelAcquire(node);
- throw ex;
- }
- }
仔細看看這個方法是個無限循環(huán)，感覺如果p == head && tryAcquire(arg)條件不滿足循環(huán)將永遠無法結(jié)束，當然不會出現(xiàn)死循環(huán)，奧秘在于第12行的parkAndCheckInterrupt會把當前線程掛起，從而阻塞住線程的調(diào)用棧。
- private final boolean parkAndCheckInterrupt() {
- LockSupport.park(this);
- return Thread.interrupted();
- }
如前面所述，LockSupport.park最終把線程交給系統(tǒng)（Linux）內(nèi)核進行阻塞。當然也不是馬上把請求不到鎖的線程進行阻塞，還要檢查該線程的狀態(tài)，比如如果該線程處于Cancel狀態(tài)則沒有必要，具體的檢查在shouldParkAfterFailedAcquire中：
- private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
- int ws = pred.waitStatus;
- if (ws == Node.SIGNAL)
- /*
- * This node has already set status asking a release
- * to signal it, so it can safely park
- */
- return true;
- if (ws > 0) {
- /*
- * Predecessor was cancelled. Skip over predecessors and
- * indicate retry.
- */
- do {
- node.prev = pred = pred.prev;
- } while (pred.waitStatus > 0);
- pred.next = node;
- } else {
- /*
- * waitStatus must be 0 or PROPAGATE. Indicate that we
- * need a signal, but don't park yet. Caller will need to
- * retry to make sure it cannot acquire before parking.
- */
- compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
- }
- return false;
- }
檢查原則在于：
◆ 規(guī)則1：如果前繼的節(jié)點狀態(tài)為SIGNAL，表明當前節(jié)點需要unpark，則返回成功，此時acquireQueued方法的第12行（parkAndCheckInterrupt）將導致線程阻塞。
◆ 規(guī)則2：如果前繼節(jié)點狀態(tài)為CANCELLED(ws>0)，說明前置節(jié)點已經(jīng)被放棄，則回溯到一個非取消的前繼節(jié)點，返回false，acquireQueued方法的無限循環(huán)將遞歸調(diào)用該方法，直至規(guī)則1返回true，導致線程阻塞。
◆ 規(guī)則3：如果前繼節(jié)點狀態(tài)為非SIGNAL、非CANCELLED，則設置前繼的狀態(tài)為SIGNAL，返回false后進入acquireQueued的無限循環(huán)，與規(guī)則2同。
總體看來，shouldParkAfterFailedAcquire就是靠前繼節(jié)點判斷當前線程是否應該被阻塞，如果前繼節(jié)點處于CANCELLED狀態(tài)，則順便刪除這些節(jié)點重新構(gòu)造隊列。
至此，鎖住線程的邏輯已經(jīng)完成，下面討論解鎖的過程。
3. 解 鎖
請求鎖不成功的線程會被掛起在acquireQueued方法的第12行，12行以后的代碼必須等線程被解鎖鎖才能執(zhí)行，假如被阻塞的線程得到解鎖，則執(zhí)行第13行，即設置interrupted = true，之后又進入無限循環(huán)。
從無限循環(huán)的代碼可以看出，并不是得到解鎖的線程一定能獲得鎖，必須在第6行中調(diào)用tryAccquire重新競爭，因為鎖是非公平的，有可能被新加入的線程獲得，從而導致剛被喚醒的線程再次被阻塞，這個細節(jié)充分體現(xiàn)了“非公平”的精髓。通過之后將要介紹的解鎖機制會看到，***個被解鎖的線程就是Head，因此p == head的判斷基本都會成功。
至此可以看到，把tryAcquire方法延遲到子類中實現(xiàn)的做法非常精妙并具有極強的可擴展性，令人嘆為觀止！當然精妙的不是這個Templae設計模式，而是Doug Lea對鎖結(jié)構(gòu)的精心布局。
解鎖代碼相對簡單，主要體現(xiàn)在AbstractQueuedSynchronizer.release和Sync.tryRelease方法中：
class AbstractQueuedSynchronizer
- public final boolean release(int arg) {
- if (tryRelease(arg)) {
- Node h = head;
- if (h != null && h.waitStatus != 0)
- unparkSuccessor(h);
- return true;
- }
- return false;
- }
class Sync
- 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);
- return free;
- }
tryRelease與tryAcquire語義相同，把如何釋放的邏輯延遲到子類中。tryRelease語義很明確：如果線程多次鎖定，則進行多次釋放，直至status==0則真正釋放鎖，所謂釋放鎖即設置status為0，因為無競爭所以沒有使用CAS。
release的語義在于：如果可以釋放鎖，則喚醒隊列***個線程（Head），具體喚醒代碼如下：
- private void unparkSuccessor(Node node) {
- /*
- * If status is negative (i.e., possibly needing signal) try
- * to clear in anticipation of signalling. It is OK if this
- * fails or if status is changed by waiting thread.
- */
- int ws = node.waitStatus;
- if (ws < 0)
- compareAndSetWaitStatus(node, ws, 0);
- /*
- * Thread to unpark is held in successor, which is normally
- * just the next node. But if cancelled or apparently null,
- * traverse backwards from tail to find the actual
- * non-cancelled successor.
- */
- 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);
- }
這段代碼的意思在于找出***個可以unpark的線程，一般說來head.next == head，Head就是***個線程，但Head.next可能被取消或被置為null，因此比較穩(wěn)妥的辦法是從后往前找***個可用線程。貌似回溯會導致性能降低，其實這個發(fā)生的幾率很小，所以不會有性能影響。之后便是通知系統(tǒng)內(nèi)核繼續(xù)該線程，在Linux下是通過pthread_mutex_unlock完成。之后，被解鎖的線程進入上面所說的重新競爭狀態(tài)。
4. Lock VS Synchronized
AbstractQueuedSynchronizer通過構(gòu)造一個基于阻塞的CLH隊列容納所有的阻塞線程，而對該隊列的操作均通過Lock-Free（CAS）操作，但對已經(jīng)獲得鎖的線程而言，ReentrantLock實現(xiàn)了偏向鎖的功能。
synchronized的底層也是一個基于CAS操作的等待隊列，但JVM實現(xiàn)的更精細，把等待隊列分為ContentionList和EntryList，目的是為了降低線程的出列速度；當然也實現(xiàn)了偏向鎖，從數(shù)據(jù)結(jié)構(gòu)來說二者設計沒有本質(zhì)區(qū)別。但synchronized還實現(xiàn)了自旋鎖，并針對不同的系統(tǒng)和硬件體系進行了優(yōu)化，而Lock則完全依靠系統(tǒng)阻塞掛起等待線程。
當然Lock比synchronized更適合在應用層擴展，可以繼承AbstractQueuedSynchronizer定義各種實現(xiàn)，比如實現(xiàn)讀寫鎖（ReadWriteLock），公平或不公平鎖；同時，Lock對應的Condition也比wait/notify要方便的多、靈活的多。
原文鏈接：http://blog.csdn.net/chen77716/article/details/6641477
【編輯推薦】
