AQS为什么用双向链表

众所周知,AQS内的同步队列为双向链表,但为什么用双向链表呢

网上大多数回答是这样的

因为链表移除和添加比较方便,只需要改动prev和next节点的指向即可,移除和添加都只需要操作一次,时间复杂度为O(1)。如果使用数组去实现,随着数据量的增加每次操作需要移动的次数也会更重。

其实如果仅仅是为了方便添加和移除node,单向链表和head+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);
    }
}

通过查看AQS源码发现,当前线程在死循环中尝试获取同步状态,而只有前驱节点是头结点才能获取到同步状态。

原因:

  • 头结点是成功获取到同步状态的节点,而头节点的线程释放了同步状态后,将会唤醒其后继节点,后继节点的线程被唤醒后需要检查自己的前驱节点是否为头结点
  • 为了维护同步队列的FIFO原则。

判断是否阻塞

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

参考:

<<java并发编程的艺术>>

https://segmentfault.com/q/1010000018514020

# Java 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×