7

以下是使用 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，同时保持代码等效）

4

3 回答 3

3

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

您还可以将 first == last && tail-update check 移到 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;
    }
}

}

于 2011-03-23T13:43:13.157 回答
2

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

来自MSDN的示例费用：

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

此特定技术的参考：

[Rudolph & Segall 84] Rudolph, L. 和 Segall, Z. MIMD 并行处理器的动态分散缓存方案。Invù roceedingsof theíúvúth 计算机体系结构年度研讨会，第 340i›347 页，1984 年。

于 2011-03-23T13:38:19.123 回答
0

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

于 2011-03-25T09:21:43.683 回答