code review 53080043: runtime: ensure fair scheduling during frequent GCs

runtime: ensure fair scheduling during frequent GCs
What was happenning is as follows:
Each writer goroutine always triggers GC during its scheduling quntum.
After GC goroutines are shuffled so that the timer goroutine is always second in the queue.
This repeats infinitely, causing timer goroutine starvation.
Fixes issue 7126.

[dvyukov, 2014-01-16 08:34:00]

Hello golang-codereviews@googlegroups.com,

I'd like you to review this change to
https://dvyukov%40google.com@code.google.com/p/go/

[shanemhansen, 2014-01-16 16:44:57]

On 2014/01/16 08:34:00, dvyukov wrote:
> Hello mailto:golang-codereviews@googlegroups.com,
> 
> I'd like you to review this change to
> https://dvyukov%2540google.com%40code.google.com/p/go/

I can verify the code fixes the goroutine starvation problems w/ GOMAXPROCS=1
(7126). Yay!

[dvyukov, 2014-01-17 10:53:20]

On Thu, Jan 16, 2014 at 8:44 PM,  <shanemhansen@gmail.com> wrote:
> On 2014/01/16 08:34:00, dvyukov wrote:
>>
>> Hello mailto:golang-codereviews@googlegroups.com,
>
>
>> I'd like you to review this change to
>> https://dvyukov%2540google.com%40code.google.com/p/go/
>
>
> I can verify the code fixes the goroutine starvation problems w/
> GOMAXPROCS=1 (7126). Yay!


Thanks for checking!

[khr, 2014-01-18 00:40:45]

https://codereview.appspot.com/53080043/diff/60001/src/pkg/runtime/proc.c
File src/pkg/runtime/proc.c (right):

https://codereview.appspot.com/53080043/diff/60001/src/pkg/runtime/proc.c#new...
src/pkg/runtime/proc.c:2223: // collect all runnable goroutines in global queue
preserving FIFO order
You're interleaving the work lists, doing p[0][0], p[1][0], ... p[P-1][0],
p[0][1], ...

Why not just concatenate the lists instead?  Do p[0][0], p[0][1], ...,
p[0][L-1], p[1][0], ...  It would be cheaper to construct and still FIFO (per
processor).

[dvyukov, 2014-01-18 12:55:28]

On Sat, Jan 18, 2014 at 4:40 AM,  <khr@golang.org> wrote:
>
> https://codereview.appspot.com/53080043/diff/60001/src/pkg/runtime/proc.c
> File src/pkg/runtime/proc.c (right):
>
>
https://codereview.appspot.com/53080043/diff/60001/src/pkg/runtime/proc.c#new...
> src/pkg/runtime/proc.c:2223: // collect all runnable goroutines in
>
> global queue preserving FIFO order
> You're interleaving the work lists, doing p[0][0], p[1][0], ...
> p[P-1][0], p[0][1], ...
>
> Why not just concatenate the lists instead?  Do p[0][0], p[0][1], ...,
> p[0][L-1], p[1][0], ...  It would be cheaper to construct and still FIFO
> (per processor).


Initially I though that it's not important at all.
There were several issue related to fairness since I've eliminated
single shared FIFO queue.
This issue says that this place is also important. So I've tried to
make "as FIFO as possible", so to say. To not do another fix soon.

I can imagine a case when a goroutine will starve under your scheme.
Consider that we have 10 goroutines on P[0] and 1 goroutine on P[1]
(let's call it X, and it will starve) during rebalancing. Under your
scheme X will be at the end of P[1] queue after rebalancing.
Then goroutines on P[0] spawn more goroutines that are added to the
end of P[0] queue.
Then, during next rebalancing we again can have 10 goroutines on P[0],
and one of few goroutines on P[1] (including X). Then again goroutines
from P[0] postpone X. And so on.
I.e. provided frequent periodic GCs, goroutines on P[0] will have
persistent priority gain over goroutines on P[1]. If goroutines spawn
new goroutines, this can lead to starvation.

Of course, with GOMAXPROCS>1 starvation is much less likely, because
of some degree of non-determinism. But I believe that it's possible to
write a program that consistently hits goroutine starvation under your
scheme.

Well, actually my scheme is also not bullet-prof, because goroutines
on a queue with more goroutines have higher priority. Fixing this will
require inserting goroutines into middle of the global runq.

[khr1, 2014-01-18 17:55:46]

LGTM.

This change sounds fine.  But maybe at some point we need to sort waiting
goroutines in reverse order by last run time.


On Sat, Jan 18, 2014 at 4:55 AM, Dmitry Vyukov <dvyukov@google.com> wrote:

> On Sat, Jan 18, 2014 at 4:40 AM,  <khr@golang.org> wrote:
> >
> >
> https://codereview.appspot.com/53080043/diff/60001/src/pkg/runtime/proc.c
> > File src/pkg/runtime/proc.c (right):
> >
> >
>
https://codereview.appspot.com/53080043/diff/60001/src/pkg/runtime/proc.c#new...
> > src/pkg/runtime/proc.c:2223: // collect all runnable goroutines in
> >
> > global queue preserving FIFO order
> > You're interleaving the work lists, doing p[0][0], p[1][0], ...
> > p[P-1][0], p[0][1], ...
> >
> > Why not just concatenate the lists instead?  Do p[0][0], p[0][1], ...,
> > p[0][L-1], p[1][0], ...  It would be cheaper to construct and still FIFO
> > (per processor).
>
>
> Initially I though that it's not important at all.
> There were several issue related to fairness since I've eliminated
> single shared FIFO queue.
> This issue says that this place is also important. So I've tried to
> make "as FIFO as possible", so to say. To not do another fix soon.
>
> I can imagine a case when a goroutine will starve under your scheme.
> Consider that we have 10 goroutines on P[0] and 1 goroutine on P[1]
> (let's call it X, and it will starve) during rebalancing. Under your
> scheme X will be at the end of P[1] queue after rebalancing.
> Then goroutines on P[0] spawn more goroutines that are added to the
> end of P[0] queue.
> Then, during next rebalancing we again can have 10 goroutines on P[0],
> and one of few goroutines on P[1] (including X). Then again goroutines
> from P[0] postpone X. And so on.
> I.e. provided frequent periodic GCs, goroutines on P[0] will have
> persistent priority gain over goroutines on P[1]. If goroutines spawn
> new goroutines, this can lead to starvation.
>
> Of course, with GOMAXPROCS>1 starvation is much less likely, because
> of some degree of non-determinism. But I believe that it's possible to
> write a program that consistently hits goroutine starvation under your
> scheme.
>
> Well, actually my scheme is also not bullet-prof, because goroutines
> on a queue with more goroutines have higher priority. Fixing this will
> require inserting goroutines into middle of the global runq.
>

[dvyukov, 2014-01-21 06:25:00]

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

runtime: ensure fair scheduling during frequent GCs
What was happenning is as follows:
Each writer goroutine always triggers GC during its scheduling quntum.
After GC goroutines are shuffled so that the timer goroutine is always second in
the queue.
This repeats infinitely, causing timer goroutine starvation.
Fixes issue 7126.

R=golang-codereviews, shanemhansen, khr, khr
CC=golang-codereviews
https://codereview.appspot.com/53080043