队列同步器AbstractQueuedSynchronizer，是用来构建锁或者其他同步组件的基础框架，它使用了一个volatile int成员变量表示同步状态，通过内置的FIFO队列来完成资源获取线程的排队工作，使用LockSupport.park(this)方法阻塞线程，LockSupport.unpark(thread)来唤醒线程。
    同步器的主要使用方式是继承，子类通过继承同步器并实现它的抽象方法来管理同步状态，在抽象方法的实现过程中免不了要对同步状态进行更改，这时就需要使用同步器提供的三个方法（getState()、setState(int newState)和compareAndSet(int expect, int update)）来进行操作，因为它们能够保证状态的改变是线程安全的。子类推荐定义为自定义同步组件的静态内部类，同步器本身没有实现任何同步接口，它仅仅是定义了若干同步状态获取和释放的方法来供自定义同步组件使用，同步器既可以支持独占式地获取同步状态，也可以支持共享式地获取同步状态，这样就可以方便实现不同类型的同步组件。
    同步器是实现锁的关键，在锁的实现中聚合同步器，利用同步器实现锁的语义

    可重写方法与描述

    方法名称 描述
    protected boolean tryAcquire(int arg) 独占式获取同步状态，实现该方法需要查询当前状态并判断同步状态是否符合预期，然后再进行CAS设置同步状态
    protected boolean tryRelease(int arg) 独占式释放同步状态，等待获取同步状态的线程将有机会获取同步状态
    protected int tryAcquireShared(int arg) 共享式获取同步状态，返回大于等于0的值，表示获取成功，反之，获取失败
    protected boolean tryReleaseShared(int arg) 共享式释放同步状态
    protected boolean isHeldExclusively() 当前同步器是否在独占模式下被线程占用，一般该方法表示是否被当前线程所独占

    同步器提供的模板方法

    方法名称 描述
    public final void acquire(int arg) 独占式获取同步状态，如果当前线程获取同步状态成功，则由该方法返回，否则，将会进入同步队列等待，该方法会调用重写的tryAcquire(int arg)方法
    public final void acquireInterruptibly(int arg) 与acquire(int arg)方法相同，但是该方法相应中断，当前线程未获取到同步状态而进入同步队列中，如果当前线程被中断，则该方法会抛出InterruptedException并返回
    public final boolean tryAcquireNanos(int arg, long nanosTimeout) 在acquireInterrupt(int arg)基础上增加了超时限制，如果当前线程在超时时间内没有获取到同步状态，那么将会返回false，如果获取到了就返回true
    public final void acquireShared(int arg) 共享式释放同步状态，如果当前线程未获取到同步状态，将会进入同步队列等待，与独占式获取的主要区别是在同一时刻可以有多个线程获取到同步状态
    public final void acquireSharedInterruptibly(int arg) 与acquireShared(int arg)相同，该方法相应中断
    public final boolean tryAcquireSharedNanos(int arg, long nanosTimeout) 在acquireSharedInterruptibly(int arg)基础上增加了超时限制
    public final boolean release(int arg) 独占式的释放同步状态，该方法会在释放同步状态之后，将同步队列中的第一个节点包含的线程唤醒
    public final boolean releaseShared(int arg) 共享式的释放同步状态
    public final Collection getQueuedThreads() 获取等待在同步队列上的线程集合

    同步队列
    同步器依赖内部的同步队列来完成同步状态管理，当前线程获取同步状态失败时，同步器会将当前线程以及等待状态等信息构成一个节点（Node）并将其加入同步队列，同时会阻塞当前线程，当同步状态释放时，会把首节点中的线程唤醒，使其再次尝试获取同步状态。
    同步队列中的节点（Node）用来保存获取同步状态失败的线程引用、等待状态以及前驱和后继节点

    属性类型与名称 描述
    int waitStatus 等待状态：
    1）CANCELLED,值为1，由于在同步队列中等待的线程等待超时或者被中断，需要从同步队列中取消等待，节点进入该状态将不会变化
    2）SIGNAL，值为-1，后继节点的线程处于等待状态，而当前节点的线程如果释放了同步状态或者被取消，将会通知后继节点，使后继节点的线程得以运行
    3）CONDITION，值为-2，节点在等待队列中，节点线程等待在condition上，当其他线程对condition调用了signal()方法后，该节点将会从等待队列中转移到同步队列中，加入到对同步状态的获取中
    4）PROPAGATE，值为-3，表示下一次共享式同步状态获取将会无条件地被传播下去
    5）INITAL，值为0，初始状态
    Node prev 前驱节点，当节点加入同步队列时被设置
    Node next 后继节点
    Node nextWaiter 等待队列中的后继节点。如果当前节点是共享的，那么这个字段将是一个SHARED变量，也就是说节点类型（独占和共享）和等待队列中的后继节点共用同一个字段
    Thread thread 获取同步状态的线程

    AbstractQueuedSynchronizer - 图1
    同步器包含了两个节点类型的引用，一个指向头节点，一个指向尾节点。试想一下，当一个线程成功地获取了同步状态，其他线程将无法获取到同步状态，转而被构造成为节点并加入到同步队列中，从而加入队列的过程必须要保证线程安全，因此同步器提供了一个基于CAS的设置尾节点的方法：compareAndSetTail(Node expect, Node update)，它需要传递当前线程“认为”的尾节点和当前节点，只有设置成功后，当前节点才正式与之前的尾节点建立联系。
    AbstractQueuedSynchronizer - 图2
    同步器将节点加入到同步队列的过程。
    AbstractQueuedSynchronizer - 图3
    同步队列遵循FIFO，首节点是获取同步状态成功的节点，首节点的线程在释放同步状态时，将会唤醒后继节点，而后继节点将会在获取同步状态成功时将自己设置为首节点
    设置首节点是通过获取同步状态成功的线程来完成的，由于只有一个线程能够成功获取到同步状态，因此设置头节点的方法不需要使用CAS来保证，它只需要将首节点设置成为原首节点的后继节点并断开原首节点的next引用即可
    独占式
    只有前驱节点是头节点才能尝试获取同步状态的原因：
    1）头节点是成功获取到同步状态的节点，而头节点的线程释放了同步状态之后，将会唤醒其后继节点，后续节点的线程被唤醒后需要检查自己的前驱节点是否是头节点。
    2）维护同步队列的FIFO原则。

    由于非首节点线程前驱节点出队或者被中断而从等待状态返回，随后检查自己的前驱是否是头节点，如果是则尝试获取同步状态。节点和节点之间不通信，简单地判断自己的前驱节点是否为头节点，这样使得节点的释放规则符合FIFO，并且也便于对过早通知的处理（过早通知是指前驱节点不是头节点的线程由于中断而被唤醒）

    独占式同步状态获取流程。
    AbstractQueuedSynchronizer - 图4

    在获取同步状态时，同步器维护了一个同步队列，获取状态失败的线程都会被加入到队列中并在队列中进行自旋；移出队列（或停止自旋）的条件是前驱节点为头节点且成功获取了同步状态。在释放同步状态时同步器调用tryRelease(int arg)方法释放同步状态，然后唤醒头部节点的后继节点。
    共享式
    共享式获取与独占式获取最大的区别在于同一时刻能否有多个线程同时获取到同步状态

    独占式超时获取同步状态
    通过调用同步器的doAcquireNanos（int arg， long nanosTimeout）方法可以超过获取同步状态，即在指定的时间段内获取同步状态。如果获取到同步状态则返回true，否则，返回false。
    Node

    1. static final class Node {
    2.     /** Marker to indicate a node is waiting in shared mode */
    3.     static final Node SHARED = new Node();
    4.     /** Marker to indicate a node is waiting in exclusive mode */
    5.     static final Node EXCLUSIVE = null;
    7.     /** waitStatus value to indicate thread has cancelled */
    8.     static final int CANCELLED =  1;
    9.     /** waitStatus value to indicate successor's thread needs unparking */
    10.     static final int SIGNAL    = -1;
    11.     /** waitStatus value to indicate thread is waiting on condition */
    12.     static final int CONDITION = -2;
    13.     /**
    14.      * waitStatus value to indicate the next acquireShared should
    15.      * unconditionally propagate
    16.      */
    17.     static final int PROPAGATE = -3;
    19.     /**
    20.      * Status field, taking on only the values:
    21.      *   SIGNAL:     The successor of this node is (or will soon be)
    22.      *               blocked (via park), so the current node must
    23.      *               unpark its successor when it releases or
    24.      *               cancels. To avoid races, acquire methods must
    25.      *               first indicate they need a signal,
    26.      *               then retry the atomic acquire, and then,
    27.      *               on failure, block.
    28.      *   CANCELLED:  This node is cancelled due to timeout or interrupt.
    29.      *               Nodes never leave this state. In particular,
    30.      *               a thread with cancelled node never again blocks.
    31.      *   CONDITION:  This node is currently on a condition queue.
    32.      *               It will not be used as a sync queue node
    33.      *               until transferred, at which time the status
    34.      *               will be set to 0. (Use of this value here has
    35.      *               nothing to do with the other uses of the
    36.      *               field, but simplifies mechanics.)
    37.      *   PROPAGATE:  A releaseShared should be propagated to other
    38.      *               nodes. This is set (for head node only) in
    39.      *               doReleaseShared to ensure propagation
    40.      *               continues, even if other operations have
    41.      *               since intervened.
    42.      *   0:          None of the above
    43.      *
    44.      * The values are arranged numerically to simplify use.
    45.      * Non-negative values mean that a node doesn't need to
    46.      * signal. So, most code doesn't need to check for particular
    47.      * values, just for sign.
    48.      *
    49.      * The field is initialized to 0 for normal sync nodes, and
    50.      * CONDITION for condition nodes.  It is modified using CAS
    51.      * (or when possible, unconditional volatile writes).
    52.      */
    53.     volatile int waitStatus;
    55.     /**
    56.      * Link to predecessor node that current node/thread relies on
    57.      * for checking waitStatus. Assigned during enqueuing, and nulled
    58.      * out (for sake of GC) only upon dequeuing.  Also, upon
    59.      * cancellation of a predecessor, we short-circuit while
    60.      * finding a non-cancelled one, which will always exist
    61.      * because the head node is never cancelled: A node becomes
    62.      * head only as a result of successful acquire. A
    63.      * cancelled thread never succeeds in acquiring, and a thread only
    64.      * cancels itself, not any other node.
    65.      */
    66.     volatile Node prev;
    68.     /**
    69.      * Link to the successor node that the current node/thread
    70.      * unparks upon release. Assigned during enqueuing, adjusted
    71.      * when bypassing cancelled predecessors, and nulled out (for
    72.      * sake of GC) when dequeued.  The enq operation does not
    73.      * assign next field of a predecessor until after attachment,
    74.      * so seeing a null next field does not necessarily mean that
    75.      * node is at end of queue. However, if a next field appears
    76.      * to be null, we can scan prev's from the tail to
    77.      * double-check.  The next field of cancelled nodes is set to
    78.      * point to the node itself instead of null, to make life
    79.      * easier for isOnSyncQueue.
    80.      */
    81.     volatile Node next;
    83.     /**
    84.      * The thread that enqueued this node.  Initialized on
    85.      * construction and nulled out after use.
    86.      */
    87.     volatile Thread thread;
    89.     /**
    90.      * Link to next node waiting on condition, or the special
    91.      * value SHARED.  Because condition queues are accessed only
    92.      * when holding in exclusive mode, we just need a simple
    93.      * linked queue to hold nodes while they are waiting on
    94.      * conditions. They are then transferred to the queue to
    95.      * re-acquire. And because conditions can only be exclusive,
    96.      * we save a field by using special value to indicate shared
    97.      * mode.
    98.      */
    99.     Node nextWaiter;
    101.     /**
    102.      * Returns true if node is waiting in shared mode.
    103.      */
    104.     final boolean isShared() {
    105.         return nextWaiter == SHARED;
    106.     }
    108.     /**
    109.      * Returns previous node, or throws NullPointerException if null.
    110.      * Use when predecessor cannot be null.  The null check could
    111.      * be elided, but is present to help the VM.
    112.      *
    113.      * @return the predecessor of this node
    114.      */
    115.     final Node predecessor() throws NullPointerException {
    116.         Node p = prev;
    117.         if (p == null)
    118.             throw new NullPointerException();
    119.         else
    120.             return p;
    121.     }
    123.     Node() {    // Used to establish initial head or SHARED marker
    124.     }
    126.     Node(Thread thread, Node mode) {     // Used by addWaiter
    127.         this.nextWaiter = mode;
    128.         this.thread = thread;
    129.     }
    131.     Node(Thread thread, int waitStatus) { // Used by Condition
    132.         this.waitStatus = waitStatus;
    133.         this.thread = thread;
    134.     }
    135. }
    1. /**
    2.  * Returns the current value of synchronization state.
    3.  * This operation has memory semantics of a {@code volatile} read.
    4.  * @return current state value
    5.  */
    6. protected final int getState() {
    7.     return state;
    8. }
    1. /**
    2.  * Sets the value of synchronization state.
    3.  * This operation has memory semantics of a {@code volatile} write.
    4.  * @param newState the new state value
    5.  */
    6. protected final void setState(int newState) {
    7.     state = newState;
    8. }
    1. /**
    2.  * Atomically sets synchronization state to the given updated
    3.  * value if the current state value equals the expected value.
    4.  * This operation has memory semantics of a {@code volatile} read
    5.  * and write.
    6.  *
    7.  * @param expect the expected value
    8.  * @param update the new value
    9.  * @return {@code true} if successful. False return indicates that the actual
    10.  *         value was not equal to the expected value.
    11.  */
    12. protected final boolean compareAndSetState(int expect, int update) {
    13.     // See below for intrinsics setup to support this
    14.     return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
    15. }

    获得同步状态

    1. public final void acquire(int arg) {
    2.     //尝试获取同步状态
    3.     if (!tryAcquire(arg) &&
    4.         //获取失败后，先将当前线程及等待状态构成一个节点加入同步队列
    5.         acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
    6.         selfInterrupt();
    7. }
    1. //添加到同步队列尾部
    2. private Node addWaiter(Node mode) {
    3.     //构造节点
    4.     Node node = new Node(Thread.currentThread(), mode);
    5.     // Try the fast path of enq; backup to full enq on failure
    6.     Node pred = tail;
    7.     //尾节点不为空
    8.     if (pred != null) {
    9.         //将当前节点的前驱节点设置为原尾节点
    10.         node.prev = pred;
    11.         //cas更新节点
    12.         if (compareAndSetTail(pred, node)) {
    13.             //将前驱节点的后继节点设置为当前节点
    14.             pred.next = node;
    15.             return node;
    16.         }
    17.     }
    18.     enq(node);
    19.     return node;
    20. }
    1. //自旋插入当前节点
    2. private Node enq(final Node node) {
    3.     for (;;) {
    4.         //指向尾节点
    5.         Node t = tail;
    6.         //如果队列为空
    7.         if (t == null) { // Must initialize
    8.             //cas设置头结点
    9.             if (compareAndSetHead(new Node()))
    10.                 tail = head;
    11.         } else {
    12.             //将当前节点的前驱节点设置为尾节点
    13.             node.prev = t;
    14.             //cas更新尾节点
    15.             if (compareAndSetTail(t, node)) {
    16.                 //尾节点的后继节点设置为当前节点
    17.                 t.next = node;
    18.                 return t;
    19.             }
    20.         }
    21.     }
    22. }
    1. final boolean acquireQueued(final Node node, int arg) {
    2.     boolean failed = true;
    3.     try {
    4.         boolean interrupted = false;
    5.         for (;;) {
    6.             //获取前节点
    7.             final Node p = node.predecessor();
    8.             //p节点是头节点 并且获得同步状态
    9.             if (p == head && tryAcquire(arg)) {
    10.                 //设置为头节点
    11.                 setHead(node);
    12.                 //这里p=node
    13.                 p.next = null; // help GC
    14.                 failed = false;
    15.                 return interrupted;
    16.             }
    17.             //获取同步状态失败，并且应该阻塞
    18.             if (shouldParkAfterFailedAcquire(p, node) &&
    19.                 //阻塞并检查线程中断标记
    20.                 parkAndCheckInterrupt())
    21.                 interrupted = true;
    22.         }
    23.     } finally {
    24.         if (failed)
    25.             //取消获取同步状态，将当前节点从队列移除
    26.             cancelAcquire(node);
    27.     }
    28. }
    1. private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    2.     int ws = pred.waitStatus;
    3.     if (ws == Node.SIGNAL)
    4.         /*
    5.          * This node has already set status asking a release
    6.          * to signal it, so it can safely park.
    7.          */
    8.         return true;
    9.     if (ws > 0) {
    10.         /*
    11.          * Predecessor was cancelled. Skip over predecessors and
    12.          * indicate retry.
    13.          */
    14.         do {
    15.             node.prev = pred = pred.prev;
    16.         } while (pred.waitStatus > 0);
    17.         pred.next = node;
    18.     } else {
    19.         /*
    20.          * waitStatus must be 0 or PROPAGATE.  Indicate that we
    21.          * need a signal, but don't park yet.  Caller will need to
    22.          * retry to make sure it cannot acquire before parking.
    23.          */
    24.         compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
    25.     }
    26.     return false;
    27. }
    1. private final boolean parkAndCheckInterrupt() {
    2.     //阻塞当前线程
    3.     LockSupport.park(this);
    4.     return Thread.interrupted();
    5. }
    1. private void cancelAcquire(Node node) {
    2.     // Ignore if node doesn't exist
    3.     if (node == null)
    4.         return;
    6.     node.thread = null;
    8.     // Skip cancelled predecessors
    9.     Node pred = node.prev;
    10.     //waitStatus > 0 就是CANCELLED状态
    11.     while (pred.waitStatus > 0)
    12.         node.prev = pred = pred.prev;
    14.     // predNext is the apparent node to unsplice. CASes below will
    15.     // fail if not, in which case, we lost race vs another cancel
    16.     // or signal, so no further action is necessary.
    17.     Node predNext = pred.next;
    19.     // Can use unconditional write instead of CAS here.
    20.     // After this atomic step, other Nodes can skip past us.
    21.     // Before, we are free of interference from other threads.
    22.     node.waitStatus = Node.CANCELLED;
    24.     // If we are the tail, remove ourselves.
    25.     if (node == tail && compareAndSetTail(node, pred)) {
    26.         compareAndSetNext(pred, predNext, null);
    27.     } else {
    28.         // If successor needs signal, try to set pred's next-link
    29.         // so it will get one. Otherwise wake it up to propagate.
    30.         int ws;
    31.         if (pred != head &&
    32.             ((ws = pred.waitStatus) == Node.SIGNAL ||
    33.              (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) &&
    34.             pred.thread != null) {
    35.             Node next = node.next;
    36.             if (next != null && next.waitStatus <= 0)
    37.                 compareAndSetNext(pred, predNext, next);
    38.         } else {
    39.             unparkSuccessor(node);
    40.         }
    42.         node.next = node; // help GC
    43.     }
    44. }

    释放同步状态

    1. public final boolean release(int arg) {
    2.     //自定义组件实现的安全释放同步状态方法
    3.     if (tryRelease(arg)) {
    4.         Node h = head;
    5.         //头节点不是空，并且等待状态不是初始状态
    6.         if (h != null && h.waitStatus != 0)
    7.             //唤醒头节点的线程
    8.             unparkSuccessor(h);
    9.         return true;
    10.     }
    11.     return false;
    12. }
    1. private void unparkSuccessor(Node node) {
    2.     /*
    3.      * If status is negative (i.e., possibly needing signal) try
    4.      * to clear in anticipation of signalling.  It is OK if this
    5.      * fails or if status is changed by waiting thread.
    6.      */
    7.     int ws = node.waitStatus;
    8.     if (ws < 0)
    9.         compareAndSetWaitStatus(node, ws, 0);
    11.     /*
    12.      * Thread to unpark is held in successor, which is normally
    13.      * just the next node.  But if cancelled or apparently null,
    14.      * traverse backwards from tail to find the actual
    15.      * non-cancelled successor.
    16.      */
    17.     Node s = node.next;
    18.     if (s == null || s.waitStatus > 0) {
    19.         s = null;
    20.         for (Node t = tail; t != null && t != node; t = t.prev)
    21.             if (t.waitStatus <= 0)
    22.                 s = t;
    23.     }
    24.     if (s != null)
    25.         LockSupport.unpark(s.thread);
    26. }

    共享式获取同步状态

    1. public final void acquireShared(int arg) {
    2.     if (tryAcquireShared(arg) < 0)
    3.         doAcquireShared(arg);
    4. }
    1. private void doAcquireShared(int arg) {
    2.     //共享式添加到同步队列
    3.     final Node node = addWaiter(Node.SHARED);
    4.     boolean failed = true;
    5.     try {
    6.         boolean interrupted = false;
    7.         for (;;) {
    8.             final Node p = node.predecessor();
    9.             //如果是头节点再尝试获取同步状态
    10.             if (p == head) {
    11.                 int r = tryAcquireShared(arg);
    12.                 //同步状态 >= 0  也就是初始状态或者是取消状态
    13.                 if (r >= 0) {
    14.                     //设置头节点和属性
    15.                     setHeadAndPropagate(node, r);
    16.                     p.next = null; // help GC
    17.                     if (interrupted)
    18.                         //自我中断
    19.                         selfInterrupt();
    20.                     failed = false;
    21.                     return;
    22.                 }
    23.             }
    24.             if (shouldParkAfterFailedAcquire(p, node) &&
    25.                 parkAndCheckInterrupt())
    26.                 interrupted = true;
    27.         }
    28.     } finally {
    29.         if (failed)
    30.             cancelAcquire(node);
    31.     }
    32. }
    1. public final boolean releaseShared(int arg) {
    2.     if (tryReleaseShared(arg)) {
    3.         doReleaseShared();
    4.         return true;
    5.     }
    6.     return false;
    7. }