Context Navigation

← Previous Change
Next Change →

Paper.tex

Timestamp:

Apr 19, 2018, 11:04:47 AM (8 years ago)

Author:

Rob Schluntz <rschlunt@…>

Branches:

ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, with_gc

Children:

c28bcc7

Parents:

b2da0574 (diff), 61323a7 (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:/u/cforall/software/cfa/cfa-cc

File:

: 1 edited

doc/papers/concurrency/Paper.tex (modified) (81 diffs)

Legend:

: Unmodified
: Added
: Removed

doc/papers/concurrency/Paper.tex

-              rb2da0574
+              r2ae16219
 % Latex packages used in the document.
 \usepackage{epic,eepic}
 \usepackage{xspace}
 …
 \usepackage{upquote}                                            % switch curled `'" to straight
 \usepackage{listings}                                           % format program code
 \usepackage[labelformat=simple]{subfig}
+\usepackage[labelformat=simple,aboveskip=0pt,farskip=0pt]{subfig}
 \renewcommand{\thesubfigure}{(\alph{subfigure})}
 \usepackage{siunitx}
 \sisetup{ binary-units=true }
-%\input{style}                                                          % bespoke macros used in the document
 \hypersetup{breaklinks=true}
 …
 \renewcommand{\linenumberfont}{\scriptsize\sffamily}
+\lefthyphenmin=4                                                        % hyphen only after 4 characters
+\righthyphenmin=4
+\renewcommand{\textfraction}{0.0}       % the entire page maybe devoted to floats with no text on the page at all
+\lefthyphenmin=3                                                        % hyphen only after 4 characters
+\righthyphenmin=3
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 …
 % Latin abbreviation
 \newcommand{\abbrevFont}{\textit}                       % set empty for no italics
+\@ifundefined{eg}{
 \newcommand{\EG}{\abbrevFont{e}.\abbrevFont{g}.}
 \newcommand*{\eg}{%
 …
                 {\@ifnextchar{:}{\EG}%
                         {\EG,\xspace}}%
+}%
+}}{}%
+\@ifundefined{ie}{
 \newcommand{\IE}{\abbrevFont{i}.\abbrevFont{e}.}
 \newcommand*{\ie}{%
 …
                 {\@ifnextchar{:}{\IE}%
                         {\IE,\xspace}}%
+}%
+}}{}%
+\@ifundefined{etc}{
 \newcommand{\ETC}{\abbrevFont{etc}}
 \newcommand*{\etc}{%
         \@ifnextchar{.}{\ETC}%
         {\ETC.\xspace}%
+}%
+}}{}%
+\@ifundefined{etal}{
 \newcommand{\ETAL}{\abbrevFont{et}~\abbrevFont{al}}
 \renewcommand*{\etal}{%
+\newcommand*{\etal}{%
         \@ifnextchar{.}{\protect\ETAL}%
                 {\protect\ETAL.\xspace}%
+}%
+}}{}%
+\@ifundefined{viz}{
 \newcommand{\VIZ}{\abbrevFont{viz}}
 \newcommand*{\viz}{%
         \@ifnextchar{.}{\VIZ}%
                 {\VIZ.\xspace}%
 }%
+}}{}%
 \makeatother
 …
 \lstdefinelanguage{CFA}[ANSI]{C}{
         morekeywords={
+                _Alignas, _Alignof, __alignof, __alignof__, asm, __asm, __asm__, _At, __attribute,
+                __attribute__, auto, _Bool, catch, catchResume, choose, _Complex, __complex, __complex__,
+                __const, __const__, disable, dtype, enable, exception, __extension__, fallthrough, fallthru,
+                finally, forall, ftype, _Generic, _Imaginary, inline, __label__, lvalue, _Noreturn, one_t,
+                otype, restrict, _Static_assert, throw, throwResume, trait, try, ttype, typeof, __typeof,
+                __typeof__, virtual, with, zero_t},
+        morekeywords=[2]{
+                _Atomic, coroutine, is_coroutine, is_monitor, is_thread, monitor, mutex, nomutex, or,
+                resume, suspend, thread, _Thread_local, waitfor, when, yield},
+                _Alignas, _Alignof, __alignof, __alignof__, asm, __asm, __asm__, __attribute, __attribute__,
+                auto, _Bool, catch, catchResume, choose, _Complex, __complex, __complex__, __const, __const__,
+                coroutine, disable, dtype, enable, __extension__, exception, fallthrough, fallthru, finally,
+                __float80, float80, __float128, float128, forall, ftype, _Generic, _Imaginary, __imag, __imag__,
+                inline, __inline, __inline__, __int128, int128, __label__, monitor, mutex, _Noreturn, one_t, or,
+                otype, restrict, __restrict, __restrict__, __signed, __signed__, _Static_assert, thread,
+                _Thread_local, throw, throwResume, timeout, trait, try, ttype, typeof, __typeof, __typeof__,
+                virtual, __volatile, __volatile__, waitfor, when, with, zero_t},
         moredirectives={defined,include_next}%
+}
 …
 \authormark{Thierry Delisle \textsc{et al}}
 \address[1]{\orgdiv{David R. Cheriton School of Computer Science}, \orgname{University of Waterloo}, \orgaddress{\state{Ontario}, \country{Canada}}}
+\address[1]{\orgdiv{Cheriton School of Computer Science}, \orgname{University of Waterloo}, \orgaddress{\state{Ontario}, \country{Canada}}}
 \corres{*Peter A. Buhr, \email{pabuhr{\char`\@}uwaterloo.ca}}
 \presentaddress{David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, N2L 3G1, Canada}
+\presentaddress{Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, N2L 3G1, Canada}
 …
 }%
 \keywords{concurrency, runtime, coroutines, threads, C, Cforall}
+\keywords{concurrency, parallelism, coroutines, threads, monitors, runtime, C, Cforall}
 …
 % ======================================================================
 This paper provides a minimal concurrency \newterm{API} that is simple, efficient and can be used to build other concurrency features.
+This paper provides a minimal concurrency \newterm{Abstract Program Interface} (API) that is simple, efficient and can be used to build other concurrency features.
 While the simplest concurrency system is a thread and a lock, this low-level approach is hard to master.
 An easier approach for programmers is to support higher-level constructs as the basis of concurrency.
 …
 Examples of high-level approaches are task based~\cite{TBB}, message passing~\cite{Erlang,MPI}, and implicit threading~\cite{OpenMP}.
 The terminology used in this paper is as follows.
+This paper used the following terminology.
 A \newterm{thread} is a fundamental unit of execution that runs a sequence of code and requires a stack to maintain state.
 Multiple simultaneous threads gives rise to \newterm{concurrency}, which requires locking to ensure safe access to shared data.
 % Correspondingly, concurrency is defined as the concepts and challenges that occur when multiple independent (sharing memory, timing dependencies, etc.) concurrent threads are introduced.
+Multiple simultaneous threads gives rise to \newterm{concurrency}, which requires locking to ensure safe communication and access to shared data.
+% Correspondingly, concurrency is defined as the concepts and challenges that occur when multiple independent (sharing memory, timing dependencies, \etc) concurrent threads are introduced.
 \newterm{Locking}, and by extension locks, are defined as a mechanism to prevent progress of threads to provide safety.
 \newterm{Parallelism} is running multiple threads simultaneously.
 …
 Hence, there are two problems to be solved in the design of concurrency for a programming language: concurrency and parallelism.
 While these two concepts are often combined, they are in fact distinct, requiring different tools~\cite{Buhr05a}.
 Concurrency tools handle mutual exclusion and synchronization, while parallelism tools handle performance, cost and resource utilization.
+While these two concepts are often combined, they are in fact distinct, requiring different tools~\cite[\S~2]{Buhr05a}.
+Concurrency tools handle synchronization and mutual exclusion, while parallelism tools handle performance, cost and resource utilization.
 The proposed concurrency API is implemented in a dialect of C, called \CFA.
 …
 Like C, the basics of \CFA revolve around structures and routines, which are thin abstractions over machine code.
 The vast majority of the code produced by the \CFA translator respects memory layouts and calling conventions laid out by C.
 Interestingly, while \CFA is not an object-oriented language, lacking the concept of a receiver (e.g., {\tt this}), it does have some notion of objects\footnote{C defines the term objects as : ``region of data storage in the execution environment, the contents of which can represent
+Interestingly, while \CFA is not an object-oriented language, lacking the concept of a receiver (\eg {\tt this}), it does have some notion of objects\footnote{C defines the term objects as : ``region of data storage in the execution environment, the contents of which can represent
 values''~\cite[3.15]{C11}}, most importantly construction and destruction of objects.
 Most of the following code examples can be found on the \CFA website~\cite{Cforall}.
 …
 \subsection{Operators}
 Overloading also extends to operators.
 The syntax for denoting operator-overloading is to name a routine with the symbol of the operator and question marks where the arguments of the operation appear, e.g.:
+The syntax for denoting operator-overloading is to name a routine with the symbol of the operator and question marks where the arguments of the operation appear, \eg:
 \begin{cfa}
 int ++? (int op);                       $\C{// unary prefix increment}$
 …
 Note that the type use for assertions can be either an @otype@ or a @dtype@.
 Types declared as @otype@ refer to ``complete'' objects, i.e., objects with a size, a default constructor, a copy constructor, a destructor and an assignment operator.
+Types declared as @otype@ refer to ``complete'' objects, \ie objects with a size, a default constructor, a copy constructor, a destructor and an assignment operator.
 Using @dtype@, on the other hand, has none of these assumptions but is extremely restrictive, it only guarantees the object is addressable.
 …
 % ======================================================================
 % ======================================================================
+Before any detailed discussion of the concurrency and parallelism in \CFA, it is important to describe the basics of concurrency and how they are expressed in \CFA user code.
+\section{Basics of concurrency}
 At its core, concurrency is based on having multiple call-stacks and scheduling among threads of execution executing on these stacks.
+Concurrency without parallelism only requires having multiple call stacks (or contexts) for a single thread of execution.
+Execution with a single thread and multiple stacks where the thread is self-scheduling deterministically across the stacks is called coroutining.
+Execution with a single and multiple stacks but where the thread is scheduled by an oracle (non-deterministic from the thread's perspective) across the stacks is called concurrency.
+Therefore, a minimal concurrency system can be achieved by creating coroutines (see Section \ref{coroutine}), which instead of context-switching among each other, always ask an oracle where to context-switch next.
+Multiple call stacks (or contexts) and a single thread of execution does \emph{not} imply concurrency.
+Execution with a single thread and multiple stacks where the thread is deterministically self-scheduling across the stacks is called \newterm{coroutining};
+execution with a single thread and multiple stacks but where the thread is scheduled by an oracle (non-deterministic from the thread's perspective) across the stacks is called concurrency~\cite[\S~3]{Buhr05a}.
+Therefore, a minimal concurrency system can be achieved using coroutines (see Section \ref{coroutine}), which instead of context-switching among each other, always defer to an oracle for where to context-switch next.
 While coroutines can execute on the caller's stack-frame, stack-full coroutines allow full generality and are sufficient as the basis for concurrency.
 The aforementioned oracle is a scheduler and the whole system now follows a cooperative threading-model (a.k.a., non-preemptive scheduling).
 …
 \section{\protect\CFA's Thread Building Blocks}
+\subsection{\protect\CFA's Thread Building Blocks}
 One of the important features that are missing in C is threading\footnote{While the C11 standard defines a ``threads.h'' header, it is minimal and defined as optional.
 …
+\section{Coroutines: A Stepping Stone}\label{coroutine}
+While the main focus of this proposal is concurrency and parallelism, it is important to address coroutines, which are actually a significant building block of a concurrency system. \textbf{Coroutine}s are generalized routines which have predefined points where execution is suspended and can be resumed at a later time.
+Therefore, they need to deal with context switches and other context-management operations.
+This proposal includes coroutines both as an intermediate step for the implementation of threads, and a first-class feature of \CFA.
+Furthermore, many design challenges of threads are at least partially present in designing coroutines, which makes the design effort that much more relevant.
+The core \textbf{api} of coroutines revolves around two features: independent call-stacks and @suspend@/@resume@.
+\subsection{Coroutines: A Stepping Stone}\label{coroutine}
+While the focus of this proposal is concurrency and parallelism, it is important to address coroutines, which are a significant building block of a concurrency system.
+\newterm{Coroutine}s are generalized routines with points where execution is suspended and resumed at a later time.
+Suspend/resume is a context switche and coroutines have other context-management operations.
+Many design challenges of threads are partially present in designing coroutines, which makes the design effort relevant.
+The core \textbf{api} of coroutines has two features: independent call-stacks and @suspend@/@resume@.
+A coroutine handles the class of problems that need to retain state between calls (\eg plugin, device driver, finite-state machine).
+For example, a problem made easier with coroutines is unbounded generators, \eg generating an infinite sequence of Fibonacci numbers:
+\begin{displaymath}
+f(n) = \left \{
+\begin{array}{ll}
+                               & n = 0         \\
+                               & n = 1         \\
+f(n-1) + f(n-2) & n \ge 2       \\
+\end{array}
+\right.
+\end{displaymath}
+Figure~\ref{f:C-fibonacci} shows conventional approaches for writing a Fibonacci generator in C.
+Figure~\ref{f:GlobalVariables} illustrates the following problems:
+unencapsulated global variables necessary to retain state between calls;
+only one fibonacci generator can run at a time;
+execution state must be explicitly retained.
+Figure~\ref{f:ExternalState} addresses these issues:
+unencapsulated program global variables become encapsulated structure variables;
+multiple fibonacci generators can run at a time by declaring multiple fibonacci objects;
+explicit execution state is removed by precomputing the first two Fibonacci numbers and returning $f(n-2)$.
 \begin{figure}
+\begin{center}
+\begin{tabular}{@{}lll@{}}
+\multicolumn{1}{c}{\textbf{callback}} & \multicolumn{1}{c}{\textbf{output array}} & \multicolumn{1}{c}{\textbf{external state}} \\
+\begin{cfa}
+void fib_func(
+        int n, void (* callback)( int )
+) {
+        int fn, f1 = 0, f2 = 1;
+        for ( int i = 0; i < n; i++ ) {
+                callback( f1 );
+                fn = f1 + f2;
+                f1 = f2;  f2 = fn;
+\centering
+\newbox\myboxA
+\begin{lrbox}{\myboxA}
+\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
+`int f1, f2, 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;
+        }
+        return fn;
+}
 int main() {
+        void print_fib( int n ) {
+                printf( "%d\n", n );
+        for ( int i = 0; i < 10; i += 1 ) {
+                printf( "%d\n", fib() );
+        }
+        fib_func( 10, print_fib );
+}
+\end{cfa}
+&
+\begin{cfa}
+void fib_array(
+        int n, int * array
+) {
+        int fn, f1 = 0, f2 = 1;
+        for ( int i = 0; i < n; i++ ) {
+                array[i] = f1;
+                fn = f1 + f2;
+                f1 = f2;  f2 = fn;
+}
+\end{lstlisting}
+\end{lrbox}
+\newbox\myboxB
+\begin{lrbox}{\myboxB}
+\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
+#define FIB_INIT `{ 0, 1 }`
+typedef struct { int f2, f1; } Fib;
+int fib( Fib * f ) {
+        int ret = f->f2;
+        int fn = f->f1 + f->f2;
+        f->f2 = f->f1; f->f1 = fn;
+        return ret;
+}
+int main() {
+        Fib f1 = FIB_INIT, f2 = FIB_INIT;
+        for ( int i = 0; i < 10; i += 1 ) {
+                printf( "%d %d\n", fib( &f1 ), fib( &f2 ) );
+        }
+}
+\end{lstlisting}
+\end{lrbox}
+\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}
+\label{f:C-fibonacci}
+\bigskip
+\newbox\myboxA
+\begin{lrbox}{\myboxA}
+\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
+`coroutine` Fib { int fn; };
+void main( Fib & f ) with( f ) {
+        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;
+}
 int main() {
+        int a[10];
+        fib_array( 10, a );
+        for ( int i = 0; i < 10; i++ ) {
+                printf( "%d\n", a[i] );
+        Fib f1, f2;
+        for ( int i = 1; i <= 10; i += 1 ) {
+                sout | next( f1 ) | next( f2 ) | endl;
+        }
+}
+\end{cfa}
+&
+\begin{cfa}
+typedef struct { int f1, f2; } Fib;
+int fib_state(
+        Fib * fib
+) {
+        int ret = fib->f1;
+        int fn = fib->f1 + fib->f2;
+        fib->f2 = fib->f1; fib->f1 = fn;
+\end{lstlisting}
+\end{lrbox}
+\newbox\myboxB
+\begin{lrbox}{\myboxB}
+\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
+`coroutine` Fib { int ret; };
+void main( Fib & f ) with( f ) {
+        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;
+}
+int main() {
+        Fib fib = { 0, 1 };
+        for ( int i = 0; i < 10; i++ ) {
+                printf( "%d\n", fib_state( &fib ) );
+        }
+}
+\end{cfa}
+\end{tabular}
+\end{center}
+\caption{Fibonacci Implementations in C}
+\label{lst:fib-c}
+\end{lstlisting}
+\end{lrbox}
+\subfloat[3 States, internal variables]{\label{f:Coroutine3States}\usebox\myboxA}
+\qquad
+\subfloat[1 State, internal variables]{\label{f:Coroutine1State}\usebox\myboxB}
+\caption{\CFA Coroutine Fibonacci Implementations}
+\label{f:fibonacci-cfa}
 \end{figure}
+A good example of a problem made easier with coroutines is generators, e.g., generating the Fibonacci sequence.
+This problem comes with the challenge of decoupling how a sequence is generated and how it is used.
+Listing \ref{lst:fibonacci-c} shows conventional approaches to writing generators in C.
+All three of these approach suffer from strong coupling.
+The left and centre approaches require that the generator have knowledge of how the sequence is used, while the rightmost approach requires holding internal state between calls on behalf of the generator and makes it much harder to handle corner cases like the Fibonacci seed.
+Listing \ref{lst:fibonacci-cfa} is an example of a solution to the Fibonacci problem using \CFA coroutines, where the coroutine stack holds sufficient state for the next generation.
+Figure~\ref{f:Coroutine3States} creates a @coroutine@ type, which provides communication for multiple interface functions, and the \newterm{coroutine main}, which runs on the coroutine stack.
+\begin{cfa}
+`coroutine C { char c; int i; _Bool s; };`      $\C{// used for communication}$
+void ?{}( C & c ) { s = false; }                        $\C{// constructor}$
+void main( C & cor ) with( cor ) {                      $\C{// actual coroutine}$
+        while ( ! s ) // process c
+        if ( v == ... ) s = false;
+}
+// interface functions
+char cont( C & cor, char ch ) { c = ch; resume( cor ); return c; }
+_Bool stop( C & cor, int v ) { s = true; i = v; resume( cor ); return s; }
+\end{cfa}
+encapsulates the Fibonacci state in the  shows is an example of a solution to the Fibonacci problem using \CFA coroutines, where the coroutine stack holds sufficient state for the next generation.
 This solution has the advantage of having very strong decoupling between how the sequence is generated and how it is used.
 Indeed, this version is as easy to use as the @fibonacci_state@ solution, while the implementation is very similar to the @fibonacci_func@ example.
+Figure~\ref{f:fmt-line} shows the @Format@ coroutine for restructuring text into groups of character blocks of fixed size.
+The example takes advantage of resuming coroutines in the constructor to simplify the code and highlights the idea that interesting control flow can occur in the constructor.
 \begin{figure}
+\begin{cfa}
+coroutine Fibonacci { int fn; };                                $\C{// used for communication}$
+void ?{}( Fibonacci & fib ) with( fib ) { fn = 0; } $\C{// constructor}$
+void main( Fibonacci & fib ) with( fib ) {              $\C{// main called on first resume}$
+        int fn1, fn2;                                                           $\C{// retained between resumes}$
+        fn = 0;  fn1 = fn;                                                      $\C{// 1st case}$
+        suspend();                                                                      $\C{// restart last resume}$
+        fn = 1;  fn2 = fn1;  fn1 = fn;                          $\C{// 2nd case}$
+        suspend();                                                                      $\C{// restart last resume}$
+        for ( ;; ) {
+                fn = fn1 + fn2; fn2 = fn1;  fn1 = fn;   $\C{// general case}$
+                suspend();                                                              $\C{// restart last resume}$
+\centering
+\begin{cfa}
+`coroutine` Format {
+        char ch;                                                                $\C{// used for communication}$
+        int g, b;                                                               $\C{// global because used in destructor}$
+};
+void ?{}( Format & fmt ) { `resume( fmt );` } $\C{// prime (start) coroutine}$
+void ^?{}( Format & fmt ) with( fmt ) { if ( g != 0 || b != 0 ) sout | endl; }
+void main( Format & fmt ) with( fmt ) {
+        for ( ;; ) {                                                    $\C{// for as many characters}$
+                for ( g = 0; g < 5; g += 1 ) {          $\C{// groups of 5 blocks}$
+                        for ( b = 0; b < 4; b += 1 ) {  $\C{// blocks of 4 characters}$
+                                `suspend();`
+                                sout | ch;                                      $\C{// print character}$
+                        }
+                        sout | "  ";                                    $\C{// print block separator}$
+                }
+                sout | endl;                                            $\C{// print group separator}$
+        }
+}
+int next( Fibonacci & fib ) with( fib ) {
+        resume( fib );                                                          $\C{// restart last suspend}$
+        return fn;
+}
+int main() {
+        Fibonacci f1, f2;
+        for ( int i = 1; i <= 10; i++ ) {
+                sout | next( f1 ) | next( f2 ) | endl;
+        }
+}
+\end{cfa}
+\caption{Coroutine Fibonacci }
+\label{lst:fibonacci-cfa}
+\end{figure}
+Listing \ref{lst:fmt-line} shows the @Format@ coroutine for restructuring text into groups of character blocks of fixed size.
+The example takes advantage of resuming coroutines in the constructor to simplify the code and highlights the idea that interesting control flow can occur in the constructor.
+\begin{figure}
+\begin{cfa}[tabsize=3,caption={Formatting text into lines of 5 blocks of 4 characters.},label={lst:fmt-line}]
+// format characters into blocks of 4 and groups of 5 blocks per line
+coroutine Format {
+        char ch;                                                                        // used for communication
+        int g, b;                                                               // global because used in destructor
+};
+void  ?{}(Format& fmt) {
+        resume( fmt );                                                  // prime (start) coroutine
+}
+void ^?{}(Format& fmt) with fmt {
+        if ( fmt.g != 0 || fmt.b != 0 )
+        sout | endl;
+}
+void main(Format& fmt) with fmt {
+        for ( ;; ) {                                                    // for as many characters
+                for(g = 0; g < 5; g++) {                // groups of 5 blocks
+                        for(b = 0; b < 4; fb++) {       // blocks of 4 characters
+                                suspend();
+                                sout | ch;                                      // print character
+                        }
+                        sout | "  ";                                    // print block separator
+                }
+                sout | endl;                                            // print group separator
+        }
+}
+void prt(Format & fmt, char ch) {
+void prt( Format & fmt, char ch ) {
         fmt.ch = ch;
+        resume(fmt);
+}
+        `resume( fmt );`
+}
 int main() {
         Format fmt;
         char ch;
         Eof: for ( ;; ) {                                               // read until end of file
                 sin | ch;                                                       // read one character
                 if(eof(sin)) break Eof;                 // eof ?
                 prt(fmt, ch);                                           // push character for formatting
+        for ( ;; ) {                                                    $\C{// read until end of file}$
+                sin | ch;                                                       $\C{// read one character}$
+          if ( eof( sin ) ) break;                              $\C{// eof ?}$
+                prt( fmt, ch );                                         $\C{// push character for formatting}$
+        }
+}
 \end{cfa}
+\caption{Formatting text into lines of 5 blocks of 4 characters.}
+\label{f:fmt-line}
 \end{figure}
+\subsection{Construction}
+\begin{figure}
+\centering
+\lstset{language=CFA,escapechar={},moredelim=**[is][\protect\color{red}]{`}{`}}
+\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
+\begin{cfa}
+`coroutine` Prod {
+        Cons & c;
+        int N, money, receipt;
+};
+void main( Prod & prod ) with( prod ) {
+        // 1st resume starts here
+        for ( int i = 0; i < N; i += 1 ) {
+                int p1 = random( 100 ), p2 = random( 100 );
+                sout | p1 | " " | p2 | endl;
+                int status = delivery( c, p1, p2 );
+                sout | " $" | money | endl | status | endl;
+                receipt += 1;
+        }
+        stop( c );
+        sout | "prod stops" | endl;
+}
+int payment( Prod & prod, int money ) {
+        prod.money = money;
+        `resume( prod );`
+        return prod.receipt;
+}
+void start( Prod & prod, int N, Cons &c ) {
+        &prod.c = &c;
+        prod.[N, receipt] = [N, 0];
+        `resume( prod );`
+}
+int main() {
+        Prod prod;
+        Cons cons = { prod };
+        srandom( getpid() );
+        start( prod, 5, cons );
+}
+\end{cfa}
+&
+\begin{cfa}
+`coroutine` Cons {
+        Prod & p;
+        int p1, p2, status;
+        _Bool done;
+};
+void ?{}( Cons & cons, Prod & p ) {
+        &cons.p = &p;
+        cons.[status, done ] = [0, false];
+}
+void ^?{}( Cons & cons ) {}
+void main( Cons & cons ) with( cons ) {
+        // 1st resume starts here
+        int money = 1, receipt;
+        for ( ; ! done; ) {
+                sout | p1 | " " | p2 | endl | " $" | money | endl;
+                status += 1;
+                receipt = payment( p, money );
+                sout | " #" | receipt | endl;
+                money += 1;
+        }
+        sout | "cons stops" | endl;
+}
+int delivery( Cons & cons, int p1, int p2 ) {
+        cons.[p1, p2] = [p1, p2];
+        `resume( cons );`
+        return cons.status;
+}
+void stop( Cons & cons ) {
+        cons.done = true;
+        `resume( cons );`
+}
+\end{cfa}
+\end{tabular}
+\caption{Producer / consumer: resume-resume cycle, bi-directional communication}
+\label{f:ProdCons}
+\end{figure}
+\subsubsection{Construction}
 One important design challenge for implementing coroutines and threads (shown in section \ref{threads}) is that the runtime system needs to run code after the user-constructor runs to connect the fully constructed object into the system.
 In the case of coroutines, this challenge is simpler since there is no non-determinism from preemption or scheduling.
 …
+}
 \end{cfa}
 The problem in this example is a storage management issue, the function pointer @_thunk0@ is only valid until the end of the block, which limits the viable solutions because storing the function pointer for too long causes undefined behaviour; i.e., the stack-based thunk being destroyed before it can be used.
+The problem in this example is a storage management issue, the function pointer @_thunk0@ is only valid until the end of the block, which limits the viable solutions because storing the function pointer for too long causes undefined behaviour; \ie the stack-based thunk being destroyed before it can be used.
 This challenge is an extension of challenges that come with second-class routines.
 Indeed, GCC nested routines also have the limitation that nested routine cannot be passed outside of the declaration scope.
 The case of coroutines and threads is simply an extension of this problem to multiple call stacks.
+\subsection{Alternative: Composition}
+\subsubsection{Alternative: Composition}
 One solution to this challenge is to use composition/containment, where coroutine fields are added to manage the coroutine.
 …
 This opens the door for user errors and requires extra runtime storage to pass at runtime information that can be known statically.
+\subsection{Alternative: Reserved keyword}
+\subsubsection{Alternative: Reserved keyword}
 The next alternative is to use language support to annotate coroutines as follows:
 \begin{cfa}
 coroutine Fibonacci {
 …
 The reserved keywords are only present to improve ease of use for the common cases.
+\subsection{Alternative: Lambda Objects}
+\subsubsection{Alternative: Lambda Objects}
 For coroutines as for threads, many implementations are based on routine pointers or function objects~\cite{Butenhof97, C++14, MS:VisualC++, BoostCoroutines15}.
 …
 As discussed in section \ref{threads}, this approach is superseded by static approaches in terms of expressivity.
+\subsection{Alternative: Trait-Based Coroutines}
+\subsubsection{Alternative: Trait-Based Coroutines}
 Finally, the underlying approach, which is the one closest to \CFA idioms, is to use trait-based lazy coroutines.
 …
 The combination of these two approaches allows users new to coroutining and concurrency to have an easy and concise specification, while more advanced users have tighter control on memory layout and initialization.
 \section{Thread Interface}\label{threads}
+\subsection{Thread Interface}\label{threads}
 The basic building blocks of multithreading in \CFA are \textbf{cfathread}.
 Both user and kernel threads are supported, where user threads are the concurrency mechanism and kernel threads are the parallel mechanism.
 …
 \end{cfa}
 However, one of the drawbacks of this approach is that threads always form a tree where nodes must always outlive their children, i.e., they are always destroyed in the opposite order of construction because of C scoping rules.
+However, one of the drawbacks of this approach is that threads always form a tree where nodes must always outlive their children, \ie they are always destroyed in the opposite order of construction because of C scoping rules.
 This restriction is relaxed by using dynamic allocation, so threads can outlive the scope in which they are created, much like dynamically allocating memory lets objects outlive the scope in which they are created.
 …
 Since many of these challenges appear with the use of mutable shared state, some languages and libraries simply disallow mutable shared state (Erlang~\cite{Erlang}, Haskell~\cite{Haskell}, Akka (Scala)~\cite{Akka}).
 In these paradigms, interaction among concurrent objects relies on message passing~\cite{Thoth,Harmony,V-Kernel} or other paradigms closely relate to networking concepts (channels~\cite{CSP,Go} for example).
 However, in languages that use routine calls as their core abstraction mechanism, these approaches force a clear distinction between concurrent and non-concurrent paradigms (i.e., message passing versus routine calls).
+However, in languages that use routine calls as their core abstraction mechanism, these approaches force a clear distinction between concurrent and non-concurrent paradigms (\ie message passing versus routine calls).
 This distinction in turn means that, in order to be effective, programmers need to learn two sets of design patterns.
 While this distinction can be hidden away in library code, effective use of the library still has to take both paradigms into account.
 …
 One of the most natural, elegant, and efficient mechanisms for synchronization and communication, especially for shared-memory systems, is the \emph{monitor}.
 Monitors were first proposed by Brinch Hansen~\cite{Hansen73} and later described and extended by C.A.R.~Hoare~\cite{Hoare74}.
 Many programming languages---e.g., Concurrent Pascal~\cite{ConcurrentPascal}, Mesa~\cite{Mesa}, Modula~\cite{Modula-2}, Turing~\cite{Turing:old}, Modula-3~\cite{Modula-3}, NeWS~\cite{NeWS}, Emerald~\cite{Emerald}, \uC~\cite{Buhr92a} and Java~\cite{Java}---provide monitors as explicit language constructs.
+Many programming languages---\eg Concurrent Pascal~\cite{ConcurrentPascal}, Mesa~\cite{Mesa}, Modula~\cite{Modula-2}, Turing~\cite{Turing:old}, Modula-3~\cite{Modula-3}, NeWS~\cite{NeWS}, Emerald~\cite{Emerald}, \uC~\cite{Buhr92a} and Java~\cite{Java}---provide monitors as explicit language constructs.
 In addition, operating-system kernels and device drivers have a monitor-like structure, although they often use lower-level primitives such as semaphores or locks to simulate monitors.
 For these reasons, this project proposes monitors as the core concurrency construct.
+\section{Basics}
+\subsection{Basics}
 Non-determinism requires concurrent systems to offer support for mutual-exclusion and synchronization.
 Mutual-exclusion is the concept that only a fixed number of threads can access a critical section at any given time, where a critical section is a group of instructions on an associated portion of data that requires the restricted access.
 On the other hand, synchronization enforces relative ordering of execution and synchronization tools provide numerous mechanisms to establish timing relationships among threads.
+\subsection{Mutual-Exclusion}
+\subsubsection{Mutual-Exclusion}
 As mentioned above, mutual-exclusion is the guarantee that only a fix number of threads can enter a critical section at once.
 However, many solutions exist for mutual exclusion, which vary in terms of performance, flexibility and ease of use.
 Methods range from low-level locks, which are fast and flexible but require significant attention to be correct, to  higher-level concurrency techniques, which sacrifice some performance in order to improve ease of use.
 Ease of use comes by either guaranteeing some problems cannot occur (e.g., being deadlock free) or by offering a more explicit coupling between data and corresponding critical section.
 For example, the \CC @std::atomic<T>@ offers an easy way to express mutual-exclusion on a restricted set of operations (e.g., reading/writing large types atomically).
+Ease of use comes by either guaranteeing some problems cannot occur (\eg being deadlock free) or by offering a more explicit coupling between data and corresponding critical section.
+For example, the \CC @std::atomic<T>@ offers an easy way to express mutual-exclusion on a restricted set of operations (\eg reading/writing large types atomically).
 Another challenge with low-level locks is composability.
 Locks have restricted composability because it takes careful organizing for multiple locks to be used while preventing deadlocks.
 Easing composability is another feature higher-level mutual-exclusion mechanisms often offer.
+\subsection{Synchronization}
+\subsubsection{Synchronization}
 As with mutual-exclusion, low-level synchronization primitives often offer good performance and good flexibility at the cost of ease of use.
 Again, higher-level mechanisms often simplify usage by adding either better coupling between synchronization and data (e.g., message passing) or offering a simpler solution to otherwise involved challenges.
+Again, higher-level mechanisms often simplify usage by adding either better coupling between synchronization and data (\eg message passing) or offering a simpler solution to otherwise involved challenges.
 As mentioned above, synchronization can be expressed as guaranteeing that event \textit{X} always happens before \textit{Y}.
 Most of the time, synchronization happens within a critical section, where threads must acquire mutual-exclusion in a certain order.
 …
 Algorithms that use flag variables to detect barging threads are said to be using barging avoidance, while algorithms that baton-pass locks~\cite{Andrews89} between threads instead of releasing the locks are said to be using barging prevention.
 % ======================================================================
 % ======================================================================
 …
 Another aspect to consider is when a monitor acquires its mutual exclusion.
 For example, a monitor may need to be passed through multiple helper routines that do not acquire the monitor mutual-exclusion on entry.
 Passthrough can occur for generic helper routines (@swap@, @sort@, etc.) or specific helper routines like the following to implement an atomic counter:
+Passthrough can occur for generic helper routines (@swap@, @sort@, \etc) or specific helper routines like the following to implement an atomic counter:
 \begin{cfa}
 …
 The call semantics discussed above have one software engineering issue: only a routine can acquire the mutual-exclusion of a set of monitor. \CFA offers the @mutex@ statement to work around the need for unnecessary names, avoiding a major software engineering problem~\cite{2FTwoHardThings}.
 Table \ref{lst:mutex-stmt} shows an example of the @mutex@ statement, which introduces a new scope in which the mutual-exclusion of a set of monitor is acquired.
+Table \ref{f:mutex-stmt} shows an example of the @mutex@ statement, which introduces a new scope in which the mutual-exclusion of a set of monitor is acquired.
 Beyond naming, the @mutex@ statement has no semantic difference from a routine call with @mutex@ parameters.
 …
 \end{center}
 \caption{Regular call semantics vs. \protect\lstinline|mutex| statement}
 \label{lst:mutex-stmt}
+\label{f:mutex-stmt}
 \end{table}
 …
 In addition to mutual exclusion, the monitors at the core of \CFA's concurrency can also be used to achieve synchronization.
 With monitors, this capability is generally achieved with internal or external scheduling as in~\cite{Hoare74}.
 With \textbf{scheduling} loosely defined as deciding which thread acquires the critical section next, \textbf{internal scheduling} means making the decision from inside the critical section (i.e., with access to the shared state), while \textbf{external scheduling} means making the decision when entering the critical section (i.e., without access to the shared state).
+With \textbf{scheduling} loosely defined as deciding which thread acquires the critical section next, \textbf{internal scheduling} means making the decision from inside the critical section (\ie with access to the shared state), while \textbf{external scheduling} means making the decision when entering the critical section (\ie without access to the shared state).
 Since internal scheduling within a single monitor is mostly a solved problem, this paper concentrates on extending internal scheduling to multiple monitors.
 Indeed, like the \textbf{bulk-acq} semantics, internal scheduling extends to multiple monitors in a way that is natural to the user but requires additional complexity on the implementation side.
 …
 There are two details to note here.
 First, @signal@ is a delayed operation; it only unblocks the waiting thread when it reaches the end of the critical section.
 This semantics is needed to respect mutual-exclusion, i.e., the signaller and signalled thread cannot be in the monitor simultaneously.
+This semantics is needed to respect mutual-exclusion, \ie the signaller and signalled thread cannot be in the monitor simultaneously.
 The alternative is to return immediately after the call to @signal@, which is significantly more restrictive.
 Second, in \CFA, while it is common to store a @condition@ as a field of the monitor, a @condition@ variable can be stored/created independently of a monitor.
 …
 A larger example is presented to show complex issues for \textbf{bulk-acq} and its implementation options are analyzed.
 Listing \ref{lst:int-bulk-cfa} shows an example where \textbf{bulk-acq} adds a significant layer of complexity to the internal signalling semantics, and listing \ref{lst:int-bulk-cfa} shows the corresponding \CFA code to implement the cfa-code in listing \ref{lst:int-bulk-cfa}.
 For the purpose of translating the given cfa-code into \CFA-code, any method of introducing a monitor is acceptable, e.g., @mutex@ parameters, global variables, pointer parameters, or using locals with the @mutex@ statement.
+Figure~\ref{f:int-bulk-cfa} shows an example where \textbf{bulk-acq} adds a significant layer of complexity to the internal signalling semantics, and listing \ref{f:int-bulk-cfa} shows the corresponding \CFA code to implement the cfa-code in listing \ref{f:int-bulk-cfa}.
+For the purpose of translating the given cfa-code into \CFA-code, any method of introducing a monitor is acceptable, \eg @mutex@ parameters, global variables, pointer parameters, or using locals with the @mutex@ statement.
 \begin{figure}
 …
 \end{cfa}
 \end{multicols}
 \begin{cfa}[caption={Internal scheduling with \textbf{bulk-acq}},label={lst:int-bulk-cfa}]
+\begin{cfa}[caption={Internal scheduling with \textbf{bulk-acq}},label={f:int-bulk-cfa}]
 \end{cfa}
 \begin{center}
 …
 \end{cfa}
 \end{multicols}
 \begin{cfa}[caption={Equivalent \CFA code for listing \ref{lst:int-bulk-cfa}},label={lst:int-bulk-cfa}]
+\begin{cfa}[caption={Equivalent \CFA code for listing \ref{f:int-bulk-cfa}},label={f:int-bulk-cfa}]
 \end{cfa}
 \begin{multicols}{2}
 …
 \end{cfa}
 \end{multicols}
 \begin{cfa}[caption={Listing \ref{lst:int-bulk-cfa}, with delayed signalling comments},label={lst:int-secret}]
+\begin{cfa}[caption={Figure~\ref{f:int-bulk-cfa}, with delayed signalling comments},label={f:int-secret}]
 \end{cfa}
 \end{figure}
 The complexity begins at code sections 4 and 8 in listing \ref{lst:int-bulk-cfa}, which are where the existing semantics of internal scheduling needs to be extended for multiple monitors.
+The complexity begins at code sections 4 and 8 in listing \ref{f:int-bulk-cfa}, which are where the existing semantics of internal scheduling needs to be extended for multiple monitors.
 The root of the problem is that \textbf{bulk-acq} is used in a context where one of the monitors is already acquired, which is why it is important to define the behaviour of the previous cfa-code.
 When the signaller thread reaches the location where it should ``release @A & B@'' (listing \ref{lst:int-bulk-cfa} line \ref{line:releaseFirst}), it must actually transfer ownership of monitor @B@ to the waiting thread.
+When the signaller thread reaches the location where it should ``release @A & B@'' (listing \ref{f:int-bulk-cfa} line \ref{line:releaseFirst}), it must actually transfer ownership of monitor @B@ to the waiting thread.
 This ownership transfer is required in order to prevent barging into @B@ by another thread, since both the signalling and signalled threads still need monitor @A@.
 There are three options:
 …
 This solution has the main benefit of transferring ownership of groups of monitors, which simplifies the semantics from multiple objects to a single group of objects, effectively making the existing single-monitor semantic viable by simply changing monitors to monitor groups.
 This solution releases the monitors once every monitor in a group can be released.
 However, since some monitors are never released (e.g., the monitor of a thread), this interpretation means a group might never be released.
+However, since some monitors are never released (\eg the monitor of a thread), this interpretation means a group might never be released.
 A more interesting interpretation is to transfer the group until all its monitors are released, which means the group is not passed further and a thread can retain its locks.
 However, listing \ref{lst:int-secret} shows this solution can become much more complicated depending on what is executed while secretly holding B at line \ref{line:secret}, while avoiding the need to transfer ownership of a subset of the condition monitors.
 Listing \ref{lst:dependency} shows a slightly different example where a third thread is waiting on monitor @A@, using a different condition variable.
+However, listing \ref{f:int-secret} shows this solution can become much more complicated depending on what is executed while secretly holding B at line \ref{line:secret}, while avoiding the need to transfer ownership of a subset of the condition monitors.
+Figure~\ref{f:dependency} shows a slightly different example where a third thread is waiting on monitor @A@, using a different condition variable.
 Because the third thread is signalled when secretly holding @B@, the goal  becomes unreachable.
 Depending on the order of signals (listing \ref{lst:dependency} line \ref{line:signal-ab} and \ref{line:signal-a}) two cases can happen:
+Depending on the order of signals (listing \ref{f:dependency} line \ref{line:signal-ab} and \ref{line:signal-a}) two cases can happen:
 \paragraph{Case 1: thread $\alpha$ goes first.} In this case, the problem is that monitor @A@ needs to be passed to thread $\beta$ when thread $\alpha$ is done with it.
 …
 Note that ordering is not determined by a race condition but by whether signalled threads are enqueued in FIFO or FILO order.
 However, regardless of the answer, users can move line \ref{line:signal-a} before line \ref{line:signal-ab} and get the reverse effect for listing \ref{lst:dependency}.
+However, regardless of the answer, users can move line \ref{line:signal-a} before line \ref{line:signal-ab} and get the reverse effect for listing \ref{f:dependency}.
 In both cases, the threads need to be able to distinguish, on a per monitor basis, which ones need to be released and which ones need to be transferred, which means knowing when to release a group becomes complex and inefficient (see next section) and therefore effectively precludes this approach.
 …
 \end{cfa}
 \end{multicols}
 \begin{cfa}[caption={Pseudo-code for the three thread example.},label={lst:dependency}]
+\begin{cfa}[caption={Pseudo-code for the three thread example.},label={f:dependency}]
 \end{cfa}
 \begin{center}
 \input{dependency}
 \end{center}
 \caption{Dependency graph of the statements in listing \ref{lst:dependency}}
+\caption{Dependency graph of the statements in listing \ref{f:dependency}}
 \label{fig:dependency}
 \end{figure}
 In listing \ref{lst:int-bulk-cfa}, there is a solution that satisfies both barging prevention and mutual exclusion.
+In listing \ref{f:int-bulk-cfa}, there is a solution that satisfies both barging prevention and mutual exclusion.
 If ownership of both monitors is transferred to the waiter when the signaller releases @A & B@ and then the waiter transfers back ownership of @A@ back to the signaller when it releases it, then the problem is solved (@B@ is no longer in use at this point).
 Dynamically finding the correct order is therefore the second possible solution.
 The problem is effectively resolving a dependency graph of ownership requirements.
 Here even the simplest of code snippets requires two transfers and has a super-linear complexity.
 This complexity can be seen in listing \ref{lst:explosion}, which is just a direct extension to three monitors, requires at least three ownership transfer and has multiple solutions.
+This complexity can be seen in listing \ref{f:explosion}, which is just a direct extension to three monitors, requires at least three ownership transfer and has multiple solutions.
 Furthermore, the presence of multiple solutions for ownership transfer can cause deadlock problems if a specific solution is not consistently picked; In the same way that multiple lock acquiring order can cause deadlocks.
 \begin{figure}
 …
 \end{cfa}
 \end{multicols}
 \begin{cfa}[caption={Extension to three monitors of listing \ref{lst:int-bulk-cfa}},label={lst:explosion}]
+\begin{cfa}[caption={Extension to three monitors of listing \ref{f:int-bulk-cfa}},label={f:explosion}]
 \end{cfa}
 \end{figure}
 Given the three threads example in listing \ref{lst:dependency}, figure \ref{fig:dependency} shows the corresponding dependency graph that results, where every node is a statement of one of the three threads, and the arrows the dependency of that statement (e.g., $\alpha1$ must happen before $\alpha2$).
+Given the three threads example in listing \ref{f:dependency}, figure \ref{fig:dependency} shows the corresponding dependency graph that results, where every node is a statement of one of the three threads, and the arrows the dependency of that statement (\eg $\alpha1$ must happen before $\alpha2$).
 The extra challenge is that this dependency graph is effectively post-mortem, but the runtime system needs to be able to build and solve these graphs as the dependencies unfold.
 Resolving dependency graphs being a complex and expensive endeavour, this solution is not the preferred one.
 …
 \subsubsection{Partial Signalling} \label{partial-sig}
 Finally, the solution that is chosen for \CFA is to use partial signalling.
 Again using listing \ref{lst:int-bulk-cfa}, the partial signalling solution transfers ownership of monitor @B@ at lines \ref{line:signal1} to the waiter but does not wake the waiting thread since it is still using monitor @A@.
+Again using listing \ref{f:int-bulk-cfa}, the partial signalling solution transfers ownership of monitor @B@ at lines \ref{line:signal1} to the waiter but does not wake the waiting thread since it is still using monitor @A@.
 Only when it reaches line \ref{line:lastRelease} does it actually wake up the waiting thread.
 This solution has the benefit that complexity is encapsulated into only two actions: passing monitors to the next owner when they should be released and conditionally waking threads if all conditions are met.
 …
 Furthermore, after being fully implemented, this solution does not appear to have any significant downsides.
 Using partial signalling, listing \ref{lst:dependency} can be solved easily:
+Using partial signalling, listing \ref{f:dependency} can be solved easily:
 \begin{itemize}
         \item When thread $\gamma$ reaches line \ref{line:release-ab} it transfers monitor @B@ to thread $\alpha$ and continues to hold monitor @A@.
 …
 This method is more constrained and explicit, which helps users reduce the non-deterministic nature of concurrency.
 Indeed, as the following examples demonstrate, external scheduling allows users to wait for events from other threads without the concern of unrelated events occurring.
 External scheduling can generally be done either in terms of control flow (e.g., Ada with @accept@, \uC with @_Accept@) or in terms of data (e.g., Go with channels).
+External scheduling can generally be done either in terms of control flow (\eg Ada with @accept@, \uC with @_Accept@) or in terms of data (\eg Go with channels).
 Of course, both of these paradigms have their own strengths and weaknesses, but for this project, control-flow semantics was chosen to stay consistent with the rest of the languages semantics.
 Two challenges specific to \CFA arise when trying to add external scheduling with loose object definitions and multiple-monitor routines.
 …
 There are other alternatives to these pictures, but in the case of the left picture, implementing a fast accept check is relatively easy.
 Restricted to a fixed number of mutex members, N, the accept check reduces to updating a bitmask when the acceptor queue changes, a check that executes in a single instruction even with a fairly large number (e.g., 128) of mutex members.
+Restricted to a fixed number of mutex members, N, the accept check reduces to updating a bitmask when the acceptor queue changes, a check that executes in a single instruction even with a fairly large number (\eg 128) of mutex members.
 This approach requires a unique dense ordering of routines with an upper-bound and that ordering must be consistent across translation units.
 For OO languages these constraints are common, since objects only offer adding member routines consistently across translation units via inheritance.
 …
 Generating a mask dynamically means that the storage for the mask information can vary between calls to @waitfor@, allowing for more flexibility and extensions.
 Storing an array of accepted function pointers replaces the single instruction bitmask comparison with dereferencing a pointer followed by a linear search.
 Furthermore, supporting nested external scheduling (e.g., listing \ref{lst:nest-ext}) may now require additional searches for the @waitfor@ statement to check if a routine is already queued.
+Furthermore, supporting nested external scheduling (\eg listing \ref{f:nest-ext}) may now require additional searches for the @waitfor@ statement to check if a routine is already queued.
 \begin{figure}
 \begin{cfa}[caption={Example of nested external scheduling},label={lst:nest-ext}]
+\begin{cfa}[caption={Example of nested external scheduling},label={f:nest-ext}]
 monitor M {};
 void foo( M & mutex a ) {}
 …
 While the set of monitors can be any list of expressions, the function name is more restricted because the compiler validates at compile time the validity of the function type and the parameters used with the @waitfor@ statement.
 It checks that the set of monitors passed in matches the requirements for a function call.
 Listing \ref{lst:waitfor} shows various usages of the waitfor statement and which are acceptable.
+Figure~\ref{f:waitfor} shows various usages of the waitfor statement and which are acceptable.
 The choice of the function type is made ignoring any non-@mutex@ parameter.
 One limitation of the current implementation is that it does not handle overloading, but overloading is possible.
 \begin{figure}
 \begin{cfa}[caption={Various correct and incorrect uses of the waitfor statement},label={lst:waitfor}]
+\begin{cfa}[caption={Various correct and incorrect uses of the waitfor statement},label={f:waitfor}]
 monitor A{};
 monitor B{};
 …
 A @waitfor@ chain can also be followed by a @timeout@, to signify an upper bound on the wait, or an @else@, to signify that the call should be non-blocking, which checks for a matching function call already arrived and otherwise continues.
 Any and all of these clauses can be preceded by a @when@ condition to dynamically toggle the accept clauses on or off based on some current state.
 Listing \ref{lst:waitfor2} demonstrates several complex masks and some incorrect ones.
+Figure~\ref{f:waitfor2} demonstrates several complex masks and some incorrect ones.
 \begin{figure}
 …
 \end{cfa}
 \caption{Correct and incorrect uses of the or, else, and timeout clause around a waitfor statement}
 \label{lst:waitfor2}
+\label{f:waitfor2}
 \end{figure}
 …
 However, a more expressive approach is to flip ordering of execution when waiting for the destructor, meaning that waiting for the destructor allows the destructor to run after the current @mutex@ routine, similarly to how a condition is signalled.
 \begin{figure}
 \begin{cfa}[caption={Example of an executor which executes action in series until the destructor is called.},label={lst:dtor-order}]
+\begin{cfa}[caption={Example of an executor which executes action in series until the destructor is called.},label={f:dtor-order}]
 monitor Executer {};
 struct  Action;
 …
 \end{cfa}
 \end{figure}
 For example, listing \ref{lst:dtor-order} shows an example of an executor with an infinite loop, which waits for the destructor to break out of this loop.
+For example, listing \ref{f:dtor-order} shows an example of an executor with an infinite loop, which waits for the destructor to break out of this loop.
 Switching the semantic meaning introduces an idiomatic way to terminate a task and/or wait for its termination via destruction.
 …
 In this decade, it is no longer reasonable to create a high-performance application without caring about parallelism.
 Indeed, parallelism is an important aspect of performance and more specifically throughput and hardware utilization.
 The lowest-level approach of parallelism is to use \textbf{kthread} in combination with semantics like @fork@, @join@, etc.
+The lowest-level approach of parallelism is to use \textbf{kthread} in combination with semantics like @fork@, @join@, \etc.
 However, since these have significant costs and limitations, \textbf{kthread} are now mostly used as an implementation tool rather than a user oriented one.
 There are several alternatives to solve these issues that all have strengths and weaknesses.
 …
 While the choice between the three paradigms listed above may have significant performance implications, it is difficult to pin down the performance implications of choosing a model at the language level.
 Indeed, in many situations one of these paradigms may show better performance but it all strongly depends on the workload.
 Having a large amount of mostly independent units of work to execute almost guarantees equivalent performance across paradigms and that the \textbf{pool}-based system has the best efficiency thanks to the lower memory overhead (i.e., no thread stack per job).
+Having a large amount of mostly independent units of work to execute almost guarantees equivalent performance across paradigms and that the \textbf{pool}-based system has the best efficiency thanks to the lower memory overhead (\ie no thread stack per job).
 However, interactions among jobs can easily exacerbate contention.
 User-level threads allow fine-grain context switching, which results in better resource utilization, but a context switch is more expensive and the extra control means users need to tweak more variables to get the desired performance.
 …
 The first step towards the monitor implementation is simple @mutex@ routines.
 In the single monitor case, mutual-exclusion is done using the entry/exit procedure in listing \ref{lst:entry1}.
+In the single monitor case, mutual-exclusion is done using the entry/exit procedure in listing \ref{f:entry1}.
 The entry/exit procedures do not have to be extended to support multiple monitors.
 Indeed it is sufficient to enter/leave monitors one-by-one as long as the order is correct to prevent deadlock~\cite{Havender68}.
 …
 \end{cfa}
 \end{multicols}
 \begin{cfa}[caption={Initial entry and exit routine for monitors},label={lst:entry1}]
+\begin{cfa}[caption={Initial entry and exit routine for monitors},label={f:entry1}]
 \end{cfa}
 \end{figure}
 …
 First of all, interaction between @otype@ polymorphism (see Section~\ref{s:ParametricPolymorphism}) and monitors is impossible since monitors do not support copying.
 Therefore, the main question is how to support @dtype@ polymorphism.
 It is important to present the difference between the two acquiring options: \textbf{callsite-locking} and entry-point locking, i.e., acquiring the monitors before making a mutex routine-call or as the first operation of the mutex routine-call.
+It is important to present the difference between the two acquiring options: \textbf{callsite-locking} and entry-point locking, \ie acquiring the monitors before making a mutex routine-call or as the first operation of the mutex routine-call.
 For example:
 \begin{table}
 …
 \end{table}
 Note the @mutex@ keyword relies on the type system, which means that in cases where a generic monitor-routine is desired, writing the mutex routine is possible with the proper trait, e.g.:
+Note the @mutex@ keyword relies on the type system, which means that in cases where a generic monitor-routine is desired, writing the mutex routine is possible with the proper trait, \eg:
 \begin{cfa}
 // Incorrect: T may not be monitor
 …
 Both entry point and \textbf{callsite-locking} are feasible implementations.
 The current \CFA implementation uses entry-point locking because it requires less work when using \textbf{raii}, effectively transferring the burden of implementation to object construction/destruction.
 It is harder to use \textbf{raii} for call-site locking, as it does not necessarily have an existing scope that matches exactly the scope of the mutual exclusion, i.e., the function body.
+It is harder to use \textbf{raii} for call-site locking, as it does not necessarily have an existing scope that matches exactly the scope of the mutual exclusion, \ie the function body.
 For example, the monitor call can appear in the middle of an expression.
 Furthermore, entry-point locking requires less code generation since any useful routine is called multiple times but there is only one entry point for many call sites.
 …
 Specifically, all @pthread@s created also have a stack created with them, which should be used as much as possible.
 Normally, coroutines also create their own stack to run on, however, in the case of the coroutines used for processors, these coroutines run directly on the \textbf{kthread} stack, effectively stealing the processor stack.
 The exception to this rule is the Main Processor, i.e., the initial \textbf{kthread} that is given to any program.
+The exception to this rule is the Main Processor, \ie the initial \textbf{kthread} that is given to any program.
 In order to respect C user expectations, the stack of the initial kernel thread, the main stack of the program, is used by the main user thread rather than the main processor, which can grow very large.
 …
 When the preemption system receives a change in preemption, it inserts the time in a sorted order and sets a kernel timer for the closest one, effectively stepping through preemption events on each signal sent by the timer.
 These timers use the Linux signal {\tt SIGALRM}, which is delivered to the process rather than the kernel-thread.
 This results in an implementation problem, because when delivering signals to a process, the kernel can deliver the signal to any kernel thread for which the signal is not blocked, i.e.:
+This results in an implementation problem, because when delivering signals to a process, the kernel can deliver the signal to any kernel thread for which the signal is not blocked, \ie:
 \begin{quote}
 A process-directed signal may be delivered to any one of the threads that does not currently have the signal blocked.
 …
 However, since the kernel thread handling preemption requires a different signal mask, executing user threads on the kernel-alarm thread can cause deadlocks.
 For this reason, the alarm thread is in a tight loop around a system call to @sigwaitinfo@, requiring very little CPU time for preemption.
 One final detail about the alarm thread is how to wake it when additional communication is required (e.g., on thread termination).
+One final detail about the alarm thread is how to wake it when additional communication is required (\eg on thread termination).
 This unblocking is also done using {\tt SIGALRM}, but sent through the @pthread_sigqueue@.
 Indeed, @sigwait@ can differentiate signals sent from @pthread_sigqueue@ from signals sent from alarms or the kernel.
 …
 \end{figure}
 This picture and the proper entry and leave algorithms (see listing \ref{lst:entry2}) is the fundamental implementation of internal scheduling.
+This picture and the proper entry and leave algorithms (see listing \ref{f:entry2}) is the fundamental implementation of internal scheduling.
 Note that when a thread is moved from the condition to the AS-stack, it is conceptually split into N pieces, where N is the number of monitors specified in the parameter list.
 The thread is woken up when all the pieces have popped from the AS-stacks and made active.
 …
 \end{cfa}
 \end{multicols}
 \begin{cfa}[caption={Entry and exit routine for monitors with internal scheduling},label={lst:entry2}]
+\begin{cfa}[caption={Entry and exit routine for monitors with internal scheduling},label={f:entry2}]
 \end{cfa}
 \end{figure}
 The solution discussed in \ref{intsched} can be seen in the exit routine of listing \ref{lst:entry2}.
+The solution discussed in \ref{intsched} can be seen in the exit routine of listing \ref{f:entry2}.
 Basically, the solution boils down to having a separate data structure for the condition queue and the AS-stack, and unconditionally transferring ownership of the monitors but only unblocking the thread when the last monitor has transferred ownership.
 This solution is deadlock safe as well as preventing any potential barging.
 …
 The main idea behind them is that, a thread cannot contain an arbitrary number of intrusive ``next'' pointers for linking onto monitors.
 The @condition node@ is the data structure that is queued onto a condition variable and, when signalled, the condition queue is popped and each @condition criterion@ is moved to the AS-stack.
 Once all the criteria have been popped from their respective AS-stacks, the thread is woken up, which is what is shown in listing \ref{lst:entry2}.
+Once all the criteria have been popped from their respective AS-stacks, the thread is woken up, which is what is shown in listing \ref{f:entry2}.
 % ======================================================================
 …
 % ======================================================================
 Similarly to internal scheduling, external scheduling for multiple monitors relies on the idea that waiting-thread queues are no longer specific to a single monitor, as mentioned in section \ref{extsched}.
 For internal scheduling, these queues are part of condition variables, which are still unique for a given scheduling operation (i.e., no signal statement uses multiple conditions).
+For internal scheduling, these queues are part of condition variables, which are still unique for a given scheduling operation (\ie no signal statement uses multiple conditions).
 However, in the case of external scheduling, there is no equivalent object which is associated with @waitfor@ statements.
 This absence means the queues holding the waiting threads must be stored inside at least one of the monitors that is acquired.
 …
 Note that if a thread has acquired two monitors but executes a @waitfor@ with only one monitor as a parameter, setting the mask of acceptable routines to both monitors will not cause any problems since the extra monitor will not change ownership regardless.
 This becomes relevant when @when@ clauses affect the number of monitors passed to a @waitfor@ statement.
         \item The entry/exit routines need to be updated as shown in listing \ref{lst:entry3}.
+        \item The entry/exit routines need to be updated as shown in listing \ref{f:entry3}.
 \end{itemize}
 …
 Indeed, when waiting for the destructors, storage is needed for the waiting context and the lifetime of said storage needs to outlive the waiting operation it is needed for.
 For regular @waitfor@ statements, the call stack of the routine itself matches this requirement but it is no longer the case when waiting for the destructor since it is pushed on to the AS-stack for later.
 The @waitfor@ semantics can then be adjusted correspondingly, as seen in listing \ref{lst:entry-dtor}
+The @waitfor@ semantics can then be adjusted correspondingly, as seen in listing \ref{f:entry-dtor}
 \begin{figure}
 …
 \end{cfa}
 \end{multicols}
 \begin{cfa}[caption={Entry and exit routine for monitors with internal scheduling and external scheduling},label={lst:entry3}]
+\begin{cfa}[caption={Entry and exit routine for monitors with internal scheduling and external scheduling},label={f:entry3}]
 \end{cfa}
 \end{figure}
 …
 \end{cfa}
 \end{multicols}
 \begin{cfa}[caption={Pseudo code for the \protect\lstinline|waitfor| routine and the \protect\lstinline|mutex| entry routine for destructors},label={lst:entry-dtor}]
+\begin{cfa}[caption={Pseudo code for the \protect\lstinline|waitfor| routine and the \protect\lstinline|mutex| entry routine for destructors},label={f:entry-dtor}]
 \end{cfa}
 \end{figure}
 …
 For example, here is a very simple two thread pipeline that could be used for a simulator of a game engine:
 \begin{figure}
 \begin{cfa}[caption={Toy simulator using \protect\lstinline|thread|s and \protect\lstinline|monitor|s.},label={lst:engine-v1}]
+\begin{cfa}[caption={Toy simulator using \protect\lstinline|thread|s and \protect\lstinline|monitor|s.},label={f:engine-v1}]
 // Visualization declaration
 thread Renderer {} renderer;
 …
 Luckily, the monitor semantics can also be used to clearly enforce a shutdown order in a concise manner:
 \begin{figure}
 \begin{cfa}[caption={Same toy simulator with proper termination condition.},label={lst:engine-v2}]
+\begin{cfa}[caption={Same toy simulator with proper termination condition.},label={f:engine-v2}]
 // Visualization declaration
 thread Renderer {} renderer;
 …
+}
 \end{cfa}
 This function is called by the kernel to fetch the default preemption rate, where 0 signifies an infinite time-slice, i.e., no preemption.
 However, once clusters are fully implemented, it will be possible to create fibers and \textbf{uthread} in the same system, as in listing \ref{lst:fiber-uthread}
+This function is called by the kernel to fetch the default preemption rate, where 0 signifies an infinite time-slice, \ie no preemption.
+However, once clusters are fully implemented, it will be possible to create fibers and \textbf{uthread} in the same system, as in listing \ref{f:fiber-uthread}
 \begin{figure}
 \lstset{language=CFA,deletedelim=**[is][]{`}{`}}
 \begin{cfa}[caption={Using fibers and \textbf{uthread} side-by-side in \CFA},label={lst:fiber-uthread}]
+\begin{cfa}[caption={Using fibers and \textbf{uthread} side-by-side in \CFA},label={f:fiber-uthread}]
 // Cluster forward declaration
 struct cluster;
 …
 Yielding causes the thread to context-switch to the scheduler and back, more precisely: from the \textbf{uthread} to the \textbf{kthread} then from the \textbf{kthread} back to the same \textbf{uthread} (or a different one in the general case).
 In order to make the comparison fair, coroutines also execute a 2-step context-switch by resuming another coroutine which does nothing but suspending in a tight loop, which is a resume/suspend cycle instead of a yield.
 Listing \ref{lst:ctx-switch} shows the code for coroutines and threads with the results in table \ref{tab:ctx-switch}.
+Figure~\ref{f:ctx-switch} shows the code for coroutines and threads with the results in table \ref{tab:ctx-switch}.
 All omitted tests are functionally identical to one of these tests.
 The difference between coroutines and threads can be attributed to the cost of scheduling.
 …
 \end{cfa}
 \end{multicols}
 \begin{cfa}[caption={\CFA benchmark code used to measure context-switches for coroutines and threads.},label={lst:ctx-switch}]
+\begin{cfa}[caption={\CFA benchmark code used to measure context-switches for coroutines and threads.},label={f:ctx-switch}]
 \end{cfa}
 \end{figure}
 …
 The next interesting benchmark is to measure the overhead to enter/leave a critical-section.
 For monitors, the simplest approach is to measure how long it takes to enter and leave a monitor routine.
 Listing \ref{lst:mutex} shows the code for \CFA.
+Figure~\ref{f:mutex} shows the code for \CFA.
 To put the results in context, the cost of entering a non-inline function and the cost of acquiring and releasing a @pthread_mutex@ lock is also measured.
 The results can be shown in table \ref{tab:mutex}.
 \begin{figure}
 \begin{cfa}[caption={\CFA benchmark code used to measure mutex routines.},label={lst:mutex}]
+\begin{cfa}[caption={\CFA benchmark code used to measure mutex routines.},label={f:mutex}]
 monitor M {};
 void __attribute__((noinline)) call( M & mutex m /*, m2, m3, m4*/ ) {}
 …
 \subsection{Internal Scheduling}
 The internal-scheduling benchmark measures the cost of waiting on and signalling a condition variable.
 Listing \ref{lst:int-sched} shows the code for \CFA, with results table \ref{tab:int-sched}.
+Figure~\ref{f:int-sched} shows the code for \CFA, with results table \ref{tab:int-sched}.
 As with all other benchmarks, all omitted tests are functionally identical to one of these tests.
 \begin{figure}
 \begin{cfa}[caption={Benchmark code for internal scheduling},label={lst:int-sched}]
+\begin{cfa}[caption={Benchmark code for internal scheduling},label={f:int-sched}]
 volatile int go = 0;
 condition c;
 …
 \subsection{External Scheduling}
 The Internal scheduling benchmark measures the cost of the @waitfor@ statement (@_Accept@ in \uC).
 Listing \ref{lst:ext-sched} shows the code for \CFA, with results in table \ref{tab:ext-sched}.
+Figure~\ref{f:ext-sched} shows the code for \CFA, with results in table \ref{tab:ext-sched}.
 As with all other benchmarks, all omitted tests are functionally identical to one of these tests.
 \begin{figure}
 \begin{cfa}[caption={Benchmark code for external scheduling},label={lst:ext-sched}]
+\begin{cfa}[caption={Benchmark code for external scheduling},label={f:ext-sched}]
 volatile int go = 0;
 monitor M {};
 …
 \end{table}
 \subsection{Object Creation}
 Finally, the last benchmark measures the cost of creation for concurrent objects.
 Listing \ref{lst:creation} shows the code for @pthread@s and \CFA threads, with results shown in table \ref{tab:creation}.
+Figure~\ref{f:creation} shows the code for @pthread@s and \CFA threads, with results shown in table \ref{tab:creation}.
 As with all other benchmarks, all omitted tests are functionally identical to one of these tests.
 The only note here is that the call stacks of \CFA coroutines are lazily created, therefore without priming the coroutine, the creation cost is very low.
 …
 \end{center}
 \caption{Benchmark code for \protect\lstinline|pthread|s and \CFA to measure object creation}
 \label{lst:creation}
+\label{f:creation}
 \end{figure}
 …
 While most of the parallelism tools are aimed at data parallelism and control-flow parallelism, many modern workloads are not bound on computation but on IO operations, a common case being web servers and XaaS (anything as a service).
 These types of workloads often require significant engineering around amortizing costs of blocking IO operations.
 At its core, non-blocking I/O is an operating system level feature that allows queuing IO operations (e.g., network operations) and registering for notifications instead of waiting for requests to complete.
+At its core, non-blocking I/O is an operating system level feature that allows queuing IO operations (\eg network operations) and registering for notifications instead of waiting for requests to complete.
 In this context, the role of the language makes Non-Blocking IO easily available and with low overhead.
 The current trend is to use asynchronous programming using tools like callbacks and/or futures and promises, which can be seen in frameworks like Node.js~\cite{NodeJs} for JavaScript, Spring MVC~\cite{SpringMVC} for Java and Django~\cite{Django} for Python.
 …
 This type of parallelism can be achieved both at the language level and at the library level.
 The canonical example of implicit parallelism is parallel for loops, which are the simplest example of a divide and conquer algorithms~\cite{uC++book}.
 Table \ref{lst:parfor} shows three different code examples that accomplish point-wise sums of large arrays.
+Table \ref{f:parfor} shows three different code examples that accomplish point-wise sums of large arrays.
 Note that none of these examples explicitly declare any concurrency or parallelism objects.
 …
 \end{center}
 \caption{For loop to sum numbers: Sequential, using library parallelism and language parallelism.}
 \label{lst:parfor}
+\label{f:parfor}
 \end{table}

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset 2ae16219 for doc/papers/concurrency/Paper.tex

Legend:

doc/papers/concurrency/Paper.tex

Download in other formats: