File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Developer Certification (SCJD/OCMJD) and the fly likes Threads 001 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 "Threads 001" Watch "Threads 001" New topic
Author

Threads 001

Javini Javono
Ranch Hand

Joined: Dec 03, 2003
Posts: 286
Hi,
I was thinking about this simple construct today (a mutex). Here are my
elementary thoughts on it. The algorithms are at Doug Lea's web site.
Class MyClass is multithreaded.

The elementary puzzler I was considering today, is why is notify()
sufficient in this context instead of notifyAll()?
This was a puzzler (at least for me) because you could have threads
waiting for different reasons:
1. ThreadA could be waiting because it called the wait() method.
2. ThreadB could be waiting because it called the wait() method.
3. ThreadC could be waiting to enter obtainIt() because another
thread was currently running within unObtainIt().
And, what would happen if ThreadE called notify(), which, I have read,
randomly selects exactly one thread to run? And, what if it selected
ThreadC?
Clearly ThreadC, or for that matter, ThreadsA and B, can't begin
running until ThreadE has exited the unObtainIt() method, for
only at that time is the lock on this released. So, assume that
ThreadE has just called notify() and exited unObtainIt().
At that point one of two things could hypothetically occur
1. ThreadA or ThreadB would begin running and obtain the lock on this, or
2. ThreadC would run and upon entering obtainIt() get the lock on this.
However, the mutex model would fail if ThreadC was given
permission to run next and that counted as a "notify"!
Thus, I believe that while its true all three threads are
waiting to get a lock on this, ThreadA and B are particularly
special, and when notify() is called, only those threads
that have called this.wait() are considered to be made running
as a direct consequence of the previous notify() call.
Or, even if ThreadC were made running first, the thread
scheduler still knows that it "owes" a notify to one of
those threads that are waiting due to having specifically
called wait().
Thus, ThreadC will never be made running as a consequence
of the notify() call (because it has not yet called wait()).
And, in short, that was the puzzler, and my explanation,
in layman's terms, as to what happens.
[Aside: moving away from the micro details of the threads,
the mutex only works properly if every call to obtainIt()
is followed by a call to unObtainIt(), otherwise, one or more
threads ends up never being awoken after calling wait().]
[Aside: after posting this, I read over the Javadoc on
Object.notify(), and it is clearer now that I have gone through
an example step by step; in short, ThreadC prior to
entering obtainIt() does not have the this's monitor, so,
it's not a player in the "wait and notify game."]
I still didn't answer the question as to why notifyAll()
wasn't used; but, I feel confident that notify() is sufficient
in the above case (and, that is because any thread awakened
by notify() will always be able to proceed. Perhaps I will
come upon an example in the text books where a notifyAll() is
required and a notify() is not sufficient; certainly the books
say "play it safe, use notifyAll()," but it's nice to understand
the details.
Thanks,
Javini Javono
[ January 15, 2004: Message edited by: Javini Javono ]
Jacques Bosch
Ranch Hand

Joined: Dec 18, 2003
Posts: 319
Hey Javini.
Concerning this, here's a question not commented on yet:
From:
http://www.coderanch.com/t/184896/java-developer-SCJD/certification/NX-Lock-Unlock-methods-OK

Even for unlocking, notify() should suffice in stead of notifyAll() since only one other thread/client will be able to get the lock. So, you're actually slowing the system if you wake up all the threads.
Missing something again?
Using notify() only:
I started up 30 threads that all tried to loop through the same 3 recs and modify them, and it works perfectly every time.

Your thoughts?


Jacques<br />*******<br />MCP, SCJP, SCJD, SCWCD
Marlene Miller
Ranch Hand

Joined: Mar 05, 2003
Posts: 1391
The elementary puzzler I was considering today, is why is notify() sufficient in this context instead of notifyAll()?

If several threads were waiting on different conditions (not your example), it would not suffice to use notify, because the JVM might pick a thread waiting for a condition that does not hold without picking the possibly many that could continue. For example, some threads are waiting for the condition count > MIN and other threads are waiting for the condition count < MAX.
notify can be used to improve performance when you are sure that at most one thread needs to be woken. This applies when
1. All possible waiting threads are necessarily waiting for conditions relying on the same notifications, usually the exact same condition.
2. Each notification intrinsically enables at most a single thread to continue. Thus it would be useless to wake up others.
3. You can accommodate uncertainties surrounding the possibility that an interrupt and a notify may occur at about the same time.
From Doug Lea�s Concurrent Programming in Java, 3.2.4.2 Single Notification.
Marlene Miller
Ranch Hand

Joined: Mar 05, 2003
Posts: 1391

while (obtained) wait();
//it is unclear why an "if (obtained)" would not work just
//just as well as long as the thread scheduler is operating
//100% correctly. Does anyone know the answer to this?

When a waiting thread is awakened and acquires the lock, the thread does not know whether the condition it is waiting for is actually true; it only knows that it has been woken up.
Suppose a thread changes the condition (obtained = true) and invokes notify(). A thread is awakened and competes with other threads to acquire the lock. Some other thread might acquire the lock and change the condition again (obtained = false) before the awakened thread acquires the lock.
[ January 16, 2004: Message edited by: Marlene Miller ]
Andrew Monkhouse
author and jackaroo
Marshal Commander

Joined: Mar 28, 2003
Posts: 11460
    
  94

Hi Javini
Just to expand on Marlene's point "If several threads were waiting on different conditions (not your example), it would not suffice to use notify" ...
  • Thread A locks record 1
  • Thread B locks record 2
  • Thread C attempts to lock record 1 - goes into wait
  • Thread D attempts to lock record 2 - goes into wait
  • Thread A unlocks record 1 - calls notify()
  • Thread D wakes up, checks record 2 is still locked, goes back into wait


  • You now have threads waiting unnecessarily. If you had called notifyAll() then this would not have occured.
    Regards, Andrew


    The Sun Certified Java Developer Exam with J2SE 5: paper version from Amazon, PDF from Apress, Online reference: Books 24x7 Personal blog
    Andrew Monkhouse
    author and jackaroo
    Marshal Commander

    Joined: Mar 28, 2003
    Posts: 11460
        
      94

    Hi Javini,
    Or, even if ThreadC were made running first, the thread
    scheduler still knows that it "owes" a notify to one of
    those threads that are waiting due to having specifically
    called wait().

    No - what happens is that one of the waiting threads is notified that it may go into Ready-to-run state. (Remember your state tables from SCJP?)
    So at the end of the call to notify(), ThreadC is in ready-to-run state, and ThreadA is in ready-to-run state (it could be ThreadB instead of ThreadA). ThreadE then leaves the unobtainIt() method. Sometime after this the scheduler looks at which threads are in ready-to-run state, and picks one of them to run. Either ThreadC or ThreadA could be picked - there is nothing special about either one of them. If ThreadC runs and gets to the wait() call, it will transition to the waiting-for-notification state. The scheduler will then look at which threads are in ready-to-run state, and picks ThreadA which has been patiently waiting for a time slice.
    Is that a bit clearer?
    Regards, Andrew
    Andrew Monkhouse
    author and jackaroo
    Marshal Commander

    Joined: Mar 28, 2003
    Posts: 11460
        
      94

    Hi Jacques,
    Originally posted by Jacques Bosch:
    Concerning this, here's a question not commented on yet:
    From:
    http://www.coderanch.com/t/184896/java-developer-SCJD/certification/NX-Lock-Unlock-methods-OK

    Sorry missed that earlier.
    Now I am stuck in a permanent loop. I go to that thread, only to find that it refers me to this thread, which refers me to that thread, which ... :roll:
    I hope your question has been answered in this post.
    Regards, Andrew
    Jacques Bosch
    Ranch Hand

    Joined: Dec 18, 2003
    Posts: 319

    Just to expand on Marlene's point "If several threads were waiting on different conditions (not your example), it would not suffice to use notify" ...
    * Thread A locks record 1
    * Thread B locks record 2
    * Thread C attempts to lock record 1 - goes into wait
    * Thread D attempts to lock record 2 - goes into wait
    * Thread A unlocks record 1 - calls notify()
    * Thread D wakes up, checks record 2 is still locked, goes back into wait
    You now have threads waiting unnecessarily. If you had called notifyAll() then this would not have occured.

    But even if notifyAll() was used. Who says thread D was not still the one that got there first? Or, can the next thread get there if D goes right back to wait?
    Bit fuzzled.
    Andrew Monkhouse
    author and jackaroo
    Marshal Commander

    Joined: Mar 28, 2003
    Posts: 11460
        
      94

    Hi Jacques,
    Perhaps I left it a bit too open. Try again...
    Using notify():
  • Thread A locks record 1
  • Thread B locks record 2
  • Thread C attempts to lock record 1 - goes into wait state
  • Thread D attempts to lock record 2 - goes into wait state
  • Thread A unlocks record 1 - calls notify()
  • Thread D goes into ready-to-run state
  • Thread D gets sliced in, checks record 2 is still locked, goes back into wait state
  • No threads remain in ready-to-run state. Server is idle


  • At the end of that cycle, we have one record locked, one thread waiting for that record to be unlocked, and one thread waiting for no good reason.
    Now for notifyAll():
  • Thread A locks record 1
  • Thread B locks record 2
  • Thread C attempts to lock record 1 - goes into wait state
  • Thread D attempts to lock record 2 - goes into wait state
  • Thread A unlocks record 1 - calls notifyAll()
  • Thread C goes into ready-to-run state
  • Thread D goes into ready-to-run state
  • Thread D gets sliced in, checks record 2 is still locked, goes back into wait state
  • Thread C gets sliced in, finds record 1 is unlocked, locks the record


  • Since notifyAll() put all waiting threads into the ready-to-run state, they will be able to run as soon as the scheduler gives them a chance. So even though Thread D "woke up" first (was scheduled first) as soon as it has gone back into wait state the scheduler will look for other threads that are ready-to-run and will schedule one of them. So thread C managed to lock its record.
    Any clearer?
    Regards, Andrew
    Jacques Bosch
    Ranch Hand

    Joined: Dec 18, 2003
    Posts: 319

    Since notifyAll() put all waiting threads into the ready-to-run state, they will be able to run as soon as the scheduler gives them a chance. So even though Thread D "woke up" first (was scheduled first) as soon as it has gone back into wait state the scheduler will look for other threads that are ready-to-run and will schedule one of them. So thread C managed to lock its record.
    Any clearer?

    Much! That's what I wasn't sure about.
    Thanx again!
    Javini Javono
    Ranch Hand

    Joined: Dec 03, 2003
    Posts: 286
    Hi,
    I've re-written my original post: as you can see, during the re-write
    I did not fully understand the why's and wherefore's of the informative
    comments from Marlene Miller and Andrew Monkhouse (and, this re-write
    cannot cover all the information in their posts, so you should read
    them individually, and not assume that all their points are presented
    herein); I've left the errors in so that the understanding is perhaps
    clearer, that is, by making false statements and seeing why they are
    false, may be clearer. And, the corrections to these false statements
    are made after the code snippet.
    I was thinking about this simple construct today (a mutex). Here are my
    elementary thoughts on it. The algorithms are at Doug Lea's web site.
    IMPORTANT: Some of the comments within the following code snippet
    are false! I made these assertions while thinking conceptual; however,
    when I went through in a case by case discussion below the code
    snippet, I reveal why some comments within the code surprised me
    and turned out false. I leave the false statements in the comments
    "for clarity" of all the complexity which exists in what appears to
    be only a few lines of code.
    Class MyClass is multithreaded.

    The elementary puzzler I was considering today, is why is notify()
    sufficient in this context instead of notifyAll()?
    This was a puzzler (at least for me) because you could have threads
    waiting for different reasons:
    1. ThreadA could be waiting because it called the wait() method.
    2. ThreadB could be waiting because it called the wait() method.
    3. ThreadC could be waiting to enter obtainIt() because another
    thread was currently running within unObtainIt().
    And, what would happen if ThreadE called notify(), which, I have read,
    randomly selects exactly one thread to run? And, what if it selected
    ThreadC?
    Clearly ThreadC, or for that matter, ThreadsA and B, can't begin
    running until ThreadE has exited the unObtainIt() method, for
    only at that time is the lock on this released. So, assume that
    ThreadE has just called notify() and exited unObtainIt().
    At that point one of two things could hypothetically occur
    1. ThreadA or ThreadB would begin running and obtain the lock on this, or
    2. ThreadC would run and upon entering obtainIt() get the lock on this.
    However, the mutex model would fail if ThreadC was given
    permission to run next and that counted as a "notify"!
    Thus, I believe that while its true all three threads are
    waiting to get a lock on this, ThreadA and B are particularly
    special, and when notify() is called, only those threads
    that have called this.wait() are considered to be made running
    as a direct consequence of the previous notify() call.
    Or, even if ThreadC were made running first, the thread
    scheduler still knows that it "owes" a notify to one of
    those threads that are waiting due to having specifically
    called wait().
    Thus, ThreadC will never be made running as a consequence
    of the notify() call (because it has not yet called wait()).
    And, in short, that was the puzzler, and my explanation,
    in layman's terms, as to what happens.
    Here is an explanation using the terminology of threads:
    a thread is runnable or blocked. If a thread is runnable,
    it is ready to be scheduled and run by the thread manager,
    and it remains ready to run until it is given a time slice
    and run.
    Thus, ThreadE leaves the unObtainIt() method, and the
    thread manager halts it to let other threads have a chance
    to run: ThreadE is then ready to run, but not running.
    Because ThreadE has just called the notify() method, either
    ThreadA or B moved from the blocked state to the ready to
    run state, because these two threads had previously called
    wait(), one of the two will make this transition when notify()
    is called. Let's say ThreadA was the thread which moved to
    the ready to run state.
    ThreadC had been blocked attempting to enter into the
    obtainIt() method, and it is remains ready to run.
    Case 1:
    Assume ThreadC is now made to run by the thread scheduler;
    it, of course, obtains the object lock on this upon entering
    the isObtained() method, never invokes wait() because obtained
    is false, and exits obtainIt() believing, correctly, that
    it now has exclusive access to the shared resource.
    ThreadA is still ready to run, and the thread scheduler runs
    ThreadA; now, we see that my assertion about using an
    if() statement within the obtainIt() method is totally and
    completely wrong! For if the if() statement had been used,
    ThreadA would also exit obtainIt() believing it had exclusive
    access to the same shared resource as ThreadC! However,
    as the code is written correctly (but be sure to remove that
    if statement which throws a ProgrammerLogicError), ThreadA
    is in a while loop instead, and so it calls wait() again
    due to isObtained being true.
    Case 2:
    Assume ThreadA is now made to run by the thread scheduler.
    It obtains the object lock on this, checks the while()
    condition which is false, and exits obtainIt() believing
    correctly that it has an exclusive lock on the shared resource.
    Then ThreadC runs, and it ends up calling wait(), thus
    blocking ThreadC, so that it is not ready to run. Now both
    ThreadB and C are not ready to run, and one of them will be
    placed into the ready to run state only when the next notify()
    call is made.
    [Aside: moving away from the micro details of the threads,
    the mutex only works properly if every call to obtainIt()
    is followed by a call to unObtainIt(), otherwise, one or more
    threads ends up never being awoken after calling wait().]
    [Aside: after posting this, I read over the Javadoc on
    Object.notify(), and it is clearer now that I have gone through
    an example step by step; in short, ThreadC prior to
    entering obtainIt() does not have the this's monitor, so,
    it's not a player in the "wait and notify game."]
    I still didn't answer the question as to why notifyAll()
    wasn't used; but, I feel confident that notify() is sufficient
    in the above case (and, that is because any thread awakened
    by notify() will always be able to proceed. Perhaps I will
    come upon an example in the text books where a notifyAll() is
    required and a notify() is not sufficient; certainly the books
    say "play it safe, use notifyAll()," but it's nice to understand
    the details.
    Aside: Notes and Quotes:
    A thread becomes Not Runnable when one of these events occurs:
    * Its sleep method is invoked.
    * The thread calls the wait method to wait for a specific condition to be satisifed.
    * The thread is blocking on I/O. To become runnable, the I/O must complete.
    When a thread is Runnable, it does not mean that it is running, but
    that it is ready to be chosen to be run. A thread that yields
    leaves the running state, remains in the Runnable state, and thus
    can be chosen to be run again.
    I use "ready to run" instead of "Runnable".
    if someThread.isAlive() returns true, the thread, someThread, is either Runnable
    or Not Runnable; that is, someThread has been started, but it has not yet stopped
    (i.e., exited its run() method and died).
    Thanks,
    Javini Javono
    [Andrew: tried to make some of the code lines less wide so we don't get horizontal scroll bars]
    [ January 16, 2004: Message edited by: Andrew Monkhouse ]
    Andrew Monkhouse
    author and jackaroo
    Marshal Commander

    Joined: Mar 28, 2003
    Posts: 11460
        
      94

    Hi Javini,

    (phew!)
    Now try running it. When I ran it the first time, I got the following:

    As you can see, I have set it up so that attempts to lock a record only happen every 10 seconds. Checks on whether anyone owns a particular lock / anyone is waiting for the lock happen at alternate 5 second intervals. You can see that at 10:52:30 there were 2 threads waiting for lock 'B', but no one owned the lock! Two clients were waiting for 20 seconds for no good reason. This is very poor design.
    Change that notify() to a notifyAll(), and this is the result:

    This time there was never a case where any thread was waiting unnecessarily. If a lock was available then a thread got it.
    Subsequently my second run only took 30 seconds to complete - and this is guaranteed every time. But when I ran the first code, it took 1:40 to complete. And that is completely variable - you cannot accurately predict how long it will take to complete.
    Regards, Andrew
    [ January 16, 2004: Message edited by: Andrew Monkhouse ]
    Javini Javono
    Ranch Hand

    Joined: Dec 03, 2003
    Posts: 286
    Hi Andrew,
    Thanks for your posting. Please remember that I am not preaching
    that people should use notify() verse notifyAll(); but, I am trying
    to understand the differences between the two, and to understand
    the details of how threading works.
    Your post is very interesting in that it extends the simple example
    I gave. My original example, based on Doug Lea's Mutex class,
    uses one class to lock one boolean.
    Question: would I be correct in asserting that for my original example,
    notify() would be sufficient and equal to notifyAll()?
    Now, let's go on to your example. And, keep in mind, that in writing
    about it, I am learning about it simultaneously, as obviously you have
    far more experience than I do.
    You have one class, this, being used as the monitor against three
    different lock flags: boolean variables a, b, and c.
    Question: does this particular mutex have a particular name?
    Using notify() in this context would appear, intuitively, and as you showed
    imperically, to be less adept than notifyAll(). So, I'll run through an example
    to see if I understand why.
    Thread01 requests a, grabs lock on a.
    Thread02 requests b, grabs lock on b.
    Thread03 requests c, grabs lock on c.
    Thread04 requests a, but wait().
    Thread05 requests b, but wait().
    Thread06 requests c, but wait().
    Thread01 calls notify(). The scheduler now wants to make only
    one thread ready to run: Thread04, 05, or 06. If it randomly
    chooses Thread04, then it is most efficient, because Thread04 will
    obtain the lock on a. But, most of the time, an inefficient
    choice will be made, such as choosing Thread05, who becomes
    ready to run. But, no sooner is Thread05 actually running,
    then Thread05 has to call wait() since Thread02 is using b.
    So, I agree, and thank you for your example, an example which
    may be applicable in our designs when we create logical record
    locking, I agree that notify() in this context is not as desirable
    as notifyAll().
    So, please let me look through the case of notifyAll(). Using
    the same scenario as above, all waiting threads would become
    ready to run after Thread01 calls notifyAll(); as each thread
    sequentially becomes running, they will immediately call
    wait(), but all but Thread04 will wait(), and Thread04() will
    obtain the lock on a. So, everything is cool and the application
    will always complete (for every lock, there will be an unlock
    on each of the three booleans).
    Now, let us return back to the notify() case in your example. I find it interesting
    that the process even is guaranteed to come to completion! That is,
    I intuitively wonder if it was only luck that when notify() was used,
    all threads eventually got the lock on their particular boolean and then
    subsequently released it.
    Question: Of course, your comment, "And that is completely variable -
    you cannot accurately predict how long it will take to complete." may
    be another way of saying: the darned thing may never complete when
    you use notify().
    In the simple example I gave (one boolean associated with only one
    mutex), there is big trouble if for any reason a thread can't grab
    the lock there and then after notify() is called.
    And, in your example, I would think that the same logic would apply
    equally fatally? Thread01 calls notify() after setting a to false,
    but Thread05 is made ready to run, becomes running, but is asking
    to lock boolean b, thus Thread05 calls wait(), and you have lost
    a thread notification making the correct thread type ready
    to run. So, I don't see how in my walk-thru, all the waiting threads
    for boolean a would ever get a chance to be made able to run
    so they could lock a. The only way this would be possible if is
    in your code example, somewhere, there is someone priming
    notify() extra times, until by chance, eventually your application
    completes; but, I only see a call to notify() in the release() method.
    Perhaps I am missing something and my conclusion is incorrect? (It
    certainly would not surprise me if I was missing something).
    Again, I understand that your example is showing the power of
    notifyAll() over notify(). And, my questions are not questioning
    your assertion, but making sure I understand the underlying
    details of how threading, wait(), notify(), and notifyAll() work.
    And, your comments now and in the above were quite helpful
    in me gaining this understanding, for I then started to use
    more appropriate vocabulary.
    Andrew, thanks for your example. Among other things, it is a blue-print
    that we can apply to our systems to trace what our threads are up to.
    I have not had a chance to read your code precisely, but I will look it
    over again, even run it over the week-end, and see if it always
    comes to completion.
    Thanks,
    Javini Javono
    [ January 17, 2004: Message edited by: Javini Javono ]
    Andrew Monkhouse
    author and jackaroo
    Marshal Commander

    Joined: Mar 28, 2003
    Posts: 11460
        
      94

    Hi Javini,
    Ooops - forgot that there is a bug in UBB which, when editing, may cause loss of part of a post which contains both quoted text and code samples - that is what happened above. I had actually covered at least your question:
    Question: would I be correct in asserting that for my original example, notify() would be sufficient and equal to notifyAll()?

    Yes, in your original example, notify() is sufficient (and may be preferable, since waking the other threads unnecessarily would be inneficiant).
    You have one class, this, being used as the monitor against three different lock flags: boolean variables a, b, and c.
    Question: does this particular mutex have a particular name?

    It is the mutex on the instance of the class.
    Now, let us return back to the notify() case in your example. I find it interesting
    that the process even is guaranteed to come to completion! That is,
    I intuitively wonder if it was only luck that when notify() was used,
    all threads eventually got the lock on their particular boolean and then
    subsequently released it.
    Question: Of course, your comment, "And that is completely variable -
    you cannot accurately predict how long it will take to complete." may
    be another way of saying: the darned thing may never complete when
    you use notify().

    No - it is still guaranteed to complete. The worst case scenario did hapen in my example - there was a case where there were two records unlocked. But even in that case, when the remaining record is unlocked, one thread will be woken up and will get a lock. And so on until all the lock requests are eventually processed.
    Regards, Andrew
    Javini Javono
    Ranch Hand

    Joined: Dec 03, 2003
    Posts: 286
    Hi,
    I drew a simple state diagram, and I have concluded that
    you are correct.

    I wrote a column of numbers: 0 through 8.
    And then went through the worst case scenario.
    When a thread was attempting to get, I drew
    the boolean by the thread number.
    When the thread got the boolean, I drew
    a square around the boolean.
    When the thread released the boolean, I crossed
    out the squared boolean and said one of two things:
    1. notify() with no effect, or
    2. notify() must have an effect since any thread notified will
    get the lock since no one has any locks.
    The absolute worst case scenario, is that one thread is
    processed sequentially at a time.
    Thanks for the puzzler,
    Javini Javono
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Threads 001