Are channels FIFO?
Hector Chu
I have here this program:
package main
import "fmt"
import "runtime"
var c, d chan int
var done chan bool
func main() {
c = make(chan int, 1)
d = make(chan int)
done = make(chan bool)
go g()
for i := 0; i < 1000; i++ {
go f(i)
}
<-done
}
func f(n int) {
c <- n
if n != <-d {
fmt.Println(n)
}
if n == 999 {
done <- true
}
}
func g() {
for {
n := <-c
runtime.Gosched()
d <- n
}
}
Is this program guaranteed to never produce any output?
roger peppe
channels *are* FIFO, but i don't think you're testing that
in that program.
i don't see any reason why the value sent on c should
be the same value that arrives back on d,
because the sequence of events might go like this
F1: c <- 10
F2: c <- 11
G: <-c == 10
G d <- 10
F2: <- d == 10
F2: fmt.Println(10)
this would be different if c was unbuffered,
because then you could guarantee that only
one process is waiting on d at any one time.
Dominik Gruntz
Btw, there are two situations where FIFO may be guaranteed:
1)
how are elements stored in a buffered channel? This seems
to be FIFO (and this is tested in function AsynchFifo() in
test/chan/fifo.go).
2)
how are send (receive) requests from different goroutines
handled on an unbuffered channel or on a buffered channel
which is full (empty)? Are they queued in FIFO order?
Dominik
Ian Lance Taylor
> Where is it specified that channels *are* FIFO?
I don't think it is. I suppose a sentence should be added to the spec.
> Btw, there are two situations where FIFO may be guaranteed:
>
> 1)
> how are elements stored in a buffered channel? This seems
> to be FIFO (and this is tested in function AsynchFifo() in
> test/chan/fifo.go).
Yes, definitely FIFO for sending values on a buffered channel.
> 2)
> how are send (receive) requests from different goroutines
> handled on an unbuffered channel or on a buffered channel
> which is full (empty)? Are they queued in FIFO order?
I'm not sure the spec should address this. It's difficult to speak
about any ordering when there is no happens-before relationship between
the sending/receiving goroutines. That is, before you can speak of FIFO
you have to define "First". That said, the implementation does
currently maintain a queue of goroutines waiting for something to happen
on a channel, and that queue is maintained in FIFO order.
Ian
Russ Cox
the FIFO behavior of channels. I believe the only
guarantee is:
If:
a send s1 on a channel c happens before
a send s2 on c,
AND
a receive r1 from c happens before
a receive r2 from c,
AND
r1 receives the value sent by s2,
Then:
r2 cannot receive the value sent by s1.
("Happens before" is as defined by the memory model.)
This is a pretty difficult condition to observe or rely on,
since most of the time there is no happens before
relation between different sends on a particular channel,
nor one between different receives on a particular channel.
The main way this could be observed is that if you have
one sending goroutine sending a sequence of values to
one receiving goroutine, the sequence will arrive in order.
The guarantee does not depend on whether the channel
is buffered, except insofar as using an unbuffered channel
makes it that much harder to have a happens before relation
between two senders.
> That said, the implementation does
> currently maintain a queue of goroutines waiting for something to happen
> on a channel, and that queue is maintained in FIFO order.
As Ian said, this is not observable, so it hardly matters, but
it is possible in the gc implementation for channel send or receive
operations to jump the queue under various simultaneity conditions.
For example, two sends waiting on a buffered channel that wake up
in response to two receives might end up sending in a different order
than they queued. But since the sends are waiting at the same time,
neither can be considered to happen before the other, so you'd
never be able to tell.
Russ