前言

JDK1.5以前只有synchronized同步鎖，并且效率非常低，因此大神Doug Lea自己寫了一套并發框架，這套框架的核心就在于AbstractQueuedSynchronizer類（即AQS），性能非常高，所以被引入JDK包中，即JUC，那么AQS是怎么實作的呢？本篇就是對AQS及其相關組件進行分析，了解其原理，并領略大神的優美而又精簡的代碼，

AbstractQueuedSynchronizer

AQS是JUC下最核心的類，沒有之一，所以我們先來分析一下這個類的資料結構，

AQS內部是使用了雙向鏈表將等待執行緒鏈接起來，當發生并發競爭的時候，就會初始化該佇列并讓執行緒進入睡眠等待喚醒，同時每個節點會根據是否為共享鎖標記狀態為共享模式或獨占模式，這個資料結構需要好好理解并牢牢記住，下面分析的組件都將基于此實作，

Lock

Lock是一個介面，提供了加/解鎖的通用API，JUC主要提供了兩種鎖，ReentrantLock和ReentrantReadWriteLock，前者是重入鎖，實作Lock介面，后者是讀寫鎖，本身并沒有實作Lock介面，而是其內部類ReadLock或WriteLock實作了Lock介面，先來看看Lock都提供了哪些介面：

// 普通加鎖，不可打斷；未獲取到鎖進入AQS阻塞
void lock();

// 可打斷鎖
void lockInterruptibly() throws InterruptedException;

// 嘗試加鎖，未獲取到鎖不阻塞，回傳標識
boolean tryLock();

// 帶超時時間的嘗試加鎖
boolean tryLock(long time, TimeUnit unit) throws InterruptedException;

// 解鎖
void unlock();

// 創建一個條件佇列
Condition newCondition();

看到這里讀者們可以先思考下，自己如何來實作上面這些介面，

ReentrantLock

加鎖

synchronized和ReentrantLock都是可重入的，后者使用更加靈活，也提供了更多的高級特性，但其本質的實作原理是差不多的（據說synchronized是借鑒了ReentrantLock的實作原理），ReentrantLock提供了兩個構造方法：

	public ReentrantLock() {
        sync = new NonfairSync();
    }

    public ReentrantLock(boolean fair) {
        sync = fair ? new FairSync() : new NonfairSync();
    }

有參構造是根據引數創建公平鎖或非公平鎖，而無參構造默認則是非公平鎖，因為非公平鎖性能非常高，并且大部分業務并不需要使用公平鎖，至于為什么非公平鎖性能很高，咱們接著往下看，

非公平鎖/公平鎖

lock

非公平鎖和公平鎖在實作上基本一致，只有個別的地方不同，因此下面會采用對比分析方法進行分析，
從lock方法開始：

    public void lock() {
        sync.lock();
    }

實際上是委托給了內部類Sync，該類實作了AQS（其它組件實作方法也基本上都是這個套路）；由于有公平和非公平兩種模式，因此該類又實作了兩個子類：FairSync和NonfairSync：

	// 非公平鎖
    final void lock() {
        if (compareAndSetState(0, 1))
            setExclusiveOwnerThread(Thread.currentThread());
        else
            acquire(1);
    }

	// 公平鎖
    final void lock() {
      	acquire(1);
    }

這里就是公平鎖和非公平鎖的第一個不同，非公平鎖首先會呼叫CAS將state從0改為1，如果能改成功則表示獲取到鎖，直接將exclusiveOwnerThread設定為當前執行緒，不用再進行后續操作；否則則同公平鎖一樣呼叫acquire方法獲取鎖，這個是在AQS中實作的模板方法：

    public final void acquire(int arg) {
        if (!tryAcquire(arg) &&
            acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            selfInterrupt();
    }

tryAcquire

這里兩種鎖唯一不同的實作就是tryAcquire方法，先來看非公平鎖的實作：

    protected final boolean tryAcquire(int acquires) {
        return nonfairTryAcquire(acquires);
    }

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

state=0表示還沒有被執行緒持有鎖，直接通過CAS修改，能修改成功的就獲取到鎖，修改失敗的執行緒先判斷exclusiveOwnerThread是不是當前執行緒，是則state+1，表示重入次數+1并回傳true，加鎖成功，否則則回傳false表示嘗試加鎖失敗并呼叫acquireQueued入隊，

    protected final boolean tryAcquire(int acquires) {
        final Thread current = Thread.currentThread();
        int c = getState();
        if (c == 0) {
            if (!hasQueuedPredecessors() &&
                compareAndSetState(0, acquires)) {
                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;
    }

    public final boolean hasQueuedPredecessors() {
        Node t = tail; // Read fields in reverse initialization order
        Node h = head;
        Node s;
        // 首尾不相等且頭結點執行緒不是當前執行緒則表示需要進入佇列
        return h != t &&
            ((s = h.next) == null || s.thread != Thread.currentThread());
    }

上面就是公平鎖的嘗試獲取鎖的代碼，可以看到基本和非公平鎖的代碼是一樣的，區別在于首次加鎖需要判斷是否已經有佇列存在，沒有才去加鎖，有則直接回傳false，

addWaiter

接著來看addWaiter方法，當嘗試加鎖失敗時，首先就會呼叫該方法創建一個Node節點并添加到佇列中去，

    private Node addWaiter(Node mode) {
        Node node = new Node(Thread.currentThread(), mode);
        Node pred = tail;
        // 尾節點不為null表示已經存在佇列，直接將當前執行緒作為尾節點
        if (pred != null) {
            node.prev = pred;
            if (compareAndSetTail(pred, node)) {
                pred.next = node;
                return node;
            }
        }
        // 尾結點不存在則表示還沒有初始化佇列，需要初始化佇列
        enq(node);
        return node;
    }

    private Node enq(final Node node) {
		// 自旋
        for (;;) {
            Node t = tail;
            if (t == null) { // 只會有一個執行緒設定頭節點成功 
                if (compareAndSetHead(new Node()))
                    tail = head;
            } else { // 其它設定頭節點失敗的都會自旋設定尾節點
                node.prev = t;
                if (compareAndSetTail(t, node)) {
                    t.next = node;
                    return t;
                }
            }
        }
    }

這里首先傳入了一個獨占模式的空節點，并根據該節點和當前執行緒創建了一個Node，然后判斷是否已經存在佇列，若存在則直接入隊，否則呼叫enq方法初始化佇列，提高效率，
此處還有一個非常細節的地方，為什么設定尾節點時都要先將之前的尾節點設定為node.pre的值呢，而不是在CAS之后再設定？比如像下面這樣：

if (compareAndSetTail(pred, node)) {
	node.prev = pred;
    pred.next = node;
    return node;
}

因為如果這樣做的話，在CAS設定完tail后會存在一瞬間的tail.pre=null的情況，而Doug Lea正是考慮到這種情況，不論何時獲取tail.pre都不會為null，

acquireQueued

接著看acquireQueued方法：

    final boolean acquireQueued(final Node node, int arg) {
    	// 為true表示存在需要取消加鎖的節點，僅從這段代碼可以看出，
    	// 除非發生例外，否則不會存在需要取消加鎖的節點，
        boolean failed = true;
        try {
        	// 打斷標記，因為呼叫的是lock方法，所以是不可打斷的
        	// （但實際上是打斷了的，只不過這里采用了一種**靜默**處理方式，稍后分析）
            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);
        }
    }

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

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

這里就是佇列中執行緒加鎖/睡眠的核心邏輯，首先判斷剛剛呼叫addWaiter方法添加到佇列的節點是否是頭節點，如果是則再次嘗試加鎖，這個剛剛分析過了，非公平鎖在這里就會再次搶一次鎖，搶鎖成功則設定為head節點并回傳打斷標記；否則則和公平鎖一樣呼叫shouldParkAfterFailedAcquire判斷是否應該呼叫park方法進入睡眠，

park細節

為什么在park前需要這么一個判斷呢？因為當前節點的執行緒進入park后只能被前一個節點喚醒，那前一個節點怎么知道有沒有后繼節點需要喚醒呢？因此當前節點在park前需要給前一個節點設定一個標識，即將waitStatus設定為Node.SIGNAL（-1），然后自旋一次再走一遍剛剛的流程，若還是沒有獲取到鎖，則呼叫parkAndCheckInterrupt進入睡眠狀態，

打斷

讀者可能會比較好奇Thread.interrupted這個方法是做什么用的，

    public static boolean interrupted() {
        return currentThread().isInterrupted(true);
    }

這個是用來判斷當前執行緒是否被打斷過，并清除打斷標記（若是被打斷過則會回傳true，并將打斷標記設定為false），所以呼叫lock方法時，通過interrupt也是會打斷睡眠的執行緒的，只是Doug Lea做了一個假象，讓用戶無感知；但有些場景又需要知道該執行緒是否被打斷過，所以acquireQueued最侄訓回傳interrupted打斷標記，如果是被打斷過，則回傳的true，并在acquire方法中呼叫selfInterrupt再次打斷當前執行緒（將打斷標記設定為true），
這里我們對比看看lockInterruptibly的實作：

    public void lockInterruptibly() throws InterruptedException {
        sync.acquireInterruptibly(1);
    }

    public final void acquireInterruptibly(int arg)
            throws InterruptedException {
        if (Thread.interrupted())
            throw new InterruptedException();
        if (!tryAcquire(arg))
            doAcquireInterruptibly(arg);
    }

    private void doAcquireInterruptibly(int arg)
        throws InterruptedException {
        final Node node = addWaiter(Node.EXCLUSIVE);
        boolean failed = true;
        try {
            for (;;) {
                final Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return;
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt())
                    throw new InterruptedException();
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

可以看到區別就在于使用lockInterruptibly加鎖被打斷后，是直接拋出InterruptedException例外，我們可以捕獲這個例外進行相應的處理，

取消

最后來看看cancelAcquire是如何取消加鎖的，該情況比較特殊，簡單了解下即可：

    private void cancelAcquire(Node node) {
        if (node == null)
            return;

		// 首先將執行緒置空
        node.thread = null;

		// waitStatus > 0表示節點處于取消狀態，則直接將當前節點的pre指向在此之前的最后一個有效節點
        Node pred = node.prev;
        while (pred.waitStatus > 0)
            node.prev = pred = pred.prev;
		
		// 保存前一個節點的下一個節點，如果在此之前存在取消節點，這里就是之前取消被取消節點的頭節點
        Node predNext = pred.next;
        
        node.waitStatus = Node.CANCELLED;

		// 當前節點是tail節點，則替換尾節點，替換成功則將新的尾結點的下一個節點設定為null；
		// 否則需要判斷是將當前節點的下一個節點賦值給最后一個有效節點，還是喚醒下一個節點，
        if (node == tail && compareAndSetTail(node, pred)) {
            compareAndSetNext(pred, predNext, null);
        } else {
            int ws;
            if (pred != head &&
                ((ws = pred.waitStatus) == Node.SIGNAL ||
                 (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) &&
                pred.thread != null) {
                Node next = node.next;
                if (next != null && next.waitStatus <= 0)
                    compareAndSetNext(pred, predNext, next);
            } else {
                unparkSuccessor(node);
            }

            node.next = node; // help GC
        }
    }

解鎖

    public void unlock() {
        sync.release(1);
    }

    public final boolean release(int arg) {
        if (tryRelease(arg)) {
            Node h = head;
            if (h != null && h.waitStatus != 0)
                unparkSuccessor(h);
            return true;
        }
        return false;
    }

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

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

解鎖就比較簡單了，先呼叫tryRelease對state執行減一操作，如果state==0，則表示完全釋放鎖；若果存在后繼節點，則呼叫unparkSuccessor喚醒后繼節點，喚醒后的節點的waitStatus會重新被設定為0.
只是這里有一個小細節，為什么是從后向前找呢？因為我們在開始說過，設定尾節點保證了node.pre不會為null，但pre.next仍有可能是null，所以這里只能從后向前找到最后一個有效節點，

小結

上面是ReentrantLock的加鎖流程，可以看到整個流程不算復雜，只是判斷和跳轉比較多，主要是Doug Lea將代碼和性能都優化到了極致，代碼非常精簡，但細節卻非常多，另外通過上面的分析，我們也可以發現，公平鎖和非公平鎖的區別就在于非公平鎖不管是否有執行緒在排隊，先搶三次鎖，而公平鎖則會判斷是否存在佇列，有執行緒在排隊則直接進入佇列排隊；另外執行緒在park被喚醒后非公平鎖還會搶鎖，公平鎖仍然需要排隊，所以非公平鎖的性能比公平鎖高很多，大部分情況下我們使用非公平鎖即可，

ReentrantReadWriteLock

ReentrantLock是一把獨占鎖，只支持重入，不支持共享，所以JUC包下還提供了讀寫鎖，這把鎖支持讀讀并發，但讀寫、寫寫都是互斥的，
讀寫鎖也是基于AQS實作的，也包含了一個繼承自AQS的內部類Sync，同樣也有公平和非公平兩種模式，下面主要討論非公平模式下的讀寫鎖實作，
讀寫鎖實作相對比較復雜，在ReentrantLock中就是使用的int型的state屬性來表示鎖被某個執行緒占有和重入次數，而ReentrantReadWriteLock分為了讀和寫兩種鎖，要怎么用一個欄位表示兩種鎖的狀態呢？Doug Lea大師將state欄位分為了高二位元組和低二位元組，即高16位用來表示讀鎖狀態，低16位則用來表示寫鎖，如下圖：

因為讀寫鎖狀態都只用了兩個位元組，所以可重入的次數最多是65535，當然正常情況下重入是不可能達到這么多的，
那它是怎么實作的呢？還是先從構造方法開始：

    public ReentrantReadWriteLock() {
        this(false);
    }

    public ReentrantReadWriteLock(boolean fair) {
        sync = fair ? new FairSync() : new NonfairSync();
        readerLock = new ReadLock(this);
        writerLock = new WriteLock(this);
    }

同樣默認就是非公平鎖，同時還創建了readerLock和writerLock兩個物件，我們只需要像下面這樣就能獲取到讀寫鎖：

    private static ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
    private static Lock r = lock.readLock();
    private static Lock w = lock.writeLock();

寫鎖

由于寫鎖的加鎖程序相對更簡單，下面先從寫鎖加鎖開始分析，入口在ReentrantReadWriteLock#WriteLock.lock()方法，點進去看，發現還是使用的AQS中的acquire方法：

    public final void acquire(int arg) {
        if (!tryAcquire(arg) &&
            acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            selfInterrupt();
    }

所以不同的地方也只有tryAcquire方法，我們重點分析這個方法就行：

	static final int SHARED_SHIFT   = 16;
	// 65535
	static final int MAX_COUNT      = (1 << SHARED_SHIFT) - 1;
	// 低16位是1111....1111
	static final int EXCLUSIVE_MASK = (1 << SHARED_SHIFT) - 1;
	// 得到c低16位的值
	static int exclusiveCount(int c) { return c & EXCLUSIVE_MASK; }

    protected final boolean tryAcquire(int acquires) {
        Thread current = Thread.currentThread();
        int c = getState();
        // 獲取寫鎖加鎖和重入的次數
        int w = exclusiveCount(c);
        if (c != 0) { // 已經有執行緒持有鎖
        	// 這里有兩種情況：1. c!=0 && w==0表示有執行緒獲取了讀鎖，不論是否是當前執行緒，直接回傳false，
        	// 也就是說讀-寫鎖是不支持升級重入的（但支持寫-讀降級），原因后文會詳細分析；
        	// 2. c!=0 && w!=0 && current != getExclusiveOwnerThread()表示有其它執行緒持有了寫鎖，寫寫互斥
            if (w == 0 || current != getExclusiveOwnerThread())
                return false;

			// 超出65535，拋例外
            if (w + exclusiveCount(acquires) > MAX_COUNT)
                throw new Error("Maximum lock count exceeded");
            // 否則寫鎖的次數直接加1
            setState(c + acquires);
            return true;
        }

		// c==0才會走到這，但這時存在兩種情況，有佇列和無佇列，所以公平鎖和非公平鎖處理不同，
		// 前者需要判斷是否存在佇列，有則嘗試加鎖失敗，無則加鎖成功，而非公平鎖直接使用CAS加鎖即可
        if (writerShouldBlock() ||
            !compareAndSetState(c, c + acquires))
            return false;
        setExclusiveOwnerThread(current);
        return true;
    }

寫鎖嘗試加鎖的程序就分析完了，其余的部分上文已經講過，這里不再贅述，

讀鎖

    public void lock() {
        sync.acquireShared(1);
    }

    public final void acquireShared(int arg) {
        if (tryAcquireShared(arg) < 0)
            doAcquireShared(arg);
    }

讀鎖在加鎖開始就和其它鎖不同，呼叫的是acquireShared方法，意為獲取共享鎖，

	static final int SHARED_UNIT    = (1 << SHARED_SHIFT);
	// 右移16位得到讀鎖狀態的值
	static int sharedCount(int c)    { return c >>> SHARED_SHIFT; }
	
    protected final int tryAcquireShared(int unused) {
         Thread current = Thread.currentThread();
         int c = getState();
         // 為什么讀寫互斥？因為讀鎖一上來就判斷了是否有其它執行緒持有了寫鎖（當前執行緒持有寫鎖再獲取讀鎖是可以的）
         if (exclusiveCount(c) != 0 &&
             getExclusiveOwnerThread() != current)
             return -1;
         int r = sharedCount(c);
         // 公平鎖判斷是否存在佇列，非公平鎖判斷第一個節點是不是EXCLUSIVE模式，是的話會回傳true
         // 回傳false則需要判斷讀鎖加鎖次數是否超過65535，沒有則使用CAS給讀鎖+1
         if (!readerShouldBlock() &&
             r < MAX_COUNT &&
             compareAndSetState(c, c + SHARED_UNIT)) {
             if (r == 0) {
             	// 第一個讀鎖執行緒就是當前執行緒
                 firstReader = current;
                 firstReaderHoldCount = 1;
             } else if (firstReader == current) {
             	// 記錄讀鎖的重入
                 firstReaderHoldCount++;
             } else {
             	// 獲取最后一次加讀鎖的重入次數記錄器HoldCounter
                 HoldCounter rh = cachedHoldCounter;
                 if (rh == null || rh.tid != getThreadId(current))
                 	// 當前執行緒第一次重入需要初始化，以及當前執行緒和快取的最后一次記錄器的執行緒id不同，需要從ThreadLocalHoldCounter拿到對應的記錄器
                     cachedHoldCounter = rh = readHolds.get();
                 else if (rh.count == 0)
                 	// 快取到ThreadLocal
                     readHolds.set(rh);
                 rh.count++;
             }
             return 1;
         }
         return fullTryAcquireShared(current);
     }

這段代碼有點復雜，首先需要保證讀寫互斥，然后進行初次加鎖，若加鎖失敗就會呼叫fullTryAcquireShared方法進行兜底處理，在初次加鎖中與寫鎖不同的是，寫鎖的state可以直接用來記錄寫鎖的重入次數，因為寫寫互斥，但讀鎖是共享的，state用來記錄讀鎖的加鎖次數了，重入次數該怎么記錄呢？重入是指同一執行緒，那么是不是可以使用ThreadLocl來保存呢？沒錯，Doug Lea就是這么處理的，新增了一個HoldCounter類，這個類只有執行緒id和重入次數兩個欄位，當執行緒重入的時候就會初始化這個類并保存在ThreadLocalHoldCounter類中，這個類就是繼承ThreadLocl的，用來初始化HoldCounter物件并保存，
這里還有個小細節，為什么要使用cachedHoldCounter快取最后一次加讀鎖的HoldCounter？因為大部分情況下，重入和釋放鎖的執行緒很有可能就是最后一次加鎖的執行緒，所以這樣做能夠提高加解鎖的效率，Doug Lea真是把性能優化到了極致，
上面只是初次加鎖，有可能會加鎖失敗，就會進入到fullTryAcquireShared方法：

    final int fullTryAcquireShared(Thread current) {
        HoldCounter rh = null;
        for (;;) {
            int c = getState();
            if (exclusiveCount(c) != 0) {
                if (getExclusiveOwnerThread() != current)
                    return -1;
            } else if (readerShouldBlock()) {
                if (firstReader == current) {
                    // assert firstReaderHoldCount > 0;
                } else {
                    if (rh == null) {
                        rh = cachedHoldCounter;
                        if (rh == null || rh.tid != getThreadId(current)) {
                            rh = readHolds.get();
                            if (rh.count == 0)
                                readHolds.remove();
                        }
                    }
                    if (rh.count == 0)
                        return -1;
                }
            }
            if (sharedCount(c) == MAX_COUNT)
                throw new Error("Maximum lock count exceeded");
            if (compareAndSetState(c, c + SHARED_UNIT)) {
                if (sharedCount(c) == 0) {
                    firstReader = current;
                    firstReaderHoldCount = 1;
                } else if (firstReader == current) {
                    firstReaderHoldCount++;
                } else {
                    if (rh == null)
                        rh = cachedHoldCounter;
                    if (rh == null || rh.tid != getThreadId(current))
                        rh = readHolds.get();
                    else if (rh.count == 0)
                        readHolds.set(rh);
                    rh.count++;
                    cachedHoldCounter = rh; // cache for release
                }
                return 1;
            }
        }
    }

這個方法中代碼和tryAcquireShared基本上一致，只是采用了自旋的方式，處理初次加鎖中的漏網之魚，讀者們可自行閱讀分析，
上面兩個方法若回傳大于0則表示加鎖成功，小于0則會呼叫doAcquireShared方法，這個就和之前分析的acquireQueued差不多了：

    private void doAcquireShared(int arg) {
    	// 先添加一個SHARED型別的節點到佇列
        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) {
                    	// 設定head節點以及傳播喚醒后面的讀執行緒
                        setHeadAndPropagate(node, r);
                        p.next = null; // help GC
                        if (interrupted)
                            selfInterrupt();
                        failed = false;
                        return;
                    }
                }
                // 只有前一個節點的waitStatus=-1時才會park，=0或者-3（先不考慮-2和1的情況）都會設定為-1后再次自旋嘗試加鎖，若還是加鎖失敗就會park
                if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt())
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

    private void setHeadAndPropagate(Node node, int propagate) {
    	// 設定頭節點
        Node h = head; // Record old head for check below
        setHead(node);
        
        // propagate是tryAcquireShared的回傳值，當前執行緒加鎖成功還要去喚醒后繼的共享節點
        // （其余的判斷比較復雜，筆者也還未想明白，知道的讀者可以指點一下）
        if (propagate > 0 || h == null || h.waitStatus < 0 ||
            (h = head) == null || h.waitStatus < 0) {
            Node s = node.next;
            // 判斷后繼節點是否是共享節點
            if (s == null || s.isShared())
                doReleaseShared();
        }
    }

    private void doReleaseShared() {
        for (;;) {
            Node h = head;
            // 存在后繼節點
            if (h != null && h != tail) {
                int ws = h.waitStatus;
                if (ws == Node.SIGNAL) {
                	// 當前一個節點加鎖成功后自然需要將-1改回0，并喚醒后繼執行緒，同時自旋將0改為-2讓喚醒傳播下去
                    if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
                        continue;        
                    unparkSuccessor(h);
                }
                // 設定頭節點的waitStatus=-2，使得喚醒可以傳播下去
                else if (ws == 0 &&
                         !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
                    continue;             
            }
            if (h == head)          
                break;
        }
    }

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

這里的邏輯也非常的繞，當多個執行緒同時呼叫addWaiter添加到佇列中后，并且假設這些節點的第一個節點的前一個節點就是head節點，那么第一個節點就能加鎖成功（假設都是SHARED節點），其余的節點在第一個節點設定頭節點之前都會進入shouldParkAfterFailedAcquire方法，這時候waitStatus都等于0，所以繼續自旋不會park，若再次加鎖還失敗就會park（因為這時候waitStatus=-1），但都是讀執行緒的情況下一般都不會出現，因為setHeadAndPropagate第一步就是修改head，所以其余SHARED節點最終都能加鎖成功并一直將喚醒傳播下去，
以上就是讀寫鎖加鎖程序，解鎖比較簡單，這里就不詳細分析了，

小結

讀寫鎖將state分為了高二位元組和低二位元組，分別存盤讀鎖和寫鎖的狀態，實作更為的復雜，在使用上還有幾點需要注意：

• 讀讀共享，但是在讀中間穿插了寫的話，后面的讀都會被阻塞，直到前面的寫釋放鎖后，后面的讀才會共享，相關原理看完前文不難理解，
• 讀寫鎖只支持降級重入，不支持升級重入，因為如果支持升級重入的話，是會出現死鎖的，如下面這段代碼：

    private static void rw() {
        r.lock();
        try {
            log.info("獲取到讀鎖");
            w.lock();
            try {
                log.info("獲取到寫鎖");
            } finally {
                w.unlock();
            }
        } finally {
            r.unlock();
        }
    }

多個執行緒訪問都能獲取到讀鎖，但讀寫互斥，彼此都要等待對方的讀鎖釋放才能獲取到寫鎖，這就造成了死鎖，
ReentrantReadWriteLock在某些場景下性能上不算高，因此Doug Lea在JDK1.8的時候又提供了一把高性能的讀寫鎖StampedLock，前者讀寫鎖都是悲觀鎖，而后者提供了新的模式——樂觀鎖，但它不是基于AQS實作的，本文不進行分析，

Condition

Lock介面中還有一個方法newCondition，這個方法就是創建一個條件佇列：

    public Condition newCondition() {
        return sync.newCondition();
    }

    final ConditionObject newCondition() {
        return new ConditionObject();
    }

所謂條件佇列就是創建一個新的ConditionObject物件，這個物件的資料結構在開篇就看過了，包含首、尾兩個節點欄位，每當呼叫Condition#await方法時就會在對應的Condition物件中排隊等待：

    public final void await() throws InterruptedException {
        if (Thread.interrupted())
            throw new InterruptedException();
        // 加入條件佇列
        Node node = addConditionWaiter();
        // 因為Condition.await必須配合Lock.lock使用，所以await時就是將已獲得鎖的執行緒全部釋放掉
        int savedState = fullyRelease(node);
        int interruptMode = 0;
        // 判斷是在同步佇列還是條件佇列，后者則直接park
        while (!isOnSyncQueue(node)) {
            LockSupport.park(this);
            // 獲取打斷處理方式（拋出例外或重設標記）
            if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                break;
        }
        // 呼叫aqs的方法
        if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
            interruptMode = REINTERRUPT;
        if (node.nextWaiter != null) // clean up if cancelled
        	// 清除掉已經進入同步佇列的節點
            unlinkCancelledWaiters();
        if (interruptMode != 0)
            reportInterruptAfterWait(interruptMode);
    }

    private Node addConditionWaiter() {
        Node t = lastWaiter;
        // 清除狀態為取消的節點
        if (t != null && t.waitStatus != Node.CONDITION) {
            unlinkCancelledWaiters();
            t = lastWaiter;
        }

		// 創建一個CONDITION狀態的節點并添加到佇列末尾
        Node node = new Node(Thread.currentThread(), Node.CONDITION);
        if (t == null)
            firstWaiter = node;
        else
            t.nextWaiter = node;
        lastWaiter = node;
        return node;
    }

await方法實作比較簡單，大部分代碼都是上文分析過的，這里不再重復，接著來看signal方法：

    public final void signal() {
        if (!isHeldExclusively())
            throw new IllegalMonitorStateException();
        // 從條件佇列第一個節點開始喚醒
        Node first = firstWaiter;
        if (first != null)
            doSignal(first);
    }

    private void doSignal(Node first) {
        do {
            if ( (firstWaiter = first.nextWaiter) == null)
                lastWaiter = null;
            first.nextWaiter = null;
        } while (!transferForSignal(first) &&
                 (first = firstWaiter) != null);
    }

    final boolean transferForSignal(Node node) {
    	// 修改waitStatus狀態，如果修改失敗，則說明該節點已經從條件佇列轉移到了同步佇列
        if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
            return false;
		
		// 上面修改成功，則將該節點添加到同步佇列末尾，并回傳之前的尾結點
        Node p = enq(node);
        int ws = p.waitStatus;
        if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
        	// unpark當前執行緒，結合await方法看
            LockSupport.unpark(node.thread);
        return true;
    }

signal的邏輯也比較簡單，就是喚醒條件佇列中的第一個節點，主要是要結合await的代碼一起理解，

其它組件

上文分析的鎖都是用來實作并發安全控制的，而對于多執行緒協作JUC又基于AQS提供了CountDownLatch、CyclicBarrier、Semaphore等組件，下面一一分析，

CountDownLatch

CountDownLatch在創建的時候就需要指定一個計數：

CountDownLatch countDownLatch = new CountDownLatch(5);

然后在需要等待的地方呼叫countDownLatch.await()方法，然后在其它執行緒完成任務后呼叫countDownLatch.countDown()方法，每呼叫一次該計數就會減一，直到計數為0時，await的地方就會自動喚醒，繼續后面的作業，所以CountDownLatch適用于一個執行緒等待多個執行緒的場景，那它是怎么實作的呢？讀者們可以結合上文自己先思考下，

    public CountDownLatch(int count) {
        if (count < 0) throw new IllegalArgumentException("count < 0");
        this.sync = new Sync(count);
    }

    Sync(int count) {
        setState(count);
    }

與前面講的鎖一樣，也有一個內部類Sync繼承自AQS，并且在構造時就將傳入的計數設定到了state屬性，看到這里不難猜到CountDownLatch的實作原理了，

    public void await() throws InterruptedException {
        sync.acquireSharedInterruptibly(1);
    }

    public final void acquireSharedInterruptibly(int arg)
            throws InterruptedException {
        if (Thread.interrupted())
            throw new InterruptedException();
        if (tryAcquireShared(arg) < 0)
            doAcquireSharedInterruptibly(arg);
    }

    protected int tryAcquireShared(int acquires) {
        return (getState() == 0) ? 1 : -1;
    }

在await方法中使用的是可打斷的方式獲取的共享鎖，同樣除了tryAcquireShared方法，其余的都是復用的之前分析過的代碼，而tryAcquireShared就是判斷state是否等于0，不等于就阻塞，

    public void countDown() {
        sync.releaseShared(1);
    }

    public final boolean releaseShared(int arg) {
        if (tryReleaseShared(arg)) {
            doReleaseShared();
            return true;
        }
        return false;
    }
    
    protected boolean tryReleaseShared(int releases) {
        for (;;) {
            int c = getState();
            if (c == 0)
                return false;
            int nextc = c-1;
            if (compareAndSetState(c, nextc))
                return nextc == 0;
        }
    }

而呼叫countDown就更簡單了，每次對state遞減，直到為0時才會呼叫doReleaseShared釋放阻塞的執行緒，
最后需要注意的是CountDownLatch的計數是不支持重置的，每次使用都要新建一個，

CyclicBarrier

CyclicBarrier和CountDownLatch使用差不多，不過它只有await方法，CyclicBarrier在創建時同樣需要指定一個計數，當呼叫await的次數達到計數時，所有執行緒就會同時喚醒，相當于設定了一個“起跑線”，需要等所有運動員都到達這個“起跑線”后才能一起開跑，另外它還支持重置計數，提供了reset方法，

    public CyclicBarrier(int parties) {
        this(parties, null);
    }

    public CyclicBarrier(int parties, Runnable barrierAction) {
        if (parties <= 0) throw new IllegalArgumentException();
        this.parties = parties;
        this.count = parties;
        this.barrierCommand = barrierAction;
    }

CyclicBarrier提供了兩個構造方法，我們可以傳入一個Runnable型別的回呼函式，當達到計數時，由最后一個呼叫await的執行緒觸發執行，

    public int await() throws InterruptedException, BrokenBarrierException {
        try {
            return dowait(false, 0L);
        } catch (TimeoutException toe) {
            throw new Error(toe); // cannot happen
        }
    }

    private int dowait(boolean timed, long nanos)
        throws InterruptedException, BrokenBarrierException,
               TimeoutException {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            final Generation g = generation;

            if (g.broken)
                throw new BrokenBarrierException();

			// 是否打斷，打斷會喚醒所有條件佇列中的執行緒
            if (Thread.interrupted()) {
                breakBarrier();
                throw new InterruptedException();
            }

			// 計數為0時，喚醒條件佇列中的所有執行緒
            int index = --count;
            if (index == 0) {  // tripped
                boolean ranAction = false;
                try {
                    final Runnable command = barrierCommand;
                    if (command != null)
                        command.run();
                    ranAction = true;
                    nextGeneration();
                    return 0;
                } finally {
                    if (!ranAction)
                        breakBarrier();
                }
            }

            for (;;) {
                try {
                	// 不帶超時時間直接進入條件佇列等待
                    if (!timed)
                        trip.await();
                    else if (nanos > 0L)
                        nanos = trip.awaitNanos(nanos);
                } catch (InterruptedException ie) {
                    if (g == generation && ! g.broken) {
                        breakBarrier();
                        throw ie;
                    } else {
                        Thread.currentThread().interrupt();
                    }
                }

                if (g.broken)
                    throw new BrokenBarrierException();

                if (g != generation)
                    return index;

                if (timed && nanos <= 0L) {
                    breakBarrier();
                    throw new TimeoutException();
                }
            }
        } finally {
            lock.unlock();
        }
    }

    private void nextGeneration() {
        // signal completion of last generation
        trip.signalAll();
        // set up next generation
        count = parties;
        generation = new Generation();
    }

這里邏輯比較清晰，就是使用了ReentrantLock以及Condition來實作，在構造方法中我們可以看到保存了兩個變數count和parties，每次呼叫await都會對count變數遞減，count不為0時都會進入到trip條件佇列中等待，否則就會通過signalAll方法喚醒所有的執行緒，并將parties重新賦值給count，
reset方法很簡單，這里不詳細分析了，

Semaphore

Semaphore是信號的意思，或者說許可，可以用來控制最大并發量，初始定義好有幾個信號，然后在需要獲取信號的地方呼叫acquire方法，執行完成后，需要呼叫release方法回收信號，

    public Semaphore(int permits) {
        sync = new NonfairSync(permits);
    }
   
    public Semaphore(int permits, boolean fair) {
        sync = fair ? new FairSync(permits) : new NonfairSync(permits);
    }

它也有兩個構造方法，可以指定公平或是非公平，而permits就是state的值，

    public void acquire() throws InterruptedException {
        sync.acquireSharedInterruptibly(1);
    }

	// 非公平方式
    final int nonfairTryAcquireShared(int acquires) {
        for (;;) {
            int available = getState();
            int remaining = available - acquires;
            if (remaining < 0 ||
                compareAndSetState(available, remaining))
                return remaining;
        }
    }

	// 公平方式
    protected int tryAcquireShared(int acquires) {
        for (;;) {
            if (hasQueuedPredecessors())
                return -1;
            int available = getState();
            int remaining = available - acquires;
            if (remaining < 0 ||
                compareAndSetState(available, remaining))
                return remaining;
        }
    }

acquire方法和CountDownLatch是一樣的，只是tryAcquireShared區分了公平和非公平方式，獲取到信號相當于加共享鎖成功，否則則進入佇列阻塞等待；而release方法和讀鎖解鎖方式也是一樣的，只是每次release都會將state+1，

總結

本文詳細分析了AQS的核心原理、鎖的實作以及常用的相關組件，掌握其原理能讓我們準確的使用JUC下面的鎖以及執行緒協作組件，另外AQS代碼設計是非常精良的，有非常多的細節，精簡的代碼中把所有的情況都考慮到了，細細體味對我們自身編碼能力也會有很大的提高，
文章錯誤和不清楚的地方歡迎批評指出，另外超時相關的API本文都未涉及到，讀者可自行分析，