søndag 2. mai 2021 kl. 21:42:10 UTC+2 skrev axel.wa...@googlemail.com: > On Sun, May 2, 2021 at 9:23 PM Øyvind Teig <oyvin...@teigfam.net> wrote: >
(Removed clumsy sentence from me. Again: sorry!) Thanks for all this answering, Axel! I have tried to expand on Jan's code ( >> https://go2goplay.golang.org/p/7xDzP6Jvyl8), here: >> https://go2goplay.golang.org/p/vhmo_Vw6OQy. I have added a mediumPriority >> channel. (Hope it's right..) >> > > That code is missing a case in the innermost select. This one seems > correct: > https://go2goplay.golang.org/p/ZEy752iEOb9 > Great! The rule is *high* in all selects, *medium* in two lowest, *low* only the last select. *Ian* said that select is not an atomic operation. I assume (but everyone >> here seems to tell me the opposite), that at each default there are >> starts of new, unique selects? >> >> Here is one of the comments I wrote to one of Axel's points above, and it >> could be iterated over three priorities as well: >> >> I think this is where I need to understand Go a little better, because it >> might be different from occam's default (TRUE & SKIP). Actually, this may >> be the reason why this thread is still not closed. To me it is very strange >> that between the first polling of the highPri and the default, why that >> outer select is not torn down. Then enter a new select, which would have >> two guards: high and low pri. In my head when setting up the new select >> there would be a decision of which one to select. It would select from the >> set of ready guards right there. They could both have become ready. >> > > This description sounds correct. This is how Go behaves. > Great. I hoped so. Even if it migth get me into trouble below. > Remember in my head these two may be hw pins. (If the first high pri poll >> was done at 0 ns and the second select's decision could be 10 ns later, >> then both hw pins could have become ready at 5 ns). If so the decision >> needs to be on one of them. With "only random" (yes, I think think this is >> so, on a general basis, but I accept that Go doesn't have the other option) >> to chose from, then it *may* chose the low pri, even *if the high pri >> also was, hw wise, ready.* >> > > This is fundamentally correct (though I'm not sure what you mean by "hw > pin"). > Great, I hoped so (2). Even if it migth get me into trouble below (2). "hw pin": On xC (by XMOS) this is valid: https://go2goplay.golang.org/p/Min0kAI7Wao (it looked so much like Go that formatting was ok!) Observe the clause between "case" and "=>" which is the expression, it has to be true to enable the guard. All guards false is an error. If these two (or three) cannot be hardware pins (as in Go), then I reason >> (by induction(?)) that all of the code must be atomic with no descheduling >> in between, for me to understand that the scheme is 100% as intended: >> meaning that there is not any state where random select is ever used. >> > > It is. > Trouble A: If random select is never used in the code example, then (as I queried after this text yesterday) why do we need to have more than one component in each select? Like this https://go2goplay.golang.org/p/ttr7sojJ-9T ?? Again: Your understanding is correct. But the resulting situation is still > equivalent to a priority select. There is no observable behavior in > difference between the two. > So let me repeat my question: > > Assume a read happened from lowPriority, even though highPriority was > ready to read as well. That's, AIUI, the outcome you are concerned about. > In that situation, how would you know that highPriority was ready to read > as well? > > I believe you'll find that the answer is "you can't". > Trouble B: Since I think you have affirmed my scenarios above, that on each select's default there is a tear-down of the previous select and a set-up of the next select, which initially checks the guards to see if there is any, and in case more than two, does random select and selects the wrong (0 ns, 5 ns, 10 ns, 15 ns..). So I would say, "yes, I can". Again, where do I go wrong in this argument (when I think you confirmed..)? You are all allowed to give up on me at this point.. (But I don't seem to be able to trust your truth without this reflection.) If so, maybe a constructive point is to try to write some runnable Go code that uses this pri select pattern. I have thought about it, but I don't know how to check whether it would ever enter one of the selects and in fact need to do a random select, and select a lower when a higher is present (or became present). Plus, if I try to synchronise clients and send over sequence counts, the scheduling pattern could become so repetitive that no such situation would occur. Is there a way to inspect the built code and do it from code inspection? (I guess so?) But for all this, I would need even more help... (Maybe I'll try to trigger a student since I have so much xC ahead of me..) Øyvind > *rog* wrote above (where I had indicated that occam (and also xC, said >> here) has a looping channel construct): "To start with, if you've got N >> clients where N isn't known in advance, it's not possible to use Go's >> select statement directly because it doesn't provide support for reading >> from a slice." Does this mean that aside from reflection ( >> https://go2goplay.golang.org/p/S_5WFkpqMP_H - which still does not serve >> "client 2", shouldn't it?) then idiomatic Go for a small number of >> priorities is the one with default case(s), and it works 100% as intended, >> with no cognitive (?) reliance on Go's inner working under the hood? (I >> mean: "WYSIWYG semantics" kind of.) >> >> I am at a point now that if the answer to the above is *yes*, I'll just >> say thank you for your help, and I will be a Go-wise wiser person. With my >> cognitive bias I will then have to accept that this is Go, nothing more to >> say. Just accept it. Anyhow, in case, thank you! >> >> Øyvind >> >> fredag 30. april 2021 kl. 10:42:47 UTC+2 skrev axel.wa...@googlemail.com: >> >>> On Fri, Apr 30, 2021 at 9:53 AM Øyvind Teig <oyvin...@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...@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...@googlegroups.com. >> > To view this discussion on the web visit >> https://groups.google.com/d/msgid/golang-nuts/9186c34b-1088-4ae0-8076-6c5cd0cdde38n%40googlegroups.com >> >> <https://groups.google.com/d/msgid/golang-nuts/9186c34b-1088-4ae0-8076-6c5cd0cdde38n%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/cda2055a-8024-4ab1-87ca-18a177aa1cb2n%40googlegroups.com.
