spurious wakeups semantics

classic Classic list List threaded Threaded
37 messages Options
12
Reply | Threaded
Open this post in threaded view
|

spurious wakeups semantics

David Biesack

Can someone clarify the semantics of spurious wakeup as noted in java.lang.Object wait() in Java 5?

What happens to the monitor that the thread is waiting on? If another thread T2 has the lock
and a waiting thread T1 wakes up "suriously", what happens to thread T2? Are both threads T1 and T2 now
running, and what risks are there of race conditions? I understand that wait must be guarded
by a loop, but is it not possible that the wait condition is no longer safe from concurrent update?
Do variables used for wait conditions have to be volatile, for example?

--
David J. Biesack     SAS Institute Inc.
(919) 531-7771       SAS Campus Drive
http://www.sas.com   Cary, NC 27513

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: spurious wakeups semantics

Joshua Bloch-2
David,

Any wakeup, spurious or otherwise, is followed by acquisition of the
intrinsic lock on the object being waited on.  There is no race
condition, and no need for a volatile variable.

        Regards,

        Josh

On 10/29/05, David J. Biesack <[hidden email]> wrote:

>
> Can someone clarify the semantics of spurious wakeup as noted in java.lang.Object wait() in Java 5?
>
> What happens to the monitor that the thread is waiting on? If another thread T2 has the lock
> and a waiting thread T1 wakes up "suriously", what happens to thread T2? Are both threads T1 and T2 now
> running, and what risks are there of race conditions? I understand that wait must be guarded
> by a loop, but is it not possible that the wait condition is no longer safe from concurrent update?
> Do variables used for wait conditions have to be volatile, for example?
>
> --
> David J. Biesack     SAS Institute Inc.
> (919) 531-7771       SAS Campus Drive
> http://www.sas.com   Cary, NC 27513
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: spurious wakeups semantics

David Biesack
> Date: Sat, 29 Oct 2005 10:56:12 -0700
> From: Joshua Bloch <[hidden email]>
> Cc: [hidden email]
>
> David,
>
> Any wakeup, spurious or otherwise, is followed by acquisition of the
> intrinsic lock on the object being waited on.  There is no race
> condition, and no need for a volatile variable.
>
>         Regards,
>
>         Josh

what happens to thread T2 which was running and holding the lock when T1 gets the spurious wakeup?
At that time, it is holding the lock, so if T1 acquires it, T2 must give it up.. thus T2 must enter
a wait state, correct?

--
David J. Biesack     SAS Institute Inc.
(919) 531-7771       SAS Campus Drive
http://www.sas.com   Cary, NC 27513

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

AW: spurious wakeups semantics

Ernst, Matthias
In reply to this post by David Biesack

> what happens to thread T2 which was running and holding the
> lock when T1 gets the spurious wakeup?
> At that time, it is holding the lock, so if T1 acquires it,
> T2 must give it up.. thus T2 must enter a wait state, correct?

No, it's the other way around: T2 continues to hold the lock, so T1
cannot acquire it _yet_. It has to wait until T2 releases the lock.
It's a spontaneous transition from "waiting on xxx" to
"trying to enter xxx".

Matthias

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

RE: spurious wakeups semantics

David Holmes
Ernst, Matthias writes:
>
> No, it's the other way around: T2 continues to hold the lock, so T1
> cannot acquire it _yet_. It has to wait until T2 releases the lock.
> It's a spontaneous transition from "waiting on xxx" to
> "trying to enter xxx".

Exactly.

I see that the documentation for Object.wait() is a bit unclear on this. It
treats all the normal causes for wait returning and states:

"The thread T is then removed from the wait set for this object and
re-enabled for thread scheduling. It then competes in the usual manner with
other threads for the right to synchronize on the object"

but the mention of spurious wakeup follows that and doesn't make it clear
exactly what happens. Spurious wakeup should just be another bullet in the
list along with notify, notifyall, interruption and timeout.

David Holmes


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

RE: spurious wakeups semantics

P.H.Welch
In reply to this post by David Biesack

Hi,

Seeing the discussion on these spurious wakeups alarms (maybe depresses)
me, :( ...

The idea of a spurious wakeup was (surely?) never part of the conceived
design for Java threads ... just something that crept in because of
some dodgy threading libraries on which early implementations depended??

There was never such a thing in Hoare monitors, from which the Java ones
are slightly descended.

As a design concept, it makes no sense.  If spurious unblocking from
"wait()" invocations are legal, then JVMs could all simplify their
implementations by implementing wait/notify/notifyAll as no-ops.  That
looks perfectly legal!  In such JVMs, all "wait()"s are immediately
spuriously notified and all "notify()"s have nothing to do - easy, :).

Humm ... maybe the "wait()" can't be a no-op since it must release
the monitor?  But it could be implemented as a release-monitor-lock
then "Thread.yield()" them spurious-wakeup then acquire-monitor-lock.
Actually, I think that's optimisable back to a no-op!  Either way ...

... all those waits-inside-while-condition loops become busy-polling,

:(,

which is actually what they really are anyway ... with no guarantees
of exit.  I suspect that many real systems running on many real JVMs
(even without spurious wakeups) are at risk from never exiting such
loops.  Isn't the *only* technical reason for programming such loops
... to cope with spurious wakeups?  The other reasons for them being
lazy (or erroneous) logic ... that's a conjecture ... suspect true.

Isn't it time that spurious wakeups were removed from Java semantics?

Peter.
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

AW: spurious wakeups semantics

Ernst, Matthias
In reply to this post by David Biesack

> As a design concept, it makes no sense.  If spurious
> unblocking from "wait()" invocations are legal, then JVMs
> could all simplify their implementations by implementing
> wait/notify/notifyAll as no-ops.  

A trivial implementation of a concept does not render the concept
nonsensical.
The implementation is just not useful then.

I'm sure spurious wakeups have a raison d'etre (which would be
interesting to know the cause for).

But even if there were no spurious wakeups, the while loop is necessary
anyway in most cases
because the condition might have already changed back to false between
wakeup and the actual
acquisition of the monitor. Take the example of a threadpool thread:

...
  synchronized(jobs) {
    if(jobs.isEmpty()) wait();
    job = jobs.take();
  }
  job.run();
...

When this thread is woken up, but before it can actually re-acquire the
monitor, another
threadpool thread might have finished its work and grabbed the next job.
So it's necessary
to change 'if' to 'while'.

I've always explained spurious wakeups to myself as follows: "The while
loop is necessary
anyway because wait cannot atomically wakeup and acquire. So why pay a
penalty for removing
spurious wakeups in the threading library?"

Matthias

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: spurious wakeups semantics

tpeierls
In reply to this post by P.H.Welch
P.H.Welch wrote:
> Isn't it time that spurious wakeups were removed from Java semantics?

Who would benefit?

Not JVM designers, since they would have to work around the possibility of spurious wakeups at the
OS level, with a consequent cost in performance.

Not programmers: The only burden imposed on the programmer by the possibility of spurious wakeups
is the need to recheck a condition predicate. But this is such a good practice in any case that it
doesn't really count as a burden.

Imagine what would happen if spurious wakeups were disallowed. First, programmers (those who never
really bought into the idea that premature optimization is evil) would rush to turn this:

   synchronized (this) {
       while (!condition) wait();
       // do things that need condition to hold
   }

into this (to avoid a condition test that they "just know" is unnecessary):

   synchronized (this) {
       if (!condition) wait();
       // assert condition;  // "commented out to save cycles" (would be the claim)
       // do things that need condition to hold
   }

and then the notifying methods would change subtly so that the condition would *not* necessarily
hold while you are doing things that require it to be true. The resulting bugs would manifest
years later and not in a way that is obviously connected to the wait() call.


--tim

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: spurious wakeups semantics

Gregg Wonderly-3
In reply to this post by P.H.Welch
P.H.Welch wrote:
> which is actually what they really are anyway ... with no guarantees
> of exit.  I suspect that many real systems running on many real JVMs
> (even without spurious wakeups) are at risk from never exiting such
> loops.  Isn't the *only* technical reason for programming such loops
> ... to cope with spurious wakeups?  The other reasons for them being
> lazy (or erroneous) logic ... that's a conjecture ... suspect true.
>
> Isn't it time that spurious wakeups were removed from Java semantics?

I regularly code

        synchronized(lock) {
                while(!cond) {
                        lock.wait(10000);
                        log.fine("lock wakeup, cond: "+cond );
                }
        }

to make sure that if I see a no-progress situation, I can check to see which
threads are stuck with conditions not changing (see my http://logman.jini.org 
project that lets you use jini to remotely manage and monitor logging streams).
  This is a good debugging aid, and it helps me to manage all the interactions
that I expect to see during testing.  I can turn this debugging on, and see that
things are flowing as expected.  One can specify an even shorter sleep time, and
get more log messages which can help alert you to longer than expected waiting.

Gregg Wonderly
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: spurious wakeups semantics

Brian Goetz
In reply to this post by P.H.Welch
> Seeing the discussion on these spurious wakeups alarms (maybe depresses)
> me, :( ...

Short answer: Don't worry about it so much.

> There was never such a thing in Hoare monitors, from which the Java ones
> are slightly descended.

Hoare monitors are a mathematical abstraction.  Spurious wakeups are
permitted in recognition of the fact that real life is messy.  You can
build an OS / thread package that NEVER delivers spurious wakeups, but
there is a real engineering cost.  It is far more practical and
efficient to allow the odd spurious wakeup.

Its like the difference between fair and barging locks.  Nonfair locks
seem disturbing to everyone at first, until they realize the true cost
of fairness (~2 orders of magnitude performance cost), and then they
realize that statistical fairness is a better deal.  Same with SW;
allowing an OS to deliver a spurious wakeup once in a while (and it is
infrequent) allows for other optimizations and engineering improvements
in the implementation.

> As a design concept, it makes no sense.  If spurious unblocking from
> "wait()" invocations are legal, then JVMs could all simplify their
> implementations by implementing wait/notify/notifyAll as no-ops.  That
> looks perfectly legal!  In such JVMs, all "wait()"s are immediately
> spuriously notified and all "notify()"s have nothing to do - easy, :).

Yes, but no reasonable JVM would do this.  JVMs could also implement
sleep() with spin-waits.  There is a market here -- and such a JVM would
be rejected by the market.

> Isn't it time that spurious wakeups were removed from Java semantics?

 From the perspective of a software developer, spurious wakeups are
totally irrelevant.  Why?  To deal with spurious wakeups, you need to
wait in a loop and re-test the condition every time.  But a program
which uses wait() must do this anyway in order to be correct!  So, if
spurious wakeups were disallowed, it would have zero effect on program
code.

Short answer: Don't worry about it so much.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: spurious wakeups semantics

David Biesack
In reply to this post by P.H.Welch
> From: "P.H.Welch" <[hidden email]>
> Date: Wed, 02 Nov 2005 14:49:51 +0000
>
> Hi,
>
> Seeing the discussion on these spurious wakeups alarms (maybe depresses)
> me, :( ...

David Holmes' comments clarified the topic for me. (I think the Javadoc should be corrected so that it is clearer.)

When a thread gets a spurious wakeup, it does not simply resume. It merely exits the wait set for the lock. It must still request/obtain the lock, which means it is still blocked, waiting for the lock. IOW, "spurious wakeup" does not mean "return from wait()" and therefore calamity.

The reason the loop/condition test is necessary is that, because of a spurious wakeup, the thread can run even if notify{All}() was not called; i.e. if the second thread calls wait(), but only once it obtains the lock. Further, the thread may resume BEFORE the second thread changes the wait condition to true. Hence the loop is necessary. But it was always a good idea/necessary to begin with:. when notifyAll() is called, another thread may run first and reset the condition to false.

--
David J. Biesack     SAS Institute Inc.
(919) 531-7771       SAS Campus Drive
http://www.sas.com   Cary, NC 27513

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: spurious wakeups semantics

P.H.Welch
In reply to this post by David Biesack

Matthias and Tim both raise the defence for while-not-condition-wait-loops
with the classical argument that something might have unset the waited-for
condition between the notifyer setting it up and the waiter reacquiring
the monitor.  Of course that may happen ... but only if the logic in the
programmed system is sloppy (I used the term "lazy" last time).

I come from a different school.  With Hoare monitors, a waiting process
atomically reacquires the monitor from a "notifying" process that has
set up the condition being awaited - the term "signal" is used rather
than "notify".  That allows proofs of liveness - that a waiting process
will eventually proceed if enough signals happen.

The Java "notify" retains the monitor, allowing silly things to be done
- like unsetting the condition about which you just notified.  Worse -
because it's more complex - entirely different threads can acquire the
monitor between notification and reacquisition by the waiting thread and,
as you say, they can unset the condition.  So, we "have" to put our
wait()s inside a while-not-condition loop.  But ... only because of
sloppy design ... conjecture again!

Why does the Java "notify" retain the monitor?  Probably to reduce context
switching (and consequent cache missing) - I guess??

But the cost is busy - possibly infinite - waiting to get out of that
while-not-condition-wait-loop.  It's easy to create an example of a system
that's 99% of its time asleep - waiting for things to happen - with all
the wait()s protected by while-loops waiting for the right condition and
with all the notifying processes doing "notifyAll()"s ... and yet some
threads never progress out of their while-not-condition-wait-loops ...
all the rules in the text book have been followed!  Not good.

Matthias noted:
> A trivial implementation of a concept does not render the concept
> nonsensical.  The implementation is just not useful then.

But our programs must survive being executed on such a useless, but legal,
implementation.  I suspect most would not?  The fact that a trivial
implementation of a concept might exist means that our use of the concept
must cope with that implementation ... and if it can't, that renders
the concept (or at least our use of it) useless.

Tim noted:
> Who would benefit?
>
> Not JVM designers, since they would have to work around the possibility
> of spurious wakeups at the OS level, with a consequent cost in performance.

It's surely much better for the JVM to protect the Java system from broken
OS threading mechanisms.  Allowing the spurious wakeups through has an
effect of performance as well -- pulling the woken thread off the wait-set
and into the acquire-the-monitor-set, scheduling that woken thread,
executing its code to test (folornly) its while-condition, and finally
putting that woken thread back in the wait-set and scheduling another
thread.  That doesn't look too attractive.

Better: don't build your JVM on a broken threading mechanism ... it is
possible to have unbroken ones that don't do things when they shouldn't.

> Imagine what would happen if spurious wakeups were disallowed. First,
> programmers (those who never really bought into the idea that premature
> optimization is evil) would rush to turn this ... <description of
> while-wait-loop turned into if-wait>.

It sounds like you're threatening us with spurious wakeups just to make
us keep the while-wait-loop, :).

I would hope that - alongside converting while-wait-loop to if-wait -
they would look very carefully at the logic of their monitor methods
to ensure that the condition can't be unset between notification and
re-acquisition.  Getting that wrong is as bad as the spurious wakeup
and as costly for performance (perhaps infinitely so).  Of course,
the same duty must be imposed on maintainers of the system.

And, of course, this might be very difficult ... but that's a problem with
working with monitors ...  and, indeed, with most kinds of object locking.

Just seen ...

Brian wrote:
> Hoare monitors are a mathematical abstraction.  Spurious wakeups are
> permitted in recognition of the fact that real life is messy.  You can
> build an OS / thread package that NEVER delivers spurious wakeups, but
> there is a real engineering cost.  It is far more practical and
> efficient to allow the odd spurious wakeup.

Clean mathematical abstractions are *necessary* (though not sufficient)
for clean - and, hence, fast, simple and efficient - systems.  Hoare's
mathematical abstractions have proved pretty successful in guiding some
really spectacular engineering developments that deal with real messy
life.

It's the absence of clean mathematical abstractions that leads to real
engineering costs (that you mention).  I just don't believe that never
delivering a spurious wakeup should impose such a cost (assuming we're
not trying to guard against hardware corruption).

Peter (who must get back to his day job!).
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: spurious wakeups semantics

Joshua Bloch-2
I agree wholeheartedly with Tim's original statement.  As an
interesting aside, I have it on reasonably good authority that the
"spurious wakeup" clause was put into the spec because one of the spec
authors felt that it encourage good coding habits, along the lines
discussed by Tim.

         Josh

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: spurious wakeups semantics

Pete.Soper
In reply to this post by David Biesack
Hi David,

You wrote:

>>
>>Seeing the discussion on these spurious wakeups alarms (maybe depresses)
>>me, :( ...
>
>
> David Holmes' comments clarified the topic for me.

>(I think the Javadoc should be corrected so that it is clearer.)
>

This went on the "todo list" when David Holmes flagged it. It is Sun bug
6344935.

-Pete
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: spurious wakeups semantics

tpeierls
In reply to this post by P.H.Welch
P.H.Welch wrote:
>> [Tim:] Imagine what would happen if spurious wakeups were disallowed. First, programmers
>> (those who never really bought into the idea that premature optimization is evil) would rush
>> to turn this ... <description of while-wait-loop turned into if-wait>.
>
> It sounds like you're threatening us with spurious wakeups just to make us keep the
> while-wait-loop, :).

Whatever works! :-)


> I would hope that - alongside converting while-wait-loop to if-wait - they would look very
> carefully at the logic of their monitor methods to ensure that the condition can't be unset
> between notification and re-acquisition.

This asks too much of the programmer, and it precludes practical designs that don't fit the
theoretical ideal.

For example, until JDK 5.0, you were limited to one wait-set per monitor, so rechecking the
condition was sometimes essential even you disregarded the possibility of spurious wakeups.


> It's the absence of clean mathematical abstractions that leads to real engineering costs (that
> you mention).

There's also a cost if you pick an abstraction that is too restrictive or that doesn't map well to
engineering realities.


> I just don't believe that never delivering a spurious wakeup should impose such a cost
> (assuming we're not trying to guard against hardware corruption).

Let me turn that around: Is there a realistic example of a setting where the cost of a single
superfluous condition evaluation dominates the context switch overhead in an essential way?  If
not, then there is no reason to avoid the "while (!cond) wait()" pattern and thus no reason to
force JVM designers to do handstands to hide spurious wakeups from us.  (If there is such an
example, then there's more to debate.)

--tim

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: spurious wakeups semantics

Brian Goetz
In reply to this post by P.H.Welch
Your argument is mostly an "aesthetic" one, and you are contorting the
world to fit your sense of aesthetic.  Spurious wakeups were not
invented because we like ugliness; they were a real-world engineering
compromise.  I presume you posted here because you wanted to understand
the issue.  But using words like "broken" (incorrectly, I might add)
does little to enlist the aid of those here.

> Matthias and Tim both raise the defence for while-not-condition-wait-loops
> with the classical argument that something might have unset the waited-for
> condition between the notifyer setting it up and the waiter reacquiring
> the monitor.  Of course that may happen ... but only if the logic in the
> programmed system is sloppy (I used the term "lazy" last time).

BZZZT.

- This can happen whenever a single wait set is used for multiple
conditions.  Until Java 5, this was the _only_ way to get multiple
conditions on a single condition queue, and you still can't with
intrinsic condition queues.  So what should we do?  Outlaw bounded
buffers, and other concurrent objects which require more than one
condition?

- This can happen whenever notifyAll is used to wake up more than one
thread, even if all threads are waiting for the same condition.  There
are good engineering reasons why you might prefer notifyAll to single
notify.

These cases don't describe "sloppiness", they describe sensible
practices for common real-world problems.

>>A trivial implementation of a concept does not render the concept
>>nonsensical.  The implementation is just not useful then.
>
> But our programs must survive being executed on such a useless, but legal,
> implementation.  I suspect most would not?  The fact that a trivial
> implementation of a concept might exist means that our use of the concept
> must cope with that implementation ... and if it can't, that renders
> the concept (or at least our use of it) useless.

The standard idioms cope with that quite well.   Such an implementation
would just perform poorly.  Which is one reason why it would be a poor,
albeit valid, implementation.

   synchronized (lock) {
     while (!conditionPredicate())
        lock.wait();
   }

will work fine if wait() is simply an unlock^n-lock^n sequence.  And the
JLS requires it to release the lock as part of a wait, so the
unlock^n-lock^n cannot be optimized away.  See JLS/3e 17.8.1.  (You
might consider looking at the spec before making claims like "X would be
a valid implementation, but that would break real programs" when the
spec very clearly outlaws X.)

> It's surely much better for the JVM to protect the Java system from broken
> OS threading mechanisms.  

You have done nothing to support your claim of brokenness.  As far as I
can tell, all you've said is that you personally find it ugly.  You may
be right, but that doesn't mean its broken.

> Allowing the spurious wakeups through has an
> effect of performance as well -- pulling the woken thread off the wait-set
> and into the acquire-the-monitor-set, scheduling that woken thread,
> executing its code to test (folornly) its while-condition, and finally
> putting that woken thread back in the wait-set and scheduling another
> thread.  That doesn't look too attractive.

OS'es which permit spurious wakeups may do so because by doing so
because they can improve overall performance.  Again, I refer you to the
fair/nonfair issue with locks.  Sure, fairness is prettier, but
starvation-free nonfair locks can be implemented a lot more efficiently.
    To make a performance argument, you'd have to analyze the
performance costs of rewriting the OS as you suggest.

> I would hope that - alongside converting while-wait-loop to if-wait -
> they would look very carefully at the logic of their monitor methods
> to ensure that the condition can't be unset between notification and
> re-acquisition.  

I share your hopes, but I've met enough real programmers to know that
this is in the same category as hoping to wake up taller tomorrow.

> Clean mathematical abstractions are *necessary* (though not sufficient)
> for clean - and, hence, fast, simple and efficient - systems.  Hoare's
> mathematical abstractions have proved pretty successful in guiding some
> really spectacular engineering developments that deal with real messy
> life.

Except that a monitor-based design for a system of even moderate
complexity will almost certainly deadlock.  This is (one reason) why the
monitor-like approach that Java uses was taken over "real" monitors.

> It's the absence of clean mathematical abstractions that leads to real
> engineering costs (that you mention).  I just don't believe that never
> delivering a spurious wakeup should impose such a cost (assuming we're
> not trying to guard against hardware corruption).

This one I buy.  But the abstractions need to be consistent with the
reality of hardware and OSs of the day.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: spurious wakeups semantics

Doug Lea
In reply to this post by P.H.Welch
Hi Peter,

It's nice (honestly!) to get your usual balance on the perennial
spurious wakeup issue.

A couple of notes on it:

1. As it turns out, the current implementation
locks.ReentrantLock.Condition.await() do not spuriously
wake up. We don't document or promise this though, for the kinds
of reasons Tim and Josh mentioned.

2. Conversely though, the underlying "primitive" operation
locks.LockSupport.park() is intentionally(!) very "leaky"
and will sometimes fail to block at all. Notice that if threads do
spuriously wake up on modern OSes, then it performance-neutral whether
the OS or the monitor implementation or application code puts
them back to sleep when necessary. However, because
blocking threads on modern multiprocessors and their operating
systems are relatively much more expensive in throughput cost
than, say, the uniprocessors of a decade ago, opportunistically
trying to proceed when you are awake anyway is often faster.

3. We hope that people will increasingly use the more convenient,
semantically cleaner,  and often significantly more efficient
medium/higher level constructs that java.util.concurrent offers
rather use monitor/condition operations at all. In fact, whenever people
post on this list that they are using them, I often wonder to myself
what higher-level construct we might put in j.u.c. that they could use
instead.

-Doug
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: spurious wakeups semantics

Remi Forax
In reply to this post by Brian Goetz
Brian Goetz a écrit :
...

>
> - This can happen whenever a single wait set is used for multiple
> conditions.  Until Java 5, this was the _only_ way to get multiple
> conditions on a single condition queue, and you still can't with
> intrinsic condition queues.  So what should we do?  Outlaw bounded
> buffers, and other concurrent objects which require more than one
> condition?
>
> - This can happen whenever notifyAll is used to wake up more than one
> thread, even if all threads are waiting for the same condition.  There
> are good engineering reasons why you might prefer notifyAll to single
> notify.

what are these good engineering reasons ?
and are these reasons can be applied to Condition.signal/signalAll too
in case of fair Lock ?

>
> These cases don't describe "sloppiness", they describe sensible
> practices for common real-world problems.

...

> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest

Rémi Forax

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: spurious wakeups semantics

Brian Goetz
>> - This can happen whenever notifyAll is used to wake up more than one
>> thread, even if all threads are waiting for the same condition.  There
>> are good engineering reasons why you might prefer notifyAll to single
>> notify.
>
> what are these good engineering reasons ?
> and are these reasons can be applied to Condition.signal/signalAll too
> in case of fair Lock ?

In order for a design to be a candidate for notify() instead of
notifyAll(), three conditions need to hold:

  - Uniform waiters.  All waiters must be waiting for the same
condition.  This rules out a bounded buffer design which uses an
intrinsic condition queue, because there are separate "notEmpty" and
"notFull" conditions.

  - One in, one-out.  A notification must release exactly one waiter.
This rules out blocking classes like latches and barriers, which must
use notifyAll().

  - Subclass safety.  This one is a little trickier.  The class must be
structured so that if the class is subclassed, the above requirements
still hold.  It is very difficult to design a blocking class so that it
can be subclassed arbitrarily.


Any class which uses an intrinsic condition queue / lock object and the
queue/lock object is not hidden cannot meet the first requirement,
because any old code could wait() on the condition queue and violate the
uniform waiters requirement.  So the monitor-like pattern encouraged by
Java does not play nicely with single notify.


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: spurious wakeups semantics

Dawid Kurzyniec
In reply to this post by Doug Lea
Doug Lea wrote:

> Hi Peter,
>
> It's nice (honestly!) to get your usual balance on the perennial
> spurious wakeup issue.
>
> A couple of notes on it:
>
> 1. As it turns out, the current implementation
> locks.ReentrantLock.Condition.await() do not spuriously
> wake up. We don't document or promise this though, for the kinds
> of reasons Tim and Josh mentioned.
>
In the 1.4 backport, spurious wakeups are possible when using unfair
conditions, and in fact I have seen them happening (on MS Windows). They
won't occur when using fair conditions, although - as Doug says - this
is undocumented and not promised to hold in the future.

Regards,
Dawid Kurzyniec

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
12