java - 无锁队列中的这些行不是必需的吗？

Question

下面是使用 compareAndSet(在 Java 中)的无锁队列的一些代码:

public void enq(T value) {
    Node newNode = new Node(value);
    while(true) {
        Node last = tail.get();
        Node next = last.next.get();

        if(last != tail.get())
            continue;   //???       

        if (next != null) { //improve tail
            tail.compareAndSet(last, next);
            continue;
        }

        if (last.next.compareAndSet(null, newNode)) {   //update last node
            tail.compareAndSet(last, newNode);  //update tail
            return;
        }
    }
}

public T deq() throws EmptyException {
    while(true) {
        Node first = head.get();
        Node last = tail.get();
        Node next = first.next.get();

        if(first != head.get())
            continue;   //???

        if(first == last) {
            if (next == null)
                throw new EmptyException();

            tail.compareAndSet(last, next);
            continue;
        }

        T value = next.value;
        if (head.compareAnsdSet(first, next)) {
            return value;
        }
    }
}

(头和尾是队列的成员)

在 deq 和 enq 函数中，第一次检查对我来说似乎是不必要的。 (评论“？？？”的)我怀疑它只是为了某种优化。

我是不是漏掉了什么？这些检查会影响代码的正确性吗？

(代码取自“多处理器编程的艺术”，尽管我确实重构了代码风格以减少嵌套的 if 和 else，同时保持代码等效)

Answer 1

是的，在 Java 中，考虑到它有垃圾收集，那些 ifs 只有作为优化的真正值(value)，而且它有点大:与仅从内存读取相比，CAS 非常昂贵，所以确保该值没有' t 在此期间发生了变化，从而降低了后续 CAS 失败的可能性，有助于减少 CAS 重试次数，从而提高性能。

您还可以将 first == last && tail-update 检查移动到 head.CAS 内部，作为进一步的优化:只有当 head 更新时，tail 才会落后，因此只有在 CAS 成功时才进行检查感觉。您也可以将 tail.get 移动到那里，因为您在其他任何地方都不需要它。下面的示例代码。希望这对您有所帮助!

public T deq() throws EmptyException {
while(true) {
    Node first = head.get();
    Node next = first.next.get();

    if (first != head.get())
        continue;

    if (next == null) {
        throw new EmptyException();
    }

    T value = next.value;

    if (head.compareAndSet(first, next)) {
        Node last = tail.get();

        if (first == last) {
            tail.compareAndSet(last, next);
        }

        return value;
    }
}