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.]