mandag 3. mai 2021 kl. 20:23:09 UTC+2 skrev axel.wa...@googlemail.com: > On Mon, May 3, 2021 at 6:34 PM Øyvind Teig <oyvin...@teigfam.net> wrote: > >> meaning that there is not any state where random select is ever used. >>>> >>> It is. >>> >> Trouble A: If random select is never used […] >> > > I was unclear: When I said "It is", I meant "it is used". Your > understanding of what select does is correct. There will be cases, where > both channels are ready when the inner `select` is entered and thus, there > will be a pseudorandom choice over which will proceed. >
Great! The argument put forward is that that's exactly how a priority select would > have to behave as well. As least as I imagine it and as well as I > understand the implementation of `select` (which is, admittedly, not > *super* well). > That is where we might disagree, or at least I not understand you. 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 >> > > This is precisely what my question was getting at. FWIW, it's ultimately > pretty straight forward to demonstrate this behavior: > https://play.golang.org/p/UUA7nRFdyJE > You seem to write Go code fast!-) I don't see where hi and lo are being sent to? Maybe add some more prints would make me understand it better. I would have expected something like https://en.wikipedia.org/wiki/Go_(programming_language)#Concurrencyexample Maybe this is not needed since you run another type of reasoning: This program exits if and only if the inner select choses `lo`. *Given that > we know* that `hi` is being closed before `lo` ("Within a single > goroutine, the happens-before order is the order expressed by the program. > <https://golang.org/ref/mem#tmp_2>"), `lo` being ready implies `hi` being > ready as well. Thus, by seeing that the program exits, we can show that the > inner select sometimes chooses the `lo` case, even though the `hi` is ready > as well. > Crucially, however, we needed to *know* that `close(hi)` happens before > `close(lo)` to prove this case was taken - thus, the communications are not > concurrent. That's what I meant by "external synchronization primitives". > But then, "happens before" is "within a single gorotine". When it comes to several and concurrent goroutines there is no other order than those forced on them by synchronisation over nonbuffered channels (or the join you had in the code example). And then implicit ordering that comes from repetive patterns in the scheduling and running that may cause difficult situations never to happen. I think my question was flawed, because really, the issue isn't about how > the `select` with `default` construct we showed works - the question is how > a priority `select` could work. That is, could we implement a priority > `select` such that this code terminates: > https://play.golang.org/p/4G8CY36L0Qy > But wouldn't this be 50% on each, like in https://play.golang.org/p/INacl7a-BU? (Taken from my note https://www.teigfam.net/oyvind/home/technology/049-nondeterminism/#go_or_go_or_golang) > I don't *think* we can - and based on that assumption I extrapolated how > a priority select would actually behave - but I have to admit that I really > don't understand `select` or the underlying hardware primitives enough to > make a solid case either way here. Maybe you can provide an equivalent > program in a language of your choice that terminates - that would certainly > prove that it's at least possible (though to be clear: I don't understand > your xC code, so I can't promise that I'd understand whatever you send > here, personally :) ). > > All of that being said: I really think that in the cases where a priority > select is needed, this construct is good enough to hold up. > Hmm.. I must admit I smile here. I kind of like that we come to different conclusions. Would you you send your daughter with a fly by wire airplane that has some "good enough" sw? I have worked with safety critical systems all my profession life (40+ years), and we certainly had to find the root cause if we suspected we arrived there. Of course, risk (probability * conesequence) is never zero. Plus, they don't rely on a single system. There is a rather good explanation of PRI ALT (=pri select) of occam, where the TRUE & SKIP (=default) is also seen at page 72 of http://www.transputer.net/obooks/isbn-013629312-3/oc20refman.pdf. This is occam, where much of Limbo and later Go came from, with regards to concurrency (CSP). The Go designers made their own choices. However, in knowing more than we think we need to know it may be an ok ref. There also is a manual in how to write compilers for this, but the PRI par is not mentioned I think, simply because I think that the transputer in fact only had PRI PAR: http://www.transputer.net/iset/pdf/tis-acwg.pdf Øyvind > > 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...@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 >> >> <https://groups.google.com/d/msgid/golang-nuts/cda2055a-8024-4ab1-87ca-18a177aa1cb2n%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/944ccecd-6a70-46de-a09f-7742eab9e2a1n%40googlegroups.com.
