Complexity of the notifyAll operation
concurrency, java, multithreading
Solution
Something gets put into the queue n times. "n wakeups would suffice" means that ideally we'd like one consumer to be notified when a producer drops something into the buffer, for instance, so there would be n notifications, and even better they would all be uncontended. But instead all of the threads waiting on the lock, including all the producers (minus 1, the one doing the putting) and all the consumers (the ones who are waiting anyway), get notified every time something gets dropped in the queue, they all fight for the lock and the scheduler picks a winner. (And we're not even considering the case where the chosen thread has to wait, that's just a detail.) So there are n times that notifyAll gets called, once for each put, and each notifyAll wakes up multiple producers and multiple consumers, which is where they get O(n2) wakeups.
Problem
I don't understand the following fragment of the Java Concurrency in Practice book: Using notifyAll when only one thread can make progress is inefficient - sometimes a little, sometimes grossly so. If ten threads are waiting on a condition queue, calling notifyAll causes each of them to wake up and contend for the lock; then most or all of them will go right back to sleep. This means a lot of context switches and a lot of contended lock acquisitions for each event that enables (maybe) a single thread to make progress. (In the worst case, using notifyAll results in O(n2) wakeups where n would suffice.) An example code is in listing 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; } } ``` We can have, for example, the following sequence of events: - two consumer threads try to get an object from the buffer, the buffer is empty, so they are suspended. - 10 producers put 10 objects to the buffer, the buffer capacity is 10. - 100001 producers try to put 100001 objects to the buffer, the buffer is full, so they are suspended. - first consumer gets an object from the buffer and invokes notifyAll. - a producer puts an object to the buffer and invokes notifyAll, the buffer is full. Now only one thread can make progress - the consumer thread. We also have 100000 producers, who can't make progress. I don't understand why in the worst case there will be O(n2) wakeups, before the thread which can make progress is woken up. I think the worst case is the following sequence - All threads are woken up (because of notifyAll). We "used" O(n) wakeups. - A producer thread gets the lock, other threads are suspended. The producer thread can't make progress, so it is suspended and it releases the lock. - Now only one producer thread is woken up, because a different mechanism is used (a thread resumes execution, because it gets the lock - but this time the notifyAll is not called). We "use" only O(1) wakeups. - The second producer can't make progress, so it is suspended and it releases the lock. - Similar events happen for all other waiting producers. - Finally the thread which can make progress (the consumer thread) is woken up. I think we "used" O(n) + O(n)*O(1) = O(n) wakeups. Is there an error in the book, or am I missing something here?