我可以在 Java 中使用信号量实现阻塞队列吗？

Question

请问是否可以使用Semaphore来实现阻塞队列？

在下面的代码中，我使用一个信号量来保护临界区，另外两个信号量对象来跟踪空槽和填充对象的数量。

public class BlockingQueue {
  private List<Object> queue = new LinkedList<Object>();
  private int limit;
  private Semaphore slots; // semaphore for empty slots
  private Semaphore objs;  // semaphore for filled slots
  private Semaphore mutex; // for the critical section
  public BlockingQueue(int limit) {
    this.limit = limit;
    this.slots = new Semaphore(limit); // initial empty slot = capacity
    this.objs = new Semaphore(0);
    this.mutex = new Semaphore(1);
  }
  private void enqueue(Object o) throws InterruptedException {
    slots.acquire();
    mutex.acquire(); // critical section starts
    queue.add(o);
    mutex.release(); // critical section ends
    objs.release();
  }
  private Object dequeue() throws InterruptedException {
    objs.acquire();
    mutex.acquire(); // critical section starts
    Object o = queue.remove(0);
    mutex.release(); // critical section ends
    slots.release();
    return o;
  }
}

Answer 1

添加到之前的评论 - 我们可以同意您的代码有效（这是一个众所周知的算法），特别是您在保护 LinkedList 方面是正确的，因为它不是内部线程安全的。

但是，如果您将代码与 java util 实现进行比较 http://grepcode.com/file_/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/concurrent/ArrayBlockingQueue.java/?v=source 它可能会提出一些要考虑的问题：

请 Google 讨论 "ReentrantLock versus Binary Semaphore"：它们都创建互斥锁并保护 临界区，但前者更好描述你的意图，加上它可能更容易为将来的维护。例如，一个程序员同事不会意外地释放一个没有获得 ReentrantLock 的线程
Google 关于 "semaphore versus condition variable" 的讨论：两者都允许您 "wait for something to become available"，但条件变量可能更通用，而且您可以将所有条件绑定到单个锁（如 java util 代码所做的那样）。我假设这对性能有一些轻微影响，加上您需要处理未来需求的方式，例如中断、超时、崩溃。这不会使你的代码"wrong"，它只是供你考虑的东西。

Answer 2

未经测试，我会说这是可行的。但是，每次release()都会通知阻塞在acquire()中的线程。因此，您实际上至少具有与重入锁+条件相同的成本，可能更糟，因为有 2 次获取和 2 次释放（）调用。

Answer 3

信号量是实现互斥&同步的另一种方式。二进制信号量或互斥量可用于锁定和解锁临界区。通用信号量或计数信号量可用于跟踪空闲槽和占用槽。

我可以在 Java 中使用信号量实现阻塞队列吗？

Can I implement blocking queue using Semaphore in Java?

java

mutex

semaphore

blockingqueue