public abstract class AbstractQueuedSynchronizer {   /**   * 表示锁的状态   * 0 表示：未锁定   * 大于0表示：已锁定（数值表示被同一个线程获取到锁的次数，每解锁一次数值减1）   */  private volatile int state;  /**   * 等待队列的头节点，通过setHead方法设置head   */  private transient volatile Node head;  /**   * 等待队列的尾结点，通过enq方法添加等待节点   */  private transient volatile Node tail;}

// The wait queue is a variant of a "CLH" (Craig, Landin, and Hagersten) lock queue.static final class Node {    // 同步器可以作为排他模式也可以作为共享模式    // 排他模式时，其他线程对其的获取就被阻止，共享模式对于多个线程获取都可以成功。    // Node 属性定义了是共享模式（SHARED）还是排他模式（EXCLUSIVE）    static final Node SHARED = new Node();    static final Node EXCLUSIVE = null;
    // 节点的等待状态，默认值为0，表示当前节点在队列中，等待着获取锁。    volatile int waitStatus;      // waitStatus 变量可选值    static final int CANCELLED =  1;    static final int SIGNAL    = -1;    static final int CONDITION = -2;    static final int PROPAGATE = -3;      // 前驱和后继节点    volatile Node prev;    volatile Node next;
    // 入队列时的当前线程    volatile Thread thread;        // Condition队列中的后继节点    Node nextWaiter;}

class Sync extends AbstractQueuedSynchronizer {}
// 非公平锁class NonfairSync extends Sync {  final void lock() {    // 通过CAS尝试改变state的状态，修改成功后设置当前线程获取了锁，修改失败的逻辑和公平锁一样。    if (compareAndSetState(0, 1))      setExclusiveOwnerThread(Thread.currentThread());    else      acquire(1);  }}
// 公平锁class FairSync extends Sync {  final void lock() {    // 独占锁加锁的核心逻辑    acquire(1);  }}

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

protected final boolean tryAcquire(int acquires) {  final Thread current = Thread.currentThread();  // 获取state状态，0表示未锁定  int c = getState();  if (c == 0) {    // 非公平锁中没有 hasQueuedPredecessors() 这个判断，判断前面是否有排队的线程    // 通过CAS的方式修改state成功之后，设置当前拥有独占访问权的线程    if (!hasQueuedPredecessors() &&        compareAndSetState(0, acquires)) {        setExclusiveOwnerThread(current);        return true;    }  }  else if (current == getExclusiveOwnerThread()) {    // 如果当前线程就是拥有独占访问权的线程，state计算重入次数    int nextc = c + acquires;    if (nextc < 0)      throw new Error("Maximum lock count exceeded");    setState(nextc);    return true;  }  return false;}

// addWaiter(Node.EXCLUSIVE), arg)  // mode 表示独占还是共享模式private Node addWaiter(Node mode) {  Node node = new Node(Thread.currentThread(), mode);  // 尝试添加尾结点，失败或没有尾节点，执行enq方法  Node pred = tail;  if (pred != null) {    node.prev = pred;    // CAS 方式添加尾节点    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;      }    }  }}

final boolean acquireQueued(final Node node, int arg) {  boolean failed = true;  try {    boolean interrupted = false;    for (;;) {      // 获取当前节点的前驱节点      final Node p = node.predecessor();      // 如果当前节点是队列中的第一个节点（前驱是 head），调用 tryAcquire 获取锁      // 否则自旋等待      if (p == head && tryAcquire(arg)) {        // 设置 head 节点（相当于出队列）        setHead(node);        p.next = null; // help GC        failed = false;        return interrupted;      }      if (shouldParkAfterFailedAcquire(p, node) &&        parkAndCheckInterrupt())        interrupted = true;    }  } finally {    if (failed)      // 自旋异常退出，取消正在进行锁争抢      cancelAcquire(node);  }}

/** * 1. 检查一下当前节点（node）的前置节点（pred）的 waitStatus * 2. pred waitStatus=0，返回true，当前节点需要被被阻塞 * 2. pred waitStatus>0，pred 线程已经 cancel，不断向前调整当前节点的 pred 节点（同时 cancel 线程移除了队列） * 3. pred waitStatus<0，设置 pred 的 waitStatus 为 SIGNAL */private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {  int ws = pred.waitStatus;  if (ws == Node.SIGNAL)    // SIGNAL 表示后继节点（即node）处于等待状态，如果pred释放或取消，会通知后继节点    // 返回true，node需要被阻塞    return true;  if (ws > 0) {    do {      // 不断向前调整当前节点的 pred 节点，直到没有被 cancel 的线程节点      node.prev = pred = pred.prev;    } while (pred.waitStatus > 0);    pred.next = node;  } else {    // 通过CAS将前驱节点的 waitStatus 设置成 SIGNAL    compareAndSetWaitStatus(pred, ws, Node.SIGNAL);  }  return false;}
/** * 当 shouldParkAfterFailedAcquire 返回 True 的时候执行 parkAndCheckInterrupt 方法 */private final boolean parkAndCheckInterrupt() {    // 阻塞当前的线程  LockSupport.park(this);  // 返回检测当前线程是否被中断  return Thread.interrupted();}

private void cancelAcquire(Node node) {  node.thread = null;
  // Skip cancelled predecessors  Node pred = node.prev;  while (pred.waitStatus > 0)    node.prev = pred = pred.prev;
  // predNext is the apparent node to unsplice. CASes below will  // fail if not, in which case, we lost race vs another cancel  // or signal, so no further action is necessary.  Node predNext = pred.next;
  // Can use unconditional write instead of CAS here.  // After this atomic step, other Nodes can skip past us.  // Before, we are free of interference from other threads.  node.waitStatus = Node.CANCELLED;
  // If we are the tail, remove ourselves.  if (node == tail && compareAndSetTail(node, pred)) {    compareAndSetNext(pred, predNext, null);  } else {    // If successor needs signal, try to set pred's next-link    // so it will get one. Otherwise wake it up to propagate.    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 final boolean release(int arg) {  if (tryRelease(arg)) {    Node h = head;    // 所有节点在 park 之前都把前置节点设置为 SIGNAL    // 如果前置节点已经重置为 0，不需要再唤醒后继节点    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)    // ws 重置为 0    compareAndSetWaitStatus(node, ws, 0);
  // 要唤醒的线程通常是 next 节点  // 如果next为空或者被取消，从尾部向前遍历以找到实际的未取消的后继者  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);}

class Semaphore {  public void acquire() throws InterruptedException {    sync.acquireSharedInterruptibly(1);  } 
  public void release() {    sync.releaseShared(1);  }    class Sync extends AbstractQueuedSynchronizer {
  }}

public final void acquireSharedInterruptibly(int arg) {  if (Thread.interrupted())    throw new InterruptedException();  // 尝试获取共享锁，失败时为负值  if (tryAcquireShared(arg) < 0)    // 可中断的自旋竞争共享锁    doAcquireSharedInterruptibly(arg);}

protected int tryAcquireShared(int acquires) {  for (;;) {    if (hasQueuedPredecessors())      // 如果有线程在排队（公平锁排队，非公平锁没有这个判断），直接返回，进入 doAcquireSharedInterruptibly 自旋获取      return -1;    int available = getState();    // 剩余许可：可用的许可减去申请的许可    // 如果小于0直接返回    // 如果有可用的剩余许可，CAS设置available，设置成功表示获取锁成功，设置失败自旋    int remaining = available - acquires;    if (remaining < 0 ||        compareAndSetState(available, remaining))      return remaining;  }}

private void doAcquireSharedInterruptibly(int arg) {  // 为当前线程创建节点并插入队列尾部  final Node node = addWaiter(Node.SHARED);  boolean failed = true;  try {    for (;;) {      final Node p = node.predecessor();      if (p == head) {        // 如果当前节点是队列中的第一个节点（前驱是 head），调用 tryAcquireShared 获取锁        // r 是剩余许可        int r = tryAcquireShared(arg);        if (r >= 0) {          // 设置 head 节点（相当于出队列）          // 设置 Propagate          setHeadAndPropagate(node, r);          p.next = null; // help GC          failed = false;          return;        }      }            // 获取锁失败后阻塞线程      if (shouldParkAfterFailedAcquire(p, node) &&          parkAndCheckInterrupt())        throw new InterruptedException();    }  } finally {    if (failed)      cancelAcquire(node);  }}

private void setHeadAndPropagate(Node node, int propagate) {  // propagate 是剩余许可  Node h = head;  setHead(node);
  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) {        if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))          continue;        unparkSuccessor(h);      }      else if (ws == 0 &&               !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))        continue;                    }    if (h == head)      break;  }}

public final boolean releaseShared(int arg) {  if (tryReleaseShared(arg)) {    doReleaseShared();    return true;  }  return false;}

protected final boolean tryReleaseShared(int releases) {  for (;;) {    int current = getState();    int next = current + releases;    if (next < current)       throw new Error("Maximum permit count exceeded");    if (compareAndSetState(current, next))      return true;  }}

private void doReleaseShared() {  for (;;) {    Node h = head;    if (h != null && h != tail) {      int ws = h.waitStatus;      if (ws == Node.SIGNAL) {        if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))          continue;                    unparkSuccessor(h);      }      else if (ws == 0 &&               !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))        continue;                    }    if (h == head)      break;  }}

Wait queue node class.等待队列节点。
The wait queue is a variant of a "CLH" 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 锁队列的变体。CLH 锁通常用于旋转锁。我们使用相同的基本策略来阻塞同步器，在一个线程节点的前一个节点中保存一些关于当前线程的控制信息。每个节点中的 status 字段跟踪线程是否应该阻塞。节点在其前一个节点释放时会发出信号。否则，队列的每个节点都充当一个特定的通知监视器，其中包含一个等待线程。status 字段并不控制线程是否被授予锁等。如果线程是队列中的第一个节点，它可能会尝试获取。但第一个节点并不能保证获取成功；只是赋予了竞争的权利。因此，当前的竞争线程可能需要继续等待。
To enqueue into a CLH lock, you atomically splice it in as new tail.  To dequeue, you just set the head field.要排队进入 CLH 锁，可以在原子操作中将其作为新的 tail 进行链接。要出队列，只需设置 head。
     +------+  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.插入到 CLH 队列只需要对 tail 执行原子操作，就可以从 unqueued 变为 queued。同样，出列只涉及更新 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. 引用 prev（原始 CLH 锁中没有使用）主要用于处理取消。如果一个节点被取消，它的后续节点（通常）要重新链接到一个未取消的前置节点。
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.)我们还使用 next 引用来实现阻塞机制。线程Id都保存在自己的节点中，因此前一个节点通过访问 next 向下一个节点发出唤醒信号。确定后继节点需要避免与新入队列的节点竞争，以设置其前驱节点的 next 字段。当节点的后继节点看起来为空时，通过从原子更新的 tail 向后检查来解决这个问题。
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.Cancellation 为算法引入了一些特性。由于我们必须轮询其他节点的取消状态，我们可能会忽略取消的节点是在前面还是后面。解决这个问题的办法是，在取消时总是 unparking 后继节点，之后找到在新的稳定的未取消的前驱节点。
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.CLH 队列需要一个虚拟 head 节点。但不会在构造函数时创建，而是在第一次有有请求时构造节点并设置 head 和 tail。
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.等待的线程使用相同的节点，但使用额外的链接。条件只需要链接简单（非并发）链接队列中的节点，因为它们仅在独占持有时才被访问。等待时，将节点插入到条件队列中。收到信号后，节点被转移到主队列。状态字段的特殊值用于标记节点所在的队列。