4

我不明白 Java Concurrency in Practice 书中的以下片段：

当只有一个线程可以取得进展时使用 notifyAll 是低效的 - 有时有点，有时很严重。如果有 10 个线程在条件队列上等待，调用 notifyAll 会导致每个线程都醒来并争夺锁；然后他们中的大多数或全部会马上回去睡觉。这意味着每个事件都会进行大量上下文切换和大量争用锁获取，从而使（可能）单个线程能够取得进展。（在最坏的情况下，使用 notifyAll 会导致 O(n 2 ) 唤醒，其中 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 2 ) 唤醒，在可以取得进展的线程被唤醒之前。

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

  1. 所有线程都被唤醒（因为 notifyAll）。我们“使用”了 O(n) 唤醒。
  2. 一个生产者线程获得锁，其他线程被挂起。生产者线程无法取得进展，因此它被挂起并释放锁。
  3. 现在只有一个生产者线程被唤醒，因为使用了不同的机制（线程恢复执行，因为它获得了锁——但这次没有调用 notifyAll）。我们仅“使用” O(1) 唤醒。
  4. 第二个生产者无法取得进展，所以它被挂起并释放锁。
  5. 所有其他等待的生产者都会发生类似的事件。
  6. 最后，可以进行的线程（消费者线程）被唤醒。

我认为我们“使用”了 O(n) + O(n)*O(1) = O(n) 唤醒。

书中有错误，还是我在这里遗漏了什么？

4

2 回答 2

3

有东西被放入队列 n 次。“n 次唤醒就足够了”意味着理想情况下，我们希望在生产者将某些东西放入缓冲区时通知一个消费者，例如，因此会有 n 个通知，甚至更好的是它们都没有竞争。但相反，所有等待锁的线程，包括所有生产者（减 1，执行 put 的线程）和所有消费者（无论如何都在等待的线程），每次在队列中删除时都会收到通知，他们所有人都为锁定而战，调度程序选择了一个胜利者。（而且我们甚至没有考虑所选线程必须等待的情况，这只是一个细节。）所以有 n 次 notifyAll 被调用，每次 put 一次，每个 notifyAll 唤醒多个生产者和多个消费者，这就是他们得到 O(n2）唤醒。

于 2013-04-06T16:35:53.293 回答
0

让我们有 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)

于 2020-05-09T16:47:59.347 回答