[concurrency-interest] Polling many queues with few threads

Doug Lea dl@cs.oswego.edu
Fri, 26 Nov 2004 09:03:02 -0500


Jean Morissette:
> > I would like to have your advice on one of my problem.  Suppose that we 
> > have N queues that are polled (not pooled) continously, in a round-robin 
> > schedule, by only M thread, where M < N.
> 

Matthias Ernst:
> I guess I wouldn't use N queues in the first place. Why not just
> one?  Which would come handy since one queue with M threads is
> actually a ThreadPoolExecutor.

This is the best advice. (Also: one input queue, M worker threads, and
one output queue is an ExecutorCompletionService.)

If for some reason you must use separate queues, then you need a
secondary notification scheme.  For example, you can use a
BlockingQueue that delegates to one of the standard ones for all
operations. But additionally, on each insertion, have each queue
enqueue its identity on a secondary collector queue that contains
references to the queues that have elements, that can be used by
consumer threads. You can further specialize to a synchronizer that
keeps track of {queue, available-item-count} rather than holding
multiple references to the same queues to represent multiple available
elements. 

Notice that these kinds of designs are variations of the idea of using
just one queue. They usually impose further overhead than having just
one queue, but might still be better than the polling overhead they
replace. 

The general design issue here is one version of the
selector/demultiplexer/alt problem: Block until any of several tasks
are ready to proceed.  General solutions tend to impose overhead,
and/or usage restrictions, and/or ugly APIs. (java.nio Selectors have
some of each :-) Usually, the best advice is to redesign to avoid the
problem rather than trying to solve it. But in some cases (most
notably IO), the performance advantages of custom solutions usually
outweigh this.

-Doug