Is message passing via channels in go guaranteed to be non-blocking?

Question

In order to assess whether go is a possible option for an audio/video application, I would like to know whether message passing in go satisfies any non-blocking progress guarantees (being obstruction-free, lock-free or wait-free). In particular, the following scenarios are relevant:

Single producer single consumer:

Two threads communicate using a shared channel. Thread A only does asynchronous sends, thread B only does asynchronous receives. Suppose the OS scheduler decides to interrupt thread A at the "worst possible moment" for an indefinite amount of time. Is thread B guaranteed to finish a receive operation in a bounded number of cpu cycles or is there a (theoretical) possibility that thread A can put the channel into a state where thread B needs to wait for the OS to resume thread A?

Multiple producers:

Several threads A1, A2, A3, ... communicate with one or more others threads using a shared channel. The threads Ai only do asynchronous sends. Suppose A2, A3, ... are suspended by the OS scheduler at the "worst possible moment" for an indefinite amount of time. Is thread A1 still guaranteed to finish a send operation in a bounded number of cpu cycles? Suppose further that each thread only wants to do one send. If the program is run sufficiently long (with a "malicious" scheduler which potentially starves some threads or interrupts and resumes threads at the "worst possible moment"), is at least one send guaranteed to succeed?

I am not so much interested in typical scenarios here, but rather worst-case guarantees. See Non-blocking algorithm (Wikipedia) for more details on obstruction-, lock- and wait-free algorithms.

Vicechairman

First, the Go runtime is not real-time (it is a garbage collected language for one thing), nor is the operating system that you are running on. Furthermore, "non-blocking" means that the channel will send when the receiver is not full, block when it is, or not send the message (in which case, the message is either dropped or queued locally). – Gower

Answer 1

The Go Memory Model doesn't require sends and receives to be non-blocking, and the current runtime implementation locks the channel for send and recv. This means, for instance, that it is possible to starve a sending or receiving go-routine if the OS-scheduler interrupts another thread running another go-routine which tries to send or receive on the same channel while it has already acquired the channel's lock.

So the answer is unfortunately no :(

_{(unless someone reimplement parts of the runtime using non-blocking algorithms).}

Vicechairman

Answer 2

Normal sends and receives are blocking operations by definition. You can do a non-blocking send or receive by using a select statement:

select {
case ch <- msg:
default:
}

(Receiving is very similar; just replace the case statement.)

The send only takes place when there is room in the channel's buffer. Otherwise the default case runs. Note that internally a mutex is still used (if I'm reading the code correctly).

Zygo

I think there might be a clash of terminology concerning the term "non-blocking". When I say "asynchronous", I mean "non-blocking" in the go sense. My real question is if I can write non-blocking algorithms using go non-blocking send/receives. This would not the case e.g. if a (go non-blocking) send/receive caused the go compiler to lock the channel using a mutex while performing the send/receive. – Vicechairman

I see. It looks to me like the runtime still uses mutexes in a non-blocking send or receive. See the chansend and chanrecv functions in src/pkg/runtime/chan.c if you're interested in details. – Zygo

Thanks for the pointer! Unfortunately, this is not the most readable code... I'll see if I can decipher it later. – Vicechairman

Answer 3

You're asking whether an operation is guarantee to complete within a bounded number of cycles, which of course is not a design consideration for this language (or most underlying OSes).

If run in a single thread, then Go uses cooperative multitasking between goroutines. So if one routine never yields, then the other will never run. If your program runs on multiple threads (as set by GOMAXPROCS), then you can run several goroutines simultaneously, in which case the OS controls scheduling between the threads. However, in neither case is there a guaranteed upper bound on the time to completion for a function call.

Note that the cooperative nature of goroutines gives you some amount of control over scheduling execution -- that is, routines are never preempted. Until you yield, you retain control of the thread.

As for blocking behavior, see The language specification:

The capacity, in number of elements, sets the size of the buffer in the channel. If the capacity is greater than zero, the channel is asynchronous: communication operations succeed without blocking if the buffer is not full (sends) or not empty (receives), and elements are received in the order they are sent. If the capacity is zero or absent, the communication succeeds only when both a sender and receiver are ready.

Note that non-blocking sends and receives on channels can be accomplished using the select syntax already mentioned.

Glaive

Answer 4

Goroutines do not own channels or the values sent on them. So, the execution status of a goroutine that has sent / is sending values on a channel has no impact on the ability of other goroutines to send or receive values on that channel, unless the channel's buffer is full, in which case all sends will block until a corresponding receive occurs, or the buffer is empty, in which case all receives will block until there is a corresponding send.

Because goroutines use cooperative scheduling (they have to yield to the scheduler, either through a channel operation, a syscall, or an explicit call to runtime.Gosched()), it is impossible for a goroutine to be interrupted at the "worst possible time". It is possible for a goroutine to never yield, in which case, it could tie up a thread indefinitely. If you have only one thread of execution, then your other goroutines will never be scheduled. It is possible, but statistically improbable, for a goroutine to just never be scheduled. However, if all goroutines but one are blocked on sends or receives, then the remaining goroutine must be scheduled.

It is possible to get a deadlock. If I have two goroutines executing:

func Goroutine(ch1, ch2 chan int) {
   i := <-ch1
   ch2 <- i
}
...
ch1, ch2 := make(chan int), make(chan int)
go Goroutine(ch1, ch2)
go Goroutine(ch2, ch1)

Then, as should be apparent, both goroutines are waiting for the other to send a value, which will never happen.

Mons