V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
amiwrong123
V2EX  ›  Java

AQS 里 hasQueuedPredecessors 里为啥要先读取 tail 成员啊?

  •  
  •   amiwrong123 · 2020-05-17 13:38:46 +08:00 · 2214 次点击
    这是一个创建于 1412 天前的主题,其中的信息可能已经有所发展或是发生改变。
        public final boolean hasQueuedPredecessors() {
            // The correctness of this depends on head being initialized
            // before tail and on head.next being accurate if the current
            // thread is first in queue.
            Node t = tail; // Read fields in reverse initialization order
            Node h = head;
            Node s;
            return h != t &&
                ((s = h.next) == null || s.thread != Thread.currentThread());
        }
    

    如上,注释说了因为第一次入队,可能出现 head 初始化了,head.next 没有初始化。那就是定位到如下地方:

        private Node enq(final Node node) {
            for (;;) {
                Node t = tail;
                if (t == null) { // Must initialize
                    if (compareAndSetHead(new Node()))//先设置 head
                        tail = head;//再设置 tail
                } else {
                    node.prev = t;
                    if (compareAndSetTail(t, node)) {
                        t.next = node;
                        return t;
                    }
                }
            }
        }
    

    看了网上的解释,都说这样就可以让 hasQueuedPredecessors 中两个域读取完只有几种情况发生:

    1. tail 为 null,head 不为 null (相对的,不会出现相反的情况)
    2. 都为 null
    3. 都不为 null

    如下图,把 hasQueuedPredecessors 的两个读取域标记为蓝色,enq 的两次设置不标记颜色。无论怎么移动(保持先后相对位置),都只会出现上面几种情况。这好像证明了我的上面的观点。 1589693327(1)

    但是此时,我又想起来多线程不是有个 happen-before 还是什么玩意,意思就是说,多线程下,每个线程只会考虑单线程下的正确执行。 而且 hasQueuedPredecessors 里 读取 tail 和读取 head 没有什么依赖关系,那上图的 标记蓝色的 读取 tail 和读取 head 岂不是可以随便交换顺序,也就不能维持 ,读取 tail 先与 读取 head 的相对顺序了吗?那岂不是 就会出现 tail 为 null,head 不为 null 的相反情况了?

    哎,想太多,要疯了。

    5 条回复    2020-05-18 00:03:50 +08:00
    xingda920813
        1
    xingda920813  
       2020-05-17 14:26:35 +08:00
    amiwrong123
        2
    amiwrong123  
    OP
       2020-05-17 15:25:28 +08:00
    @xingda920813
    这篇我看了,大概就是我图片里那个意思。 但需要考虑什么 happen-before 语义不呢
    liangdu
        3
    liangdu  
       2020-05-17 19:54:51 +08:00 via Android
    颠倒两句赋值语句是否会影响最终的结果关键在于 return 的写法是否有考虑 4 种情况(如果是单线程,只有 2 种,要么全为空,要么,全为非空),

    明显上面代码只 return 逻辑只考虑 3 种情况(没考虑 tail 非空,head 空的情况会空指针异常)


    emmmmm 你要说这代码不好?但是不这么写你的逻辑就要加个多一次判断了,重新给 head 赋值了。

    至于你说的 happenbefore 原则,推理得不错,没想多,自信点,只是你对“语序逻辑是否依赖”没理解对而已,其实是有依赖的,所以 CAS 最恶心的地方就是为了降低锁的粒度而不得面对更复杂的场景(结果是好的,但增加理解的难度,优劣就不讨论了)。
    amiwrong123
        4
    amiwrong123  
    OP
       2020-05-17 20:18:30 +08:00
    @liangdu
    >只是你对“语序逻辑是否依赖”没理解对而已,其实是有依赖的

    我怎么看怎么赶脚 Node t = tail; Node h = head;这两句没啥依赖关系啊。

    对了,我又突然想起来了,难道是这是两次 volatile 写操作,然后会在每次 volatile 写后面,加 StoreStore 和 StoreLoad 屏障,然后才能 这两句 不会被 指令重排序 ?是因为这个原因吗
    liangdu
        5
    liangdu  
       2020-05-18 00:03:50 +08:00 via Android
    @amiwrong123 有 cas 地方都有 volatile 的,不能单单讨论两句赋值依赖性,要结合整个函数来来看是否线程安全。

    这里不存在重排问题,只是涉及 cas 可见性而已。但和我们上面讨论的不是一起回事哦!
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2764 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 12:18 · PVG 20:18 · LAX 05:18 · JFK 08:18
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.