多用户无锁队列的实现

Question

最近，我遇到了一个问题:假设有3个使用者线程，需要实现一个没有锁的synchronization)队列(不能使用，这样就不会阻塞使用线程)。假设队列已经包含数据。

我想了一会儿，偶然发现了原子操作，如果仔细使用这些操作会有所帮助。我的实现如下所示。由于数据已经在队列中，所以我没有实现enqueue方法，也没有在构造函数中填充数组。

public class SPMCQueue {

    private AtomicInteger index = new AtomicInteger(0);

    public int[] arr;

    public SPMCQueue(int size) {
        arr = IntStream.range(0, size).toArray();
    }

    public Integer dequeue() {
        Integer ret = null;
        int x = index.getAndIncrement();
        if (x < arr.length) {
            ret = arr[x];
            System.out.println(arr[x] + " by " + Thread.currentThread().getName());
        }
        else {
            throw new RuntimeException("Queue is empty");
        }
        return ret;
    }
}

class QueueTest {
    public static void main(String[] args) {

        SPMCQueueq = new SPMCQueue(40);

        Runnable t1 = () -> {
            try {
            while (true) {
                q.dequeue();
            }
            }catch(Exception e) {

            }
        };

        Runnable t2 = () -> { 
            try {
            while(true) { q.dequeue(); }
            }catch(Exception e) {

            }
        };

        Runnable r3 = () -> { 

            try {
                while(true) { q.dequeue(); }
            } catch (Exception e) {
                // TODO Auto-generated catch block
                //e.printStackTrace();
            }

        };

        Thread thread1 = new Thread(t1);
        Thread thread2 = new Thread(t2);
        Thread thread3 = new Thread(r3);

        thread1.start();
        thread2.start();
        thread3.start();

    }
}

我已经执行了上面的程序，结果显示，所有三个使用者都在使用数据，尽管是无序的，一些线程比其他线程消耗更多的数据，但是我没有看到任何数据在o/p中多次出现。

我有以下问题：

1. 上述实施是否有任何问题？
2. 实现无锁消费者队列的其他方法是什么？

Answer 1

我想同时给我的答复：https://stackoverflow.com/a/21101904/7340499，因为这是一个类似的问题，你的。

那么，你的问题：

但我没有看到任何数据多次出现在o/p中。

这是意料之中的。因为，getAndIncrement()是原子的，只要访问该函数，就会得到不同的x值，从而得到不同的输出。但是，由于将"getAndIncrement()“和"System.out.print()”函数组合在一个非原子的去队列操作中，您的输出有时会出现故障，例如在一个线程上得到x=1，而另一个线程中断，得到x=2并打印出来，然后初始线程完成打印。我认为，正如第1段所要求的那样，这也指出了你的执行问题。您的应用程序是否可以对队列进行无序处理？

实现无锁消费者队列的其他方法是什么？

嗯，原子操作是一种方式，正如你已经注意到的。但在本质上，他们非常像锁，无论如何。它们只是在较小的范围内运行(尽管存在一些实现上的差异)。因此，很难将它们概念化为不同的方法，至少对我自己来说是这样。除此之外，我相信这里还有一些很好的资源：Lock Free Queue -- Single Producer, Multiple Consumers