threads or queue for this task

Alex Martelli aleax at aleax.it
Mon Sep 16 15:27:44 EDT 2002


James J. Besemer wrote:
    ...
>>How can one code if you don't
>>reliably know when a Queue is empty or full?
> 
> Generally, Queues never get "full" and you generally don't care if
> they're empty.

You can define Queues that can hold a maximum number of items; in
this case, they do get full if they're being filled faster than
they're being emptied.  Sometimes, this IS what you want -- and
generally in such cases you just call method put and let it sleep
until a slot frees up, should that be needed -- just the converse
of the normal case for empty.

For example, suppose an architecture such as:

                        --> W1
   supervisor -> Q ---/---> W2
                      \---> W3

i.e., one supervisor thread that produces work requests and
places them in a single queue Q, from which three worker
threads peel work requests and produce results (say the W
threads place their results in another queue Q1 from which
another thread X peels them for output or whatever -- it
doesn't really matter).

Say that producing a work request takes CPU time T, that
processing the work request and producing the result takes
10T, and that 3 or 4 simultaneous threads is ideal to keep
the system maximally busy.  Round-robin scheduling assumed.

Now, if Q is unlimited, the supervisor thread will soon
fill it up.  In, say, the first 40T or so time units, threads
W1, W2 and W3 will each have gotten and processed one work
unit, while the supervisor has received 10T time units and
thus has produced 10 work units: there are now 7 units in
Q.  After another 40T have elapsed, Q has grown to now hold
14 units.  And so on: Q grows without bounds, assuming there
is always more work to perform.  Eventually Q overflows
available memory, and boom, the whole process goes haywire.
Even if the total number of work units to perform is bounded,
say N, with this arrangement Q must still grow to hold 0.7N
work units at the peak.  This might force pagination and at
the very least slow things down noticeably.

The solution is trivial: just set Q to hold, at most, 3 items.
A little bit more, if you want -- doesn't matter.  In any
case, soon the supervisor thread will find Q full and wait
until one of the W threads is done with its work and peels
off another work unit, thus freeing a slot in Q.  Basically,
with this simple device, we have changed the way processing
time is being allocated: instead of each 40T units going,
30 to processing 3 work units and 10 to producing 10 work
units, giving Q a maximum size automatically balances the
number of work units produced and processed when the
system is working in steady-state, so we know by this that
each 33T units will go, 30 to process 3 work units, 3 to
produce 3 more work units.  Besides avoiding wasting too
much memory on Q, this also speeds up the rate at which
results are output in steady state: 3 results come out
every 33T time units, instead of every 40T time units.
That's an average wait of 11T time units per result produced
(best possible, since it takes 1T to produce the work
request and 10T to process it!) rather than 13.3T -- in
this sense, the system with an unlimited-size Q is about
20% slowes than the variant with a Q of limited size (during
the system's overall steady-state).

You're welcome to apply queueing theory to analyze variants
where times to produce and process working units are not
deterministic (or, probably easier, simulate them:-) to
determine the effects of Q's size depending on these key
system parameters.  E.g., if sometimes processing time is
very short, we want to set Q's size large enough to
ensure there is just about more work for the W thread that
got free unexpectedly fast -- and similarly, if sometimes
time to produce the next working unit is occasionally quite
long.  For each assumption about times there will be
optimal sizes for Q to optimize system throughput or
response times.  Rarely will optimal sizes be infinite.



> The import thing about Queues is that the reader thread will
> automatically be suspended when reading from an empty queue and
> furthermore it will automatically wake up when the queue becomes non
> empty.
> 
> All you need from Queues is to create them and to get and put data.

Yep.  Setting size is just an optional embellishment, though
sometimes it does pay dividends.


> You probably should look for a book on concurrent sequential processes.
>  Most of the paradigms and pitfalls are pretty standard and would be
> spelled out in the book.  Unfortunately, I am at a loss to make a
> specific recommendation.  Perhaps somebody else has an idea.

I think the standard reference on this nowadays might be
Gregory Andrews' "Foundations of Multithreaded, Parallel, and 
Distributed Programming", Addison-Wesley.


Alex




More information about the Python-list mailing list