同步器(AQS)为什么维护的同步队列是一个双向队列？

Question

为什么要用双端队列呢？单向队列我感觉也可以实现功能，因为大部分的查找只是查找后继节点，或者是判断当前节点的前驱是不是head。

另外，同步器维护的waiter的node到底是什么作用？
源码的注释是为了指向condition的waiter节点，但是没有特别看明白。

Answer 1

很明显嘛，假如你的队列是单向的如：Head -> N1 -> N2 -> Tail。出队的时候你要获取N1很简单，Head.next就行了，入队你就麻烦了，你要遍历整个链表到N2，然后N2.next = N3;N3.next = Tail。入队的复杂度就是O(n),而且Tail也失去他的意义。相反双向链表出队和入队都是O(1)时间复杂度。说白了空间换时间。

Answer 2

AQS的双向链表，如果只是简单的加入节点与移除节点，其实使用单链表加上head、tail已经足够，与出队，入队没有关系。

在AQS中，还有其它一些功能。比如，线程A此时占有锁，线程B也来lock，因为A占有，B会判断是否需要阻塞，如下代码为判断是否需要阻塞，

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.
         */
        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.
         */
        compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
    }
    return false;
}

需要阻塞的条件是前驱节点的waitStatus=Node.SIGNAL,在代码块

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

中，如果pred.waitStatus > 0就要不断向前查找，此时就是双向链表的特性，可以循环向前查找。

以上是双向链表在AQS中的一个体现。

Answer 3

源码里面的注释，显示是为了double 可以扫描进行 double-check