FAQ
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.

--
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+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Search Discussions

  • Dave Cheney at Jan 31, 2015 at 8:53 am
    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

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Enormouspenguin at Jan 31, 2015 at 4:42 pm
    You confirmed my doubt. But why would one want to use something that is not
    fair? Isn't starvation considered bad in concurrent programming?
    On Saturday, January 31, 2015 at 3:53:41 PM UTC+7, Dave Cheney wrote:

    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
    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Rob Pike at Jan 31, 2015 at 6:57 pm
    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

    On Sat, Jan 31, 2015 at 8:42 AM, enormouspenguin wrote:

    You confirmed my doubt. But why would one want to use something that is
    not fair? Isn't starvation considered bad in concurrent programming?
    On Saturday, January 31, 2015 at 3:53:41 PM UTC+7, Dave Cheney wrote:

    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
    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Enormouspenguin at Feb 1, 2015 at 5:09 am
    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.

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Andrey mirtchovski at Feb 1, 2015 at 5:24 am
    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 ... {}

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Enormouspenguin at Feb 1, 2015 at 11:07 am
    Are you serious (or just plain mocking me)?
    On Sunday, February 1, 2015 at 12:24:16 PM UTC+7, andrey mirtchovski wrote:

    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 ... {}
    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Thwd at Feb 1, 2015 at 2:07 pm

    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

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Matthew Kane at Feb 1, 2015 at 2:26 pm
    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.
    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

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Jesper Louis Andersen at Feb 1, 2015 at 3:44 pm

    On Sun, Feb 1, 2015 at 6:09 AM, enormouspenguin 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.

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Andrewchamberss at Feb 1, 2015 at 9:58 pm
    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).
    On Sunday, February 1, 2015 at 6:09:39 PM UTC+13, enormouspenguin wrote:

    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.
    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Enormouspenguin at Feb 2, 2015 at 4:24 am
    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.

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Dave Cheney at Feb 2, 2015 at 8:12 am
    I recommend starting with select {} now, and iff it becomes a problem,
    worry about a workaround then.
    On Monday, 2 February 2015 15:24:29 UTC+11, enormouspenguin wrote:

    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.
    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Ian Lance Taylor at Feb 2, 2015 at 9:59 pm

    On Sat, Jan 31, 2015 at 9:09 PM, enormouspenguin 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

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • John Souvestre at Feb 3, 2015 at 10:00 am
    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

    -----Original Message-----
    From: golang-nuts@googlegroups.com On Behalf Of Ian Lance Taylor
    Sent: 2015 February 02, Mon 16:00
    To: enormouspenguin
    Cc: golang-nuts
    Subject: Re: [go-nuts] Re: SELECT statement: Is channel starvation possible?
    On Sat, Jan 31, 2015 at 9:09 PM, enormouspenguin 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

    --
    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+unsubscribe@googlegroups.com.

    For more options, visit https://groups.google.com/d/optout.

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Jan Mercl at Feb 3, 2015 at 10:24 am

    On Tue Feb 03 2015 at 11:00:52 John Souvestre 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

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • John Souvestre at Feb 3, 2015 at 10:44 am
    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



    From: Jan Mercl
    Sent: 2015 February 03, Tue 04:25
    To: John Souvestre; golang-nuts@googlegroups.com
    Subject: Re: FW: [go-nuts] Re: SELECT statement: Is channel starvation possible?


    On Tue Feb 03 2015 at 11:00:52 John Souvestre 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



    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Ian Lance Taylor at Feb 3, 2015 at 1:39 pm

    On Tue, Feb 3, 2015 at 2:00 AM, John Souvestre 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

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-nuts @
categoriesgo
postedJan 31, '15 at 8:17a
activeFeb 3, '15 at 1:39p
posts18
users11
websitegolang.org

People

Translate

site design / logo © 2022 Grokbase