[concurrency-interest] Multi-Reader One-Writer Queue

Gregg Wonderly gregg at cytetech.com
Sat Sep 3 00:37:27 EDT 2005



Brian Goetz wrote:
>  > However, I'm
>  > wondering how to determine efficiently who is the last reader during
>  > dequeue operation?
> 
> I think that's a task for the garbage collector.
> 
>> To achieve that, I'm thinking to create an array-based custom queue
> 
>  > where each reader is in fact a queue proxy that keep its "dequeue
>  > pointer" in the array.
> 
> This will only work if you can ensure that the producer cannot outrun 
> the slowest consumer.  If you can't, then you have to make the 
> multi-insert operation block.
> 
> To do this, you could have a semaphore which represents the put credit, 
> and no master queue, but N array-based queues:

The other choice is to make the receivers be listeners in a list that the producer cycles through.  If the listeners 
need to manage some queuing, they could use queues in their listener objects.  But, in the end, you have to be very 
careful about unbounded production opportunities.  It can seem attractive to let them run asynchronously, but this can 
be a big trap to fall into.

Asynchronous processing is good for unrelated activities, or when you are using multi-threading to hide latency.  But, 
you have to be careful to still keep data producers and consumers in sync either by using bounded queues, or counting 
semaphores or something that will keep the outstanding operations at some reasonable level.

Gregg Wonderly


More information about the Concurrency-interest mailing list