英文:
Is message passing via channels in go guaranteed to be non-blocking?
问题
为了评估Go语言是否适用于音频/视频应用程序,我想知道Go语言中的消息传递是否满足非阻塞进展保证(无阻塞、无锁或无等待)。特别是以下情况是相关的:
单生产者单消费者:
两个线程使用共享通道进行通信。线程A只进行异步发送,线程B只进行异步接收。假设操作系统调度程序在“最糟糕的时刻”中断线程A,并持续一段不确定的时间。线程B是否保证在有限的CPU周期内完成接收操作,或者存在(理论上的)可能性,即线程A可以将通道置于线程B需要等待操作系统恢复线程A的状态?
多生产者:
多个线程A1、A2、A3等使用共享通道与一个或多个其他线程进行通信。线程Ai只进行异步发送。假设A2、A3等线程被操作系统调度程序在“最糟糕的时刻”中断,并持续一段不确定的时间。线程A1是否仍然保证在有限的CPU周期内完成发送操作?进一步假设每个线程只想进行一次发送。如果程序运行足够长的时间(使用“恶意”调度程序,可能会使某些线程饥饿或在“最糟糕的时刻”中断和恢复线程),是否至少有一个发送操作保证成功?
我对典型情况不太感兴趣,而更关注最坏情况的保证。
有关阻塞、锁定和无等待算法的更多详细信息,请参见非阻塞算法(维基百科)。
英文:
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.
答案1
得分: 11
正常的发送和接收操作是阻塞的。你可以通过使用select语句来进行非阻塞的发送或接收:
select {
case ch <- msg:
default:
}
(接收操作非常类似,只需替换case语句。)
只有当通道的缓冲区有空间时,发送操作才会执行。否则,将执行default语句。请注意,根据我正确理解代码,内部仍然使用了互斥锁。
英文:
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).
答案2
得分: 4
Go内存模型不要求发送和接收是非阻塞的,并且当前的运行时 实现在“发送”和“接收”时会锁定通道。这意味着,例如,如果操作系统调度程序中断另一个正在运行的线程,而该线程尝试在已经获取了通道锁的同时在同一通道上发送或接收,那么发送或接收的go例程可能会被饿死。
所以,不幸的答案是不行
<sub>(除非有人使用非阻塞算法重新实现运行时的某些部分)。</sub>
英文:
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
<sub>(unless someone reimplement parts of the runtime using non-blocking algorithms).</sub>
答案3
得分: 1
你正在询问一个操作是否保证在有限的周期内完成,当然这不是这种语言(或大多数底层操作系统)的设计考虑因素。
如果在单个线程中运行,Go语言在goroutine之间使用协作式多任务处理。因此,如果一个例程从不让出控制,那么另一个例程将永远无法运行。如果您的程序在多个线程上运行(由GOMAXPROCS
设置),那么您可以同时运行多个goroutine,在这种情况下,操作系统控制线程之间的调度。然而,在任何情况下,函数调用的完成时间都没有保证的上限。
请注意,goroutine的协作性质使您对调度执行有一定程度的控制 - 也就是说,例程永远不会被抢占。在您让出控制之前,您保留对线程的控制权。
至于阻塞行为,请参阅语言规范:
> 容量(以元素数量表示)设置通道缓冲区的大小。如果容量大于零,则通道是异步的:如果缓冲区不满(发送)或不为空(接收),通信操作将成功而不阻塞,并且元素按发送的顺序接收。如果容量为零或不存在,则通信仅在发送方和接收方都准备好时成功。
请注意,可以使用已经提到的select
语法来实现通道上的非阻塞发送和接收。
英文:
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.
答案4
得分: 0
Goroutines不拥有通道或发送到通道上的值。因此,发送或正在发送通道上的值的goroutine的执行状态对其他goroutine在该通道上发送或接收值的能力没有影响,除非通道的缓冲区已满,在这种情况下,所有发送操作都将阻塞,直到相应的接收操作发生,或者缓冲区为空,在这种情况下,所有接收操作都将阻塞,直到有相应的发送操作。
由于goroutine使用协作调度(它们必须通过通道操作、系统调用或对runtime.Gosched()
的显式调用来让出给调度器),因此不可能在“最糟糕的时刻”中断goroutine。一个goroutine可能永远不会让出,这种情况下,它可能会无限期地占用一个线程。如果只有一个执行线程,那么其他的goroutine将永远不会被调度。一个goroutine可能永远不会被调度,但这种情况在统计上是不太可能的。然而,如果除了一个goroutine之外的所有goroutine都被阻塞在发送或接收操作上,那么剩下的goroutine必须被调度。
可能会发生死锁。如果我有两个执行的goroutine:
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)
那么,显然,两个goroutine都在等待另一个发送一个值,这将永远不会发生。
英文:
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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论