无锁队列中的这些行是不必要的吗？

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;
        }
    }
}

（head和tail是队列的成员）

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

我在这里错过了什么吗？这些检查会影响代码的正确性吗？

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

Answer 1

是的，在 Java 中，考虑到它有垃圾收集功能，这些 if 只具有优化的真正价值，而且它有点大：与仅从内存中读取相比，CAS 非常昂贵，因此请确保该值在同时，从而减少后续 CAS 失败的机会，有助于减少 CAS 重试次数，从而提高性能。

您还可以移动第一个==最后一个&& 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;
    }
}

}

Answer 2

它们不是必需的，但出于性能原因使用，请注意检查是在不使用原子操作的情况下进行的。

来自 MSDN 的示例成本：

• MemoryBarrier 是测量为 20-90 个周期。
• InterlockedIncrement 测量为 36-90 个周期。
• 获取或释放关键部分被测量为需要 40-100 个周期。
• 测量获取或释放互斥体需要大约 750-2500 个周期。

此特定技术的参考：

[鲁道夫与Segall 84]鲁道夫，L.和
Segall, Z. 动态去中心化
MIMD 并行缓存方案
处理器。 Invù roceedingsof
theíúvúth 年度研讨会
计算机体系结构，页面
340i›347, 1984.

Answer 3

它是非阻塞链表算法。
详细描述在JCP书中（15.4.2. A Nonblocking Linked List）