notifyAll操作的复杂性

Question

我不理解Java Concurrency in Practice书中的以下片段。

当只有一个线程可以取得进展时，使用notifyAll是低效的--有时是一点，有时是严重的。如果有十个线程在条件队列上等待，调用notifyAll会导致它们每个线程都被唤醒，并争夺锁；然后它们中的大多数或所有线程会马上回到睡眠状态。这意味着每个事件都要进行大量的上下文切换和大量的争夺锁的获取，使（也许）一个线程取得进展。在最坏的情况下，使用notifyAll的结果是O(n²)的唤醒，其中n就足够了。)

一个例子在清单14.6中。

@ThreadSafe
public class BoundedBuffer<V> extends BaseBoundedBuffer<V> {
    // CONDITION PREDICATE: not-full (!isFull())
    // CONDITION PREDICATE: not-empty (!isEmpty())

    public BoundedBuffer(int size) { super(size); }

    // BLOCKS-UNTIL: not-full
    public  synchronized void put(V v) throws InterruptedException {
        while (isFull())
            wait();
        doPut(v);
        notifyAll();
    }

    // BLOCKS-UNTIL: not-empty
    public  synchronized V take() throws InterruptedException {
        while (isEmpty())
            wait();
        V v = doTake();
        notifyAll();
        return v;
    }
}

例如，我们可以有以下事件序列。

1. 两个消费者线程试图从缓冲区中获取一个对象，缓冲区是空的，所以他们被暂停。
2. 10个生产者向缓冲区放10个对象，缓冲区容量为10。
3. 100001个生产者试图把100001个对象放到缓冲区，缓冲区是满的，所以它们被暂停。
4. 第一个消费者从缓冲区中得到一个对象，并调用notifyAll。
5. 一个生产者将一个对象放入缓冲区，并调用notifyAll，缓冲区已满。

现在只有一个线程可以取得进展--消费者线程。我们还有100000个生产者，他们不能取得进展。

我不明白为什么在最坏的情况下，会有O(n)²)唤醒，在能取得进展的线程被唤醒之前。

我认为最坏的情况是以下顺序

1. 所有线程都被唤醒（因为notifyAll）。我们 "使用 "了O(n)次唤醒。
2. 一个生产者线程得到锁，其他线程被暂停。生产者线程不能取得进展，所以它被暂停，它释放锁。
3. 现在 只有一个 生产者线程被唤醒，因为使用了不同的机制（一个线程恢复执行，因为它得到了锁--但这次notifyAll是 不 调用）。) 我们只 "使用 "O(1)次唤醒。
4. 第二个生产者不能取得进展，所以它被暂停，它释放锁。
5. 类似的事件发生在所有其他等待的生产者身上。
6. 最后，可以取得进展的线程（消费者线程）被唤醒。

我想我们 "使用 "了O(n)+O(n)*O(1)=O(n)次唤醒。

是书上有错误，还是我这里有遗漏？

Answer 1

东西被放入队列n次。"n次唤醒就够了 "的意思是，理想情况下，我们希望当一个生产者把东西放进缓冲区的时候，比如说，一个消费者会被通知到，这样就会有n次通知，甚至更好的是，这些通知都是无争议的。但是相反，所有等待锁的线程，包括所有的生产者（减去1，做投放的那个）和所有的消费者（反正是在等待的那个），每次有东西掉进队列里都会收到通知，他们都会为了锁而争夺，调度器会选出一个赢家。我们甚至没有考虑被选中的线程要等待的情况，这只是一个细节）。所以有n次notifyAll被调用，每次投放一次，每次notifyAll都会唤醒多个生产者和多个消费者，这就是他们得到O(n)²)唤醒。

Answer 2

假设我们有n个消费者线程和n个生产者线程，并且缓冲区是空的(满缓冲区的例子类似)。所有线程都处于准备运行状态（调度器可以选择任何线程运行）。

如果有消费者线程运行 - 它将进入等待状态。如果有生产者运行 - 它将成功并调用notifyAll()。

最大化wait()调用(和唤醒)数量的情况。

Example for 5 producer and 5 consumer
+--------------+-------------------------------------+
| C-C-C-C-C-P  | all consumers move to waiting state |
+--------------+-------------------------------------+
| C*-C-C-C-C-P | 5 wake ups                          |
+--------------+-------------------------------------+
| C*-C-C-C-P   | 4 wake ups                          |
+--------------+-------------------------------------+
| C*-C-C-P     | 3 wake ups                          |
+--------------+-------------------------------------+
| C*-C-P       | 2 wake ups                          |
+--------------+-------------------------------------+
| C*           | 1 wake up                           |
+--------------+-------------------------------------+

P - producer
C - consumer
C* - consumer that succesfully finish take() method ( without wait() invoking)

让我们来数数:5 + 4 + 3 + 2 + 1 = 15.

对于n个生产者和n个消费者：n+(n-1)+(n-2)+(n-3)+...+1=1+2+3+4+...+n=前n个元素之和。等差数列 =n * (1 + n) 2 = (n + n^2) 2 → O(n^2)