aspose file tools*
The moose likes Developer Certification (SCJD/OCMJD) and the fly likes Thread states, notify, notifyAll, wait Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Certification » Developer Certification (SCJD/OCMJD)
Bookmark "Thread states, notify, notifyAll, wait" Watch "Thread states, notify, notifyAll, wait" New topic
Author

Thread states, notify, notifyAll, wait

Derek Canaan
Ranch Hand

Joined: Nov 05, 2003
Posts: 64
Hi,
Would like your answers on the questions below:

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
Greenhorn

Joined: Jan 26, 2004
Posts: 25
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
Ranch Hand

Joined: Nov 05, 2003
Posts: 64
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
author and jackaroo
Marshal Commander

Joined: Mar 28, 2003
Posts: 11486
    
  94

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


    The Sun Certified Java Developer Exam with J2SE 5: paper version from Amazon, PDF from Apress, Online reference: Books 24x7 Personal blog
    Derek Canaan
    Ranch Hand

    Joined: Nov 05, 2003
    Posts: 64
    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:
    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
    Ranch Hand

    Joined: Nov 05, 2003
    Posts: 64
    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
    town drunk
    ( and author)
    Sheriff

    Joined: Jun 27, 2002
    Posts: 4118
    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


    Java Regular Expressions
    Derek Canaan
    Ranch Hand

    Joined: Nov 05, 2003
    Posts: 64
    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
    town drunk
    ( and author)
    Sheriff

    Joined: Jun 27, 2002
    Posts: 4118
    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
    Bartender

    Joined: Jun 02, 2003
    Posts: 1872
    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
    town drunk
    ( and author)
    Sheriff

    Joined: Jun 27, 2002
    Posts: 4118
    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
    Ranch Hand

    Joined: Nov 05, 2003
    Posts: 64
    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:
    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
    Bartender

    Joined: Jun 02, 2003
    Posts: 1872
    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
    Ranch Hand

    Joined: Nov 05, 2003
    Posts: 64
    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:

    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
    Bartender

    Joined: Jun 02, 2003
    Posts: 1872
    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
    Ranch Hand

    Joined: Nov 05, 2003
    Posts: 64
    Hi Phil,
    Thanks for bearing with this thread (pun not intended). The codes in question:
    [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
    Ranch Hand

    Joined: Nov 05, 2003
    Posts: 64
    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.


    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
    Ranch Hand

    Joined: Dec 03, 2003
    Posts: 286
    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
    Ranch Hand

    Joined: Nov 05, 2003
    Posts: 64
    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
    author and jackaroo
    Marshal Commander

    Joined: Mar 28, 2003
    Posts: 11486
        
      94

    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
    Bartender

    Joined: Jun 02, 2003
    Posts: 1872
    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
    Bartender

    Joined: Jun 02, 2003
    Posts: 1872
    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.
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Thread states, notify, notifyAll, wait