JAVA 中的无等待队列实现

Question

我一直在尝试使用 Alex Kogan 和 Erez Petrank 已经编写的无等待队列，摘自 here，却遇到了问题。我无法理解在第 5 页和第 7 页的 que() 和 deque() 方法中需要使用确切的线程 ID：

void enq(int value) {
    long phase = maxPhase() + 1; // cf. Figure 3b
    state.set(TID, new
        OpDesc(phase, true, true, new Node(value, TID)));
    help(phase);
    help finish enq();
}

和

int deq() throws EmptyException {
    long phase = maxPhase() + 1; // cf. Figure 5a
    state.set(TID, new OpDesc(phase, true, false, null));
    help(phase);
    help finish deq();
    Node node = state.get(TID).node;
    if (node == null) {
        throw new EmptyException();
    }
    return node.next.get().value;
}

应该使用什么线程 ID？

Answer 1

在论文中他们说 TID 是 [0, . . . , NUM THRDS−1]. 范围内的一个 int，因此它看起来像是一个手动分配的号码。

我没看过论文，不知道有没有严格要求只能使用满足这个规范的标识符。 java.lang.Thread 上有一个 long getId() 方法。见 Javadoc for Thread.getId():

Returns the identifier of this Thread. The thread ID is a positive long number generated when this thread was created. The thread ID is unique and remains unchanged during its lifetime. When a thread is terminated, this thread ID may be reused.

您可以使用它而不是自己分配 TID。

Answer 2

考虑到 JDK 中的所有队列选择并发包，我不得不说我不相信你选择这样一个非标准队列实现。

首先，从你发的方法来看，最差的deq()方法性能很差。它在队列为空时抛出异常，这对于任何需要这种无等待队列的应用程序来说都是非常昂贵的。

其次，论文中的性能测量是基于动态分配的队列；其中内存分配碎片和页面错误将是这里的主要性能损失。实际上，可以通过 peak arrival rate * peak lasting period 轻松估计正常情况下的最大队列长度，并将队列设置为静态分配该容量。生产者试图放入队列已满的任何情况都可以简单地暂停（并且不太可能发生）。即使发生这种情况，线程停放的性能损失通常也是 1 毫秒。

如果您正在寻找真实世界生产系统中小于 1 毫秒的延迟，Java 可能不适合您。如果没有精细的内存对齐，即使有可能实现也是非常困难的。是的，LMAX 使用 Disruptor 做到了，但恕我直言，只是通过向 JVM 添加一些自定义内存管理包。

所以从所有实践的角度来看，你应该在 JDK 中使用标准队列，或者转向 Disruptor，或者使用 C/C++。这种具有未经证实的实现的数据结构本身并不是一个正确的选择。

JAVA 中的无等待队列实现

Wait-free queue implementation in JAVA

java

multithreading

queue

theory

wait-free