[cpp-threads] High-level concurrency issues

[Peter A. Buhr]

   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.