本文分析JVM中的另一種鎖Lock的實(shí)現(xiàn)。與synchronized不同的是，Lock完全用Java寫(xiě)成，在java這個(gè)層面是無(wú)關(guān)JVM實(shí)現(xiàn)的。

在java.util.concurrent.locks包中有很多Lock的實(shí)現(xiàn)類(lèi)，常用的有ReentrantLock、ReadWriteLock（實(shí)現(xiàn)類(lèi)ReentrantReadWriteLock），其實(shí)現(xiàn)都依賴java.util.concurrent.AbstractQueuedSynchronizer類(lèi)，實(shí)現(xiàn)思路都大同小異，因此我們以ReentrantLock作為講解切入點(diǎn)。

1. ReentrantLock的調(diào)用過(guò)程
   經(jīng)過(guò)觀察ReentrantLock把所有Lock接口的操作都委派到一個(gè)Sync類(lèi)上，該類(lèi)繼承了AbstractQueuedSynchronizer：

static abstract class Sync extends AbstractQueuedSynchronizer  

Sync又有兩個(gè)子類(lèi)：

final static class NonfairSync extends Sync  
final static class FairSync extends Sync  

顯然是為了支持公平鎖和非公平鎖而定義，默認(rèn)情況下為非公平鎖。
先理一下Reentrant.lock()方法的調(diào)用過(guò)程（默認(rèn)非公平鎖）：

lock

這些討厭的Template模式導(dǎo)致很難直觀的看到整個(gè)調(diào)用過(guò)程，其實(shí)通過(guò)上面調(diào)用過(guò)程及AbstractQueuedSynchronizer的注釋可以發(fā)現(xiàn)，AbstractQueuedSynchronizer中抽象了絕大多數(shù)Lock的功能，而只把tryAcquire方法延遲到子類(lèi)中實(shí)現(xiàn)。tryAcquire方法的語(yǔ)義在于用具體子類(lèi)判斷請(qǐng)求線程是否可以獲得鎖，無(wú)論成功與否AbstractQueuedSynchronizer都將處理后面的流程。

2. 鎖實(shí)現(xiàn)（加鎖）

簡(jiǎn)單說(shuō)來(lái)，AbstractQueuedSynchronizer會(huì)把所有的請(qǐng)求線程構(gòu)成一個(gè)CLH隊(duì)列，當(dāng)一個(gè)線程執(zhí)行完畢（lock.unlock()）時(shí)會(huì)激活自己的后繼節(jié)點(diǎn)，但正在執(zhí)行的線程并不在隊(duì)列中，而那些等待執(zhí)行的線程全部處于阻塞狀態(tài)，經(jīng)過(guò)調(diào)查線程的顯式阻塞是通過(guò)調(diào)用LockSupport.park()完成，而LockSupport.park()則調(diào)用sun.misc.Unsafe.park()本地方法，再進(jìn)一步，HotSpot在Linux中中通過(guò)調(diào)用pthread_mutex_lock函數(shù)把線程交給系統(tǒng)內(nèi)核進(jìn)行阻塞。
該隊(duì)列如圖：

Paste_Image.png

與synchronized相同的是，這也是一個(gè)虛擬隊(duì)列，不存在隊(duì)列實(shí)例，僅存在節(jié)點(diǎn)之間的前后關(guān)系。令人疑惑的是為什么采用CLH隊(duì)列呢？原生的CLH隊(duì)列是用于自旋鎖，但Doug Lea把其改造為阻塞鎖。
當(dāng)有線程競(jìng)爭(zhēng)鎖時(shí)，該線程會(huì)首先嘗試獲得鎖，這對(duì)于那些已經(jīng)在隊(duì)列中排隊(duì)的線程來(lái)說(shuō)顯得不公平，這也是非公平鎖的由來(lái)，與synchronized實(shí)現(xiàn)類(lèi)似，這樣會(huì)極大提高吞吐量。
如果已經(jīng)存在Running線程，則新的競(jìng)爭(zhēng)線程會(huì)被追加到隊(duì)尾，具體是采用基于CAS的Lock-Free算法，因?yàn)榫€程并發(fā)對(duì)Tail調(diào)用CAS可能會(huì)導(dǎo)致其他線程CAS失敗，解決辦法是循環(huán)CAS直至成功。AbstractQueuedSynchronizer的實(shí)現(xiàn)非常精巧，令人嘆為觀止，不入細(xì)節(jié)難以完全領(lǐng)會(huì)其精髓，下面詳細(xì)說(shuō)明實(shí)現(xiàn)過(guò)程：

2.1 Sync.nonfairTryAcquire

nonfairTryAcquire方法將是lock方法間接調(diào)用的第一個(gè)方法，每次請(qǐng)求鎖時(shí)都會(huì)首先調(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;
        }

該方法會(huì)首先判斷當(dāng)前狀態(tài)，如果c==0說(shuō)明沒(méi)有線程正在競(jìng)爭(zhēng)該鎖，如果不c !=0 說(shuō)明有線程正擁有了該鎖。
如果發(fā)現(xiàn)c==0，則通過(guò)CAS設(shè)置該狀態(tài)值為acquires,acquires的初始調(diào)用值為1，每次線程重入該鎖都會(huì)+1，每次unlock都會(huì)-1，但為0時(shí)釋放鎖。如果CAS設(shè)置成功，則可以預(yù)計(jì)其他任何線程調(diào)用CAS都不會(huì)再成功，也就認(rèn)為當(dāng)前線程得到了該鎖，也作為Running線程，很顯然這個(gè)Running線程并未進(jìn)入等待隊(duì)列。
如果c !=0 但發(fā)現(xiàn)自己已經(jīng)擁有鎖，只是簡(jiǎn)單地++acquires，并修改status值，但因?yàn)闆](méi)有競(jìng)爭(zhēng)，所以通過(guò)setStatus修改，而非CAS，也就是說(shuō)這段代碼實(shí)現(xiàn)了偏向鎖的功能，并且實(shí)現(xiàn)的非常漂亮。

2.2 AbstractQueuedSynchronizer.addWaiter

addWaiter方法負(fù)責(zé)把當(dāng)前無(wú)法獲得鎖的線程包裝為一個(gè)Node添加到隊(duì)尾：

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;  
}  

其中參數(shù)mode是獨(dú)占鎖還是共享鎖，默認(rèn)為null，獨(dú)占鎖。追加到隊(duì)尾的動(dòng)作分兩步：

1. 如果當(dāng)前隊(duì)尾已經(jīng)存在(tail!=null)，則使用CAS把當(dāng)前線程更新為T(mén)ail
2. 如果當(dāng)前Tail為null或則線程調(diào)用CAS設(shè)置隊(duì)尾失敗，則通過(guò)enq方法繼續(xù)設(shè)置Tail
   下面是enq方法：

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ā)的場(chǎng)景，無(wú)限循環(huán)將會(huì)最終成功把當(dāng)前線程追加到隊(duì)尾（或設(shè)置隊(duì)頭）?？偠灾?，addWaiter的目的就是通過(guò)CAS把當(dāng)前現(xiàn)在追加到隊(duì)尾，并返回包裝后的Node實(shí)例。
把線程要包裝為Node對(duì)象的主要原因，除了用Node構(gòu)造供虛擬隊(duì)列外，還用Node包裝了各種線程狀態(tài)，這些狀態(tài)被精心設(shè)計(jì)為一些數(shù)字值：

• SIGNAL(-1) ：線程的后繼線程正/已被阻塞，當(dāng)該線程release或cancel時(shí)要重新這個(gè)后繼線程(unpark)
• CANCELLED(1)：因?yàn)槌瑫r(shí)或中斷，該線程已經(jīng)被取消
• CONDITION(-2)：表明該線程被處于條件隊(duì)列，就是因?yàn)檎{(diào)用了Condition.await而被阻塞
• PROPAGATE(-3)：傳播共享鎖
• 0：0代表無(wú)狀態(tài)

2.3 AbstractQueuedSynchronizer.acquireQueued

acquireQueued的主要作用是把已經(jīng)追加到隊(duì)列的線程節(jié)點(diǎn)（addWaiter方法返回值）進(jìn)行阻塞，但阻塞前又通過(guò)tryAccquire重試是否能獲得鎖，如果重試成功能則無(wú)需阻塞，直接返回

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;  
    }  
}  

仔細(xì)看看這個(gè)方法是個(gè)無(wú)限循環(huán)，感覺(jué)如果p == head && tryAcquire(arg)條件不滿足循環(huán)將永遠(yuǎn)無(wú)法結(jié)束，當(dāng)然不會(huì)出現(xiàn)死循環(huán)，奧秘在于第12行的parkAndCheckInterrupt會(huì)把當(dāng)前線程掛起，從而阻塞住線程的調(diào)用棧。

private final boolean parkAndCheckInterrupt() {  
    LockSupport.park(this);  
    return Thread.interrupted();  
}  

如前面所述，LockSupport.park最終把線程交給系統(tǒng)（linux）內(nèi)核進(jìn)行阻塞。當(dāng)然也不是馬上把請(qǐng)求不到鎖的線程進(jìn)行阻塞，還要檢查該線程的狀態(tài)，比如如果該線程處于Cancel狀態(tài)則沒(mé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é)點(diǎn)狀態(tài)為SIGNAL，表明當(dāng)前節(jié)點(diǎn)需要unpark，則返回成功，此時(shí)acquireQueued方法的第12行（parkAndCheckInterrupt）將導(dǎo)致線程阻塞
• 規(guī)則2：如果前繼節(jié)點(diǎn)狀態(tài)為CANCELLED(ws>0)，說(shuō)明前置節(jié)點(diǎn)已經(jīng)被放棄，則回溯到一個(gè)非取消的前繼節(jié)點(diǎn)，返回false，acquireQueued方法的無(wú)限循環(huán)將遞歸調(diào)用該方法，直至規(guī)則1返回true，導(dǎo)致線程阻塞
• 規(guī)則3：如果前繼節(jié)點(diǎn)狀態(tài)為非SIGNAL、非CANCELLED，則設(shè)置前繼的狀態(tài)為SIGNAL，返回false后進(jìn)入acquireQueued的無(wú)限循環(huán)，與規(guī)則2同

總體看來(lái)，shouldParkAfterFailedAcquire就是靠前繼節(jié)點(diǎn)判斷當(dāng)前線程是否應(yīng)該被阻塞，如果前繼節(jié)點(diǎn)處于CANCELLED狀態(tài)，則順便刪除這些節(jié)點(diǎn)重新構(gòu)造隊(duì)列。
至此，鎖住線程的邏輯已經(jīng)完成，下面討論解鎖的過(guò)程。

3. 解鎖

請(qǐng)求鎖不成功的線程會(huì)被掛起在acquireQueued方法的第12行，12行以后的代碼必須等線程被解鎖鎖才能執(zhí)行，假如被阻塞的線程得到解鎖，則執(zhí)行第13行，即設(shè)置interrupted = true，之后又進(jìn)入無(wú)限循環(huán)。

從無(wú)限循環(huán)的代碼可以看出，并不是得到解鎖的線程一定能獲得鎖，必須在第6行中調(diào)用tryAccquire重新競(jìng)爭(zhēng)，因?yàn)殒i是非公平的，有可能被新加入的線程獲得，從而導(dǎo)致剛被喚醒的線程再次被阻塞，這個(gè)細(xì)節(jié)充分體現(xiàn)了“非公平”的精髓。通過(guò)之后將要介紹的解鎖機(jī)制會(huì)看到，第一個(gè)被解鎖的線程就是Head，因此p == head的判斷基本都會(huì)成功。

至此可以看到，把tryAcquire方法延遲到子類(lèi)中實(shí)現(xiàn)的做法非常精妙并具有極強(qiáng)的可擴(kuò)展性，令人嘆為觀止！當(dāng)然精妙的不是這個(gè)Templae設(shè)計(jì)模式，而是Doug Lea對(duì)鎖結(jié)構(gòu)的精心布局。

解鎖代碼相對(duì)簡(jiǎn)單，主要體現(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語(yǔ)義相同，把如何釋放的邏輯延遲到子類(lèi)中。tryRelease語(yǔ)義很明確：如果線程多次鎖定，則進(jìn)行多次釋放，直至status==0則真正釋放鎖，所謂釋放鎖即設(shè)置status為0，因?yàn)闊o(wú)競(jìng)爭(zhēng)所以沒(méi)有使用CAS。

release的語(yǔ)義在于：如果可以釋放鎖，則喚醒隊(duì)列第一個(gè)線程（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);  
}  

這段代碼的意思在于找出第一個(gè)可以u(píng)npark的線程，一般說(shuō)來(lái)head.next == head，Head就是第一個(gè)線程，但Head.next可能被取消或被置為null，因此比較穩(wěn)妥的辦法是從后往前找第一個(gè)可用線程。貌似回溯會(huì)導(dǎo)致性能降低，其實(shí)這個(gè)發(fā)生的幾率很小，所以不會(huì)有性能影響。之后便是通知系統(tǒng)內(nèi)核繼續(xù)該線程，在Linux下是通過(guò)pthread_mutex_unlock完成。之后，被解鎖的線程進(jìn)入上面所說(shuō)的重新競(jìng)爭(zhēng)狀態(tài)。

4. Lock VS Synchronized

AbstractQueuedSynchronizer通過(guò)構(gòu)造一個(gè)基于阻塞的CLH隊(duì)列容納所有的阻塞線程，而對(duì)該隊(duì)列的操作均通過(guò)Lock-Free（CAS）操作，但對(duì)已經(jīng)獲得鎖的線程而言，ReentrantLock實(shí)現(xiàn)了偏向鎖的功能。

synchronized的底層也是一個(gè)基于CAS操作的等待隊(duì)列，但JVM實(shí)現(xiàn)的更精細(xì)，把等待隊(duì)列分為ContentionList和EntryList，目的是為了降低線程的出列速度；當(dāng)然也實(shí)現(xiàn)了偏向鎖，從數(shù)據(jù)結(jié)構(gòu)來(lái)說(shuō)二者設(shè)計(jì)沒(méi)有本質(zhì)區(qū)別。但synchronized還實(shí)現(xiàn)了自旋鎖，并針對(duì)不同的系統(tǒng)和硬件體系進(jìn)行了優(yōu)化，而Lock則完全依靠系統(tǒng)阻塞掛起等待線程。

當(dāng)然Lock比synchronized更適合在應(yīng)用層擴(kuò)展，可以繼承AbstractQueuedSynchronizer定義各種實(shí)現(xiàn)，比如實(shí)現(xiàn)讀寫(xiě)鎖（ReadWriteLock），公平或不公平鎖；同時(shí)，Lock對(duì)應(yīng)的Condition也比wait/notify要方便的多、靈活的多。

參考

http://blog.csdn.net/chen77716/article/details/6641477
http://blog.csdn.net/chen77716/article/details/6618779