On Tue, Jan 12, 2010 at 3:12 PM, Steve Schveighoffer <span dir="ltr"><<a href="mailto:schveiguy@yahoo.com">schveiguy@yahoo.com</a>></span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
The other possibility is to only allow so many messages to be queued before the queue is "full". Unsure what you want to do at that point though, either block or return an EAGAIN type error (maybe you can do both depending on how you want to send the message). This solution is at least more likely to show logic errors, since with the first solution you may forget to close the handle. But it also could cause deadlocks or force you to write handling code for full queue conditions.<br>
<br>
How does erlang handle this?<br>
<font color="#888888"><br>
-Steve<br>
</font><div><div></div><br></div></blockquote></div><br>Not sure what erlang does, but...<br><br>I've tried to implement request / response on top of a system that happens to use blocking queues. Come to discover, that this pattern results in deadlock. A 'server' actor can fill up with messages on its input queue and its output queue. If any of the actors writing requests into the server are also blocked waiting for responses, you can get a deadlock where A is writing a response but B can't get it because as part of processing another new incoming request, it has blocked on writing another request to A.<br>
<br>I think blocking is kind of like reference counted memory -- you don't want to do it unless there is a way to break the cycles in the graph. In this case that would mean a few queues that are not capable of blocking (they would be the 'ever expanding' kind), in the right places. (I'm not sure if this is enough. Even if it is enough in theory it might not be enough in practice as the system might grind to a halt if things expand too much.)<br>
<br>An idea that I think is likely to work better is to prioritize actors reading from large input queues over actors reading from small ones, or else prioritize readers from large queues over writers to them. Depending on circularity in the design, it might be possible to prioritize "later" processes over "earlier" ones. None of this is fool proof of course.<br>
<br>Suppose you have three processes, A, B, and C, that process each piece of data in that order, and C is slower than the others, and you have at least four CPUs working on the problem.<br><br>My hunch is that you will not be able to avoid an ever expanding queue between B and C, or else wasted CPU time, no matter what you do at the framework level. If there is circularity as well, you may get an ever expanding queue, wasted CPU, or deadlock. If there is enough circularity and/or general complexity in the overall message passing 'graph' you may not even be able to reason about what is going to happen.<br>
<br>You could send messages "backward" along the chain saying "please stop until I tell you otherwise". That approach could be used to resist this problem. (NOTE: If you have these meta-messages, be sure to check for them before checking for more incoming elephants that need to be turned into hot dogs.)<br>
<br>--> This assumes you can tell how full your own mailbox is!<br><br>And one downside of this application-controlled volume throttling is that the system can probably no longer reason about deadlocks at all. Since the messages going "backward" are always part of a two-way flow, there is no way for the system to automatically tell which end of the animal is the head and which is the tail.<br>
<br>This suggests that different policies might be available for each queue... (does anyone have experience with a system that has such configurable queues?)<br><br>My advice in general is that this kind of message passing system can't be completely encapsulated. There are failure states, the application designer *needs* to be able to measure the system to gauge whether you are about to stumble into one, and in general, designing the message passing control and recovery behavior is part of designing your system.<br>
<br>And it is probably one of the next big "it's hard to get right" topics for concurrent programming.<br><br>Kevin<br><br>