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

implement-your-own blocking queue in java

提问by tugcem

I know this question has been asked and answered many times before, but I just couldn't figure out a trick on the examples found around internet, like thisor thatone.

我知道这个问题之前已经被问过和回答过很多次了，但我只是想不出在互联网上找到的例子中的一个技巧，比如这个或那个。

Both of these solutions check for emptiness of the blocking queue's array/queue/linkedlist to notifyAllwaiting threads in put()method and vice versa in get()methods. A commentin the second link emphasizes this situation and mentions that that's not necessary.

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

So the question is; It also seems a bit odd to me to check whether the queue is empty | full to notify all waiting threads. Any ideas?

所以问题是；检查队列是否为空对我来说似乎也有点奇怪 | full 通知所有等待线程。有任何想法吗？

Thanks in advance.

提前致谢。

回答by Adrian Shum

I think logically there is no harm doing that extra check before notifyAll().

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

You can simply notifyAll()once you put/get something from the queue. Everything will still work, and your code is shorter. However, there is also no harm checking if anyone is potentially waiting (by checking if hitting the boundary of queue) before you invoke notifyAll(). This extra piece of logic saves unnecessary notifyAll()invocations.

您可以简单地notifyAll()从队列中放入/获取一些东西。一切仍然有效，并且您的代码更短。但是，在您调用notifyAll(). 这个额外的逻辑可以节省不必要的notifyAll()调用。

It just depends on you want a shorter and cleaner code, or you want your code to run more efficiently. (Haven't looked into notifyAll()'s implementation. If it is a cheap operation if there is no-one waiting, the performance gain may not be obvious for that extra checking anyway)

这取决于您想要更短更干净的代码，或者您希望代码更有效地运行。（还没有研究notifyAll()的实现。如果没有人等待它是一种廉价的操作，那么额外检查的性能提升可能并不明显）

回答by TwoThe

The reason why the authors used notifyAll()is simple: they had no clue whether or not it was necessary, so they decided for the "safer" option.

作者使用的原因notifyAll()很简单：他们不知道是否有必要，所以他们决定选择“更安全”的选项。

In the above example it would be sufficient to just call notify()as for each single element added, only a single thread waiting can be served under all circumstances.

在上面的示例中，只需notify()为添加的每个单个元素调用as就足够了，在所有情况下只能为一个等待的线程提供服务。

This becomes more obvious, if your queue as well has the option to add multiple elements in one step like addAll(Collection<T> list), as in this case more than one thread waiting on an empty list could be served, to be exact: as many threads as elements have been added.

这变得更加明显，如果您的队列也可以选择在一个步骤中添加多个元素，例如addAll(Collection<T> list)，在这种情况下，可以为多个等待空列表的线程提供服务，准确地说：与元素一样多的线程添加。

The notifyAll()however causes an extra overhead in the special single-element case, as many threads are woken up unnecessarily and therefore have to be put to sleep again, blocking queue access in the meantime. So replacing notifyAll()with notify()would improve speed in this special case.

该notifyAll()然而，导致在特殊的单元素的情况下，额外的开销，因为许多线程不必要的被唤醒，因此必须再次进入睡眠状态，阻塞在此期间队列的访问。因此notifyAll()，在这种特殊情况下替换withnotify()会提高速度。

But then notusing wait/notify and synchronized at all, but instead use the concurrent package would increase speed by a lot more than any smart wait/notify implementation could ever get to.

但是，根本不使用等待/通知和同步，而是使用并发包将提高速度，这比任何智能等待/通知实现所能达到的速度要快得多。

回答by Ayesh Qumhieh

I know this is an old question by now, but after reading the question and answers I couldn't help my self, I hope you find this useful.

我现在知道这是一个老问题，但在阅读了问题和答案后，我忍不住了，我希望你觉得这有用。

Regarding checking if the queue is actually full or empty before notifying other waiting threads, you're missing something which is both methods put (T t)and T get()are both synchronizedmethods, meaning that only one thread can enter one of these methods at a time, yet this will not prevent them from working together, so if a thread-a has entered put (T t)method another thread-b can still enter and start executing the instructions in T get()method before thread-a has exited put (T t), and so this double-checkingdesign is will make the developer feel a little bit more safe because you can't know if future cpu context switching if will or when will happen.

关于在通知其他等待线程之前检查队列实际上是满还是空，您错过了既是方法put (T t)又T get()是synchronized方法的东西，这意味着一次只有一个线程可以进入这些方法之一，但这不会阻止他们一起工作，所以如果一个线程-a进入了put (T t)方法，另一个线程-b仍然可以T get()在线程-a退出之前进入并开始执行方法中的指令put (T t)，所以这种double-checking设计会让开发者感觉更安全一点因为您无法知道未来的 CPU 上下文切换是否会或何时会发生。

A better and a more recommended approach is to use Reentrant Locksand Conditions:

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

//I've edited the source code from this link

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

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;
}

Using this approach there's no need for double checking, because the lockobject is shared between the two methods, meaning only one thread a or b can enter any of these methods at a time unlike synchronized methods which creates different monitors, and only those threads waiting because the queue is full will be notified when there's more space, and the same goes for threads waiting because the queue is empty, this will lead to a better cpu utilization. you can find more detailed example with source code here

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

回答by Sumanth Varada

I would like to write a simple blocking queue implementation which will help the people to understand this easily. This is for someone who is novice to this.

我想编写一个简单的阻塞队列实现来帮助人们轻松理解这一点。这适用于对此不熟悉的人。

class BlockingQueue {
private List queue = new LinkedList();

private int limit = 10;

public BlockingQueue(int limit){
    this.limit = limit;
}

public synchronized void enqueue(Object ele) throws InterruptedException {
    while(queue.size() == limit)
        wait();
    if(queue.size() == 0)
        notifyAll();
    // add
    queue.add(ele);
}

public synchronized Object deque() throws InterruptedException {
    while (queue.size() == 0)
        wait();
    if(queue.size() == limit)
        notifyAll();
    return queue.remove(0);
}

}

}

---

---