Thread states, notify, notifyAll, wait

[Derek Canaan]

Hi,
Would like your answers on the questions below:

  
1.  public void methodA {
2.      synchronized(aMonitor) {
3.          // codes
4.      }
5.  }
1.  public void methodX {
2.      synchronized(aMonitor) {
3.          // codes
4.          while (conditionX) {
5.              aMonitor.wait();
6.          }
7.          // codes that make conditionX true
8.      }
9.  }
1.  public void methodY {
2.      synchronized(aMonitor) {
3.          // codes that make conditionX false
4.          aMonitor.notify();
5.      }
6.  }

Suppose:
1. Thread T1 runs methodA and acquires aMonitor.
2. Concurrently, thread T2 wants to run methodX.
Q1: Since aMonitor is acquired by T1, does thread T2 go into Seeking lock state or Waiting state or Blocked state? Are these states synonymous?
Q2: When T1 exits the synch block after line 4 of methodA, aMonitor is released. At this point, which pool of threads does the JVM informs that the aMonitor is available? The threads in Seeking lock state? Waiting state? or Blocked state?
Q3: Suppose now, T2 acquired aMonitor, reached line 4 of methodX and found conditionX to be true. T2 releases aMonitorX but which state does it go to?
Q4: Now another thread T3 runs methodA, acquired aMonitor, and exits the synch block of methodA. At this point, does T2 get informed by the JVM?
Q5: Suppose, another thread T4 now enters methodY, and successfully acquired aMonitor, but at this same time, another thread T5 wants to run methodA. Which state does T5 go?
Q6: Now T4 executes line 4 of methodY: aMonitor.notify(). Who gets notified here? T2 definitely, but how about T5?
Q7: If several threads called wait(), which of the following is true when aMonitor.notify() is invoked:
a) the first thread that executed the wait() call is enabled for running.
b) one thread from the Waiting state pool is selected randomly and is enabled running.
Q8: If notify() and notifyAll() effectively wake up only ONE thread from a pool of thread and enable it to run, is there a practical difference on which one to use?
thanks in advance,
derek

[Raj Shekhar]

Derek,
I would like to know the answers of most of your questions as it might help me undertsnad the problem I am seeing with synchronization. The answer to question 8, however is below(I am quoting from max's book).
Notify() wakes up only one of the waiting threads, which then acquires the lock on the aMonitor. However, notifyAll() wakes up all the waiting threads. Even in this case only one these threads will get the lock to aMonitor. The CPU will decide which of these threads will get the lock and all the other threads go back to waiting state.
Since notify() wakes up only one of the waiting threads, there is a possiblility of starvation here as some thread may remain waiting forever.
HTH
Raj

[Derek Canaan]

Hi Raj,
Hopefully, some java "gurus" can help us out here.
On Q8, it depends on Q7 (one author wrote a and another b) - so i'm confused.
If answer to Q7 is (a), then we implicitly have a FIFO thread queue - in this case, is there still thread starvation?
If answer to Q7 is (b), and for notifyAll, the "The CPU will decide which of these threads will get the lock" - for the developer, this is as good as random since we cannot know/determine how the CPU will decide. So notify and notifyAll gave the same net consequence.
I know I'm definitely missing something.
Any advice is appreciated.
Derek

[Andrew Monkhouse]

Hi Derek,
All I can say is
Marlene - I thought this would be something you would love.
Just took a look at the Java Language Specification (JLS) and it doesn't seem to specify the names of the states a thread can be in. So I looked at a couple of the books on my shelf, and while they all agree on what state your threads should be in, they use different names for them . So I will put it in my own words, and see how we go.

Since aMonitor is acquired by T1, does thread T2 go into Seeking lock state or Waiting state or Blocked state? Are these states synonymous?
This is one of the Blocked states. One book simply calls this "Blocked" while another specifies that it is "Blocked for lock aquisition" (different from "Blocked for I/O"). So I guess that this corresponds to your first and last options.
It is not in waiting state - it has not called wait() and it will not be woken by a call to notify() or notifyAll().

When T1 exits the synch block after line 4 of methodA, aMonitor is released. At this point, which pool of threads does the JVM informs that the aMonitor is available? The threads in Seeking lock state? Waiting state? or Blocked state?
When T1 exits the synch block, all the threads which are blocked for aMonitor are returned to the Runnable state. Sooner or later the scheduler will check which threads are in Runnable state and run one or more of them, in which case one of them may aquire the mutex on aMonitor. The others will transition back into blocked state.

Suppose now, T2 acquired aMonitor, reached line 4 of methodX and found conditionX to be true. T2 releases aMonitorX but which state does it go to?
T2 now goes into "Waiting" or "Waiting for notification" state.

Now another thread T3 runs methodA, acquired aMonitor, and exits the synch block of methodA. At this point, does T2 get informed by the JVM?
No, you do not have a notify() or notifyAll() in methodA. So T2 is still in "Waiting" state.

Suppose, another thread T4 now enters methodY, and successfully acquired aMonitor, but at this same time, another thread T5 wants to run methodA. Which state does T5 go?
T5 should now go to "Blocked" state.

Now T4 executes line 4 of methodY: aMonitor.notify(). Who gets notified here? T2 definitely, but how about T5?
T2 comes out of "Waiting" state at line 4, and enters "Blocked" state.
T2 and T5 come out of "Blocked" state and enter "Runnable" (or "Ready to Run") state when T4 gets to line 6 of methodY.

If several threads called wait(), which of the following is true when aMonitor.notify() is invoked:

a) the first thread that executed the wait() call is enabled for running.
b) one thread from the Waiting state pool is selected randomly and is enabled running.
Option b is closest to correct - from our perspective one thread will be selected randomly to transition from "Waiting" to "Blocked" state. We have no way of knowing which one.
In reality it is a bit unfair to say that it is random - there are well defined rules in the JVM as to which one will get selected. But it is invisible to us .

If notify() and notifyAll() effectively wake up only ONE thread from a pool of thread and enable it to run, is there a practical difference on which one to use?
notify() will transition one thread from "waiting" state to "blocked" state.
notifyAll() will transition all threads from "waiting" state to "blocked" state.
If you only have a single condition to check then you are quite safe with just using notify(). But if multiple threads can go into wait() state on a single mutex waiting for different conditions, then you really need to notify all of them so that they can all check whether their personal condition has changed.
So if you had a mutex on recordOne then you know that there is only one condition for this mutex (recordOne is either locked or unlocked) and you could safely call notify() on a single thread waiting for recordOne.
But if you had a mutex on a collection of records, then calling notify() on that collection will only transition one thread to blocked state (and then to runnable state), and when it transitions to runnable it may find that the condition it was waiting for (the individual record lock within the collection) is still not available - which will result in all the waiting threads returning to waiting state, even though there is potentially a lock free.

Clear as mud?
Regards, Andrew

[Derek Canaan]

Hi Andrew,
Just want to say that you have always been such a great help
Q1-7 is now as clear as the bright blue sky.
Q8 is still grey for me, but i can see a little light at the end of the tunnel. Let me see if i understood your following statements correctly:

But if multiple threads can go into wait() state on a single mutex waiting for different conditions, then you really need to notify all of them so that they can all check whether their personal condition has changed.
So if you had a mutex on recordOne then you know that there is only one condition for this mutex (recordOne is either locked or unlocked) and you could safely call notify() on a single thread waiting for recordOne.
But if you had a mutex on a collection of records, then calling notify() on that collection will only transition one thread to blocked state (and then to runnable state), and when it transitions to runnable it may find that the condition it was waiting for (the individual record lock within the collection) is still not available - which will result in all the waiting threads returning to waiting state, even though there is potentially a lock free.

First, let me put a little meat into the codes:

     
1.    Collection lockedRecords;
2.    lock(recNo) {
3.       synchronized(lockedRecords){
4.            while(lockedRecords.contains(recNo))
5.                lockedRecords.wait();
6.            }
7.            lockedRecords.put(recNo);
8.    }
9.    unlock(recNo) {
10       synchronized(lockedRecords){
11            lockedRecords.remove(recNo);
12            lockedRecords.notifyAll();
13    }

Suppose
1. Thread T12 runs lock(recNo) and successfully put recNo 12 into lockedRecords and exits lock method but has not started on unlock(recNo 12).
2. Since T12 exited, lockedRecords monitor is available. Suppose T35 runs lock(recNo), acquires lockedRecords monitor and successfully put recNo 35 into lockedRecords and exits lock method but has not started on unlock(recNo 35).
3. Now T1 and T2 would like to lock(recNo 12) and T3 and T5 would like to lock (recNo 35).
4. Threads T1, T2, T3, T5 successively got lockedRecords monitor but go to Waiting state because recNo 12 and 35 are still contained in lockedRecords.
5. T12 manages to get lockedRecords monitor and run unlock(recNo12) and does a lockedRecords.notifyAll()

Q1. In this case, all of threads T1, 2, 3, 5 will go to Blocked state and JVM will select one to Running state. Suppose T3 got selected, T3 wastes some CPU, and go back to Waiting state, BUT at the same time releases lockedRecords monitor. So JVM selects one from the Blocked state (T1, 2, and 5) but NOT T3 as it is in Waiting state. Is this understanding correct?
Q2. Now let's suppose lockedRecords.notify() is used instead of notifyAll. So JVM chooses one thread from (T1,2,3,5) from Waiting state to Blocked state. Let's consider the worst scenario: JVM chooses T3. T3 runs line 4, go back to Waiting state, BUT also releases the lockedRecords monitor. No other threads are in the Blocked state -> Thread starvation.
Nobody calls notify, so these threads cannot come out of the Waiting state. T35 will eventually invoke lockedRecords.notify() but in effect one out of T1,2,3,5 will get to call unlock(). The other 3 threads starve. Is this correct?
The light is getting brighter.
thanks,
Derek

[Derek Canaan]

Hey, wait a minute ... there may be no starvation even for notify()
Let's continue the analysis:

...JVM chooses T3. T3 runs line 4, go back to Waiting state, BUT also releases the lockedRecords monitor. No other threads are in the Blocked state.

But thread T35 to the rescue. T35 eventually runs unlock(recNo 35) and does a lockedRecords.notify().
1. Because T35 calls lockedRecords.notify(), JVM chooses one of (T1,2,3,5) from the Waiting state to Blocked state. (Remember now that recNo 12, and 35 are no longer in lockedRecords.)
2. Say JVM chooses T1 (it does not matter).
3. T1 goes to Running state because T35 releases the lockedRecords monitor when it exits unlock(recNo), and there is only one thread namely T1 in the Blocked state.
4. At this stage, T2,3,5 are in Waiting state.
5. T1 runs lock(), put recNo 12 into lockedRecords and finally, unlock() removing recNo 12 from lockedRecords and calls lockedRecords.notify(). (Now, again, recNo 12, and 35 are not in lockedRecords)
6. Because T1 calls lockedRecords.notify(), JVM chooses one of (T2,3,5) from the Waiting state to Block state.
7. Say JVM chooses T2 (it does not matter).
8. T2 goes to Running state because T1 releases the lockedRecords monitor when it exits unlock(recNo), and there is only one thread namely T2 in the Blocked state.
9. At this stage, T3,5 are in Waiting state.
10. T2 runs lock(), put recNo 12 into lockedRecords and finally, unlock() removing recNo 12 from lockedRecords and call lockedRecords.notify(). (Now, again, recNo 12, and 35 are not in lockedRecords)
11. Because T2 calls lockedRecords.notify(), JVM chooses one of (T3,5) from the Waiting state to Block state and so on ..., and hence the remaining threads 3 and 5 will also go to Running state.
Hence no thread starvation!
Is this correct? The light seems further again.
rgds,
derek

[Max Habibi]

Hey Derek,
According to my reading of the spec, calling notify bypasses any and all priority that the various threads might have.
That is, since the thread that wakes up is completely arbitrary, then you lowest priority Thread could wake up, find that it has no threads to compete with, then go on to execute.
Assume that you have three Threads: one that handles printing for me, another that handles printling for you, and a Third that handles printing for Andrew. If you never use notifyAll, then the threading mechanism, which might normally 'bump' the priority of the threads that have been waiting the longest(or originally had the higher priority), will never get a chance to have it's input considered.
Accordingly, you might find that the Thread that handles printing for me keeps waking up(and winning) again, and again, effectively starving the threads that you and Andrew are using.

Make sense?
M

[Derek Canaan]

Hi Max,
First, thanks for your contributions in this forum. They helped me a lot. Please help me out here as i am trying to get a grip on this issue.
In the printing scenario, let's consider time-sliced vs pre-emptive OS.
Case A (time-sliced OS)
-----------------------
For time-sliced OS, notify() would not cause thread starvation because Thread(Andrew) will also be given a chance to execute. In this case, notify() or notifyAll() works. Probably, here notify() is more efficient, as only one thread is woken up. Is this right?
Case B (pre-emptive + notify)
-----------------------------
Let's consider pre-emptive OS. Thread(Andrew) may have the highest priority, but notify() nullifies all priorities. It "bypasses any and all priority that the various threads". So Thread(Andrew) will starve if Thread(Max) keeps waking up(and winning) again.
Case C (pre-emptive + notifyAll)
--------------------------------
Now let's consider notifyAll(). All threads will be waken up, but Thread(Andrew) keeps winning because he has the highest priority. So Thread(Max) starves. Is this correct?
Case D (equal priority threads)
-------------------------------
Now let's consider the scenario where the developer never use Thread.setPriority() in his codes. So all threads will have the same priorities because they inherit from the same main thread when they were spawned.
i. If OS = time-sliced, back to Case A. All threads get to run.
ii. If OS = pre-emptive, and notify() is used, Case B can happen if Thread(Max) keeps waking up(and winning) again.
iii. If OS = pre-emptive, and notifyAll() is used, Case B can also happen if Thread(Max) keeps being selected to run. Because for notifyAll(), only one thread is selected arbitrarily as far as the developer is concerned to run.
So ceteris paribus, notify and notifyAll have the same net effect.
Please advise,
Derek

[Max Habibi]

Originally posted by Derek Canaan:
Hi Max,
First, thanks for your contributions in this forum. They helped me a lot. Please help me out here as i am trying to get a grip on this issue.

Not at all. I probably get more out of this than anyone here.

...excellent analysis snipped

Here's the thing: Most operating systems use a combination of PE and TS, exactly for this sort of issue(Thread(Max) waking up again and again). That is, all other things being equal, the priority of the thread that's been waiting the longest gets bumped a bit, eventually culminating into a winning advantage, and starvation is avoided.
By using notify, you're essentially disallowing the operating system from taking Thread priorities into account, even to the extent in which it uses priority to massage these sorts of problems: In effect, you're disabling part of the built in Threading functionally, which is the evaluation of Thread priority. Of course, this doesn't hurt if you're only working with a single Thread, but it doesn't lend itself to more demanding scenarios.
As a matter of interest, most UNIX type systems pay more attention to thread priority then window systems. This is because they expect smarter operation systems decisions (and some would say smarter programs that actually know what they're doing when they set a higher priority).
You get this for free with a notifyall call, and you don't suffer any measurable performance penalty: You avoid starvation from, say, the Thread(Max) winning each argument simply by virtue of waking up. I know it seems it's like an unlikely occurrence, but run super fast code through a super fast system continuously, for a long enough time, and it's guaranteed to happen.
With the notifyAll call, the priority of the Threads(!=Max) will gradually get bumped until they gets a chance to run. Thus, you don't run the risk of starvation. Additionally, you're working 'within' the Threading system, priority and all. Finally, when a single Thread is concerned, you don't get any sort of measurable performance hit either way. You're basically getting a more extendable, scalable, and resilient implemention at no extra cost. Why wouldn't you do it?
all best,
M

[Philippe Maquet]

Hi Derek,
You asked me to reply here to question 8, but I've nothing to add to what Andrew wrote so clearly!
And I agree with Max either about the not measurable difference between notifying a single thread through notify() or notifyAll() as my tests proves it.
Though, reading Max, it looks like notify() should be deprecated, yet it isn't... (anyway not yet)
When applicable to your design, it appears that the principal/only(?) benefit of notify() is purely semantic (Max, remember the Skateboard Notification pattern ).
OK, I'm giving up here, you won Max!
Best,
Phil.

[Max Habibi]

It's a good discussion, IMO. And I'm not sure that notify should be removed from the language: after all, volitile is still around. That should probably be the first candidate to go.
M

[Derek Canaan]

Hi Phil,
I was trying to understand what Andrew was stating on mutex on recordOne vs. mutex on collection of records by using some codes. Would you comment on this analysis:

Q8 is still grey for me, but i can see a little light at the end of the tunnel. Let me see if i understood your following statements correctly:

[Andrew]: But if multiple threads can go into wait() state on a single mutex waiting for different conditions, then you really need to notify all of them so that they can all check whether their personal condition has changed.
So if you had a mutex on recordOne then you know that there is only one condition for this mutex (recordOne is either locked or unlocked) and you could safely call notify() on a single thread waiting for recordOne.
But if you had a mutex on a collection of records, then calling notify() on that collection will only transition one thread to blocked state (and then to runnable state), and when it transitions to runnable it may find that the condition it was waiting for (the individual record lock within the collection) is still not available - which will result in all the waiting threads returning to waiting state, even though there is potentially a lock free.

First, let me put a little meat into the codes:
code:

1.    Collection lockedRecords;
2.    lock(recNo) {
3.       synchronized(lockedRecords){
4.            while(lockedRecords.contains(recNo))
5.                lockedRecords.wait();
6.            }
7.            lockedRecords.put(recNo);
8.    }
9.    unlock(recNo) {
10       synchronized(lockedRecords){
11            lockedRecords.remove(recNo);
12            lockedRecords.notifyAll();
13    }

Suppose
1. Thread T12 runs lock(recNo) and successfully put recNo 12 into lockedRecords and exits lock method but has not started on unlock(recNo 12).
2. Since T12 exited, lockedRecords monitor is available. Suppose T35 runs lock(recNo), acquires lockedRecords monitor and successfully put recNo 35 into lockedRecords and exits lock method but has not started on unlock(recNo 35).
3. Now T1 and T2 would like to lock(recNo 12) and T3 and T5 would like to lock (recNo 35).
4. Threads T1, T2, T3, T5 successively got lockedRecords monitor but go to Waiting state because recNo 12 and 35 are still contained in lockedRecords.
5. T12 manages to get lockedRecords monitor and run unlock(recNo12) and does a lockedRecords.notifyAll()

Q1. In this case, all of threads T1, 2, 3, 5 will go to Blocked state and JVM will select one to Running state. Suppose T3 got selected, T3 wastes some CPU, and go back to Waiting state, BUT at the same time releases lockedRecords monitor. So JVM selects one from the Blocked state (T1, 2, and 5) but NOT T3 as it is in Waiting state. Is this understanding correct?
Q2. Now let's suppose lockedRecords.notify() is used instead of notifyAll. So JVM chooses one thread from (T1,2,3,5) from Waiting state to Blocked state. Let's consider the worst scenario: JVM chooses T3. T3 runs line 4, go back to Waiting state, BUT also releases the lockedRecords monitor. No other threads are in the Blocked state -> Thread starvation.
Nobody calls notify, so these threads cannot come out of the Waiting state. T35 will eventually invoke lockedRecords.notify() but in effect one out of T1,2,3,5 will get to call unlock(). The other 3 threads starve. Is this correct?
Follow-up post...:
Hey, wait a minute ... there may be no starvation even for notify()
Let's continue the analysis:

...JVM chooses T3. T3 runs line 4, go back to Waiting state, BUT also releases the lockedRecords monitor. No other threads are in the Blocked state.

But thread T35 to the rescue. T35 eventually runs unlock(recNo 35) and does a lockedRecords.notify().
1. Because T35 calls lockedRecords.notify(), JVM chooses one of (T1,2,3,5) from the Waiting state to Blocked state. (Remember now that recNo 12, and 35 are no longer in lockedRecords.)
2. Say JVM chooses T1 (it does not matter).
3. T1 goes to Running state because T35 releases the lockedRecords monitor when it exits unlock(recNo), and there is only one thread namely T1 in the Blocked state.
4. At this stage, T2,3,5 are in Waiting state.
5. T1 runs lock(), put recNo 12 into lockedRecords and finally, unlock() removing recNo 12 from lockedRecords and calls lockedRecords.notify(). (Now, again, recNo 12, and 35 are not in lockedRecords)
6. Because T1 calls lockedRecords.notify(), JVM chooses one of (T2,3,5) from the Waiting state to Block state.
7. Say JVM chooses T2 (it does not matter).
8. T2 goes to Running state because T1 releases the lockedRecords monitor when it exits unlock(recNo), and there is only one thread namely T2 in the Blocked state.
9. At this stage, T3,5 are in Waiting state.
10. T2 runs lock(), put recNo 12 into lockedRecords and finally, unlock() removing recNo 12 from lockedRecords and call lockedRecords.notify(). (Now, again, recNo 12, and 35 are not in lockedRecords)
11. Because T2 calls lockedRecords.notify(), JVM chooses one of (T3,5) from the Waiting state to Block state and so on ..., and hence the remaining threads 3 and 5 will also go to Running state.
Hence no thread starvation!
Is this correct?

[Philippe Maquet]

Hi Derek,

Q1. In this case, all of threads T1, 2, 3, 5 will go to Blocked state and JVM will select one to Running state. Suppose T3 got selected, T3 wastes some CPU, and go back to Waiting state, BUT at the same time releases lockedRecords monitor. So JVM selects one from the Blocked state (T1, 2, and 5) but NOT T3 as it is in Waiting state. Is this understanding correct?

Yes!

Q2. Now let's suppose lockedRecords.notify() is used instead of notifyAll. So JVM chooses one thread from (T1,2,3,5) from Waiting state to Blocked state. Let's consider the worst scenario: JVM chooses T3. T3 runs line 4, go back to Waiting state, BUT also releases the lockedRecords monitor. No other threads are in the Blocked state -> Thread starvation.

Yes, the other threads would stay asleep, possibly forever.

Nobody calls notify, so these threads cannot come out of the Waiting state. T35 will eventually invoke lockedRecords.notify() but in effect one out of T1,2,3,5 will get to call unlock(). The other 3 threads starve. Is this correct?

Still correct. BTW, that's why I didn't comment anything when I first read that post of you.

Follow-up post (...) Is this correct?

No. The problem is that each time you write "(it does not matter)", in fact it *DOES*. IMO.
Regards,
Phil.
[ February 13, 2004: Message edited by: Philippe Maquet ]

[Derek Canaan]

Hi Phil,

No. The problem is that each time you write "(it does not matter)", in fact it *DOES*.

Please bear with me as i run this analysis over for notify() case:

 
Time  Action                lockRecords  Wait pool  Remarks
------------------------------------------------------------
t0    starting               nil          nil             
t1    T12 calls lock(12)     R12          nil             
t2    T35 calls lock(35)     R12,R35      nil             
t3    T1,T2 calls lock(12)   R12,R35      T1,2          
t4    T3,T5 calls lock(35)   R12,R35      T1,2,3,5        
                                        
t5    T12 calls unlock(12)   R35          T2,3,5    JVM chose T1 - case 1
                                          T1,3,5    JVM chose T2 - case 2
                                          T1,2,5    JVM chose T3 - case 3
                                          T1,2,3    JVM chose T5 - case 4
case 1 (JVM chose T1)                                 
t6      T1 calls lock(12)    R35, R12     T2,3,5              
t7      T1 calls unlock(12)  R35          T3,5      JVM chose T2 - case 11
                                          T2,5      JVM chose T3 - case 12
                                          T2,3      JVM chose T5 - case 13
    case 11 (JVM chose T2)                                        
t8      T2 calls lock(12)    R35          T3,5          
        T2 calls unlock(12)  R35          T5        JVM chose T3 - case 111
                                          T3        JVM chose T5 - case 112
                                        
        case 111 (JVM chose T3)
t9      T3 calls lock(35)    R35          T5,3          
                                        
t10     T35 calls unlock(35) nil          T5        JVM chose T3 - case 111a
                                          T3        JVM chose T5 - case 111b
            case 111a (JVM chose T3)
t11     T3 calls lock(35)    R35          T5              
t12     T3 calls unlock(35)  nil          nil       JVM chose T5
t13     T5 calls lock(35)    R35          nil             
t14     T5 calls unlock(35)  nil          nil             

If the analysis is run for all other cases, the end result is still the same. No threads will be starved regardless which thread is chosen after notify() because the thread who calls lock will finally unlock, and other threads will have a chance to run.
Please comment,
Derek
[ February 16, 2004: Message edited by: Derek Canaan ]

[Philippe Maquet]

Hi Derek,
Or I missed everything in this thread, or you are talking about a design where threads synchronize on the locks container, right ?
In that case, each time the unlocking thread calls notify() instead of notifyAll(), it gives only one thread the chance to check is waiting condition. But maybe not to the one (if any) which could be interested in that particular unlock:
T1 owns L1
T2 waits for L1
T3 owns L2
T4 waits for L2
T1 unlocks and calls notify().
T4 is chosen and ... keeps waiting.
T3 unlocks and calls notify()
T4 is chosen again( why not) and is granted L2
T2 is still waiting... for ever? No, not sure, it may benefit of a future unlock, but it missed a chance to get L1 when it was released.
I really cannot add anything to what Andrew wrote in his first reply above, because everything is there and his English is far better than mine:

Andrew:
So if you had a mutex on recordOne then you know that there is only one condition for this mutex (recordOne is either locked or unlocked) and you could safely call notify() on a single thread waiting for recordOne.
But if you had a mutex on a collection of records, then calling notify() on that collection will only transition one thread to blocked state (and then to runnable state), and when it transitions to runnable it may find that the condition it was waiting for (the individual record lock within the collection) is still not available - which will result in all the waiting threads returning to waiting state, even though there is potentially a lock free.

Regards,
Phil.
[ February 16, 2004: Message edited by: Philippe Maquet ]

[Derek Canaan]

Hi Phil,
Thanks for bearing with this thread (pun not intended). The codes in question:

     Collection lockedRecords;
    lock(recNo) {
       synchronized(lockedRecords){
            while(lockedRecords.contains(recNo))
                lockedRecords.wait();
            }
            lockedRecords.put(recNo);
        }
    }
    unlock(recNo) {
       synchronized(lockedRecords){
            lockedRecords.remove(recNo);
            lockedRecords.[B][I]notify()[/I][/B];
       }
    } 

[Phil]:T1 owns L1
T2 waits for L1
T3 owns L2
T4 waits for L2
T1 unlocks and calls notify().
T4 is chosen and ... keeps waiting.
T3 unlocks and calls notify()
T4 is chosen again( why not) and is granted L2
T2 is still waiting... for ever? No, not sure, it may benefit of a future unlock, but it missed a chance to get L1 when it was released

Analysis below does show that T2 benefits from a future unlock:
T4 is chosen. T4 locks(L2) and T4 unlock(L2). At this point the lockRecords collection is empty! When T4 unlocks, lockRecords invokes notify(). Since T2 is the only thread in the wait pool, JVM has to choose it, and T2 runs lock and unlock L1.
Q1.If "it missed a chance to get L1 when it was released", does this constitute thread starvation?
Q2. When notifyAll() is used instead, T2 can also miss a chance to get L1 when it was released. Does this constitute a thread starvation? What is the official technical definition?
Q3. Could we conclude from the analysis, that for designs synchronizing on a record collection monitor and calling notify(), there still will not be any thread starvation?
Comments?
rgds,
derek
[ February 16, 2004: Message edited by: Derek Canaan ]

[Derek Canaan]

Hi Phil, Andrew, and Max
Let's put Andrew and Max statements and run a scenario in the context of a possible SCJD design:

[Andrew]:If you only have a single condition to check then you are quite safe with just using notify(). But if multiple threads can go into wait() state on a single mutex waiting for different conditions, then you really need to notify all of them so that they can all check whether their personal condition has changed.
So if you had a mutex on recordOne then you know that there is only one condition for this mutex (recordOne is either locked or unlocked) and you could safely call notify() on a single thread waiting for recordOne.

lock(recNo) {
       synchronized(RecNo){
            while(RecNo.isLock())
                RecNo.wait();
            }
            RecNo.setLock();
        }
    }
    unlock(recNo) {
       synchronized(RecNo){
            RecNo.unlock();
            RecNo.notify();
       }
    }

Now in the light of what Max said below, notify() even under this single condition check is *not* safe:

Here's the thing: Most operating systems use a combination of PE and TS, exactly for this sort of issue(Thread(Max) waking up again and again). That is, all other things being equal, the priority of the thread that's been waiting the longest gets bumped a bit, eventually culminating into a winning advantage, and starvation is avoided

.
1. T1, T2 competes for recNo 5.
2. T2 gets monitor.
3. T1 goes to wait pool
4. T2 finishes locks but has not started unlock
5. T3 wants recNo5, goes to wait pool
6. T2 unlocks, call notify()
7. T3 gets monitor
8. T1 continue to wait, OS bumps up T1 priority
9. T3 finishes locks but has not started unlock
10 T4 wants recNo5, goes to wait pool
11 T3 unlocks, call notify()
12 T4 gets monitor
13 T1 continue to wait, OS bumps up T1 priority
14 Repeat block and T1 waits forever ...
Because notify() nullifies OS priorities setting for waiting threads, T1 continue to starve. If notifyAll() is used, T1 gets to run.
Q1. Can we conclude that we should never use notify() even if there is only one condition for the mutex?
Q2. Phil mentioned that notify() should be deprecated, in this thread, Peter said notify() has its place. But at the moment, analysis shows notifyAll is safer and notify() starves threads even for a single condition check.
Comments?
derek
[ February 16, 2004: Message edited by: Derek Canaan ]

[Javini Javono]

Hi,
I am not a thread expert, but certainly since we are writing a server, for us
to study threading is an important topic, and in this way your questions are
relevant and important.
Forgive me for being "lazy", I've been studying my books concerning threads,
and admit that I have not read the above posts.

Q1. Can we conclude that we should never use notify() even if there is only one condition for the mutex?

No. notify() has it's place. And, if there is only one condition, and the boolean variable is
private, this is the place to use it. For more details, see the brilliant writing of Bloch.

Q2. Phil mentioned that notify() should be deprecated, in this thread, Peter said notify() has its place. But at the moment, analysis shows notifyAll is safer and notify() starves threads even for a single condition check.

Feel free to use notify() for a lot, or everything, depends on the context. There are some
circumstances, as pointed out by Bloch that notifyAll() can significantly degrade performance.
I suspect, that if you specify and document that all threads using your system must
use a, let's say, normal priority, that is, their priority must be identical, then using, for
example, a simple mutex, will most probably work on almost every single system.
But, if in doubt, and you want to ensure no starvation, use Phil's specific notification
technique. By the way, are you sure Phil said that notify() should be deprecated (admittedly
your sentence is ambiguous as to which person "in this thread" refers to); this
is rather alarming, if true, because in Phils specific notification algorithm, that is exactly where
you would want to use notify() instead of notifyAll() (as pointed out by Bloch, assuming
I understood Bloch correctly, as it is getting late, and it is time for bed).
Keep in mind that it may take a while to understand threads, thought certainly you
seem to know quite a lot and are very inquisitive. Bloch's book gives a very good
treatment, technical, which you may quite enjoy reading. Next, I'd recommend
Core Java, whichever volume covers threads. Even between these two books,
they differ in opinion, if my memory serves me, but I've been looking through
6-plus books on threading, taking notes, writing test code, and the like, and I
may be mistaken.
Again, if you are in to technicalities, definitely get Bloch's book, you can only enjoy
it.
Thanks,
Javini Javono

[Derek Canaan]

Hi Javini,

[Javini]:By the way, are you sure Phil said that notify() should be deprecated (admittedly your sentence is ambiguous as to which person "in this thread" refers to);

Admittedly, i did miss out the conjunction "but". My sentence should read, "Q2. Phil mentioned that notify() should be deprecated, but in this thread, Peter said notify() has its place. But at the moment, analysis shows notifyAll is safer and notify() starves threads even for a single condition check."
But yes, Phil did suggest it:

[Phil]:Though, reading Max, it looks like notify() should be deprecated, yet it isn't... (anyway not yet)

[Javini]:Keep in mind that it may take a while to understand threads, thought certainly you seem to know quite a lot and are very inquisitive

LOL, you are right about the inquisitive part.
My problem is i am having a tough time harmonizing what Andrew and Max said in the context of some possible designs for scjd:
In the context of scjd, Andrew basically gave two rules of thumb when to use notify and notifyAll:
1. Use notifyAll when mutex = collection of records
2. Use notify when mutex = a particular record
But i have drawn up two scenarios which seem to suggest:
1. It is ok to use notify even if mutex = collection of records
2. Using notify when mutex = a particular record may not be safe. It may cause thread starvation. Use notifyAll prevents that.
So my current state of understanding =
rgds,
derek
ps: thanks for the book recommendations. i see if i can get my hands on them
[ February 16, 2004: Message edited by: Derek Canaan ]

[Andrew Monkhouse]

Hi Derek,
Instead of "use notifyAll on a collection of Records", I should have said "use notifyAll when there are multiple conditions being checked on a single mutex".

Because notify() nullifies OS priorities setting for waiting threads, T1 continue to starve. If notifyAll() is used, T1 gets to run.

In your example, where you always had one thread waiting for the lock object, then T1 would always have a chance to run, and would probably get a higher chance than later threads:

T2 gets mutex, locks record 5, releases mutex

T1 gets mutex, goes into wait state

T2 gets mutex, releases lock, calls notify()

T1 blocks waiting for mutex

T3 blocks waiting for mutex

T2 releases mutex

In this case, since there was only one thread waiting for the lock, it did get woken up with the call to notify(), and it did get the chance to run. If that scenario continues (another thread attempting to get the lock each time a lock is released), then T1 will continue to be woken and while it is blocked state it's priority will increase until eventually it will get priority over new calls.
But this falls apart if you have say three threads / clients that are continually doing locking:

T2 gets mutex, locks record 5, releases mutex

T1 gets mutex, goes into wait state

T3 gets mutex, goes into wait state

T2 gets mutex, releases lock, calls notify()

T3 blocks waiting for mutex

T2 releases mutex

T3 gets mutex, locks record 5, releases mutex

T2 gets mutex, goes into wait state

T3 gets mutex, releases lock, calls notify()

T2 blocks waiting for mutex

T3 releases mutex

T2 gets mutex, locks record 5, releases mutex

T3 gets mutex, goes into wait state

In that case, I reused threads T2 and T3 - each time they released the lock they immediately tried to get it again.
Since a thread in wait state is disabled for thread scheduling purposes, T1 will never get a higher priority, and it is possible that it will never be woken.
So yes - in such a scenario you would be better off using notifyAll().
But if you have a case where you are only waiting on a single lock, and it is unlikely that there will be more than one thread waiting on that lock, then you could be quite safe using notify().
Regards, Andrew

[Philippe Maquet]

Hi Derek!
When Andrew wrote:

If you only have a single condition to check then you are quite safe with just using notify(). But if multiple threads can go into wait() state on a single mutex waiting for different conditions, then you really need to notify all of them so that they can all check whether their personal condition has changed.

it was clear (IMO) that notify() cannot be used with your design (multiple threads waiting on a single monitor for *different* conditions) !
Now just a few quick comments on what you wrote since my last post here:

Q1.If "[Phil]T2 missed a chance to get L1 when it was released[/Phil]", does this constitute thread starvation?

The problem is that it missed a chance to be granted the lock *when* it was available.

Q2. When notifyAll() is used instead, T2 can also miss a chance to get L1 when it was released.

No. Not if the lock was available, as it was in my example. It could "miss" a lock (but is it still missing?) if another thread is waiting to be granted a lock on the same record. But in that case, it doesn't miss anything, it just looses a fair competition . Do you see the difference ?

Q3. Could we conclude from the analysis, that for designs synchronizing on a record collection monitor and calling notify(), there still will not be any thread starvation?

No, obviously not.

Q1. Can we conclude that we should never use notify() even if there is only one condition for the mutex?

No, not if "there is only one condition".

Q2. Phil mentioned that notify() should be deprecated, in this thread, Peter said notify() has its place. But at the moment, analysis shows notifyAll is safer and notify() starves threads even for a single condition check.

Mmh... sorry but it was a bit ironic. I really thought it was clear.
Let me try again:
For defendable reasons, Max suggests to avoid notify() in all cases:

Max:
notifyAll is more adaptable(in case you actually need to notify more then a single thread in the future), and it's just as efficient. That is, I would challenge you to even be able to measure the time between notifyAll and notify when a single thread is waiting.

I did ("measure the time between notifyAll and notify when a single thread is waiting") and Max is right, there is no real difference.
Now, the test applied only to that particular case: one thread waiting on one monitor. It's probable (but I didn't check it) that notify() is more efficient that notifyAll() when multiple *interchangeable* threads are waiting.
But even in that case (where you cannot measure any performance difference - only one thread waiting on one monitor by design), I like notify() for semantic reasons, because it's self-documenting what happens: you are not "notifying all passengers of a skateboard", a sort of vehicule (your design context) which cannot have more than one passenger (thread).
In other words, I fully agree with what Peter den Haan wrote in the thread you mention (which is not different from what Andrew wrote above BTW).

Javini:
By the way, are you sure Phil said that notify() should be deprecated (admittedly
your sentence is ambiguous as to which person "in this thread" refers to); this
is rather alarming, if true, because in Phils specific notification algorithm, that is exactly where
you would want to use notify() instead of notifyAll() (as pointed out by Bloch, assuming
I understood Bloch correctly, as it is getting late, and it is time for bed).

Now you know that I was ironic about it, sorry.
But you let me think that I should complete that thread when I'll find the time to do it. Or I'll have to make even clearer that it is now that the "specific notification" technique doesn't worth while (my published test results showed that it performs just in the average of the three compared solutions, which would be OK if it wasn't the most complex ), or I'll find a way to optimize it (I have a few ideas).

Javini:
Keep in mind that it may take a while to understand threads, thought certainly you
seem to know quite a lot and are very inquisitive.

Agreed. I'd just add that experimenting is a good (the best?) way of learning. That's what makes the SCJD assignment and this forum so valuable BTW, more valuable than the piece of paper you'll get at the end anyway.
Mmh... I now just pray to not have Max reading this post, he'd be ROFL!
Best regards,
Phil.
[ February 17, 2004: Message edited by: Philippe Maquet ]

[Philippe Maquet]

Hi Andrew,
My post crossed yours.
Anyway, it's so nice to see you coming back here!
4 posts of mine to try - rather confusingly, I confess - to explain why and how your first post in this thread (9 days ago! ) was just clear and truthful... I feel a little ashamed!
Best regards,
Phil.