Java中是否有任何（无界）公平阻塞队列？

Question

如果有多个消费者从同一个队列中移除元素，是否有任何实现阻塞队列保证公平的take()操作。我检查了LinkedBlockingQueue和LinkedTransferQueue，似乎它们都是不公平的。ArrayBlockingQueue提供公平操作，但它是有界的。

- user467158

---

并发链表怎么样？（好吧，它本质上不是一个“队列”...而且我不确定它是否更加“公平”） - user166390

Answer 1

我们可以使用像ConcurrentLinkedQueue和公平Semaphore这样的无界队列来实现一个无界公平阻塞队列。下面的类没有实现BlockingQueue接口中的所有方法，只是为了演示而实现了其中几个方法。主函数main()只是一个测试。

public class FairBlockingQueue<T> {

    private final Queue<T> queue;
    private final Semaphore takeSemaphore;

    public FairBlockingQueue() {
        queue = new ConcurrentLinkedQueue<T>();
        takeSemaphore = new Semaphore(0, true);
    }

    public FairBlockingQueue(Collection<T> c) {
        queue = new ConcurrentLinkedQueue<T>(c);
        takeSemaphore = new Semaphore(c.size(), true);
    }

    public T poll() {
        if (!takeSemaphore.tryAcquire()) {
            return null;
        }
        return queue.poll();
    }

    public T poll(long millis) throws InterruptedException {
        if (!takeSemaphore.tryAcquire(millis, TimeUnit.MILLISECONDS)) {
            return null;
        }
        return queue.poll();
    }

    public T take() throws InterruptedException {
        takeSemaphore.acquire();
        return queue.poll();
    }

    public void add(T t) {
        queue.add(t);
        takeSemaphore.release();
    }

    public static void main(String[] args) throws Exception {
        FairBlockingQueue<Object> q = new FairBlockingQueue<Object>();
        Object o = q.poll();
        assert o == null;
        o = q.poll(1000);
        assert o == null;

        q.add(new Object());
        q.add(new Object());
        q.add(new Object());

        o = q.take();
        assert o != null;
        o = q.poll();
        assert o != null;
        o = q.poll(1000);
        assert o != null;

        o = q.poll();
        assert o == null;
    }
}

- Simeon Malchev

---

不错且公平的解决方案，尽管我建议使用PriorityBlockingQueue。 - Michael

谢谢，迈克尔。如果我们想要使用现成的东西，我们可以选择PriorityBlockingQueue，但是PBQ和上面建议的FBQ在排序/顺序方面有所不同。PBQ使用优先堆按其自然排序对其元素进行排序，并按照特定顺序从PBQ中取出元素，而FBQ由ConcurrentLinkedQueue支持，这是一个普通的FIFO队列。 - Simeon Malchev

顺便提一下，在 Java SE 6 中，PriorityBlockingQueue 中的 take() 对调用者是公平的，因为它使用了一个公平的 ReentrantLock 实现，但在 Java SE 7 中，它使用了一个非公平的 ReentrantLock 实现，因此不再对调用者公平。我刚刚检查了源代码。 - Simeon Malchev

Answer 2

PriorityBlockingQueue

PriorityBlockingQueue

是一个 Java 中的类，它实现了一个基于优先级的阻塞队列。它是线程安全的，并且可以用于多线程环境中。该类使用可重入锁来保证线程安全性，并且提供了许多方法来操作队列中的元素。如果您需要在 Java 中使用优先级队列，那么 PriorityBlockingQueue 可能是一个不错的选择。

- Woot4Moo

Answer 3

可以为SynchronousQueue指定公平策略：

将公平性设置为真实的队列以FIFO顺序授予线程访问权。

- Vasil Remeniuk

---

看那个类的Javadoc让我笑了，比如清除什么也不做。 - Woot4Moo

@Woot4Moo，你显然（无意刻意）不理解那个类的工作原理——它根本没有容量，因此无法被清除。 - Jed Wesley-Smith

你显然不觉得将没有任何作用的事情记录下来很有趣。 - Woot4Moo