在java中实现自己的阻塞队列

Question

我知道这个问题之前已被多次询问和回答,但我无法弄清楚互联网上的例子,比如这个或那个.

这两种解决方案都检查阻塞队列的数组/队列/链表的空白,notifyAll以及put()方法中的等待线程,反之亦然get().一个评论在第二环节强调了这一情况,并提到这是没有必要的.

所以问题是; 检查队列是否为空,对我来说似乎有点奇怪 完全通知所有等待的线程.有任何想法吗？

提前致谢.

Answer 1

我知道这是一个古老的问题,但在阅读了问题和答案后,我无法帮助自己,我希望你发现这很有用.

关于在通知其他等待线程之前检查队列是否实际已满或为空,您遗漏的是两种方法put (T t)并且T get()都是synchronized方法,这意味着一次只有一个线程可以进入这些方法之一,但这不会阻止他们从一起工作,所以如果一个线程-a已经进入put (T t)方法,另一个线程-b仍然可以T get()在线程-a退出之前进入并开始执行方法中的指令put (T t),因此这个double-checking设计将使开发人员感觉更安全一点因为你不知道未来的cpu上下文切换是否会发生.

更好和更推荐的方法是使用Reentrant Locks和Conditions:

//我已经从这个链接编辑了源代码

Condition isFullCondition;
Condition isEmptyCondition;
Lock lock;

public BQueue() {
    this(Integer.MAX_VALUE);
}

public BQueue(int limit) {
    this.limit = limit;
    lock = new ReentrantLock();
    isFullCondition = lock.newCondition();
    isEmptyCondition = lock.newCondition();
}

public void put (T t) {
    lock.lock();
    try {
       while (isFull()) {
            try {
                isFullCondition.await();
            } catch (InterruptedException ex) {}
        }
        q.add(t);
        isEmptyCondition.signalAll();
    } finally {
        lock.unlock();
    }
 }

public T get() {
    T t = null;
    lock.lock();
    try {
        while (isEmpty()) {
            try {
                isEmptyCondition.await();
            } catch (InterruptedException ex) {}
        }
        t = q.poll();
        isFullCondition.signalAll();
    } finally { 
        lock.unlock();
    }
    return t;
}

使用这种方法不需要double checking,因为lock对象在两个方法之间共享,这意味着只有一个线程a或b可以一次输入任何这些方法,这与创建不同监视器的同步方法不同,并且只有那些线程因为队列而等待当有更多空间时会通知已满,并且由于队列为空,等待线程也是如此,这将导致更好的CPU利用率.你可以在这里找到更详细的源代码示例

Answer 2

我认为从逻辑上讲，之前进行额外的检查并没有什么坏处notifyAll()。

notifyAll()您只需从队列中放入/取出一些东西即可。一切仍然有效，并且您的代码更短。但是，在调用之前检查是否有人可能正在等待（通过检查是否到达队列边界）也没有什么坏处notifyAll()。这段额外的逻辑可以节省不必要的notifyAll()调用。

这仅取决于您想要更短、更清晰的代码，或者您希望代码运行更高效。（还没有研究notifyAll()的实现。如果这是一个廉价的操作，并且没有人等待，那么对于额外的检查来说，性能增益可能并不明显）