Re: Threads: Other Primitives

From: danl_miller (danl_miller_at_[hidden])
Date: 2002-03-13 13:53:34

--- In boost_at_y..., "bill_kempf" <williamkempf_at_h...> wrote:
> --- In boost_at_y..., Darryl Green <green_at_t...> wrote:
> > >   I have been working with multithread software designs for 
> nearly 10
> > > years now in embedded real-time telecom equipment.  I have seen
> > > neither the need nor the use for the LIFO case, but maybe
someone 
> else
> > > has.
> > I think a thread pool would want to use LIFO - it would seem 
> reasonable to
> > expect that the dispatch of making a more recently run thread
ready 
> would be
> > faster than a less recently run one (it would be unlikely to be 
> slower in
> > any case). I can't think of any other  reason (off hand) for 
> wanting LIFO. I
> > must admit that I have never explicitly requested LIFO.

  Darryl, this applies if there is some form of penalty regarding the
use of the least-recently-used (LRU) unallocated resource in a pool
and some sort of economy of using the most-recently-used (MRU)
unallocated resource in a pool.

  Regarding this allocation-of-a-thread-from-a-thread-pool topic, I
can see that one such penalty could arise from the use of virtual
memory (VM).

  In RTOSes and in embedded software and in real-time software, VM
usually falls somewhere in between thoroughly unacceptable and frowned
upon.  I agree with a LRU/LIFO approach if in a VM OS where there is a
penalty for demand-paging in (portions of) the LRU thread's
address-space into core RAM.

> LIFO must be applied to the queued jobs, but there need not be a
LIFO 
> gaurantee on any synchronization primitives to do this.  So I think 
> this is a different topic from what was being discussed.
> 
> Bill Kempf

  Bill, this is where you & I disagree.  Semaphore is at its core, a
mechanism of doling out (i.e., decrement) permission to access a
resource in a shared fixed-size pool (which must be put back when
finished: i.e., increment) or to consume/kill (i.e., decrement) a
disposable member of a population, whose members are dynamically
manufactured/born (i.e., increment).  The debate which killed of
semaphore treated semaphore only as a list of mechanical
increment/decrement functionality without discussing this
pool-allocation and producer/consumer metaphor.  The mechanical
viewpoint says that the semaphore whell can be reinvented upon demand
with the use of condition-variables.  So be it for the next paragraph;
avoid semaphore if that makes common ground for the conversation
possible.

  In real-time software, RTOSes, and embedded software, message-queue
falls into the second producer/consumer metaphor of semaphore. 
Certain threads all produce work-requests and all pushes those
work-requests into a single interthread message-queue.  Each thread in
a pool of threads (which might or might not be the aforementioned
threads) pends on that single message-queue when they have nothing
else to do (i.e., when that pooled thread has completed its prior
work-request if it had one or at start-up if it has not yet processed
a prior work-request).  Thus when more than one thread in that
thread-pool is idle, more than one thread is pending on the same
message-queue, which as mentioned is a case of the producer-consumer
application of semaphore.  The message-queue has as the core of its
internal implementation a semaphore governing the size of the
work-requests pushed into the shared(-among-producers) queue as well
as governing the doling out of the work-requests which each idle
thread pops from the shared(-among-consumers) queue.

  Thus the message-queue (and in fact its internal semaphore) is
performing the entirety of the scheduling behavior for all threads in
the thread-pool.  Thus we have a case of interthread synchronization
primitives performing the entirety of the doling out of work to the
threads in a thread-pool.  [This case is very much like a single queue
of people at the bank or post office serviced by multiple
tellers/clerks.]

  Another alternative is to have a god-controller with some sort of
per-thread FIFO (multiple queue-orifices into the community of threads
instead of a single queue/orifice that the prior architecture had). 
But that architecture 1) has gratuitous complexity and 2) has defects
related to work-requests being placed in suboptimal queuing
strategies.  [This case is very much like a queue of people for each
clerk/teller, where some clerks'/tellers' line moves faster than other
clerks/tellers.]