SELECT statement: Is channel starvation possible?

[enormouspenguin]

I know that SELECT pseudo-randomly select a channel among ready channels to proceed. But could it be that starvation happen when a channel compete with large enough number of other channels in the same SELECT statement? What I really want to know is the mechanic (or algorithm) behind that makes SELECT statement starvation possible or not.

[Dave Cheney]

Starvation is possible, but in practice unlikely.

On Saturday, 31 January 2015 19:17:51 UTC+11, enormouspenguin wrote:

I know that SELECT pseudo-randomly select a channel among ready channels to proceed. But could it be that starvation happen when a channel compete with large enough number of other channels in the same SELECT statement? What I really want to know is the mechanic (or algorithm) behind that makes SELECT statement starvation possible or not.

Use the source, luke: https://github.com/golang/go/blob/master/src/runtime/select.go#L222 

[enormouspenguin]

You confirmed my doubt. But why would one want to use something that is not fair? Isn't starvation considered bad in concurrent programming?

[Rob Pike]

It is fair. Starvation is only possible for finite time. As with any uniform statistical process, eventually it averages out.

All other things being equal (which they never are, but ignore that), if multiple communications are ready in a select, the choice of which one proceeds is made by a fair pseudorandom coin toss.

Starvation doesn't happen. Don't worry about it.

-rob

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[enormouspenguin]

Starvation doesn't happen. Don't worry about it.

It's a relief to hear the guarantee comes from the famous creator of Go. But I still have some thoughts I want to share and questions in need of answers.

I think finite time is enough to make result stale in real-time programs. Though not the entire time, but aren't intermittent failures the thing we always want to avoid? Base the correctness of programs on probability is a risky choice, don't you think?

May I ask what is the original purposes of making SELECT pseudo-randomly choose between ready channels each time it's entered? Is it to distract programmers from over-ordering cases?

Come to think of it, why not introduce 2 different kinds of SELECT:

+ The first is normal SELECT like we have today. This kind of SELECT is not recommended to be used inside a tight loop because it enhances the chance of channel starvation.

+ The second is loop (or starve-free) SELECT: a SELECT that tightly coupled with a loop (FOR loop). Or it could be a combination of both (SELECT and FOR therefore form a new statement, for example FORLECT). FORLECT pseudo-randomly shuffle cases list only when it is entered. On subsequent iterations, choices is based on priority of the shuffled cases list. But the list is not static, it will be cycled (i.e increase head pointer by 1 element, wrap around at the end like a ring) after each choice. If my reasoning is correct, that strategy will ensure fairness.

Some newbie boring thoughts on a big subject. Thanks in advanced for taking the time to read it.

[andrey mirtchovski]

how about giving the programmer several possible evaluation options
instead of just two? some ideas how SELECT may choose amongst the
available channels:

- fair pseudorandom
- unfair pseudorandom
- top-down orderly
- bottom-up disorderly
- priority based

and rather than introducing different reserved keywords we can use
non-reserved modifiers for SELECT, for example we can do SELECT FAIR
{}, SELECT UNFAIR {}, SELECT TOPSDOWN {}, SELECT BOTTOMSUP{}, etc.

we'll stop when we reach SELECT ... FROM ... WHERE ... ORDER BY ... {}

[enormouspenguin]

Are you serious (or just plain mocking me)?

[thwd]

On Sunday, February 1, 2015 at 6:09:39 AM UTC+1, enormouspenguin wrote:

Come to think of it, why not introduce 2 different kinds of SELECT:

[...]

Some newbie boring thoughts on a big subject. Thanks in advanced for taking the time to read it.

The formal reason is the Go 1 guarantee. If you haven't read it I invite you to do so [1].

Beyond that, if the bug remains purely theoretical then it is of no priority. One of the foremost priorities, however, is maintaining the simple design of the language.

- Tom

[1] http://golang.org/doc/go1compat

[Matthew Kane]

Adding a new select via keyword or API wouldn't break the guarantee if it wouldn't break old source code.

Sent from my mobile.

--

[Jesper Louis Andersen]

On Sun, Feb 1, 2015 at 6:09 AM, enormouspenguin <kimkh...@gmail.com> wrote:

I think finite time is enough to make result stale in real-time programs. Though not the entire time, but aren't intermittent failures the thing we always want to avoid? Base the correctness of programs on probability is a risky choice, don't you think?

While it may sound risky, this mailing list suggests it is not. There are far more problems with other parts of the Go system, most notably GC interaction. In turn, it is more important to fix the problems there than it is to solve a problem which only exists in theory at the time being.

For process starvation, there are a number of different strategies: round robin, credit oriented, stochastic, and naive are some of them. In practice, stochastic solutions strike a good balance between being fast and being correct.

May I ask what is the original purposes of making SELECT pseudo-randomly choose between ready channels each time it's entered? Is it to distract programmers from over-ordering cases?

In Go, the select construction is a statement, not an expression. Hence, the order in which you process channel communication is static in the program and can't be altered by code, unless you write several variants of the same select expression yourself. If there were a pre-determined order, say first match wins, then starvation is a real problem in real-world programs.

So the programmer who orders the cases in order to obtain a "faster" flow might very well see a starvation problem, had it not been for the random selection of channel order. It is worse in reality: for some selects, it turns out there is no satisfactory order among channels and any choice risks starving one channel. Here, the only correct solution is to force channels into fair selection. And the reasonable way to do that is with random choice, which has proven to be a good choice in practice.

In Haskell, one of the many concurrency primitives is the 'STM' Monad for software transactions. Here, select can be implemented as an expression and the code can then decide to reorder statements for each invocation. The code can simply program the ordering scheme as you see fit. On one hand, this yields explicit control of the selection process, which leads to better performance. On the other hand, it risks the subtle introduction of starvation errors in code.

Concurrent ML also allows for programmable event trees, but Concurrent ML defines selection to be a fair choice among the possible events like in Go. Because it is so much simpler to work with in practice, rather than worrying about selection order. Furthermore, Concurrent ML allows you to build trees of select events with negative acknowledgements. And once you get to such complicated event models, you *need* fair choice. It is impossible to figure out what happens, had it not been for the guarantee of fair selection.

This final remark is the key observation: fair choice among several channels is a guarantee which simplifies the mental cognitive load for the programmer. You don't have to worry about the order in which you put channels in a select statement, simplifying the expression considerably.

--

J.

[andrewc...@gmail.com]

I thought the point of select statements is that there is no happens before guarantee, the order the receive happens, is the order the go code perceives events to have happened.

Adding any sort of guarantee of ordering is against the idea of the select statement (to serialize events that all happen at the same logical time).

[enormouspenguin]

Looks like I have gone way too deep in theory to forget about reality. So the general points are:

+ Starvation is highly unlikely to happen in reality

+ Adding more will break even more (design, philosophy, beauty, practical, ...)

I think I am going to settle with accepting it and find some workaround if I need a fair SELECT, for now.

[Dave Cheney]

I recommend starting with select {} now, and iff it becomes a problem, worry about a workaround then.

[Ian Lance Taylor]

On Sat, Jan 31, 2015 at 9:09 PM, enormouspenguin <kimkh...@gmail.com> wrote:
>
> I think finite time is enough to make result stale in real-time programs.
> Though not the entire time, but aren't intermittent failures the thing we
> always want to avoid? Base the correctness of programs on probability is a
> risky choice, don't you think?

I see that this question has already been resolved, but I wanted to
make a different comment. Go is for programs that run in the real
world. In the real world, program correctness is always based on
probability. There is a small but real probability that the machine
will have a hardware error that will cause it to execute something
completely unexpected. While this probability is small, it's real
enough that programs run on large server farms need to consider it.

So in the real world all that is necessary for the Go language and
implementation is to make the probability of starvation due to
unfortunate choices in select be a few orders of magnitude lower than
the probability of program error due to hardware failure.

I think that if you look at real numbers you will see that that is
achieved when using a uniform pseudo-random choice.

Ian

[John Souvestre]

Hello Ian.

I read your comment and I am confused.  Was your response meant to include the original premise of a real-time program?

If so, I think that the most common error isn't hardware failure but  missing a timing deadline.  I've worked on systems where accuracy of 0.1 microseconds was required.  Even human interfaces require sub-second response times. 

 > Go is for programs that run in the real world.

What programs don't?  Certainly real-time programs do.  Errors due to probabilistic scheduling increase as the response requirement approaches the speed of the system.

I realize that Go isn't designed for tight real-time requirements.  It currently does well in average cases.  With scheduling (preemption and forced rescheduling) and GC improvements (past and planned) is getting "faster".  I think this is wonderful.  It will make coding more possible for gamers and drone controllers, for example.

In one of my programs I used multiple selects in a "waterfall" arrangement to achieve a priority effect.  Yes, it would have been nice had Select offered some sort of priority scheduling, but since it didn't I worked around it.

 >>> I think that if you look at real numbers you will see that that is
achieved when using a uniform pseudo-random choice.

If a task needs to run once a second, yes.  Once a millisecond, probably (except for GC and for compute-bound GoRoutines which don't force rescheduling).  Once a microsecond, no.

John

    John Souvestre - New Orleans LA

--

You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

[Jan Mercl]

On Tue Feb 03 2015 at 11:00:52 John Souvestre <jo...@sstar.com> wrote:

> Yes, it would have been nice had Select offered some sort of priority

> scheduling, but since it didn't I worked around it.

http://play.golang.org/p/0zpXnO_QWC

-j

[John Souvestre]

Hi Jan.

 

Nice!  It certainly changes the odds, but still isn’t quite as deterministic as if channels had different priorities.

 

John

    John Souvestre - New Orleans LA

 

[Ian Lance Taylor]

On Tue, Feb 3, 2015 at 2:00 AM, John Souvestre <jo...@sstar.com> wrote:
>
> I read your comment and I am confused. Was your response meant to include
> the original premise of a real-time program?

I didn't, and don't, see that in the original note on this thread.

> In one of my programs I used multiple selects in a "waterfall" arrangement
> to achieve a priority effect. Yes, it would have been nice had Select
> offered some sort of priority scheduling, but since it didn't I worked
> around it.

Yes, if you have channels that are almost always ready, and you also
need hard real-time deadlines, that is what you must do. As you say,
the only way to avoid this would be strict channel priorities. That
is an issue different from what the first message on this thread was
talking about, which is the possibility of starvation when several
channels are almost always ready. In a hard real-time system things
like round robin scheduling of select statements are not good enough.
You must have channel priorities. As you say, in Go, this can only be
implemented by nested select statements.

Ian