关于AQS中unparkSuccessor从tail向head遍历查找的思考?

为什么在unparkSuccessor中查找需要被唤醒的节点是从tail向head查找呢?

这个问题,我在之前分析AQS时已经解析了一次,我觉得这是AQS中考虑得非常周全的地方,和以前阅读jdk源码的感触一样 ,真的可以感觉到这些真正的大佬的思想是何等的高度.

要想明白这个问题,需要从节点入队开始说起,前面我在解析lock的过程中分析了节点入队的操作,也就是addWaiter(),

主要的入队源码如下:

    private Node addWaiter(Node mode) {
        //将当前线程封装为阻塞队列的Node节点
        Node node = new Node(Thread.currentThread(), mode);
        // Try the fast path of enq; backup to full enq on failure
        //获取尾节点
        Node pred ![]()= tail;
        //如果尾节点不为null，则说明当前的阻塞队列已经有阻塞节点了，那么直接放入尾节点之后
        if (pred != null) {
            //tail(旧尾) <-- currentNode
            node.prev = pred;
            if (compareAndSetTail(pred, node)) {
                //tail(旧尾) --> currentNode  
                pred.next = node;
                return node;
            }
        }
        //如果pred是null，这说明当前阻塞队列可能是第一次初始化，阻塞队列是空的，当前节点作为头尾节点
        enq(node);
        return node;
    }

    private Node enq(final Node node) {
    //这里使用cas自旋操作,放在循环中,因为可能目前已经不满足之前的阻塞队列为空的条件了.
        for (;;) {
            Node t = tail;
            if (t == null) { // Must initialize
                //执行到这里说明,当前同步阻塞双向队列是空的,进行初始化,并且可以看出,同步阻塞双向队列的头元素是没有保存线程
                //数据的,初始化的时候设置的是一个空Node对象，head只保存了下一个节点的指针
                if (compareAndSetHead(new Node()))
                    //这样,下面再次执行for循环,tail就不是空了
                    tail = head;
            } else {
                //先: tail(即将成为旧的尾节点的尾节点) <-- currentNode
                node.prev = t;
                //后: cas设置当前准备添加的同步阻塞双向队列的节点为tail
                //cas成功,则tail(旧尾节点了) --> currentNode（当前操作的节点，并且已经是新的tail）
                if (compareAndSetTail(t, node)) {
                    t.next = node;
                    return t;
                }
            }
        }
    }

可以看到,入队时,分为以下三步,整体不是原子性操作,在执行期间,其他线程可能会调用unlock中的获取后续需要唤醒的节点.

那么就会出现问题,比如在第一步执行完之后,在最后一步执行完之前就在遍历获取节点元素了,如果从头部开始往tail遍历,那么就会出现无法访问到最后一个刚入队的元素,因为第三步还没有结束,没有next指针指向他,所以如果使用从尾部开始遍历,只要第二步的cas设置 tail结束了即可,不需要等到第三步结束. 所以这里的设计考虑真的是太太太严谨了

思考:这样设计的确很全面,但是相对于head开始遍历,在极致要求下,这样的耗时比从head开始遍历耗时要多,因为如果从head开始遍历,找到第一个即可返回,但是现在从尾部开始,需要遍历整个队列才能找到哪个离head最近的需要唤醒的节点,当然这是不可避免的,因为从head开始遍历会有直接的并发安全问题.

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2021/10/16 17:41