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，缓冲区已满。

现在只有一个线程可以取得进展——消费者线程。我们还有10万生产者，他们无法进步。

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

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

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，执行放入操作的线程）和所有消费者（无论如何都在等待的线程），每次在队列中丢弃某些内容时都会收到通知，它们所有人都争夺锁，调度程序选出获胜者。（我们甚至没有考虑所选线程必须等待的情况，这只是一个细节。）因此，notifyAll 被调用 n 次，每个 put 调用一次，每个 notificationAll 唤醒多个生产者和多个消费者，这是他们获得 O(n ² ) 唤醒的地方。