notify / notifyAll misunderstanding

[VisionSet]

As I understand it, notify wakes up a waiting thread that then attempts to
gain lock the object it is waiting for. Where as notifyAll wakes up all
waiting threads and ONLY ONE gains the lock, the others go back to waiting.
The following code does not seem to show this.

I have a record locking system that I have condensed to the simple example
below. Record locks are placed on Integers that are managed by a Set. When
lock is called then the record is put in the set if not already there. If
the record is already there then wait() is called.
When unlock() is called a record is removed from the set and notifyAll() is
called.

In the example I have 2 threads that lock on record 5, and 8 that lock on
record 6.
So after the 10 lock threads run, I will have 1 thread locked 5, 1 thread
locked 6, 1 thread is waiting to lock 5, and 7 threads are waiting to lock
6.
Then a single thread unlocks record 5 and notifyAll is called.
So 8 waiting threads are then all notified and 1 arbitraily gets the lock.
If it is the 1 waiting to lock 5 then it will succeed since 5 has just been
locked. But more likely it will be one of the 7 waiting to lock 6, which
will be unsuccessful because 6 hasn't been unlocked.

SO! Why does it always succeed?

With notifyAll() I always get:

locked 5
locked 6
unlocked 5
locked 5

notify() on the other hand works as expected ie:

locked 5
locked 6
unlocked 5

but probably for the wrong reason since my understanding is obviously
flawed.


import java.io.*;
import java.util.*;

public class Test {

private Set lockSet = new HashSet();

public void lock(int recNo) {
Integer key = new Integer(recNo);
synchronized(lockSet) {
while(lockSet.contains(key)) {
try{
lockSet.wait();
}
catch(InterruptedException ex) {}
}
lockSet.add(key);
System.out.println("locked "+recNo);
}
}

public void unlock(int recNo) {

try {Thread.sleep(500);}
catch(InterruptedException ex) {}

Integer key = new Integer(recNo);
synchronized(lockSet) {
lockSet.remove(key);
System.out.println("unlocked "+recNo);
lockSet.notifyAll();
}
}


public static void main(String[] args) throws Exception {

Test test = new Test();
test.testLocking();

}

private void testLocking() {

lockIt(5);

lockIt(6);
lockIt(6);
lockIt(6);
lockIt(6);
lockIt(6);
lockIt(6);
lockIt(6);
lockIt(6);

lockIt(5);

unlockIt(5);

}

// these just fire up threads for lock & unlock
private void lockIt(final int x) {
new Thread(new Runnable() {
public void run() {
try {
lock(x);
}
catch(Exception e) {e.printStackTrace();}
}
}).start();
}
private void unlockIt(final int x) {
new Thread(new Runnable() {
public void run() {
try {
unlock(x);
}
catch(Exception e) {e.printStackTrace();}
}
}).start();
}
}

 

[Filip Larsen]

Mike wrote

I have a record locking system that I have condensed to the simple example

With notifyAll() I always get:

locked 5
locked 6
unlocked 5
locked 5

This looks like the correct behaviour because you have two threads
trying to lock 5, and they both get turns.

notify() on the other hand works as expected ie:

locked 5
locked 6
unlocked 5

This does not look correct because when you use notify only one
(arbitrary choosen) thread that wait on the lock gets notified and the
second "lock 5" thread will therefore (probably) never be notified to
discover that 5 indeed is available for locking again.

As a rule of thumb you should only use notify when the condition you
wait for is implied by the lock itself. If the wait is inside a while
loop you probably need to use notifyAll. In your case you could for
instance, with some modification to the code of course, wait for a
separate object for each integer, in which case you *can* use notify
because all threads that wait on the "5-object" is then in fact trying
to lock 5.


Regards,

 

[Chris Smith]

As I understand it, notify wakes up a waiting thread that then attempts to
gain lock the object it is waiting for. Where as notifyAll wakes up all
waiting threads and ONLY ONE gains the lock, the others go back to waiting.

Not exactly. The code for the waiting looks something like this:

synchronized (obj) // 1
{
...

// 2
obj.wait(); // 3
// 4

...
} // 5

Note that I've left out the predicate NOT because it's unimportant, but
because it's irrelevant to the point I'm making.

Now, when a thread begins this code it first grabs the monitor for obj,
meaning it can be the only thread running that has that monitor. Just
before it enters a wait state, and checkpoint 2, it atomically releases
that monitor and then enters the wait state. When it is woken, it
regains the monitor. (Actually, steps 2, 3, and 4 all take place inside
the wait call, but this is the easiest way to represent this in text.)
Finally, when it's done, it releases that monitor again.

Let's draw distinction between waiting and blocked. A thread that's
waiting is at checkpoint 3 in the code above. It is waiting for a
notify to happen, NOT for a monitor to be released. A thread that's
blocked is at checkpoint 1 or 4 above. It is blocked on a monitor, NOT
waiting for notify, so a call to notify won't affect it. In the case of
notifyAll() above, every single one of the threads that's waiting at #3
will move to #4, and THEN try to gain the monitor. At that point, none
of these threads are waiting; they are all blocked instead.

So here's the difference. In the notify() case, only one thread leaves
the waiting state, and it gains the monitor at #4 and then possibly
discovers that its predicate has not been fulfilled, so it goes back to
sleep. Then you're stuck. (It's not guaranteed to be that way; the
order in which threads are returned from a wait() state is not
specified, so it's actually possible that the one thread waiting on 5
will be the one that is woken up, and you will see something different.)

In the notifyAll() case, every single waiting thread is woken, and they
all line up at #4, and then (because of the monitor), they take turns
checking their predicates. The one that's looking for 5 WILL eventually
make it through, and it will continue on its merry way.

You've given an example here of a case where it's not safe to use plain
notify() on a monitor. Specifically, since different threads have
different predicates, you have no way of knowing whether the thread you
happen to wake up will be the one that cares about the notification, so
you have to use notifyAll. If all your threads were symmetrical, so
that they were all waiting for the same thing and only one would be able
to respond, then notify() would be valid.

The rule is this: use notifyAll(), and then replace it with notify()
only when the waiting threads are interchangeable.

--
www.designacourse.com
The Easiest Way to Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[John C. Bollinger]

As I understand it, notify wakes up a waiting thread that then attempts to
gain lock the object it is waiting for.

That is correct. The thread that is awakened will return from wait()
and resume execution when it re-obtains all the monitors it held before
invoking wait().

Where as notifyAll wakes up all
waiting threads and ONLY ONE gains the lock, the others go back to waiting.

That is incorrect. notifyAll() wakes up all waiting threads, all
initially blocked on monitor access. From each individual thread's
point of view, it is no different from being the lucky thread chosen by
notify(). One at a time, in no particular order, each will gain the
lock and resume executing. (In your code below, most such threads will
indeed ultimately resume waiting -- but because they loop back around to
invoke wait() again, not because of the semantics of notifyAll().)

The following code does not seem to show this.

Unsurprising, as your expected behavior is not the specified one.

I have a record locking system that I have condensed to the simple example
below. Record locks are placed on Integers that are managed by a Set. When
lock is called then the record is put in the set if not already there. If
the record is already there then wait() is called.
When unlock() is called a record is removed from the set and notifyAll() is
called.

In the example I have 2 threads that lock on record 5, and 8 that lock on
record 6.
So after the 10 lock threads run, I will have 1 thread locked 5, 1 thread
locked 6, 1 thread is waiting to lock 5, and 7 threads are waiting to lock
6.
Then a single thread unlocks record 5 and notifyAll is called.
So 8 waiting threads are then all notified and 1 arbitraily gets the lock.
If it is the 1 waiting to lock 5 then it will succeed since 5 has just been
locked. But more likely it will be one of the 7 waiting to lock 6, which
will be unsuccessful because 6 hasn't been unlocked.

SO! Why does it always succeed?

Because all the waiting threads are awakened and eventually run,
including the one waiting to lock record 5.

With notifyAll() I always get:

locked 5
locked 6
unlocked 5
locked 5

notify() on the other hand works as expected ie:

locked 5
locked 6
unlocked 5

but probably for the wrong reason since my understanding is obviously
flawed.

As an aside: isn't the behavior you actually get more what you want than
the behavior you expect? I.e. if a lock for a particular record is
released and one or more threads is waiting for that lock, then don't
you want one of the waiting threads to reliably get the lock?

import java.io.*;
import java.util.*;

public class Test {

private Set lockSet = new HashSet();

public void lock(int recNo) {
Integer key = new Integer(recNo);
synchronized(lockSet) {
while(lockSet.contains(key)) {
try{
lockSet.wait();

This method, in every thread, becomes eligible to return when
lockSet.notifyAll is invoked. It will in fact return when the thread
obtains lockSet's monitor, independent of what any other thread does.

}
catch(InterruptedException ex) {}
}

For each key that has been unlocked, the first thread that obtains
lockSet's monitor after the unlock will drop out of the while loop here,
add the key back into the lockSet, and then continue doing whatever else
it is supposed to do. Other threads that obtain lockSet's monitor later
will see the key in lockSet and loop around to wait() again. I admit to
a bit of bemusement, because this appears to be a perfectly workable
code that does what I would think you would want.

lockSet.add(key);
System.out.println("locked "+recNo);
}
}

public void unlock(int recNo) {

try {Thread.sleep(500);}
catch(InterruptedException ex) {}

Integer key = new Integer(recNo);
synchronized(lockSet) {
lockSet.remove(key);
System.out.println("unlocked "+recNo);
lockSet.notifyAll();
}
}


public static void main(String[] args) throws Exception {

Test test = new Test();
test.testLocking();

}

private void testLocking() {

lockIt(5);

lockIt(6);
lockIt(6);
lockIt(6);
lockIt(6);
lockIt(6);
lockIt(6);
lockIt(6);
lockIt(6);

lockIt(5);

unlockIt(5);

}

// these just fire up threads for lock & unlock
private void lockIt(final int x) {
new Thread(new Runnable() {
public void run() {
try {
lock(x);
}
catch(Exception e) {e.printStackTrace();}
}
}).start();
}
private void unlockIt(final int x) {
new Thread(new Runnable() {
public void run() {
try {
unlock(x);
}
catch(Exception e) {e.printStackTrace();}
}
}).start();
}
}

If you anticipated having many threads locking on many different records
then it might improve your performance to lock on the individual keys
instead of on the whole lockSet. It would be a bit more complicated,
but fundamentally it would work about the same. For relatively few
threads, relatively few records, or relatively few expected lock
contentions it's probably not worth it to introduce the extra bookkeeping.


John Bollinger
(e-mail address removed)

 

[Chris Smith]

And do you concur with My Larsens final point concerning the applicability
of notify() in my case?

Not in everything that was said, no. All uses of Object.wait should be
protected by a predicate loop, even when you're waiting for the same
condition from all threads. But yes, you should restrict notify() to
cases where all threads are waiting on the same thing and a thread that
wakes will immediately change the state of the predicate again. That
is, if it's ever okay for thread 1 to proceed but not thread 2, then
notifyAll is needed so each thread can individually check whether it
ought to proceed; and if all threads should simultaneously wake up at
the same time (if, for example, you're implementing a read/write lock
and the writer just released) then of course you need notifyAll as well.

--
www.designacourse.com
The Easiest Way to Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[VisionSet]

Mike wrote


This looks like the correct behaviour because you have two threads
trying to lock 5, and they both get turns.

No, I don't see it that way.
The 1st 5 thread will lock because 5 is not locked.
But when that is unlocked notifyAll will wake all threads but ONLY ONE will
aquire the lock on the Set object, this is arbitrary and sinece there are 7
lots of threads waiting to lock 6 versus 1 thread trying to lock 5 then it
is likely the 6 thread will win. Since notifyAll is only called once in this
example I don't see that the waiting threads get another chance to aquire
the lock.

This does not look correct because when you use notify only one
(arbitrary choosen) thread that wait on the lock gets notified and the
second "lock 5" thread will therefore (probably) never be notified to
discover that 5 indeed is available for locking again.

Yes I understand this, but for the same reason this should be the case for
notifyAll(), since although all waiting threads are woken (I know they
weren't sleeping) ONLY ONE will run and which one is arbitrary.

As a rule of thumb you should only use notify when the condition you
wait for is implied by the lock itself. If the wait is inside a while
loop you probably need to use notifyAll. In your case you could for
instance, with some modification to the code of course, wait for a
separate object for each integer, in which case you *can* use notify
because all threads that wait on the "5-object" is then in fact trying
to lock 5.

Thanks that is useful, I'll give it some thought.
But my main reason for the post is to understand the notifyAll quandry,
which I still don't :-(

 

[VisionSet]

As an aside: isn't the behavior you actually get more what you want than
the behavior you expect? I.e. if a lock for a particular record is
released and one or more threads is waiting for that lock, then don't
you want one of the waiting threads to reliably get the lock?

Yes, I was just using it to understand the notifyAll(), which I now do
thankyou.

 

[VisionSet]

In the case of
notifyAll() above, every single one of the threads that's waiting at #3
will move to #4, and THEN try to gain the monitor. At that point, none
of these threads are waiting; they are all blocked instead. ....
In the notifyAll() case, every single waiting thread is woken, and they
all line up at #4, and then (because of the monitor), they take turns
checking their predicates. The one that's looking for 5 WILL eventually
make it through, and it will continue on its merry way.

Thankyou, I understand now.

Basically it boils down to, notifyAll() cause all threads to stop waiting,
they all queue up to aquire the lock and hence they all check the while
condition.

Whereas initially I thought notifyAll() was far to similar to notify() to
actually be of any addtional use! should of realised.

And do you concur with My Larsens final point concerning the applicability
of notify() in my case?

Thanks again, I just hope this doesn't start off Mr Java
<b>'</b>Architect<b>'</b> ;-)

 

[Chris Smith]

Could you expand on this please, perhaps with some code?

Ah, okay! Though I'm not Filip, here's a reimplementation of your lock
and unlock methods in that way:

public static final int MAX_LOCKS = 10;
private boolean[] lockHeld = new boolean[MAX_LOCKS];
private Object[] syncObjs = new Object[MAX_LOCKS];
{
for (int i = 0; o < MAX_LOCKS; i++) syncObjs = new Object();
}

public void lock(int recNo)
{
if ((recNo < 0) || (recNo >= MAX_LOCKS))
{
throw new IllegalArgumentException();
}

synchronized (syncObjs[recNo])
{
while (lockHeld[recNo])
{
try
{
syncObjs[recNo].wait();
}
catch (InterruptedException ex) { }
}

lockHeld[recNo] = true;
System.out.println("locked " + recNo);
}
}

public void unlock(int recNo)
{
if ((recNo < 0) || (recNo >= MAX_LOCKS))
{
throw new IllegalArgumentException();
}

try
{
Thread.sleep(500);
}
catch (InterruptedException ex) { }

synchronized (syncObjs[recNo])
{
lockHeld[recNo] = false;
System.out.println("unlocked " + recNo);
syncObjs[recNo].notify();
}
}

--
www.designacourse.com
The Easiest Way to Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[VisionSet]

In your case you could for
instance, with some modification to the code of course, wait for a
separate object for each integer, in which case you *can* use notify
because all threads that wait on the "5-object" is then in fact trying
to lock 5.

Could you expand on this please, perhaps with some code?

 

[VisionSet]

Not in everything that was said, no. All uses of Object.wait should be
protected by a predicate loop, even when you're waiting for the same
condition from all threads. But yes, you should restrict notify() to
cases where all threads are waiting on the same thing and a thread that
wakes will immediately change the state of the predicate again. That
is, if it's ever okay for thread 1 to proceed but not thread 2, then
notifyAll is needed so each thread can individually check whether it
ought to proceed; and if all threads should simultaneously wake up at
the same time (if, for example, you're implementing a read/write lock
and the writer just released) then of course you need notifyAll as well.

I was refering to the point made about a single reference to a record that
could be synchronized on. See my reply to him.
I understand the point about always using a conditional loop rather than an
'if'

 

[Chris Smith]

The question then becomes does the overhead of having a separate lock object
for each record plus the additional managing of this in conjuntion with
records being deleted and added, outweighs the gain of notify over notifyAll
ie reducing the number of wasted CPU cycles from needlessly awaken threads?

That will depend on the number of threads, and the number of different
logical locks that you need. If the number of threads is far higher
than the number of locks, you'll likely find multiple lock objects to be
more efficient, and opposite if the number of locks is far higher than
the number of threads

I know... test it.

Basically, yes.

--
www.designacourse.com
The Easiest Way to Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[VisionSet]

Could you expand on this please, perhaps with some code?

Ah, okay! Though I'm not Filip, here's a reimplementation of your lock
and unlock methods in that way:

public static final int MAX_LOCKS = 10;
private boolean[] lockHeld = new boolean[MAX_LOCKS];
private Object[] syncObjs = new Object[MAX_LOCKS];
{
for (int i = 0; o < MAX_LOCKS; i++) syncObjs = new Object();
}

public void lock(int recNo)
{
if ((recNo < 0) || (recNo >= MAX_LOCKS))
{
throw new IllegalArgumentException();
}

synchronized (syncObjs[recNo])
{
while (lockHeld[recNo])
{
try
{
syncObjs[recNo].wait();
}
catch (InterruptedException ex) { }
}

lockHeld[recNo] = true;
System.out.println("locked " + recNo);
}
}

public void unlock(int recNo)
{
if ((recNo < 0) || (recNo >= MAX_LOCKS))
{
throw new IllegalArgumentException();
}

try
{
Thread.sleep(500);
}
catch (InterruptedException ex) { }

synchronized (syncObjs[recNo])
{
lockHeld[recNo] = false;
System.out.println("unlocked " + recNo);
syncObjs[recNo].notify();
}
}

Thanks Chris.

The question then becomes does the overhead of having a separate lock object
for each record plus the additional managing of this in conjuntion with
records being deleted and added, outweighs the gain of notify over notifyAll
ie reducing the number of wasted CPU cycles from needlessly awaken threads?

I know... test it.

 

[Filip Larsen]

Mike wrote

Could you expand on this please, perhaps with some code?

The idea is to wait on some object that represent the condition you want
to wait for.

Starting with your example code, I have refactored and changed it to
include a Lock class that represent a resource or critical section that
can only be access by one thread at a time, and then used that to manage
a set of keyed resources. Note that synchronization is done on method
level for Lock.enter, Lock.leave, leave and getLock. The last two
synchronized are to avoid race-conditions in the dynamic management of
locks which is not really essential for showing how notify can be used.

I have tested and reviewed the code a bit for race-conditions, but there
is of course no guarantees. Like Sun says, don't use this in a rocket or
anything else that needs to be fail-safe


==== NotifyTest.java ====
import java.util.Map;
import java.util.HashMap;

public class NotifyTest {

public class Lock {

public synchronized void enter() throws InterruptedException {
count++;
while (count > 0) wait();
}

public synchronized boolean leave() {
notify();
return --count == 0;
}

private int count;
}

private Map locks = new HashMap();

public void enter(int key) throws InterruptedException {
enter(new Integer(key));
}

public void enter(Object key) throws InterruptedException {
getLock(key).enter();
System.out.println("locked " + key);
}

public void leave(int key) {
leave(new Integer(key));
}

public synchronized void leave(Object key) {
System.out.println("unlocked " + key);
final Lock lock = getLock(key);
if (lock.leave()) locks.remove(key);
}

private synchronized Lock getLock(Object key) {
Lock lock = (Lock) locks.get(key);
if (lock == null) {
lock = new Lock();
locks.put(key,lock);
}
return lock;
}

public static void main(String[] args) throws Exception {
NotifyTest test = new NotifyTest();
test.testLocking();
}

private void testLocking() {
lockIt(5);

lockIt(6);
lockIt(6);
lockIt(6);
lockIt(6);
lockIt(6);
lockIt(6);
lockIt(6);
lockIt(6);

lockIt(5);

unlockIt(5);
}

// these just fire up threads for lock & unlock
private void lockIt(final int x) {
new Thread() {
public void run() {
try {
enter(x);
} catch (Exception e) {
e.printStackTrace();
}
}
}.start();
}

private void unlockIt(final int x) {
new Thread() {
public void run() {
doSleep(500);
leave(x);
}
}.start();
}

private void doSleep(long millis) {
try {
Thread.sleep(millis);
} catch (InterruptedException e) {
}
}

}
========

If the management of locks is static, the Lock class can be written
slightly more intuitive:

public class Lock {


public synchronized void enter() throws InterruptedException {
while (locked) wait();
locked = true;
}

public synchronized void leave() {
locked = false;
notify();
}

private boolean locked;

}

By the way, please ignore my earlier comment where I said something like
"if your wait is inside a loop you probably need notifyAll". You almost
always need a loop to guard against race-conditions no matter which of
notify and notifyAll that is used.