Сложность операции notifyAll

Question

Я не понимаю, следующий фрагмент Java Параллелизм на практике книге:

Использование notifyAll когда только один поток может добиться прогресса неэффективна - иногда немного, иногда грубо так. Если в очереди состояния ждут десять потоков, вызов notifyAll заставляет каждого из них проснуться и бороться за блокировку; то большинство или все они снова вернутся спать. Это означает множество контекстных переключателей и множество конкурирующих блокировок для каждого события, которое позволяет (возможно) создать один поток для достижения прогресса. (В худшем случае, используя notifyAll результаты в O (п) пробуждений, где п будет достаточно.)

Пример кода в листинге 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 wakeups would enough» означает, что в идеале мы хотели бы, чтобы один потребитель был уведомлен, когда производитель что-то бросает что-то в буфер, так что было бы n уведомлений, и даже лучше все они были бы беспомощными. Но вместо этого все потоки, ожидающие блокировки, включая всех производителей (минус 1, тот, кто делает ставку), и все потребители (те, кто все равно ждет), получают уведомление каждый раз, когда что-то падает в очереди, они все сражаются за блокировку, а планировщик выбирает победителя. (И мы даже не рассматриваем случай, когда выбранный поток должен ждать, это просто деталь.) Таким образом, существует n раз, что notifyAll вызывается, один раз для каждого put, и каждый notifyAll пробуждает несколько производителей и нескольких потребителей, где они получают O (n) пробуждения.