java - notifyAll 操作的复杂性

Question

我不理解 Java 并发实践书中的以下片段:

当只有一个线程可以取得进展时使用 notifyAll 是低效的 - 有时是一点点，有时是非常低效。如果有 10 个线程在一个条件队列上等待，调用 notifyAll 会导致它们中的每一个都被唤醒并争夺锁；然后他们中的大多数人或所有人将立即重新休眠。这意味着每个事件都会进行大量的上下文切换和大量争用的锁获取，这使得(可能)单个线程能够取得进展。 (在最坏的情况下，使用 notifyAll 会导致 O(n²) 次唤醒，其中 n 就足够了。)

示例代码在 list 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 被调用，每个 put 一次，每个 notifyAll 唤醒多个生产者和多个消费者，这是他们获得 O(n²) 次唤醒的地方。