C++ Threading Proposal
Boehm, Hans
hans.boehm at hp.com
Thu Sep 30 01:50:41 BST 2004
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?)
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.)
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.
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
> > >
> >
>
>
More information about the cpp-threads
mailing list