Re: Threads: Other Primitives

From: danl_miller (danl_miller_at_[hidden])
Date: 2002-03-12 11:40:59

--- In boost_at_y..., "bill_kempf" <williamkempf_at_h...> wrote:
> --- In boost_at_y..., "dmoore99atwork" <dmoore_at_a...> wrote:
> > --- In boost_at_y..., "bill_kempf" <williamkempf_at_h...> wrote:
> > > There are some higher-level constructs that are planned for 
> > inclusion 
> > > in Boost.Threads.  They include the barrier, rw_mutex and 
> > > thread_pool.  They don't exist right now simply because of time 
> > > constraints and other priorities.  If you want to tackle 
> designing 
> > > and implementing (and remember that designing is more important 
> to 
> > > me) any of these concepts while I'm busy with the other things 
> > > (updating the documentation, fleshing out cancellation and
thread 
> > > attributes are the three current top priorities) I'd be happy
for 
> > the 
> > > assist.
[snip]
> > B.  FIFO, or LIFO, or priority based mutexes (or other 
> primitives).  
> 
> This one I'd need more convincing of.  Can you provide detailed 
> rationale and prior art for this?

  The threads module of RogueWave's SourcePro Core has a FIFO mutex:

http://www.roguewave.com/support/docs/SourcePro/threadsref/rwfifomutexlock.cfm

  The semantics of FIFO/std::queue (and/or of std::priority_queue) is
what most theoreticians mean when they use the word "strong" in the
context of pv-semaphores, spinlocks, barrier, mutexes, rwlocks,
message-queues, and other interthread entities which involve multiple
threads pending/waiting on a single interthread entity which itself
has the power to awake one or more of its pending threads.  Here the
word "strong" is short for "strong guarantee regarding ordering". 
Search the Boost developer-list history for references to "strong
semaphore" and the like last year, such as the postings by Kevin Van
Horn.
  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.

  Conversely, the priority-queue-based pv-semaphores, spinlocks,
barrier, mutexes, rwlocks, message-queues, and other interthread
entities which involve multiple threads pending/waiting on a single
interthread entity which itself has the power to awake one or more of
its pending threads are considered very useful, especially in RTOSes
and in real-time applications.
 With priority-queue interthread entities, the thread's priority is
used to sort more-eligible-to-run threads from less-eligible-to-run
threads.  This provides not only a strong FIFO guarantee, but also a
strong priority-based guarantee.  Mutexes which have the
scheduling-policies of FIFO/queue and priority-queue are discussed at:
  http://www.boost.org/libs/thread/doc/mutex_concept.html
  As with all of the MT/thread/interthread classes, the implementation
of interthread classes must permit both:
  1) relying on Boost's own code when the underlying operating system
lacks a certain concept (e.g., lacks priority-queue mutexes,
priority-queue pv-semaphores, priority-queue rwlocks, priority-queue
barrier, priority-queue message-queues)
  2) relying on an extreme-efficiency-tuned/kernel-implemented
implementation of that interthread entity in the underlying
operating-system (e.g., an RTOS's priority-queue pv-semaphore, an
RTOS's priority-queue message-queue, POSIX's queue-based
pthread_attr_setschedpolicy: "When threads executing with the
scheduling policy SCHED_FIFO, SCHED_RR, or SCHED_SPORADIC are waiting
on a mutex, they shall acquire the mutex in priority order when the
mutex is unlocked."  from
http://www.opengroup.org/onlinepubs/007904975/functions/pthread_attr_setschedpolicy.html)

  By the way, here is a concise summary of the portions of POSIX which
I came across:

         POSIX.0 - guide to POSIX
         POSIX.1 - system API for the C language
         POSIX.1a - system API extensions (e.g. symlinks, etc.) 
         POSIX.1b - real-time and I/O extensions (formerly POSIX.4)
         POSIX.1c - threads (formerly POSIX.4a)
         POSIX.1d - more real-time extensions (formerly POSIX.4b) 
         POSIX.1e - security extensions and ACLs (formerly POSIX.6) 
         POSIX.1f - transparent network file access (formerly POSIX.8) 
         POSIX.1g - protocol independent communications and sockets
(formerly POSIX.12) 
         POSIX.1h - fault tolerance 
         POSIX.1i - technical corrections to POSIX.1b
         POSIX.1j - advanced real-time extensions 
         POSIX.1k - removable media API 
         POSIX.1m - checkpointing and restarting 
         POSIX.1n - fixes to .1, .1b, .1c and .1i 
         POSIX.1q - tracing 
         POSIX.2 - shells and common utility programs
         POSIX.2a - more tools and utilities
         POSIX.2b - more utilities 
         POSIX.2c - security utilities 
         POSIX.2d - batch processing utilities
         POSIX.2e - removable media utilities 
         POSIX.5 - Ada binding to POSIX.1 
         POSIX.5b - Ada binding to POSIX.1b
         POSIX.5c - Ada binding to POSIX.1g 
         POSIX.9 - Fortran 77 binding to POSIX.1 
         POSIX.10 - supercomputing profile 
         POSIX.13 - realtime profile 
         POSIX.14 - multi-processing profile 
         POSIX.18 - POSIX profile