AQS唤醒后继线程 为什么是从后向前遍历

Question

    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);
    }

如果没有合法的数据，从后向前遍历，为什么这么做呢？从前向后不行吗？

Answer 1

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

如果下一个节点为空或者被取消，则从后向前遍历。下一个都是空了，也没办法next吧。如果下一个节点是正常节点，也没有说一定要从后向前。

Answer 2

我目前测试出来的一个原因是和acquireQueued方法有关。

acquireQueued方法中有

p.next = null; // help GC

因为执行到这里，p.next关联的线程已经获取到锁了，不需要再根据next唤醒线程了。所有置p.next = null，然后unparkSuccessor中就可能需要从tail开始往前遍历了。

    final boolean acquireQueued(final Node node, int arg) {
        boolean failed = true;
        try {
            boolean interrupted = false;
            for (;;) {
                final Node p = node.predecessor();
                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);
        }
    }

下边是我用idea调试，代码如何执行才会导致从后向前遍历。

    public static void main(String[] args) {
        ReentrantLock reentrantLock = new ReentrantLock();
        for (int i = 0; i < 2; i++) {
            new Thread(() -> {
                try {
                    reentrantLock.lock();
                    //Thread.sleep(10000);
                    reentrantLock.unlock();
                } catch (Exception e) {
                    e.printStackTrace();
                }

            }).start();
        }

    }

一共两个线程，假设命名为thread-0和thread-1。

1. 让thread-0执行到reentrantLock.unlock();
2. 让thread-1尝试获取锁，然后会进入acquireQueued方法，让for循环执行一次。之所以执行一次是为了让p.waitStatus=-1。
3. 让thread-0释放锁，最终进入unparkSuccessor方法。先不往后执行。
4. 让thread-1继续执行，会走到了p.next = null 这里。
5. 这个时候你如果让thread-0继续执行，就会走到从后向前遍历的部分。

这是我找到的一种情况。

我搜索到的很多文章的说法是在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;
        if (pred != null) {
            node.prev = pred;
            if (compareAndSetTail(pred, node)) {
                //说代码执行到这里,node已经是尾节点了，但是pred.next = node没执行，next可能存在短暂为null
                pred.next = node;
                return node;
            }
        }
        enq(node);
        return node;
    }

但是我没调试出来。

Answer 3

当下个节点为已取消时，当前节点的下个节点是不确定的，所以需要从后往前获取。
如下的取消函数，在取消时，先修改状态为cancelled，然后再修改指向下个节点的指针为自身，
如果获取唤醒线程正好卡在两个操作之间，则会导致从前往后遍历获得唤醒线程失败。
有两种可能，第一种进入死循环，第二种获取的不是第一个待唤醒的线程

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