我不理解 Java 并发实践书中的以下片段:
当只有一个线程可以取得进展时使用 notifyAll 是低效的 - 有时是一点点,有时是非常低效。如果有 10 个线程在一个条件队列上等待,调用 notifyAll 会导致它们中的每一个都被唤醒并争夺锁;然后他们中的大多数人或所有人将立即重新休眠。这意味着每个事件都会进行大量的上下文切换和大量争用的锁获取,这使得(可能)单个线程能够取得进展。 (在最坏的情况下,使用 notifyAll 会导致 O(n2) 次唤醒,其中 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;
}
}
例如,我们可以有以下事件序列:
- 两个消费者线程试图从缓冲区中获取对象,缓冲区为空,因此它们被挂起。
- 10个生产者将10个对象放入缓冲区,缓冲区容量为10。
- 100001 个生产者尝试将 100001 个对象放入缓冲区,缓冲区已满,因此被挂起。
- 第一个消费者从缓冲区中获取一个对象并调用 notifyAll。
- 生产者将对象放入缓冲区并调用 notifyAll,缓冲区已满。
现在只有一个线程可以取得进展——消费者线程。我们还有 100000 个生产者,他们无法进步。
我不明白为什么在最坏的情况下会有 O(n2) 次唤醒,在唤醒可以取得进展的线程之前。
我认为最坏的情况是下面的序列
- 所有线程都被唤醒(因为notifyAll)。我们“使用”了 O(n) 次唤醒。
- 一个生产者线程获得锁,其他线程被挂起。生产者线程无法取得进展,因此被挂起并释放锁。
- 现在只有一个生产者线程被唤醒,因为使用了不同的机制(一个线程恢复执行,因为它获得了锁——但是这次notifyAll是不是 称为)。我们仅“使用”O(1) 次唤醒。
- 第二个生产者无法取得进展,因此被挂起并释放锁。
- 所有其他等待的生产者都会发生类似的事件。
- 最终唤醒能取得进展的线程(消费者线程)。
我认为我们“使用”了 O(n) + O(n)*O(1) = O(n) 次唤醒。
这本书有错误,还是我遗漏了什么?
最佳答案
某物被放入队列 n 次。 “n 次唤醒就足够了”意味着理想情况下,我们希望当生产者将某些东西放入缓冲区时通知一个消费者,例如,这样就会有 n 次通知,更好的是它们都不会发生竞争。但是,所有等待锁的线程,包括所有生产者(减去 1,执行放置的线程)和所有消费者(无论如何都在等待的线程),每次队列中有东西掉落时都会收到通知,他们所有人都为锁而战,调度程序选择一个赢家。 (而且我们甚至没有考虑选择的线程必须等待的情况,这只是一个细节。)所以有 n 次 notifyAll 被调用,每个 put 一次,每个 notifyAll 唤醒多个生产者和多个消费者,这是他们获得 O(n2) 次唤醒的地方。
关于java - notifyAll 操作的复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15852935/