[cpp-threads] High-level concurrency issues
Herb Sutter
hsutter at microsoft.com
Mon Oct 17 16:29:31 BST 2005
Thanks, Peter.
I agree with most, but maybe not all, of what's below. We should talk
about this in person sometime.
Just as some quick feedback, here's one basic point I don't agree with:
You rule out asynchronous calls as being interesting and rule out case
7, where to me that's the default and fundamental case. This is just to
let you know my own thoughts, speaking only for myself and not for the
committee or anyone else of course. Hopefully we can get together
sometime with a whiteboard handy -- it's hard to have these
conversations in email alone. :-) Maybe at C++ Connections?
The analysis you gave below is a summary of your 1992 paper, and pretty
much follows from the design requirements laid out at the beginning of
that paper. I buy into most of the design requirements, but not this one
(quoting the paper):
Both synchronous and asynchronous communication are needed. However,
we believe that the best way to support this is to provide
synchronous communication as the fundamental mechanism; asynchronous
mechanisms, such as buffering or futures [9], can then be built when
that is appropriate.
I don't buy into that part, because that makes blocking the default, and
implicit blocking is one of the big problems with today's concurrent
programming models that we need to overcome. (Another big one is of
course better isolation, or how to reduce or eliminate mutable shared
state and the need for locks.)
It's been clear to me that asynchronous (aka nonblocking,
message-passing) has to be the default when communicating between
threads. Certainly Lawrence at least seems to agree that futures are a
key abstraction.
Your paper's design requirements paragraph about this continues:
Building synchronous communication out of
asynchronous mechanisms requires a protocol for the caller to
subsequently detect completion. This is error prone because the
caller may not obey the protocol (e.g. never retrieve a result).
The above is actually pretty trivial in the implementation (e.g., think
of a future<T> containing just a shared_ptr<FutureData<T>>). In the
programming model it's easy too: The caller doesn't create a future for
the result at all, or creates one but then lets it go away without
touching it to get the result. Maybe I'm misunderstanding. Probably
whiteboard material.
Further, asynchronous requests require the creation of implicit
queues of outstanding requests, each of which must contain a copy of
the arguments of the request. This creates a storage management
problem because different requests require different amounts of
storage in the queue. We believe asynchronous communication is too
complicated a mechanism to be hidden in the system.
Well, message queues are simple and well understood. Lots of libraries
and systems for this exist. (Also, while garbage collection isn't
necessary for this, I should note that GC is also being proposed for
C++; GC can make some of the implementation choices easier.)
I mention the sync/async issue only because it seems to be pretty
fundamental to your approach, and has flavored many of the details and
results. In particular, you reject case 7 which seems to be the category
that would include an active task that is communicated with
asynchronously only, i.e., every method call is a message. This design
does not need any form of locking or other synchronization (the active
object's internal structures are only used by its own thread, though
I'll add "conceptually" here because we need to get away from explicit
threads), and so does not fall into what case 8 appears to describe
where uMutex is implicit. Did I understand your categories correctly, or
is case 8 already nonblocking for callers (if so, that's wonderful)?
Also, while I'm writing, one other thought:
> All synchronization is contained within mutual exclusion
> constructs so programming is race-free, meaning programmers do not
have to
> think about a memory model.
I agree that typical developers must never need to know about the memory
model. (Makes me think of Jack Nicholson's character saying: "The truth?
You can't handle the truth.")
But if you mean that 'doing the right locking' is the answer, I would
disagree with that because locks are known to be inherently
inappropriate for building modern software -- they aren't composable.
One of the key things we need to do in a next-generation programming
model for concurrency is to get better isolation to reduce or eliminate
mutable shared state (and thereby reduce or eliminate the need for
locks), just to get back composability. The world's best frameworks,
including Java's and .NET's, are deadlock-prone because of this (e.g.,
calling unknown code while holding a lock is a recipe for deadlock, and
calling a virtual function is calling unknown code), and we're just
getting away with it because people aren't actually writing much
concurrent code with their own locks.
Just some thoughts. Maybe we can chat over lunch or beer at C++
Connections?
Herb
> -----Original Message-----
> From: cpp-threads-bounces at decadentplace.org.uk [mailto:cpp-threads-
> bounces at decadentplace.org.uk] On Behalf Of Peter A. Buhr
> Sent: Sunday, October 16, 2005 5:54 PM
> To: cpp-threads at decadentplace.org.uk
> Subject: [cpp-threads] High-level concurrency issues
>
> Upon rereading the above, I realize I might have misunderstood the
> paragraph. So, sorry! Instead of disagreeing, let me ask for more
> detail. What high-level race-free mechanisms do you have in mind?
>
> As you pointed out, parsing certain parts of C++ is very difficult.
And
> as I
> pointed out:
>
> If you want to make it hard, it can be very difficult; if you make
it
> easy,
> it is very very easy.
>
> I've try lots of different approaches for adding concurrency into both
C
> and
> C++. During the attempts, certain basic concepts appeared and
gradually
> directed the work. In my previous email, I listed the three primary
> concurrency
> properties:
>
> thread: mechanism to sequentially execute statements, independently
of
> and
> possibly concurrently with other threads.
>
> execution context: the state needed to permit independent execution,
> including a separate stack.
>
> mutual exclusion/synchronization (MES): mechanisms to exclusively
access
> a
> resource and provide necessary timing relationships among threads.
>
> Now object-oriented design is built on the notion of the class, which
is a
> strong reason for concurrency to also be built on the class notion,
> allowing it
> to leverage other class-based language features. This is particular
true
> for
> C++ as many language features stem, directly or indirectly, from the
class
> notion. I have found that joining the concurrency properties with the
> class
> model is best done by associating thread and execution-context with
the
> class,
> and MES with member routines. Other approaches are possibly, but this
> particular matching seems to work very well.
>
> This coupling and the interactions among the concurrency properties
> generate
> the following high-level programming abstractions:
>
> object properties | member routine properties
> ------------------+---------------------------------------
> thread | stack | No MES | MES
> ------------------+---------------+-----------------------
> ------------------+---------------+-----------------------
> No | No | 1 class | 2 monitor
> ------------------+---------------------------------------
> No | Yes | 3 coroutine | 4 coroutine-monitor
> ------------------+---------------------------------------
> Yes | No | 5 reject | 6 reject
> ------------------+---------------------------------------
> Yes | Yes | 7 reject | 8 task
> ------------------+---------------------------------------
>
> Case 1 is a standard C++ object; its member routines do not provide
MES,
> and
> the caller's thread and stack are used to perform execution. Case 2
has
> all
> the properties of Case 1 but only one thread at a time can be
executing
> among
> the member routines with the MES property, called a mutex member;
within a
> mutex member, synchronization with other tasks can be performed. This
> abstraction is a monitor, which is well understood and appears in many
> concurrent languages (Java). Case 3 is an object that has its own
> execution
> context but no MES or thread; the execution context is associated with
a
> distinguished member in the object. This abstraction is a coroutine,
> which
> goes back to the roots of C++ in Simula, and supports finite-state
> problems
> like device drivers. Case 4 is like Case 3 but deals with concurrent
> access by
> adding MES. This abstraction is a coroutine-monitor. Case 5 and 6
are a
> thread without a stack, which is meaningless because a thread must
have a
> stack
> to execute. Case 7 is an object that has its own thread and execution
> context
> but no MES. This case is questionable because explicit locking is now
> required
> to handle calls from other threads, which violates the desire to be
high-
> level.
> Case 8 is like Case 7 but deals with concurrent access by adding MES.
> This
> abstraction is a task, which is an active object and appears in other
> concurrent languages (Ada). Note, the abstractions are derived from
> fundamental properties and not ad-hoc decisions by a language
designer,
> and
> each has a particular set of problems it can solve well. Simulating
one
> abstraction with the others often results in awkward solutions that
are
> inefficient; therefore, each has a place in a programming language.
>
> Below is the syntax used in uC++ for adding the programming
abstractions
> above
> into C++. (Other designs are possible.) There are two new type
> constructors
> _Coroutine and _Task, extensions of class, implicitly associating the
> execution-context and thread properties to objects. There are two new
> type
> qualifiers, _Mutex and _Nomutex, for qualifying member routines
needing
> the
> mutual exclusion property and which contain synchronization. There
are
> implicitly inherited members providing context-switch/synchronization,
> suspend(), resume(), wait(), signal(), signalBlock(), and one new
> statement
> _Accept. (I hope this table is readable.)
>
> No MES MES
>
+------------------------------+--------------------------------
> --
> | 1 class c { | 2 _Mutex class M {
> No Stack | public: | uCondition
variables;
> No Thread | m() { } | public:
> | }; | m() {
wait/signal/accept
> }
> | | };
>
+------------------------------+--------------------------------
> --
> | 3 _Coroutine C { | 4 _Mutex _Coroutine CM {
> | void main() {suspend} | uCondition
variables;
> Stack | public: | void main() {
> suspend/wait/signal/accept }
> No Thread | m() { resume } | public:
> | }; | m() {
> resume/wait/signal/accept }
> | | };
>
+------------------------------+--------------------------------
> --
> | | 8 _Task T {
> | | uCondition
variables;
> Stack | | void main() {
> wait/signal/accept }
> Thread | | public:
> | | m() {
wait/signal/accept
> }
> | | };
>
+------------------------------+--------------------------------
> --
>
> Points of import are as follows. All the primary concurrency
properties
> are
> available indirectly to the programmer via high-level constructs with
full
> knowledge by the compiler. Only a small number of new keywords have
been
> introduced, and there are no variables in the STL or UNIX system
libraries
> with
> these names (so far). All synchronization is contained within mutual
> exclusion
> constructs so programming is race-free, meaning programmers do not
have to
> think about a memory model. None of these language changes affects any
of
> the
> "difficult" parts of C++, with respect to parsing or semantic
analysis.
> The new
> language abstractions continue to rely on object instantiation and
> communication is by routine call. Templates and inheritance are
directly
> applicable with the new kinds of objects. Finally, these constructs
can
> implement a large number of problems with high-level solutions
allowing
> regular
> programmers to tackle complex concurrent projects, versus working with
> low-level mechanisms.
>
> Obviously, I have left out many details, and for some, I have stated
> nothing
> more than the obvious. The key point is that much can be expressed
with
> only a
> few changes and many of these changes have to be done with a library
> approach
> if the compiler is to be kept informed.
>
> --
> cpp-threads mailing list
> cpp-threads at decadentplace.org.uk
> http://www.decadentplace.org.uk/cgi-bin/mailman/listinfo/cpp-threads
More information about the cpp-threads
mailing list