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

寂寞的肥皂
  • 54

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

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

回复
阅读 5.5k
3 个回答
✓ 已被采纳

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

liaochuanhu
  • 3
新手上路,请多包涵

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中的一个体现。

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

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏