Changeset 466b1c9 for doc/papers/concurrency

Timestamp:

Mar 18, 2019, 2:32:26 PM (7 years ago)

Author:

tdelisle <tdelisle@…>

Branches:

ADT, arm-eh, ast-experimental, cleanup-dtors, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

78e109f

Parents:

76d3ca6 (diff), a927662 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

File:

• doc/papers/concurrency/Paper.tex (modified) (20 diffs)

doc/papers/concurrency/Paper.tex

@@ -215 +215 @@
 {}
 \lstnewenvironment{Go}[1][]
-{\lstset{#1}}
+{\lstset{language=go,moredelim=**[is][\protect\color{red}]{`}{`},#1}\lstset{#1}}
+{}
+\lstnewenvironment{python}[1][]
+{\lstset{language=python,moredelim=**[is][\protect\color{red}]{`}{`},#1}\lstset{#1}}
 {}
 
@@ -228 +231 @@
 }
 
-\title{\texorpdfstring{Advanced Control-flow in \protect\CFA}{Advanced Control-flow in Cforall}}
+\title{\texorpdfstring{Advanced Control-flow and Concurrency in \protect\CFA}{Advanced Control-flow in Cforall}}
 
 \author[1]{Thierry Delisle}
@@ -242 +245 @@
 \abstract[Summary]{
 \CFA is a modern, polymorphic, non-object-oriented, backwards-compatible extension of the C programming language.
-This paper discusses the advanced control-flow features in \CFA, which include concurrency and parallelism, and its supporting runtime system.
-These features are created from scratch as ISO C's concurrency is low-level and unimplemented, so C programmers continue to rely on the C pthreads library.
-\CFA provides high-level control-flow mechanisms, like coroutines and user-level threads, and monitors for mutual exclusion and synchronization.
-A unique contribution of this work is allowing multiple monitors to be safely acquired \emph{simultaneously} (deadlock free), while integrating this capability with all monitor synchronization mechanisms.
-All features respect the expectations of C programmers, while being fully integrate with the \CFA polymorphic type-system and other language features.
+This paper discusses some advanced control-flow and concurrency/parallelism features in \CFA, along with the supporting runtime.
+These features are created from scratch because they do not exist in ISO C, or are low-level and/or unimplemented, so C programmers continue to rely on library features, like C pthreads.
+\CFA introduces language-level control-flow mechanisms, like coroutines, user-level threading, and monitors for mutual exclusion and synchronization.
+A unique contribution of this work is allowing multiple monitors to be safely acquired \emph{simultaneously} (deadlock free), while integrating this capability with monitor synchronization mechanisms.
+These features also integrate with the \CFA polymorphic type-system and exception handling, while respecting the expectations and style of C programmers.
 Experimental results show comparable performance of the new features with similar mechanisms in other concurrent programming-languages.
 }%
@@ -261 +264 @@
 \section{Introduction}
 
-This paper discusses the design of advanced, high-level control-flow extensions (especially concurrency and parallelism) in \CFA and its runtime.
+This paper discusses the design of language-level control-flow and concurrency/parallelism extensions in \CFA and its runtime.
 \CFA is a modern, polymorphic, non-object-oriented\footnote{
 \CFA has features often associated with object-oriented programming languages, such as constructors, destructors, virtuals and simple inheritance.
 However, functions \emph{cannot} be nested in structures, so there is no lexical binding between a structure and set of functions (member/method) implemented by an implicit \lstinline@this@ (receiver) parameter.},
 backwards-compatible extension of the C programming language~\cite{Moss18}.
-Within the \CFA framework, new control-flow features were created from scratch.
-ISO \Celeven defines only a subset of the \CFA extensions, and with respect to concurrency~\cite[\S~7.26]{C11}, the features are largely wrappers for a subset of the pthreads library~\cite{Butenhof97,Pthreads}.
-Furthermore, \Celeven and pthreads concurrency is basic, based on thread fork/join in a function and a few locks, which is low-level and error prone;
-no high-level language concurrency features exist.
-Interestingly, almost a decade after publication of the \Celeven standard, neither gcc-8, clang-8 nor msvc-19 (most recent versions) support the \Celeven include @threads.h@, indicating little interest in the C concurrency approach.
-Finally, while the \Celeven standard does not state a concurrent threading-model, the historical association with pthreads suggests the threading model is kernel-level threading (1:1)~\cite{ThreadModel}.
+Within the \CFA framework, new control-flow features are created from scratch.
+ISO \Celeven defines only a subset of the \CFA extensions, where the overlapping features are concurrency~\cite[\S~7.26]{C11}.
+However, \Celeven concurrency is largely wrappers for a subset of the pthreads library~\cite{Butenhof97,Pthreads}.
+Furthermore, \Celeven and pthreads concurrency is simple, based on thread fork/join in a function and a few locks, which is low-level and error prone;
+no high-level language concurrency features are defined.
+Interestingly, almost a decade after publication of the \Celeven standard, neither gcc-8, clang-8 nor msvc-19 (most recent versions) support the \Celeven include @threads.h@, indicating little interest in the C11 concurrency approach.
+Finally, while the \Celeven standard does not state a concurrent threading-model, the historical association with pthreads suggests implementations would adopt kernel-level threading (1:1)~\cite{ThreadModel}.
 
 In contrast, there has been a renewed interest during the past decade in user-level (M:N, green) threading in old and new programming languages.
@@ -284 +288 @@
 
 A further effort over the past decade is the development of language memory-models to deal with the conflict between certain language features and compiler/hardware optimizations.
-This issue can be rephrased as some features are pervasive (language and runtime) and cannot be safely added via a library to prevent invalidation by sequential optimizations~\cite{Buhr95a,Boehm05}.
+This issue can be rephrased as: some language features are pervasive (language and runtime) and cannot be safely added via a library to prevent invalidation by sequential optimizations~\cite{Buhr95a,Boehm05}.
 The consequence is that a language must be cognizant of these features and provide sufficient tools to program around any safety issues.
 For example, C created the @volatile@ qualifier to provide correct execution for @setjmp@/@logjmp@ (concurrency came later).
-The simplest solution is to provide a handful of complex qualifiers and functions (e.g., @volatile@ and atomics) allowing programmers to write consistent/race-free programs, often in the sequentially-consistent memory-model~\cite{Boehm12}.
+The common solution is to provide a handful of complex qualifiers and functions (e.g., @volatile@ and atomics) allowing programmers to write consistent/race-free programs, often in the sequentially-consistent memory-model~\cite{Boehm12}.
 
 While having a sufficient memory-model allows sound libraries to be constructed, writing these libraries can quickly become awkward and error prone, and using these low-level libraries has the same issues.
 Essentially, using low-level explicit locks is the concurrent equivalent of assembler programming.
-Just as most assembler programming is replaced with programming in a high-level language, explicit locks can be replaced with high-level concurrency constructs in a programming language.
-The goal is to get the compiler to check for correct usage and follow any complex coding conventions implicitly.
+Just as most assembler programming is replaced with high-level programming, explicit locks can be replaced with high-level concurrency in a programming language.
+Then the goal is for the compiler to check for correct usage and follow any complex coding conventions implicitly.
 The drawback is that language constructs may preclude certain specialized techniques, therefore introducing inefficiency or inhibiting concurrency.
 For most concurrent programs, these drawbacks are insignificant in comparison to the speed of composition, and subsequent reliability and maintainability of the high-level concurrent program.
@@ -299 +303 @@
 As stated, this observation applies to non-concurrent forms of complex control-flow, like exception handling and coroutines.
 
-Adapting the programming language allows matching the control-flow model with the programming-language style, versus adapting to one general (sound) library/paradigm.
+Adapting the programming language to these features also allows matching the control-flow model with the programming-language style, versus adopting one general (sound) library/paradigm.
 For example, it is possible to provide exceptions, coroutines, monitors, and tasks as specialized types in an object-oriented language, integrating these constructs to allow leveraging the type-system (static type-checking) and all other object-oriented capabilities~\cite{uC++}.
 It is also possible to leverage call/return for blocking communication via new control structures, versus switching to alternative communication paradigms, like channels or message passing.
@@ -307 +311 @@
 however, the reverse is seldom true, i.e., given implicit concurrency, e.g., actors, it is virtually impossible to create explicit concurrency, e.g., blocking thread objects.}
 Finally, with extended language features and user-level threading it is possible to discretely fold locking and non-blocking I/O multiplexing into the language's I/O libraries, so threading implicitly dovetails with the I/O subsystem.
-
-\CFA embraces language extensions and user-level threading to provide advanced control-flow and concurrency.
-We attempt to show the \CFA extensions and runtime are demonstrably better than those proposed for \CC and other concurrent, imperative programming languages.
-The contributions of this work are:
+\CFA embraces language extensions and user-level threading to provide advanced control-flow (exception handling\footnote{
+\CFA exception handling will be presented in a separate paper.
+The key feature that dovetails with this paper is non-local exceptions allowing exceptions to be raised across stacks, with synchronous exceptions raised among coroutines and asynchronous exceptions raised among threads, similar to that in \uC~\cite[\S~5]{uC++}
+} and coroutines) and concurrency.
+
+Most augmented traditional (Fortran 18~\cite{Fortran18}, Cobol 14~\cite{Cobol14}, Ada 12~\cite{Ada12}, Java 11~\cite{Java11}) and new languages (Go~\cite{Go}, Rust~\cite{Rust}, and D~\cite{D}), except \CC, diverge from C with different syntax and semantics, only interoperate indirectly with C, and are not systems languages, for those with managed memory.
+As a result, there is a significant learning curve to move to these languages, and C legacy-code must be rewritten.
+While \CC, like \CFA, takes an evolutionary approach to extend C, \CC's constantly growing complex and interdependent features-set (e.g., objects, inheritance, templates, etc.) mean idiomatic \CC code is difficult to use from C, and C programmers must expend significant effort learning \CC.
+Hence, rewriting and retraining costs for these languages, even \CC, are prohibitive for companies with a large C software-base.
+\CFA with its orthogonal feature-set, its high-performance runtime, and direct access to all existing C libraries circumvents these problems.
+
+We present comparative examples so the reader can judge if the \CFA control-flow extensions are equivalent or better than those in or proposed for \Celeven, \CC and other concurrent, imperative programming languages, and perform experiments to show the \CFA runtime is competitive with other similar mechanisms.
+The detailed contributions of this work are:
 \begin{itemize}
 \item
@@ -615 +628 @@
 
 
-\section{Coroutines: A Stepping Stone}\label{coroutine}
-
-Advanced controlWhile the focus of this discussion is concurrency and parallelism, it is important to address coroutines, which are a significant building block of a concurrency system (but not concurrent among themselves).
+\section{Coroutines: Stepping Stone}
+\label{coroutine}
+
 Coroutines are generalized routines allowing execution to be temporarily suspended and later resumed.
 Hence, unlike a normal routine, a coroutine may not terminate when it returns to its caller, allowing it to be restarted with the values and execution location present at the point of suspension.
@@ -643 +656 @@
 \begin{lrbox}{\myboxA}
 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
-`int f1, f2, state = 1;`   // single global variables
+`int fn1, fn2, state = 1;`   // single global variables
 int fib() {
         int fn;
         `switch ( state )` {  // explicit execution state
-          case 1: fn = 0;  f1 = fn;  state = 2;  break;
-          case 2: fn = 1;  f2 = f1;  f1 = fn;  state = 3;  break;
-          case 3: fn = f1 + f2;  f2 = f1;  f1 = fn;  break;
+          case 1: fn = 0;  fn1 = fn;  state = 2;  break;
+          case 2: fn = 1;  fn2 = fn1;  fn1 = fn;  state = 3;  break;
+          case 3: fn = fn1 + fn2;  fn2 = fn1;  fn1 = fn;  break;
         }
         return fn;
@@ -666 +679 @@
 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
 #define FIB_INIT `{ 0, 1 }`
-typedef struct { int f2, f1; } Fib;
+typedef struct { int fn2, fn1; } Fib;
 int fib( Fib * f ) {
 
-        int ret = f->f2;
-        int fn = f->f1 + f->f2;
-        f->f2 = f->f1; f->f1 = fn;
+        int ret = f->fn2;
+        int fn = f->fn1 + f->fn2;
+        f->fn2 = f->fn1; f->fn1 = fn;
 
         return ret;
@@ -678 +691 @@
         Fib f1 = FIB_INIT, f2 = FIB_INIT;
         for ( int i = 0; i < 10; i += 1 ) {
-                printf( "%d %d\n", fib( &f1 ), fib( &f2 ) );
+                printf( "%d %d\n", fib( &fn1 ), fib( &f2 ) );
         }
 }
@@ -684 +697 @@
 \end{lrbox}
 
-\subfloat[3 States: global variables]{\label{f:GlobalVariables}\usebox\myboxA}
+\subfloat[3 states: global variables]{\label{f:GlobalVariables}\usebox\myboxA}
 \qquad
-\subfloat[1 State: external variables]{\label{f:ExternalState}\usebox\myboxB}
-\caption{C Fibonacci Implementations}
+\subfloat[1 state: encapsulated variables]{\label{f:ExternalState}\usebox\myboxB}
+\caption{C fibonacci fsm}
 \label{f:C-fibonacci}
 
@@ -697 +710 @@
 `coroutine` Fib { int fn; };
 void main( Fib & fib ) with( fib ) {
-        int f1, f2;
-        fn = 0;  f1 = fn;  `suspend()`;
-        fn = 1;  f2 = f1;  f1 = fn;  `suspend()`;
-        for ( ;; ) {
-                fn = f1 + f2;  f2 = f1;  f1 = fn;  `suspend()`;
-        }
-}
-int next( Fib & fib ) with( fib ) {
-        `resume( fib );`
-        return fn;
-}
+        fn = 0;  int fn1 = fn; `suspend()`;
+        fn = 1;  int fn2 = fn1;  fn1 = fn; `suspend()`;
+        for () {
+                fn = fn1 + fn2; fn2 = fn1; fn1 = fn; `suspend()`; }
+}
+int next( Fib & fib ) with( fib ) { `resume( fib );` return fn; }
 int main() {
         Fib f1, f2;
-        for ( int i = 1; i <= 10; i += 1 ) {
+        for ( 10 )
                 sout | next( f1 ) | next( f2 );
-        }
 }
 \end{cfa}
@@ -718 +725 @@
 \newbox\myboxB
 \begin{lrbox}{\myboxB}
-\begin{cfa}[aboveskip=0pt,belowskip=0pt]
-`coroutine` Fib { int ret; };
-void main( Fib & f ) with( fib ) {
-        int fn, f1 = 1, f2 = 0;
-        for ( ;; ) {
-                ret = f2;
-
-                fn = f1 + f2;  f2 = f1;  f1 = fn; `suspend();`
-        }
-}
-int next( Fib & fib ) with( fib ) {
-        `resume( fib );`
-        return ret;
-}
-
-
-
-
-
-
-\end{cfa}
+\begin{python}[aboveskip=0pt,belowskip=0pt]
+
+def Fibonacci():
+        fn = 0; fn1 = fn; `yield fn`  # suspend
+        fn = 1; fn2 = fn1; fn1 = fn; `yield fn`
+        while True:
+                fn = fn1 + fn2; fn2 = fn1; fn1 = fn; `yield fn`
+
+
+f1 = Fibonacci()
+f2 = Fibonacci()
+for i in range( 10 ):
+        print( `next( f1 )`, `next( f2 )` ) # resume
+
+\end{python}
 \end{lrbox}
-\subfloat[3 States, internal variables]{\label{f:Coroutine3States}\usebox\myboxA}
-\qquad\qquad
-\subfloat[1 State, internal variables]{\label{f:Coroutine1State}\usebox\myboxB}
-\caption{\CFA Coroutine Fibonacci Implementations}
+\subfloat[\CFA]{\label{f:Coroutine3States}\usebox\myboxA}
+\qquad
+\subfloat[Python]{\label{f:Coroutine1State}\usebox\myboxB}
+\caption{Fibonacci input coroutine, 3 states, internal variables}
 \label{f:cfa-fibonacci}
 \end{figure}
@@ -784 +785 @@
 \begin{lrbox}{\myboxA}
 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
-`coroutine` Format {
-        char ch;   // used for communication
-        int g, b;  // global because used in destructor
+`coroutine` Fmt {
+        char ch;   // communication variables
+        int g, b;   // needed in destructor
 };
-void main( Format & fmt ) with( fmt ) {
-        for ( ;; ) {
-                for ( g = 0; g < 5; g += 1 ) {      // group
-                        for ( b = 0; b < 4; b += 1 ) { // block
+void main( Fmt & fmt ) with( fmt ) {
+        for () {
+                for ( g = 0; g < 5; g += 1 ) { // groups
+                        for ( b = 0; b < 4; b += 1 ) { // blocks
                                 `suspend();`
-                                sout | ch;              // separator
-                        }
-                        sout | "  ";               // separator
-                }
-                sout | nl;
-        }
-}
-void ?{}( Format & fmt ) { `resume( fmt );` }
-void ^?{}( Format & fmt ) with( fmt ) {
-        if ( g != 0 || b != 0 ) sout | nl;
-}
-void format( Format & fmt ) {
-        `resume( fmt );`
-}
+                                sout | ch; } // print character
+                        sout | "  "; } // block separator
+                sout | nl; }  // group separator
+}
+void ?{}( Fmt & fmt ) { `resume( fmt );` } // prime
+void ^?{}( Fmt & fmt ) with( fmt ) { // destructor
+        if ( g != 0 || b != 0 ) // special case
+                sout | nl; }
+void send( Fmt & fmt, char c ) { fmt.ch = c; `resume( fmt )`; }
 int main() {
-        Format fmt;
-        eof: for ( ;; ) {
-                sin | fmt.ch;
-          if ( eof( sin ) ) break eof;
-                format( fmt );
-        }
+        Fmt fmt;
+        sout | nlOff;   // turn off auto newline
+        for ( 41 )
+                send( fmt, 'a' );
 }
 \end{cfa}
@@ -820 +814 @@
 \newbox\myboxB
 \begin{lrbox}{\myboxB}
-\begin{cfa}[aboveskip=0pt,belowskip=0pt]
-struct Format {
-        char ch;
-        int g, b;
-};
-void format( struct Format * fmt ) {
-        if ( fmt->ch != -1 ) {      // not EOF ?
-                printf( "%c", fmt->ch );
-                fmt->b += 1;
-                if ( fmt->b == 4 ) {  // block
-                        printf( "  " );      // separator
-                        fmt->b = 0;
-                        fmt->g += 1;
-                }
-                if ( fmt->g == 5 ) {  // group
-                        printf( "\n" );     // separator
-                        fmt->g = 0;
-                }
-        } else {
-                if ( fmt->g != 0 || fmt->b != 0 ) printf( "\n" );
-        }
-}
-int main() {
-        struct Format fmt = { 0, 0, 0 };
-        for ( ;; ) {
-                scanf( "%c", &fmt.ch );
-          if ( feof( stdin ) ) break;
-                format( &fmt );
-        }
-        fmt.ch = -1;
-        format( &fmt );
-}
-\end{cfa}
+\begin{python}[aboveskip=0pt,belowskip=0pt]
+
+
+
+def Fmt():
+        try:
+                while True:
+                        for g in range( 5 ):
+                                for b in range( 4 ):
+
+                                        print( `(yield)`, end='' )
+                                print( '  ', end='' )
+                        print()
+
+
+        except GeneratorExit:
+                if g != 0 | b != 0:
+                        print()
+
+
+fmt = Fmt()
+`next( fmt )`                    # prime
+for i in range( 41 ):
+        `fmt.send( 'a' );`      # send to yield
+
+\end{python}
 \end{lrbox}
-\subfloat[\CFA Coroutine]{\label{f:CFAFmt}\usebox\myboxA}
+\subfloat[\CFA]{\label{f:CFAFmt}\usebox\myboxA}
 \qquad
-\subfloat[C Linearized]{\label{f:CFmt}\usebox\myboxB}
-\caption{Formatting text into lines of 5 blocks of 4 characters.}
+\subfloat[Python]{\label{f:CFmt}\usebox\myboxB}
+\caption{Output formatting text}
 \label{f:fmt-line}
 \end{figure}
@@ -878 +865 @@
 void main( Prod & prod ) with( prod ) {
         // 1st resume starts here
-        for ( int i = 0; i < N; i += 1 ) {
+        for ( i; N ) {
                 int p1 = random( 100 ), p2 = random( 100 );
                 sout | p1 | " " | p2;
@@ -894 +881 @@
 }
 void start( Prod & prod, int N, Cons &c ) {
-        &prod.c = &c;
+        &prod.c = &c; // reassignable reference
         prod.[N, receipt] = [N, 0];
         `resume( prod );`
@@ -909 +896 @@
         Prod & p;
         int p1, p2, status;
-        _Bool done;
+        bool done;
 };
 void ?{}( Cons & cons, Prod & p ) {
-        &cons.p = &p;
+        &cons.p = &p; // reassignable reference
         cons.[status, done ] = [0, false];
 }
@@ -969 +956 @@
 The program main restarts after the resume in @start@.
 @start@ returns and the program main terminates.
+
+One \emph{killer} application for a coroutine is device drivers, which at one time caused 70\%-85\% of failures in Windows/Linux~\cite{Swift05}.
+Many device drivers are a finite state-machine parsing a protocol, e.g.:
+\begin{tabbing}
+\ldots STX \= \ldots message \ldots \= ESC \= ETX \= \ldots message \ldots  \= ETX \= 2-byte crc \= \ldots      \kill
+\ldots STX \> \ldots message \ldots \> ESC \> ETX \> \ldots message \ldots  \> ETX \> 2-byte crc \> \ldots
+\end{tabbing}
+where a network message begins with the control character STX and ends with an ETX, followed by a 2-byte cyclic-redundancy check.
+Control characters may appear in a message if preceded by an ESC.
+Because FSMs can be complex and occur frequently in important domains, direct support of the coroutine is crucial in a systems programminglanguage.
+
+\begin{figure}
+\begin{cfa}
+enum Status { CONT, MSG, ESTX, ELNTH, ECRC };
+`coroutine` Driver {
+        Status status;
+        char * msg, byte;
+};
+void ?{}( Driver & d, char * m ) { d.msg = m; }         $\C[3.0in]{// constructor}$
+Status next( Driver & d, char b ) with( d ) {           $\C{// 'with' opens scope}$
+        byte = b; `resume( d );` return status;
+}
+void main( Driver & d ) with( d ) {
+        enum { STX = '\002', ESC = '\033', ETX = '\003', MaxMsg = 64 };
+        unsigned short int crc;                                                 $\C{// error checking}$
+  msg: for () {                                                                         $\C{// parse message}$
+                status = CONT;
+                unsigned int lnth = 0, sum = 0;
+                while ( byte != STX ) `suspend();`
+          emsg: for () {
+                        `suspend();`                                                    $\C{// process byte}$
+                        choose ( byte ) {                                               $\C{// switch with default break}$
+                          case STX:
+                                status = ESTX; `suspend();` continue msg;
+                          case ETX:
+                                break emsg;
+                          case ESC:
+                                suspend();
+                        } // choose
+                        if ( lnth >= MaxMsg ) {                                 $\C{// buffer full ?}$
+                                status = ELNTH; `suspend();` continue msg; }
+                        msg[lnth++] = byte;
+                        sum += byte;
+                } // for
+                msg[lnth] = '\0';                                                       $\C{// terminate string}\CRT$
+                `suspend();`
+                crc = (unsigned char)byte << 8; // prevent sign extension for signed char
+                `suspend();`
+                status = (crc | (unsigned char)byte) == sum ? MSG : ECRC;
+                `suspend();`
+        } // for
+}
+\end{cfa}
+\caption{Device driver for simple communication protocol}
+\end{figure}