Re: Threads: Other Primitives

From: danl_miller (danl_miller_at_[hidden])
Date: 2002-03-13 19:14:22

--- In boost_at_y..., "dmoore99atwork" <dmoore_at_a...> wrote:
> --- In boost_at_y..., "danl_miller" <danl_miller_at_b...> wrote:
> 
> > 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.
> 

> It sounds like the semaphore you are proposing would block
> readers who call "down" when count == 0 and would block writers
> who call "up" when count == MAX?

  No.

> Or do you mean a message queue with two internal semaphores, one
> for  readers that reaches zero when empty, and one for writers
> that reaches zero when full?

  No.

> Thanks,
> Dave

  Your questions are not quite hitting the nail on the head, but
are very insightful and are indicative of what is really going on
regarding the use of the semaphore.

  As I mentioned there are 2 broad topics which semaphores model
best.  Both topics involve a population of resources, where
permission to operate on one individual in the population is
granted by the semaphore.

  One topic is where the population starts out at some size
*greater* than zero (typically fixed to a maximum, because
typically the population is a fixed-size pool).  One may ask the
semaphore for permission to temporarily check out one of the
resources in the pool.  The resources in the pool are considered
interchangable (and optionally even of arbitrary order,
reinforcing this interchangability).  Each resource in the pool
is in one of two states: allocated or unallocated.  The pool
starts out entirely in the all-members-eligible state and thus
the semaphore starts out at the pool'smaximum size.  Thus
permission to allocate some unallocated member of the pool is
granted by the successful completion of the semaphore's decrement
operation.  Obviously, this decrement operation does not block
when the semaphore's count (which is the number of unallocated
members of the pool) is greater than zero.  But when the
semaphore's count is zero (which directly states that all members
of the pool are allocated), then a requestor of permission to
allocate a member of the pool (the semaphore's decrement
operation) will block until the moment that the semaphore's count
becomes greater than zero (i.e., some other thread returned its
checked-out resource to the pool) at which point the pending
thread's decrement request will be completed (i.e., permission to
check out one member of the pool is granted), causing the
semaphore's count to be zero (which again directly states that
all members of the pool are allocated).  Thus we see 1) a
blocking ability to request permission to check out a resource
from the pool (which is congruent to cannonical semaphore's
blocking-decrement semantics) and 2) a nonblocking ability to
return an already-checked-out member of the pool to the pools
list of unallocated eligibles (which is congruent to cannonical
semaphore's nonblocking-increment semantics).  Thus here we see a
population which started out full-sized/nonempty and had a
semaphore count starting out at that positive integer and we see
a cannonical semaphore pending when its count is zero (i.e., all
members of the pool are checked out).  Note in this fixed-size
pool case that the population *always* stays fixed-size.  Note
that only the allocated versus unallocated state of the members
of the pool change.  Note here that
permission-to-check-out/semaphore-decrement must occur
chronologically before
return-to-pool's-unallocated-eligibles/semaphore-increment for
each member of the pool.  Note that interested threads would
queue up when all of the pools members are busy.  These threads
await their turn at accessing a member of a pool of scarce
resources.

  The other topic is where the population starts out at size
zero.  The population increases dynamically in size as
individuals of the population are manufactured (so to speak,
congruent with this dynamically-sized more "commercial-product
population" analogy).  As wares are manufactured, they enter a
warehouse where they exist until they are purchased (so to
speak).  Manufacture = produced resource = population increased
in size by one = increment the semaphore.  Request to purchase =
request to consume resource = request to decrease the
population's size by one = request to decrement the semaphore.
Thus we see 1) a nonblocking ability to produce (i.e., inject yet
another ware into the warehouse) which is congruent to cannonical
semaphore's nonblocking-increment semantics and 2) a blocking
ability to consume (i.e., purchase a ware from the warehouse)
which is congruent to cannonical semaphore's blocking-decrement
semantics.  Thus we see 1) a nonblocking ability to
manufacture/produce a ware to be placed in the warehouse (a
behavior which is congruent to cannonical-semaphore's
nonblocking-increment semantics) and 2) a blocking ability to
request permission to purchase/consume an
already-manufactured/produced individual from the warehouse
(which is congruent to cannonical semaphore's blocking-decrement
semantics). Thus here we see a population which started out empty
and had a cannonical semaphore count starting out at that zero
and we see a cannonical semaphore pending when its count is zero
(i.e., no already-manufactured/produced individuals are in the
warehouse ready to be purchased/consumed).  Note in this topic
that the population is not inherently fixed-size [just like the
Dorito's ads with Jay Leno a decade ago: "They'll make more!"]
(although for efficiency reasons, the message-queue---the
stereotypical use of the producer/consumer pattern in real-time
systems---would impose a fixed size in real-time systems so that
an upper-bound is established to guarantee availability of
resources as the real-time embedded software executes without
restart for months or years or decades).  Note that the
population size in the warehouse changes and that the only state
which changes regarding the individual wares is whether they are
in the warehouse or not.  Note here that
manufacturing/semaphore-increment must occur chronologically
before purchasing/semaphore-decrement for each individual ware in
the warehouse.  Note that produced wares would queue up in the
wearhouse when all of the consuming threads are
busy/unwilling-to-purchase.  These wares await their turn at
being consumed by a scarce thread(-pool) resource.

  Thus we see multiple polarizations when comparing the two broad
topics best addressed by semaphores:

  1) nonzero-sized pool of existing members which can be borrowed
temporarily versus initially-zero-sized warehouse of transient
individual wares

  2) members of a pool who expect to permanently stay members of
the pool (despite their allocated versus unallocated transient
state) versus individual wares who expect that their life in the
warehouse is transient

  3) initial value of the semaphore count starts out at the
positive-integer pool-size versus initial value of the semaphore
count starts out at the zero individuals initially in the
warehouse

  4) for pool case, semaphore decrement chronologically precedes
semaphore increment versus semaphore increment chronologically
preceding semaphore decrement for the producer-consumer case

--- In boost_at_y..., "dmoore99atwork" <dmoore_at_a...> wrote:
> It sounds like the semaphore you are proposing would
[snip]

  By the way, I am not *proposing* anything regarding semaphore
or semaphore usage.  This is a factual description of
long-established semaphore-usage practice, as witnessed by the 2+
decades of the real-time embedded software world.  I am sure that
invention of these two broad categories of typical semaphore
usage goes back even further, nearly to Edsger Dijkstra's
description of (PV-)semaphore in 1968.