code review 4524083: sync: wake up current goroutine on Cond.Signal if waiters=0

sync: always wake up previously sleeping goroutines on Cond.Signal

This changes the internal implementation of Cond so that
it uses two generations of waiters.  This enables Signal
to guarantee that it will only wake up waiters that are
currently sleeping at the call time.

Fixes issue 1648.

[niemeyer, 2011-05-31 13:33:02]

Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://go.googlecode.com/hg/

[dvyukov, 2011-05-31 13:49:12]

On 2011/05/31 13:33:02, niemeyer wrote:
> Hello mailto:golang-dev@googlegroups.com (cc:
mailto:golang-dev@googlegroups.com),
> 
> I'd like you to review this change to
> https://go.googlecode.com/hg/

I don't think it's that simple. If there are 2 waiters, signal must wake one of
these waiters. It's still possible that a new waiter from the next wait
generation will consume the signal.

[gustavo_niemeyer.net, 2011-05-31 13:56:49]

> I don't think it's that simple. If there are 2 waiters, signal must wake
> one of these waiters. It's still possible that a new waiter from the
> next wait generation will consume the signal.

It is that simple to fix the reported issue.  If we want to make sure
that Signal() _never_ picks a goroutine which is not yet asleep at the
precise time it's called, then we have to do more work.

-- 
Gustavo Niemeyer
http://niemeyer.net
http://niemeyer.net/blog
http://niemeyer.net/twitter

[gustavo_niemeyer.net, 2011-05-31 14:27:41]

> It is that simple to fix the reported issue.  If we want to make sure
> that Signal() _never_ picks a goroutine which is not yet asleep at the
> precise time it's called, then we have to do more work.

Hmmm, I think I can increase the guarantees without creeping up the
design.  Give me a moment.

-- 
Gustavo Niemeyer
http://niemeyer.net
http://niemeyer.net/blog
http://niemeyer.net/twitter

[niemeyer, 2011-05-31 15:22:13]

> Hmmm, I think I can increase the guarantees without creeping up the
> design.  Give me a moment.

Alright, changed the design so it uses two generations of waiters
so that Signal can guarantee the same properties of Broadcast.

Please take another look and let me know what you think.

[dvyukov, 2011-06-01 15:05:48]

On 2011/05/31 15:22:13, niemeyer wrote:
> > Hmmm, I think I can increase the guarantees without creeping up the
> > design.  Give me a moment.
> 
> Alright, changed the design so it uses two generations of waiters
> so that Signal can guarantee the same properties of Broadcast.
> 
> Please take another look and let me know what you think.

The algorithm looks good to me. I am pretty sure it's correct. I think it won't
do for full-fledged POSIX-compatible implementation with regard to
SCHED_RR/SCHED_FIFO and priorities... fortunately it's irrelevant for us.
But the test seems to not test what it must test. As far as I see, there is only
1 goroutine waiting on the cv during signal() call. As a dumb test I replaced
signal() with broadcast() and it does not break the test, however it should if
there were at least 2 threads waiting. Also, wait() call not surrounded with a
predicate-checking loop looks quite suspicious, and I am unable to figure out
from the documentation as to whether it's guaranteed to work or not (I mean
spurious wakeups here). I think it's better to introduce some predicate and a
loop, condvar is not a semaphore, it has no state and should not be used that
way. The rule of thumb for condvars is that wait can be replaced with
unlock/lock and signal/wait with no-op, and a program should stay correct.

[gustavo_niemeyer.net, 2011-06-01 16:35:12]

> The algorithm looks good to me. I am pretty sure it's correct. I think
> it won't do for full-fledged POSIX-compatible implementation with regard
> to SCHED_RR/SCHED_FIFO and priorities... fortunately it's irrelevant for
> us.

Nice, that's good to hear.

> But the test seems to not test what it must test. As far as I see, there
> is only 1 goroutine waiting on the cv during signal() call. As a dumb
> test I replaced signal() with broadcast() and it does not break the
> test, however it should if there were at least 2 threads waiting. Also,

There are two goroutines waiting:

A) Start for loop
B) Start first goroutine
C) Wait for it to be running
D) Wait for it to release lock
E) Signal, unlock, and loop
F) Start second goroutine

If you want to see the test breaking, copy & paste it as-is in the
current tip and run it with GOMAXPROCS=4.

> wait() call not surrounded with a predicate-checking loop looks quite
> suspicious, and I am unable to figure out from the documentation as to
> whether it's guaranteed to work or not (I mean spurious wakeups here). I
> think it's better to introduce some predicate and a loop, condvar is not
> a semaphore, it has no state and should not be used that way. The rule
> of thumb for condvars is that wait can be replaced with unlock/lock and
> signal/wait with no-op, and a program should stay correct.

There are no spurious wakeups in Cond, and the test case is a concise
exploitation of an aspect of Cond.  If this test breaks I'd consider
Cond to be buggy, which is the intent, rather than being a best
practices recommendation.

Thanks a lot for the review and feedback Dmitriy.  It's truly appreciated.

-- 
Gustavo Niemeyer
http://niemeyer.net
http://niemeyer.net/blog
http://niemeyer.net/twitter

[dvyukov, 2011-06-01 16:46:00]

On 2011/06/01 16:35:12, gustavo_niemeyer.net wrote:
> > The algorithm looks good to me. I am pretty sure it's correct. I think
> > it won't do for full-fledged POSIX-compatible implementation with regard
> > to SCHED_RR/SCHED_FIFO and priorities... fortunately it's irrelevant for
> > us.
> 
> Nice, that's good to hear.
> 
> > But the test seems to not test what it must test. As far as I see, there
> > is only 1 goroutine waiting on the cv during signal() call. As a dumb
> > test I replaced signal() with broadcast() and it does not break the
> > test, however it should if there were at least 2 threads waiting. Also,
> 
> There are two goroutines waiting:
> 
> A) Start for loop
> B) Start first goroutine
> C) Wait for it to be running
> D) Wait for it to release lock
> E) Signal, unlock, and loop
> F) Start second goroutine
> 
> If you want to see the test breaking, copy & paste it as-is in the
> current tip and run it with GOMAXPROCS=4.

Yes, your right. I was thinking about something else. I was thinking about a
test where 2 goroutines are waiting and there is also another goroutine (or two)
that is 'not yet waiting' (but may consume the signal), and we do signal() and
want to wake up one of these 2 gorotuines.


> > wait() call not surrounded with a predicate-checking loop looks quite
> > suspicious, and I am unable to figure out from the documentation as to
> > whether it's guaranteed to work or not (I mean spurious wakeups here). I
> > think it's better to introduce some predicate and a loop, condvar is not
> > a semaphore, it has no state and should not be used that way. The rule
> > of thumb for condvars is that wait can be replaced with unlock/lock and
> > signal/wait with no-op, and a program should stay correct.
> 
> There are no spurious wakeups in Cond, and the test case is a concise
> exploitation of an aspect of Cond.  If this test breaks I'd consider
> Cond to be buggy, which is the intent, rather than being a best
> practices recommendation.

From this point of view it's OK. It's even good because we will get to know if
condvar starts producing spurious wakeups.


> Thanks a lot for the review and feedback Dmitriy.  It's truly appreciated.

No problem.
Actually I wanted to fix it myself, I had no complete solution but potentially
my solution would be more complicated.



So LGTM on my side.

[niemeyer, 2011-06-01 16:49:25]

> So LGTM on my side.

Thanks.

Russ/Rob, can one of you please have a look at this as well?

[rsc, 2011-06-01 19:10:44]

LGTM

Nice code.

http://codereview.appspot.com/4524083/diff/5/src/pkg/sync/cond.go
File src/pkg/sync/cond.go (right):

http://codereview.appspot.com/4524083/diff/5/src/pkg/sync/cond.go#newcode19
src/pkg/sync/cond.go:19: oldwaiters int     // number of goroutines blocked on
Wait for oldsema
more comments please:

// We must be careful to make sure that when Signal
// releases a semaphore, the corresponding acquire is
// executed by a goroutine that was already waiting at
// the time of the call to Signal, not one that arrived later.
// To ensure this, we segment waiting goroutines into
// generations punctuated by calls to Signal.  Each call to
// Signal begins another generation if there are no goroutines
// left in older generations for it to wake.  Because of this
// optimization (only begin another generation if there is
// are no older goroutines left), we only need to keep track
// of the two most recent generations, which we call old
// and new.
oldWaiters int  // waiters in old generation...
oldSema *uint32  // ... waiting on this semaphore

newWaiters int  // number of waiters in new generation...
newSema *uint32  /// ... waiting on this semaphore

http://codereview.appspot.com/4524083/diff/5/src/pkg/sync/cond.go#newcode65
src/pkg/sync/cond.go:65: // Swap generations.
not really a swap
// Retire old generation; rename new to old.

http://codereview.appspot.com/4524083/diff/5/src/pkg/sync/cond.go#newcode84
src/pkg/sync/cond.go:84: if c.oldwaiters > 0 || c.newwaiters > 0 {
split into two; c.oldWaiters > 0 does not imply 
that we need to delete newSema.

// Wake both generations.
if c.oldWaiters > 0 {
    for ...
    c.oldWaiters = 0
}
if c.newWaiters > 0 {
    for ...
    c.newWaiters = 0
    c.newSema = nil
}

[niemeyer, 2011-06-01 23:30:54]

*** Submitted as http://code.google.com/p/go/source/detail?r=dc4142625e5f ***

sync: always wake up previously sleeping goroutines on Cond.Signal

This changes the internal implementation of Cond so that
it uses two generations of waiters.  This enables Signal
to guarantee that it will only wake up waiters that are
currently sleeping at the call time.

Fixes issue 1648.

R=dvyukov, gustavo, rsc
CC=golang-dev
http://codereview.appspot.com/4524083