java中的您自己的实现队列

Question

[我知道这个问题以前曾被问过很多次，但我只是想不出互联网上的例子，例如this或that一个窍门。

[这两种解决方案都在notifyAll方法中检查阻塞队列的数组/队列/链表是否为put()等待线程，而在get()方法中则为空。第二个链接中的comment强调了这种情况，并指出这是不必要的。

所以问题是；检查队列是否为空对我来说似乎也有些奇怪。通知所有等待线程已满。有什么想法吗？

提前感谢。

Answer 1

我现在知道这是一个老问题，但是在阅读了问题和答案之后，我无济于事，希望您觉得这个有用。

关于在通知其他等待线程之前检查队列是否实际上已满或为空，您丢失了一些东西，而这两种方法put (T t)和T get()都是synchronized方法，这意味着只有一个线程可以输入以下一种：一次只能使用这些方法，但这不会阻止它们一起工作，因此，如果线程a已进入put (T t)方法，另一个线程b仍可以进入并开始执行线程[a]中的T get()方法中的指令退出put (T t)，因此此double-checking设计将使开发人员感到更加安全，因为您不知道将来的cpu上下文切换是否会或何时会发生。

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

//我已经从此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;
}
使用这种方法，不需要double checking，因为lock对象在两种方法之间共享，这意味着与创建不同监视器的同步方法不同，只有一个线程a或b一次可以进入这些方法中的任何一个，当只有更多的空间时，才会通知那些由于队列已满而正在等待的线程，而由于队列为空而正在等待的线程也将得到通知，这将导致更好的cpu利用率。您可以找到包含源代码here]的更详细的示例

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

一旦从队列中放入/获取某些内容，您就可以简单地notifyAll()。一切仍然有效，并且您的代码更短。但是，在调用notifyAll()之前，是否有任何潜在的等待对象（通过检查是否达到队列边界）也没有任何危害。这种额外的逻辑节省了不必要的notifyAll()调用。

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

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

在上面的示例中，只需为添加的每个单个元素调用notify()就足够了，在所有情况下仅可以等待单个线程等待。

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

notifyAll()在特殊的单元素情况下会导致额外的开销，因为不必要地唤醒了许多线程，因此不得不重新进入睡眠状态，同时阻塞了队列访问。因此，用notifyAll()替换notify()将提高速度在这种特殊情况下>>。

但是然后not

使用等待/通知并完全同步，但是使用并发包将比任何智能等待/通知实现所能达到的速度提高很多。

我想编写一个简单的阻塞队列实现，这将帮助人们轻松理解这一点。这是给对此不熟悉的人的。

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

}

---

Answer 2

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

Answer 3

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

Answer 4

我想编写一个简单的阻塞队列实现，这将帮助人们轻松理解这一点。这是给对此不熟悉的人的。

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