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.
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
       +------+       +-----+       +-----+

该等待队列是“CLH”（Craig、Landin 和 Hagersten）锁队列的一种变体。CLH 锁通常用于自旋锁，但我们将其用于阻塞式同步器，同时保留了相同的基本策略：将线程的部分控制信息存储在其节点的前驱节点中。每个节点中的"status"字段用于跟踪线程是否应被阻塞。当前驱节点释放时，当前节点会收到唤醒信号。队列中的每个节点本质上充当特定通知模式的监视器，承载单个等待线程。

需重点注意：

status 字段并不控制线程是否被授予锁等权限。若线程位于队列首位，则可尝试获取锁，但首位位置并不保证成功——它仅赋予竞争资格。因此，当前释放的竞争线程可能需要重新进入等待状态。

队列操作机制：

• 入队：通过原子操作将新节点拼接为尾节点
• 出队：直接设置头节点字段

向CLH队列插入节点仅需对"尾节点"执行单次原子操作，因此存在一个清晰的原子化界限，用于区分节点从未排队到已排队的状态转变。类似地，出队操作也仅涉及更新"头节点"字段。

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.

然而，节点需要更多处理逻辑来确定其后继节点，这部分额外工作主要用于应对因超时和中断可能引发的节点取消情况。

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/

"prev"（前驱）链接（在原始CLH锁中未使用）主要用于处理节点取消问题。当某个节点被取消时，其后继节点通常会被重新链接到一个未被取消的前驱节点上。关于自旋锁中类似机制的详细解释，请参阅Scott和Scherer的论文：http://www.cs.rochester.edu/u/scott/synchronization/

该设计通过引入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"字段产生竞争。该问题通过以下方式解决：当某节点的后继节点显示为null时，必要时从原子更新的"tail"（尾节点）开始反向扫描。（换言之，next链接是一种优化机制，通常可避免反向扫描。）

竞争场景说明：
当出现以下时序时可能触发反向扫描：

前驱节点P尝试读取其后继节点（此时P.next=null）
新节点N同时入队：CAS更新tail成功，但尚未设置P.next字段
此时P误判无后继节点，需通过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.

取消机制为基本算法引入了一定的保守性设计。由于必须轮询检查其他节点的取消状态，我们可能无法准确判断已取消节点位于当前节点的前方还是后方。该问题通过以下策略解决：在节点取消时总是唤醒其后继节点，使其能够基于新的前驱节点重新稳定状态，除非能明确识别出某个未取消的前驱节点将承担此责任。

此保守设计通过"宁可过度唤醒，不可遗漏阻塞"的原则，在无法精确感知节点拓扑关系的限制下，仍保证了阻塞队列的活锁安全性（liveness safety）。

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队列需要一个哑头节点（dummy header node） 来启动队列。但我们不会在构造时创建该节点，因为如果从未发生竞争，这将造成资源浪费。相反，节点会在首次出现竞争时动态创建，并同时设置头指针（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.

在条件队列上等待的线程复用相同节点结构，但使用额外链接。条件队列仅需构建简单（非并发）链表队列，因其仅在线程独占持有时被访问。当调用await()时，节点被插入条件队列；当调用signal()时，节点被转移到主等待队列。通过状态字段的特殊值标记节点当前所属队列。

Node类的属性

waitStatus

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).

对于普通同步节点，该字段初始化为 0；对于条件节点，则初始化为 CONDITION 状态值。字段修改采用 CAS（比较并交换）操作实现，或在允许的情况下使用无条件的 volatile 写操作。

Node类的方法

/**
  * Returns true if node is waiting in shared mode.
  * 节点状态是共享模式时返回true
  */
final boolean isShared() {
     return nextWaiter == SHARED;
}

/**
* Returns previous node, or throws NullPointerException if null.
* Use when predecessor cannot be null.  The null check could
* be elided, but is present to help the VM.
* 返回前驱节点，若节点为空则抛出 NullPointerException。
* 该方法应在确定前驱节点非空时使用。
* 虽然空检查本可省略，但保留此检查有助于虚拟机优化。
* 
* @return the predecessor of this node
*/
final Node predecessor() throws NullPointerException {
   Node p = prev;
   if (p == null)
       throw new NullPointerException();
   else
       return p;
}

// 无参构造方法，用于建立初始头节点或 SHARED 标记
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;
}

属性

方法

/**
 * Returns the current value of synchronization state.
 * This operation has memory semantics of a {@code volatile} read.
 * 返回同步状态的当前值。该操作具有 volatile 读的内存语义。
 * @return current state value
 */
protected final int getState() {
  return state;
}

/**
 * Sets the value of synchronization state.
 * This operation has memory semantics of a {@code volatile} write.
 * 设置同步状态值。该操作具有 volatile 写的内存语义
 * @param newState the new state value
*/
protected final void setState(int newState) {
        state = newState;
}

/**
 * Atomically sets synchronization state to the given updated
 * value if the current state value equals the expected value.
 * This operation has memory semantics of a {@code volatile} read
 * and write.
 * 原子的将当前的同步状态设置为给定的更新值，前提时当前状态值等于期望值
 * 该操作具有 volatile 读写内存语义
 *
 * @param expect the expected value
 * @param update the new value
 * @return {@code true} if successful. False return indicates that the actual
 * value was not equal to the expected value.
 */
protected final boolean compareAndSetState(int expect, int update) {
  // See below for intrinsics setup to support this
  return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
}

/**
 * Inserts node into queue, initializing if necessary. See picture above.
 * 向对接中插入一个节点，必要的时候进行初始化
 * @param node the node to insert
 * @return node's predecessor
 */
private Node enq(final Node node) {
    for (;;) {
        Node t = tail;
        if (t == null) { // Must initialize
            if (compareAndSetHead(new Node()))
                tail = head;
        } else {
            node.prev = t;
            if (compareAndSetTail(t, node)) {
                t.next = node;
                return t;
            }
        }
    }
}

/**
 * Creates and enqueues node for current thread and given mode.
 * 基于当前线程和给定的模式（Node.EXCLUSIVE or Node.SHARED）创建节点并入队
 *
 * @param mode Node.EXCLUSIVE for exclusive, Node.SHARED for shared
 * @return the new node
 */
private Node addWaiter(Node mode) {
    Node node = new Node(Thread.currentThread(), mode);
    // 快速路径尝试：直接CAS入队
    Node pred = tail;
    if (pred != null) {
        node.prev = pred;
        if (compareAndSetTail(pred, node)) {
            pred.next = node;
            return node;
        }
    }
    // 快速路径失败时回退到完整入队
    enq(node);
    return node;
}

/**
 * Sets head of queue to be node, thus dequeuing. Called only by
 * acquire methods.  Also nulls out unused fields for sake of GC
 * and to suppress unnecessary signals and traversals.
 * 将队列的头节点设置为指定节点，从而实现出队操作。该方法仅由资源获取方法调用。
 * 同时，为便于垃圾回收（GC）并避免不必要的信号通知和队列遍历，会将不再使用的字段置空。
 *
 * @param node the node
 */
private void setHead(Node node) {
     head = node;
     node.thread = null;
     node.prev = null;
}

/**
 * Wakes up node's successor, if one exists.
 * 唤醒节点的后继节点，如果后继节点存在的话
 *
 * @param node the node
 */
private void unparkSuccessor(Node node) {
    /*
     * If status is negative (i.e., possibly needing signal) try
     * to clear in anticipation of signalling.  It is OK if this
     * fails or if status is changed by waiting thread.
     * 如果状态为负值（也就是说，可能需要发送信号通知）
     * 尝试预先清除状态以准备进行信号通知
     * 处理失败是可以接受的，当状态被等待的线程修改过了
     */
    int ws = node.waitStatus;
    if (ws < 0)
        compareAndSetWaitStatus(node, ws, 0);

    /*
     * Thread to unpark is held in successor, which is normally
     * just the next node.  But if cancelled or apparently null,
     * traverse backwards from tail to find the actual
     * non-cancelled successor.
     * 需要唤醒的线程保存在后继节点中，通常就是下一个节点。
     * 但如果该节点已取消或明显为空，则从尾部开始向后遍历，以找到实际的未取消的后继节点。
     */
    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);
}

/**
 * Release action for shared mode -- signals successor and ensures
 * propagation. (Note: For exclusive mode, release just amounts
 * to calling unparkSuccessor of head if it needs signal.)
 * 共享模式下的释放动作——通知后继节点并且确保能够传播下去
 * （注意：在独占模式下，释放操作仅需在头节点需要信号时调用其 unparkSuccessor 方法。）
 */
private void doReleaseShared() {
    /*
     * Ensure that a release propagates, even if there are other
     * in-progress acquires/releases.  This proceeds in the usual
     * way of trying to unparkSuccessor of head if it needs
     * signal. But if it does not, status is set to PROPAGATE to
     * ensure that upon release, propagation continues.
     * Additionally, we must loop in case a new node is added
     * while we are doing this. Also, unlike other uses of
     * unparkSuccessor, we need to know if CAS to reset status
     * fails, if so rechecking.
     * 确保释放操作能够传播，即使此时有其他正在进行的获取/释放操作。
     * 其处理方式遵循常规逻辑：若头节点需要信号通知，则尝试唤醒其后继节点。
     * 但若头节点无需信号，则将其状态设置为 PROPAGATE，以保证在后续释放时传播持续进行。
     * 此外，我们必须循环处理，以防操作过程中有新节点加入队列。
     * 另请注意：与其他 unparkSuccessor 的使用场景不同，此处需检测重置状态的 CAS 操作是否失败，
     * 若失败则重新检查状态。
     */
    for (;;) {
        Node h = head;
        if (h != null && h != tail) {
            int ws = h.waitStatus;
            if (ws == Node.SIGNAL) {
                if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
                    continue;            // loop to recheck cases
                unparkSuccessor(h);
            }
            else if (ws == 0 &&
                     !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
                continue;                // loop on failed CAS
        }
        if (h == head)                   // loop if head changed
            break;
    }
}

/**
 * Sets head of queue, and checks if successor may be waiting
 * in shared mode, if so propagating if either propagate > 0 or
 * PROPAGATE status was set.
 * 设置队列的头节点，并检查其后继节点是否可能处于共享等待模式。
 * 如果是，则当传播值（propagate）大于0或PROPAGATE状态已被设置时，继续传播唤醒信号。
 *
 * @param node the node
 * @param propagate the return value from a tryAcquireShared
 */
private void setHeadAndPropagate(Node node, int propagate) {
    Node h = head; // Record old head for check below
    setHead(node);
    /*
     * Try to signal next queued node if:
     *   Propagation was indicated by caller,
     *     or was recorded (as h.waitStatus either before
     *     or after setHead) by a previous operation
     *     (note: this uses sign-check of waitStatus because
     *      PROPAGATE status may transition to SIGNAL.)
     * and
     *   The next node is waiting in shared mode,
     *     or we don't know, because it appears null
     *
     * The conservatism in both of these checks may cause
     * unnecessary wake-ups, but only when there are multiple
     * racing acquires/releases, so most need signals now or soon
     * anyway.
     * 在以下情况下尝试通知下一个排队节点：
     *   调用方明确指示需要传播（propagate > 0），
     *     或由先前的操作记录了传播状态（通过检查 setHead 前/后 h.waitStatus 的值）
     *     （注意：这里使用 waitStatus 的符号检查，因为 PROPAGATE 状态可能转换为 SIGNAL）
     * 同时满足：
     *   下一个节点处于共享等待模式，
     *     或节点显示为空（此时无法确定）
     * 
     * 这两项检查的保守性可能导致不必要的唤醒，
     * 但这仅发生在多个并发获取/释放操作竞争的场景中，
     * 而这些节点大多需要立即或稍后被唤醒。
     */
    if (propagate > 0 || h == null || h.waitStatus < 0 ||
        (h = head) == null || h.waitStatus < 0) {
        Node s = node.next;
        if (s == null || s.isShared())
            doReleaseShared();
    }
}

/**
 * Cancels an ongoing attempt to acquire.
 * 取消一个正在进行的资源获取尝试。
 *
 * @param node the node
 */
private void cancelAcquire(Node node) {
    // Ignore if node doesn't exist
    // 如果节点为空则忽略
    if (node == null)
        return;

    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.
    // predNext 是需要断开的表面后继节点。如果下面的 CAS 操作失败，
    // 说明我们与其他取消或信号操作竞争失败，此时无需进一步操作。
    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.
    // 此处可直接写入而无需 CAS 操作。
    // 在此原子步骤后，其他节点可跳过当前节点。
    // 在此之前，我们不受其他线程干扰。
    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.
        // 如果后继节点需要信号通知，尝试设置前驱节点的 next 链接，
        // 以便信号能传递。否则唤醒后继以传播信号。
        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
    }
}

/**
 * Checks and updates status for a node that failed to acquire.
 * Returns true if thread should block. This is the main signal
 * control in all acquire loops.  Requires that pred == node.prev.
 * 检查并更新获取资源失败的节点的状态。
 * 如果线程应当阻塞则返回 true。这是所有获取循环中的核心信号控制逻辑。
 * 要求：pred 必须是 node 的前驱节点（即 pred == node.prev）。
 *
 * @param pred node's predecessor holding status
 * @param node the node
 * @return {@code true} if thread should block
 */
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    int ws = pred.waitStatus;
    if (ws == Node.SIGNAL)
        /*
         * This node has already set status asking a release
         * to signal it, so it can safely park.
         * 前驱节点已设置为 SIGNAL 状态，表明它将在释放时通知当前节点，
         * 因此当前线程可以安全阻塞。
         */
        return true;
    if (ws > 0) {
        /*
         * Predecessor was cancelled. Skip over predecessors and
         * indicate retry.
         * 前驱节点已被取消。向前遍历跳过所有已取消的前驱节点，
         * 并指示调用方需要重试获取。
         */
        do {
            node.prev = pred = pred.prev;
        } while (pred.waitStatus > 0);
        pred.next = node;
    } else {
        /*
         * waitStatus must be 0 or PROPAGATE.  Indicate that we
         * need a signal, but don't park yet.  Caller will need to
         * retry to make sure it cannot acquire before parking.
         * 前驱状态必须是 0 或 PROPAGATE。将前驱状态标记为需要信号通知（SIGNAL），
         * 但当前线程暂不阻塞。调用方需要重试获取，确保在阻塞前无法获取资源。
         */
        compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
    }
    return false;
}

/**
 * Convenience method to interrupt current thread.
 * 中断当前线程的一个便捷方法
 */
static void selfInterrupt() {
    Thread.currentThread().interrupt();
}

/**
 * Convenience method to park and then check if interrupted
 * 挂起当前线程然后检查是否已中断的便捷方法
 *
 * @return {@code true} if interrupted
 */
private final boolean parkAndCheckInterrupt() {
LockSupport.park(this);
return Thread.interrupted();
}

Various flavors of acquire, varying in exclusive/shared and control modes. Each is mostly the same, but annoyingly different. Only a little bit of factoring is possible due to interactions of exception mechanics (including ensuring that we cancel if tryAcquire throws exception) and other control, at least not without hurting performance too much.

acquire 操作存在多种变体，包括独占/共享模式以及不同的控制方式。这些操作大体相似，但令人烦恼的是它们存在差异。由于异常处理机制（包括确保当 `tryAcquire 抛出异常时能正确取消操作）与其他控制逻辑的交互影响，只能进行有限的重构，至少在不严重损害性能的前提下无法进行更多重构。