3.14 Java AQS原理決議

3.14 AQS

AQS是Java中AbstractQueuedSynchronizer的簡稱，AQS實在是太有名了，以至于它的全稱經常被遺忘，先看看AQS是什么，

Provides a framework for implementing blocking locks and related synchronizers (semaphores, events, etc) that rely on first-in-first-out (FIFO) wait queues. This class is designed to be a useful basis for most kinds of synchronizers that rely on a single atomic {@code int} value to represent state.¹

AQS通過一個先進先出的等待佇列提供了一個實作鎖和相應同步的框架，AQS依靠一個原子型數值表示狀態來搭建同步操作的基礎，

3.14.1 AQS繼承關系

AbstractQueuedSynchronizer（AQS）繼承了AbstractOwnableSynchronizer(AOS)，先來看下AOS是個啥，

3.14.2 AbstractOwnableSynchronizer

AOS只有一個私有的exclusiveOwnerThread執行緒屬性，表示當前運行的獨占的執行緒，它的子類只能通過受保護的get和set方法訪問該屬性，

public abstract class AbstractOwnableSynchronizer
    implements java.io.Serializable {
    private static final long serialVersionUID = 3737899427754241961L;
    protected AbstractOwnableSynchronizer() { }
    private transient Thread exclusiveOwnerThread;
    protected final void setExclusiveOwnerThread(Thread thread) {
        exclusiveOwnerThread = thread;
    }
    protected final Thread getExclusiveOwnerThread() {
        return exclusiveOwnerThread;
    }
}

3.14.3 AQS CLH佇列

CLH佇列是一種自旋鎖佇列，自旋鎖佇列是什么含義呢？當頭部節點執行緒在運行的時候，它的后續節點執行緒都處于一種自旋的狀態，

CLH佇列Node原始碼，其實內部很簡單，一個雙向鏈表，每個節點有一個執行緒和表示該執行緒的狀態的waitStatus，還有惟一一個非volatile修飾的nextWaiter屬性，當該屬性Node為該類屬性SHARED節點時，表示共享，這個SHARED節點上的執行緒都是可共享的，不存在排他性，所以不需要用volatile關鍵詞修飾，

static final class Node {
    static final Node SHARED = new Node();
    static final Node EXCLUSIVE = null;

    /** waitStatus value to indicate thread has cancelled */
    static final int CANCELLED =  1;
    /** waitStatus value to indicate successor's thread needs unparking */
    static final int SIGNAL    = -1;
    /** waitStatus value to indicate thread is waiting on condition */
    static final int CONDITION = -2;
    /**
     * waitStatus value to indicate the next acquireShared should
     * unconditionally propagate
     */
    static final int PROPAGATE = -3;
    volatile int waitStatus;
     * head only as a result of successful acquire. A
     * cancelled thread never succeeds in acquiring, and a thread only
     * cancels itself, not any other node.
     */
    volatile Node prev;
    volatile Node next;
    volatile Thread thread;
    Node nextWaiter;
    final boolean isShared() {
        return nextWaiter == SHARED;
    }
    final Node predecessor() throws NullPointerException {
        Node p = prev;
        if (p == null)
            throw new NullPointerException();
        else
            return p;
    }

    Node() {    // Used to establish initial head or SHARED marker
    }

    Node(Thread thread, Node mode) {     // Used by addWaiter
        this.nextWaiter = mode;
        this.thread = thread;
    }

    Node(Thread thread, int waitStatus) { // Used by Condition
        this.waitStatus = waitStatus;
        this.thread = thread;
    }
}

AQS中的CLH佇列機制如下，

3.14.4 AQS組成

雙向鏈表，一個指向頭部，一個指向尾部，再加一個state表示屬性，

/**
 * Head of the wait queue, lazily initialized.  Except for
 * initialization, it is modified only via method setHead.  Note:
 * If head exists, its waitStatus is guaranteed not to be
 * CANCELLED.
 */
private transient volatile Node head;

/**
 * Tail of the wait queue, lazily initialized.  Modified only via
 * method enq to add new wait node.
 */
private transient volatile Node tail;

/**
 * The synchronization state.
 */
private volatile int state;

3.14.5 原始碼方法決議

添加新Node進入CLH佇列（尾插法），添加新節點到尾部，

private Node enq(final Node node) {
	//回圈直到尾節點不為null，添加到尾部
    for (;;) {
        Node t = tail;
        if (t == null) { // Must initialize
        	//當前head為null比較并更新成新Node，是Unsafe提供的方法，可以看出頭Node不存執行緒，
            if (compareAndSetHead(new Node()))
                tail = head;
        } else {
            node.prev = t;
            if (compareAndSetTail(t, node)) {
                t.next = node;
                return t;
            }
        }
    }
}

addWaiter方法

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;
    //當尾節點不為null，直接入佇列
    if (pred != null) {
        node.prev = pred;
        if (compareAndSetTail(pred, node)) {
            pred.next = node;
            return node;
        }
    }
   	//當尾節點為null，回圈先構建head節點然后入佇列
    enq(node);
    return node;
}

acquireQueued方法

final boolean acquireQueued(final Node node, int arg) {
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            final Node p = node.predecessor();
            //tryAcquire(arg)抽象方法，子類具體實作
            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);
    }
}

3.14.6 小結

AQS中還有很多方法沒有提到，實在是肝不動了，AQS作為Java原始碼中最難的一塊筆者在寫這點的時候也是很擔心寫錯，雖然看了很多遍，但很多細節還是不了解，本來在寫鎖之前就該先說AQS，不過AQS確實太難了，先知道鎖再去看AQS反而更容易理解，