On Fri, Apr 30, 2021 at 9:53 AM Øyvind Teig <oyvind.t...@teigfam.net> wrote:
> If there is no notion of simultaneity why all the effort to describe the
> random distribution?
>
While it's not possible for two cases to become ready at the same time,
it's definitely possible for two cases to be ready when entering a select.
That's where the random selection comes in.
There's also the notable difference between a select with a default and one
without. A select with a default never blocks, so which branch is taken is
*only* determined by what's ready when entering the select, whereas a
select without can block and then gets woken up by the first communication
that's ready - and there'll always be a "first".
In a sense, the nested select uses that: The outer select handles the
"what's currently ready" case and the inner select handles the "what
becomes ready in the future".
The priority select would use the same basic logic:
- Is the high priority case ready? If so, do that
- If not, block until one of the cases become ready - do the first that
becomes ready
The crux here is exactly that we can't have two cases "becoming ready" at
the same time, so we really *have* to "take the first one that becomes
ready".
The select is first set up, at which time the code decides on which one to
> take if more than one guard is ready. If the clients were only sending,
> then nowhere in the system is this noted on "the other" side of the channel
> (in the server) before it enters the select. The channel would have noted
> the first contender, yes, but the servre have yet no idea. If none is
> ready, then the server was first on all the ends, and when a sender arrives
> it will match the guard set in the server and tear down the select. In due
> time the server is scheduled with that one event.
>
> This is how I have seen it in several systems. I wonder what might be so
> different with go.
>
I don't think I understand this exposition. But on first glance, your
description doesn't sound terribly different from what's happening in Go.
To be clear: No one is claiming it would be impossible to implement a
priority select in Go. Obviously we could replace the pseudo-random choice
by something else. We are just saying that it would be equivalent to the
nested select code.
Ok, so this is a pattern that Go people would use if they needed to do pri
> select. Then, why go to the lengths of the other code shown above? Is it
> because I have kind of "pressed" you to come up with code and then of
> course, one thing may be solved several ways?
>
I think the first code you where shown by Jan (which is the same as Ian's)
is correct and I believe it's likely that your insistence that it isn't is
what prompted people to come up with more and more complicated code.
Will your Go code examples stand the test of formal verification? Of
> course, when it's not formally verified you probaby could not answer such a
> question. But the stomach feeling?
>
I'm not very familiar with formal methods for this, or what the invariant
is that would be verified.
I do feel quite confident about the statement that the shown snippet is
equivalent to how I'd think a priority select would work.
Another angle: Go does not have the expression before the select that
> evaluates to true or false. Nothing like
>
> select {
> case (do_this) => val1 <-c1:
> case val2 <-c2:
> }
>
> Instead, the chan is set to nil to exclude it from the set. What might
> happen if we had a set of 100 clients and they were switched on and off
> internally in the server (that's their purpose) - when will the uniform
> distribution be reset? What's the life span of the distribution? With a
> psudorandom sequence any one value is only visited once on a round.
>
I'm not sure what you mean here. Is what you call a "round" the cycle of
the PRNG? In that case, this statement isn't true, the cycle is likely
significantly longer than the number of cases. So we definitely chose at
least one case multiple times per cycle.
AFAIK this is the PRNG used by the select
<https://github.com/golang/go/blob/9c7207891c16951121d8b3f19f49ec72f87da9fe/src/runtime/stubs.go#L124>,
FWIW. I assume it simply calls into it (or likely `fastrandn` directly
below) when entering a select with multiple available cases.
We still want this to be fair. Could those having been served be served
> again (before the others) after a reset of the distribution, and this
> introduce a notion of unfairness?
>
It can definitely happen, but I'm not sure that "unfairness" is a
meaningful term here. AIUI the process is "if the runtime enters a select
and multiple cases are ready, it chooses one uniformly at random" (within
the limits of the PRNG). Yes, as an outcome this can mean that one case is
hit more often than the others. But all cases are equally likely to be hit
more often. And by the law of large numbers, you'd expect the distribution
to flatten over time.
(I gues that jamming is that only one client alone gets to the server,
> whereas starving is that a client never gets to the server).
>
Both are statistically unlikely, if we assume the PRNG is reasonably good -
which I think we can, it has been subjected to reasonable statistical tests.
>
> Øyvind
>
>
>>
>> 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+unsubscr...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/golang-nuts/ec5e5c0f-c5bf-4efb-b1c4-dc056720ba5cn%40googlegroups.com
> <https://groups.google.com/d/msgid/golang-nuts/ec5e5c0f-c5bf-4efb-b1c4-dc056720ba5cn%40googlegroups.com?utm_medium=email&utm_source=footer>
> .
>
--
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/golang-nuts/CAEkBMfHA9dqEwUXkttdP5_VaRjWUCAsydiY2F1RUuAOimVT%3D6w%40mail.gmail.com.
