C++ Threading Proposal

[Jim Rogers]

----- Original Message ----- 
From: "Boehm, Hans" <hans.boehm at hp.com>
To: "'Jim Rogers'" <jimmaureenrogers at att.net>; "Boehm, Hans"
<hans.boehm at hp.com>; "'Andrei Alexandrescu'" <andrei at metalanguage.com>; "Ben
Hutchings" <ben at decadentplace.org.uk>; "Kevlin Henney"
<kevlin at curbralan.com>; "Bill Pugh" <pugh at cs.umd.edu>; "Douglas C. Schmidt"
<schmidt at dre.vanderbilt.edu>; "Doug Lea" <dl at cs.oswego.edu>
Sent: Wednesday, September 29, 2004 6:50 PM
Subject: RE: Re: C++ Threading Proposal


> You raise an interesting question, which is the extent we want to address
> real-time issues.
>
> I think that lock-free algorithms are interesting in either case, and
> their design is not affected by this decision.  The kind of modifiers or
> pragmas that Ada apparently provides get you part-way there.  You need
> something like compare-and-swap for many of the more interesting
> algorithms, and I couldn't find that.  And the effect of "volatile"
> on ordering seems to be unspecified.  (If x_initialized is volatile,
> one thread does " x = 17; x_initialized = true; " and another thread
> sees x_initialized is true, is it guaranteed to see the "x = 17; "
> assignment?  The answer appears to be no.  What if x is also volatile?)

Ada does not provide any guarantee of execution order. This is particularly
appropriate since we have computer architectures that provide
out-of-order execution.

In your example above, if x_initialized is volatile, while x is not, then
two
different threads on separate processors can be expected to see different
values for x, since each processor has its own copy of x in local cache.

If x is also volatile, another thread will see the "x = 17" once x is
updated.
The way to ensure that both x_initialized and x will properly be viewed and
set by different threads is by the use of critical regions. Atomic compare
and
swap operations are never specified in hardware for arbitrarily large
regions of
memory. This is the reason that critical regions have been defined. This is
also
the situation where mutex locks are very useful.

>
> As far as thread primitives are concerned, I was never convinced that
> real-time programming had much to do with other uses of threads, or
> that you want exactly the same primitives, even though many people have
tried.
> (E.g. strict priorities seem to be clearly a good idea for real-time,
> but in my experience usually get you into trouble for larger systems that
don't care
> about hard real-time behavior.  Similarly non-preemptive thread
> implementations seem to make sense for real-time work, but in my
> opinion are problematic for anything else.)

I agree that priorities must be used very carefully. My experience is that
priorities should only be used when necessary, and improper use can
result in priority inversions, deadlocks, and livelocks.

>
> This is one more reason I'd personally be happy to dodge the thread
library
> issues, and just define enough atomic operations and a memory model
> framework that different thread libraries could conform to.

I understand the desire for a minimalist approach. That may be the best
solution for C++. One hazard of such an approach is the non-portablity
of C++ libraries.

I am still in favor of the Ada approach (although it may be irritating to
C++
programmers) of providing a high level threading abstraction that can be
implemented using different thread models. Rather than burdening the
programmer with conditional compilation issues to support multiple
thread libraries, the Ada approach only requires the programmer to
compile a common set of source files on a compiler targeted to the
desired platform. The compilation differences are moved to the compiler
back-end, making the source code highly portable.

I have been thinking about your previous message, particularly the part
where
you indicated a desire to maintain a close similarity to the Java threading
model. If you do maintain a similarity with Java, then you must decide how
you want to implement a Thread class, and whether or not you want to
implement anything similar to a Runnable interface. My personal choice
would be to ignore the Java Runnable interface, since that is simply a Java
work-around for the lack of multiple inheritance.

The Java threading model also does not provide a good way for a Thread
class to specify its own timeout when waiting for a condition (using the
wait/notify pair). In Java, any timeout for a wait is specified within the
called synchronized block, and not withing the calling method's code.
This produces an inversion of responsibilities. All Theads calling that
synchronized block are subject to the same time-out rules. The calling
Thread cannot be the master of its own execution schedule, no matter
what its priority.

I find it much cleaner and easier to work with the Ada selective
entry calls. They provide a much cleaner separation of responsibilities.
The protected object is responsible for monitoring entry conditions and
entry queues. The calling task is responsible for the calling  and
call-cancelling
semantics.

C++ should also consider mundane behaviors, such as the ability for one
thread to safely abort another thread. Java attempted to do this with the
stop() method, which was eventually shown to be unsafe and was deprecated.
This is important because one of the mundane, but necessary considerations
in
thread programming is orderly program termination. A threaded program will
not terminate simply because the thread containing the main() function
has completed its work. All the child threads started from main() or any
child of main() must be terminated before the parent can be terminated.
To do things any other way would risk "zombie" threads, or run-away
threads. In either case the program cannot terminate in an orderly manner.

Java allows threads to send messages to each other through any public
method, whether or not that method contains a synchronized block. This
is an invitation to race conditions, because Java does not ensure atomic
updates of all the data members in a Thread class. I would suggest that
the public functions of a C++ Thread class should be implicitly
synchronized.
The method of synchronization may be through locks or lock-free
algorithms. The programmer should be able to choose either approach
by inheriting from a LockingThread base class or a LockFreeThread
base class. I have no idea what the result should be if a class inherits
from
both kinds of base classes. There may also be a simple Thread base
class, from which the other two base classes inherit. Any class that
inherits from the Thread base class (not through one of the synchronized
classes) should have no public functions beyond constructors and
destructors.

Jim Rogers

>
> Hans
>
> > -----Original Message-----
> > From: Jim Rogers [mailto:jimmaureenrogers at att.net]
> > Sent: Monday, September 27, 2004 9:02 PM
> > To: Boehm, Hans; 'Andrei Alexandrescu'; Ben Hutchings; Kevlin Henney;
> > Bill Pugh; Douglas C. Schmidt; Doug Lea
> > Subject: Re: Re: C++ Threading Proposal
> >
> >
> >
> > ----- Original Message ----- 
> > From: "Boehm, Hans" <hans.boehm at hp.com>
> > To: "'Andrei Alexandrescu'" <andrei at metalanguage.com>; "Ben Hutchings"
> > <ben at decadentplace.org.uk>; "Boehm, Hans" <hans.boehm at hp.com>; "Kevlin
> > Henney" <kevlin at curbralan.com>; "Bill Pugh"
> > <pugh at cs.umd.edu>; "Douglas C.
> > Schmidt" <schmidt at dre.vanderbilt.edu>; "Doug Lea" <dl at cs.oswego.edu>
> > Cc: "Jim Rogers" <jimmaureenrogers at att.net>
> > Sent: Monday, September 27, 2004 1:20 PM
> > Subject: RE: Re: C++ Threading Proposal
> >
> >
> > > My understanding of the Ada model (based also on a 1994 draft of the
> > standard) is that it's actually pretty good for the time.  It
> > differs from
> > the Java approach in several ways:
> > >
> > > 1) Writes to a field are allowed to "interfere with" at
> > least other fields
> > in that object.  I currently think this is a mistake given
> > current hardware
> > capabilities and the existing difficulties of writing
> > multithreaded code.
> > It was a reasonable choice in 1994.
> >
> > Protected procedures and protected entries are allowed to
> > modify any data in
> > the protected object.
> >
> > >
> > > 2) A concurrent write and other access (a race) is viewed
> > as an error,
> > just like the Pthread model.    Unlike in the Java setting where this
> > creates security issues, this is OK for many C++ programs.
> > But it doesn't
> > address lock-free algorithms, which was a big part of our motivation.
> >
> > I understand some of the appeal of lock-free algorithms. I
> > have not seen
> > documentation claiming that lock-free algorithms are
> > deterministic to the
> > levels needed for hard real time systems. Given this lack of
> > knowledge, I
> > would not focus all thread communication around only
> > lock-free algorithms.
> >
> > >
> > > 3) It uses guards on entry to a "protected procedure" (roughly
> > "synchronized method" in Java) instead of condition
> > variables.  I gather
> > that these are typically repeatedly evaluated on exit from protected
> > procedures?  I think I mildly prefer explicit condition
> > variables (roughly
> > as in Pthreads, though I don't fully understand the tradeoffs
> > as to whether
> > or not a notification should hold the lock) to either this or the Java
> > model, since I think it makes performance a bit more transparent.
> >
> > I would like to make a correction here. Protected objects are
> > allowed three
> > kinds of methods: procedures, entries, and functions.
> > Protected procedures are given exclusive access to the object
> > without guard
> > conditions.
> > Protected entries are given exclusive access to the object
> > when a specified
> > guard condition evaluates to True.
> > Protected functions are given shared access to the object through an
> > implicit read-lock.
> >
> > Protected entries are similar to critical sections controlled
> > by a condition
> > variable. Every protected entry has an associated entry
> > queue. That queue is
> > used to queue up calls to the entry while the guard condition
> > evaluates to
> > False. Upon completion of a protected entry or protected
> > procedure all entry
> > guard conditions are evaluated. If a condition evaluates to
> > True and the
> > entry queue size is greater than 0 the current task executes
> > the entry body
> > as a proxy for the next task waiting in the queue. Entry
> > queues can be set
> > up as either priority queues or FIFO queues.
> >
> > >
> > > 4) It's a bit clearer than the Pthread model about
> > visibility rules, but
> > not as clear as I would like.  It's a bit more of a stretch
> > to argue that my
> > register promotion example is legal in Ada, but it's not as clearly
> > prohibited as I would like.
> >
> > I am not familiar with your register promotion example.
> >
> > >
> > > 5) It doesn't seem to address atomic memory operations or
> > "unscoped" e.g.
> > conditionally acquired locks.
> >
> > The Ada tasking model does provide the ability to specify
> > atomic operations,
> > as well as volatile operations.
> > The Ada Language Reference Manual contains the following language:
> >
> > C.6 Shared Variable Control
> >
> > C.6 Shared Variable Control
> >
> >   1.. This clause specifies representation pragmas that
> > control the use of
> > shared variables.
> >
> > Syntax
> >
> >   2.. The form for pragmas Atomic, Volatile, Atomic_Components, and
> > Volatile_Components is as follows:
> >
> >     3.. pragma Atomic(local_name);
> >
> >     4.. pragma Volatile(local_name);
> >
> >     5.. pragma Atomic_Components(array_local_name);
> >
> >     6.. pragma Volatile_Components(array_local_name);
> >
> >   7.. An atomic type is one to which a pragma Atomic applies.
> > An atomic
> > object (including a component) is one to which a pragma
> > Atomic applies, or a
> > component of an array to which a pragma Atomic_Components
> > applies, or any
> > object of an atomic type.
> >
> >   8.. A volatile type is one to which a pragma Volatile
> > applies. A volatile
> > object (including a component) is one to which a pragma
> > Volatile applies, or
> > a component of an array to which a pragma Volatile_Components
> > applies, or
> > any object of a volatile type. In addition, every atomic type
> > or object is
> > also defined to be volatile. Finally, if an object is
> > volatile, then so are
> > all of its subcomponents (the same does not apply to atomic).
> >
> > Name Resolution Rules
> >
> >   9.. The local_name in an Atomic or Volatile pragma shall
> > resolve to denote
> > either an object_declaration, a non-inherited
> > component_declaration, or a
> > full_type_declaration. The array_local_name in an Atomic_Components or
> > Volatile_Components pragma shall resolve to denote the
> > declaration of an
> > array type or an array object of an anonymous type.
> >
> > Legality Rules
> >
> >   1.. It is illegal to apply either an Atomic or
> > Atomic_Components pragma to
> > an object or type if the implementation cannot support the
> > indivisible reads
> > and updates required by the pragma (see below).
> >
> >   2.. It is illegal to specify the Size attribute of an
> > atomic object, the
> > Component_Size attribute for an array type with atomic
> > components, or the
> > layout attributes of an atomic component, in a way that prevents the
> > implementation from performing the required indivisible reads
> > and updates.
> >
> >   3.. If an atomic object is passed as a parameter, then the
> > type of the
> > formal parameter shall either be atomic or allow pass by copy
> > (that is, not
> > be a nonatomic by-reference type). If an atomic object is
> > used as an actual
> > for a generic formal object of mode in out, then the type of
> > the generic
> > formal object shall be atomic. If the prefix of an
> > attribute_reference for
> > an Access attribute denotes an atomic object (including a
> > component), then
> > the designated type of the resulting access type shall be
> > atomic. If an
> > atomic type is used as an actual for a generic formal derived
> > type, then the
> > ancestor of the formal type shall be atomic or allow pass by copy.
> > Corresponding rules apply to volatile objects and types.
> >
> >   4.. If a pragma Volatile, Volatile_Components, Atomic, or
> > Atomic_Components applies to a stand-alone constant object,
> > then a pragma
> > Import shall also apply to it.
> > Pragma Volatile is used to enforce properly shared global updates on
> > multi-processor systems. Pragma Volatile forces each
> > processor to view and
> > update the shared variable directly, instead of through a
> > local copy of the
> > shared variable.
> >
> > >
> > > My general inclination is still to try for as much commonality as
> > reasonable between Java and C++, since many programmers will
> > need to deal
> > with both.
> >
> > I suggest you avoid the Java model implemented through wait()/notify()
> > operations. The Java model does not ensure that all waiting
> > threads will
> > ever be serviced. The Java model ensures that things will
> > work out "on the
> > average", which is not deterministic and is totally
> > inappropriate for hard
> > real-time systems.
> >
> > The Ada model of protected entries (which corresponds well
> > with Pthread
> > condition variables) includes a queue so that you can
> > deterministically
> > assure all waiting tasks will be processed in a predictable order.
> >
> > >
> > > Hans
> > >
> > > > -----Original Message-----
> > > > From: Andrei Alexandrescu [mailto:andrei at metalanguage.com]
> > > > Sent: Saturday, September 25, 2004 2:21 PM
> > > > To: Ben Hutchings; Hans Boehm; Kevlin Henney; Bill Pugh;
> > Douglas C.
> > > > Schmidt; Doug Lea
> > > > Cc: Jim Rogers
> > > > Subject: Fwd: Re: C++ Threading Proposal
> > > >
> > > >
> > > > Jim  Rogers  (cc'd)  sent  me some examples of using
> > Ada's concurrency
> > > > mechanisms, for possible inspiration.
> > > > One   is   attached   in   text   format,   and   the
> > other   is  at
> > > > http://home.att.net/~jimmaureenrogers/Shared_Resource_Design_P
> > > > atterns.html.
> > > > I  am sending this to you FYI, and am also adding the
> > documents to our
> > > > nascent institutional memory.
> > > > Andrei
> > > > This is a forwarded message
> > > > From: Jim Rogers <jimmaureenrogers at att.net>
> > > > To: "Andrei Alexandrescu" <andrei at metalanguage.com>
> > > > Date: Monday, September 20, 2004, 9:13:24 PM
> > > > Subject: C++ Threading Proposal
> > > > ===8<==============Original message text===============
> > > > Hello Andrei,
> > > > The attached file is a simple text file containing an
> > example of Ada
> > > > tasking.
> > > > I used the attachment because my email tool was mangling my
> > > > formatting.
> > > > Jim Rogers
> > > > ===8<===========End of original message text===========
> > > > -- 
> > > > Best regards,
> > > >  Andrei                            mailto:andrei at metalanguage.com
> > > >
> > >
> >
> >
>