Groups keyboard shortcuts have been updated
Dismiss
See shortcuts

Still "missing" priority or ordered select in go?

1,870 views
Skip to first unread message

Øyvind Teig

unread,
Apr 29, 2021, 4:51:43 AM4/29/21
to golang-nuts
I know from some years ago that go did not have any priority or ordered select construct [1].

The idea is that select always is a nondeterministic choice operator, if this is still so. Implemented with a random, I assume.

Programming user defined "fair" algorithms or patterns is then not possible, I believe.

Is this still so in Go? No prioritised or ordered select in go?

But is there still a way to code this by f.ex. combining several selects? I saw a different take at this at [2], where the select is replaced a single chan containing a chan bundle, thus becoming "deterministic".

[1] Blog note Nondeterminism (disclaimer: no ads, no gifts, only fun and expenses)

Jan Mercl

unread,
Apr 29, 2021, 5:15:14 AM4/29/21
to Øyvind Teig, golang-nuts
On Thu, Apr 29, 2021 at 10:52 AM Øyvind Teig <oyvin...@teigfam.net> wrote:

> I know from some years ago that go did not have any priority or ordered select construct [1].

Not sure what does "ordered" wrt select mean, but the default clause
of the select statement provides exactly that - a priority mechanism:
first try something, otherwise do something else. The most elementary
one, sure, but all the more complex ones can be built with this basic
building block.

Øyvind Teig

unread,
Apr 29, 2021, 5:23:54 AM4/29/21
to golang-nuts
Thanks! A construct like "pri select" or "alt select" or "ordered select", so it's not a "wrt", it's a tagging of select changing ets sematics from being nondeterminstic to deterministic. 

CSP has both: external choice (nondeterminsitic), internal choice (deterministic).

The occam programming language has both "ALT" (=select) and "PRI ALT".

The xC programming language has both "select" and "[[ordered]] select".

This is not solved with a default clause, which transforms the selective choice waiting for some event to happen into busy polling. It's nice yo have some times, but that is something orthogonal to pri/ordered.

Jan Mercl

unread,
Apr 29, 2021, 5:36:45 AM4/29/21
to Øyvind Teig, golang-nuts
On Thu, Apr 29, 2021 at 11:24 AM Øyvind Teig <oyvin...@teigfam.net> wrote:

> This is not solved with a default clause, which transforms the selective choice waiting for some event to happen into busy polling. It's nice yo have some times, but that is something orthogonal to pri/ordered.

Not sure if I would call it busy polling, but I meant schematically this:

select {
case x := <-highPriority:
handle(x)
default:
select {
case x := <-highPriority:
handle(x)
case x := <-lowPriority:
handle(x)
}
}

Øyvind Teig

unread,
Apr 29, 2021, 8:26:15 AM4/29/21
to golang-nuts
Interesting! 

Your suggestion would in fact do pri select in the special case 1. below:
  1. Poll highPri first (take it if it's ready), if highPri not ready then take lowPri (provided highPri has not become ready since the first poll)
  2. However, if highPri has become ready between the first and the second, then it would be taken (provided lowPri is not also ready)
  3. If both have become ready when the second select is entered they would be taken 50% of the time on the average
I fail to see that this is the general pri select that I am quering about whether it has "appeared" in go over the last years. I have a stomach feeling that it can not be implemented by polling. In the semantics of a select the whole select is evaluated before it is entered to se if there is/are any guard(s) ready. If not, pick randomly. If not, set alle guards up in some wait state.

The default case I have always used like "since no event ready (polling) then do something else than listening again on the same events". occam has deafult (although it's called TRUE & SKIP), xC does not.

Øyvind Teig

unread,
Apr 29, 2021, 8:27:47 AM4/29/21
to golang-nuts
If not, pick randomly -> If so, pick randomly

Axel Wagner

unread,
Apr 29, 2021, 8:35:31 AM4/29/21
to Øyvind Teig, golang-nuts
On Thu, Apr 29, 2021 at 2:26 PM Øyvind Teig <oyvin...@teigfam.net> wrote:
Interesting! 

Your suggestion would in fact do pri select in the special case 1. below:
  1. Poll highPri first (take it if it's ready), if highPri not ready then take lowPri (provided highPri has not become ready since the first poll)
  2. However, if highPri has become ready between the first and the second, then it would be taken (provided lowPri is not also ready)
  3. If both have become ready when the second select is entered they would be taken 50% of the time on the average

One thing to point out is that since we are talking about concurrency, where you can really only talk about something happening "after" something else happened, if there is a causal edge between them, this really *is* equivalent to a simple priority select. You can't observe the difference, unless you add more synchronization - in which case we aren't really talking about the code under discussion anymore.

I fail to see that this is the general pri select that I am quering about whether it has "appeared" in go over the last years.

I tend to agree with you on this though. So to answer that question plainly: No, there is no prioritized select in Go and I find it personally unlikely that we'll get one. It might be possible to address some use cases when we get generics, though.
 
I have a stomach feeling that it can not be implemented by polling. In the semantics of a select the whole select is evaluated before it is entered to se if there is/are any guard(s) ready. If not, pick randomly. If not, set alle guards up in some wait state.

The default case I have always used like "since no event ready (polling) then do something else than listening again on the same events". occam has deafult (although it's called TRUE & SKIP), xC does not.
torsdag 29. april 2021 kl. 11:36:45 UTC+2 skrev Jan Mercl:
On Thu, Apr 29, 2021 at 11:24 AM Øyvind Teig <oyvin...@teigfam.net> wrote:

> This is not solved with a default clause, which transforms the selective choice waiting for some event to happen into busy polling. It's nice yo have some times, but that is something orthogonal to pri/ordered.

Not sure if I would call it busy polling, but I meant schematically this:

select {
case x := <-highPriority:
handle(x)
default:
select {
case x := <-highPriority:
handle(x)
case x := <-lowPriority:
handle(x)
}
}

--
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/47051a51-f040-4b51-a792-24a0f96c50f4n%40googlegroups.com.

Jan Mercl

unread,
Apr 29, 2021, 8:58:23 AM4/29/21
to Øyvind Teig, golang-nuts
On Thu, Apr 29, 2021 at 2:26 PM Øyvind Teig <oyvin...@teigfam.net> wrote:

> Your suggestion would in fact do pri select in the special case 1. below:
>
> Poll highPri first (take it if it's ready), if highPri not ready then take lowPri (provided highPri has not become ready since the first poll)
> However, if highPri has become ready between the first and the second, then it would be taken (provided lowPri is not also ready)
> If both have become ready when the second select is entered they would be taken 50% of the time on the average

My analysis is different. There are four cases on entry of the outer
select statement:

1. high is ready and low is ready -> high handled, correct.
2. high is ready and low is not ready -> high handled, correct.
3. high is not ready and low is ready -> low handled, correct.

The "interesting" case is

4. high not ready and low not ready.

We enter the default clause of the outer select statement and enter
the inner select statement. Now there are three subcases when
eventually something gets ready:

4a. high gets ready before low gets ready -> high handled, correct.
4b. low gets ready before high gets ready -> low handled, correct.
4c. both high and low get ready at the same time -> one of them is
randomly chosen, correct.

Øyvind Teig

unread,
Apr 29, 2021, 9:10:31 AM4/29/21
to golang-nuts
I agree with you.

However, with the first select in the example we have a "first" and with the second we have an "after" which might be considered race condition(s9 for the purpose of seeing the example of what I was after.

Also, scheduling arguments cannot be used here: like "we know that there is no scheduling (of go goroutines) between the first and the second select." If we know, it's not an argument.

Robert Engels

unread,
Apr 29, 2021, 9:20:40 AM4/29/21
to Øyvind Teig, golang-nuts
It is trivial to do a priority select. Check the high priority channel again after getting a low priority value. If the high priority is available enqueue the low value and handle the high. 

It is also trivial to “delay” the handling to allow more time for high events to arrive if dealing with synchronized events and you need to account for jitter. 

On Apr 29, 2021, at 8:10 AM, Øyvind Teig <oyvin...@teigfam.net> wrote:

I agree with you.

Øyvind Teig

unread,
Apr 29, 2021, 9:23:36 AM4/29/21
to golang-nuts
Jan, I agree on your list, it's better set up than mine. 

But you can add a point after (4.) though, call it (second.pre), dealing with what might have happened after the first select decided that none were taken until it evaluates the precondition to the second select. 

4c is not "correct" as I want it. In the pri select case, if more than one is ready, then they shall not be randomly chosen. Never. They should be selected according to priority.

As I discussed (and several with me) in the blog note, the fact that Go doesn't seem to have it, then go needs another definition of "fair" than what is normal discussing these things. The basic idea for Google was, if we have a problem with fairness (none gets starved, all get served), just add another computer (said over a beer). Plus, the need for the fairness that one can build with a pri select (most often by reordering the list of guards according to one's pleasing of what one might think of as fair), is according to Goodle (on go, I think), so tiny that we make it simple: drop it. Of course it's also easy to try to implement one's own fairness and fail with it. In a realtime system it's not that easy to test, and these things most often are best evaluated on paper. So a formal proof might do.

Axel Wagner

unread,
Apr 29, 2021, 9:28:03 AM4/29/21
to Øyvind Teig, golang-nuts
My argument is that you can't distinguish the case "neither was ready and highPriority and lowPriority became ready simultaneously and lowPriority was selected" from "highPriority became ready after lowPriority" (as long as there is the same code in both highPriority cases). Because there is no "simultaneous" or "after" in concurrency, unless you use synchronization - the real phrasing is "highPriority and lowPriority became ready simultaneously" and if, *in real time* that means one or the other came first is indeterminate. There is no implementation or scheduling argument here - this argument is purely based on the Go memory model and the spec.

If there is no observable difference in behavior, the two are equivalent.

But either way, as I said, it's not really the same, just based on readability and clarity. It's semantically equivalent, but semantically, Go is equivalent to Assembly and yet we prefer Go :)

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/cf43611c-599f-46d9-98ac-60ede00daea9n%40googlegroups.com.

Øyvind Teig

unread,
Apr 29, 2021, 9:29:51 AM4/29/21
to golang-nuts
I sent that to the wrong entry! Is it possible that you could make a code example?

Øyvind Teig

unread,
Apr 29, 2021, 9:38:47 AM4/29/21
to golang-nuts
axel, it's difficult to try to explain in words how a select behaves. On that we can agree. For me, select cases can be channels, timeouts, external events etc. If a task is in a select (none triggered yet) and there is an interrupt that detects the select entry, it's ticked as triggered, the select is torn down, and in time the select will be taken with that event only. Not like Linux select which can deliver several causes. But if the timrout came just before the pin, then.. etc. Temporal logic in this case certainly makes sense.

Jan Mercl

unread,
Apr 29, 2021, 9:47:42 AM4/29/21
to Øyvind Teig, golang-nuts
On Thu, Apr 29, 2021 at 3:23 PM Øyvind Teig <oyvin...@teigfam.net> wrote:

> 4c is not "correct" as I want it. In the pri select case, if more than one is ready, then they shall not be randomly chosen. Never. They should be selected according to priority.

That's not what 4c says. Instead of "more than one ready" it says
"both high and low _get ready at the same time_".

Note that in the first approximation the probability of 4c happening
is approaching zero. If we consider time "ticks" in discrete quanta,
the probability is proportional to the size of the quantum. And
depending on a particular implementation of the scheduler the
probability of 4c can still be exactly zero. For example, the OS
kernel may deliver only one signal at a time to the process etc.

So the "Never" case may quite well never happen at all.

Øyvind Teig

unread,
Apr 29, 2021, 9:53:49 AM4/29/21
to golang-nuts

They could still both have become ready (not in the same "cycle") between the two selects. Even if that probability is low, it would need knowledge like yours to show that this may in fact be zero. There could be a descheduling in between, one of those in my opinion, not relevant arguments.

robert engels

unread,
Apr 29, 2021, 10:10:00 AM4/29/21
to Øyvind Teig, golang-nuts
I will give you the pseudo code:

{ // step #1 do select on both
   select high
   select low
}

if high read:
   return high
else:
   // we read a low so do a high poll
   {
       select high:
       default:
   }

 if high read:
      enqueue low and return high
 else:
      if queue empty:
         return low
      else:
           use queue and enqueue low from step #1 // FIFO order on low reads 

The above code will always return high values over low values (if high available), and return low values in order of events


Jan Mercl

unread,
Apr 29, 2021, 10:18:20 AM4/29/21
to Øyvind Teig, golang-nuts
On Thu, Apr 29, 2021 at 3:54 PM Øyvind Teig <oyvin...@teigfam.net> wrote:

> Even if that probability is low, it would need knowledge like yours to show that this may in fact be zero. There could be a descheduling in between, one of those in my opinion, not relevant arguments.

The upper limit of 4c happening is 1/12 for random events. I guess in
practice it is at least an order of magnitude lower because the
"effective" time ticks are small.

Ian Davis

unread,
Apr 29, 2021, 10:27:17 AM4/29/21
to golan...@googlegroups.com
On Thu, 29 Apr 2021, at 3:09 PM, robert engels wrote:
I will give you the pseudo code:

{ // step #1 do select on both
   select high
   select low
}

if high read:
   return high
else:
   // we read a low so do a high poll
   {
       select high:
       default:
   }

 if high read:
      enqueue low and return high
 else:
      if queue empty:
         return low
      else:
           use queue and enqueue low from step #1 // FIFO order on low reads 

The above code will always return high values over low values (if high available), and return low values in order of events

This seems likely deadlock if the low channel is being filled continually by another goroutine. In addition I usually aim to give ownership of the channel to the writer so it can close cleanly, but mixing reads and writes in a single function greatly complicates that.

Ian

robert engels

unread,
Apr 29, 2021, 10:29:55 AM4/29/21
to Øyvind Teig, golang-nuts
It needs one other fix, and that is to have a check of the queue and poll high, in case the queue has elements when the method is entered.

But if you implement the queue using a buffered channel it is trivial to change the step #1 to handle this (the low and queue channels are mimic the high and low channel).

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

robert engels

unread,
Apr 29, 2021, 10:32:11 AM4/29/21
to Ian Davis, golan...@googlegroups.com
It is not.

Because the low items will be read if there are no highs available. If the low isn’t read, the producer on the low will block.

Or you run out of memory if you cannot process the events fast enough - which is also easily handled by bounding the queue - but then you may need to drop items.

There are no free lunches.

But no deadlock.



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

robert engels

unread,
Apr 29, 2021, 10:34:50 AM4/29/21
to Ian Davis, golan...@googlegroups.com
To clarify, you might never process a low item if a high is always available - but I believe that is what the OP is requesting.

It is also fairly trivial to add fairness to this ti always process a low if available every N cycles.

Axel Wagner

unread,
Apr 29, 2021, 10:40:19 AM4/29/21
to Øyvind Teig, golang-nuts
On Thu, Apr 29, 2021 at 3:54 PM Øyvind Teig <oyvin...@teigfam.net> wrote:
They could still both have become ready (not in the same "cycle") between the two selects. Even if that probability is low, it would need knowledge like yours to show that this may in fact be zero. There could be a descheduling in between, one of those in my opinion, not relevant arguments.

FTR, again: Yes, it's definitely possible, but it's irrelevant. It makes no observable difference. Even if we had a prioritized select, it would still be *de facto* implemented as a multi-step process and even then, you might run into exactly the same situation - you could have both channels becoming ready while the runtime does setup, or you could have a random scheduling event delaying one of the goroutines infinitesimally, or you could have…

This is why we *don't* talk about the behavior of concurrent programs in terms of cycles and time, but instead based on causal order. We don't know how long it takes to park or unpark a goroutine, so all we can say is that a read from a channel happens after the corresponding write. In terms of time, between entering the `select` statement and between parking the goroutine might lie a nanosecond, or a million years - we don't know, so we don't talk about it.

The memory model is exactly there to abstract away these differences and to not get caught up in scheduling and cycle discussions - so, FWIW, if these arguments are not relevant, you shouldn't bring them up. Logically, between the first `select` statement and the second `select` statement, there is zero time happening. Arguing that there is, is using exactly those irrelevant arguments about schedulers and processing time.
 
torsdag 29. april 2021 kl. 15:47:42 UTC+2 skrev Jan Mercl:
On Thu, Apr 29, 2021 at 3:23 PM Øyvind Teig <oyvin...@teigfam.net> wrote:

> 4c is not "correct" as I want it. In the pri select case, if more than one is ready, then they shall not be randomly chosen. Never. They should be selected according to priority.

That's not what 4c says. Instead of "more than one ready" it says
"both high and low _get ready at the same time_".

Note that in the first approximation the probability of 4c happening
is approaching zero. If we consider time "ticks" in discrete quanta,
the probability is proportional to the size of the quantum. And
depending on a particular implementation of the scheduler the
probability of 4c can still be exactly zero. For example, the OS
kernel may deliver only one signal at a time to the process etc.

So the "Never" case may quite well never happen at all.

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

Axel Wagner

unread,
Apr 29, 2021, 10:44:40 AM4/29/21
to Øyvind Teig, golang-nuts
FWIW, maybe this helps:

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?

roger peppe

unread,
Apr 29, 2021, 2:22:32 PM4/29/21
to Axel Wagner, Øyvind Teig, golang-nuts
I agree with Axel's take here. It seems, Øyvind, that you are concerned more with principle than practice here. Can you give an example of a real world case where you think that this might actually matter?

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAEkBMfFC1gtxbWZsy88gM4ymPncCjs6Q3YJpTcXym8bT1Ev6Kw%40mail.gmail.com.

Øyvind Teig

unread,
Apr 29, 2021, 3:05:04 PM4/29/21
to golang-nuts
torsdag 29. april 2021 kl. 20:22:32 UTC+2 skrev rog:
I agree with Axel's take here. It seems, Øyvind, that you are concerned more with principle than practice here. Can you give an example of a real world case where you think that this might actually matter?

Thanks, yes. I have written some about that in the Nondeterminsim blog note, referred to at the top. I admit I indicated that seeing some code might be interesting, but it was the principle I was after. In the end a "yes" or "no".

Some from the chapter "-Nondeterministic selective choice in implementations is not good": (Preceeding the quote I have been telling about CSP's external nondeterministic choice in the specfications ("implement this any way you want") but in the implementation part we have to take decisions (deterministic, inner choice: "we do it this way"). I was thinking this is relevant because Why build concurrency on the ideas of CSP? Here's the quote:

"The statement was that with the non-deterministic guarded choice in Go, what happens is up to the run-time, which is “not good”. This is implementation, not specification. With occam there is ALT or PRI ALT, always coded as PRI ALT. For a server to be “fair” I have to code it myself, it’s up to me, at the application level to find the best algorithm. Which, during my years as occam programmer was “new starting channel index in the ALT-set is the channel index of the served channel + 1 modulo-divided by number of channels”. Channels are clients[0..4] (five) ALT‘ed in set [4,0,1,2,3] served index 4, then 4+1 rem 5 == 0 yields next ALT set [0,1,2,3,4]. Just served 4 and you’re at the back of the set."

The example here is a server with N clients where it is essential that none of clients will starve and none jam the server. I have needed to do this coding several times. Go has random select which in theory may mean starving and jamming. I worked with safety critical fire detection, and it was necessary to ensure this. Or at least we didn't dare to take the chance. We could not just add another machine.

To use select when that's fair enough (pun 1) - "fair enough" (pun 2). But If I want to be certain of no starving or jamming I need to code the fairness algorithm. I can then promise a client that may have been ready but wasn't served to come in before I take the previous clients that were allowed. This is at best very difficult if all we have is select. Having pri select as the starting point is, in this case, easier.

Øyvind

Robert Engels

unread,
Apr 29, 2021, 4:02:23 PM4/29/21
to Øyvind Teig, golang-nuts
I already gave you the solution to this. Trust me it works. I did HFT for 7+ years - the algo is well known. 

On Apr 29, 2021, at 2:05 PM, Øyvind Teig <oyvin...@teigfam.net> wrote:



Øyvind Teig

unread,
Apr 29, 2021, 4:46:34 PM4/29/21
to golang-nuts
  1. I'm sorry I didn't follow up on your answer where you had got to the length of spelling out some code right before my eyes. I got lost in the other points (I actually started a response..)
  2. I trust you
  3. But to do more than trusting, understanding would be much better. I'm sorry: to understand I would need more than pseudo code
  4. But I was really after whether the "pri" keyword (or whatever) in front of "select" had been introduced over the last years. The answer seems to be "no"
  5. Although I appreciate that Turing proved that any language can code anything, I some times have had a hard time believing it. Maybe that's not exactly what he meant. But then, since I trust you, I do find that solution as surprising as as I would be happy to run it on The Go Playground

Axel Wagner

unread,
Apr 29, 2021, 5:02:10 PM4/29/21
to Øyvind Teig, golang-nuts
On Thu, Apr 29, 2021 at 10:47 PM Øyvind Teig <oyvin...@teigfam.net> wrote:
  1. I'm sorry I didn't follow up on your answer where you had got to the length of spelling out some code right before my eyes. I got lost in the other points (I actually started a response..)
  2. I trust you
  3. But to do more than trusting, understanding would be much better. I'm sorry: to understand I would need more than pseudo code
  4. But I was really after whether the "pri" keyword (or whatever) in front of "select" had been introduced over the last years. The answer seems to be "no"

FWIW I did answer this explicitly above :) No, there is no way to manually specify priorities of `select` and no, I subjectively wouldn't predict it happening at any point in the near or far future. Unless someone comes up with an extremely convincing, so far unheard of argument in its favor :)
 

roger peppe

unread,
Apr 29, 2021, 5:52:05 PM4/29/21
to Øyvind Teig, golang-nuts
On Thu, 29 Apr 2021, 20:05 Øyvind Teig, <oyvin...@teigfam.net> wrote:
torsdag 29. april 2021 kl. 20:22:32 UTC+2 skrev rog:
I agree with Axel's take here. It seems, Øyvind, that you are concerned more with principle than practice here. Can you give an example of a real world case where you think that this might actually matter?

Thanks, yes. I have written some about that in the Nondeterminsim blog note, referred to at the top. I admit I indicated that seeing some code might be interesting, but it was the principle I was after. In the end a "yes" or "no".

Some from the chapter "-Nondeterministic selective choice in implementations is not good": (Preceeding the quote I have been telling about CSP's external nondeterministic choice in the specfications ("implement this any way you want") but in the implementation part we have to take decisions (deterministic, inner choice: "we do it this way"). I was thinking this is relevant because Why build concurrency on the ideas of CSP? Here's the quote:

"The statement was that with the non-deterministic guarded choice in Go, what happens is up to the run-time, which is “not good”. This is implementation, not specification. With occam there is ALT or PRI ALT, always coded as PRI ALT. For a server to be “fair” I have to code it myself, it’s up to me, at the application level to find the best algorithm. Which, during my years as occam programmer was “new starting channel index in the ALT-set is the channel index of the served channel + 1 modulo-divided by number of channels”. Channels are clients[0..4] (five) ALT‘ed in set [4,0,1,2,3] served index 4, then 4+1 rem 5 == 0 yields next ALT set [0,1,2,3,4]. Just served 4 and you’re at the back of the set."

The example here is a server with N clients where it is essential that none of clients will starve and none jam the server.
I have needed to do this coding several times. Go has random select which in theory may mean starving and jamming. I worked with safety critical fire detection, and it was necessary to ensure this. Or at least we didn't dare to take the chance. We could not just add another machine.

To use select when that's fair enough (pun 1) - "fair enough" (pun 2). But If I want to be certain of no starving or jamming I need to code the fairness algorithm. I can then promise a client that may have been ready but wasn't served to come in before I take the previous clients that were allowed. This is at best very difficult if all we have is select. Having pri select as the starting point is, in this case, easier.

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.
You can do it with reflection though. It's not too hard to code something quite similar to your algorithm above.

I think the above code should fit your definition of fairness, and it seems to me that it's a reasonably general approach.
 
  cheers,
    rog.

Ian Lance Taylor

unread,
Apr 29, 2021, 8:45:02 PM4/29/21
to Øyvind Teig, golang-nuts
On Thu, Apr 29, 2021 at 12:05 PM Øyvind Teig <oyvin...@teigfam.net> wrote:
>
> The example here is a server with N clients where it is essential that none of clients will starve and none jam the server. I have needed to do this coding several times. Go has random select which in theory may mean starving and jamming. I worked with safety critical fire detection, and it was necessary to ensure this. Or at least we didn't dare to take the chance. We could not just add another machine.
>
> To use select when that's fair enough (pun 1) - "fair enough" (pun 2). But If I want to be certain of no starving or jamming I need to code the fairness algorithm. I can then promise a client that may have been ready but wasn't served to come in before I take the previous clients that were allowed. This is at best very difficult if all we have is select. Having pri select as the starting point is, in this case, easier.

When there are multiple ready results, the select statement in Go is
guaranteed to use a uniform pseudo-random selection
(https://golang.org/ref/spec#Select_statements). The fact that cases
are selected using a uniform distribution ensures that executing a
select statement in a loop can't lead to starving (I'm not sure what
jamming is).

As several people have said, it's meaningless to say "I want to ensure
that if both case A and case B are available then the select statement
will choose case A." It's meaningless because it relies on a notion
of simultaneity that literally doesn't exist. There will always be a
period of time after the select statement chooses B, but before it
actually executes the case, that case A may become ready. That will
be true for any possible implementation of select, because select is
not an atomic operation.

Therefore, this code using a hypothetical priority case

select {
case pri <-c1:
case <-c2:
}

can always be rewritten as

select {
case <-c1:
default:
select {
case <-c1:
case <-c2:
}
}

The rewritten select is exactly equivalent to the first. The only way
that they could not be equivalent would be if select were atomic.

Ian

Øyvind Teig

unread,
Apr 30, 2021, 3:20:20 AM4/30/21
to golang-nuts
torsdag 29. april 2021 kl. 23:52:05 UTC+2 skrev rog:
On Thu, 29 Apr 2021, 20:05 Øyvind Teig, <oyvin...@teigfam.net> wrote:
torsdag 29. april 2021 kl. 20:22:32 UTC+2 skrev rog:
I agree with Axel's take here. It seems, Øyvind, that you are concerned more with principle than practice here. Can you give an example of a real world case where you think that this might actually matter?

Thanks, yes. I have written some about that in the Nondeterminsim blog note, referred to at the top. I admit I indicated that seeing some code might be interesting, but it was the principle I was after. In the end a "yes" or "no".

Some from the chapter "-Nondeterministic selective choice in implementations is not good": (Preceeding the quote I have been telling about CSP's external nondeterministic choice in the specfications ("implement this any way you want") but in the implementation part we have to take decisions (deterministic, inner choice: "we do it this way"). I was thinking this is relevant because Why build concurrency on the ideas of CSP? Here's the quote:

"The statement was that with the non-deterministic guarded choice in Go, what happens is up to the run-time, which is “not good”. This is implementation, not specification. With occam there is ALT or PRI ALT, always coded as PRI ALT. For a server to be “fair” I have to code it myself, it’s up to me, at the application level to find the best algorithm. Which, during my years as occam programmer was “new starting channel index in the ALT-set is the channel index of the served channel + 1 modulo-divided by number of channels”. Channels are clients[0..4] (five) ALT‘ed in set [4,0,1,2,3] served index 4, then 4+1 rem 5 == 0 yields next ALT set [0,1,2,3,4]. Just served 4 and you’re at the back of the set."

The example here is a server with N clients where it is essential that none of clients will starve and none jam the server.
I have needed to do this coding several times. Go has random select which in theory may mean starving and jamming. I worked with safety critical fire detection, and it was necessary to ensure this. Or at least we didn't dare to take the chance. We could not just add another machine.

To use select when that's fair enough (pun 1) - "fair enough" (pun 2). But If I want to be certain of no starving or jamming I need to code the fairness algorithm. I can then promise a client that may have been ready but wasn't served to come in before I take the previous clients that were allowed. This is at best very difficult if all we have is select. Having pri select as the starting point is, in this case, easier.

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.
You can do it with reflection though. It's not too hard to code something quite similar to your algorithm above.

Thanks! I like the fact that you can do it like this. However, there was "client 2" in the log(?)

Øyvind

Øyvind Teig

unread,
Apr 30, 2021, 3:53:21 AM4/30/21
to golang-nuts
fredag 30. april 2021 kl. 02:45:02 UTC+2 skrev Ian Lance Taylor:
On Thu, Apr 29, 2021 at 12:05 PM Øyvind Teig <oyvin...@teigfam.net> wrote:
>
> The example here is a server with N clients where it is essential that none of clients will starve and none jam the server. I have needed to do this coding several times. Go has random select which in theory may mean starving and jamming. I worked with safety critical fire detection, and it was necessary to ensure this. Or at least we didn't dare to take the chance. We could not just add another machine.
>
> To use select when that's fair enough (pun 1) - "fair enough" (pun 2). But If I want to be certain of no starving or jamming I need to code the fairness algorithm. I can then promise a client that may have been ready but wasn't served to come in before I take the previous clients that were allowed. This is at best very difficult if all we have is select. Having pri select as the starting point is, in this case, easier.

When there are multiple ready results, the select statement in Go is
guaranteed to use a uniform pseudo-random selection
(https://golang.org/ref/spec#Select_statements). The fact that cases
are selected using a uniform distribution ensures that executing a
select statement in a loop can't lead to starving (I'm not sure what
jamming is).

As several people have said, it's meaningless to say "I want to ensure
that if both case A and case B are available then the select statement
will choose case A." It's meaningless because it relies on a notion
of simultaneity that literally doesn't exist.

I have a stomach feeling that I agree with you. I will still argue against. I just wish someone could pinpoint where these standpoints clash, or don't. 

If there is no notion of simultaneity why all the effort to describe the random distribution? 

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.
 
There will always be a
period of time after the select statement chooses B, but before it
actually executes the case, that case A may become ready. That will
be true for any possible implementation of select, because select is
not an atomic operation.

Therefore, this code using a hypothetical priority case

select {
case pri <-c1:
case <-c2:
}

can always be rewritten as

select {
case <-c1:
default:
select {
case <-c1:
case <-c2:
}
}

The rewritten select is exactly equivalent to the first. The only way
that they could not be equivalent would be if select were atomic.

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? 

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?

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

 (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).

Øyvind
 

Ian

Axel Wagner

unread,
Apr 30, 2021, 4:42:47 AM4/30/21
to golang-nuts
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, 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.

Øyvind Teig

unread,
May 2, 2021, 3:23:13 PM5/2/21
to golang-nuts
Axel, it is impolite not to try to comment and discuss each and every point above. I actually started to do exactly that when I discovered that it all boils down to this (FWIW?):

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

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

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. 

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

Øyvind Teig

unread,
May 2, 2021, 3:32:02 PM5/2/21
to golang-nuts
One more thing, if (by presumably faulty reasoning above) random select is never done, would we need the two guards in the second select? 

Axel Wagner

unread,
May 2, 2021, 3:42:10 PM5/2/21
to Øyvind Teig, golang-nuts
On Sun, May 2, 2021 at 9:23 PM Øyvind Teig <oyvin...@teigfam.net> wrote:
Axel, it is impolite not to try to comment and discuss each and every point above.

I wasn't trying to be impolite. But I also won't go through your messages sentence by sentence, trying to say something even if I have nothing to say. Sorry. If that doesn't suit you, I'll step out of the conversation.
 
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:
 
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.
 
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").
 
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.

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

 

Øyvind Teig

unread,
May 2, 2021, 5:55:50 PM5/2/21
to golang-nuts
Axel, I was saying (at least meaning) that it was impolite of me not to answer your exhaustive comments! The other way around. But I now see why you got upset. It may read that way too! I read things over many times, did spell checking, but I didn't see this coming! I will read the rest of the comments tomorrow! Please excuse me for my Bad English! I have always been impressed by the golang-nuts group, how well everything has been responded to, and how much people have taken the time to answer my questions, coming from the other side of the field. I don't take this for granted at all! Øyvind

Axel Wagner

unread,
May 3, 2021, 3:24:45 AM5/3/21
to golang-nuts
No worries, I was not upset :) But I did misunderstand you, thanks for clearing that up.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/dc3898ea-032e-4b28-acd4-65e1b7cef21fn%40googlegroups.com.

Øyvind Teig

unread,
May 3, 2021, 12:34:20 PM5/3/21
to golang-nuts
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:

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

Axel Wagner

unread,
May 3, 2021, 2:23:09 PM5/3/21
to Øyvind Teig, golang-nuts
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.

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

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:
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."), `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".

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

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. 

Robert Engels

unread,
May 3, 2021, 3:11:48 PM5/3/21
to Axel Wagner, Øyvind Teig, golang-nuts
In most “select” implementations a set of “ready” endpoints is returned. So it is trivial for the reader to prioritize some endpoints over others. 

Because of the way Go select works it is more difficult - requiring nested selects - and it is more easily implemented using multiple readers and queues once it moves beyond a few producers. 

On May 3, 2021, at 1:23 PM, 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:



Øyvind Teig

unread,
May 3, 2021, 3:16:09 PM5/3/21
to golang-nuts
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:

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."), `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

 
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

Øyvind Teig

unread,
May 3, 2021, 3:24:24 PM5/3/21
to golang-nuts
mandag 3. mai 2021 kl. 21:11:48 UTC+2 skrev ren...@ix.netcom.com:
In most “select” implementations a set of “ready” endpoints is returned. So it is trivial for the reader to prioritize some endpoints over others. 

Do you mean in user code in other languages than Go? If so, which ones were you thinking of? 

Because of the way Go select works it is more difficult - requiring nested selects - and it is more easily implemented using multiple readers and queues once it moves beyond a few producers. 

I see that, which is great. But I still don't understand why https://go2goplay.golang.org/p/S_5WFkpqMP_H (By rog, 29Apr2021 23:52:05) seems not to print "Client 2".

Øyvind

Axel Wagner

unread,
May 3, 2021, 3:44:49 PM5/3/21
to Øyvind Teig, golang-nuts
On Mon, May 3, 2021 at 9:16 PM Øyvind Teig <oyvin...@teigfam.net> wrote:
I don't see where hi and lo are being sent to?

They are being `close`d. Reading from a closed channel immediately succeeds, yielding the zero value.
I chose to use `close` because it's a non-blocking way to make a channel readable. You could get the same demonstration by making the channels buffered and writing to them.

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

Exactly. It is only *because* we use a single goroutine and we thus know that there is a happens-before edge.
For example, this program *also* exits (i.e. line 16 is executed), but you can no longer conclude that `hi` was ready when it does.

This is how most practical cases would likely 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


I don't understand this question. Though I also see that my question is wrong - it should be "could we implement a priority `select` such that this code *never* terminates.

If we suppose a perfect priority select, which never chooses the `lo` case if the `hi` case is ready, the program I linked would never terminate. Because `lo` is never ready unless `hi` is ready too. This, AIUI, is the priority `select` you'd want. Note, in particular, the made up `pri` keyword in the example.

So, no, in that scenario we wouldn't have a pseudo-random choice. The question I was begging is if we could actually implement a select like you want. If you can write this program in another language, and that program ends up not terminating, that would demonstrate that it's indeed possible to write a `select` as you are requesting.

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?

This is… a strange question. I'm not saying "the software might be buggy, but it will be buggy software that is good enough". I'm saying "the construct is good enough to implement non-buggy software with it". Of course you need to know what the construct does and take it into account when writing your code - if you assume it works differently than it does, you'll introduce bugs, yes. That is true in any language.
 
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.

Can you translate the example into that language? And demonstrate that it doesn't terminate?
 
It's not practical for me to learn a different language and scour its reference manual, to try and figure out how their select works, if that is compatible with how Go's select works and thus if and how lessons learned from that language are transferable to Go.

You seem to be convinced that their priority select is superior to Go's select construct and can map semantics that Go can't. I'm willing to believe that, but I'd prefer a demonstration. The example should, in a loop
• create two channels `hi` and `lo`
• In a concurrent routine, write first to `hi` and then to `lo` (to establish a happens-before edge)
• use a priority-select
• prioritizing reading from `hi`
• exiting the program if it reads from `lo`
• never exit, when run
If you can make this translation, I'm convinced that it's possible implementing a `select` statement using the semantics you suggest. Without that - no offense - I must consider the possibility that you are misunderstanding how Occam's select statement works.

Robert Engels

unread,
May 3, 2021, 3:48:20 PM5/3/21
to Øyvind Teig, golang-nuts
Yes, C for instance. 

It doesn’t print ‘client 2’ because your code is broken. It prints “late arrival” if you remove the sleep. The main program finishes before the go routine runs.  

On May 3, 2021, at 2:24 PM, Øyvind Teig <oyvin...@teigfam.net> wrote:

Øyvind Teig

unread,
May 3, 2021, 5:12:03 PM5/3/21
to golang-nuts
mandag 3. mai 2021 kl. 21:44:49 UTC+2 skrev axel.wa...@googlemail.com:
On Mon, May 3, 2021 at 9:16 PM Øyvind Teig <oyvin...@teigfam.net> wrote:
I don't see where hi and lo are being sent to?

They are being `close`d. Reading from a closed channel immediately succeeds, yielding the zero value.
I chose to use `close` because it's a non-blocking way to make a channel readable. You could get the same demonstration by making the channels buffered and writing to them.

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

Exactly. It is only *because* we use a single goroutine and we thus know that there is a happens-before edge.
For example, this program *also* exits (i.e. line 16 is executed), but you can no longer conclude that `hi` was ready when it does.

This is how most practical cases would likely 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


I don't understand this question. Though I also see that my question is wrong - it should be "could we implement a priority `select` such that this code *never* terminates.

If we suppose a perfect priority select, which never chooses the `lo` case if the `hi` case is ready, the program I linked would never terminate. Because `lo` is never ready unless `hi` is ready too. This, AIUI, is the priority `select` you'd want. Note, in particular, the made up `pri` keyword in the example.

So, no, in that scenario we wouldn't have a pseudo-random choice. The question I was begging is if we could actually implement a select like you want. If you can write this program in another language, and that program ends up not terminating, that would demonstrate that it's indeed possible to write a `select` as you are requesting.

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?

This is… a strange question. I'm not saying "the software might be buggy, but it will be buggy software that is good enough". I'm saying "the construct is good enough to implement non-buggy software with it". Of course you need to know what the construct does and take it into account when writing your code - if you assume it works differently than it does, you'll introduce bugs, yes. That is true in any language.
 
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.

Can you translate the example into that language? And demonstrate that it doesn't terminate?
 
It's not practical for me to learn a different language and scour its reference manual, to try and figure out how their select works, if that is compatible with how Go's select works and thus if and how lessons learned from that language are transferable to Go.

You seem to be convinced that their priority select is superior to Go's select construct and can map semantics that Go can't.

This is the only point I'll respond to tonight (with the possibility of being impolite since your response is so thorough). No, I am not saying that occam's PRI ALT or xC's [[ordered]] select are superior to Go's select (or Promela's :: for that sake: https://en.wikipedia.org/wiki/Promela#Executability). What I could say is that occam (and probably xC) nondeterministic choice (select without pri) is inferior to the Go select, since Go select is indeed pseudo random. I like it. My eager in telling about occam and xC prioritised choice may have mislead. I am simply saying that a select and a pri select are different, and I still don't understand why Go doesn't have pri select, and I started with asking about whether that had changed over the previous years. Compared with the letters "pri" the reflection case example is complicated, and the select default select.. special case for a small number of channels is simple to read, but in my opinion it stops there. I do want to be convinced that it is elegant (even if you promise it works, compared to "pri"), but I am not. About the case below. I like Go because it is so expressive, by the looks of it. When Go came with channels, you wont' believe what a relief if was to us who had used them and loved them for years. They were not dying. I don't have time to dig up an occam compiler (yes, they exist, there is some on comp.sys.transputer group, they even make FPGA transputers these days, for those who need them..) but doing what you suggest would have been fun. The semantics of an occam PRI ALT is simple and I programmed it for ten years, and I hope some of that understanding has remained.)

Øyvind

roger peppe

unread,
May 4, 2021, 7:13:51 AM5/4/21
to Øyvind Teig, golang-nuts
On Mon, 3 May 2021 at 20:24, Øyvind Teig <oyvin...@teigfam.net> wrote:
I see that, which is great. But I still don't understand why https://go2goplay.golang.org/p/S_5WFkpqMP_H (By rog, 29Apr2021 23:52:05) seems not to print "Client 2".

That's because to try to emphasise the arbitrariness of the producers (and to check that the consuming code was working as intended), the producing code deliberately doesn't produce any values on channel 2. Instead, it sleeps for a second and produces a "late arrival" message.

It's trivial to take out the if statement and show that it works as you'd expect: https://go2goplay.golang.org/p/TjgiOmZtQhR

Øyvind Teig

unread,
May 5, 2021, 12:55:48 PM5/5/21
to golang-nuts
mandag 3. mai 2021 kl. 23:12:03 UTC+2 skrev Øyvind Teig:
mandag 3. mai 2021 kl. 21:44:49 UTC+2 skrev axel.wa...@googlemail.com:
On Mon, May 3, 2021 at 9:16 PM Øyvind Teig <oyvin...@teigfam.net> wrote:
I don't see where hi and lo are being sent to?

They are being `close`d. Reading from a closed channel immediately succeeds, yielding the zero value.
I chose to use `close` because it's a non-blocking way to make a channel readable. You could get the same demonstration by making the channels buffered and writing to them.

I have played with that code at https://play.golang.org/p/U17AbmGBZUY. Instead of starting and starting lots of tasks, I just start 3. Sender (two configs: one with two tasks in parallel and one config with one task sending in sequence, and one with zero or 1 dim of the chans. However, I am just as wise. I don't see how any of the test cod" examples based on this proves that a hi is always taken if there is a lo lurking. I hope it's not my cognitive bias that I just cant' see it! I only see code that terminates if lo is taken after hi has been polled as not active some time before, but it says nothing about hi at the time lo is taken. It might have become active. If you see what any flawed thinking in the example above is, I'd be happy to know.

Here is my cognitive test case. It is not 100% realistic, but it's just to convey my point:
hiPri is a disconnect message of a smoke detetector. loPri is a fire alarm. If the disconnect hiPri is activated before (1 sec to 1 ns) or simulatenously (same polling of "hw pins") as the alarm loPri there should be no alarm being sent to the fire department. No emergency fire trucks. Not ever. There should not be any case of some low probability where this may happen. However, if the hiPri disconnect message was activated after the alarm, then it was too late, and the alarm will go off. (Disconnect was because we knew that there was going to be an alarm since we were doing something, and we explicitly did not want the fire trucks to come)

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

Exactly. It is only *because* we use a single goroutine and we thus know that there is a happens-before edge.
For example, this program *also* exits (i.e. line 16 is executed), but you can no longer conclude that `hi` was ready when it does.

This is how most practical cases would likely 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


I don't understand this question. Though I also see that my question is wrong - it should be "could we implement a priority `select` such that this code *never* terminates.

You used close which I didn't understand then. Thanks.
 
If we suppose a perfect priority select, which never chooses the `lo` case if the `hi` case is ready, the program I linked would never terminate.

Fair enough. But termination is not a requirement. That was just for the test code. The whole idea with a perfect priority select would, if we had it, to build the "fair algorithm" ourselves. For the disconnect and alarm cases there is only one message of each within some large time. The random select as in go might in case have caused the fire trucks to arrive when we had explicitly told not to.

The fair select (other than the random select of go, which I know the Go designers meant was "fair enough", or maybe even "fair" as they saw it) is when we have a pri select and can use it to make our own fair algorithm. No jamming, no starving. To repeat myself, the fair algorithm here would be to use a pri select and swap the order in the pri list.
 
Because `lo` is never ready unless `hi` is ready too. This, AIUI, is the priority `select` you'd want. Note, in particular, the made up `pri` keyword in the example.

Oh, if I could follow you on this one. I don't seem able to.
 
So, no, in that scenario we wouldn't have a pseudo-random choice. The question I was begging is if we could actually implement a select like you want. If you can write this program in another language, and that program ends up not terminating, that would demonstrate that it's indeed possible to write a `select` as you are requesting.

Commented the other day.
 
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?

This is… a strange question. I'm not saying "the software might be buggy, but it will be buggy software that is good enough". I'm saying "the construct is good enough to implement non-buggy software with it". Of course you need to know what the construct does and take it into account when writing your code - if you assume it works differently than it does, you'll introduce bugs, yes. That is true in any language.

Great. If expanded to "the construct is good enough to implement buggy-enough (per specification) software with it". Risk = probability * connsequence is never zero. Which is an argument against my alarm scenario. But it's the formally proven "never lo if hi" I am after.
 
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.

Can you translate the example into that language? And demonstrate that it doesn't terminate?

If I were convinced that this is it, I could do it in xC. Would have been fun. But that would have to be in the course of this summer. But I must be convinced that it does what it should. My mentioned playing at  https://play.golang.org/p/U17AbmGBZUY didn't make it easier for me.

Øyvind

Øyvind Teig

unread,
May 5, 2021, 12:58:43 PM5/5/21
to golang-nuts
Thanks, rog! (Blush.. I should have seen it and not nagged about it..) Sorry. Øyvind

Robert Engels

unread,
May 5, 2021, 2:53:45 PM5/5/21
to Øyvind Teig, golang-nuts
You are over complicating things. Start with simple code based on Ian’s. 

Still, I think you might be misunderstanding the tug between priority and starvation. It depends on the frequency and latency of events processing. There is no structure/language that can address this. You either drop or you stall - and often only drop is appropriate for safety critical systems. 

On May 5, 2021, at 11:59 AM, Øyvind Teig <oyvin...@teigfam.net> wrote:

Thanks, rog! (Blush.. I should have seen it and not nagged about it..) Sorry. Øyvind
--
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.

Øyvind Teig

unread,
May 5, 2021, 3:54:48 PM5/5/21
to golang-nuts
onsdag 5. mai 2021 kl. 20:53:45 UTC+2 skrev ren...@ix.netcom.com:
You are over complicating things. Start with simple code based on Ian’s. 


I guess I'd need help to get that pesudo code into go. Looks like pseudo code for some code generator to me, to implement the pri select. Hmm..

Still, I think you might be misunderstanding the tug between priority and starvation.

I'd hope not. I know I have been going from one to the other in my attempt at explanations. I usually go this path: if I need fair handling to avoid starvation, start with pri select then implement my own fair algorthm. The priority case with disconnect and alarm is priority only, with no requirement of any fairness. So, yes, those are two different things. 

However pri select should be one thing.
 
It depends on the frequency and latency of events processing.

If pri select depens on this then it's not the pri select I am thinking on here. That being said, as I said earlier, it's hard to make a test code case to prove things!
 
There is no structure/language that can address this.

I hope I can prove you wrong with xC. (You are triggering me to show it!) It has determinstic handling with setting up timing requirements: https://www.teigfam.net/oyvind/home/technology/209-my-xc-softblinking-pwm-notes/#timing_analysis 

Plus, scheduling of multi-logical cores on a cycle basis. There's no opsys below and there is a scheduler in the hw of the xCORE architecture. (No, I have nothing to do with XMOS!)
 
You either drop or you stall - and often only drop is appropriate for safety critical systems. 

I have related to IEC 61508 (https://en.wikipedia.org/wiki/IEC_61508) in several products over the years. Then how we answered the accreditation controllers was rather important. I'd guess that all of the answers presented here would please them. I hope, also my arguments. 

Øyvind

Jan Mercl

unread,
May 5, 2021, 4:29:50 PM5/5/21
to Øyvind Teig, golang-nuts
On Wed, May 5, 2021 at 6:56 PM Øyvind Teig <oyvin...@teigfam.net> wrote:

> hiPri is a disconnect message of a smoke detetector. loPri is a fire alarm. If the disconnect hiPri is activated before (1 sec to 1 ns) or simulatenously (same polling of "hw pins") as the alarm loPri there should be no alarm being sent to the fire department.

I think that if the correctness of some code depends on the ordering
of external/random events within a single nanosecond or less then it's
IMO probably never correct code.

I started my professional life as a HW designer. (18yo college
drop-out, only later migrated to writing SW.) What is quoted above is
called a hazard[0]. The specifications of ICs have specifications
about how much time must separate changes in inputs of a, for example,
7400 NAND gate for its output to be the negation of the boolean
product of its inputs. Otherwise the output is allowed to be
undefined. Not even just zero or one, but any (voltage) value in
between might occur. In combination with the maximum time allowed for
the gate to change and settle its output the specs allow for (at those
times tedious, pencil and paper) calculation of propagation delays in
complex circuits and detecting any hazards. Because hazards cause
chaotic behavior that is seldomly intended or welcome, usually it's
not correct/acceptable.

Your "logic circuit" depicted above has a hazard. It should not be
deployed until it is redesigned to be robust, ie. hazard-free.

[0]: https://en.wikipedia.org/wiki/Hazard_(logic)

Ian Lance Taylor

unread,
May 5, 2021, 5:17:14 PM5/5/21
to Øyvind Teig, golang-nuts
On Wed, May 5, 2021 at 9:56 AM Øyvind Teig <oyvin...@teigfam.net> wrote:
>
> Here is my cognitive test case. It is not 100% realistic, but it's just to convey my point:
> hiPri is a disconnect message of a smoke detetector. loPri is a fire alarm. If the disconnect hiPri is activated before (1 sec to 1 ns) or simulatenously (same polling of "hw pins") as the alarm loPri there should be no alarm being sent to the fire department. No emergency fire trucks. Not ever. There should not be any case of some low probability where this may happen. However, if the hiPri disconnect message was activated after the alarm, then it was too late, and the alarm will go off. (Disconnect was because we knew that there was going to be an alarm since we were doing something, and we explicitly did not want the fire trucks to come)

This description assumes that there is some notion of absolute time
that permits you to determine whether event A occurs 1ns before event
B. In a concurrent programming language like Go, with a program
running on a multi-core processor like more modern processors, there
is no absolute time. While it may be possible in principle for
someone outside the system to say that event A happened first, within
the system there is no way to determine which event happened first.
Events that occur close in time on different cores are effectively
simultaneous.

So I would say that the problem with your cognitive test is that it
misunderstands the nature of concurrent languages on multicore
systems. Unless there is an explicit synchronization event, it's
often impossible to say which event happened first.

Ian

Bakul Shah

unread,
May 5, 2021, 5:34:35 PM5/5/21
to Øyvind Teig, golang-nuts
On May 5, 2021, at 9:55 AM, Øyvind Teig <oyvin...@teigfam.net> wrote:
>
> Here is my cognitive test case. It is not 100% realistic, but it's just to convey my point:
> hiPri is a disconnect message of a smoke detetector. loPri is a fire alarm. If the disconnect hiPri is activated before (1 sec to 1 ns) or simulatenously (same polling of "hw pins") as the alarm loPri there should be no alarm being sent to the fire department. No emergency fire trucks. Not ever. There should not be any case of some low probability where this may happen. However, if the hiPri disconnect message was activated after the alarm, then it was too late, and the alarm will go off. (Disconnect was because we knew that there was going to be an alarm since we were doing something, and we explicitly did not want the fire trucks to come)

Imagine that the latency between the device detecting a disconnect
signal and a user hitting a disconnect button is D ns while the fire
detection latency is F ns. So if D > F the device would raise the
alarm even if you implement it all in hardware! The only difference
between a Go implementation vs a hardware one is the window size.
If you want to make it minimize it, Go is not the right solution.
For that, in H/W you'd probably *gate* the alarm line to the fire
department with the disconnect signal! But even so there is a small
window.

I think if you have a mix of hard and soft real time requirements,
where soft RT tasks can take a long time, you'd likely want priority
scheduling with preemption. IMHO Go is the wrong choice for that.

Robert Engels

unread,
May 5, 2021, 7:18:19 PM5/5/21
to Bakul Shah, Øyvind Teig, golang-nuts
To Ian’s point, you can try to synchronize using an external shared or multiple synced clocks - but the error is too great when comparing cpu frequency events.

> On May 5, 2021, at 4:34 PM, Bakul Shah <ba...@iitbombay.org> wrote:
> --
> 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/73C1590D-F77A-4613-B522-3DFE1A3FA0BE%40iitbombay.org.

tapi...@gmail.com

unread,
May 5, 2021, 10:27:06 PM5/5/21
to golang-nuts
older threads:

On Thursday, April 29, 2021 at 4:51:43 AM UTC-4 oyvin...@teigfam.net wrote:
I know from some years ago that go did not have any priority or ordered select construct [1].

The idea is that select always is a nondeterministic choice operator, if this is still so. Implemented with a random, I assume.

Programming user defined "fair" algorithms or patterns is then not possible, I believe.

Is this still so in Go? No prioritised or ordered select in go?

But is there still a way to code this by f.ex. combining several selects? I saw a different take at this at [2], where the select is replaced a single chan containing a chan bundle, thus becoming "deterministic".

[1] Blog note Nondeterminism (disclaimer: no ads, no gifts, only fun and expenses)

Jesper Louis Andersen

unread,
May 6, 2021, 8:29:31 AM5/6/21
to Bakul Shah, Øyvind Teig, golang-nuts
On Wed, May 5, 2021 at 11:34 PM Bakul Shah <ba...@iitbombay.org> wrote:

Imagine that the latency between the device detecting a disconnect
signal and a user hitting a disconnect button is D ns while the fire
detection latency is F ns. So if D > F the device would raise the
alarm even if you implement it all in hardware! The only difference
between a Go implementation vs a hardware  one is the window size.
If you want to make it minimize it, Go is not the right solution.
For that, in H/W you'd probably *gate* the alarm line to the fire
department with the disconnect signal! But even so there is a small
window.


There's a more contrived example which takes this argument to the extreme. It illustrates some of the problems.

Imagine you had D on Venus, and F on Mars. You receive radio signals on Earth from F and D. Due to planet orbits, this system is in constant motion, so the window constantly changes. It makes it really hard to nail down a good window, though it can be argued we can precompute the position of planets and thus compensate. However, you might have other systems where even the prediction of the window size is impossible.

Most computer systems, as Ian writes, exhibit the same window fluctuations at a far smaller scale, seemingly at random. In particular, time is not absolute in computer systems. See e.g., "There is no Now" (https://queue.acm.org/detail.cfm?id=2745385) by Justin Sheehy for an example. The writing by Sheehy also injects an important point into these discussions: impossibility results. As you add more and more distribution to a system---of which one can argue that a modern multicore system is, in fact, a distributed system---you may end up with FLP or CAP in disguise. Both these results put a wooden stake through the determinism vampire.
I don't think it is too far fetched to argue that prioritization, ordering and (non-)determinism are intertwined.


--
J.

Øyvind Teig

unread,
May 6, 2021, 9:13:20 AM5/6/21
to golang-nuts
torsdag 6. mai 2021 kl. 04:27:06 UTC+2 skrev tapi...@gmail.com:
older threads:

Thanks a lot! I'll try to have a look through them! 

Øyvind 

Øyvind Teig

unread,
May 6, 2021, 9:21:46 AM5/6/21
to golang-nuts
Of course all this apply. I guess I need to relate to them when (oops.. if) I make a test case in xC for xCORE. I was thinking about actually waiting in hi and low for two hw pins that I can exercise simultaneously or or not, from another set of pins. The xCORE polls the pins and presents them to tasks. Plus, I assume I could just try to send hi and low on channels. Each task will run on their own logical core, and the cycles run in round robin, like one for each core at a time. But in any case I (think I) know is that the xC [[ordered]] select with is interpreted once, for both (all) guards of the select, when the select is entered. I will try to write more below all the other comments.

Øyvind
 
[0]: https://en.wikipedia.org/wiki/Hazard_(logic)

Axel Wagner

unread,
May 6, 2021, 9:40:52 AM5/6/21
to golang-nuts
FWIW after all this discussion I *am* curious about a more detailed argument for why we can't have a priority select that guarantees that if the high-priority case becomes ready before the low-priority one (in the sense of "there exists a happens-before edge according to the memory model"), the high-priority will always be chosen.

That is, in the example I posted above, we do know that `hi` becoming readable happens-before `lo` becoming readable, so a true prioritized select would always choose `hi` and never return. The construct we presented does return.

Now, I do 100% agree that it's not possible to have a select that guarantees that `hi` will be read if both become readable concurrently. But I don't see a fundamental issue with having a select that always chooses `hi` if `hi` becoming readable happens-before `lo` becoming readable.

And to be clear, I also kinda like that we don't have that - I think the value provided by the pseudo-random choice in preventing starvation is worth not having an "ideal" priority select construct in the language. But I couldn't really make a good case why we can't have it.

Axel Wagner

unread,
May 6, 2021, 9:42:12 AM5/6/21
to golang-nuts
PS: And I'm not saying there is no argument. Maybe "select is not atomic" is such an argument. But if there is an argument and/or if this is that argument, I don't fully understand it myself.

Øyvind Teig

unread,
May 6, 2021, 10:06:18 AM5/6/21
to golang-nuts
Thanks for your comments. I'll try to respond to several here. They also all apply! (Even if I see while I write that two more have arrived.)

This thread seems to have taken me to places where I didn't intend to go. 

Go is no language for this kind of application, not even with a pri select. I know that. Just see how they removed rendezvous from Ada for these type of applications, for the Ravenscar profile: https://en.wikipedia.org/wiki/Ravenscar_profile "No_Select_Statements"!  (I also have a blog note about this). Just the fact that a language uses a queue for the select is a problem by itself. They are not deterministic and thus any select based on them cannot be hard real-time and safety critical. (That being said both soft real-time and queues are approved in many safety critical applications. It depends on how that usage is reasoned about.)

My interest here is purely academical.

Then, when I queried about pri select in go and the Jan Mercl's post on the almost top here set up the "select hi, default hi low", I got stuck in a way. I am still there. 

It has been said above that select is not atomic (not one window), and my query is what happens between the window of the first select and the window of the second select in that code. And what happens inside those windows. I have tried to guess in previous comments, and I thought there was a confirmation. If that confirmation really is a confirmation, then the "Mercl code" is still not a pri select that matches the pri select I was querying about.

Øyvind 

Axel Wagner

unread,
May 6, 2021, 10:18:18 AM5/6/21
to Øyvind Teig, golang-nuts
On Thu, May 6, 2021 at 4:06 PM Øyvind Teig <oyvin...@teigfam.net> wrote:
If that confirmation really is a confirmation, then the "Mercl code" is still not a pri select that matches the pri select I was querying about.

I don't believe it is. It took a while to wrap my head around it - apologies for that.

But yes, at this point I believe the specific property that is violated that you'd be interested in is as I said in my last message, the guarantee that "if the high-priority case becomes ready before (in the sense of the memory model) the low-priority case, then the high-priority case will be chosen".

That's certainly a reasonable expectation to have from a priority select and it is not a guarantee that the code we gave you, using nested selects with defaults, provides.

I believe we became hung up on the idea of what happens if the cases become ready *concurrently*. In that case, there is no real sensible answer to what any select implementation could guarantee.


Øyvind 

torsdag 6. mai 2021 kl. 14:29:31 UTC+2 skrev jesper.lou...@gmail.com:
On Wed, May 5, 2021 at 11:34 PM Bakul Shah <ba...@iitbombay.org> wrote:

Imagine that the latency between the device detecting a disconnect
signal and a user hitting a disconnect button is D ns while the fire
detection latency is F ns. So if D > F the device would raise the
alarm even if you implement it all in hardware! The only difference
between a Go implementation vs a hardware  one is the window size.
If you want to make it minimize it, Go is not the right solution.
For that, in H/W you'd probably *gate* the alarm line to the fire
department with the disconnect signal! But even so there is a small
window.


There's a more contrived example which takes this argument to the extreme. It illustrates some of the problems.

Imagine you had D on Venus, and F on Mars. You receive radio signals on Earth from F and D. Due to planet orbits, this system is in constant motion, so the window constantly changes. It makes it really hard to nail down a good window, though it can be argued we can precompute the position of planets and thus compensate. However, you might have other systems where even the prediction of the window size is impossible.

Most computer systems, as Ian writes, exhibit the same window fluctuations at a far smaller scale, seemingly at random. In particular, time is not absolute in computer systems. See e.g., "There is no Now" (https://queue.acm.org/detail.cfm?id=2745385) by Justin Sheehy for an example. The writing by Sheehy also injects an important point into these discussions: impossibility results. As you add more and more distribution to a system---of which one can argue that a modern multicore system is, in fact, a distributed system---you may end up with FLP or CAP in disguise. Both these results put a wooden stake through the determinism vampire.
I don't think it is too far fetched to argue that prioritization, ordering and (non-)determinism are intertwined.


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

roger peppe

unread,
May 6, 2021, 10:44:08 AM5/6/21
to Axel Wagner, golang-nuts
On Thu, 6 May 2021 at 14:41, 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:
PS: And I'm not saying there is no argument. Maybe "select is not atomic" is such an argument. But if there is an argument and/or if this is that argument, I don't fully understand it myself.

One reason is that the semantics can conflict. Consider this code, for example (assuming a hypothetical "pri select" statement that chooses the first ready arm of the select) - the priorities conflict. I suspect Occam doesn't encounter that issue because it only allows (or at least, it did back when I used Occam) select on input, not output. I believe that restriction was due to the difficulty of implementing bidirectional select between actual distributed hardware processors, but I'm sure Øyvind knows better.

func main() {
        c1, c2, c3 := make(chan int), make(chan int), make(chan int)

        go func() {
                pri select {
                case c1 <- 1:
                case v := <-c2:
                        c3 <- v
                }
        }()
        go func() {
                pri select {
                case c2 <- 2:
                case v := <-c1:
                        c3 <- v
                }
        }()
        fmt.Println(<-c3)
}

That said, I suspect that the semantics could be ironed out, and the real reason for Go's lack is that it's not actually that useful; that it would be one more feature; and that in practice a random choice makes sense almost all the time.


On Thu, May 6, 2021 at 3:40 PM Axel Wagner <axel.wa...@googlemail.com> wrote:
FWIW after all this discussion I *am* curious about a more detailed argument for why we can't have a priority select that guarantees that if the high-priority case becomes ready before the low-priority one (in the sense of "there exists a happens-before edge according to the memory model"), the high-priority will always be chosen.

That is, in the example I posted above, we do know that `hi` becoming readable happens-before `lo` becoming readable, so a true prioritized select would always choose `hi` and never return. The construct we presented does return.

Now, I do 100% agree that it's not possible to have a select that guarantees that `hi` will be read if both become readable concurrently. But I don't see a fundamental issue with having a select that always chooses `hi` if `hi` becoming readable happens-before `lo` becoming readable.

And to be clear, I also kinda like that we don't have that - I think the value provided by the pseudo-random choice in preventing starvation is worth not having an "ideal" priority select construct in the language. But I couldn't really make a good case why we can't have 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...@googlegroups.com.

Axel Wagner

unread,
May 6, 2021, 11:28:14 AM5/6/21
to roger peppe, golang-nuts
On Thu, May 6, 2021 at 4:43 PM roger peppe <rogp...@gmail.com> wrote:

On Thu, 6 May 2021 at 14:41, 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:
PS: And I'm not saying there is no argument. Maybe "select is not atomic" is such an argument. But if there is an argument and/or if this is that argument, I don't fully understand it myself.

One reason is that the semantics can conflict. Consider this code, for example (assuming a hypothetical "pri select" statement that chooses the first ready arm of the select) - the priorities conflict. I suspect Occam doesn't encounter that issue because it only allows (or at least, it did back when I used Occam) select on input, not output. I believe that restriction was due to the difficulty of implementing bidirectional select between actual distributed hardware processors, but I'm sure Øyvind knows better.

func main() {
        c1, c2, c3 := make(chan int), make(chan int), make(chan int)

        go func() {
                pri select {
                case c1 <- 1:
                case v := <-c2:
                        c3 <- v
                }
        }()
        go func() {
                pri select {
                case c2 <- 2:
                case v := <-c1:
                        c3 <- v
                }
        }()
        fmt.Println(<-c3)
}

Interesting case. I would argue, though, that there is no happens-before edge here to order the cases and I was only considering providing a guarantee if there is one.
 
That said, I suspect that the semantics could be ironed out, and the real reason for Go's lack is that it's not actually that useful; that it would be one more feature; and that in practice a random choice makes sense almost all the time.

As I said, this would certainly satisfy me as an answer :)

Robert Engels

unread,
May 6, 2021, 1:32:53 PM5/6/21
to Axel Wagner, roger peppe, golang-nuts
I already showed you - just change it to 

Select hi
Default:
    Select hi,lo
If lo:
    Select hi
    Default :
          Pass

And enqueue the lo if a hi and lo are read. 

That is all that is needed. 



On May 6, 2021, at 10:28 AM, 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:



Axel Wagner

unread,
May 6, 2021, 1:37:29 PM5/6/21
to golang-nuts
No, it is not. Your "if lo" branch implies that the communication happened - e.g. the sender was already unblocked. A `select` would not unblock the other side unless that's the actual branch taken.

Robert Engels

unread,
May 6, 2021, 2:22:29 PM5/6/21
to Axel Wagner, golang-nuts
“If lo” means that if the lo channel was read. 

This code will prevent a lo from being processed if a hi is available at the happens before moment of a value being ready. 

That moment is somewhat arbitrary so it is only mildly different than 

Select hi:
   Default:
      Select hi
      Select lo

Btw using indents rather than brackets in the above - maybe that is causing the confusion. 
      


On May 6, 2021, at 12:37 PM, 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:



Axel Wagner

unread,
May 6, 2021, 2:30:59 PM5/6/21
to Robert Engels, golang-nuts
On Thu, May 6, 2021 at 8:22 PM Robert Engels <ren...@ix.netcom.com> wrote:
“If lo” means that if the lo channel was read. 

Exactly. To fulfill the requirements and answering the question, it must not be read.

This code will prevent a lo from being processed if a hi is available at the happens before moment of a value being ready. 

What the receiver does with the value is immaterial. Point is, that the receiver has already read the value, thus the communication has happened, thus the sender was unblocked. The question is about a select that wouldn't do that.
 
Btw using indents rather than brackets in the above - maybe that is causing the confusion. 

I'm not confused. Your code is simply not answering the question posed. Which is about a select which always lets the high priority communication happen, if it is ready before the low priority communication - and consequently *doesn't* let the low priority communication happen.

Robert Engels

unread,
May 6, 2021, 3:41:11 PM5/6/21
to Axel Wagner, golang-nuts
But that is not really true because there are no constraints on if the source channels are buffered - if they are then my code operates similarly. 

Even if using unbuffered channels there is buffering being done at a lower level (hardware buffers, network stack buffers, etc) - so not “unblocking a sender” is a dubious endeavor. 

On May 6, 2021, at 1:30 PM, 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:



Axel Wagner

unread,
May 6, 2021, 4:06:18 PM5/6/21
to golang-nuts
On Thu, May 6, 2021 at 9:40 PM Robert Engels <ren...@ix.netcom.com> wrote:
But that is not really true because there are no constraints on if the source channels are buffered - if they are then my code operates similarly. 

I was very clear. I was asking if it is possible to implement a priority select with the semantics "if the high priority case becomes ready before the low priority case, it always takes the high priority case". Saying "but what if we try to ensure that both of them are always ready" is not answering the question.
Please stop insisting that the code you provide solves this. It simply doesn't. Given that I phrased the question, I feel justified in claiming the authority if it does or not.
 
Even if using unbuffered channels there is buffering being done at a lower level (hardware buffers, network stack buffers, etc) - so not “unblocking a sender” is a dubious endeavor. 

That is how select behaves, though. It chooses a communication to proceed (currently, uniformly at random, under the premise of the question, the highest priority one) and lets that proceed.

If you don't have an answer to the question I posed, it is okay to just not answer it. If there is no answer, that's okay too. But arguing about code which clearly does not answer it is frustrating.

Peter Wilson

unread,
May 6, 2021, 4:08:31 PM5/6/21
to golang-nuts
Back in the days of transputers and occam, there was a desire to be able to manage all interesting events in a system in a within-language (language being occam) manner.
Interrupts were a problem, because you can't describe interrupts as implemented by microprocessors (steal the PC and jump somewhere, saving minimal state) in a language which doesn't discuss stealing the PC nor what minimal state might be.

So there were two scenarios handled.

In one scenario, you created a high-priority process (occam had priorities) and had it wait on a hardware channel. If a signal arrived from hardware which would normally interrupt (in a classic microprocessor), it delivered a message to the hardware channel, and the waiting process work up pre-empting the execution of any currently-executing lower-priority process. This is a close approximation to the behaviour of classic device interrupts with the limitation of a single level of interrupt priority, the latter being imposed by the implementation of the transputers, not the language. This works fine if the high priority process is completely 'individualistic', and doesn't need to tell other processes anything (because then you fall direct into the second scenario, albeit in another process). 

In the other scenario, you had what we might look upon as sorta an object which got asked to do different sorts of things. All the requests arrived by messages on separate (unbuffered at the time) channels. The PRI ALT simply said that for one reason or another, if requests arrived on several channels while the process was busy doing other stuff, then it must choose to service the highest priority channel. It was still up to the software designer to be sure that the time the process was busy was not so long that the priority was useless.

So to model classic prioritised interrupts, you would consider than handling an interrupt - classically, someone mashes the Big Red Button on a software controlled black box implemented by a number of communicating processes, requiring it to stop as close to Right Now as possible - as a message to a high-priority process, which would perform any immediate, time-critical operation (turning off the electricity to the black box?) and then send a message to a lower priority process in charge of the general state of the black box to tidy up internal state. Then you really want there to be a PRI ALT, because the black box isn't running any more and handling useless messages from prior 'clients' is just silly - you want the 'big red button mashed' message to be taken in preference to anything else.

And the dual notions of process priority and select priority work together well to make it clear what the designer's intents were. Such transparency is valuable.

It can be argued that go isn't and wasn't ever intended to deal with such scenarios, and so the provision of priorities in goroutines and selects  is not an interesting capability. 

Axel Wagner

unread,
May 6, 2021, 4:15:14 PM5/6/21
to golang-nuts
To clarify again: As a litmus test, a `select` construct like the one I'm talking about would mean that this code blocks forever:
With the current `select`, it doesn't. With a different `select`, which uses source order to express priority and under the semantics I'm asking about, this would always block, because `lo` would never be read.

Robert Engels

unread,
May 6, 2021, 5:38:57 PM5/6/21
to Axel Wagner, golang-nuts
Yes, but barring the nanosecs of a window this is simply implemented as Ian wrote with

Select hi
Default:
   Select hi,lo

If both channels are ready when the code is entered the high will always be taken. 

There is no such thing as simultaneous source events - even the first that occurred in external observed time might arrive at the controller later than the second. You need full hardware and OS support to even begin to minimize this possibility. Unless you have a full RTS this is the best you will do with any software based solution. 

On May 6, 2021, at 3:15 PM, 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:



Axel Wagner

unread,
May 6, 2021, 6:12:39 PM5/6/21
to golang-nuts
On Thu, May 6, 2021 at 11:38 PM Robert Engels <ren...@ix.netcom.com> wrote:
Yes, but barring the nanosecs of a window this is simply implemented as Ian wrote with

Select hi
Default:
   Select hi,lo

No, it is not. "Barring a nanosecond" is not a guarantee. And that this is not actually doing what I'm asking is the entire start of my inquiry.
 
Again: "It can't be implemented" is a valid answer to the question, though I'm specifically asking for details why. Posting code which doesn't do it, is not an answer.

If both channels are ready when the code is entered the high will always be taken.

But not if they are not both ready when the code is entered. Again, I was very specific about the guarantee I'm asking about: "If `hi` becomes ready before `lo` (in the sense of the memory model happens-before relationship), then the `hi` case should always be taken".
 
There is no such thing as simultaneous source events

I am specifically talking about *non* simultaneous events. I am specifically talking about causally ordered events with a well-defined order, according to the memory model. And I specifically acknowledged (and originally pointed out) the impossibility to even assign meaning to the question in the context of concurrent events.

I am specifically *not* asking about any guarantees in the case where the two events are concurrent. *Neither* about the low-priority communication becoming ready before the high priority one. I am exclusively talking about the situation where it can be proven that the high-priority event happens before the low priority one - as is the case in the example I posted.

Again: If you don't have an answer, it is fine to not respond. If you don't know if it's possible to implement a `select` statement with these semantics - or why it isn't - you don't have an answer. The point of my question is pure curiosity. I'm not suggesting that we add a construct like this or arguing it is needed or saying that I want it. I'm only curious if it could be done. So there is absolutely nothing lost by not getting an answer and there is absolutely nothing gained by trying to convince me a non-answer actually is one.

Sorry to be so blunt, but this interaction is very frustrating.

Robert Engels

unread,
May 6, 2021, 7:12:03 PM5/6/21
to Axel Wagner, golang-nuts


On May 6, 2021, at 5:12 PM, 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:


On Thu, May 6, 2021 at 11:38 PM Robert Engels <ren...@ix.netcom.com> wrote:
Yes, but barring the nanosecs of a window this is simply implemented as Ian wrote with

Select hi
Default:
   Select hi,lo

No, it is not. "Barring a nanosecond" is not a guarantee. And that this is not actually doing what I'm asking is the entire start of my inquiry.
 
Again: "It can't be implemented" is a valid answer to the question, though I'm specifically asking for details why. Posting code which doesn't do it, is not an answer.

If both channels are ready when the code is entered the high will always be taken.

But not if they are not both ready when the code is entered. Again, I was very specific about the guarantee I'm asking about: "If `hi` becomes ready before `lo` (in the sense of the memory model happens-before relationship), then the `hi` case should always be taken".
 
Happens before is only valid under the context of synchronization. 

While under the synchronized check it is trivial to check the channels in order rather than pseudo randomly. 


There is no such thing as simultaneous source events

I am specifically talking about *non* simultaneous events. I am specifically talking about causally ordered events with a well-defined order, according to the memory model. And I

Again, ordering is only based on synchronization. The synchronization occurs when determining which channels are ready (and when the channel is mutated)


specifically acknowledged (and originally pointed out) the impossibility to even assign meaning to the question in the context of concurrent events.

I am specifically *not* asking about any guarantees in the case where the two events are concurrent. *Neither* about the low-priority communication becoming ready before the high priority one. I am exclusively talking about the situation where it can be proven that the high-priority event happens before the low priority one - as is the case in the example I posted.


This example you give is trivial. Just remove the randomizer from the channel selector and synchronize around all channels (global channel lock) in the select. 

Then it will fail to exit. 

Again: If you don't have an answer, it is fine to not respond. If you don't know if it's possible to implement a `select` statement with these semantics - or why it isn't - you don't have an answer. The point of my question is pure curiosity. I'm not suggesting that we add a construct like this or arguing it is needed or saying that I want it. I'm only curious if it could be done. So there is absolutely nothing lost by not getting an answer and there is absolutely nothing gained by trying to convince me a non-answer actually is one.

Sorry to be so blunt, but this interaction is very frustrating.

I do have an answer and I’ve been very straightforward and rational. I’ve implemented device drivers for numerous pieces of hardware and designed circuits as well. Your thinking about some global order provided by the memory model is incorrect. (If there were - multi process   computers would be horribly inefficient). You can implement global ordering among channels by having a common sync/lock point - but that slows things considerably. 

I’m sorry you’re frustrated but I think that’s on you. 




Robert Engels

unread,
May 6, 2021, 7:34:22 PM5/6/21
to Axel Wagner, golang-nuts
To simply this :your request is easily accommodated if all channel state changes and all selects are synchronized. This is easily doable but would crush performance. 

On May 6, 2021, at 6:11 PM, Robert Engels <ren...@ix.netcom.com> wrote:



Ian Lance Taylor

unread,
May 6, 2021, 10:10:42 PM5/6/21
to Axel Wagner, golang-nuts
I believe that we could implement a select statement that supports
priority cases, such that when multiple cases are ready, and at least
one is a priority case, then we would always choose one of the
priority cases.

The reason we don't have such a feature is not because of
implementation difficulty. It's because the feature isn't needed, and
because, as this thread indicates, it tends to confuse people. In
particular it's easy for people to be misled into thinking that if a
low priority case is chosen then at that point none of the high
priority cases can be ready, but of course that is false (as the high
priority case may have become ready in the span of time between
choosing the low priority case and starting to execute the associated
statements).

Ian

Axel Wagner

unread,
May 7, 2021, 2:05:35 AM5/7/21
to Ian Lance Taylor, golang-nuts
Thank you :)

Øyvind Teig

unread,
May 7, 2021, 3:29:40 AM5/7/21
to golang-nuts
torsdag 6. mai 2021 kl. 16:18:18 UTC+2 skrev axel.wa...@googlemail.com:
On Thu, May 6, 2021 at 4:06 PM Øyvind Teig <oyvin...@teigfam.net> wrote:
If that confirmation really is a confirmation, then the "Mercl code" is still not a pri select that matches the pri select I was querying about.

I don't believe it is. It took a while to wrap my head around it - apologies for that.

Since it looks like this is a thread with "us talking with each other" and not "me discussing with you" I will try to comment in line for all where it would be applicable, in the view that it's you who know what Go does. 16 new messages since I was here last time! (I only handle this at intervals, so that I can get some time with other things as well!-) 

But this one certainly needs a comment! No need to apologise! But I starting to get tired of myself hammering that I did not understand how select-hi-default-select-hi-low could possible work the way it was presented to work. I am indeed excited to read the next 16 messages, to see if that (now double) doubt still holds. But you made my day, Axel, I must admit that!

But yes, at this point I believe the specific property that is violated that you'd be interested in is as I said in my last message, the guarantee that "if the high-priority case becomes ready before (in the sense of the memory model) the low-priority case, then the high-priority case will be chosen".

That's certainly a reasonable expectation to have from a priority select and it is not a guarantee that the code we gave you, using nested selects with defaults, provides.

I believe we became hung up on the idea of what happens if the cases become ready *concurrently*. In that case, there is no real sensible answer to what any select implementation could guarantee.

Very interesting reading!

Øyvind 

Øyvind Teig

unread,
May 7, 2021, 4:01:28 AM5/7/21
to golang-nuts
torsdag 6. mai 2021 kl. 16:44:08 UTC+2 skrev rog:
On Thu, 6 May 2021 at 14:41, 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:
PS: And I'm not saying there is no argument. Maybe "select is not atomic" is such an argument. But if there is an argument and/or if this is that argument, I don't fully understand it myself.

One reason is that the semantics can conflict. Consider this code, for example (assuming a hypothetical "pri select" statement that chooses the first ready arm of the select) - the priorities conflict. I suspect Occam doesn't encounter that issue because it only allows (or at least, it did back when I used Occam) select on input, not output. I believe that restriction was due to the difficulty of implementing bidirectional select between actual distributed hardware processors, but I'm sure Øyvind knows better.

This is exactly how I have understood it too. Neither occam nor xC has output guards. Like Go does not have pri select, we'd we have to live with it. There are reasons. For the transputer (and the xCORE grandchild) it's multi-core and then the protocolling for also having output guards, they said, had been more complicated that the need for this. It may be simulated. But they did introduce something very intersting for some prospective occam  (which never was implemented), which was extended input ("??") and output ("!!") primitives. Prof Peter Welch "used" them to prove my "XCHAN" in https://www.cs.kent.ac.uk/research/groups/plas/wiki/An_occam_Model_of_XCHANs. I think they basically bind the other side of the channel to guarantee the ALT for that special input or output the next time. (If yo ask more I'll have to refresh it..)

Aside: I have also sat through severeal dicussion on whether it was the tasks or the messaging that should be prioritised. Occam had two task priorities where one was thought of for "drivers". It did in theory at least have both ALT and PRI ALT. xC/xCORE has no task priorities, but they have like  2 * 8 = 16 logical cores and a scheme to handle (even guarateed by time limits) deterministic timing, so virtually everything is a potential "interrupt". As far as I remember, all these discussion ended up with some agreement that it was the pri select that was to be chosed over pri par.

func main() {
        c1, c2, c3 := make(chan int), make(chan int), make(chan int)

        go func() {
                pri select {
                case c1 <- 1:
                case v := <-c2:
                        c3 <- v
                }
        }()
        go func() {
                pri select {
                case c2 <- 2:
                case v := <-c1:
                        c3 <- v
                }
        }()
        fmt.Println(<-c3)
}

That said, I suspect that the semantics could be ironed out, and the real reason for Go's lack is that it's not actually that useful; that it would be one more feature; and that in practice a random choice makes sense almost all the time.

I guess so too. Rob Pike, are you there?

This one prints 1 or 2: https://play.golang.org/p/QfiPsh6udgz I cant' twist my head to see what two pri selects might print? 

Øyvind

Øyvind Teig

unread,
May 7, 2021, 12:24:56 PM5/7/21
to golang-nuts
torsdag 6. mai 2021 kl. 16:44:08 UTC+2 skrev rog:
On Thu, 6 May 2021 at 14:41, 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:
PS: And I'm not saying there is no argument. Maybe "select is not atomic" is such an argument. But if there is an argument and/or if this is that argument, I don't fully understand it myself.

One reason is that the semantics can conflict. Consider this code, for example (assuming a hypothetical "pri select" statement that chooses the first ready arm of the select) - the priorities conflict. I suspect Occam doesn't encounter that issue because it only allows (or at least, it did back when I used Occam) select on input, not output. I believe that restriction was due to the difficulty of implementing bidirectional select between actual distributed hardware processors, but I'm sure Øyvind knows better.

func main() {
        c1, c2, c3 := make(chan int), make(chan int), make(chan int)

        go func() {
                pri select {
                case c1 <- 1:
                case v := <-c2:
                        c3 <- v
                }
        }()
        go func() {
                pri select {
                case c2 <- 2:
                case v := <-c1:
                        c3 <- v
                }
        }()
        fmt.Println(<-c3)
}

Without the assumed pri select the above it is the same as https://en.wikipedia.org/wiki/Promela#Executability. I have stared a lot on that one almost not believing my eyes when it didn't deadlock. The text emphasises that there are "non-deterministic choices" but I don't think we foresaw any pri choice. (I got some help from Holzmann to do some of the text in that chapter). I assume you would say a pri select there would cause a deadlock? It probably would, yes.

Øyvind

Øyvind Teig

unread,
May 7, 2021, 12:40:48 PM5/7/21
to golang-nuts
torsdag 6. mai 2021 kl. 20:30:59 UTC+2 skrev axel.wa...@googlemail.com:
On Thu, May 6, 2021 at 8:22 PM Robert Engels <ren...@ix.netcom.com> wrote:
“If lo” means that if the lo channel was read. 

Exactly. To fulfill the requirements and answering the question, it must not be read.

This code will prevent a lo from being processed if a hi is available at the happens before moment of a value being ready. 

What the receiver does with the value is immaterial. Point is, that the receiver has already read the value, thus the communication has happened, thus the sender was unblocked. The question is about a select that wouldn't do that.
 
Btw using indents rather than brackets in the above - maybe that is causing the confusion. 

I'm not confused. Your code is simply not answering the question posed. Which is about a select which always lets the high priority communication happen, if it is ready before the low priority communication - and consequently *doesn't* let the low priority communication happen.

This one of the difficult things with implementing a select. I have implemented several, for CSP-based run-time systems that we used for small controllers. I guess that's why they, in the world I come from talk about (1) set-up of select (to see if any is ready at that time, if so pick out one, pri or not pri. Several may have "their bits" set at that time), if not then (2) wait in the select until one event happes (input, port, timeout and for some output) and (3) tear-down the select when it's being triggered, at when any other side that is also waiting is put back on the select as a precond for the next time. It's easy to forget to put the others back on the select (ie. don't touch them). It we don't we'll just deadlock or the other part believes that the action (input or output) did happen when it didn't. That would depend on how it's coded I gues. It is unsafe to let the user control any queue, because much of the idea with CSP is that we have "WYSIWYG semantics" (A term by Peter Welch, UofKent, UK (emeritus)). In order to understand the code in a task, all we look at is the channel usage and the protocol. Not what the other task(s) do.

Øyvind

Øyvind Teig

unread,
May 7, 2021, 12:51:42 PM5/7/21
to golang-nuts
torsdag 6. mai 2021 kl. 21:41:11 UTC+2 skrev ren...@ix.netcom.com:
But that is not really true because there are no constraints on if the source channels are buffered - if they are then my code operates similarly. 

Even if using unbuffered channels there is buffering being done at a lower level (hardware buffers, network stack buffers, etc) - so not “unblocking a sender” is a dubious endeavor. 

For a [0] dim unbuffered chan there should be no need for any buffer, unless (as you say, there is some network in between). Basically a channel consists of which task was "first" on it, what it wants to do and a pointer to the data and the len, when the first part is descheduled until after the second part on the channel is ready, the action is done (a memcpy in the correct direction, from local data inside one task to local data in the other task, this is 100% safe and there is no need for semaphores etc. to protect anything) and the first part is set to become rescheduled. This means that a synchronous unbufferd channel has no buffer and no queue for the data. And as Rob Pike said "Now for those experts in the room who know about buffered channels in Go – which exist – you can create a channel with a buffer. And buffered channels have the property that they don’t synchronize when you send, because you can just drop a value in the buffer and keep going. So they have different properties. And they’re kind of subtle. They’re very useful for certain problems, but you don’t need them. And we’re not going to use them at all in our examples today, because I don’t want to complicate life by explaining them.” (https://www.youtube.com/watch?v=f6kdp27TYZs)

Øyvind

Øyvind Teig

unread,
May 7, 2021, 2:20:05 PM5/7/21
to golang-nuts
torsdag 6. mai 2021 kl. 22:08:31 UTC+2 skrev Peter Wilson:
Back in the days of transputers and occam, there was a desire to be able to manage all interesting events in a system in a within-language (language being occam) manner.
Interrupts were a problem, because you can't describe interrupts as implemented by microprocessors (steal the PC and jump somewhere, saving minimal state) in a language which doesn't discuss stealing the PC nor what minimal state might be.

So there were two scenarios handled.

In one scenario, you created a high-priority process (occam had priorities) and had it wait on a hardware channel. If a signal arrived from hardware which would normally interrupt (in a classic microprocessor), it delivered a message to the hardware channel, and the waiting process work up pre-empting the execution of any currently-executing lower-priority process. This is a close approximation to the behaviour of classic device interrupts with the limitation of a single level of interrupt priority, the latter being imposed by the implementation of the transputers, not the language. This works fine if the high priority process is completely 'individualistic', and doesn't need to tell other processes anything (because then you fall direct into the second scenario, albeit in another process). 

In the other scenario, you had what we might look upon as sorta an object which got asked to do different sorts of things. All the requests arrived by messages on separate (unbuffered at the time) channels. The PRI ALT simply said that for one reason or another, if requests arrived on several channels while the process was busy doing other stuff, then it must choose to service the highest priority channel. It was still up to the software designer to be sure that the time the process was busy was not so long that the priority was useless.

So to model classic prioritised interrupts, you would consider than handling an interrupt - classically, someone mashes the Big Red Button on a software controlled black box implemented by a number of communicating processes, requiring it to stop as close to Right Now as possible - as a message to a high-priority process, which would perform any immediate, time-critical operation (turning off the electricity to the black box?) and then send a message to a lower priority process in charge of the general state of the black box to tidy up internal state. Then you really want there to be a PRI ALT, because the black box isn't running any more and handling useless messages from prior 'clients' is just silly - you want the 'big red button mashed' message to be taken in preference to anything else.

And the dual notions of process priority and select priority work together well to make it clear what the designer's intents were. Such transparency is valuable.

It can be argued that go isn't and wasn't ever intended to deal with such scenarios, and so the provision of priorities in goroutines and selects  is not an interesting capability. 

Thanks for the summary! I do recognise the scenarios. But from an acadamic point of view I think Go is indeed interesting simply because <a href="https://golang.org/doc/faq#csp">Why build concurrency on the ideas of CSP?</a>. It's interesting to see xC/xCORE in view of your discussion. It's designed by some of the same people with many of the problems you describe in mind.

Øyvind

Øyvind Teig

unread,
May 7, 2021, 2:48:46 PM5/7/21
to golang-nuts
torsdag 6. mai 2021 kl. 22:15:14 UTC+2 skrev axel.wa...@googlemail.com:
To clarify again: As a litmus test, a `select` construct like the one I'm talking about would mean that this code blocks forever:
With the current `select`, it doesn't. With a different `select`, which uses source order to express priority and under the semantics I'm asking about, this would always block, because `lo` would never be read.

I don't know if one would use a pri select to pick up channels from the same task. Here's a mod that seems to behave wildly differently when the channels are signalled from one task each and those two tasks are swapped in order. How may that be explained? I would have suggested the same log trail for both: https://play.golang.org/p/lJA0XPWtj-w 

Øyvind

Øyvind Teig

unread,
May 7, 2021, 3:10:29 PM5/7/21
to golang-nuts
fredag 7. mai 2021 kl. 04:10:42 UTC+2 skrev Ian Lance Taylor:
On Thu, May 6, 2021 at 6:40 AM 'Axel Wagner' via golang-nuts
<golan...@googlegroups.com> wrote:
>
> FWIW after all this discussion I *am* curious about a more detailed argument for why we can't have a priority select that guarantees that if the high-priority case becomes ready before the low-priority one (in the sense of "there exists a happens-before edge according to the memory model"), the high-priority will always be chosen.
>
> That is, in the example I posted above, we do know that `hi` becoming readable happens-before `lo` becoming readable, so a true prioritized select would always choose `hi` and never return. The construct we presented does return.
>
> Now, I do 100% agree that it's not possible to have a select that guarantees that `hi` will be read if both become readable concurrently. But I don't see a fundamental issue with having a select that always chooses `hi` if `hi` becoming readable happens-before `lo` becoming readable.
>
> And to be clear, I also kinda like that we don't have that - I think the value provided by the pseudo-random choice in preventing starvation is worth not having an "ideal" priority select construct in the language. But I couldn't really make a good case why we can't have it.

I believe that we could implement a select statement that supports
priority cases, such that when multiple cases are ready, and at least
one is a priority case, then we would always choose one of the
priority cases.

The reason we don't have such a feature is not because of
implementation difficulty. It's because the feature isn't needed,

..I hope you mean "isn't needed in Go"? 

There are at least the two cases, which I think that you would say would not pertain to Go (fair enough!)
(1) priority of one select case over another (which in the non-Go example might be exemplified as an alternative to prioritised interrupts, which much HW find useful, even necessary)
(2) a means to enable the programmer to design his/her own "fair" handling in servers, of clients (but for Go "fair" is always random/nondeterministic).
 
and
because, as this thread indicates, it tends to confuse people.

I think the main reason for the confusion was that many tried to understand the select-pri-default-select-hi-lo code example? Or is this some "idiomatic Go confusion"?
 
In
particular it's easy for people to be misled into thinking that if a
low priority case is chosen then at that point none of the high
priority cases can be ready, but of course that is false (as the high
priority case may have become ready in the span of time between
choosing the low priority case and starting to execute the associated
statements).

Exactly!

Øyvind
Enough of me for now.
 

Ian

Axel Wagner

unread,
May 7, 2021, 3:10:39 PM5/7/21
to Øyvind Teig, golang-nuts
On Fri, May 7, 2021 at 8:49 PM Øyvind Teig <oyvin...@teigfam.net> wrote:
I don't know if one would use a pri select to pick up channels from the same task. Here's a mod that seems to behave wildly differently when the channels are signalled from one task each and those two tasks are swapped in order. How may that be explained? I would have suggested the same log trail for both: https://play.golang.org/p/lJA0XPWtj-w 

It does seem to make a difference, but that's mainly due to coincidences of the implementation. I assume it has something to do with how the newly created goroutines are scheduled - you do start one after the other and maybe, for some implementation specific detail, it tends to schedule the last one first.

Either way, you can't rely on that behavior. From a pure spec and memory model POV, both programs provide you the same behavioral guarantees.

 

Øyvind Teig

unread,
May 7, 2021, 3:20:35 PM5/7/21
to golang-nuts
fredag 7. mai 2021 kl. 21:10:39 UTC+2 skrev axel.wa...@googlemail.com:
On Fri, May 7, 2021 at 8:49 PM Øyvind Teig <oyvin...@teigfam.net> wrote:
I don't know if one would use a pri select to pick up channels from the same task. Here's a mod that seems to behave wildly differently when the channels are signalled from one task each and those two tasks are swapped in order. How may that be explained? I would have suggested the same log trail for both: https://play.golang.org/p/lJA0XPWtj-w 

It does seem to make a difference, but that's mainly due to coincidences of the implementation. I assume it has something to do with how the newly created goroutines are scheduled - you do start one after the other and maybe, for some implementation specific detail, it tends to schedule the last one first.

Either way, you can't rely on that behavior. From a pure spec and memory model POV, both programs provide you the same behavioral guarantees.

Agree. But if a behavioural guarantee doesn't behave, then it leaves me just staring out on the sky that's blue 35 minutes more..

Øyvind

Ian Lance Taylor

unread,
May 8, 2021, 8:02:37 AM5/8/21
to Øyvind Teig, golang-nuts
On Fri, May 7, 2021, 3:10 PM Øyvind Teig <oyvin...@teigfam.net> wrote:

fredag 7. mai 2021 kl. 04:10:42 UTC+2 skrev Ian Lance Taylor:

The reason we don't have such a feature is not because of
implementation difficulty. It's because the feature isn't needed,

..I hope you mean "isn't needed in Go"? 

I am only talking about Go.


and
because, as this thread indicates, it tends to confuse people.

I think the main reason for the confusion was that many tried to understand the select-pri-default-select-hi-lo code example? Or is this some "idiomatic Go confusion"?

I think this thread has had many different confusions.

Ian

Øyvind Teig

unread,
May 8, 2021, 10:51:19 AM5/8/21
to golang-nuts
lørdag 8. mai 2021 kl. 14:02:37 UTC+2 skrev Ian Lance Taylor:
On Fri, May 7, 2021, 3:10 PM Øyvind Teig <oyvin...@teigfam.net> wrote:

fredag 7. mai 2021 kl. 04:10:42 UTC+2 skrev Ian Lance Taylor:

The reason we don't have such a feature is not because of
implementation difficulty. It's because the feature isn't needed,

..I hope you mean "isn't needed in Go"? 

I am only talking about Go.

Thanks. Go, no surprise, on golang-nuts:-) I have brought in occam/transputer and xC/xCORE some times when I thought it relevant, which.... 

and
because, as this thread indicates, it tends to confuse people.

I think the main reason for the confusion was that many tried to understand the select-pri-default-select-hi-lo code example? Or is this some "idiomatic Go confusion"?

I think this thread has had many different confusions.
 
.... I guess might have increased the mean confusion here. 

However, I would also like to thank for all the very qualified posts! There is more of them than confusion, I think. And for all the time spent!

It's not relevant to draw up the whole textbook each time, which also adds to the confusion. Since I won't apologise, I guess some of the confusion may be "as expected". I guess this goes both ways.

I hope not only I have learned something, though. Like Go does not have "pri select" and in the Go world it's considered "not necessary" (also after all these years, which started my query). Plus the select-hi-default-select-hi-low is not a fast track pattern to "pri select". However, a pattern build on reflect was shown, but not much discussed.

If I do something in xC for xCORE showing an example where it's so nice that I may have trouble keeping it to myself, I may be back with a new thread. But even then the I must consider the relevance on golang-nuts !-) 


Ian

Haddock

unread,
May 12, 2021, 3:40:36 AM5/12/21
to golang-nuts
I once implemented something to solve the same problem in Java. So I have a high priority queue (hq) and a low priority queue (lq). Whenever an item is atted to the hq a token is also added to some associated high priority token queue (htq). Same for the lq and ltq.

Some thread or goroutine takes tokens from the htq as long as in contains tokens. You can add a count so that after any n tokens taken from the htq the ltq is checked whether it contains a token.

Works fine until both, htp and ltp, are empty. You don't want to iterate over htp and ltp all the time till one contains a token again. So I introduced a semaphore on which the thread serving all these queues would be blocked till htq ot ltq recevie a new token.

I thought that the sempahore would slow things down. So I did measurements with a bare bone concurrent queue and the priority queue. The difference in time to serve n tokens in htq and m tokens in ltq was very small also for high values of n and m.

oyvin...@teigfam.net schrieb am Donnerstag, 29. April 2021 um 10:51:43 UTC+2:
I know from some years ago that go did not have any priority or ordered select construct [1].

The idea is that select always is a nondeterministic choice operator, if this is still so. Implemented with a random, I assume.

Programming user defined "fair" algorithms or patterns is then not possible, I believe.

Is this still so in Go? No prioritised or ordered select in go?

But is there still a way to code this by f.ex. combining several selects? I saw a different take at this at [2], where the select is replaced a single chan containing a chan bundle, thus becoming "deterministic".

[1] Blog note Nondeterminism (disclaimer: no ads, no gifts, only fun and expenses)

Brian Candler

unread,
May 12, 2021, 4:34:31 AM5/12/21
to golang-nuts
On Wednesday, 12 May 2021 at 08:40:36 UTC+1 Haddock wrote:
I once implemented something to solve the same problem in Java. So I have a high priority queue (hq) and a low priority queue (lq). Whenever an item is atted to the hq a token is also added to some associated high priority token queue (htq). Same for the lq and ltq.

Some thread or goroutine takes tokens from the htq as long as in contains tokens. You can add a count so that after any n tokens taken from the htq the ltq is checked whether it contains a token.

Works fine until both, htp and ltp, are empty. You don't want to iterate over htp and ltp all the time till one contains a token again. So I introduced a semaphore on which the thread serving all these queues would be blocked till htq ot ltq recevie a new token.

I thought that the sempahore would slow things down. So I did measurements with a bare bone concurrent queue and the priority queue. The difference in time to serve n tokens in htq and m tokens in ltq was very small also for high values of n and m.

I think you'll enjoy this video by Rob Pike:

Great ways to handle this stuff robustly using Go channels instead of low-level synchronization primatives like semaphores.  First time watching, I had to keep my finger on the pause button to make sure I understood each screenful of code before he moved on :-)

Haddock

unread,
May 12, 2021, 7:00:02 AM5/12/21
to golang-nuts
In addition to htq and ltq you have a third queue  into which you also insert a token once one has been added to htq or ltp. The thread/goroutine that serves htq, ltp, hq, lq is blocked by this additional queue. When it is empty, htq and ltq are also empty. So when the goroutine is blocked it is fine in this case. This sound like this could be it :-)

Haddock

unread,
May 12, 2021, 10:52:19 AM5/12/21
to golang-nuts
In addition to htq and ltq you have a third queue  into which you also insert a token once one has been added to htq or ltp. The thread/goroutine that serves htq, ltp, hq, lq is blocked by this additional queue. When it is empty, htq and ltq are also empty. So when the goroutine is blocked it is fine in this case. This sound like this could be it :-)

Well, coming to think of it just using a sempahore here for the third queue consumes less memory: Just a counter that blocks the thread/goroutine once it has reached 0.

Øyvind Teig

unread,
May 12, 2021, 12:53:08 PM5/12/21
to golang-nuts
I am not certain whether you start with Java and end up with describing a possible implementation for Go, or stay with Java. In any case Java is your starting point. 

I guess, comparing any feature of any language, from the outside, then the feature comparison lists turn up. But since you brought in Java..:

Then I can just as well throw in the JCSP library's Alternative (=ALT, =select) class [1]. And here is their description of the associated Alternative type:

By invoking one of the following methods, a process may passively wait for one or more of the guards associated with an Alternative object to become ready. The methods differ in the way they choose which guard to select in the case when two or more guards are ready:

  • select waits for one or more of the guards to become ready. If more than one become ready, it makes an arbitrary choice between them (and corresponds to the occam ALT).
  • priSelect also waits for one or more of the guards to become ready. However, if more than one becomes ready, it chooses the first one listed (and corresponds to the occam PRI ALT). Note: the use of priSelect between channel inputs and a skip guard (at lowest priority) gives us a polling operation on the readiness of those channels.
  • fairSelect also waits for one or more of the guards to become ready. If more than one become ready, it prioritises its choice so that the guard it chose the last time it was invoked has lowest priority this time. This corresponds to a common occam idiom used for real-time applications. If fairSelect is used in a loop, a ready guard has the guarantee that no other guard will be serviced twice before it will be serviced. This enables an upper bound on service times to be calculated and ensures that no ready guard can be indefinitely starved.
In that world Go would look like this (provided perhaps, it also supported list type select guards):

select
pri select
fair select

[1] JCSP Alternative class - I am not certain how much JCSP has been used. It's "beautiful" (my words). Observe that they didn't make any GoCSP library..

==========
Aside: After the above discussion in this thread I found what I searched for, before I started it: a thread from 2012 [2]. Some déjà vu experience!

Is there any Go page with the rationale for having a single select type and not the other select type(s)? Like [3] or [4]. If not, maybe a new paragraph to [4]?

Øyvind

[3] Bell Labs and CSP Threads by Russ Cox
==========

robert engels

unread,
May 12, 2021, 10:48:31 PM5/12/21
to Øyvind Teig, golang-nuts
Here is a simple priority select implementation using unbuffered channels. https://play.golang.org/p/Hvl0iMr-cFW

Uncomment the lines as instructed and you will see that channel A is always picked.

What this demonstrates is that ‘priority’ and ‘event order’ is highly dependent on latency, event frequency, etc. The ’sleep’ + locks in this example function as an external clock - as long as all events are ready at the clock edge you can implement priority - but with async events and scheduling - priority is impossible.

(In the absence of the sleep - the Go scheduler + OS scheduler determines whether A or B will run and scheduling delays will allow B events to arrive before an A event.

You can also trivially change this example to implement the ‘close A, close B’ scenario using a single Go routine and will see the desired ’never ends’ state is obtained.

(btw - there are probably some deadlock scenarios - I didn’t spend a lot of time on this)





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

Øyvind Teig

unread,
May 15, 2021, 4:48:05 AM5/15/21
to golang-nuts
Thanks, rog. I appreciate this! Even if I cant' stop thinking that a "pri" would have been sligtly more elegant. But you shall be praised for the try! I wont' take the time to fine read the code, though... 

..Aside: Being more than busy to digest the fact that XMOS has announced a paradigm shift with keeping the xC compiler, but for new projects wanting us to code "in C" instead, with a library lib_xcore. There are reasons. But ordered select is kept! See my reaction blog note C plus lib_xcore black-boxes xC (disclaimer: no association with XMOS, no ads, no income, no gifts etc with my blogs. Only fun an expensens)

Robert Engels

unread,
May 15, 2021, 6:44:48 AM5/15/21
to Øyvind Teig, golang-nuts
Robert :)

On May 15, 2021, at 3:48 AM, Øyvind Teig <oyvin...@teigfam.net> wrote:

Thanks, rog. I appreciate this! Even if I cant' stop thinking that a "pri" would have been sligtly more elegant. But you shall be praised for the try! I wont' take the time to fine read the code, though... 
Reply all
Reply to author
Forward
0 new messages