java - 除了 ConcurrentLinkedQueue，我是否需要使用带锁的 LinkedList？

Question

我目前正在使用 ConcurrentLinkedQueue，这样我就可以使用自然顺序 FIFO，也可以在线程安全应用程序中使用它。我需要每分钟记录队列的大小并且考虑到这个集合不能保证大小并且计算大小的成本也是 O(N)，是否有任何替代的有界非阻塞并发队列我可以在获取的地方使用大小不会是一个昂贵的操作，同时添加/删除操作也不昂贵？

如果没有集合，是否需要使用带锁的LinkedList？

Answer 1

如果您真的(真的)需要记录您当前正在处理的Queue 的正确当前大小——您需要阻塞。别无他法。您可以认为维护一个单独的 LongAdder 字段可能会有所帮助，可能会将您自己的接口(interface)作为 ConcurrentLinkedQueue 的包装器，例如:

interface KnownSizeQueue<T> {
    T poll();
    long size();
}

和一个实现:

static class ConcurrentKnownSizeQueue<T> implements KnownSizeQueue<T> {

    private final ConcurrentLinkedQueue<T> queue = new ConcurrentLinkedQueue<>();
    private final LongAdder currentSize = new LongAdder();

    @Override
    public T poll() {
        T result = queue.poll();
        if(result != null){
            currentSize.decrement();
        }
        return result;
    }

    @Override
    public long size() {
        return currentSize.sum();
    }
}

我只是鼓励您再添加一种方法，例如remove 到界面中并尝试对代码进行推理。你很快就会意识到，这样的实现仍然会给你一个错误的结果。所以，不要这样做。

如果你真的需要它，唯一可靠的获取大小的方法是为每个操作阻塞。这是一个高昂的代价，因为 ConcurrentLinkedQueue 被记录为:

This implementation employs an efficient non-blocking...

您将失去这些属性，但如果这是一个不关心它的硬性要求，您可以编写自己的:

static class ParallelKnownSizeQueue<T> implements KnownSizeQueue<T> {

    private final Queue<T> queue = new ArrayDeque<>();
    private final ReentrantLock lock = new ReentrantLock();

    @Override
    public T poll() {

        try {
            lock.lock();
            return queue.poll();
        } finally {
            lock.unlock();
        }
    }

    @Override
    public long size() {
        try {
            lock.lock();
            ConcurrentLinkedQueue
            return queue.size();
        } finally {
            lock.unlock();
        }
    }
}

或者，当然，您可以使用现有的结构，例如 LinkedBlockingDeque 或 ArrayBlockingQueue 等 - 取决于您的需要。