Win a copy of Murach's Python Programming this week in the Jython/Python forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

What exactly makes notifyAll() expensive?  RSS feed

 
Victor Ho
Ranch Hand
Posts: 74
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

notifyAll() definitely has the obvious overhead to go through all threads in the object's wait list vs. just picking one in notify(). It is a O(n) vs. O(1) issue.

But I am thinking if people are actually referring to another potentially worse overhead when we say notifyAll() is bad.

Typical case:

1: public synchronized int get() {
2: while (available == false) {
3: try {
4: //wait for Producer to put value
5: wait();
6: } catch (InterruptedException e) { }
7: }
8: available = false;
9: return contents;
10: }

public synchronized void put(int value) {
contents = value;
available = true;
//notify Consumer that value has been set
notifyAll();
}

When there are multiple threads waiting on the 'this' object, notifyAll() wakes up all of them, but only one winning thread can grab the lock on the 'this' object and execute line 6-10.

For the rest:
1) Got woken up
2) Go back to wait state for grabbing the lock to enter line 6
3) When winning thread is done with line 10, grab lock, loop back to line3.
4) Release lock and back to where it was before the notifyAll() was invoked.

This sounds bad to me, each losing thread will do this grab lock, release lock just to get back to where it was. And if line 6-10 takes a long time, it is very likely that there will be a good number of context switches incurred (due to losing thread gets woken up, but need to go back to wait state again realizing line 6 still cannot be entered).

What do you guys think? It feels to me that the latter drawback is the real problem.

Thanks
[ October 21, 2005: Message edited by: Victor Ho ]
 
Edward Harned
Ranch Hand
Posts: 291
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your example is too simple.

Think of an RMI Server. Every request to the server starts or reuses a thread. There is no way to exactly notify the thread that is processing your request. The only way to notify your thread is with notifyAll().

When there are multiple threads attached to the same object you never know what thread is doing what at any one time.

If you create a single thread yourself then you can pass the object to the other thread and it can use notify().
 
Victor Ho
Ranch Hand
Posts: 74
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Edward. But you didn't get my point of the question.

Of course one has to consider cases where notify() simply won't work in terms of functionality. I am raising this question just so that we can understand more on why notifyAll() shouldn't be abused when it is not necessary.
 
Edward Harned
Ranch Hand
Posts: 291
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You wrote the following:

This sounds bad to me, each losing thread will do this grab lock, release lock just to get back to where it was. And if line 6-10 takes a long time, it is very likely that there will be a good number of context switches incurred (due to losing thread gets woken up, but need to go back to wait state again realizing line 6 still cannot be entered).

What do you guys think? It feels to me that the latter drawback is the real problem.
--------------------------------------------------

If you must use notifyAll() then you're stuck with every thread waking up. It's not a drawback, it's the way it is.

My suggestion is to use notify() whenever possible.
 
Mr. C Lamont Gilbert
Ranch Hand
Posts: 1170
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Its just wasteful and makes no sense. Why notify 10 threads if 9 of them are guaranteed to go back to wait without doing anything?

You seem to be asking why not. But I think the question is why should you.
 
Henry Wong
author
Sheriff
Posts: 22851
119
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Victor Ho:
Thanks Edward. But you didn't get my point of the question.

Of course one has to consider cases where notify() simply won't work in terms of functionality. I am raising this question just so that we can understand more on why notifyAll() shouldn't be abused when it is not necessary.


This is actually one of my pet peeves -- the use of the notifyAll() method because they can't get the notify() method to work correctly. Currently, there are two main cases where this is okay (and one no really) ...

First, there are multiple possible conditions on the same lock. This situation has actually been fixed with Java 5.0 with the Lock and Condition class. It is possible to have multiple conditions variables working with the same lock. Prior to 5.0, you will need to implement the class -- which surprisingly is not that hard.

Second, the algorithm is designed that way. For example, freeing a resource that could be used by muliple threads at the same time. If I return 3 books to the library, those 3 books can be checked out by 1, 2, or 3 people. In this case, there is no other option.

Henry
 
Mr. C Lamont Gilbert
Ranch Hand
Posts: 1170
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I used notifyAll when I created an implementation of message passing interface. When you broadcast something, notifyAll works perfectly.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!