[cpp-threads] High-level concurrency issues

[Andrei Alexandrescu]

I don't mean to boycott by silence, but I'm experiencing a paper 
deadline syndrome. Thanks Peter for taking the time to explain, and I'll 
let others (at least for now) carry the discussion.

My first impression (I did read the emails and sketched your paper) is 
that the concurrency principles as embodied are a tad removed from what 
I have in mind about how threading in C++ should look like. However, 
that's only a first impression, and I understand it's going to take more 
to understand more than a decade's worth of trial and error. It's 
possible that and accomodating the new concepts in terms that are more 
familiar to me, I'll find things quite natural.

I'll get back to y'all on this.


Andrei

Peter A. Buhr wrote:
>    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.
>