1.队列结点Node介绍

Wait queue node class.

 The wait queue is a variant of a "CLH" (Craig, Landin, and
Hagersten) lock queue. CLH locks are normally used for
spinlocks.  We instead use them for blocking synchronizers, but
use the same basic tactic of holding some of the control
information about a thread in the predecessor of its node.  A
"status" field in each node keeps track of whether a thread
should block.  A node is signalled when its predecessor
releases.  Each node of the queue otherwise serves as a
specific-notification-style monitor holding a single waiting
thread. The status field does NOT control whether threads are
granted locks etc though.  A thread may try to acquire if it is
first in the queue. But being first does not guarantee success;
it only gives the right to contend.  So the currently released
contender thread may need to rewait.

等待队列是“CLH”（Craig，Landin和Hagersten）锁队列的变体。CLH锁通常用于自旋锁。这里使用其作为阻塞同步器，但是使用了相同的基本策略——线程结点的前驱中保存了后一个结点的一些控制信息。每个结点中的status域跟踪线程是否应该阻塞。前驱释放锁时会signal后继。其他情况队列中的结点作为保存单个等待线程的特定通知样式监视器。status与不能控制线程是否获得锁。队列中首个线程会尝试获取锁，但是不确保成功。

 To enqueue into a CLH lock, you atomically splice it in as new
tail. To dequeue, you just set the head field.
 
     +------+  prev +-----+       +-----+
head |      | <---- |     | <---- |     |  tail
     +------+       +-----+       +-----+
 

 Insertion into a CLH queue requires only a single atomic
operation on "tail", so there is a simple atomic point of
demarcation from unqueued to queued. Similarly, dequeuing
involves only updating the "head". However, it takes a bit
more work for nodes to determine who their successors are,
in part to deal with possible cancellation due to timeouts
and interrupts.

入队，需要原子地拼接在尾部，出队，只要设置head域。

出队只需要更新head，但是需要花费更多的工作来确定其继任者是谁，部分原因是为了处理由于超市或中断产生的取消结点。

 The "prev" links (not used in original CLH locks), are mainly
needed to handle cancellation. If a node is cancelled, its
successor is (normally) relinked to a non-cancelled
predecessor. For explanation of similar mechanics in the case
of spin locks, see the papers by Scott and Scherer at
http://www.cs.rochester.edu/u/scott/synchronization/

 We also use "next" links to implement blocking mechanics.
The thread id for each node is kept in its own node, so a
predecessor signals the next node to wake up by traversing
next link to determine which thread it is.  Determination of
successor must avoid races with newly queued nodes to set
the "next" fields of their predecessors.  This is solved
when necessary by checking backwards from the atomically
updated "tail" when a node's successor appears to be null.
(Or, said differently, the next-links are an optimization
so that we don't usually need a backward scan.)

处理取消主要需要prev。如果结点被取消了，其后继通常会重新链接到未被取消的前驱。

使用next链接来实现阻塞机制。结点中保存了线程id，因此前驱通过遍历后继来确定需要唤醒的下一个线程。后继的确定必须避免与新入队结点的竞争。当后继为null时，必要时会通过原子更新的tail向后检查来解决。（换句话说，next链接是个优化，通常不需要向后扫描）。

 Cancellation introduces some conservatism to the basic
algorithms.  Since we must poll for cancellation of other
nodes, we can miss noticing whether a cancelled node is
ahead or behind us. This is dealt with by always unparking
successors upon cancellation, allowing them to stabilize on
a new predecessor, unless we can identify an uncancelled
predecessor who will carry this responsibility.

取消给基本算法引入了一些保守性。取消时总是唤醒后继结点，允许后继结点链接到新的前驱上面。

 CLH queues need a dummy header node to get started. But
we don't create them on construction, because it would be wasted
effort if there is never contention. Instead, the node
is constructed and head and tail pointers are set upon first
contention.

 Threads waiting on Conditions use the same nodes, but
use an additional link. Conditions only need to link nodes
in simple (non-concurrent) linked queues because they are
only accessed when exclusively held.  Upon await, a node is
inserted into a condition queue.  Upon signal, the node is
transferred to the main queue.  A special value of status
field is used to mark which queue a node is on.

 Thanks go to Dave Dice, Mark Moir, Victor Luchangco, Bill
Scherer and Michael Scott, along with members of JSR-166
expert group, for helpful ideas, discussions, and critiques
on the design of this class.

CLH队列需要一个哑head结点。不在构造器中创建，因为如果没有争用就浪费了。相反，在第一次争用时创建。

在Conditions上等待的线程使用相同的结点，但是使用一个额外的链接。条件队列只需要简单地链接结点，因为只有在独占时才会被访问。调用await时，结点插入到条件度列。调用signal时，结点会被转移到主队列中。status域的一个特殊值用来表示结点是在哪个队列中。

2.Node域介绍

    static final class Node {
        /** Marker to indicate a node is waiting in shared mode */
        static final Node SHARED = new Node();
        /** Marker to indicate a node is waiting in exclusive mode */
        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;

        /**
         * Status field, taking on only the values:
         *   SIGNAL:     The successor of this node is (or will soon be)
         *               blocked (via park), so the current node must
         *               unpark its successor when it releases or
         *               cancels. To avoid races, acquire methods must
         *               first indicate they need a signal,
         *               then retry the atomic acquire, and then,
         *               on failure, block.
         *   CANCELLED:  This node is cancelled due to timeout or interrupt.
         *               Nodes never leave this state. In particular,
         *               a thread with cancelled node never again blocks.
         *   CONDITION:  This node is currently on a condition queue.
         *               It will not be used as a sync queue node
         *               until transferred, at which time the status
         *               will be set to 0. (Use of this value here has
         *               nothing to do with the other uses of the
         *               field, but simplifies mechanics.)
         *   PROPAGATE:  A releaseShared should be propagated to other
         *               nodes. This is set (for head node only) in
         *               doReleaseShared to ensure propagation
         *               continues, even if other operations have
         *               since intervened.
         *   0:          None of the above
         *
         * The values are arranged numerically to simplify use.
         * Non-negative values mean that a node doesn't need to
         * signal. So, most code doesn't need to check for particular
         * values, just for sign.
         *
         * The field is initialized to 0 for normal sync nodes, and
         * CONDITION for condition nodes.  It is modified using CAS
         * (or when possible, unconditional volatile writes).
         */
        volatile int waitStatus;

waitStatus几种状态的介绍：

• SIGNAL：表明后继结点的线程需要唤醒。当current线程释放锁或取消时，必须唤醒后继结点线程。
• CANCELLED：因为超时或中断而被取消的结点
• CONDITION：该结点是在条件队列中。转移到同步队列时，会被设置为0
  *PROPAGATE：releaseShared应该传递到其他结点。

        /**
         * Link to predecessor node that current node/thread relies on
         * for checking waitStatus. Assigned during enqueuing, and nulled
         * out (for sake of GC) only upon dequeuing.  Also, upon
         * cancellation of a predecessor, we short-circuit while
         * finding a non-cancelled one, which will always exist
         * because the head node is never cancelled: A node becomes
         * 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;

        /**
         * Link to the successor node that the current node/thread
         * unparks upon release. Assigned during enqueuing, adjusted
         * when bypassing cancelled predecessors, and nulled out (for
         * sake of GC) when dequeued.  The enq operation does not
         * assign next field of a predecessor until after attachment,
         * so seeing a null next field does not necessarily mean that
         * node is at end of queue. However, if a next field appears
         * to be null, we can scan prev's from the tail to
         * double-check.  The next field of cancelled nodes is set to
         * point to the node itself instead of null, to make life
         * easier for isOnSyncQueue.
         */
        volatile Node next;

        /**
         * The thread that enqueued this node.  Initialized on
         * construction and nulled out after use.
         */
        volatile Thread thread;

        /**
         * Link to next node waiting on condition, or the special
         * value SHARED.  Because condition queues are accessed only
         * when holding in exclusive mode, we just need a simple
         * linked queue to hold nodes while they are waiting on
         * conditions. They are then transferred to the queue to
         * re-acquire. And because conditions can only be exclusive,
         * we save a field by using special value to indicate shared
         * mode.
         */
        Node nextWaiter;

在条件队列中使用的域（独占模式），共享模式时使用特殊值SHARED。这个域是一个独占、共享都使用的域。

        /**
         * Returns true if node is waiting in shared mode.
         */
        final boolean isShared() {
            return nextWaiter == SHARED;
        }

3.AQS的域

    /**
     * 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;